FastCollection


1   /*
2    * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
3    * Copyright (C) 2006 - Javolution (http://javolution.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package javolution.util;
10  
11  import j2me.util.Collection;
12  import j2me.util.Iterator;
13  import j2me.util.List;
14  import j2me.util.ListIterator;
15  import j2me.util.Set;
16  import j2me.io.Serializable;
17  import j2me.lang.UnsupportedOperationException;
18  import j2mex.realtime.MemoryArea;
19  
20  import javolution.Javolution;
21  import javolution.context.Realtime;
22  import javolution.context.RealtimeObject;
23  import javolution.lang.Reusable;
24  import javolution.text.Text;
25  import javolution.xml.XMLBinding;
26  import javolution.xml.XMLFormat;
27  import javolution.xml.stream.XMLStreamException;
28  
29  /**
30   * <p> This class represents collections which can quickly be iterated over 
31   *     (forward or backward) in a thread-safe manner without creating new 
32   *     objects and without using {@link #iterator iterators} . For example:[code]
33   *     boolean search(Object item, FastCollection c) {
34   *         for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
35   *              if (item.equals(c.valueOf(r))) return true;
36   *         }
37   *         return false;
38   *     }[/code]</p>
39   *     
40   * <p> Iterations are thread-safe as long as the {@link Record record} sequence
41   *     iterated over is not structurally modified by another thread 
42   *     (objects can safely be append/prepend during iterations but not 
43   *     inserted/removed).</p>
44   *     
45   * <p> Users may provide a read-only view of any {@link FastCollection} 
46   *     instance using the {@link #unmodifiable()} method (the view is 
47   *     thread-safe if iterations are thread-safe). For example:[code]
48   *     public class Polynomial {
49   *         private final FastTable<Coefficient> _coefficients = new FastTable<Coefficient>();
50   *         public List<Coefficient> getCoefficients() { // Read-only view. 
51   *             return _coefficients.unmodifiable();
52   *         }
53   *     }[/code]</p>
54   *     
55   * <p> Finally, {@link FastCollection} may use custom {@link #getValueComparator
56   *     comparators} for element equality or ordering if the collection is 
57   *     ordered (e.g. <code>FastTree</code>).
58   *     
59   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
60   * @version 4.2, December 18, 2006
61   */
62  public abstract class FastCollection/*<E>*/extends RealtimeObject implements
63          Collection/*<E>*/, Reusable, Serializable {
64  
65      /**
66       * Holds the default XML representation for FastCollection instances.
67       * This representation is identical to {@link XMLBinding#COLLECTION_XML}.
68       */
69      protected static final XMLFormat/*<FastCollection>*/ XML = new XMLFormat(
70              Javolution.j2meGetClass("javolution.util.FastCollection")) {
71  
72          public void read(InputElement xml, Object   obj) throws XMLStreamException {
73              FastCollection fc = (FastCollection) obj;
74              while (xml.hasNext()) {
75                  fc.add(xml.getNext());
76              }
77          }
78  
79          public void write(Object   obj, OutputElement xml) throws XMLStreamException {
80              FastCollection fc = (FastCollection) obj;
81              for (Record r=fc.head(), end=fc.tail(); (r=r.getNext())!=end;) {
82                  xml.add(fc.valueOf(r));
83              }
84          }
85      };
86  
87      /**
88       * Holds the unmodifiable view (allocated in the same memory area as 
89       * this collection).  
90       */
91      private Unmodifiable _unmodifiable;
92  
93      /**
94       * Default constructor.  
95       */
96      protected FastCollection() {
97      }
98  
99      /**
100      * Returns the number of values in this collection. 
101      *
102      * @return the number of values.
103      */
104     public abstract int size();
105 
106     /**
107      * Returns the head record of this collection; it is the record such as 
108      * <code>head().getNext()</code> holds the first collection value.
109      * 
110      * @return the head record.
111      */
112     public abstract Record head();
113 
114     /**
115      * Returns the tail record of this collection; it is the record such as
116      * <code>tail().getPrevious()</code> holds the last collection value.
117      * 
118      * @return the tail record.
119      */
120     public abstract Record tail();
121 
122     /**
123      * Returns the collection value for the specified record.
124      *
125      * @param record the record whose current value is returned.
126      * @return the current value.
127      */
128     public abstract Object  /*{E}*/valueOf(Record record);
129 
130     /**
131      * Deletes the specified record from this collection.
132      * 
133      * <p> Implementation must ensure that removing a record from the 
134      *     collection does not affect in any way the records preceding 
135      *     the record being removed (it might affect the next records though,
136      *     e.g. in a list collection, the indices of the subsequent records
137      *     will change).</p>   
138      *
139      * @param record the record to be removed.
140      * @throws UnsupportedOperationException if not supported.
141      */
142     public abstract void delete(Record record);
143 
144     /**
145      * Returns the unmodifiable view associated to this collection. 
146      * Attempts to modify the returned collection result in an 
147      * {@link UnsupportedOperationException} being thrown. The view is 
148      * typically part of the collection itself (created only once)
149      * and also an instance of {@link FastCollection} supporting direct
150      * iterations.  
151      * 
152      * @return the unmodifiable view over this collection.
153      */
154     public Collection/*<E>*/unmodifiable() {
155         if (_unmodifiable == null) {
156             MemoryArea.getMemoryArea(this).executeInArea(new Runnable  () {
157                 public void run() {
158                     _unmodifiable = new Unmodifiable();
159                 }
160             });
161         }
162         return _unmodifiable;
163     }
164 
165     /**
166      * Returns an iterator over the elements in this collection 
167      * (allocated on the stack when executed in a 
168      * {@link javolution.context.PoolContext PoolContext}).
169      *
170      * @return an iterator over this collection's elements.
171      */
172     public Iterator/*<E>*/iterator() {
173         return FastIterator.valueOf(this);
174     }
175 
176     /**
177      * Returns the value comparator for this collection (default 
178      * {@link FastComparator#DEFAULT}).
179      *
180      * @return the comparator to use for value equality (or ordering if 
181      *        the collection is ordered)
182      */
183     public FastComparator/*<? super E>*/ getValueComparator() {
184         return FastComparator.DEFAULT;
185     }
186 
187     /**
188      * Appends the specified value to the end of this collection
189      * (optional operation).
190      * 
191      * <p>Note: This default implementation always throws 
192      *          <code>UnsupportedOperationException</code>.</p>
193      * 
194      * @param value the value to be appended to this collection.
195      * @return <code>true</code> (as per the general contract of the
196      *         <code>Collection.add</code> method).
197      * @throws UnsupportedOperationException if not supported.
198      */
199     public boolean add(Object  /*{E}*/value) {
200         throw new UnsupportedOperationException  ();
201     }
202 
203     /**
204      * Removes the first occurrence in this collection of the specified value
205      * (optional operation).
206      *
207      * @param value the value to be removed from this collection.
208      * @return <code>true</code> if this collection contained the specified
209      *         value; <code>false</code> otherwise.
210      * @throws UnsupportedOperationException if not supported.
211      */
212     public boolean remove(Object   value) {
213         final FastComparator valueComp = this.getValueComparator();
214         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
215             if (valueComp.areEqual(value, valueOf(r))) {
216                 delete(r);
217                 return true;
218             }
219         }
220         return false;
221     }
222 
223     /**
224      * Removes all of the values from this collection (optional operation).
225      *
226      * @throws UnsupportedOperationException if not supported.
227      */
228     public void clear() {
229         // Removes last record until empty.
230         for (Record head = head(), r = tail().getPrevious(); r != head; r = r
231                 .getPrevious()) {
232             delete(r);
233         }
234     }
235 
236     /**
237      * Indicates if this collection is empty.
238      *
239      * @return <code>true</code> if this collection contains no value;
240      *         <code>false</code> otherwise.
241      */
242     public final boolean isEmpty() {
243         return size() == 0;
244     }
245 
246     /**
247      * Indicates if this collection contains the specified value.
248      *
249      * @param value the value whose presence in this collection 
250      *        is to be tested.
251      * @return <code>true</code> if this collection contains the specified
252      *         value;<code>false</code> otherwise.
253      */
254     public boolean contains(Object   value) {
255         final FastComparator valueComp = this.getValueComparator();
256         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
257             if (valueComp.areEqual(value, valueOf(r)))
258                 return true;
259         }
260         return false;
261     }
262 
263     /**
264      * Appends all of the values in the specified collection to the end of
265      * this collection, in the order that they are returned by the specified
266      * collection's iterator or the node order if the specified collection
267      * is a {@link FastCollection}.
268      *
269      * @param c collection whose values are to be added to this collection.
270      * @return <code>true</code> if this collection changed as a result of 
271      *         the call; <code>false</code> otherwise.
272      */
273     public boolean addAll(Collection/*<? extends E>*/c) {
274         if (c instanceof FastCollection)
275             return addAll((FastCollection) c);
276         boolean modified = false;
277         Iterator/*<? extends E>*/itr = c.iterator();
278         int pos = c.size();
279         while (--pos >= 0) {
280             if (add(itr.next())) {
281                 modified = true;
282             }
283         }
284         return modified;
285     }
286 
287     private boolean addAll(FastCollection/*<? extends E>*/c) {
288         if (c instanceof FastTable)
289             return addAll((FastTable) c);
290         boolean modified = false;
291         for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
292             if (this.add(c.valueOf(r))) {
293                 modified = true;
294             }
295         }
296         return modified;
297     }
298 
299     private boolean addAll(FastTable/*<? extends E>*/c) {
300         boolean modified = false;
301         for (int i=0, n = c.size(); i < n;) { // Faster than direct iterators.
302             if (this.add(c.get(i++))) {
303                 modified = true;
304             }
305         }
306         return modified;
307     }
308 
309     /**
310      * Indicates if this collection contains all of the values of the
311      * specified collection.
312      *
313      * @param  c collection to be checked for containment in this collection.
314      * @return <code>true</code> if this collection contains all of the values
315      *         of the specified collection; <code>false</code> otherwise.
316      */
317     public boolean containsAll(Collection/*<?>*/c) {
318         if (c instanceof FastCollection)
319             return containsAll((FastCollection) c);
320         Iterator/*<?>*/itr = c.iterator();
321         int pos = c.size();
322         while (--pos >= 0) {
323             if (!contains(itr.next())) {
324                 return false;
325             }
326         }
327         return true;
328     }
329 
330     private boolean containsAll(FastCollection/*<?>*/c) {
331         for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
332             if (!contains(c.valueOf(r))) {
333                 return false;
334             }
335         }
336         return true;
337     }
338 
339     /**
340      * Removes from this collection all the values that are contained in the
341      * specified collection.
342      *
343      * @param c collection that defines which values will be removed from
344      *          this collection.
345      * @return <code>true</code> if this collection changed as a result of 
346      *         the call; <code>false</code> otherwise.
347      */
348     public boolean removeAll(Collection/*<?>*/c) {
349         boolean modified = false;
350         // Iterates from the tail and removes the record if present in c. 
351         for (Record head = head(), r = tail().getPrevious(), previous; r != head; r = previous) {
352             previous = r.getPrevious(); // Saves previous.
353             if (c.contains(valueOf(r))) {
354                 delete(r);
355                 modified = true;
356             }
357         }
358         return modified;
359     }
360 
361     /**
362      * Retains only the values in this collection that are contained in the
363      * specified collection.
364      *
365      * @param c collection that defines which values this set will retain.
366      * @return <code>true</code> if this collection changed as a result of 
367      *         the call; <code>false</code> otherwise.
368      */
369     public boolean retainAll(Collection/*<?>*/c) {
370         boolean modified = false;
371         // Iterates from the tail and remove the record if not present in c. 
372         for (Record head = head(), r = tail().getPrevious(), previous; r != head; r = previous) {
373             previous = r.getPrevious(); // Saves previous.
374             if (!c.contains(valueOf(r))) {
375                 delete(r);
376                 modified = true;
377             }
378         }
379         return modified;
380     }
381 
382     /**
383      * Returns a new array allocated on the heap containing all of the values 
384      * in this collection in proper sequence.
385      * <p> Note: To avoid heap allocation {@link #toArray(Object[])} is 
386      *           recommended.</p> 
387      * @return <code>toArray(new Object[size()])</code>
388      */
389     public Object  [] toArray() {
390         return toArray(new Object  [size()]);
391     }
392 
393     /**
394      * Fills the specified array with the values of this collection in 
395      * the proper sequence.
396      *  
397      * <p> Note: Unlike standard Collection, this method does not try to resize
398      *           the array using reflection (which might not be supported) if 
399      *           the array is too small. UnsupportedOperationException is raised 
400      *           if the specified array is too small for this collection.</p>
401      *
402      * @param  array the array into which the values of this collection
403      *         are to be stored.
404      * @return the specified array.
405      * @throws UnsupportedOperationException if <code>array.length < size()</code> 
406      */
407     public Object  /*{<T> T}*/[] toArray(Object  /*{T}*/[] array) {
408         int size = size();
409         if (array.length < size)
410             throw new UnsupportedOperationException  (
411                     "Destination array too small");
412         if (array.length > size) {
413             array[size] = null; // As per Collection contract.
414         }
415         int i = 0;
416         Object  [] arrayView = array;
417         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
418             arrayView[i++] = valueOf(r);
419         }
420         return array;
421     }
422 
423     /**
424      * Returns the textual representation of this collection.
425      * 
426      * @return this collection textual representation.
427      */
428     public Text toText() {
429         final Text sep = Text.valueOf(", ");
430         Text text = Text.valueOf('[');
431         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
432             text = text.concat(Text.valueOf(valueOf(r)));
433             if (r.getNext() != end) {
434                 text = text.concat(sep);
435             }
436         }
437         return text.concat(Text.valueOf(']'));
438     }
439 
440     /**
441      * Compares the specified object with this collection for equality.  Returns
442      * <code>true</code> if and only both collection contains the same values
443      * regardless of the order; unless this collection is a list instance 
444      * in which case both collections must be list with the same order. 
445      *
446      * @param obj the object to be compared for equality with this collection.
447      * @return <code>true</code> if the specified object is equal to this
448      *         collection; <code>false</code> otherwise.
449      */
450     public boolean equals(Object   obj) {
451         if (this instanceof List)
452             return equalsList(obj);
453         return obj == this
454                 || (obj instanceof Collection
455                         && ((Collection) obj).size() == size() && containsAll((Collection) obj));
456     }
457 
458     private boolean equalsList(Object   obj) {
459         if (obj == this)
460             return true;
461         if (!(obj instanceof List)) 
462             return false;
463         if (obj instanceof FastCollection)
464             return equalsList((FastCollection)obj);
465         List that = (List) obj;
466         if (this.size() != that.size())
467             return false;
468         Iterator thatIterator = that.iterator();
469         final FastComparator comp = this.getValueComparator();
470         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
471             Object   o1 = valueOf(r);
472             Object   o2 = thatIterator.next();
473             if (!comp.areEqual(o1, o2))
474                 return false;
475         }
476         return true;
477     }
478 
479     private boolean equalsList(FastCollection that) {
480         if (this.size() != that.size())
481             return false;
482         Record t = that.head();
483         final FastComparator comp = this.getValueComparator();
484         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
485             Object   o1 = valueOf(r);
486             Object   o2 = that.valueOf(t = t.getNext());
487             if (!comp.areEqual(o1, o2))
488                 return false;
489         }
490         return true;
491     }
492 
493     /**
494      * Returns the hash code for this collection (independent from the 
495      * collection order; unless this collection is a list instance).
496      *
497      * @return the hash code for this collection.
498      */
499     public int hashCode() {
500         if (this instanceof List)
501             return hashCodeList();
502         final FastComparator valueComp = this.getValueComparator();
503         int hash = 0;
504         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
505             hash += valueComp.hashCodeOf(valueOf(r));
506         }
507         return hash;
508     }
509 
510     private int hashCodeList() {
511         final FastComparator comp = this.getValueComparator();
512         int h = 1;
513         for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
514             h = 31 * h + comp.hashCodeOf(valueOf(r));
515         }
516         return h;
517 
518     }
519 
520     // Implements Reusable.
521     public void reset() {
522         clear();
523     }
524 
525     // Overrides.
526     public boolean move(ObjectSpace os) {
527         if (super.move(os)) {
528             for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
529                 Object   obj = valueOf(r);
530                 if (obj instanceof Realtime) {
531                     ((Realtime)obj).move(os);
532                 }
533             }
534             return true;
535         }
536         return false;
537     }
538     
539     /**
540      * This interface represents the collection records which can directly be
541      * iterated over.
542      */
543     public interface Record {
544 
545         /**
546          * Returns the record before this one.
547          * 
548          * @return the previous record.
549          */
550         public Record getPrevious();
551 
552         /**
553          * Returns the record after this one.
554          * 
555          * @return the next record.
556          */
557         public Record getNext();
558 
559     }
560 
561     /**
562      * This inner class represents an unmodifiable view over the collection.
563      */
564     private final class Unmodifiable extends FastCollection implements
565             Set, List { // Allows to be used for unmodifiable set/list view.
566 
567         // Implements abstract method.
568         public int size() {
569             return FastCollection.this.size();
570         }
571 
572         // Implements abstract method.
573         public Record head() {
574             return FastCollection.this.head();
575         }
576 
577         // Implements abstract method.
578         public Record tail() {
579             return FastCollection.this.tail();
580         }
581 
582         // Implements abstract method.
583         public Object   valueOf(Record record) {
584             return FastCollection.this.valueOf(record);
585         }
586 
587         // Forwards...
588         public boolean contains(Object   value) {
589             return (FastCollection.this).contains(value);
590         }
591 
592         // Forwards...
593         public boolean containsAll(Collection c) {
594             return (FastCollection.this).containsAll(c);
595         }
596 
597         // Forwards...
598         public FastComparator getValueComparator() {
599             return FastCollection.this.getValueComparator();
600         }
601 
602         // Disallows...
603         public boolean add(Object   obj) {
604             throw new UnsupportedOperationException  ("Unmodifiable");
605         }
606 
607         // Disallows...
608         public void delete(Record node) {
609             throw new UnsupportedOperationException  ("Unmodifiable");
610         }
611 
612         //////////////////////////////////////////
613         // List interface supplementary methods //
614         //////////////////////////////////////////
615         
616         public boolean addAll(int index, Collection c) {
617             throw new UnsupportedOperationException  ("Unmodifiable");
618         }
619 
620         public Object   get(int index) {
621             return ((List)FastCollection.this).get(index);
622         }
623 
624         public Object   set(int index, Object   element) {
625             throw new UnsupportedOperationException  ("Unmodifiable");
626         }
627 
628         public void add(int index, Object   element) {
629             throw new UnsupportedOperationException  ("Unmodifiable");
630         }
631 
632         public Object   remove(int index) {
633             throw new UnsupportedOperationException  ("Unmodifiable");
634         }
635 
636         public int indexOf(Object   o) {
637             return ((List)FastCollection.this).indexOf(o);
638         }
639 
640         public int lastIndexOf(Object   o) {
641             return ((List)FastCollection.this).lastIndexOf(o);
642         }
643 
644         public ListIterator listIterator() {
645             throw new UnsupportedOperationException  (
646             "List iterator not supported for unmodifiable collection");
647         }
648 
649         public ListIterator listIterator(int index) {
650             throw new UnsupportedOperationException  (
651             "List iterator not supported for unmodifiable collection");
652         }
653 
654         public List subList(int fromIndex, int toIndex) {
655             throw new UnsupportedOperationException  (
656                     "Sub-List not supported for unmodifiable collection");
657         }
658     }
659 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags