001: // Copyright (c) 2001, 2002, 2003, 2005 Per M.A. Bothner and Brainfood Inc.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.lists;
005:
006: import java.util.*;
007:
008: /**
009: * An AbstractSequence is used to implement Sequences, and almost all
010: * classes that extend AbstractSequence will implement Sequence.
011: * However, AbstractSequence itself does not implement Sequence.
012: * This is so we can use AbstractSequence to implement classes that are
013: * "sequence-like" (such as multi-dimesnional arrays) but are not Sequences.
014: *
015: * Additionally, a sequence may have zero or more attributes, which are
016: * name-value pairs. A sequence may also have a named "type". These
017: * extensions are to support XML functionality - it might be cleaner to
018: * moe them to a sub-class of Sequence or some interface.
019: *
020: * Many of the protected methods in Sequence (such as nextIndex) are
021: * only intended to be called from SeqPosition or TreePosition, see those.
022: *
023: * @author Per Bothner
024: */
025:
026: public abstract class AbstractSequence {
027: /** See java.util.List. */
028: public abstract int size();
029:
030: public boolean isEmpty() {
031: return size() == 0;
032: }
033:
034: public int rank() {
035: return 1;
036: }
037:
038: /** See java.util.List. */
039: public abstract Object get(int index);
040:
041: public int getEffectiveIndex(int[] indexes) {
042: return indexes[0];
043: }
044:
045: public Object get(int[] indexes) {
046: return get(indexes[0]);
047: }
048:
049: public Object set(int[] indexes, Object value) {
050: return set(indexes[0], value);
051: }
052:
053: public int getLowBound(int dim) {
054: return 0;
055: }
056:
057: public int getSize(int dim) {
058: return dim == 0 ? size() : 1;
059: }
060:
061: protected RuntimeException unsupported(String text) {
062: return unsupportedException(getClass().getName()
063: + " does not implement " + text);
064: }
065:
066: public static RuntimeException unsupportedException(String text) {
067: /* #ifdef JAVA2 */
068: return new UnsupportedOperationException(text);
069: /* #endif */
070: /* #ifndef JAVA2 */
071: // return new RuntimeException(text);
072: /* #endif */
073: }
074:
075: public Object set(int index, Object element) {
076: throw unsupported("set");
077: }
078:
079: public void fill(Object value) {
080: for (int i = startPos(); (i = nextPos(i)) != 0;)
081: setPosPrevious(i, value);
082: }
083:
084: public void fillPosRange(int fromPos, int toPos, Object value) {
085: int i = copyPos(fromPos);
086: for (; compare(i, toPos) < 0; i = nextPos(i))
087: setPosNext(i, value);
088: releasePos(i);
089: }
090:
091: public void fill(int fromIndex, int toIndex, Object value) {
092: int i = createPos(fromIndex, false);
093: int limit = createPos(toIndex, true);
094: for (; compare(i, limit) < 0; i = nextPos(i))
095: setPosNext(i, value);
096: releasePos(i);
097: releasePos(limit);
098: }
099:
100: // FIXME?
101: //public final Object elementAt (int index) { return get(index); }
102:
103: /** See java.util.List. */
104: public int indexOf(Object o) {
105: int i = 0;
106: for (int iter = startPos(); (iter = nextPos(iter)) != 0; i++) {
107: Object v = getPosPrevious(iter);
108: if (o == null ? v == null : o.equals(v)) {
109: releasePos(iter);
110: return i;
111: }
112: }
113: return -1;
114: }
115:
116: /** See java.util.List. */
117: public int lastIndexOf(Object o) {
118: // FIXME use iterator?
119: for (int n = size(); --n >= 0;) {
120: Object e = get(n);
121: if (o == null ? e == null : o.equals(e))
122: return n;
123: }
124: return -1;
125: }
126:
127: /** Get next matching child or descendent (ignoring attributes).
128: * @param startPos starting position
129: * @param type a test (predicate) to apply to selected elements
130: * @param endPos stop before endPos
131: * @param descend if true do depth-first traversal.
132: * @return poistion of next match or 0 if none found
133: */
134: public int nextMatching(int startPos, ItemPredicate type,
135: int endPos, boolean descend) {
136: if (descend)
137: throw unsupported("nextMatching with descend");
138: int ipos = startPos;
139: for (;;) {
140: if (compare(ipos, endPos) >= 0)
141: return 0;
142: ipos = nextPos(ipos);
143: if (type.isInstancePos(this , ipos))
144: return ipos;
145: }
146: }
147:
148: /** See java.util.List. */
149: public boolean contains(Object o) {
150: return indexOf(o) >= 0;
151: }
152:
153: /* #ifdef JAVA2 */
154: /** See java.util.List. */
155: public boolean containsAll(Collection c) {
156: Iterator i = c.iterator();
157: while (i.hasNext()) {
158: Object e = i.next();
159: if (!contains(e))
160: return false;
161: }
162: return true;
163: }
164:
165: /* #endif */
166:
167: public final Enumeration elements() {
168: return getIterator();
169: }
170:
171: public final SeqPosition getIterator() {
172: return getIterator(0);
173: }
174:
175: public SeqPosition getIterator(int index) {
176: return new SeqPosition(this , index, false);
177: }
178:
179: public SeqPosition getIteratorAtPos(int ipos) {
180: return new SeqPosition(this , copyPos(ipos));
181: }
182:
183: /* #ifdef JAVA2 */
184: public final Iterator iterator() {
185: return getIterator();
186: }
187:
188: public final ListIterator listIterator() {
189: return getIterator(0);
190: }
191:
192: public final ListIterator listIterator(int index) {
193: return getIterator(index);
194: }
195:
196: /* #endif */
197:
198: /** Add a value at a specified Pos.
199: * @return the updated Pos, which is after the inserted value..
200: */
201: protected int addPos(int ipos, Object value) {
202: throw unsupported("addPos");
203: }
204:
205: /** See java.util.Collection. */
206: public boolean add(Object o) {
207: addPos(endPos(), o);
208: return true;
209: }
210:
211: /** See java.util.List. */
212: public void add(int index, Object o) {
213: int pos = createPos(index, false);
214: addPos(pos, o);
215: releasePos(pos);
216: }
217:
218: /* #ifdef JAVA2 */
219: /** See java.util.Collection. */
220: public boolean addAll(Collection c) {
221: return addAll(size(), c);
222: }
223:
224: /** See java.util.Collection. */
225: public boolean addAll(int index, Collection c) {
226: boolean changed = false;
227: int pos = createPos(index, false);
228: for (Iterator it = c.iterator(); it.hasNext();) {
229: pos = addPos(pos, it.next());
230: changed = true;
231: }
232: releasePos(pos);
233: return changed;
234: }
235:
236: /* #endif */
237: /* #ifndef JAVA2 */
238: // public boolean addAll(Sequence c)
239: // {
240: // return addAll(size(), c);
241: // }
242: // public boolean addAll(int index, Sequence c)
243: // {
244: // boolean changed = false;
245: // int pos = createPos(index, false);
246: // for (int iter = startPos(); (iter = nextPos(iter)) != 0; )
247: // {
248: // pos = addPos(pos, getPosPrevious(iter));
249: // changed = true;
250: // }
251: // releasePos(pos);
252: // return changed;
253: // }
254: /* #endif */
255:
256: /**
257: * Remove one or more elements.
258: * @param ipos position where elements should be removed
259: * @param count if non-negative, remove that number of elements
260: * following (poses, posNumber); if negative the negative of the number
261: * of elements to remove before (poses, posNumber).
262: * @exception java.lang.IndexOutOfBoundsException
263: * if (count >= 0 ? (index < 0 || index + count > size())
264: * : (index + count < 0 || index > size())),
265: * where index == nextIndex(ipos, xpos).
266: */
267: public void removePos(int ipos, int count) {
268: int rpos = createRelativePos(ipos, count, false);
269: if (count >= 0)
270: removePosRange(ipos, rpos);
271: else
272: removePosRange(rpos, ipos);
273: releasePos(rpos);
274: }
275:
276: /** Remove a range where each end-point is a position in a container.
277: * @param ipos0 start of range, as a poistion
278: * @param ipos1 end of range
279: * @exception java.lang.IndexOutOfBoundsException
280: * if nextIndex(ipos0) > nextIndex(ipos1)
281: * || nextIndex(ipos0) < 0 || nextIndex(ipos1) > size()
282: */
283: protected void removePosRange(int ipos0, int ipos1) {
284: throw unsupported("removePosRange");
285: }
286:
287: public Object remove(int index) {
288: if (index < 0 || index >= size())
289: throw new IndexOutOfBoundsException();
290: int ipos = createPos(index, false);
291: Object result = getPosNext(ipos);
292: removePos(ipos, 1);
293: releasePos(ipos);
294: return result;
295: }
296:
297: public boolean remove(Object o) {
298: int index = indexOf(o);
299: if (index < 0)
300: return false;
301: int ipos = createPos(index, false);
302: removePos(ipos, 1);
303: releasePos(ipos);
304: return true;
305: }
306:
307: /* #ifdef JAVA2 */
308: public boolean removeAll(Collection c) {
309: boolean changed = false;
310: for (int iter = startPos(); (iter = nextPos(iter)) != 0;) {
311: Object value = getPosPrevious(iter);
312: if (c.contains(value)) {
313: removePos(iter, -1);
314: changed = true;
315: }
316: }
317: return changed;
318: }
319:
320: public boolean retainAll(Collection c) {
321: boolean changed = false;
322: for (int iter = startPos(); (iter = nextPos(iter)) != 0;) {
323: Object value = getPosPrevious(iter);
324: if (!c.contains(value)) {
325: removePos(iter, -1);
326: changed = true;
327: }
328: }
329: return changed;
330: }
331:
332: /* #endif */
333:
334: public void clear() {
335: removePos(startPos(), endPos());
336: }
337:
338: /** Tests whether the position has the "isAfter" property.
339: * I.e. if something is inserted at the position, will
340: * the iterator end up being after the new data? */
341: protected boolean isAfterPos(int ipos) {
342: return (ipos & 1) != 0;
343: }
344:
345: /** Generate a position at a given index.
346: * The result is a position cookie that must be free'd with releasePos.
347: * @param index offset from beginning of desired position
348: * @param isAfter should the position have the isAfter property
349: * @exception IndexOutOfBoundsException if index is out of bounds
350: */
351: public abstract int createPos(int index, boolean isAfter);
352:
353: public int createRelativePos(int pos, int delta, boolean isAfter) {
354: return createPos(nextIndex(pos) + delta, isAfter);
355: }
356:
357: public int startPos() {
358: return 0;
359: }
360:
361: public int endPos() {
362: return -1;
363: }
364:
365: /**
366: * Reclaim any resources used by the given position int.
367: * @param ipos the Pos being free'd.
368: */
369: protected void releasePos(int ipos) {
370: }
371:
372: /** Make a copy of a position int.
373: * For simple positions returns the argument.
374: * However, if the positions are magic cookies that are actively managed
375: * by the sequence (as opposed to for example a simple index), then making
376: * a copy may need to increment a reference count, or maybe allocate a
377: * new position cookie. In any case, the new position is initialized to
378: * the same offset (and isAfter property) as the original.
379: * @param ipos the position being copied.
380: * @return the new position
381: */
382: public int copyPos(int ipos) {
383: return ipos;
384: }
385:
386: /** Get offset of (ipos1) relative to (ipos0). */
387: protected int getIndexDifference(int ipos1, int ipos0) {
388: return nextIndex(ipos1) - nextIndex(ipos0);
389: }
390:
391: /**
392: * Get the offset from the beginning corresponding to a position cookie.
393: */
394: protected int nextIndex(int ipos) {
395: return getIndexDifference(ipos, startPos());
396: }
397:
398: protected int fromEndIndex(int ipos) {
399: return size() - nextIndex(ipos);
400: }
401:
402: /**
403: * Get the size of the (sub-) sequence containing a given position.
404: * Normally the same as size(), but may be different if this Sequence
405: * is a tree and the position points at an interior node.
406: */
407: protected int getContainingSequenceSize(int ipos) {
408: return size();
409: }
410:
411: public boolean hasNext(int ipos) {
412: return nextIndex(ipos) != size();
413: }
414:
415: public int getNextKind(int ipos) {
416: return hasNext(ipos) ? Sequence.OBJECT_VALUE
417: : Sequence.EOF_VALUE;
418: }
419:
420: public String getNextTypeName(int ipos) {
421: return null;
422: }
423:
424: public Object getNextTypeObject(int ipos) {
425: return null;
426: }
427:
428: /** Called by SeqPosition.hasPrevious. */
429: protected boolean hasPrevious(int ipos) {
430: return nextIndex(ipos) != 0;
431: }
432:
433: /** Return the next position following the argument.
434: * The new position has the isAfter property.
435: * The argument is implicitly released (as in releasePos).
436: * Returns 0 if we are already at end of file.
437: */
438: public int nextPos(int ipos) {
439: if (!hasNext(ipos))
440: return 0;
441: int next = createRelativePos(ipos, 1, true);
442: releasePos(ipos);
443: return next;
444: }
445:
446: /** Return the previous position following the argument.
447: * The new position has the isBefore property.
448: * The argument is implicitly released (as in releasePos).
449: * Returns -1 if we are already at beginning of file.
450: */
451: public int previousPos(int ipos) {
452: if (!hasPrevious(ipos))
453: return 0;
454: int next = createRelativePos(ipos, -1, false);
455: releasePos(ipos);
456: return next;
457: }
458:
459: /** Set position before first child (of the element following position).
460: * @return true if there is a child sequence (which might be empty);
461: * false if current position is end of sequence or following element
462: * is atomic (cannot have children).
463: */
464: public final boolean gotoChildrenStart(TreePosition pos) {
465: int ipos = firstChildPos(pos.getPos());
466: if (ipos == 0)
467: return false;
468: pos.push(this , ipos);
469: return true;
470: }
471:
472: /** Get position before first child (of the element following position).
473: * @param ipos parent position. It is not released by this method.
474: * @return non-zero position cookie if there is a child sequence
475: * (which might be empty); zero if current position is end of sequence
476: * or following element is atomic (cannot have children).
477: */
478: public int firstChildPos(int ipos) {
479: return 0;
480: }
481:
482: public int firstChildPos(int ipos, ItemPredicate predicate) {
483: int child = firstChildPos(ipos);
484: if (child == 0)
485: return 0;
486: if (predicate.isInstancePos(this , child))
487: return child;
488: else
489: return nextMatching(child, predicate, endPos(), false);
490: }
491:
492: /** Like firstChildPos.
493: * Problem: Should this stop before we get to children?
494: * I think so, but that requires changes to TreeList. */
495: public int firstAttributePos(int ipos) {
496: return 0;
497: }
498:
499: /** Get position of parent.
500: * @param ipos child position. It is not released by this method.
501: * @return the p os of the parent, or endPos() is there is no known parent.
502: */
503: public int parentPos(int ipos) {
504: return endPos();
505: }
506:
507: protected boolean gotoParent(TreePosition pos) {
508: if (pos.depth < 0)
509: return false;
510: pos.pop();
511: return true;
512: }
513:
514: public int getAttributeLength() {
515: return 0;
516: }
517:
518: public Object getAttribute(int index) {
519: return null;
520: }
521:
522: protected boolean gotoAttributesStart(TreePosition pos) {
523: return false;
524: }
525:
526: /** Get the element following the specified position.
527: * @param ipos the specified position.
528: * @return the following element, or eofValue if there is none.
529: * Called by SeqPosition.getNext. */
530: public Object getPosNext(int ipos) {
531: if (!hasNext(ipos))
532: return Sequence.eofValue;
533: return get(nextIndex(ipos));
534: }
535:
536: /** Get the element before the specified position.
537: * @param ipos the specified position.
538: * @return the following element, or eofValue if there is none. */
539: public Object getPosPrevious(int ipos) {
540: int index = nextIndex(ipos);
541: if (index <= 0)
542: return Sequence.eofValue;
543: return get(index - 1);
544: }
545:
546: protected void setPosNext(int ipos, Object value) {
547: int index = nextIndex(ipos);
548: if (index >= size())
549: throw new IndexOutOfBoundsException();
550: set(index, value);
551: }
552:
553: protected void setPosPrevious(int ipos, Object value) {
554: int index = nextIndex(ipos);
555: if (index == 0)
556: throw new IndexOutOfBoundsException();
557: set(index - 1, value);
558: }
559:
560: public final int nextIndex(SeqPosition pos) {
561: return nextIndex(pos.ipos);
562: }
563:
564: /** Compare two positions, and indicate if they are the same position. */
565: public boolean equals(int ipos1, int ipos2) {
566: return compare(ipos1, ipos2) == 0;
567: }
568:
569: /** Compare two positions, and indicate their relative order. */
570: public int compare(int ipos1, int ipos2) {
571: int i1 = nextIndex(ipos1);
572: int i2 = nextIndex(ipos2);
573: return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
574: }
575:
576: public final int compare(SeqPosition i1, SeqPosition i2) {
577: return compare(i1.ipos, i2.ipos);
578: }
579:
580: public Object[] toArray() {
581: int len = size();
582: Object[] arr = new Object[len];
583: int it = startPos();
584: int i = 0;
585: while ((it = nextPos(it)) != 0)
586: arr[i++] = getPosPrevious(it);
587: return arr;
588: }
589:
590: public Object[] toArray(Object[] arr) {
591: int alen = arr.length;
592: int len = size();
593: if (len > alen) {
594: Class componentType = arr.getClass().getComponentType();
595: arr = (Object[]) java.lang.reflect.Array.newInstance(
596: componentType, len);
597: alen = len;
598: }
599:
600: int it = startPos();
601: for (int i = 0; (it = nextPos(it)) != 0; i++) {
602: arr[i] = getPosPrevious(it);
603: }
604: if (len < alen)
605: arr[len] = null;
606: return arr;
607: }
608:
609: /** This is used for the XML concept of "document order". */
610: public int stableCompare(AbstractSequence other) {
611: int id1 = System.identityHashCode(this );
612: int id2 = System.identityHashCode(other);
613: return id1 < id2 ? -1 : id1 > id2 ? 1 : 0;
614: }
615:
616: /** This is used for the XML concept of "document order".
617: * It is overridden in gnu.xml.NodeTree for a more robust implementation.
618: */
619: public static int compare(AbstractSequence seq1, int pos1,
620: AbstractSequence seq2, int pos2) {
621: if (seq1 == seq2)
622: return seq1.compare(pos1, pos2);
623: return seq1.stableCompare(seq2);
624: }
625:
626: public int hashCode() {
627: // Implementation specified by the Collections specification.
628: int hash = 1;
629: for (int i = startPos(); (i = nextPos(i)) != 0;) {
630: Object obj = getPosPrevious(i);
631: hash = 31 * hash + (obj == null ? 0 : obj.hashCode());
632: }
633: return hash;
634: }
635:
636: public boolean equals(Object o) {
637: // Compatible with the Collections specification.
638: // FIXME should also depend on class?
639: /* #ifdef JAVA2 */
640: if (!(this instanceof java.util.List)
641: || !(o instanceof java.util.List))
642: return this == o;
643: Iterator it1 = iterator();
644: Iterator it2 = ((java.util.List) o).iterator();
645: /* #endif */
646: /* #ifndef JAVA2 */
647: // if (! (this instanceof Sequence) || ! (o instanceof Sequence))
648: // return this == o;
649: // Enumeration it1 = elements();
650: // Enumeration it2 = ((Sequence) o).elements();
651: /* #endif */
652: for (;;) {
653: /* #ifdef JAVA2 */
654: boolean more1 = it1.hasNext();
655: boolean more2 = it2.hasNext();
656: /* #endif */
657: /* #ifndef JAVA2 */
658: // boolean more1 = it1.hasMoreElements();
659: // boolean more2 = it2.hasMoreElements();
660: /* #endif */
661: if (more1 != more2)
662: return false;
663: if (!more1)
664: return true;
665: /* #ifdef JAVA2 */
666: Object e1 = it1.next();
667: Object e2 = it2.next();
668: /* #endif */
669: /* #ifndef JAVA2 */
670: // Object e1 = it1.nextElement();
671: // Object e2 = it2.nextElement();
672: /* #endif */
673: if (e1 == null) {
674: if (e2 != null)
675: return false;
676: } else if (!e1.equals(e2))
677: return false;
678: }
679: }
680:
681: public Sequence subSequence(SeqPosition start, SeqPosition end) {
682: return subSequencePos(start.ipos, end.ipos);
683: }
684:
685: protected Sequence subSequencePos(int ipos0, int ipos1) {
686: return new SubSequence(this , ipos0, ipos1);
687: }
688:
689: /* #ifdef JAVA2 */
690: public List subList(int fromIx, int toIx) {
691: return new SubSequence(this , createPos(fromIx, false),
692: createPos(toIx, true));
693: }
694:
695: /* #endif */
696:
697: /** Copy an element specified by a position pair to a Consumer.
698: * @return if hasNext(ipos). */
699: public boolean consumeNext(int ipos, Consumer out) {
700: int next = nextPos(ipos);
701: if (next == 0)
702: return false;
703: consumePosRange(ipos, next, out);
704: return true;
705: }
706:
707: public void consumePosRange(int iposStart, int iposEnd, Consumer out) {
708: if (out.ignoring())
709: return;
710: int it = copyPos(iposStart);
711: while (!equals(it, iposEnd)) {
712: if (!hasNext(it))
713: throw new RuntimeException();
714: out.writeObject(getPosNext(it));
715: it = nextPos(it);
716: }
717: releasePos(it);
718: }
719:
720: public void consume(Consumer out) {
721: boolean isSequence = this instanceof Sequence;
722: if (isSequence)
723: out.startElement("#sequence");
724: consumePosRange(startPos(), endPos(), out);
725: if (isSequence)
726: out.endElement();
727: }
728:
729: public void toString(String sep, StringBuffer sbuf) {
730: boolean seen = false;
731: for (int i = startPos(); (i = nextPos(i)) != 0;) {
732: if (seen)
733: sbuf.append(sep);
734: else
735: seen = true;
736: sbuf.append(getPosPrevious(i));
737: }
738: }
739:
740: public String toString() {
741: StringBuffer sbuf = new StringBuffer(100);
742: if (this instanceof Sequence)
743: sbuf.append('[');
744: toString(", ", sbuf);
745: if (this instanceof Sequence)
746: sbuf.append(']');
747: return sbuf.toString();
748: }
749: }
|