001: /*
002: * Javolution - Java(TM) Solution for Real-Time and Embedded Systems
003: * Copyright (C) 2006 - Javolution (http://javolution.org/)
004: * All rights reserved.
005: *
006: * Permission to use, copy, modify, and distribute this software is
007: * freely granted, provided that this notice is preserved.
008: */
009: package javolution.util;
010:
011: import j2me.util.Collection;
012: import j2me.util.Iterator;
013: import j2me.util.List;
014: import j2me.util.ListIterator;
015: import j2me.util.Set;
016: import j2me.lang.UnsupportedOperationException;
017: import j2mex.realtime.MemoryArea;
018: import javolution.lang.Realtime;
019: import javolution.text.Text;
020: import javolution.xml.XMLSerializable;
021:
022: /**
023: * <p> This class represents collections which can quickly be iterated over
024: * (forward or backward) in a thread-safe manner without creating new
025: * objects and without using {@link #iterator iterators} . For example:[code]
026: * boolean search(Object item, FastCollection c) {
027: * for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
028: * if (item.equals(c.valueOf(r))) return true;
029: * }
030: * return false;
031: * }[/code]</p>
032: *
033: * <p> Iterations are thread-safe as long as the {@link Record record} sequence
034: * iterated over is not structurally modified by another thread
035: * (objects can safely be append/prepend during iterations but not
036: * inserted/removed).</p>
037: *
038: * <p> Users may provide a read-only view of any {@link FastCollection}
039: * instance using the {@link #unmodifiable()} method (the view is
040: * thread-safe if iterations are thread-safe). For example:[code]
041: * public class Polynomial {
042: * private final FastTable<Coefficient> _coefficients = new FastTable<Coefficient>();
043: * public List<Coefficient> getCoefficients() { // Read-only view.
044: * return _coefficients.unmodifiable();
045: * }
046: * }[/code]</p>
047: *
048: * <p> Finally, {@link FastCollection} may use custom {@link #getValueComparator
049: * comparators} for element equality or ordering if the collection is
050: * ordered (e.g. <code>FastTree</code>).
051: *
052: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
053: * @version 4.2, December 18, 2006
054: */
055: public abstract class FastCollection/*<E>*/implements
056: Collection/*<E>*/, XMLSerializable, Realtime {
057:
058: /**
059: * Holds the unmodifiable view (allocated in the same memory area as
060: * this collection).
061: */
062: private Unmodifiable _unmodifiable;
063:
064: /**
065: * Default constructor.
066: */
067: protected FastCollection() {
068: }
069:
070: /**
071: * Returns the number of values in this collection.
072: *
073: * @return the number of values.
074: */
075: public abstract int size();
076:
077: /**
078: * Returns the head record of this collection; it is the record such as
079: * <code>head().getNext()</code> holds the first collection value.
080: *
081: * @return the head record.
082: */
083: public abstract Record head();
084:
085: /**
086: * Returns the tail record of this collection; it is the record such as
087: * <code>tail().getPrevious()</code> holds the last collection value.
088: *
089: * @return the tail record.
090: */
091: public abstract Record tail();
092:
093: /**
094: * Returns the collection value for the specified record.
095: *
096: * @param record the record whose current value is returned.
097: * @return the current value.
098: */
099: public abstract Object/*{E}*/valueOf(Record record);
100:
101: /**
102: * Deletes the specified record from this collection.
103: *
104: * <p> Implementation must ensure that removing a record from the
105: * collection does not affect in any way the records preceding
106: * the record being removed (it might affect the next records though,
107: * e.g. in a list collection, the indices of the subsequent records
108: * will change).</p>
109: *
110: * @param record the record to be removed.
111: * @throws UnsupportedOperationException if not supported.
112: */
113: public abstract void delete(Record record);
114:
115: /**
116: * Returns the unmodifiable view associated to this collection.
117: * Attempts to modify the returned collection result in an
118: * {@link UnsupportedOperationException} being thrown. The view is
119: * typically part of the collection itself (created only once)
120: * and also an instance of {@link FastCollection} supporting direct
121: * iterations.
122: *
123: * @return the unmodifiable view over this collection.
124: */
125: public Collection/*<E>*/unmodifiable() {
126: if (_unmodifiable == null) {
127: MemoryArea.getMemoryArea(this ).executeInArea(
128: new Runnable() {
129: public void run() {
130: _unmodifiable = new Unmodifiable();
131: }
132: });
133: }
134: return _unmodifiable;
135: }
136:
137: /**
138: * Returns an iterator over the elements in this collection
139: * (allocated on the stack when executed in a
140: * {@link javolution.context.StackContext StackContext}).
141: *
142: * @return an iterator over this collection's elements.
143: */
144: public Iterator/*<E>*/iterator() {
145: return FastIterator.valueOf(this );
146: }
147:
148: /**
149: * Returns the value comparator for this collection (default
150: * {@link FastComparator#DEFAULT}).
151: *
152: * @return the comparator to use for value equality (or ordering if
153: * the collection is ordered)
154: */
155: public FastComparator/*<? super E>*/getValueComparator() {
156: return FastComparator.DEFAULT;
157: }
158:
159: /**
160: * Appends the specified value to the end of this collection
161: * (optional operation).
162: *
163: * <p>Note: This default implementation always throws
164: * <code>UnsupportedOperationException</code>.</p>
165: *
166: * @param value the value to be appended to this collection.
167: * @return <code>true</code> (as per the general contract of the
168: * <code>Collection.add</code> method).
169: * @throws UnsupportedOperationException if not supported.
170: */
171: public boolean add(Object/*{E}*/value) {
172: throw new UnsupportedOperationException();
173: }
174:
175: /**
176: * Removes the first occurrence in this collection of the specified value
177: * (optional operation).
178: *
179: * @param value the value to be removed from this collection.
180: * @return <code>true</code> if this collection contained the specified
181: * value; <code>false</code> otherwise.
182: * @throws UnsupportedOperationException if not supported.
183: */
184: public boolean remove(Object value) {
185: final FastComparator valueComp = this .getValueComparator();
186: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
187: if (valueComp.areEqual(value, valueOf(r))) {
188: delete(r);
189: return true;
190: }
191: }
192: return false;
193: }
194:
195: /**
196: * Removes all of the values from this collection (optional operation).
197: *
198: * @throws UnsupportedOperationException if not supported.
199: */
200: public void clear() {
201: // Removes last record until empty.
202: for (Record head = head(), r = tail().getPrevious(); r != head; r = r
203: .getPrevious()) {
204: delete(r);
205: }
206: }
207:
208: /**
209: * Indicates if this collection is empty.
210: *
211: * @return <code>true</code> if this collection contains no value;
212: * <code>false</code> otherwise.
213: */
214: public final boolean isEmpty() {
215: return size() == 0;
216: }
217:
218: /**
219: * Indicates if this collection contains the specified value.
220: *
221: * @param value the value whose presence in this collection
222: * is to be tested.
223: * @return <code>true</code> if this collection contains the specified
224: * value;<code>false</code> otherwise.
225: */
226: public boolean contains(Object value) {
227: final FastComparator valueComp = this .getValueComparator();
228: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
229: if (valueComp.areEqual(value, valueOf(r)))
230: return true;
231: }
232: return false;
233: }
234:
235: /**
236: * Appends all of the values in the specified collection to the end of
237: * this collection, in the order that they are returned by the specified
238: * collection's iterator or the node order if the specified collection
239: * is a {@link FastCollection}.
240: *
241: * @param c collection whose values are to be added to this collection.
242: * @return <code>true</code> if this collection changed as a result of
243: * the call; <code>false</code> otherwise.
244: */
245: public boolean addAll(Collection/*<? extends E>*/c) {
246: if (c instanceof FastCollection)
247: return addAll((FastCollection) c);
248: boolean modified = false;
249: Iterator/*<? extends E>*/itr = c.iterator();
250: int pos = c.size();
251: while (--pos >= 0) {
252: if (add(itr.next())) {
253: modified = true;
254: }
255: }
256: return modified;
257: }
258:
259: private boolean addAll(FastCollection/*<? extends E>*/c) {
260: if (c instanceof FastTable)
261: return addAll((FastTable) c);
262: boolean modified = false;
263: for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
264: if (this .add(c.valueOf(r))) {
265: modified = true;
266: }
267: }
268: return modified;
269: }
270:
271: private boolean addAll(FastTable/*<? extends E>*/c) {
272: boolean modified = false;
273: for (int i = 0, n = c.size(); i < n;) { // Faster than direct iterators.
274: if (this .add(c.get(i++))) {
275: modified = true;
276: }
277: }
278: return modified;
279: }
280:
281: /**
282: * Indicates if this collection contains all of the values of the
283: * specified collection.
284: *
285: * @param c collection to be checked for containment in this collection.
286: * @return <code>true</code> if this collection contains all of the values
287: * of the specified collection; <code>false</code> otherwise.
288: */
289: public boolean containsAll(Collection/*<?>*/c) {
290: if (c instanceof FastCollection)
291: return containsAll((FastCollection) c);
292: Iterator/*<?>*/itr = c.iterator();
293: int pos = c.size();
294: while (--pos >= 0) {
295: if (!contains(itr.next())) {
296: return false;
297: }
298: }
299: return true;
300: }
301:
302: private boolean containsAll(FastCollection/*<?>*/c) {
303: for (Record r = c.head(), end = c.tail(); (r = r.getNext()) != end;) {
304: if (!contains(c.valueOf(r))) {
305: return false;
306: }
307: }
308: return true;
309: }
310:
311: /**
312: * Removes from this collection all the values that are contained in the
313: * specified collection.
314: *
315: * @param c collection that defines which values will be removed from
316: * this collection.
317: * @return <code>true</code> if this collection changed as a result of
318: * the call; <code>false</code> otherwise.
319: */
320: public boolean removeAll(Collection/*<?>*/c) {
321: boolean modified = false;
322: // Iterates from the tail and removes the record if present in c.
323: for (Record head = head(), r = tail().getPrevious(), previous; r != head; r = previous) {
324: previous = r.getPrevious(); // Saves previous.
325: if (c.contains(valueOf(r))) {
326: delete(r);
327: modified = true;
328: }
329: }
330: return modified;
331: }
332:
333: /**
334: * Retains only the values in this collection that are contained in the
335: * specified collection.
336: *
337: * @param c collection that defines which values this set will retain.
338: * @return <code>true</code> if this collection changed as a result of
339: * the call; <code>false</code> otherwise.
340: */
341: public boolean retainAll(Collection/*<?>*/c) {
342: boolean modified = false;
343: // Iterates from the tail and remove the record if not present in c.
344: for (Record head = head(), r = tail().getPrevious(), previous; r != head; r = previous) {
345: previous = r.getPrevious(); // Saves previous.
346: if (!c.contains(valueOf(r))) {
347: delete(r);
348: modified = true;
349: }
350: }
351: return modified;
352: }
353:
354: /**
355: * Returns a new array allocated on the heap containing all of the values
356: * in this collection in proper sequence.
357: * <p> Note: To avoid heap allocation {@link #toArray(Object[])} is
358: * recommended.</p>
359: * @return <code>toArray(new Object[size()])</code>
360: */
361: public Object[] toArray() {
362: return toArray(new Object[size()]);
363: }
364:
365: /**
366: * Fills the specified array with the values of this collection in
367: * the proper sequence.
368: *
369: * <p> Note: Unlike standard Collection, this method does not try to resize
370: * the array using reflection (which might not be supported) if
371: * the array is too small. UnsupportedOperationException is raised
372: * if the specified array is too small for this collection.</p>
373: *
374: * @param array the array into which the values of this collection
375: * are to be stored.
376: * @return the specified array.
377: * @throws UnsupportedOperationException if <code>array.length < size()</code>
378: */
379: public Object/*{<T> T}*/[] toArray(Object/*{T}*/[] array) {
380: int size = size();
381: if (array.length < size)
382: throw new UnsupportedOperationException(
383: "Destination array too small");
384: if (array.length > size) {
385: array[size] = null; // As per Collection contract.
386: }
387: int i = 0;
388: Object[] arrayView = array;
389: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
390: arrayView[i++] = valueOf(r);
391: }
392: return array;
393: }
394:
395: /**
396: * Returns the textual representation of this collection.
397: *
398: * @return this collection textual representation.
399: */
400: public Text toText() {
401: Text text = Text.valueOf("[");
402: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
403: text = text.plus(valueOf(r));
404: if (r.getNext() != end) {
405: text = text.plus(", ");
406: }
407: }
408: return text.plus("]");
409: }
410:
411: /**
412: * Returns the <code>String</code> representation of this
413: * {@link FastCollection}.
414: *
415: * @return <code>toText().toString()</code>
416: */
417: public final String toString() {
418: return toText().toString();
419: }
420:
421: /**
422: * Compares the specified object with this collection for equality. Returns
423: * <code>true</code> if and only both collection contains the same values
424: * regardless of the order; unless this collection is a list instance
425: * in which case both collections must be list with the same order.
426: *
427: * @param obj the object to be compared for equality with this collection.
428: * @return <code>true</code> if the specified object is equal to this
429: * collection; <code>false</code> otherwise.
430: */
431: public boolean equals(Object obj) {
432: if (this instanceof List)
433: return equalsList(obj);
434: return obj == this
435: || (obj instanceof Collection
436: && ((Collection) obj).size() == size() && containsAll((Collection) obj));
437: }
438:
439: private boolean equalsList(Object obj) {
440: if (obj == this )
441: return true;
442: if (!(obj instanceof List))
443: return false;
444: if (obj instanceof FastCollection)
445: return equalsList((FastCollection) obj);
446: List that = (List) obj;
447: if (this .size() != that.size())
448: return false;
449: Iterator thatIterator = that.iterator();
450: final FastComparator comp = this .getValueComparator();
451: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
452: Object o1 = valueOf(r);
453: Object o2 = thatIterator.next();
454: if (!comp.areEqual(o1, o2))
455: return false;
456: }
457: return true;
458: }
459:
460: private boolean equalsList(FastCollection that) {
461: if (this .size() != that.size())
462: return false;
463: Record t = that.head();
464: final FastComparator comp = this .getValueComparator();
465: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
466: Object o1 = valueOf(r);
467: Object o2 = that.valueOf(t = t.getNext());
468: if (!comp.areEqual(o1, o2))
469: return false;
470: }
471: return true;
472: }
473:
474: /**
475: * Returns the hash code for this collection (independent from the
476: * collection order; unless this collection is a list instance).
477: *
478: * @return the hash code for this collection.
479: */
480: public int hashCode() {
481: if (this instanceof List)
482: return hashCodeList();
483: final FastComparator valueComp = this .getValueComparator();
484: int hash = 0;
485: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
486: hash += valueComp.hashCodeOf(valueOf(r));
487: }
488: return hash;
489: }
490:
491: private int hashCodeList() {
492: final FastComparator comp = this .getValueComparator();
493: int h = 1;
494: for (Record r = head(), end = tail(); (r = r.getNext()) != end;) {
495: h = 31 * h + comp.hashCodeOf(valueOf(r));
496: }
497: return h;
498:
499: }
500:
501: /**
502: * This interface represents the collection records which can directly be
503: * iterated over.
504: */
505: public interface Record {
506:
507: /**
508: * Returns the record before this one.
509: *
510: * @return the previous record.
511: */
512: public Record getPrevious();
513:
514: /**
515: * Returns the record after this one.
516: *
517: * @return the next record.
518: */
519: public Record getNext();
520:
521: }
522:
523: /**
524: * This inner class represents an unmodifiable view over the collection.
525: */
526: private final class Unmodifiable extends FastCollection implements
527: Set, List { // Allows to be used for unmodifiable set/list view.
528:
529: // Implements abstract method.
530: public int size() {
531: return FastCollection.this .size();
532: }
533:
534: // Implements abstract method.
535: public Record head() {
536: return FastCollection.this .head();
537: }
538:
539: // Implements abstract method.
540: public Record tail() {
541: return FastCollection.this .tail();
542: }
543:
544: // Implements abstract method.
545: public Object valueOf(Record record) {
546: return FastCollection.this .valueOf(record);
547: }
548:
549: // Forwards...
550: public boolean contains(Object value) {
551: return (FastCollection.this ).contains(value);
552: }
553:
554: // Forwards...
555: public boolean containsAll(Collection c) {
556: return (FastCollection.this ).containsAll(c);
557: }
558:
559: // Forwards...
560: public FastComparator getValueComparator() {
561: return FastCollection.this .getValueComparator();
562: }
563:
564: // Disallows...
565: public boolean add(Object obj) {
566: throw new UnsupportedOperationException("Unmodifiable");
567: }
568:
569: // Disallows...
570: public void delete(Record node) {
571: throw new UnsupportedOperationException("Unmodifiable");
572: }
573:
574: //////////////////////////////////////////
575: // List interface supplementary methods //
576: //////////////////////////////////////////
577:
578: public boolean addAll(int index, Collection c) {
579: throw new UnsupportedOperationException("Unmodifiable");
580: }
581:
582: public Object get(int index) {
583: return ((List) FastCollection.this ).get(index);
584: }
585:
586: public Object set(int index, Object element) {
587: throw new UnsupportedOperationException("Unmodifiable");
588: }
589:
590: public void add(int index, Object element) {
591: throw new UnsupportedOperationException("Unmodifiable");
592: }
593:
594: public Object remove(int index) {
595: throw new UnsupportedOperationException("Unmodifiable");
596: }
597:
598: public int indexOf(Object o) {
599: return ((List) FastCollection.this ).indexOf(o);
600: }
601:
602: public int lastIndexOf(Object o) {
603: return ((List) FastCollection.this ).lastIndexOf(o);
604: }
605:
606: public ListIterator listIterator() {
607: throw new UnsupportedOperationException(
608: "List iterator not supported for unmodifiable collection");
609: }
610:
611: public ListIterator listIterator(int index) {
612: throw new UnsupportedOperationException(
613: "List iterator not supported for unmodifiable collection");
614: }
615:
616: public List subList(int fromIndex, int toIndex) {
617: throw new UnsupportedOperationException(
618: "Sub-List not supported for unmodifiable collection");
619: }
620: }
621: }
|