KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > lists > TreeList


1 // Copyright (c) 2001, 2002, 2003, 2006 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 gnu.text.Char;
6
7 /** A compact representation of a tree, that is a nested list structure.
8  * The data structure can store anything that can be emitted to a Consumer.
9  * This data structure is optimized for efficient forwards traversal
10  * through the data structure, not random access.
11  * It does have an "insertion point"; insertions and deletions are
12  * efficient through the use of a buffer gap.
13  * It is a reasonable choice for a "DOM" for XML data.
14  */

15
16 public class TreeList extends AbstractSequence
17   implements
18   /* #ifdef JAVA5 */
19   // Appendable,
20
/* #endif */
21   XConsumer, PositionConsumer, Consumable
22 {
23   // Some public fields and methods are public which probably shouldn't be,
24
// for the sake of XMLFilter. FIXME. Perhaps an abstract class
25
// in gnu.lists that XMLFilter extend?
26

27   public Object JavaDoc[] objects;
28   public int oindex;
29   public char[] data;
30   public int gapStart;
31   public int gapEnd;
32
33   /** If non-zero, gap is in an attribute starting (1 less than) here. */
34   public int attrStart;
35   /** If non-zero, gap is in an document starting (1 less than) here. */
36   public int docStart;
37
38   public TreeList()
39   {
40     resizeObjects();
41     gapEnd = 200;
42     data = new char[gapEnd];
43   }
44
45   /**
46    * Make a copy of a sub-range of a TreeList.
47    * @param list the TreeList to copy
48    * @param startPosition start of range, as a raw index in data
49    * @param endPosition end of range, as a raw index in data
50    */

51   public TreeList(TreeList list, int startPosition, int endPosition)
52   {
53     this();
54     list.consumeIRange(startPosition, endPosition, this);
55   }
56
57   public TreeList(TreeList list)
58   {
59     this(list, 0, list.data.length);
60   }
61
62   public void clear()
63   {
64     gapStart = 0;
65     gapEnd = data.length;
66     attrStart = 0;
67     if (gapEnd > 1500)
68       {
69     gapEnd = 200;
70     data = new char[gapEnd];
71       }
72     objects = null;
73     oindex = 0;
74     resizeObjects();
75   }
76
77   // The data array contains an encoding of values, as follows:
78
// 0x0000 ... 0x9FFF: A single Unicode character.
79
// 0xAXXX: BEGIN_GROUP_SHORT
80
// 0xBXXX: negative integer ((short)0x0XXX<<4)>>4, range -4096 to -1
81
// 0xCXXX: positive integer 0x0XXX, in the range 0 to 4095
82
// 0xDXXX: positive integer 0x1XXX, in the range 4096 to 8191
83
// 0xEXXX:: OBJECT_REF_SHORT. The object in objects[0xXXX].
84
// 0xF0XX: A byte (encoded character or char fragment) ((byte) 0xXX).
85
// 0xF100 ... 0xF101: A Boolean (BOOL_FALSE, BOOL_TRUE)
86
// 0xF102 A B: INT_FOLLOWS - 32-bit int (big-endian)
87
// 0xF103 A B C D: LONG_FOLLOWS 64-bit long int (big-endian)
88
// 0xF104 A B: FLOAT_FOLLOWS 32-bit float (big-endian)
89
// 0xF105 A B C D: DOUBLE_FOLLOWS 64-bit double (big-endian)
90
// 0xF106: CHAR_FOLLOWS
91
// 0xF108: BEGIN_GROUP_LONG
92
// 0xF109: BEGIN_ATTRIBUTE_LONG
93
// 0xF10A: END_ATTRIBUTE
94
// 0xF10B: END_GROUP_SHORT
95
// 0xF10C: END_GROUP_LONG
96
// 0xF10D A B: OBJECT_REF_FOLLOWS: The object in objects[(A,B)].
97
// 0xF10E A B: POSITION_REF_FOLLOWS: The TreePosition in objects[(A,B)].
98
// 0xF10F A B C D: POSITION_PAIR_FOLLOWS
99
// 0xF110 BEGIN_DOCUMENT
100
// 0xF111 END_DOCUMENT
101
// 0xF112 BEGIN_ENTITY
102
// 0xF113 END_ENTITY
103
// 0xF114 PROCESSING_INSTRUCTION
104
// 0xF115 CDATA_SECTION
105
// 0xF116 JOINER
106
// 0xF117 COMMENT
107
// 0xF118 DOCUMENT_URI: Not a node, but a property of the previous document.
108

109   /** The largest Unicode character that can be encoded in one char. */
110   public static final int MAX_CHAR_SHORT = 0x9FFF;
111
112   /** The smallest integer that can use the short int encoding. */
113   static final int MIN_INT_SHORT = -0x1000; // -4096
114

115   /** The largest integer that can use the short int encoding. */
116   static final int MAX_INT_SHORT = 0x1FFF; // 8191
117

118   /** The value used to encode the integer zero. */
119   static final int INT_SHORT_ZERO = 0xC000;
120
121   /** The value used to encode the object in objects[0]. */
122   static final int OBJECT_REF_SHORT = 0xE000;
123
124   /** The maximum offset in the objects array for a short object-ref. */
125   static final int OBJECT_REF_SHORT_INDEX_MAX = 0xFFF;
126
127   /** Followed by 2 chars that provide an index into objects. */
128   static final char OBJECT_REF_FOLLOWS = 0xF10D;
129
130   /** Followed by 2 chars that provide an index into objects. */
131   static final char POSITION_REF_FOLLOWS = 0xF10E;
132
133   /** A position triple referenceing some other "nodes".
134    * Followed by index of sequence (2 chars), and ipos (2 chars). */

135   protected static final char POSITION_PAIR_FOLLOWS = 0xF10F;
136
137   /** Encoding prefix that indicates a byte value. */
138   static final int BYTE_PREFIX = 0xF000;
139
140   /** The value used to encode false. */
141   static final char BOOL_FALSE = 0xF100;
142
143   /** The value used to encode true. */
144   static final char BOOL_TRUE = 0xF101;
145
146   /** A 32-bit integer, non-compact form.
147    *
148    * [INT_FOLLOWS]
149    * [word1], [word2]: The big-endian bits of the integer.
150    */

151   public static final int INT_FOLLOWS = 0xF102;
152
153   /** A 64-bit long integer.
154    *
155    * [LONG_FOLLOWS]
156    * [word1], [word2], [word3], [word4]: The big-endian bits of the long.
157    */

158   static final int LONG_FOLLOWS = 0xF103;
159
160   /** A 64-bit float floating-pointer number.
161    *
162    * [FLOAT_FOLLOWS]
163    * [word1], [word2]: The big-endian bits of the float.
164    */

165   static final int FLOAT_FOLLOWS = 0xF104;
166
167   /** A 64-bit double floating-pointer number.
168    *
169    * [DOUBLE_FOLLOWS]
170    * [word1], [word2], [word3], [word4]: The big-endian bits of the double.
171    */

172   static final int DOUBLE_FOLLOWS = 0xF105;
173
174   /** A 16-bit (non-compact) Unicode char follows. */
175   static final int CHAR_FOLLOWS = 0xF106;
176
177   /** A comment node follows.
178    * [COMMENT]
179    * [length] 2 shorts
180    * [comment text], (length) number of characters.
181    */

182   static final int COMMENT = 0xF117;
183
184   /** A processing-instruction node follows.
185    * [PROCESSING_INSTRUCTION]
186    * [target] 2 shorts, where objects[target] is the target as a String.
187    * [length] 2 shorts.
188    * [comment text], (length) number of characters.
189    */

190   protected static final int PROCESSING_INSTRUCTION = 0xF114;
191
192   /** A CDATA node follows.
193    * [CDATA_SECTION]
194    * [length] 2 shorts
195    * [comment text], (length) number of characters.
196    */

197   static final int CDATA_SECTION = 0xF115;
198
199   /** Suppress spacing between non-node items. */
200   static final int JOINER = 0xF116;
201
202   /** The beginning of an attribute.
203    * [BEGIN_ATTRIBUTE_LONG]
204    * [index], 2 shorts, where objects[index] is the attribute type name
205    * and objects[index+1] is the attribute type object.
206    * [end_offset], 2 shorts, giving the location of the following
207    * END_ATTRIBUTE. If the attribute straddles the gap, then
208    * end_offset is a negative offset relative to data.length.
209    * (Therefore allocating more space for the gap does not require
210    * adjusting end_offset.) Otherwise, the end_offset is relative
211    * to the BEGIN_ATTRIBUTE_LONG word.
212    */

213   protected static final int BEGIN_ATTRIBUTE_LONG = 0xF109;
214   public static final int BEGIN_ATTRIBUTE_LONG_SIZE = 5;
215
216   /** The end of an attribute of a node. */
217   static final int END_ATTRIBUTE = 0xF10A;
218   public static final int END_ATTRIBUTE_SIZE = 1;
219
220   /** Beginning of a document (or top-level value).
221    * Used to distinguish a document from its element node.
222    * [end_offset], 2 shorts, giving the location of the following
223    * END_DOCUMENT. If the attribute straddles the gap, then
224    * end_offset is a negative offset relative to data.length.
225    * (Therefore allocating more space for the gap does not require
226    * adjusting end_offset.) Otherwise, the end_offset is relative
227    * to the BEGIN_DOCUMENT word.
228    * [parent_offset], in 2 shorts. The parent node, or -1 if no parent.
229    * Otherwise, a negative value is a relative offset, while a non-negative
230    * value is absolute. (Use the latter when gap is between this node and
231    * its parent. The parent would normally be a BEGIN_ENTITY.
232    */

233   protected static final int BEGIN_DOCUMENT = 0xF110;
234
235   /** End of a document. */
236   protected static final int END_DOCUMENT = 0xF111;
237
238   /** End of an entity (typically a file, possibly included).
239    * [base_uri], 2 short, given an index of a base-uri object
240    * [parent_offset], in 2 shorts, encoded as for BEGIN_DOCUMENT.
241    */

242   public static final int BEGIN_ENTITY = 0xF112;
243   public static final int BEGIN_ENTITY_SIZE = 5;
244
245   protected static final int END_ENTITY = 0xF113;
246
247   /** The document-uri property of a node.
248    * This is not an actual value, but it is a property of the previous
249    * document node, or the surrounding node just after a BEGIN_XXX entry.
250    * [DOCUMENT_URI]
251    * [index]. 2 shorts, where objects[index] is the document-uri value.
252    */

253   protected static final int DOCUMENT_URI = 0xF118;
254
255   /** Beginning of a group, compact form.
256    *
257    * [BEGIN_GROUP_SHORT + index], where objects[index] is the group's
258    * type name and objects[index+1] is the type object.
259    * [end_offset], the unsigned offset (from the initial word)
260    * to the corresponding END_GROUP_SHORT.
261    * [parent_offset], the (unsigned absolute value of the) offset
262    * to the outer BEGIN_GROUP_SHORT/BEGIN_GROUP_LONG/BEGIN_DOCUMENT.
263    *. (If these is no parent, then parent_offset==0.)
264    *
265    * This should is used when index < BEGIN_GROUP_SHORT_INDEX_MAX,
266    * both end_offset and parent_offset fit in 16 bits,
267    * and the group does not straddle the gap.
268    */

269   protected static final int BEGIN_GROUP_SHORT = 0xA000;
270   protected static final int BEGIN_GROUP_SHORT_INDEX_MAX = 0xFFF;
271
272   /** End of a group, compact form.
273    *
274    * [END_GROUP_SHORT]
275    * [begin_offset], the unsigned absolute value of the offset to the
276    * matching BEGIN. (This is the same as the matching end_offset.)
277    *
278    */

279   protected static final int END_GROUP_SHORT = 0xF10B;
280
281   /** Begin of a group, non-compact form.
282    *
283    * [BEGIN_GROUP_LONG]
284    * [end_offset], in 2 shorts. The position of the matching END_GROUP_LONG.
285    * If the group straddles the gap, then end_offset is a negative offset
286    * relative to data.length. (Therefore allocating more space for the
287    * gap does not require adjusting any end_offset.) If the group and
288    * and its children are all on the same side of the gap, then end_offset
289    * is a positive offset relative to the BEGIN_GROUP_LONG word. (Hence
290    * shifting an entire group when the gap is moved does not require
291    * changing its end_offset.)
292    *
293    * Note that the space taken by a BEGIN_GROUP_LONG is the same that
294    * needed for a BEGIN_GROUP_SHORT (but a END_GROUP_LONG takes much
295    * more space than a END_GROUP_SHORT). This is to make it easier
296    * to convert a BEGIN_GROUP_LONG to a BEGIN_GROUP_SHORT or vice
297    * versa, as needed.
298    */

299   protected static final int BEGIN_GROUP_LONG = 0xF108;
300
301   /** End of a group, non-compact form.
302    *
303    * [END_GROUP_LONG]
304    * [index], 2 shorts where objects[index] is the group's type name and
305    * objects[index+1] is the type object.
306    * [begin_offset], in 2 shorts. The position of the matching
307    * BEGIN_GROUP_LONG. If the group straddles the gap, then begin_offset
308    * is the actual index (i.e. relative to the start of data) of the
309    * matching BEGIN_GROUP_LONG. (Therefore allocating more space for the
310    * gap does not require adjusting begin_offset.) If the group does not
311    * straddle the gap, then begin_offset is a negative offset relative
312    * to the END_GROUP_LONG word. (Hence shifting an entire group when
313    * the gap is moved does not require changing its begin_offset.)
314    * relative to data.length.
315    * [parent_offset], in 2 shorts. The position of the outer BEGIN_GROUP_LONG,
316    * BEGIN_GROUP_SHORT or BEGIN_DOCUMENT. If the difference straddles
317    * the gap (i.e. either this group straddles the gap or the parent group
318    * does and the gap precedes this group), then parent_offset is the
319    * actual index of the parent group. Otherwise, then parent_offset is a
320    * negative offset relative to the END_GROUP_LONG word.
321    */

322   protected static final int END_GROUP_LONG = 0xF10C;
323
324   int currentParent = -1;
325
326   public void ensureSpace(int needed)
327   {
328     int avail = gapEnd - gapStart;
329     if (needed > avail)
330       {
331     int oldSize = data.length;
332     int neededSize = oldSize - avail + needed;
333     int newSize = 2 * oldSize;
334     if (newSize < neededSize)
335       newSize = neededSize;
336     char[] tmp = new char[newSize];
337     if (gapStart > 0)
338       System.arraycopy(data, 0, tmp, 0, gapStart);
339     int afterGap = oldSize - gapEnd;
340     if (afterGap > 0)
341       System.arraycopy(data, gapEnd, tmp, newSize - afterGap, afterGap);
342     gapEnd = newSize - afterGap;
343     data = tmp;
344       }
345   }
346
347   public final void resizeObjects()
348   {
349     int oldLength;
350     int newLength;
351     Object JavaDoc[] tmp;
352     if (objects == null)
353       {
354     oldLength = 0;
355     newLength = 100;
356     tmp = new Object JavaDoc[newLength];
357       }
358     else
359       {
360     oldLength = objects.length;
361     newLength = 2 * oldLength;
362     tmp = new Object JavaDoc[newLength];
363     System.arraycopy(objects, 0, tmp, 0, oldLength);
364       }
365     objects = tmp;
366   }
367
368   public int find (Object JavaDoc arg1)
369   {
370     if (oindex == objects.length)
371       resizeObjects();
372     objects[oindex] = arg1;
373     return oindex++;
374   }
375
376   /** Get a 32-bit int from the data array. */
377   final protected int getIntN(int index)
378   {
379     return (data[index] << 16) | (data[index + 1] & 0xFFFF);
380   }
381
382   /** Get a 64-bit long from the data array. */
383   final protected long getLongN(int index)
384   {
385     char[] data = this.data; // Optimization.
386
return (data[index] & 0xFFFFL) << 48
387       | (data[index+1] & 0xFFFFL) << 32
388       | (data[index+2] & 0xFFFFL) << 16
389       | (data[index+3] & 0xFFFFL);
390   }
391
392   final public void setIntN(int index, int i)
393   {
394     data[index] = (char) (i >> 16);
395     data[index+1] = (char) i;
396   }
397
398   public void consume (SeqPosition position)
399   {
400     ensureSpace(3);
401     // FIXME - no need for find to search in this case!
402
int index = find(position.copy());
403     data[gapStart++] = POSITION_REF_FOLLOWS;
404     setIntN(gapStart, index);
405     gapStart += 2;
406   }
407
408   public void writePosition(AbstractSequence seq, int ipos)
409   {
410     ensureSpace(5);
411     data[gapStart] = POSITION_PAIR_FOLLOWS;
412     int seq_index = find(seq);
413     setIntN(gapStart+1, seq_index);
414     setIntN(gapStart+3, ipos);
415     gapStart += 5;
416   }
417
418   public void writeObject(Object JavaDoc v)
419   {
420     ensureSpace(3);
421     int index = find(v);
422     if (index < 0x1000)
423       data[gapStart++] = (char) (OBJECT_REF_SHORT | index);
424     else
425       {
426     data[gapStart++] = OBJECT_REF_FOLLOWS;
427     setIntN(gapStart, index);
428     gapStart += 2;
429       }
430   }
431
432   /** Write/set the document-uri property of the current document.
433    * Only allowed immediately following beginDocument. */

434   public void writeDocumentUri (Object JavaDoc uri)
435   {
436     ensureSpace(3);
437     int index = find(uri);
438     data[gapStart++] = DOCUMENT_URI;
439     setIntN(gapStart, index);
440     gapStart += 2;
441   }
442
443   public void writeComment(char[] chars, int offset, int length)
444   {
445     ensureSpace(3+length);
446     int i = gapStart;
447     data[i++] = COMMENT;
448     setIntN(i, length);
449     i += 2;
450     System.arraycopy(chars, offset, data, i, length);
451     gapStart = i + length;
452   }
453
454   public void writeProcessingInstruction(String JavaDoc target, char[] content,
455                      int offset, int length)
456   {
457     ensureSpace(5+length);
458     int i = gapStart;
459     data[i++] = PROCESSING_INSTRUCTION;
460     int index = find(target);
461     setIntN(i, index);
462     setIntN(i+2, length);
463     i += 4;
464     System.arraycopy(content, offset, data, i, length);
465     gapStart = i + length;
466   }
467
468   public void beginGroup(Object JavaDoc type)
469   {
470     beginGroup(find(type));
471   }
472
473   public void beginDocument()
474   {
475     ensureSpace(5+1);
476     gapEnd--;
477     int p = gapStart;
478     data[p] = BEGIN_DOCUMENT;
479     if (docStart != 0)
480       throw new Error JavaDoc("nested document");
481     docStart = p+1;
482     setIntN(p+1, gapEnd - data.length);
483     setIntN(p+3, currentParent == -1 ? -1 : currentParent-p); // parent_offset
484
currentParent = p;
485     gapStart = p + 5;
486     currentParent = p;
487     data[gapEnd] = END_DOCUMENT;
488   }
489
490   public void endDocument()
491   {
492     if (data[gapEnd] != END_DOCUMENT || docStart <= 0
493         || data[currentParent] != BEGIN_DOCUMENT)
494       throw new Error JavaDoc("unexpected endDocument");
495     // Move the END_DOCUMENT to before the gap.
496
gapEnd++;
497     setIntN(docStart, gapStart - docStart + 1);
498     docStart = 0;
499     data[gapStart++] = END_DOCUMENT;
500     int parent = getIntN(currentParent+3);
501     currentParent = parent >= -1 ? parent : currentParent + parent;
502   }
503
504   public void beginEntity (Object JavaDoc base)
505   {
506     ensureSpace(BEGIN_ENTITY_SIZE+1);
507     gapEnd--;
508     int p = gapStart;
509     data[p] = BEGIN_ENTITY;
510     setIntN(p+1, find(base));
511     setIntN(p+3, currentParent == -1 ? -1 : currentParent-p); // parent_offset
512
gapStart = p + 5;
513     currentParent = p;
514     data[gapEnd] = END_ENTITY;
515   }
516
517   public void endEntity ()
518   {
519     if (data[gapEnd] != END_ENTITY
520         || data[currentParent] != BEGIN_ENTITY)
521       throw new Error JavaDoc("unexpected endEntity");
522     // Move the END_ENTITY to before the gap.
523
gapEnd++;
524     data[gapStart++] = END_ENTITY;
525     int parent = getIntN(currentParent+3);
526     currentParent = parent >= -1 ? parent : currentParent + parent;
527   }
528
529   public void beginGroup(int index)
530   {
531     ensureSpace(3 + 7);
532     gapEnd -= 7;
533     data[gapStart++] = BEGIN_GROUP_LONG;
534     setIntN(gapStart, gapEnd - data.length); // end_offset
535
gapStart += 2;
536     data[gapEnd] = END_GROUP_LONG;
537     setIntN(gapEnd + 1, index); // begin_offset
538
setIntN(gapEnd + 3, gapStart - 3); // begin_offset
539
setIntN(gapEnd + 5, currentParent); // parent_offset
540
currentParent = gapStart - 3;
541   }
542
543   public void setGroupName (int groupIndex, int nameIndex)
544   {
545     if (data[groupIndex] == BEGIN_GROUP_LONG)
546       {
547         int j = getIntN(groupIndex+1);
548         groupIndex = j + (j < 0 ? data.length : groupIndex);
549       }
550     if (groupIndex < gapEnd)
551       throw new Error JavaDoc("setGroupName before gapEnd");
552     setIntN(groupIndex + 1, nameIndex);
553   }
554
555   public void endGroup ()
556   {
557     if (data[gapEnd] != END_GROUP_LONG)
558       throw new Error JavaDoc("unexpected endGroup");
559     int index = getIntN(gapEnd + 1);
560     int begin = getIntN(gapEnd + 3);
561     int parent = getIntN(gapEnd + 5);
562     currentParent = parent;
563     gapEnd += 7;
564     int offset = gapStart - begin;
565     int parentOffset = begin - parent;
566     if (index < BEGIN_GROUP_SHORT_INDEX_MAX
567     && offset < 0x10000 && parentOffset < 0x10000)
568       {
569     data[begin] = (char) (BEGIN_GROUP_SHORT | index);
570     data[begin + 1] = (char) offset; // end_offset
571
data[begin + 2] = (char) parentOffset;
572     data[gapStart] = END_GROUP_SHORT;
573     data[gapStart + 1] = (char) offset; // begin_offset
574
gapStart += 2;
575       }
576     else
577       {
578     data[begin] = BEGIN_GROUP_LONG;
579     setIntN(begin + 1, offset);
580     data[gapStart] = END_GROUP_LONG;
581     setIntN(gapStart + 1, index);
582     setIntN(gapStart + 3, - offset);
583     if (parent >= gapStart || begin <= gapStart)
584       parent -= gapStart;
585     setIntN(gapStart + 5, parent);
586     gapStart += 7;
587       }
588   }
589
590   public void beginAttribute(Object JavaDoc attrType)
591   {
592     beginAttribute(find(attrType));
593   }
594
595   public void beginAttribute(int index)
596   {
597     /* This needs to be tested. FIXME. Anyway only solves limited problem.
598     // If there is whitespace and nothing else between the BEGIN_GROUP_LONG
599     // and the current position, get rid of the spaces.
600     int i = currentParent;
601     if (i > 0 && (i += 3) < gapStart)
602       {
603     for (int j = i; ; j++)
604       {
605         if (j == gapStart)
606           {
607         gapStart = i;
608         break;
609           }
610         char c = data[j];
611         if (c != ' ' && c != '\t' && c != '\n' && c != '\r')
612           break;
613       }
614       }
615     */

616
617     ensureSpace(5 + 1);
618     gapEnd--;
619     data[gapStart++] = BEGIN_ATTRIBUTE_LONG;
620     if (attrStart != 0)
621       throw new Error JavaDoc("nested attribute");
622     attrStart = gapStart;
623     setIntN(gapStart, index);
624     setIntN(gapStart + 2, gapEnd - data.length);
625     gapStart += 4;
626     data[gapEnd] = END_ATTRIBUTE;
627   }
628
629   public void setAttributeName (int attrIndex, int nameIndex)
630   {
631     setIntN(attrIndex + 1, nameIndex);
632   }
633
634   public void endAttribute()
635   {
636     if (attrStart <= 0)
637       return;
638     if (data[gapEnd] != END_ATTRIBUTE)
639       throw new Error JavaDoc("unexpected endAttribute");
640     // Move the END_ATTRIBUTES to before the gap.
641
gapEnd++;
642     setIntN(attrStart+2, gapStart - attrStart + 1);
643     attrStart = 0;
644     data[gapStart++] = END_ATTRIBUTE;
645   }
646
647   public Consumer append (char c)
648   {
649     write(c);
650     return this;
651   }
652
653   public void write (int c)
654   {
655     ensureSpace(3);
656     if (c <= MAX_CHAR_SHORT)
657       data[gapStart++] = (char) c;
658     else if (c < 0x10000)
659       {
660     data[gapStart++] = CHAR_FOLLOWS;
661     data[gapStart++] = (char) c;
662       }
663     else
664       Char.print(c, this);
665   }
666
667   public void writeBoolean(boolean v)
668   {
669     ensureSpace(1);
670     data[gapStart++] = v ? BOOL_TRUE : BOOL_FALSE;
671   }
672
673   public void writeByte(int v)
674   {
675     ensureSpace(1);
676     data[gapStart++] = (char) (BYTE_PREFIX + (v & 0xFF));
677   }
678
679   public void writeInt(int v)
680   {
681     ensureSpace(3);
682     if (v >= MIN_INT_SHORT && v <= MAX_INT_SHORT)
683       data[gapStart++] = (char) (INT_SHORT_ZERO + v);
684     else
685       {
686     data[gapStart++] = INT_FOLLOWS;
687     setIntN(gapStart, v);
688     gapStart += 2;
689       }
690   }
691
692   public void writeLong(long v)
693   {
694     ensureSpace(5);
695     data[gapStart++] = LONG_FOLLOWS;
696     data[gapStart++] = (char) (v >>> 48);
697     data[gapStart++] = (char) (v >>> 32);
698     data[gapStart++] = (char) (v >>> 16);
699     data[gapStart++] = (char) v;
700   }
701
702   public void writeFloat(float v)
703   {
704     ensureSpace(3);
705     int i = Float.floatToIntBits(v);
706     data[gapStart++] = FLOAT_FOLLOWS;
707     data[gapStart++] = (char) (i >>> 16);
708     data[gapStart++] = (char) i;
709   }
710
711   public void writeDouble(double v)
712   {
713     ensureSpace(5);
714     long l = Double.doubleToLongBits(v);
715     data[gapStart++] = DOUBLE_FOLLOWS;
716     data[gapStart++] = (char) (l >>> 48);
717     data[gapStart++] = (char) (l >>> 32);
718     data[gapStart++] = (char) (l >>> 16);
719     data[gapStart++] = (char) l;
720   }
721
722   public boolean ignoring()
723   {
724     return false;
725   }
726
727   public void writeJoiner ()
728   {
729     ensureSpace(1);
730     data[gapStart++] = JOINER;
731   }
732
733   public void write(char[] buf, int off, int len)
734   {
735     if (len == 0)
736       writeJoiner();
737     ensureSpace(len);
738     while (len > 0)
739       {
740     char ch = buf[off++];
741     len--;
742     if (ch <= MAX_CHAR_SHORT)
743       data[gapStart++] = ch;
744     else
745       {
746         write(ch);
747         ensureSpace(len);
748       }
749       }
750   }
751
752   public void write (String JavaDoc str)
753   {
754     write(str, 0, str.length());
755   }
756
757   /* #ifdef use:java.lang.CharSequence */
758   public void write (CharSequence JavaDoc str, int start, int length)
759   /* #else */
760   // public void write (String str, int start, int length)
761
/* #endif */
762   {
763     if (length == 0)
764       writeJoiner();
765     ensureSpace(length);
766     while (length > 0)
767       {
768     char ch = str.charAt(start++);
769     length--;
770     if (ch <= MAX_CHAR_SHORT)
771       data[gapStart++] = ch;
772     else
773       {
774         write(ch);
775         ensureSpace(length);
776       }
777       }
778   }
779
780   public void writeCDATA (char[] chars, int offset, int length)
781   {
782     ensureSpace(3+length);
783     int i = gapStart;
784     data[i++] = CDATA_SECTION;
785     setIntN(i, length);
786     i += 2;
787     System.arraycopy(chars, offset, data, i, length);
788     gapStart = i + length;
789   }
790
791   /* #ifdef use:java.lang.CharSequence */
792   public Consumer append (CharSequence JavaDoc csq)
793   {
794     if (csq == null)
795       csq = "null";
796     return append(csq, 0, csq.length());
797   }
798
799   public Consumer append (CharSequence JavaDoc csq, int start, int end)
800   {
801     if (csq == null)
802       csq = "null";
803     for (int i = start; i < end; i++)
804       append(csq.charAt(i));
805     return this;
806   }
807   /* #else */
808   // public Consumer append (String str)
809
// {
810
// if (str == null)
811
// str = "null";
812
// int len = str.length();
813
// for (int i = 0; i < len; i++)
814
// append(str.charAt(i));
815
// return this;
816
// }
817
/* #endif */
818
819   public boolean isEmpty()
820   {
821     // FIXME does not work if we allow comment() entries!
822
int pos = gapStart == 0 ? gapEnd : 0;
823     return pos == data.length;
824   }
825
826   public int size()
827   {
828     int size = 0;
829     int i = 0;
830     for (;;)
831       {
832     i = nextPos(i);
833     if (i == 0)
834       return size;
835     size++;
836       }
837   }
838
839   public int createPos(int index, boolean isAfter)
840   {
841     return createRelativePos(0, index, isAfter);
842   }
843
844   public final int posToDataIndex (int ipos)
845   {
846     if (ipos == -1)
847       return data.length;
848     int index = ipos >>> 1;
849     if ((ipos & 1) != 0)
850       index--;
851     if (index >= gapStart)
852       index += gapEnd - gapStart;
853     if ((ipos & 1) != 0)
854       {
855     index = nextDataIndex(index);
856     if (index < 0)
857       return data.length;
858     if (index == gapStart)
859       index += gapEnd - gapStart;
860       }
861     return index;
862   }
863
864   public int firstChildPos (int ipos)
865   {
866     int index = gotoChildrenStart(posToDataIndex(ipos));
867     if (index < 0)
868       return 0;
869     return index << 1;
870   }
871
872   public final int gotoChildrenStart(int index)
873   {
874     if (index == data.length)
875       return -1;
876     char datum = data[index];
877     if ((datum >= BEGIN_GROUP_SHORT
878      && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
879     || datum == BEGIN_GROUP_LONG)
880       index += 3;
881     else if (datum == BEGIN_DOCUMENT || datum == BEGIN_ENTITY)
882       index += 5;
883     else
884       return -1;
885     for (;;)
886       {
887     if (index >= gapStart)
888       index += gapEnd - gapStart;
889     datum = data[index];
890     if (datum == BEGIN_ATTRIBUTE_LONG)
891       {
892         int end = getIntN(index+3);
893         index = end + (end < 0 ? data.length : index);
894       }
895     else if (datum == END_ATTRIBUTE || datum == JOINER)
896       index++;
897     else if (datum == DOCUMENT_URI)
898       index += 3;
899     else
900       break;
901       }
902     return index;
903   }
904
905   public int parentPos (int ipos)
906   {
907     int index = posToDataIndex(ipos);
908     for (;;)
909       {
910         index = parentOrEntityI(index);
911         if (index == -1)
912           return -1;
913         if (data[index] != BEGIN_ENTITY)
914           return index << 1;
915       }
916   }
917
918   public int parentOrEntityPos (int ipos)
919   {
920     int index = parentOrEntityI(posToDataIndex(ipos));
921     return index < 0 ? -1 : index << 1;
922   }
923
924   public int parentOrEntityI (int index)
925   {
926     if (index == data.length)
927       return -1;
928     char datum = data[index];
929     if (datum == BEGIN_DOCUMENT || datum == BEGIN_ENTITY)
930       {
931     int parent_offset = getIntN(index+3);
932         if (parent_offset >= -1)
933           return parent_offset;
934         else
935           return index + parent_offset;
936       }
937     if (datum >= BEGIN_GROUP_SHORT
938      && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
939       {
940     int parent_offset = data[index+2];
941     return parent_offset == 0 ? -1 : index - parent_offset;
942       }
943     if (datum == BEGIN_GROUP_LONG)
944       {
945     int end_offset = getIntN(index+1);
946     end_offset += end_offset < 0 ? data.length : index;
947     int parent_offset = getIntN(end_offset+5);
948     if (parent_offset == 0)
949       return -1;
950     if (parent_offset < 0)
951       parent_offset += end_offset;
952     return parent_offset;
953       }
954     for (;;)
955       {
956     if (index == gapStart)
957       index = gapEnd;
958     if (index == data.length)
959       return -1;
960     datum = data[index];
961     switch (datum)
962       {
963       case END_GROUP_SHORT:
964         return index - data[index+1];
965       case END_GROUP_LONG:
966         int begin_offset = getIntN(index+3);
967         if (begin_offset < 0)
968           begin_offset += index;
969         return begin_offset;
970       case END_ATTRIBUTE:
971         index++;
972         continue;
973       case END_DOCUMENT:
974         return -1;
975       default:
976         index = nextDataIndex(index);
977       }
978     if (index < 0)
979       break;
980       }
981     return -1;
982   }
983
984   public int getAttributeCount (int parent)
985   {
986     int n = 0;
987     for (int attr = firstAttributePos(parent);
988          attr != 0 && getNextKind(attr) == Sequence.ATTRIBUTE_VALUE;
989          attr = nextPos(attr))
990       n++;
991     return n;
992   }
993
994   public boolean gotoAttributesStart(TreePosition pos)
995   {
996     int index = gotoAttributesStart(pos.ipos >> 1);
997     if (index < 0)
998       return false;
999     pos.push(this, index << 1);
1000    return true;
1001  }
1002
1003  public int firstAttributePos (int ipos)
1004  {
1005    int index = gotoAttributesStart(posToDataIndex(ipos));
1006    return index < 0 ? 0 : index << 1;
1007  }
1008
1009  public int gotoAttributesStart(int index)
1010  {
1011    if (index >= gapStart)
1012      index += gapEnd - gapStart;
1013    if (index == data.length)
1014      return -1;
1015    char datum = data[index];
1016    if ((datum >= BEGIN_GROUP_SHORT
1017     && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1018    || datum == BEGIN_GROUP_LONG)
1019      return index + 3;
1020    else
1021      return -1;
1022  }
1023
1024  public Object JavaDoc get (int index)
1025  {
1026    int i = 0;
1027    while (--index >= 0)
1028      {
1029    i = nextPos(i);
1030    if (i == 0)
1031      throw new IndexOutOfBoundsException JavaDoc();
1032      }
1033    return getPosNext(i);
1034  }
1035
1036  public boolean consumeNext(int ipos, Consumer out)
1037  {
1038    if (! hasNext(ipos))
1039      return false;
1040    int start = posToDataIndex(ipos);
1041    int end = nextNodeIndex(start, -1 >>> 1);
1042    if (end == start)
1043      end = nextDataIndex(start);
1044    if (end >= 0)
1045      consumeIRange(start, end, out);
1046    return true;
1047  }
1048
1049  public void consumePosRange(int startPos, int endPos, Consumer out)
1050  {
1051    consumeIRange(posToDataIndex(startPos), posToDataIndex(endPos), out);
1052  }
1053
1054  public int consumeIRange(int startPosition, int endPosition, Consumer out)
1055  {
1056    int pos = startPosition;
1057    int limit = startPosition <= gapStart && endPosition > gapStart ? gapStart
1058      : endPosition;
1059    int index;
1060    for (;;)
1061      {
1062    if (pos >= limit)
1063      {
1064        if (pos == gapStart && endPosition > gapEnd)
1065          {
1066        pos = gapEnd;
1067        limit = endPosition;
1068          }
1069        else
1070          break;
1071      }
1072
1073    char datum = data[pos++];
1074
1075    if (datum <= MAX_CHAR_SHORT)
1076      {
1077        int start = pos - 1;
1078        int lim = limit;
1079        for (;;)
1080          {
1081        if (pos >= lim)
1082          break;
1083        datum = data[pos++];
1084        if (datum > MAX_CHAR_SHORT)
1085          {
1086            pos--;
1087            break;
1088          }
1089          }
1090        out.write(data, start, pos - start);
1091        continue;
1092      }
1093    if (datum >= OBJECT_REF_SHORT
1094         && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1095      {
1096        out.writeObject(objects[datum-OBJECT_REF_SHORT]);
1097        continue;
1098      }
1099    if (datum >= BEGIN_GROUP_SHORT
1100        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1101      {
1102        index = datum-BEGIN_GROUP_SHORT;
1103        out.beginGroup(objects[index]);
1104        pos += 2;
1105        continue;
1106      }
1107    /*
1108    if ((datum & 0xFF00) == BYTE_PREFIX)
1109      {
1110        out.writeByte((byte) datum);
1111        continue;
1112      }
1113    */

1114    if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1115        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1116      {
1117        out.writeInt(datum - INT_SHORT_ZERO);
1118        continue;
1119      }
1120    switch (datum)
1121      {
1122      case BEGIN_DOCUMENT:
1123        out.beginDocument();
1124        pos += 4;
1125        continue;
1126      case END_DOCUMENT:
1127        out.endDocument();
1128        continue;
1129          case BEGIN_ENTITY:
1130        if (out instanceof TreeList)
1131          ((TreeList) out).beginEntity(objects[getIntN(pos)]);
1132        pos += 4;
1133            continue;
1134          case END_ENTITY:
1135        if (out instanceof TreeList)
1136          ((TreeList) out).endEntity();
1137             continue;
1138      case DOCUMENT_URI:
1139        if (out instanceof TreeList)
1140          ((TreeList) out).writeDocumentUri(objects[getIntN(pos)]);
1141        pos += 2;
1142        continue;
1143      case COMMENT:
1144        {
1145          int length = getIntN(pos);
1146          pos += 2;
1147          if (out instanceof XConsumer)
1148        ((XConsumer) out).writeComment(data, pos, length);
1149          pos += length;
1150        }
1151        continue;
1152      case CDATA_SECTION:
1153        {
1154          int length = getIntN(pos);
1155          pos += 2;
1156          if (out instanceof XConsumer)
1157        ((XConsumer) out).writeCDATA(data, pos, length);
1158              else
1159                out.write(data, pos, length);
1160          pos += length;
1161        }
1162        continue;
1163      case PROCESSING_INSTRUCTION:
1164        {
1165          String JavaDoc target = (String JavaDoc) objects[getIntN(pos)];
1166          int length = getIntN(pos+2);
1167          pos += 4;
1168          if (out instanceof XConsumer)
1169        ((XConsumer) out).writeProcessingInstruction(target, data,
1170                                 pos, length);
1171          pos += length;
1172        }
1173        continue;
1174      case BOOL_FALSE:
1175      case BOOL_TRUE:
1176        out.writeBoolean(datum != BOOL_FALSE);
1177        continue;
1178          case JOINER:
1179            out.write("");
1180            continue;
1181      case CHAR_FOLLOWS:
1182        out.write(data, pos, 1 + datum - CHAR_FOLLOWS);
1183        pos++;
1184        continue;
1185      case POSITION_PAIR_FOLLOWS:
1186        {
1187          AbstractSequence seq = (AbstractSequence) objects[getIntN(pos)];
1188          int ipos = getIntN(pos+2);
1189          if (out instanceof PositionConsumer)
1190        ((PositionConsumer) out).writePosition(seq, ipos);
1191          else
1192        out.writeObject(seq.getIteratorAtPos(ipos));
1193          pos += 4;
1194        }
1195        continue;
1196      case POSITION_REF_FOLLOWS:
1197        if (out instanceof PositionConsumer)
1198          {
1199        ((PositionConsumer) out).consume((SeqPosition) objects[getIntN(pos)]);
1200        pos += 2;
1201        continue;
1202          }
1203        // ... else fall through ...
1204
case OBJECT_REF_FOLLOWS:
1205        out.writeObject(objects[getIntN(pos)]);
1206        pos += 2;
1207        continue;
1208      case END_GROUP_SHORT:
1209        pos++;
1210        out.endGroup();
1211        continue;
1212      case BEGIN_GROUP_LONG:
1213        index = getIntN(pos);
1214        index += index >= 0 ? pos - 1 : data.length;
1215        pos += 2;
1216        index = getIntN(index + 1);
1217        out.beginGroup(objects[index]);
1218        continue;
1219      case END_GROUP_LONG:
1220        index = getIntN(pos);
1221        out.endGroup();
1222        pos += 6;
1223        continue;
1224      case BEGIN_ATTRIBUTE_LONG:
1225        index = getIntN(pos);
1226        out.beginAttribute(objects[index]);
1227        pos += 4;
1228        continue;
1229      case END_ATTRIBUTE:
1230        out.endAttribute();
1231        continue;
1232      case INT_FOLLOWS:
1233        out.writeInt(getIntN(pos));
1234        pos += 2;
1235        continue;
1236      case FLOAT_FOLLOWS:
1237        out.writeFloat(Float.intBitsToFloat(getIntN(pos)));
1238        pos += 2;
1239        continue;
1240      case LONG_FOLLOWS:
1241        out.writeLong(getLongN(pos));
1242        pos += 4;
1243        continue;
1244      case DOUBLE_FOLLOWS:
1245        out.writeDouble(Double.longBitsToDouble(getLongN(pos)));
1246        pos += 4;
1247        continue;
1248      default:
1249        throw new Error JavaDoc("unknown code:"+(int) datum);
1250      }
1251      }
1252    return pos;
1253  }
1254
1255  public void toString (String JavaDoc sep, StringBuffer JavaDoc sbuf)
1256  {
1257    int pos = 0;
1258    int limit = gapStart;
1259    int index;
1260    boolean seen = false;
1261    boolean inStartTag = false;
1262    boolean inAttribute = false;
1263    for (;;)
1264      {
1265    if (pos >= limit)
1266      {
1267        if (pos == gapStart)
1268          {
1269        pos = gapEnd;
1270        limit = data.length;
1271        if (pos == limit)
1272          break;
1273          }
1274        else
1275          break;
1276      }
1277
1278    char datum = data[pos++];
1279
1280    if (datum <= MAX_CHAR_SHORT)
1281      {
1282        int start = pos - 1;
1283        int lim = limit;
1284        for (;;)
1285          {
1286        if (pos >= lim)
1287          break;
1288        datum = data[pos++];
1289        if (datum > MAX_CHAR_SHORT)
1290          {
1291            pos--;
1292            break;
1293          }
1294          }
1295        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1296        sbuf.append(data, start, pos - start);
1297        seen = false;
1298        continue;
1299      }
1300    if (datum >= OBJECT_REF_SHORT
1301         && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1302      {
1303        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1304        if (seen) sbuf.append(sep); else seen = true;
1305        sbuf.append(objects[datum-OBJECT_REF_SHORT]);
1306        continue;
1307      }
1308    if (datum >= BEGIN_GROUP_SHORT
1309        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1310      {
1311        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1312        index = datum-BEGIN_GROUP_SHORT;
1313        if (seen) sbuf.append(sep);
1314        sbuf.append('<');
1315        sbuf.append(objects[index].toString());
1316        pos += 2;
1317        seen = false;
1318        inStartTag = true;
1319        continue;
1320      }
1321    if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1322        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1323      {
1324        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1325        if (seen) sbuf.append(sep); else seen = true;
1326        sbuf.append(datum - INT_SHORT_ZERO);
1327        continue;
1328      }
1329    switch (datum)
1330      {
1331      case BEGIN_DOCUMENT:
1332      case BEGIN_ENTITY:
1333        pos += 4;
1334        continue;
1335      case DOCUMENT_URI:
1336        pos += 2;
1337        continue;
1338      case COMMENT:
1339        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1340        index = getIntN(pos); // comment length
1341
pos += 2;
1342        sbuf.append("<!--");
1343        sbuf.append(data, pos, index);
1344        sbuf.append("-->");
1345        pos += index;
1346        continue;
1347      case CDATA_SECTION:
1348        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1349        index = getIntN(pos); // comment length
1350
pos += 2;
1351        sbuf.append("<![CDATA[");
1352        sbuf.append(data, pos, index);
1353        sbuf.append("]]>");
1354        pos += index;
1355        continue;
1356      case PROCESSING_INSTRUCTION:
1357        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1358        sbuf.append("<?");
1359        index = getIntN(pos); // target
1360
pos += 2;
1361        sbuf.append(objects[index]);
1362        index = getIntN(pos); // comment length
1363
pos += 2;
1364        if (index > 0)
1365          {
1366        sbuf.append(' ');
1367        sbuf.append(data, pos, index);
1368        pos += index;
1369          }
1370        sbuf.append("?>");
1371        continue;
1372      case END_DOCUMENT:
1373      case END_ENTITY:
1374        continue;
1375      case BOOL_FALSE:
1376      case BOOL_TRUE:
1377        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1378        if (seen) sbuf.append(sep); else seen = true;
1379        sbuf.append(datum != BOOL_FALSE);
1380        continue;
1381          case JOINER:
1382            continue;
1383      case CHAR_FOLLOWS:
1384        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1385        sbuf.append(data, pos, 1 + datum - CHAR_FOLLOWS);
1386        seen = false;
1387        pos++;
1388        continue;
1389      case POSITION_PAIR_FOLLOWS:
1390        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1391        if (seen) sbuf.append(sep); else seen = true;
1392        {
1393          AbstractSequence seq = (AbstractSequence) objects[getIntN(pos)];
1394          int ipos = getIntN(pos+2);
1395          // This could lead to to a lot of copying. FIXME.
1396
sbuf.append(seq.getIteratorAtPos(ipos));
1397          pos += 4;
1398        }
1399        continue;
1400      case POSITION_REF_FOLLOWS:
1401      case OBJECT_REF_FOLLOWS:
1402        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1403        if (seen) sbuf.append(sep); else seen = true;
1404        sbuf.append(objects[getIntN(pos)]);
1405        pos += 2;
1406        continue;
1407      case BEGIN_GROUP_LONG:
1408        index = getIntN(pos);
1409        index += index >= 0 ? pos - 1 : data.length;
1410        pos += 2;
1411        index = getIntN(index + 1);
1412        if (inStartTag) sbuf.append('>');
1413        else if (seen) sbuf.append(sep);
1414        sbuf.append('<');
1415        sbuf.append(objects[index]);
1416        seen = false;
1417        inStartTag = true;
1418        continue;
1419      case END_GROUP_LONG:
1420      case END_GROUP_SHORT:
1421        if (datum == END_GROUP_SHORT)
1422          {
1423        index = data[pos++];
1424        index = data[pos - 2 - index] - BEGIN_GROUP_SHORT;
1425          }
1426        else
1427          {
1428        index = getIntN(pos);
1429        pos += 6;
1430          }
1431        if (inStartTag)
1432          sbuf.append("/>");
1433        else
1434          {
1435        sbuf.append("</");
1436        sbuf.append(objects[index]);
1437        sbuf.append('>');
1438          }
1439        inStartTag = false;
1440        seen = true;
1441        continue;
1442      case BEGIN_ATTRIBUTE_LONG:
1443        index = getIntN(pos);
1444        sbuf.append(' ');
1445        sbuf.append(objects[index]);
1446        sbuf.append("=\"");
1447        inAttribute = true;
1448        inStartTag = false;
1449        pos += 4;
1450        continue;
1451      case END_ATTRIBUTE:
1452        sbuf.append('"');
1453        inAttribute = false;
1454        inStartTag = true;
1455        seen = false;
1456        continue;
1457      case INT_FOLLOWS:
1458        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1459        if (seen) sbuf.append(sep); else seen = true;
1460        sbuf.append(getIntN(pos));
1461        pos += 2;
1462        continue;
1463      case FLOAT_FOLLOWS:
1464        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1465        if (seen) sbuf.append(sep); else seen = true;
1466        sbuf.append(Float.intBitsToFloat(getIntN(pos)));
1467        pos += 2;
1468        continue;
1469      case LONG_FOLLOWS:
1470        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1471        if (seen) sbuf.append(sep); else seen = true;
1472        sbuf.append(getLongN(pos));
1473        pos += 4;
1474        continue;
1475      case DOUBLE_FOLLOWS:
1476        if (inStartTag) { sbuf.append('>'); inStartTag = false; }
1477        if (seen) sbuf.append(sep); else seen = true;
1478        sbuf.append(Double.longBitsToDouble(getLongN(pos)));
1479        pos += 4;
1480        continue;
1481      default:
1482        throw new Error JavaDoc("unknown code:"+(int) datum);
1483      }
1484      }
1485  }
1486
1487  public boolean hasNext(int ipos)
1488  {
1489    int index = posToDataIndex(ipos);
1490    if (index == data.length)
1491      return false;
1492    char ch = data[index];
1493    return ch != END_ATTRIBUTE && ch != END_GROUP_SHORT
1494      && ch != END_GROUP_LONG && ch != END_DOCUMENT;
1495  }
1496
1497  public int getNextKind(int ipos)
1498  {
1499    return getNextKindI(posToDataIndex(ipos));
1500  }
1501
1502  public int getNextKindI (int index)
1503  {
1504    if (index == data.length)
1505      return Sequence.EOF_VALUE;
1506    char datum = data[index];
1507    if (datum <= MAX_CHAR_SHORT)
1508      return Sequence.CHAR_VALUE;
1509    if (datum >= OBJECT_REF_SHORT
1510    && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1511      return Sequence.OBJECT_VALUE;
1512    if (datum >= BEGIN_GROUP_SHORT
1513        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1514      return Sequence.GROUP_VALUE;
1515    if ((datum & 0xFF00) == BYTE_PREFIX)
1516      return Sequence.TEXT_BYTE_VALUE;
1517    if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1518    && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1519      return Sequence.INT_S32_VALUE;
1520    switch (datum)
1521      {
1522      case BOOL_FALSE:
1523      case BOOL_TRUE:
1524    return Sequence.BOOLEAN_VALUE;
1525      case INT_FOLLOWS:
1526    return Sequence.INT_S32_VALUE;
1527      case LONG_FOLLOWS:
1528    return Sequence.INT_S64_VALUE;
1529      case FLOAT_FOLLOWS:
1530    return Sequence.FLOAT_VALUE;
1531      case DOUBLE_FOLLOWS:
1532    return Sequence.DOUBLE_VALUE;
1533      case CHAR_FOLLOWS:
1534      case BEGIN_DOCUMENT:
1535    return Sequence.DOCUMENT_VALUE;
1536      case BEGIN_ENTITY:
1537        return getNextKind((index+BEGIN_ENTITY_SIZE) << 1);
1538      case BEGIN_GROUP_LONG:
1539    return Sequence.GROUP_VALUE;
1540      case END_GROUP_SHORT:
1541      case END_GROUP_LONG:
1542      case END_ATTRIBUTE:
1543      case END_DOCUMENT:
1544      case END_ENTITY:
1545    return Sequence.EOF_VALUE;
1546      case BEGIN_ATTRIBUTE_LONG:
1547    return Sequence.ATTRIBUTE_VALUE;
1548      case CDATA_SECTION:
1549    return Sequence.CDATA_VALUE;
1550      case COMMENT:
1551    return Sequence.COMMENT_VALUE;
1552      case PROCESSING_INSTRUCTION:
1553    return Sequence.PROCESSING_INSTRUCTION_VALUE;
1554      case DOCUMENT_URI: // FIXME
1555
case POSITION_REF_FOLLOWS: // FIXME
1556
case POSITION_PAIR_FOLLOWS:
1557      case OBJECT_REF_FOLLOWS:
1558      case JOINER: // FIXME
1559
default:
1560    return Sequence.OBJECT_VALUE;
1561      }
1562
1563  }
1564
1565  public Object JavaDoc getNextTypeObject (int ipos)
1566  {
1567    int index = posToDataIndex(ipos);
1568    char datum;
1569    for (;;)
1570      {
1571        if (index == data.length)
1572          return null;
1573        datum = data[index];
1574        if (datum != BEGIN_ENTITY)
1575          break;
1576        index += BEGIN_ENTITY_SIZE;
1577      }
1578    if (datum >= BEGIN_GROUP_SHORT
1579    && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1580      index = datum-BEGIN_GROUP_SHORT;
1581    else if (datum == BEGIN_GROUP_LONG)
1582      {
1583    int j = getIntN(index+1);
1584    j += j < 0 ? data.length : index;
1585    index = getIntN(j + 1);
1586      }
1587    else if (datum == BEGIN_ATTRIBUTE_LONG)
1588      index = getIntN(index + 1);
1589    else if (datum == PROCESSING_INSTRUCTION)
1590      index = getIntN(index + 1);
1591    else
1592      return null;
1593    return index < 0 ? null : objects[index];
1594  }
1595
1596  public String JavaDoc getNextTypeName(int ipos)
1597  {
1598    Object JavaDoc type = getNextTypeObject(ipos);
1599    return type == null ? null : type.toString();
1600  }
1601
1602  public Object JavaDoc getPosPrevious(int ipos)
1603  {
1604    if ((ipos & 1) != 0 && ipos != -1)
1605      return getPosNext(ipos - 3);
1606    else
1607      return super.getPosPrevious(ipos);
1608  }
1609
1610  private Object JavaDoc copyToList(int startPosition, int endPosition)
1611  {
1612    return new TreeList(this, startPosition, endPosition);
1613  }
1614
1615  /** Return following value (like getPosNext), as an integer. */
1616  public int getPosNextInt (int ipos)
1617  {
1618    int index = posToDataIndex(ipos);
1619    if (index < data.length)
1620      {
1621    char datum = data[index];
1622    if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1623        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1624      return datum-INT_SHORT_ZERO;
1625    if (datum == INT_FOLLOWS)
1626      return getIntN(index+1);
1627      }
1628    return ((Number JavaDoc) getPosNext(ipos)).intValue();
1629  }
1630
1631  public Object JavaDoc getPosNext(int ipos)
1632  {
1633    int index = posToDataIndex(ipos);
1634    if (index == data.length)
1635      return Sequence.eofValue;
1636    char datum = data[index];
1637    if (datum <= MAX_CHAR_SHORT)
1638      return Convert.toObject(datum);
1639    if (datum >= OBJECT_REF_SHORT
1640    && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1641      return objects[datum-OBJECT_REF_SHORT];
1642    if (datum >= BEGIN_GROUP_SHORT
1643        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1644      return copyToList(index, index + data[index+1] + 2);
1645    /*
1646    if ((datum & 0xFF00) == BYTE_PREFIX)
1647      return Sequence.TEXT_BYTE_VALUE;
1648    */

1649    if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1650    && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1651      return Convert.toObject(datum-INT_SHORT_ZERO);
1652    switch (datum)
1653      {
1654      case BEGIN_DOCUMENT:
1655    {
1656      int end_offset = getIntN(index+1);
1657      end_offset += end_offset < 0 ? data.length : index;
1658      end_offset++;
1659      /* Need to be careful about this.
1660      if (index == 0
1661          && (end_offset == data.length
1662          || (end_offset == gapStart && gapEnd == data.length)))
1663        return this;
1664      */

1665      return copyToList(index, end_offset);
1666    }
1667      case BOOL_FALSE:
1668      case BOOL_TRUE:
1669    return Convert.toObject(datum != BOOL_FALSE);
1670      case INT_FOLLOWS:
1671    return Convert.toObject(getIntN(index+1));
1672      case LONG_FOLLOWS:
1673    return Convert.toObject(getLongN(index+1));
1674      case FLOAT_FOLLOWS:
1675    return Convert.toObject(Float.intBitsToFloat(getIntN(index+1)));
1676      case DOUBLE_FOLLOWS:
1677    return Convert.toObject(Double.longBitsToDouble(getLongN(index+1)));
1678      case CHAR_FOLLOWS:
1679    return Convert.toObject(data[index+1]);
1680      case BEGIN_ATTRIBUTE_LONG:
1681    {
1682      int end_offset = getIntN(index+3);
1683      end_offset += end_offset < 0 ? data.length : index;
1684      return copyToList(index, end_offset+1);
1685    }
1686      case BEGIN_GROUP_LONG:
1687    {
1688      int end_offset = getIntN(index+1);
1689      end_offset += end_offset < 0 ? data.length : index;
1690      return copyToList(index, end_offset+7);
1691    }
1692      case END_GROUP_SHORT:
1693      case END_GROUP_LONG:
1694      case END_ATTRIBUTE:
1695      case END_DOCUMENT:
1696    return Sequence.eofValue;
1697      case POSITION_REF_FOLLOWS:
1698      case OBJECT_REF_FOLLOWS:
1699    return objects[getIntN(index+1)];
1700      case JOINER:
1701        return "";
1702      case POSITION_PAIR_FOLLOWS: //FIXME
1703
AbstractSequence seq = (AbstractSequence) objects[getIntN(index+1)];
1704    ipos = getIntN(index+3);
1705    return seq.getIteratorAtPos(ipos);
1706      default:
1707    throw unsupported("getPosNext, code="+Integer.toHexString(datum));
1708      }
1709  }
1710
1711  public void stringValue (int startIndex, int endIndex, StringBuffer JavaDoc sbuf)
1712  {
1713    int index = startIndex;
1714    while (index < endIndex && index >= 0)
1715      index = stringValue(false, index, sbuf);
1716  }
1717
1718  public int stringValue(int index, StringBuffer JavaDoc sbuf)
1719  {
1720    int next = nextNodeIndex(index, -1 >>> 1);
1721    if (next > index)
1722      {
1723        stringValue(index, next, sbuf);
1724    return index;
1725      }
1726    else
1727      return stringValue(false, index, sbuf);
1728  }
1729
1730  public int stringValue(boolean inGroup, int index, StringBuffer JavaDoc sbuf)
1731  {
1732    Object JavaDoc value = null;
1733    int doChildren = 0, j;
1734    if (index >= gapStart)
1735      index += gapEnd - gapStart;
1736    if (index == data.length)
1737      return -1;
1738    char datum = data[index];
1739    index++;
1740    boolean spaceNeeded = false;
1741    if (datum <= MAX_CHAR_SHORT)
1742      {
1743    sbuf.append(datum);
1744    return index;
1745      }
1746    if (datum >= OBJECT_REF_SHORT
1747    && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1748      {
1749        if (spaceNeeded)
1750          sbuf.append(' ');
1751    value = objects[datum-OBJECT_REF_SHORT];
1752        spaceNeeded = false;
1753      }
1754    else if (datum >= BEGIN_GROUP_SHORT
1755         && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1756      {
1757    doChildren = index + 2;
1758    index = data[index] + index + 1;
1759      }
1760    else if ((datum & 0xFF00) == BYTE_PREFIX)
1761      {
1762    sbuf.append(datum & 0xFF);
1763    return index;
1764      }
1765    else if (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1766    && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1767      {
1768    sbuf.append((int) datum - INT_SHORT_ZERO);
1769    return index;
1770      }
1771    else
1772      {
1773    switch (datum)
1774      {
1775      case DOCUMENT_URI:
1776        return index + 2;
1777      case PROCESSING_INSTRUCTION:
1778        index += 2;
1779        /* ... fall through ... */
1780      case CDATA_SECTION:
1781      case COMMENT:
1782        {
1783          int length = getIntN(index);
1784          index += 2;
1785          if (! inGroup || datum == CDATA_SECTION)
1786        sbuf.append(data, index, length);
1787          return index + length;
1788        }
1789      case BOOL_FALSE:
1790      case BOOL_TRUE:
1791            if (spaceNeeded)
1792              sbuf.append(' ');
1793        sbuf.append(datum != BOOL_FALSE);
1794            spaceNeeded = true;
1795        return index;
1796      case INT_FOLLOWS:
1797            if (spaceNeeded)
1798              sbuf.append(' ');
1799        sbuf.append(getIntN(index));
1800            spaceNeeded = true;
1801        return index + 2;
1802      case LONG_FOLLOWS:
1803            if (spaceNeeded)
1804              sbuf.append(' ');
1805        sbuf.append(getLongN(index));
1806            spaceNeeded = true;
1807        return index + 4;
1808      case FLOAT_FOLLOWS:
1809            if (spaceNeeded)
1810              sbuf.append(' ');
1811        sbuf.append(Float.intBitsToFloat(getIntN(index)));
1812            spaceNeeded = true;
1813        return index + 2;
1814      case DOUBLE_FOLLOWS:
1815            if (spaceNeeded)
1816              sbuf.append(' ');
1817        sbuf.append(Double.longBitsToDouble(getLongN(index)));
1818            spaceNeeded = true;
1819        return index + 4;
1820      case CHAR_FOLLOWS:
1821            spaceNeeded = false;
1822        sbuf.append(data[index]);
1823        return index + 1;
1824      case BEGIN_DOCUMENT:
1825      case BEGIN_ENTITY:
1826        doChildren = index + 4;
1827        j = getIntN(index);
1828        index = j + (j < 0 ? data.length + 1 : index);
1829        break;
1830      case BEGIN_GROUP_LONG:
1831            spaceNeeded = false;
1832        doChildren = index + 2;
1833        j = getIntN(index);
1834        j += j < 0 ? data.length : index-1;
1835        index = j + 7;
1836        break;
1837          case JOINER:
1838            spaceNeeded = false;
1839            break;
1840      case END_GROUP_SHORT:
1841      case END_GROUP_LONG:
1842      case END_ATTRIBUTE:
1843      case END_DOCUMENT:
1844      case END_ENTITY:
1845        return -1;
1846      case BEGIN_ATTRIBUTE_LONG:
1847        if (! inGroup)
1848          doChildren = index + 4;
1849        int end = getIntN(index+2);
1850        index = end + (end < 0 ? data.length + 1: index);
1851        break;
1852      case POSITION_PAIR_FOLLOWS:
1853        {
1854          AbstractSequence seq = (AbstractSequence) objects[getIntN(index)];
1855          int ipos = getIntN(index+2);
1856          ((TreeList) seq).stringValue(inGroup, ipos >> 1, sbuf);
1857          index += 4;
1858        }
1859        break;
1860      case POSITION_REF_FOLLOWS:
1861      case OBJECT_REF_FOLLOWS:
1862      default:
1863        throw new Error JavaDoc("unimplemented: "+Integer.toHexString(datum)+" at:"+index);
1864      }
1865      }
1866    if (value != null)
1867      sbuf.append(value);
1868    if (doChildren > 0)
1869      {
1870    do
1871      {
1872        doChildren = stringValue(true, doChildren, sbuf);
1873      }
1874    while (doChildren >= 0);
1875      }
1876    return index;
1877  }
1878
1879  public int createRelativePos(int istart, int offset, boolean isAfter)
1880  {
1881    if (isAfter)
1882      {
1883    if (offset == 0)
1884      {
1885        if ((istart & 1) != 0)
1886          return istart;
1887        if (istart == 0)
1888          return 1;
1889      }
1890    offset--;
1891      }
1892    if (offset < 0)
1893      throw unsupported("backwards createRelativePos");
1894    int pos = posToDataIndex(istart);
1895    while (--offset >= 0)
1896      {
1897    pos = nextDataIndex(pos);
1898    if (pos < 0)
1899      throw new IndexOutOfBoundsException JavaDoc();
1900      }
1901    if (pos >= gapEnd)
1902      pos -= gapEnd - gapStart;
1903    return isAfter ? ((pos + 1) << 1) | 1 : (pos << 1);
1904  }
1905
1906  /** Skip all primitive content nodes. */
1907  public final int nextNodeIndex (int pos, int limit)
1908  {
1909   if ((limit | 0x80000000) == -1) // kludge
1910
limit = data.length;
1911    for (;;)
1912      {
1913    if (pos == gapStart)
1914      pos = gapEnd;
1915    if (pos >= limit)
1916      return pos;
1917    char datum = data[pos];
1918    if (datum <= MAX_CHAR_SHORT
1919        || (datum >= OBJECT_REF_SHORT
1920        && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
1921        || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
1922        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT)
1923        || (datum & 0xFF00) == BYTE_PREFIX)
1924      {
1925        pos++;
1926        continue;
1927      }
1928    if (datum >= BEGIN_GROUP_SHORT
1929        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
1930      return pos;
1931    switch (datum)
1932      {
1933      case DOCUMENT_URI:
1934        pos += 3;
1935        break;
1936          case JOINER:
1937            pos += 1;
1938            break;
1939      case PROCESSING_INSTRUCTION:
1940      case COMMENT:
1941      case BEGIN_DOCUMENT:
1942      case BEGIN_GROUP_LONG:
1943      case BEGIN_ATTRIBUTE_LONG:
1944        return pos;
1945          case BEGIN_ENTITY:
1946            pos += 5;
1947            break;
1948      case END_GROUP_SHORT:
1949      case END_GROUP_LONG:
1950      case END_ATTRIBUTE:
1951      case END_DOCUMENT:
1952        return pos;
1953      case CDATA_SECTION:
1954      default:
1955        pos = nextDataIndex(pos);
1956        continue;
1957      }
1958      }
1959  }
1960
1961  public int nextMatching(int startPos, ElementPredicate predicate,
1962              int endPos, boolean descend)
1963  {
1964    int start = posToDataIndex(startPos);
1965    int limit = posToDataIndex(endPos);
1966    int pos = start;
1967    if (predicate instanceof NodePredicate)
1968      pos = nextNodeIndex(pos, limit);
1969    boolean checkAttribute = false; // true if attribute nodes could match.
1970
boolean checkNode;
1971    boolean checkText;
1972    boolean checkGroup; // true if group nodes could match.
1973
if (predicate instanceof GroupPredicate)
1974      {
1975    checkNode = true;
1976    checkGroup = true;
1977    checkText = false;
1978      }
1979    else if (predicate instanceof AttributePredicate)
1980      {
1981    checkNode = true;
1982    checkGroup = false;
1983    checkText = false;
1984      }
1985    else
1986      {
1987    checkNode = true;
1988    checkGroup = true;
1989    checkText = true;
1990      }
1991    int next;
1992    for (;; pos = next)
1993      {
1994    if (pos == gapStart)
1995      pos = gapEnd;
1996    if (pos >= limit && limit != -1)
1997      return 0;
1998    int j;
1999    char datum = data[pos];
2000    if (datum <= MAX_CHAR_SHORT
2001        || (datum >= OBJECT_REF_SHORT
2002        && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
2003        || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
2004        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT))
2005      {
2006        if (checkText && predicate.isInstancePos(this, pos << 1))
2007          {
2008        if (pos >= gapEnd)
2009          pos -= gapEnd - gapStart;
2010        return pos << 1;
2011          }
2012        next = pos + 1;
2013        continue;
2014      }
2015    switch (datum)
2016      {
2017      case DOCUMENT_URI:
2018        next = pos + 3;
2019        continue;
2020      case BEGIN_DOCUMENT:
2021        next = pos + 5;
2022        if (checkNode) break;
2023        continue;
2024      case BEGIN_ENTITY:
2025        next = pos + 5;
2026        continue;
2027      case POSITION_REF_FOLLOWS:
2028      case OBJECT_REF_FOLLOWS:
2029      case INT_FOLLOWS:
2030        next = pos + 3;
2031        if (checkText) break;
2032        continue;
2033      case CHAR_FOLLOWS:
2034        next = pos + 2;
2035        continue;
2036      case END_GROUP_SHORT:
2037        if (! descend)
2038          return 0;
2039        next = pos + 2;
2040        continue;
2041      case POSITION_PAIR_FOLLOWS:
2042        next = pos + 5;
2043        if (checkText) break;
2044        continue;
2045      case END_GROUP_LONG:
2046        if (! descend)
2047          return 0;
2048        next = pos + 7;
2049        continue;
2050      case END_ATTRIBUTE:
2051      case END_DOCUMENT:
2052        if (! descend)
2053          return 0;
2054            /* ... fall through ...*/
2055          case END_ENTITY:
2056        next = pos + 1;
2057        continue;
2058      case BEGIN_ATTRIBUTE_LONG:
2059        if (checkNode)
2060          {
2061        j = getIntN(pos+3);
2062        next = j + 1 + (j < 0 ? data.length : pos);
2063          }
2064        else
2065          next = pos + 5;
2066        if (checkAttribute) break;
2067        continue;
2068      case BOOL_FALSE:
2069      case BOOL_TRUE:
2070        next = pos + 1;
2071        if (checkText) break;
2072        continue;
2073          case JOINER:
2074        next = pos + 1;
2075            continue;
2076      case LONG_FOLLOWS:
2077      case DOUBLE_FOLLOWS:
2078        next = pos + 5;
2079        if (checkText) break;
2080        continue;
2081      case PROCESSING_INSTRUCTION:
2082        next = pos + 5 + getIntN(pos+3);
2083        if (checkNode) break;
2084        continue;
2085      case COMMENT:
2086        next = pos + 3 + getIntN(pos+1);
2087        if (checkNode) break;
2088        continue;
2089      case CDATA_SECTION:
2090        next = pos + 3 + getIntN(pos+1);
2091        if (checkText) break;
2092        continue;
2093      case BEGIN_GROUP_LONG:
2094        if (descend)
2095          next = pos + 3;
2096        else
2097          {
2098        j = getIntN(pos+1);
2099        next = j + (j < 0 ? data.length : pos) + 7;
2100          }
2101        if (checkGroup) break;
2102        continue;
2103      default:
2104        if (datum >= BEGIN_GROUP_SHORT
2105        && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
2106          {
2107        if (descend)
2108          next = pos + 3;
2109        else
2110          next = pos + data[pos+1] + 2;
2111        if (checkGroup) break;
2112          }
2113        else
2114          throw new Error JavaDoc("unknown code:"+(int) datum);
2115        continue;
2116      }
2117    if (pos > start && predicate.isInstancePos(this, pos << 1))
2118      {
2119        if (pos >= gapEnd)
2120          pos -= gapEnd - gapStart;
2121        return pos << 1;
2122      }
2123      }
2124  }
2125
2126  public int nextPos (int position)
2127  {
2128    int index = posToDataIndex(position);
2129    if (index == data.length)
2130      return 0;
2131    if (index >= gapEnd)
2132      index -= gapEnd - gapStart;
2133    return (index << 1) + 3;
2134  }
2135
2136  public final int nextDataIndex(int pos)
2137  {
2138    if (pos == gapStart)
2139      pos = gapEnd;
2140    if (pos == data.length)
2141      return -1;
2142    int j;
2143    char datum = data[pos++];
2144    if (datum <= MAX_CHAR_SHORT
2145    || (datum >= OBJECT_REF_SHORT
2146        && datum <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
2147    || (datum >= INT_SHORT_ZERO + MIN_INT_SHORT
2148        && datum <= INT_SHORT_ZERO + MAX_INT_SHORT))
2149      return pos;
2150    if (datum >= BEGIN_GROUP_SHORT
2151    && datum <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
2152      return data[pos] + pos + 1;
2153    switch (datum)
2154      {
2155      case BEGIN_DOCUMENT:
2156    j = getIntN(pos);
2157    j += j < 0 ? data.length : pos-1;
2158    return j + 1;
2159        //case BEGIN_ENTITY: // FIXME???
2160
//return j + 5;
2161
case BOOL_FALSE:
2162      case BOOL_TRUE:
2163      case JOINER:
2164    return pos;
2165      case CHAR_FOLLOWS:
2166    return pos + 1;
2167      case POSITION_REF_FOLLOWS:
2168      case OBJECT_REF_FOLLOWS:
2169      case INT_FOLLOWS:
2170    return pos + 2;
2171      case POSITION_PAIR_FOLLOWS:
2172    return pos + 4;
2173      case END_GROUP_SHORT:
2174      case END_GROUP_LONG:
2175      case END_ATTRIBUTE:
2176      case END_DOCUMENT:
2177    return -1;
2178      case BEGIN_GROUP_LONG:
2179    j = getIntN(pos);
2180    j += j < 0 ? data.length : pos-1;
2181    return j + 7;
2182      case BEGIN_ATTRIBUTE_LONG:
2183    j = getIntN(pos+2);
2184    j += j < 0 ? data.length : pos-1;
2185    return j + 1;
2186      case LONG_FOLLOWS:
2187      case DOUBLE_FOLLOWS:
2188    return pos + 4;
2189      case PROCESSING_INSTRUCTION:
2190    pos += 2;
2191    // ... fall through ...
2192
case CDATA_SECTION:
2193      case COMMENT:
2194    return pos + 2 + getIntN(pos);
2195      default:
2196        dump();
2197    throw new Error JavaDoc("unknown code:"+Integer.toHexString((int) datum));
2198      }
2199  }
2200
2201  public Object JavaDoc documentUriOfPos (int pos)
2202  {
2203    int index = posToDataIndex(pos);
2204    if (index == data.length)
2205      return null;
2206    if (data[index] == BEGIN_DOCUMENT)
2207      {
2208        int next = index + 5;
2209        if (next == gapStart)
2210          next = gapEnd;
2211        if (next < data.length && data[next] == DOCUMENT_URI)
2212          return objects[getIntN(next+1)];
2213      }
2214    return null;
2215  }
2216
2217  /** Compare two positions, and indicate their relative order. */
2218  public int compare(int ipos1, int ipos2)
2219  {
2220    // It's difficult to optimize this, because because if (say) isAfter(ipos1)
2221
// then we need nextDataIndex((ipos1>>>1)-1). In that case comparing
2222
// (ipos1>>>1)-1 and (pos2>>>1)-1 tells us nothing, since the former
2223
// could be a BEGIN_GROUP, while the latter might be a node inside
2224
// the group.
2225
int i1 = posToDataIndex(ipos1);
2226    int i2 = posToDataIndex(ipos2);
2227    return i1 < i2 ? -1 : i1 > i2 ? 1 : 0;
2228  }
2229
2230  protected int getIndexDifference(int ipos1, int ipos0)
2231  {
2232    int i0 = posToDataIndex(ipos0);
2233    int i1 = posToDataIndex(ipos1);
2234    boolean negate = false;
2235    if (i0 > i1)
2236      {
2237    negate = true;
2238    int i = i1; i1 = i0; i0 = i;
2239      }
2240    int i = 0;
2241    while (i0 < i1)
2242      {
2243    i0 = nextDataIndex(i0);
2244    i++;
2245      }
2246    return negate ? -i : i;
2247  }
2248
2249  public int hashCode()
2250  {
2251    // Calculating a real hashCode is real pain.
2252
return System.identityHashCode(this);
2253  }
2254
2255  public void consume(Consumer out)
2256  {
2257    consumeIRange(0, data.length, out);
2258  }
2259
2260  public void statistics ()
2261  {
2262    java.io.PrintWriter JavaDoc out = new java.io.PrintWriter JavaDoc(System.out);
2263    statistics(out);
2264    out.flush();
2265  }
2266
2267  public void statistics (java.io.PrintWriter JavaDoc out)
2268  {
2269    out.print("data array length: "); out.println(data.length);
2270    out.print("data array gap: "); out.println(gapEnd-gapStart);
2271    out.print("object array length: "); out.println(objects.length);
2272  }
2273
2274  // /* DEBUGGING
2275
public void dump ()
2276  {
2277    java.io.PrintWriter JavaDoc out = new java.io.PrintWriter JavaDoc(System.out);
2278
2279    dump(out);
2280    out.flush();
2281  }
2282
2283  public void dump (java.io.PrintWriter JavaDoc out)
2284  {
2285    out.println(getClass().getName()+" @"+Integer.toHexString(System.identityHashCode(this))
2286               + " gapStart:"+gapStart+" gapEnd:"+gapEnd+" length:"+data.length);
2287    dump(out, 0, data.length);
2288  }
2289
2290  public void dump (java.io.PrintWriter JavaDoc out, int start, int limit)
2291  {
2292    int toskip = 0;
2293    // Skip follow-on words.
2294
boolean skipFollowingWords = true;
2295    for (int i = start; i < limit; i++)
2296      {
2297    
2298    if (i < gapStart || i >= gapEnd)
2299      {
2300        int j; long l;
2301        int ch = data[i];
2302            out.print(""+i+": 0x"+Integer.toHexString(ch)+'='+((short) ch));
2303        if (--toskip < 0)
2304          {
2305        if (ch <= MAX_CHAR_SHORT)
2306          {
2307            if (ch >= ' ' && ch < 127)
2308              out.print("='"+((char)ch)+"'");
2309            else if (ch=='\n')
2310              out.print("='\\n'");
2311            else
2312              out.print("='\\u"+Integer.toHexString(ch)+"'");
2313          }
2314        else if (ch >= OBJECT_REF_SHORT
2315             && ch <= OBJECT_REF_SHORT+OBJECT_REF_SHORT_INDEX_MAX)
2316          {
2317            ch = ch - OBJECT_REF_SHORT;
2318            Object JavaDoc obj = objects[ch];
2319            out.print("=Object#"+((int)ch)+'='
2320                  +obj+':'+obj.getClass().getName()
2321                  +'@'+Integer.toHexString(System.identityHashCode(obj)));
2322          }
2323        else if (ch >= BEGIN_GROUP_SHORT
2324             && ch <= BEGIN_GROUP_SHORT+BEGIN_GROUP_SHORT_INDEX_MAX)
2325          {
2326            ch = ch - BEGIN_GROUP_SHORT;
2327            j = data[i+1] + i;
2328            out.print("=BEGIN_GROUP_SHORT end:"+j+" index#"+((int)ch)+"=<"+objects[ch]+'>');
2329            toskip = 2;
2330          }
2331        else if (ch >= INT_SHORT_ZERO + MIN_INT_SHORT
2332             && ch <= INT_SHORT_ZERO + MAX_INT_SHORT)
2333          {
2334            out.print("= INT_SHORT:"+(ch-INT_SHORT_ZERO));
2335          }
2336        else
2337          {
2338            switch (ch)
2339              {
2340              case INT_FOLLOWS:
2341            j = getIntN(i+1);
2342            out.print("=INT_FOLLOWS value:"+j);
2343            toskip = 2;
2344            break;
2345              case LONG_FOLLOWS:
2346            l = getLongN(i+1);
2347            out.print("=LONG_FOLLOWS value:"+l);
2348            toskip = 4;
2349            break;
2350              case FLOAT_FOLLOWS:
2351            j = getIntN(i+1);
2352            out.write("=FLOAT_FOLLOWS value:"
2353                  +Float.intBitsToFloat(j));
2354            toskip = 2;
2355            break;
2356              case DOUBLE_FOLLOWS:
2357            l = getLongN(i+1);
2358            out.print("=DOUBLE_FOLLOWS value:"
2359                  +Double.longBitsToDouble(l));
2360            toskip = 4;
2361            break;
2362              case BEGIN_DOCUMENT:
2363            j = getIntN(i+1);
2364            j += j < 0 ? data.length : i;
2365            out.print("=BEGIN_DOCUMENT end:");
2366            out.print(j);
2367                        out.print(" parent:");
2368            j = getIntN(i+3);
2369            out.print(j);
2370            toskip = 4;
2371            break;
2372              case BEGIN_ENTITY:
2373            j = getIntN(i+1);
2374            out.print("=BEGIN_ENTITY base:");
2375            out.print(j);
2376                        out.print(" parent:");
2377            j = getIntN(i+3);
2378            out.print(j);
2379            toskip = 4;
2380            break;
2381              case END_ENTITY:
2382            out.print("=END_ENTITY");
2383            break;
2384              case DOCUMENT_URI:
2385            out.print("=DOCUMENT_URI: ");
2386            j = getIntN(i+1);
2387            out.print(objects[j]);
2388            toskip = 2;
2389            break;
2390              case COMMENT:
2391            out.print("=COMMENT: '");
2392            j = getIntN(i+1);
2393            out.write(data, i+3, j);
2394            out.print('\'');
2395            toskip = 2+j;
2396            break;
2397              case CDATA_SECTION:
2398            out.print("=CDATA: '");
2399            j = getIntN(i+1);
2400            out.write(data, i+3, j);
2401            out.print('\'');
2402            toskip = 2+j;
2403            break;
2404              case PROCESSING_INSTRUCTION:
2405            out.print("=PROCESSING_INSTRUCTION: ");
2406            j = getIntN(i+1);
2407            out.print(objects[j]);
2408            out.print(" '");
2409            j = getIntN(i+3);
2410            out.write(data, i+5, j);
2411            out.print('\'');
2412            toskip = 4+j;
2413            break;
2414              case END_DOCUMENT:
2415            out.print("=END_DOCUMENT");
2416            break;
2417              case BOOL_FALSE: out.print("= false"); break;
2418              case BOOL_TRUE: out.print("= true"); break;
2419              case JOINER: out.print("= joiner"); break;
2420              case CHAR_FOLLOWS:
2421            out.print("=CHAR_FOLLOWS"); toskip = 1; break;
2422              case POSITION_REF_FOLLOWS:
2423              case OBJECT_REF_FOLLOWS:
2424            toskip = 2; break;
2425              case END_GROUP_SHORT:
2426            out.print("=END_GROUP_SHORT begin:");
2427            j = i - data[i+1];
2428            out.print(j);
2429            j = data[j] - BEGIN_GROUP_SHORT;
2430            out.print(" -> #");
2431            out.print(j);
2432            out.print("=<");
2433            out.print(objects[j]);
2434            out.print('>');
2435            toskip = 1; break;
2436              case BEGIN_GROUP_LONG:
2437            j = getIntN(i+1);
2438            j += j < 0 ? data.length : i;
2439            out.print("=BEGIN_GROUP_LONG end:");
2440            out.print(j);
2441            j = getIntN(j + 1);
2442            out.print(" -> #");
2443            out.print(j);
2444                        if (j >= 0 && j+1 < objects.length)
2445                          out.print("=<"+objects[j]+'>');
2446                        else
2447                          out.print("=<out-of-bounds>");
2448            toskip = 2;
2449            break;
2450              case END_GROUP_LONG:
2451            j = getIntN(i+1);
2452            out.print("=END_GROUP_LONG name:"+j
2453                  +"=<"+objects[j]+'>');
2454            j = getIntN(i+3);
2455            j = j < 0 ? i + j : j;
2456            out.print(" begin:"+j);
2457            j = getIntN(i+5);
2458            j = j < 0 ? i + j : j;
2459            out.print(" parent:"+j);
2460            toskip = 6;
2461            break;
2462              case BEGIN_ATTRIBUTE_LONG:
2463            j = getIntN(i+1);
2464            out.print("=BEGIN_ATTRIBUTE name:"+j
2465                  +"="+objects[j]);
2466            j = getIntN(i+3);
2467            j += j < 0 ? data.length : i;
2468            out.print(" end:"+j);
2469            toskip = 4;
2470            break;
2471              case END_ATTRIBUTE: out.print("=END_ATTRIBUTE"); break;
2472              case POSITION_PAIR_FOLLOWS:
2473            out.print("=POSITION_PAIR_FOLLOWS seq:");
2474            {
2475              j = getIntN(i+1); out.print(j);
2476                          out.print('=');
2477              Object JavaDoc seq = objects[j];
2478                          out.print(seq==null?null:seq.getClass().getName());
2479                          out.print('@');
2480              if (seq == null) out.print("null");
2481              else out.print(Integer.toHexString(System.identityHashCode(seq)));
2482              out.print(" ipos:");
2483              out.print(getIntN(i+3));
2484            }
2485            toskip = 4;
2486            /*
2487            AbstractSequence seq = (AbstractSequence) objects[getIntN(i+1)];
2488            ipos = getIntN(i+3);
2489            */

2490            break;
2491              }
2492          }
2493          }
2494        out.println();
2495        if (skipFollowingWords && toskip > 0)
2496          {
2497        i += toskip;
2498        toskip = 0;
2499          }
2500      }
2501      }
2502  }
2503  // DEBUGGING */
2504
}
2505
Popular Tags