001: // -*-Java-*-
002: // Copyright (c) 2001 Per M.A. Bothner and Brainfood Inc.
003: // This is free software; for terms and warranty disclaimer see ./COPYING.
004:
005: package gnu.lists;
006:
007: import java.util.*;
008: import java.util.Enumeration;
009:
010: /**
011: * An AbstractSequence is used to implement Sequences, and almost all
012: * classes that extend AbstractSequence will implement Sequence.
013: * However, AbstractSequence itself does not implement Sequence.
014: * This is so we can use AbstractSequence to implement classes that are
015: * "sequence-like" (such as multi-dimesnional arrays) but are not Sequences.
016: *
017: * Additionally, a sequence may have zero or more attributes, which are
018: * name-value pairs. A sequence may also have a named "type". These
019: * extensions are to support XML functionality - it might be cleaner to
020: * moe them to a sub-class of Sequence or some interface.
021: *
022: * Many of the protected methods in Sequence (such as nextIndex) are
023: * only intended to be called from SeqPosition or TreePosition, see those.
024: *
025: * @author Per Bothner
026: */
027:
028: public abstract class AbstractSequence {
029: /** See java.util.List. */
030: public abstract int size();
031:
032: public boolean isEmpty() {
033: return size() > 0;
034: }
035:
036: public int rank() {
037: return 1;
038: }
039:
040: /** See java.util.List. */
041: public abstract Object get(int index);
042:
043: public int getEffectiveIndex(int[] indexes) {
044: return indexes[0];
045: }
046:
047: public Object get(int[] indexes) {
048: return get(indexes[0]);
049: }
050:
051: public Object set(int[] indexes, Object value) {
052: return set(indexes[0], value);
053: }
054:
055: protected RuntimeException unsupported(String text) {
056: text = getClass().getName() + " does not implement " + text;
057: return new UnsupportedOperationException(text);
058: }
059:
060: public Object set(int index, Object element) {
061: throw unsupported("set");
062: }
063:
064: public void fill(Object value) {
065: SeqPosition it = getIterator();
066: while (gotoNext(it))
067: setPrevious(it.ipos, it.xpos, value);
068: it.finalize();
069: }
070:
071: public void fill(int fromIndex, int toIndex, Object value) {
072: for (int i = fromIndex; i < toIndex; i++)
073: set(i, value);
074: }
075:
076: // FIXME?
077: //public final Object elementAt (int index) { return get(index); }
078:
079: /** See java.util.List. */
080: public int indexOf(Object o) {
081: int i = 0;
082: SeqPosition it = getIterator();
083: for (; it.hasNext(); i++) {
084: Object e = it.next();
085: if (o == null ? e == null : o.equals(e))
086: return i;
087: }
088: return -1;
089: }
090:
091: /** See java.util.List. */
092: public int lastIndexOf(Object o) {
093: // FIXME use iterator?
094: for (int n = size(); --n >= 0;) {
095: Object e = get(n);
096: if (o == null ? e == null : o.equals(e))
097: return n;
098: }
099: return -1;
100: }
101:
102: /** See java.util.List. */
103: public boolean contains(Object o) {
104: SeqPosition i = getIterator();
105: while (i.hasNext()) {
106: Object e = i.next();
107: if (o == null ? e == null : o.equals(e))
108: return true;
109: }
110: return false;
111: }
112:
113: /** See java.util.List. */
114: public boolean containsAll(Collection c) {
115: SeqPosition i = getIterator();
116: while (i.hasNext()) {
117: Object e = i.next();
118: if (!contains(e))
119: return false;
120: }
121: return true;
122: }
123:
124: public Enumeration elements() {
125: SeqPosition it = new SeqPosition();
126: makeStartPosition(it);
127: return it;
128: }
129:
130: public SeqPosition getIterator() {
131: SeqPosition it = new SeqPosition();
132: makeStartPosition(it);
133: return it;
134: }
135:
136: public Iterator iterator() {
137: SeqPosition it = new SeqPosition();
138: makeStartPosition(it);
139: return it;
140: }
141:
142: public ListIterator listIterator() {
143: return listIterator(0);
144: }
145:
146: public ListIterator listIterator(int index) {
147: SeqPosition it = new SeqPosition();
148: makePosition(index, it);
149: return it;
150: }
151:
152: protected void add(PositionContainer posSet, int posNumber,
153: Object value) {
154: throw unsupported("add");
155: }
156:
157: /** See java.util.Collection. */
158: public boolean add(Object o) {
159: add(size(), o);
160: return true;
161: }
162:
163: /** See java.util.List. */
164: public void add(int index, Object o) {
165: throw unsupported("add single Object at index");
166: }
167:
168: /** See java.util.Collection. */
169: public boolean addAll(Collection c) {
170: return addAll(size(), c);
171: }
172:
173: /** See java.util.Collection. */
174: public boolean addAll(int index, Collection c) {
175: boolean changed = false;
176: for (Iterator it = c.iterator(); it.hasNext();) {
177: add(index++, it.next());
178: changed = true;
179: }
180: return changed;
181: }
182:
183: /**
184: * Remove one or more elements.
185: * @param ipos integer part of position where elements should be removed
186: * @param xpos object part of position where elements should be removed
187: * @param count if non-negative, remove that number of elements
188: * following (poses, posNumber); if negative the negative of the number
189: * of elements to remove before (poses, posNumber).
190: * @return number of elements actually removed (non-negative)
191: * @exception java.lang.IndexOutOfBoundsException
192: * if (count >= 0 ? (index < 0 || index + count > size())
193: * : (index + count < 0 || index > size())),
194: * where index == nextIndex(ipos, xpos).
195: */
196: protected void remove(int ipos, Object xpos, int count) {
197: SeqPosition it = new SeqPosition(this );
198: makeRelativePosition(ipos, xpos, count, true, it, 0);
199: if (count >= 0)
200: remove(ipos, xpos, it.ipos, it.xpos);
201: else
202: remove(it.ipos, it.xpos, ipos, xpos);
203: }
204:
205: /** Remove a range where each end-point is a position in a container.
206: * @param ipos0 integer part of start of range
207: * @param xpos0 object part of start of range
208: * @param ipos1 integer part of end of range
209: * @param xpos1 object part of end of range
210: * @exception java.lang.IndexOutOfBoundsException
211: * if nextIndex(ipos0, xpos0) > nextIndex(ipos1, xpos1)
212: * || nextIndex(ipos0, xpos0) < 0 || nextIndex(ipos1, xpos1) > size()
213: */
214: protected void remove(int ipos0, Object xpos0, int ipos1,
215: Object xpos1) {
216: throw unsupported("remove (with range)");
217: }
218:
219: public Object remove(int index) {
220: if (index < 0 || index >= size())
221: throw new IndexOutOfBoundsException();
222: SeqPosition it = new SeqPosition(this );
223: makePosition(index, it);
224: Object result = getNext(it.ipos, it.xpos);
225: remove(it.ipos, it.xpos, 1);
226: return result;
227: }
228:
229: public boolean remove(Object o) {
230: int index = indexOf(o);
231: if (index < 0)
232: return false;
233: SeqPosition it = new SeqPosition();
234: makePosition(index, it);
235: remove(it.ipos, it.xpos, 1);
236: return true;
237: }
238:
239: public boolean removeAll(Collection c) {
240: boolean changed = false;
241: for (SeqPosition it = getIterator(); it.hasNext();) {
242: Object value = it.next();
243: if (c.contains(value)) {
244: it.remove();
245: changed = true;
246: }
247: }
248: return changed;
249: }
250:
251: public boolean retainAll(Collection c) {
252: boolean changed = false;
253: for (SeqPosition it = getIterator(); it.hasNext();) {
254: Object value = it.next();
255: if (!c.contains(value)) {
256: it.remove();
257: changed = true;
258: }
259: }
260: return changed;
261: }
262:
263: public void clear() {
264: SeqPosition it = new SeqPosition();
265: makeStartPosition(it);
266: remove(it.ipos, it.xpos, size());
267: }
268:
269: /** Does the position pair have the "isAfter" property?
270: * I.e. if something is inserted at the position, will
271: * the iterator end up being after the new data? */
272: protected boolean isAfter(int ipos, Object xpos) {
273: return false;
274: }
275:
276: protected final void makePosition(int index, SeqPosition pos) {
277: makePosition(index, true, pos);
278: }
279:
280: /** Generate a position at a given index.
281: * @param index offset from beginning of desired position
282: * @param isAfter should the position have the isAfter property
283: * @param pos where to store the generated position
284: * This old position should be already released, if needed.
285: * @exception IndexOutOfBoundsException if index is out of bounds
286: */
287: public void makePosition(int index, boolean isAfter, SeqPosition pos) {
288: makePosition(index, isAfter, pos, 0);
289: }
290:
291: /** Generate a position at a given index.
292: * @param index offset from beginning of desired position
293: * @param isAfter should the position have the isAfter property
294: * @param posSet where to store the generated position
295: * @param posNumber index in posSet for the generated position. Any old
296: * position there should be alread released, if needed.
297: * @exception IndexOutOfBoundsException if index is out of bounds
298: */
299: protected abstract void makePosition(int index, boolean isAfter,
300: PositionContainer posSet, int posNumber);
301:
302: /** Generate a position relative to an existing position.
303: * @param istart int part of initial position
304: * @param xstart object part of initial position
305: * @param offset offset from (istart,xstart) of desired position
306: * @param isAfter should the position have the isAFter property
307: * @param posSet where to store the generated position
308: * @param positionNumber index in posSet for the generated position. Any
309: * old position there should be alread released, if needed.
310: * @exception IndexOutOfBoundsException if resulting index is out of bounds
311: */
312: protected void makeRelativePosition(int istart, Object xstart,
313: int offset, boolean isAfter, PositionContainer posSet,
314: int posNumber) {
315: makePosition(nextIndex(istart, xstart) + offset, isAfter,
316: posSet, posNumber);
317: }
318:
319: public void makeStartPosition(SeqPosition pos) {
320: makeStartPosition(pos, 0);
321: }
322:
323: /** Set a position to the start of this sequence. */
324: protected void makeStartPosition(PositionContainer poses,
325: int positionNumber) {
326: makePosition(0, false, poses, positionNumber);
327: }
328:
329: /** Set a position to the end of this sequence. */
330: public void makeEndPosition(SeqPosition pos) {
331: makeEndPosition(pos, 0);
332: pos.setSequence(0, this ); // FIXME - handled by caller?
333: }
334:
335: protected void makeEndPosition(PositionContainer poses,
336: int positionNumber) {
337: makePosition(size(), true, poses, positionNumber);
338: }
339:
340: /**
341: * Reclaim any resources used by the given position pair.
342: * @param ipos integer part of the position being free'd.
343: * @param xpos Object part of the position being free'd.
344: */
345: protected void releasePosition(int ipos, Object xpos) {
346: }
347:
348: protected final void releasePosition(SeqPosition pos) {
349: releasePosition(pos.ipos, pos.xpos);
350: }
351:
352: protected void releasePosition(PositionContainer posSet,
353: int posNumber) {
354: int ipos = posSet.getPositionInt(posNumber);
355: Object xpos = posSet.getPositionPtr(posNumber);
356: releasePosition(ipos, xpos);
357: }
358:
359: /** Make a copy of a position pair.
360: * For simple positions this is a simple copy (assignment).
361: * However, if the positions are magic cookies that are actively managed
362: * by the sequence (as opposed to for example a simple index), then making
363: * a copy may need to increment a reference count, or maybe allocate a
364: * new position pair. In any case, the new pair is initialized to the
365: * same offset (and isAfter property) as the original.
366: * @param ipos integer part of the position being copied.
367: * @param xpos Object part of the position being copied.
368: * @param posSet where to put the new copy
369: * @param posNumber which psoition in posSet that gets the copy.
370: */
371: public void copyPosition(int ipos, Object xpos,
372: PositionContainer posSet, int posNumber) {
373: /*
374: makePosition(nextIndex(ipos, xpos), isAfter(ipos, xpos),
375: posSet, posNumber);
376: */
377: posSet.setSequence(posNumber, this );
378: posSet.setPosition(posNumber, ipos, xpos);
379: }
380:
381: /** Get offset of (ipos1,xpos1) relative to (ipos0,xpos0). */
382: protected int getIndexDifference(int ipos1, Object xpos1,
383: int ipos0, Object xpos0) {
384: return nextIndex(ipos1, xpos1) - nextIndex(ipos0, xpos0);
385: }
386:
387: /**
388: * Get the offset from the beginning corresponding to a position pair.
389: * Note default implementation only works for array-like sequences!
390: */
391: protected int nextIndex(int ipos, Object xpos) {
392: throw unsupported("nextIndex");
393: }
394:
395: protected int fromEndIndex(int ipos, Object xpos) {
396: return size() - nextIndex(ipos, xpos);
397: }
398:
399: /**
400: * Get the size of the (sub-) sequence containing a given position.
401: * Normally the same as size(), but may be different if this Sequence
402: * is a tree and the position points at an interior node.
403: */
404: protected int getContainingSequenceSize(int ipos, Object xpos) {
405: return size();
406: }
407:
408: /** Called by SeqPosition.hasNext. */
409: protected boolean hasNext(int ipos, Object xpos) {
410: return nextIndex(ipos, xpos) != size();
411: }
412:
413: public int getNextKind(int ipos, Object xpos) {
414: return hasNext(ipos, xpos) ? Sequence.OBJECT_VALUE
415: : Sequence.EOF_VALUE;
416: }
417:
418: public String getNextTypeName(int ipos, Object xpos) {
419: return null;
420: }
421:
422: public Object getNextTypeObject(int ipos, Object xpos) {
423: return null;
424: }
425:
426: /** Called by SeqPosition.hasPrevious. */
427: protected boolean hasPrevious(int ipos, Object xpos) {
428: return nextIndex(ipos, xpos) != 0;
429: }
430:
431: /** Move forward one element position.
432: * @return true unless at end of sequence.
433: */
434: public boolean gotoNext(PositionContainer posSet, int posNumber) {
435: int ipos = posSet.getPositionInt(posNumber);
436: Object xpos = posSet.getPositionPtr(posNumber);
437: if (!hasNext(ipos, xpos))
438: return false;
439: if (true) // FIXME if not managed positions
440: makeRelativePosition(ipos, xpos, 1, true, posSet, posNumber);
441: else {
442: int index = nextIndex(ipos, xpos);
443: releasePosition(posSet, posNumber);
444: makePosition(index + 1, true, posSet, posNumber);
445: }
446: return true;
447: }
448:
449: /** Potential optimization. */
450: public boolean gotoNext(SeqPosition pos) {
451: return gotoNext(pos, 0);
452: }
453:
454: /** Move backwards one element.
455: * @return false iff already at beginning.
456: */
457: protected boolean gotoPrevious(PositionContainer posSet,
458: int posNumber) {
459: int ipos = posSet.getPositionInt(posNumber);
460: Object xpos = posSet.getPositionPtr(posNumber);
461: if (!hasPrevious(ipos, xpos))
462: return false;
463: if (true) // FIXME if not managed positions
464: makeRelativePosition(ipos, xpos, -1, false, posSet,
465: posNumber);
466: else {
467: int index = nextIndex(ipos, xpos);
468: releasePosition(posSet, posNumber);
469: makePosition(index - 1, false, posSet, posNumber);
470: }
471: return true;
472: }
473:
474: /** Set position before first child (of the element following position).
475: * @return true if there is a child sequence (which might be empty);
476: * false if current position is end of sequence or following element
477: * is atomic (cannot have children).
478: */
479: public boolean gotoChildrenStart(TreePosition pos) {
480: return false;
481: }
482:
483: protected boolean gotoParent(TreePosition pos) {
484: if (pos.depth < 0)
485: return false;
486: pos.pop();
487: return true;
488: }
489:
490: public int getAttributeLength() {
491: return 0;
492: }
493:
494: public Object getAttribute(int index) {
495: return null;
496: }
497:
498: protected boolean gotoAttributesStart(TreePosition pos) {
499: return false;
500: }
501:
502: /** Get the element following the specified position.
503: * @param ipos integer part of the specified position.
504: * @param xpos Object part of the specified position.
505: * @return the following element, or eofValue if there is none.
506: * Called by SeqPosition.getNext. */
507: protected Object getNext(int ipos, Object xpos) {
508: // wrong result if out of bounds FIXME
509: return get(nextIndex(ipos, xpos));
510: }
511:
512: /** Get the element before the specified position.
513: * @param ipos integer part of the specified position.
514: * @param xpos Object part of the specified position.
515: * @return the following element, or eofValue if there is none.
516: * Called by SeqPosition.getNext. */
517: protected Object getPrevious(int ipos, Object xpos) {
518: return get(nextIndex(ipos, xpos) - 1);
519: }
520:
521: protected void setNext(int ipos, Object xpos, Object value) {
522: int index = nextIndex(ipos, xpos);
523: if (index >= size())
524: throw new IndexOutOfBoundsException();
525: set(index, value);
526: }
527:
528: protected void setPrevious(int ipos, Object xpos, Object value) {
529: int index = nextIndex(ipos, xpos);
530: if (index == 0)
531: throw new IndexOutOfBoundsException();
532: set(index - 1, value);
533: }
534:
535: public final int nextIndex(SeqPosition pos) {
536: return nextIndex(pos.ipos, pos.xpos);
537: }
538:
539: /** Compare two positions, and indicate if the are the same position. */
540: public boolean equals(int ipos1, Object xpos1, int ipos2,
541: Object xpos2) {
542: return compare(ipos1, xpos1, ipos2, xpos2) == 0;
543: }
544:
545: /** Compare two positions, and indicate their relative order. */
546: public int compare(int ipos1, Object xpos1, int ipos2, Object xpos2) {
547: int i1 = nextIndex(ipos1, xpos1);
548: int i2 = nextIndex(ipos2, xpos2);
549: return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
550: }
551:
552: public final int compare(SeqPosition i1, SeqPosition i2) {
553: return compare(i1.ipos, i1.xpos, i2.ipos, i2.xpos);
554: }
555:
556: public Object[] toArray() {
557: int len = size();
558: Object[] arr = new Object[len];
559:
560: java.util.Enumeration e = elements();
561: for (int i = 0; e.hasMoreElements(); i++)
562: arr[i] = e.nextElement();
563: return arr;
564: }
565:
566: public Object[] toArray(Object[] arr) {
567: int alen = arr.length;
568: int len = size();
569: if (len > alen) {
570: Class componentType = arr.getClass().getComponentType();
571: arr = (Object[]) java.lang.reflect.Array.newInstance(
572: componentType, len);
573: alen = len;
574: }
575:
576: java.util.Enumeration e = elements();
577: for (int i = 0; e.hasMoreElements(); i++) {
578: arr[i] = e.nextElement();
579: }
580: if (len < alen)
581: arr[len] = null;
582: return arr;
583: }
584:
585: public int hashCode() {
586: // Implementation specified by the Collections specification.
587: int hash = 1;
588: SeqPosition i = getIterator();
589: while (i.hasNext()) {
590: Object obj = i.next();
591: hash = 31 * hash + (obj == null ? 0 : obj.hashCode());
592: }
593: return hash;
594: }
595:
596: public boolean equals(Object o) {
597: // Compatible with the Collections specification.
598: // FIXME should also depend on class?
599: if (!(o instanceof java.util.List))
600: return false;
601: Iterator it1 = iterator();
602: Iterator it2 = ((java.util.List) o).iterator();
603: for (;;) {
604: boolean more1 = it1.hasNext();
605: boolean more2 = it2.hasNext();
606: if (more1 != more2)
607: return false;
608: if (!more1)
609: return true;
610: Object e1 = it1.next();
611: Object e2 = it2.next();
612: if (e1 == null) {
613: if (e2 != null)
614: return false;
615: } else if (!e1.equals(e2))
616: return false;
617: }
618: }
619:
620: public Sequence subSequence(SeqPosition start, SeqPosition end) {
621: return subSequence(start.ipos, start.xpos, end.ipos, end.xpos);
622: }
623:
624: protected Sequence subSequence(int ipos0, Object xpos0, int ipos1,
625: Object xpos1) {
626: SubSequence sub = new SubSequence(this );
627: copyPosition(ipos0, xpos0, sub, 0);
628: copyPosition(ipos1, xpos1, sub, 1);
629: return sub;
630: }
631:
632: public List subList(int fromIx, int toIx) {
633: SubSequence sub = new SubSequence(this );
634: makePosition(fromIx, false, sub, 0);
635: makePosition(toIx, true, sub, 1);
636: return sub;
637: }
638:
639: /** Copy an element specified by a position pair to a Consumer.
640: * @return if hasNext(ipos, xpos). */
641: public boolean consumeNext(int ipos, Object xpos, Consumer out) {
642: if (!hasNext(ipos, xpos))
643: return false;
644: out.writeObject(getNext(ipos, xpos));
645: return true;
646: }
647:
648: protected void consume(int iposStart, Object xposStart,
649: int iposEnd, Object xposEnd, Consumer out) {
650: if (out.ignoring())
651: return;
652: SeqPosition it = new SeqPosition();
653: copyPosition(iposStart, xposStart, it, 0);
654: while (!equals(it.ipos, it.xpos, iposEnd, xposEnd)) {
655: if (!it.hasNext())
656: throw new RuntimeException();
657: out.writeObject(it.nextElement());
658: }
659: it.finalize();
660: }
661:
662: /*
663: Consume wlements, without any beginGroup/endGroup.
664: public void consumeElements() ...
665: */
666:
667: public void consume(Consumer out) {
668: String typeName = "#sequence";
669: String type = typeName;
670: out.beginGroup(typeName, type);
671: java.util.Enumeration e = elements();
672: for (int i = 0; e.hasMoreElements(); i++)
673: out.writeObject(e.nextElement());
674: out.endGroup(typeName);
675: }
676: }
|