001: // Copyright (c) 2001 Per M.A. Bothner and Brainfood Inc.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.lists;
005:
006: /**
007: * A position that can also go down and up in a tree.
008: * A TreePosition is a stack of positions. The "current" position
009: * (i.e. the one you get if you tree the TreePosition as a SeqPosition)
010: * is that in the innermost containing sequence.
011: *
012: * Normally, the "current" element is (the one following) a position in a
013: * sequence. As a special (initial case), we may want to treat the
014: * entire sequence is the "current element". This is represented by depth==-1
015: * and xpos set to the root element (which need not actually be a sequence).
016: */
017:
018: public class TreePosition extends SeqPosition implements Cloneable {
019: /** Used when depth==-1 to indicate the "entire" object.
020: * Usually an AbstractSequence, but need not be. */
021: private Object xpos;
022:
023: /** Stack of pushed values for sequence. */
024: AbstractSequence[] sstack;
025:
026: /** Stack of pushed values for iposition. */
027: int[] istack;
028:
029: /** Depth of the above stacks.
030: * Note that getDepth returns depth+1; this should perhaps match. */
031: int depth;
032:
033: /** Start of stacks - anything below 'start' is ignored.
034: * This is useful for pushing/pop positions without object allocation. */
035: int start;
036:
037: public TreePosition() {
038: depth = -1;
039: }
040:
041: /** Not a position *in* a sequence, but the current element is the entire sequence. */
042: public TreePosition(Object root) {
043: xpos = root;
044: depth = -1;
045: }
046:
047: public TreePosition(AbstractSequence seq, int index) {
048: super (seq, index, false);
049: }
050:
051: public TreePosition(TreePosition pos) {
052: set(pos);
053: }
054:
055: public Object clone() {
056: return new TreePosition(this );
057: }
058:
059: public void set(TreePosition position) {
060: release();
061: int d = position.depth;
062: depth = d;
063: if (d < 0) {
064: xpos = position.xpos;
065: return;
066: }
067: if (sstack == null || sstack.length <= d)
068: sstack = new AbstractSequence[d + 10];
069: if (istack == null || istack.length <= d)
070: istack = new int[d + 10];
071: AbstractSequence seq;
072: int i;
073: for (i = 0; i < depth; i++) {
074: int j = i + position.start;
075: seq = position.sstack[j];
076: sstack[depth - 1] = seq;
077: istack[depth - i] = seq.copyPos(position.istack[j]);
078: }
079: seq = position.sequence;
080: sequence = seq;
081: ipos = seq.copyPos(position.ipos);
082: }
083:
084: /** Number of ancestor sequences, including current sequence. */
085: public int getDepth() {
086: return depth + 1;
087: }
088:
089: /** Get the "root document". */
090: public AbstractSequence getRoot() {
091: return depth == 0 ? sequence : sstack[start];
092: }
093:
094: public Object getPosNext() {
095: return sequence == null ? xpos : sequence.getPosNext(ipos);
096: }
097:
098: public void push(AbstractSequence child, int iposChild) {
099: int d = depth + start;
100: if (d >= 0) {
101: if (d == 0) {
102: istack = new int[8];
103: sstack = new AbstractSequence[8];
104: } else if (d >= istack.length) {
105: int ndepth = 2 * d;
106: int[] itemp = new int[ndepth];
107: Object[] xtemp = new Object[ndepth];
108: AbstractSequence[] stemp = new AbstractSequence[ndepth];
109: System.arraycopy(istack, 0, itemp, 0, depth);
110: System.arraycopy(sstack, 0, stemp, 0, depth);
111: istack = itemp;
112: sstack = stemp;
113: }
114: sstack[d] = sequence;
115: istack[d] = ipos;
116: }
117: depth++;
118: sequence = child;
119: ipos = iposChild;
120: }
121:
122: public void pop() {
123: sequence.releasePos(ipos);
124: popNoRelease();
125: }
126:
127: public void popNoRelease() {
128: if (--depth < 0) {
129: xpos = sequence;
130: sequence = null;
131: } else {
132: sequence = sstack[start + depth];
133: ipos = istack[start + depth];
134: }
135: }
136:
137: public final boolean gotoParent() {
138: return sequence == null ? false : sequence.gotoParent(this );
139: }
140:
141: /** Set position before first child (of the element following position).
142: * @return true if there is a child sequence (which might be empty);
143: * false if current position is end of sequence or following element
144: * is atomic (cannot have children).
145: */
146: public boolean gotoChildrenStart() {
147: if (sequence == null) {
148: if (!(xpos instanceof AbstractSequence))
149: return false;
150: depth = 0;
151: sequence = (AbstractSequence) xpos;
152: setPos(sequence.startPos());
153: } else {
154: if (!sequence.gotoChildrenStart(this ))
155: return false;
156: }
157: return true;
158: }
159:
160: /** Set position before first attribute (of the element following position).
161: * This is used to iterate through the sequence of attributes.
162: */
163: public boolean gotoAttributesStart() {
164: if (sequence == null) {
165: if (xpos instanceof AbstractSequence) {
166: // ??? FIXME
167: }
168: return false;
169: }
170: return sequence.gotoAttributesStart(this );
171: }
172:
173: /*
174: public boolean gotoAttribute(Object name)
175: {
176: return sequence.gotoAttribute(this);
177: }
178: */
179:
180: /** Get the value of an ancestor node.
181: * @param up the number parents to go up.
182: * @return if up is 0, same getNext. Otherwise get parent
183: * applied as specified.
184: */
185: public Object getAncestor(int up) {
186: if (up == 0)
187: return sequence.getPosNext(ipos);
188: int i = depth - up;
189: if (i <= 0)
190: return getRoot();
191: i += start;
192: return sstack[i].getPosNext(istack[i]);
193: }
194:
195: public void release() {
196: while (sequence != null) {
197: sequence.releasePos(ipos);
198: pop();
199: }
200: xpos = null;
201: }
202:
203: /** Copy this position into pos. */
204: /*
205: public void clone (Position pos)
206: {
207: // FIXME!
208: }
209:
210: public Object clone()
211: {
212: TreePosition pos = new TreePosition();
213: clone(pos);
214: return pos;
215: }
216: */
217:
218: public void dump() {
219: System.err.println("TreePosition dump depth:" + depth
220: + " start:" + start);
221: for (int i = 0; i <= depth; i++) {
222: AbstractSequence seq = i == 0 ? sequence
223: : sstack[depth - i];
224: System.err.print("#" + i + " seq:" + seq);
225: System.err.println(" ipos:"
226: + (i == 0 ? ipos : istack[depth - i]));
227: }
228: }
229: }
230: // This is for people using the Emacs editor:
231: // Local Variables:
232: // c-file-style: "gnu"
233: // tab-width: 8
234: // indent-tabs-mode: t
235: // End:
|