Java > Open Source Codes > gnu > lists > AbstractSequence


1 // Copyright (c) 2001, 2002, 2003, 2005 Per M.A. Bothner and Brainfood Inc.
2 // This is free software; for terms and warranty disclaimer see ./COPYING.
3
4 package gnu.lists;
5 import java.util.*;
6
7 /**
8  * An AbstractSequence is used to implement Sequences, and almost all
9  * classes that extend AbstractSequence will implement Sequence.
10  * However, AbstractSequence itself does not implement Sequence.
11  * This is so we can use AbstractSequence to implement classes that are
12  * "sequence-like" (such as multi-dimesnional arrays) but are not Sequences.
13  *
14  * Additionally, a sequence may have zero or more attributes, which are
15  * name-value pairs. A sequence may also have a named "type". These
16  * extensions are to support XML functionality - it might be cleaner to
17  * moe them to a sub-class of Sequence or some interface.
18  *
19  * Many of the protected methods in Sequence (such as nextIndex) are
20  * only intended to be called from SeqPosition or TreePosition, see those.
21  *
22  * @author Per Bothner
23  */
24
25 public abstract class AbstractSequence
26 {
27   /** See java.util.List. */
28   public abstract int size();
29
30   public boolean isEmpty()
31   {
32     return size() == 0;
33   }
34
35   public int rank()
36   {
37     return 1;
38   }
39
40   /** See java.util.List. */
41   public abstract Object get (int index);
42
43   public int getEffectiveIndex(int[] indexes)
44   {
45     return indexes[0];
46   }
47
48   public Object get(int[] indexes)
49   {
50     return get(indexes[0]);
51   }
52
53   public Object set(int[] indexes, Object value)
54   {
55     return set(indexes[0], value);
56   }
57
58   public int getLowBound(int dim)
59   {
60     return 0;
61   }
62
63   public int getSize (int dim)
64   {
65     return dim==0 ? size() : 1;
66   }
67
68   protected RuntimeException unsupported (String text)
69   {
70     return unsupportedException(getClass().getName()
71                                 + " does not implement " + text);
72   }
73
74   public static RuntimeException unsupportedException (String text)
75   {
76     /* #ifdef JAVA2 */
77     return new UnsupportedOperationException (text);
78     /* #endif */
79     /* #ifndef JAVA2 */
80     // return new RuntimeException(text);
81 /* #endif */
82   }
83
84   public Object set(int index, Object element)
85   {
86     throw unsupported("set");
87   }
88
89   public void fill(Object value)
90   {
91     for (int i = startPos(); (i = nextPos(i)) != 0; )
92       setPosPrevious(i, value);
93   }
94
95   public void fillPosRange(int fromPos, int toPos, Object value)
96   {
97     int i = copyPos(fromPos);
98     for (; compare(i, toPos) < 0; i = nextPos(i))
99       setPosNext(i, value);
100     releasePos(i);
101   }
102
103   public void fill(int fromIndex, int toIndex, Object value)
104   {
105     int i = createPos(fromIndex, false);
106     int limit = createPos(toIndex, true);
107     for (; compare(i, limit) < 0; i = nextPos(i))
108       setPosNext(i, value);
109     releasePos(i);
110     releasePos(limit);
111   }
112
113   // FIXME?
114 //public final Object elementAt (int index) { return get(index); }
115
116   /** See java.util.List. */
117   public int indexOf(Object o)
118   {
119     int i = 0;
120     for (int iter = startPos(); (iter = nextPos(iter)) != 0; i++)
121       {
122     Object v = getPosPrevious(iter);
123         if (o==null ? v==null : o.equals(v))
124       {
125         releasePos(iter);
126         return i;
127       }
128       }
129     return -1;
130   }
131
132   /** See java.util.List. */
133   public int lastIndexOf(Object o)
134   {
135     // FIXME use iterator?
136 for (int n = size(); --n >= 0; )
137       {
138         Object e = get(n);
139         if (o==null ? e == null : o.equals(e))
140           return n;
141       }
142     return -1;
143   }
144
145   /** Get next matching child or descendent (ignoring attributes).
146    * @param startPos starting position
147    * @param type a test (predicate) to apply to selected elements
148    * @param endPos stop before endPos
149    * @param descend if true do depth-first traversal.
150    * @return poistion of next match or 0 if none found
151    */
152   public int nextMatching(int startPos, ElementPredicate type,
153               int endPos, boolean descend)
154   {
155     if (descend)
156       throw unsupported("nextMatching with descend");
157     int ipos = startPos;
158     for (;;)
159       {
160     if (compare(ipos, endPos) >= 0)
161       return 0;
162     ipos = nextPos(ipos);
163     if (type.isInstancePos(this, ipos))
164       return ipos;
165       }
166   }
167
168   /** See java.util.List. */
169   public boolean contains(Object o)
170   {
171     return indexOf(o) >= 0;
172   }
173
174   /* #ifdef JAVA2 */
175   /** See java.util.List. */
176   public boolean containsAll(Collection c)
177   {
178     Iterator i = c.iterator();
179     while (i.hasNext())
180       {
181         Object e = i.next();
182         if (! contains(e))
183           return false;
184       }
185     return true;
186   }
187   /* #endif */
188
189   public final Enumeration elements()
190   {
191     return getIterator();
192   }
193
194   public final SeqPosition getIterator()
195   {
196     return getIterator(0);
197   }
198
199   public SeqPosition getIterator(int index)
200   {
201     return new SeqPosition(this, index, false);
202   }
203
204   public SeqPosition getIteratorAtPos(int ipos)
205   {
206     return new SeqPosition(this, copyPos(ipos));
207   }
208
209   /* #ifdef JAVA2 */
210   public final Iterator iterator()
211   {
212     return getIterator();
213   }
214
215   public final ListIterator listIterator()
216   {
217     return getIterator(0);
218   }
219
220   public final ListIterator listIterator(int index)
221   {
222     return getIterator(index);
223   }
224   /* #endif */
225
226   /** Add a value at a specified Pos.
227    * @return the updated Pos, which is after the inserted value..
228    */
229   protected int addPos (int ipos, Object value)
230   {
231     throw unsupported("addPos");
232   }
233
234   /** See java.util.Collection. */
235   public boolean add(Object o)
236   {
237     addPos(endPos(), o);
238     return true;
239   }
240
241   /** See java.util.List. */
242   public void add(int index, Object o)
243   {
244     int pos = createPos(index, false);
245     addPos(pos, o);
246     releasePos(pos);
247   }
248
249   /* #ifdef JAVA2 */
250   /** See java.util.Collection. */
251   public boolean addAll(Collection c)
252   {
253     return addAll(size(), c);
254   }
255
256   /** See java.util.Collection. */
257   public boolean addAll(int index, Collection c)
258   {
259     boolean changed = false;
260     int pos = createPos(index, false);
261     for (Iterator it = c.iterator(); it.hasNext(); )
262       {
263         pos = addPos(pos, it.next());
264         changed = true;
265       }
266     releasePos(pos);
267     return changed;
268   }
269   /* #endif */
270   /* #ifndef JAVA2 */
271   // public boolean addAll(Sequence c)
272 // {
273 // return addAll(size(), c);
274 // }
275
276   // public boolean addAll(int index, Sequence c)
277 // {
278 // boolean changed = false;
279 // int pos = createPos(index, false);
280 // for (int iter = startPos(); (iter = nextPos(iter)) != 0; )
281 // {
282 // pos = addPos(pos, getPosPrevious(iter));
283 // changed = true;
284 // }
285 // releasePos(pos);
286 // return changed;
287 // }
288 /* #endif */
289
290   /**
291    * Remove one or more elements.
292    * @param ipos position where elements should be removed
293    * @param count if non-negative, remove that number of elements
294    * following (poses, posNumber); if negative the negative of the number
295    * of elements to remove before (poses, posNumber).
296    * @exception java.lang.IndexOutOfBoundsException
297    * if (count >= 0 ? (index < 0 || index + count > size())
298    * : (index + count < 0 || index > size())),
299    * where index == nextIndex(ipos, xpos).
300    */
301   public void removePos(int ipos, int count)
302   {
303     int rpos = createRelativePos(ipos, count, false);
304     if (count >= 0)
305       removePosRange(ipos, rpos);
306     else
307       removePosRange(rpos, ipos);
308     releasePos(rpos);
309   }
310
311   /** Remove a range where each end-point is a position in a container.
312    * @param ipos0 start of range, as a poistion
313    * @param ipos1 end of range
314    * @exception java.lang.IndexOutOfBoundsException
315    * if nextIndex(ipos0) > nextIndex(ipos1)
316    * || nextIndex(ipos0) < 0 || nextIndex(ipos1) > size()
317    */
318   protected void removePosRange(int ipos0, int ipos1)
319   {
320     throw unsupported("removePosRange");
321   }
322
323   public Object remove(int index)
324   {
325     if (index < 0 || index >= size())
326       throw new IndexOutOfBoundsException ();
327     int ipos = createPos(index, false);
328     Object result = getPosNext(ipos);
329     removePos(ipos, 1);
330     releasePos(ipos);
331     return result;
332   }
333
334   public boolean remove(Object o)
335   {
336     int index = indexOf(o);
337     if (index < 0)
338       return false;
339     int ipos = createPos(index, false);
340     removePos(ipos, 1);
341     releasePos(ipos);
342     return true;
343   }
344
345   /* #ifdef JAVA2 */
346   public boolean removeAll(Collection c)
347   {
348     boolean changed = false;
349     for (int iter = startPos(); (iter = nextPos(iter)) != 0; )
350       {
351         Object value = getPosPrevious(iter);
352         if (c.contains(value))
353           {
354             removePos(iter, -1);
355             changed = true;
356           }
357       }
358     return changed;
359   }
360
361   public boolean retainAll(Collection c)
362   {
363     boolean changed = false;
364     for (int iter = startPos(); (iter = nextPos(iter)) != 0; )
365       {
366         Object value = getPosPrevious(iter);
367         if (! c.contains(value))
368           {
369             removePos(iter, -1);
370             changed = true;
371           }
372       }
373     return changed;
374   }
375   /* #endif */
376
377   public void clear()
378   {
379     removePos(startPos(), endPos());
380   }
381
382   /** Tests whether the position has the "isAfter" property.
383    * I.e. if something is inserted at the position, will
384    * the iterator end up being after the new data? */
385   protected boolean isAfterPos (int ipos)
386   {
387     return (ipos & 1) != 0;
388   }
389
390   /** Generate a position at a given index.
391    * The result is a position cookie that must be free'd with releasePos.
392    * @param index offset from beginning of desired position
393    * @param isAfter should the position have the isAfter property
394    * @exception IndexOutOfBoundsException if index is out of bounds
395    */
396   public abstract int createPos (int index, boolean isAfter);
397
398   public int createRelativePos(int pos, int delta, boolean isAfter)
399   {
400     return createPos(nextIndex(pos) + delta, isAfter);
401   }
402
403   public int startPos () { return 0; }
404   public int endPos () { return -1; }
405
406   /**
407    * Reclaim any resources used by the given position int.
408    * @param ipos the Pos being free'd.
409    */
410   protected void releasePos(int ipos)
411   {
412   }
413
414   /** Make a copy of a position int.
415    * For simple positions returns the argument.
416    * However, if the positions are magic cookies that are actively managed
417    * by the sequence (as opposed to for example a simple index), then making
418    * a copy may need to increment a reference count, or maybe allocate a
419    * new position cookie. In any case, the new position is initialized to
420    * the same offset (and isAfter property) as the original.
421    * @param ipos the position being copied.
422    * @return the new position
423    */
424   public int copyPos (int ipos)
425   {
426     return ipos;
427   }
428
429   /** Get offset of (ipos1) relative to (ipos0). */
430   protected int getIndexDifference(int ipos1, int ipos0)
431   {
432     return nextIndex(ipos1) - nextIndex(ipos0);
433   }
434
435   /**
436    * Get the offset from the beginning corresponding to a position cookie.
437    */
438   protected int nextIndex(int ipos)
439   {
440     return getIndexDifference(ipos, startPos());
441   }
442
443   protected int fromEndIndex(int ipos)
444   {
445     return size() - nextIndex(ipos);
446   }
447
448   /**
449    * Get the size of the (sub-) sequence containing a given position.
450    * Normally the same as size(), but may be different if this Sequence
451    * is a tree and the position points at an interior node.
452    */
453   protected int getContainingSequenceSize(int ipos)
454   {
455     return size();
456   }
457
458   public boolean hasNext (int ipos)
459   {
460     return nextIndex(ipos) != size();
461   }
462
463   public int getNextKind(int ipos)
464   {
465     return hasNext(ipos) ? Sequence.OBJECT_VALUE : Sequence.EOF_VALUE;
466   }
467
468   public String getNextTypeName(int ipos)
469   {
470     return null;
471   }
472
473   public Object getNextTypeObject(int ipos)
474   {
475     return null;
476   }
477
478   /** Called by SeqPosition.hasPrevious. */
479   protected boolean hasPrevious(int ipos)
480   {
481     return nextIndex(ipos) != 0;
482   }
483
484   /** Return the next position following the argument.
485    * The new position has the isAfter property.
486    * The argument is implicitly released (as in releasePos).
487    * Returns 0 if we are already at end of file.
488    */
489   public int nextPos (int ipos)
490   {
491     if (! hasNext(ipos))
492       return 0;
493     int next = createRelativePos(ipos, 1, true);
494     releasePos(ipos);
495     return next;
496   }
497
498   /** Return the previous position following the argument.
499    * The new position has the isBefore property.
500    * The argument is implicitly released (as in releasePos).
501    * Returns -1 if we are already at beginning of file.
502    */
503   public int previousPos (int ipos)
504   {
505     if (! hasPrevious(ipos))
506       return 0;
507     int next = createRelativePos(ipos, -1, false);
508     releasePos(ipos);
509     return next;
510   }
511
512   /** Set position before first child (of the element following position).
513    * @return true if there is a child sequence (which might be empty);
514    * false if current position is end of sequence or following element
515    * is atomic (cannot have children).
516    */
517   public final boolean gotoChildrenStart(TreePosition pos)
518   {
519     int ipos = firstChildPos(pos.getPos());
520     if (ipos == 0)
521       return false;
522     pos.push(this, ipos);
523     return true;
524   }
525
526   /** Get position before first child (of the element following position).
527    * @param ipos parent position. It is not released by this method.
528    * @return non-zero position cookie if there is a child sequence
529    * (which might be empty); zero if current position is end of sequence
530    * or following element is atomic (cannot have children).
531    */
532   public int firstChildPos (int ipos)
533   {
534     return 0;
535   }
536
537   public int firstChildPos (int ipos, ElementPredicate predicate)
538   {
539     int child = firstChildPos(ipos);
540     if (child == 0)
541       return 0;
542     if (predicate.isInstancePos(this, child))
543       return child;
544     else
545       return nextMatching(child, predicate, endPos(), false);
546   }
547
548   /** Like firstChildPos.
549    * Problem: Should this stop before we get to children?
550    * I think so, but that requires changes to TreeList. */
551   public int firstAttributePos (int ipos)
552   {
553     return 0;
554   }
555
556   /** Get position of parent.
557    * @param ipos child position. It is not released by this method.
558    * @return the p os of the parent, or endPos() is there is no known parent.
559    */
560   public int parentPos (int ipos)
561   {
562     return endPos();
563   }
564
565   protected boolean gotoParent(TreePosition pos)
566   {
567     if (pos.depth < 0)
568       return false;
569     pos.pop();
570     return true;
571   }
572
573   public int getAttributeLength()
574   {
575     return 0;
576   }
577
578   public Object getAttribute(int index)
579   {
580     return null;
581   }
582
583   protected boolean gotoAttributesStart(TreePosition pos)
584   {
585     return false;
586   }
587
588   /** Get the element following the specified position.
589    * @param ipos the specified position.
590    * @return the following element, or eofValue if there is none.
591    * Called by SeqPosition.getNext. */
592   public Object getPosNext(int ipos)
593   {
594     if (! hasNext(ipos))
595       return Sequence.eofValue;
596     return get(nextIndex(ipos));
597   }
598
599   /** Get the element before the specified position.
600    * @param ipos the specified position.
601    * @return the following element, or eofValue if there is none. */
602   public Object getPosPrevious(int ipos)
603   {
604     int index = nextIndex(ipos);
605     if (index <= 0)
606       return Sequence.eofValue;
607     return get(index - 1);
608   }
609
610   protected void setPosNext(int ipos, Object value)
611   {
612     int index = nextIndex(ipos);
613     if (index >= size())
614       throw new IndexOutOfBoundsException ();
615     set(index, value);
616   }
617
618   protected void setPosPrevious(int ipos, Object value)
619   {
620     int index = nextIndex(ipos);
621     if (index == 0)
622       throw new IndexOutOfBoundsException ();
623     set(index - 1, value);
624   }
625
626   public final int nextIndex(SeqPosition pos)
627   {
628     return nextIndex(pos.ipos);
629   }
630
631   /** Compare two positions, and indicate if they are the same position. */
632   public boolean equals(int ipos1, int ipos2)
633   {
634     return compare(ipos1, ipos2) == 0;
635   }
636
637   /** Compare two positions, and indicate their relative order. */
638   public int compare(int ipos1, int ipos2)
639   {
640     int i1 = nextIndex(ipos1);
641     int i2 = nextIndex(ipos2);
642     return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
643   }
644
645   public final int compare(SeqPosition i1, SeqPosition i2)
646   {
647     return compare(i1.ipos, i2.ipos);
648   }
649
650   public Object [] toArray()
651   {
652     int len = size();
653     Object [] arr = new Object [len];
654     int it = startPos();
655     int i = 0;
656     while ((it = nextPos(it)) != 0)
657       arr[i++] = getPosPrevious(it);
658     return arr;
659   }
660
661   public Object [] toArray(Object [] arr)
662   {
663     int alen = arr.length;
664     int len = size();
665     if (len > alen)
666     {
667       Class componentType = arr.getClass().getComponentType();
668       arr = (Object []) java.lang.reflect.Array.newInstance(componentType, len);
669       alen = len;
670     }
671     
672     int it = startPos();
673     for (int i = 0; (it = nextPos(it)) != 0; i++)
674     {
675       arr[i] = getPosPrevious(it);
676     }
677     if (len < alen)
678       arr[len] = null;
679     return arr;
680   }
681
682   /** This is used for the XML concept of "document order". */
683   public int stableCompare (AbstractSequence other)
684   {
685     int id1 = System.identityHashCode(this);
686     int id2 = System.identityHashCode(other);
687     return id1 < id2 ? -1 : id1 > id2 ? 1 : 0;
688   }
689
690   /** This is used for the XML concept of "document order".
691    * It is overridden in gnu.xml.NodeTree for a more robust implementation.
692    */
693   public static int compare(AbstractSequence seq1, int pos1,
694                 AbstractSequence seq2, int pos2)
695   {
696     if (seq1 == seq2)
697       return seq1.compare(pos1, pos2);
698     return seq1.stableCompare(seq2);
699   }
700
701   public int hashCode()
702   {
703     // Implementation specified by the Collections specification.
704 int hash = 1;
705     for (int i = startPos(); (i = nextPos(i)) != 0; )
706       {
707     Object obj = getPosPrevious(i);
708     hash = 31*hash + (obj==null ? 0 : obj.hashCode());
709       }
710     return hash;
711   }
712
713   public boolean equals(Object o)
714   {
715     // Compatible with the Collections specification.
716 // FIXME should also depend on class?
717 /* #ifdef JAVA2 */
718     if (! (this instanceof java.util.List )
719         || ! (o instanceof java.util.List ))
720       return this == o;
721     Iterator it1 = iterator();
722     Iterator it2 = ((java.util.List ) o).iterator();
723     /* #endif */
724     /* #ifndef JAVA2 */
725     // if (! (this instanceof Sequence) || ! (o instanceof Sequence))
726 // return this == o;
727 // Enumeration it1 = elements();
728 // Enumeration it2 = ((Sequence) o).elements();
729 /* #endif */
730     for (;;)
731       {
732         /* #ifdef JAVA2 */
733         boolean more1 = it1.hasNext();
734         boolean more2 = it2.hasNext();
735         /* #endif */
736         /* #ifndef JAVA2 */
737         // boolean more1 = it1.hasMoreElements();
738 // boolean more2 = it2.hasMoreElements();
739 /* #endif */
740         if (more1 != more2)
741           return false;
742         if (! more1)
743           return true;
744     /* #ifdef JAVA2 */
745         Object e1 = it1.next();
746         Object e2 = it2.next();
747     /* #endif */
748     /* #ifndef JAVA2 */
749         // Object e1 = it1.nextElement();
750 // Object e2 = it2.nextElement();
751 /* #endif */
752         if (e1 == null)
753           {
754             if (e2 != null)
755               return false;
756           }
757         else if (! e1.equals(e2))
758           return false;
759       }
760   }
761
762   public Sequence subSequence(SeqPosition start, SeqPosition end)
763   {
764     return subSequencePos(start.ipos, end.ipos);
765   }
766
767   protected Sequence subSequencePos(int ipos0, int ipos1)
768   {
769     return new SubSequence(this, ipos0, ipos1);
770   }
771
772   /* #ifdef JAVA2 */
773   public List subList(int fromIx, int toIx)
774   {
775     return new SubSequence(this,
776                            createPos(fromIx, false),
777                        createPos(toIx, true));
778   }
779   /* #endif */
780
781   /** Copy an element specified by a position pair to a Consumer.
782    * @return if hasNext(ipos). */
783   public boolean consumeNext (int ipos, Consumer out)
784   {
785     int next = nextPos(ipos);
786     if (next == 0)
787       return false;
788     consumePosRange(ipos, next, out);
789     return true;
790   }
791
792   public void consumePosRange(int iposStart, int iposEnd, Consumer out)
793   {
794     if (out.ignoring())
795       return;
796     int it = copyPos(iposStart);
797     while (! equals(it, iposEnd))
798       {
799     if (! hasNext(it))
800       throw new RuntimeException ();
801     out.writeObject(getPosNext(it));
802         it = nextPos(it);
803       }
804     releasePos(it);
805   }
806
807   public void consume(Consumer out)
808   {
809     boolean isSequence = this instanceof Sequence;
810     if (isSequence)
811       out.beginGroup("#sequence");
812     consumePosRange(startPos(), endPos(), out);
813     if (isSequence)
814       out.endGroup();
815   }
816
817   public void toString (String sep, StringBuffer sbuf)
818   {
819     boolean seen = false;
820     for (int i = startPos(); (i = nextPos(i)) != 0; )
821       {
822     if (seen)
823       sbuf.append(sep);
824     else
825       seen = true;
826     sbuf.append(getPosPrevious(i));
827       }
828   }
829
830   public String toString ()
831   {
832     StringBuffer sbuf = new StringBuffer (100);
833     if (this instanceof Sequence)
834       sbuf.append('[');
835     toString(", ", sbuf);
836     if (this instanceof Sequence)
837       sbuf.append(']');
838     return sbuf.toString();
839   }
840 }
841

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags