01: // Copyright (c) 2003 Per M.A. Bothner.
02: // This is free software; for terms and warranty disclaimer see ./COPYING.
03:
04: package gnu.kawa.xml;
05:
06: import gnu.lists.*;
07: import gnu.xml.*;
08:
09: /** Manages a sequence of node references in document order without duplicates.
10: * All elements are POSITION_PAIR_FOLLOWS elements, which makes operations
11: * simple and efficient. The most recently added element is just before
12: * the gap. Optimized for the data being in order, or at least having good
13: * locality (a node being "near" the previously-entered node). */
14:
15: public class SortedNodes extends Nodes {
16: int nesting = 0;
17:
18: int compareIndex(int index, AbstractSequence seq2, int ipos2) {
19: int datum = data[index];
20: if (datum != POSITION_PAIR_FOLLOWS)
21: throw new RuntimeException(
22: "invalid kind of value to compare");
23: AbstractSequence seq = (AbstractSequence) objects[getIntN(index + 1)];
24: return AbstractSequence.compare(seq, getIntN(index + 3), seq2,
25: 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: int lo = 0;
37: int hi = count;
38: // We use binary search, though the arraycopy operations in writePosition
39: // limit the value - a sequence of writePosition calls is still quadratic
40: // in the worst case (but linear if locality is good).
41: while (lo < hi) {
42: int mid = (lo + hi) >> 1;
43: int cmp = compareIndex(start + POS_SIZE * mid, seq, ipos);
44: if (cmp == 0)
45: return -1;
46: if (cmp > 0)
47: hi = mid;
48: else
49: lo = mid + 1;
50: }
51: return start + POS_SIZE * lo;
52: }
53:
54: public void writePosition(AbstractSequence seq, int ipos) {
55: if (count > 0) {
56: int lastIndex = gapStart - POS_SIZE;
57: int cmp = compareIndex(lastIndex, seq, ipos);
58: if (cmp < 0) {
59: // The new node is after all nodes up to gapStart.
60: int i = gapEnd;
61: int end = data.length;
62: // Note that if the incoming nodes are already sorted (a common
63: // case in path expressions), then find will immediately return i.
64: i = find(i, (end - i) / POS_SIZE, seq, ipos);
65: if (i < 0)
66: return;
67: int delta = i - gapEnd;
68: if (delta > 0) {
69: System.arraycopy(data, gapEnd, data, gapStart,
70: delta);
71: gapEnd = i;
72: gapStart += delta;
73: }
74: } else if (cmp == 0)
75: return;
76: else {
77: int i = find(0, lastIndex / POS_SIZE, seq, ipos);
78: if (i < 0)
79: return;
80: int delta = gapStart - i;
81: if (delta > 0) {
82: System.arraycopy(data, i, data, gapEnd - delta,
83: delta);
84: gapStart = i;
85: gapEnd -= delta;
86: }
87: }
88: }
89: super.writePosition(seq, ipos);
90: }
91:
92: }
|