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: /** Stack of pushed values for sequence. */
020: AbstractSequence[] sstack;
021:
022: /** Stack of pushed values for iposition. */
023: int[] istack;
024:
025: /** Stack of pushed values for xposition. */
026: Object[] xstack;
027:
028: /** Depth of the above stacks.
029: * Note that getDepth returns depth+1; this should perhaps match. */
030: int depth;
031:
032: public TreePosition() {
033: depth = -1;
034: }
035:
036: /** Not a position *in* a sequence, but the current element is the entire sequence. */
037: public TreePosition(Object root) {
038: xpos = root;
039: depth = -1;
040: }
041:
042: public TreePosition(AbstractSequence seq, int index) {
043: seq.makePosition(index, false, this , 0);
044: }
045:
046: public TreePosition(TreePosition pos) {
047: set(pos);
048: }
049:
050: public Object clone() {
051: return new TreePosition(this );
052: }
053:
054: public void set(TreePosition position) {
055: clear();
056: int d = position.depth;
057: depth = d;
058: if (d < 0) {
059: xpos = position.xpos;
060: return;
061: }
062: if (sstack == null || sstack.length <= d)
063: sstack = new AbstractSequence[d + 10];
064: if (istack == null || istack.length <= d)
065: istack = new int[d + 10];
066: if (xstack == null || xstack.length <= d)
067: xstack = new Object[d + 10];
068: AbstractSequence seq;
069: int i;
070: for (i = 0; i < depth; i++) {
071: seq = position.sstack[i];
072: seq.copyPosition(position.istack[i], position.xstack[i],
073: this , depth - i);
074: }
075: seq = position.sequence;
076: seq.copyPosition(position.ipos, position.xpos, this , 0);
077: }
078:
079: /** Number of ancestor sequences, including current sequence. */
080: public int getDepth() {
081: return depth + 1;
082: }
083:
084: /** Get the "root document". */
085: public AbstractSequence getRoot() {
086: return depth == 0 ? sequence : sstack[0];
087: }
088:
089: public Object getNext() {
090: return sequence == null ? xpos : sequence.getNext(ipos, xpos);
091: }
092:
093: public void push(AbstractSequence child, int iposChild,
094: Object xposChild) {
095: if (depth >= 0) {
096: if (depth == 0) {
097: istack = new int[8];
098: xstack = new Object[8];
099: sstack = new AbstractSequence[8];
100: } else if (depth >= istack.length) {
101: int ndepth = 2 * depth;
102: int[] itemp = new int[ndepth];
103: Object[] xtemp = new Object[ndepth];
104: AbstractSequence[] stemp = new AbstractSequence[ndepth];
105: System.arraycopy(istack, 0, itemp, 0, depth);
106: System.arraycopy(xstack, 0, xtemp, 0, depth);
107: System.arraycopy(sstack, 0, stemp, 0, depth);
108: istack = itemp;
109: xstack = xtemp;
110: sstack = stemp;
111: }
112: sstack[depth] = sequence;
113: istack[depth] = ipos;
114: xstack[depth] = xpos;
115: }
116: depth++;
117: sequence = child;
118: ipos = iposChild;
119: xpos = xposChild;
120: }
121:
122: public void pop() {
123: sequence.releasePosition(ipos, xpos);
124: popNoRelease();
125: }
126:
127: public void popNoRelease() {
128: if (--depth < 0) {
129: xpos = sequence;
130: sequence = null;
131: } else {
132: sequence = sstack[depth];
133: ipos = istack[depth];
134: xpos = xstack[depth];
135: }
136: }
137:
138: public final boolean gotoParent() {
139: return sequence == null ? false : sequence.gotoParent(this );
140: }
141:
142: /** Set position before first child (of the element following position).
143: * @return true if there is a child sequence (which might be empty);
144: * false if current position is end of sequence or following element
145: * is atomic (cannot have children).
146: */
147: public boolean gotoChildrenStart() {
148: if (sequence == null) {
149: if (!(xpos instanceof AbstractSequence))
150: return false;
151: depth = 0;
152: sequence = (AbstractSequence) xpos;
153: sequence.makeStartPosition(this , 0);
154: } else {
155: if (!sequence.gotoChildrenStart(this ))
156: return false;
157: }
158: return true;
159: }
160:
161: /** Set position before first attribute (of the element following position).
162: * This is used to iterate through the sequence of attributes.
163: */
164: public boolean gotoAttributesStart() {
165: if (sequence == null) {
166: if (xpos instanceof AbstractSequence) {
167: // ??? FIXME
168: }
169: return false;
170: }
171: return sequence.gotoAttributesStart(this );
172: }
173:
174: /*
175: public boolean gotoAttribute(Object name)
176: {
177: return sequence.gotoAttribute(this);
178: }
179: */
180:
181: /** Get the value of an ancestor node.
182: * @param up the number parents to go up.
183: * @return if up is 0, same getNext. Otherwise get parent
184: * applied as specified.
185: */
186: public Object getAncestor(int up) {
187: if (up == 0)
188: return sequence.getNext(ipos, xpos);
189: int i = depth - up;
190: if (i <= 0)
191: return getRoot();
192: return sstack[i].getNext(istack[i], xstack[i]);
193: }
194:
195: public void finalize() {
196: clear();
197: }
198:
199: public void clear() {
200: while (sequence != null) {
201: sequence.releasePosition(ipos, xpos);
202: pop();
203: }
204: xpos = null;
205: }
206:
207: /** Copy this position into pos. */
208: /*
209: public void clone (Position pos)
210: {
211: // FIXME!
212: }
213:
214: public Object clone()
215: {
216: TreePosition pos = new TreePosition();
217: clone(pos);
218: return pos;
219: }
220: */
221:
222: /** Implements PositionContainer. */
223: public int getPositionInt(int positionNumber) {
224: return positionNumber == 0 ? ipos : istack[depth
225: - positionNumber];
226: }
227:
228: /** Implements PositionContainer. */
229: public Object getPositionPtr(int positionNumber) {
230: return positionNumber == 0 ? xpos : xstack[depth
231: - positionNumber];
232: }
233:
234: /** Implements PositionContainer. */
235: public void setPosition(int positionNumber, int ipos, Object xpos) {
236: if (positionNumber == 0) {
237: this .ipos = ipos;
238: this .xpos = xpos;
239: } else {
240: istack[depth - positionNumber] = ipos;
241: xstack[depth - positionNumber] = xpos;
242: }
243: }
244:
245: /** Implements PositionContainer. */
246: public void setSequence(int positionNumber, AbstractSequence seq) {
247: if (positionNumber == 0)
248: this .sequence = seq;
249: else
250: sstack[depth - positionNumber] = seq;
251: }
252:
253: /** Implements PositionContainer. */
254: public int countPositions() {
255: return depth + 1;
256: }
257:
258: public void dump() {
259: System.err.println("TreePosition dump depth:" + depth);
260: if (depth < 0) {
261: System.err.println("#- xpos:" + getPositionPtr(0));
262: }
263: for (int i = 0; i <= depth; i++) {
264: AbstractSequence seq = i == 0 ? sequence
265: : sstack[depth - i];
266: System.err.print("#" + i + " seq:" + seq);
267: System.err.println(" ipos:" + getPositionInt(i) + " xpos:"
268: + getPositionPtr(i));
269: }
270: }
271: }
272: // This is for people using the Emacs editor:
273: // Local Variables:
274: // c-file-style: "gnu"
275: // tab-width: 8
276: // indent-tabs-mode: t
277: // End:
|