KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > kawa > xml > SortedNodes


1 // Copyright (c) 2003 Per M.A. Bothner.
2 // This is free software; for terms and warranty disclaimer see ./COPYING.
3
4 package gnu.kawa.xml;
5 import gnu.lists.*;
6 import gnu.xml.*;
7
8 /** Manages a sequence of node references in document order without duplicates.
9  * All elements are POSITION_PAIR_FOLLOWS elements, which makes operations
10  * simple and efficient. The most recently added element is just before
11  * the gap. Optimized for the data being in order, or at least having good
12  * locality (a node being "near" the previously-entered node). */
13
14 public class SortedNodes extends Nodes
15 {
16   int nesting = 0;
17
18   int compareIndex(int index, AbstractSequence seq2, int ipos2)
19   {
20     int datum = data[index];
21     if (datum != POSITION_PAIR_FOLLOWS)
22       throw new RuntimeException JavaDoc("invalid kind of value to compare");
23     AbstractSequence seq = (AbstractSequence) objects[getIntN(index+1)];
24     return AbstractSequence.compare(seq, getIntN(index+3),
25                     seq2, ipos2);
26   }
27
28   /** Find index where to put position (seq, ipos).
29    * Require {@code index>=start && index<end},
30    * where {@code end==start+POS_SIZE*count}.
31    * Require all position before index are "less than" (seq, ipos),
32    * and all positions after are "greater than" (seq, ipos).
33    * If there is no such index (because it is "same as"), return -1.
34    */
35   int find (int start, int count, AbstractSequence seq, int ipos)
36   {
37     int lo = 0;
38     int hi = count;
39     // We use binary search, though the arraycopy operations in writePosition
40 // limit the value - a sequence of writePosition calls is still quadratic
41 // in the worst case (but linear if locality is good).
42 while (lo < hi)
43       {
44     int mid = (lo + hi) >> 1;
45     int cmp = compareIndex(start + POS_SIZE * mid, seq, ipos);
46     if (cmp == 0)
47       return -1;
48     if (cmp > 0)
49       hi = mid;
50     else
51       lo = mid + 1;
52       }
53     return start + POS_SIZE * lo;
54   }
55
56   public void writePosition(AbstractSequence seq, int ipos)
57   {
58     if (count > 0)
59       {
60     int lastIndex = gapStart - POS_SIZE;
61     int cmp = compareIndex(lastIndex, seq, ipos);
62     if (cmp < 0)
63       {
64         // The new node is after all nodes up to gapStart.
65 int i = gapEnd;
66         int end = data.length;
67         // Note that if the incoming nodes are already sorted (a common
68 // case in path expressions), then find will immediately return i.
69 i = find (i, (end - i) / POS_SIZE, seq, ipos);
70         if (i < 0)
71           return;
72         int delta = i - gapEnd;
73         if (delta > 0)
74           {
75         System.arraycopy(data, gapEnd, data, gapStart, delta);
76         gapEnd = i;
77         gapStart += delta;
78           }
79       }
80     else if (cmp == 0)
81       return;
82     else
83       {
84         int i = find (0, lastIndex / POS_SIZE, seq, ipos);
85         if (i < 0)
86           return;
87         int delta = gapStart - i;
88         if (delta > 0)
89           {
90         System.arraycopy(data, i, data, gapEnd - delta, delta);
91         gapStart = i;
92         gapEnd -= delta;
93           }
94       }
95       }
96     super.writePosition(seq, ipos);
97   }
98
99 }
100
Popular Tags