TreePosition


1   // Copyright (c) 2001  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   
6   /**
7    * A position that can also go down and up in a tree. 
8    * A TreePosition is a stack of positions.  The "current" position
9    * (i.e. the one you get if you tree the TreePosition as a SeqPosition)
10   * is that in the innermost containing sequence.
11   *
12   * Normally, the "current" element is (the one following) a position in a
13   * sequence.  As a special (initial case), we may want to treat the
14   * entire sequence is the "current element".  This is represented by depth==-1
15   * and xpos set to the root element (which need not actually be a sequence).
16   */
17  
18  public class TreePosition extends SeqPosition implements Cloneable  
19  {
20    /** Used when depth==-1 to indicate the "entire" object.
21     * Usually an AbstractSequence, but need not be. */
22    private Object   xpos;
23  
24    /** Stack of pushed values for sequence. */
25    AbstractSequence[] sstack;
26  
27    /** Stack of pushed values for iposition. */
28    int[] istack; 
29  
30    /** Depth of the above stacks.
31     * Note that getDepth returns depth+1; this should perhaps match. */
32    int depth;
33  
34    /** Start of stacks - anything below 'start' is ignored.
35     * This is useful for pushing/pop positions without object allocation. */
36    int start;
37  
38    public TreePosition()
39    {
40      depth = -1;
41    }
42  
43    /** Not a position *in* a sequence, but the current element is the entire sequence. */
44    public TreePosition(Object   root)
45    {
46      xpos = root;
47      depth = -1;
48    }
49  
50    public TreePosition(AbstractSequence seq, int index)
51    {
52      super(seq, index, false);
53    }
54  
55    public TreePosition (TreePosition pos)
56    {
57      set(pos);
58    }
59  
60    public Object   clone ()
61    {
62      return new TreePosition(this);
63    }
64  
65    public void set (TreePosition position)
66    {
67      release();
68      int d = position.depth;
69      depth = d;
70      if (d < 0)
71        {
72      xpos = position.xpos;
73      return;
74        }
75      if (sstack == null || sstack.length <= d)
76        sstack = new AbstractSequence[d + 10];
77      if (istack == null || istack.length <= d)
78        istack = new int[d + 10];
79      AbstractSequence seq;
80      int i;
81      for (i = 0;  i < depth;  i++)
82        {
83      int j = i + position.start;
84      seq = position.sstack[j];
85      sstack[depth-1] = seq;
86      istack[depth - i] = seq.copyPos(position.istack[j]);
87        }
88      seq = position.sequence;
89      sequence = seq;
90      ipos = seq.copyPos(position.ipos);
91    }
92  
93    /** Number of ancestor sequences, including current sequence. */
94    public int getDepth()
95    {
96      return depth + 1;
97    }
98  
99    /** Get the "root document". */
100   public AbstractSequence getRoot()
101   {
102     return depth == 0 ? sequence : sstack[start];
103   }
104 
105   public Object   getPosNext()
106   {
107     return sequence == null ? xpos : sequence.getPosNext(ipos);
108   }
109 
110   public void push(AbstractSequence child, int iposChild)
111   {
112     int d = depth + start;
113     if (d >= 0)
114       {
115     if (d == 0)
116       {
117         istack = new int[8];
118         sstack = new AbstractSequence[8];
119       }
120     else if (d >= istack.length)
121       {
122         int ndepth = 2 * d;
123         int[] itemp = new int[ndepth];
124         Object  [] xtemp = new Object  [ndepth];
125         AbstractSequence[] stemp = new AbstractSequence[ndepth];
126         System.arraycopy(istack, 0, itemp, 0, depth);
127         System.arraycopy(sstack, 0, stemp, 0, depth);
128         istack = itemp;
129         sstack = stemp;
130       }
131     sstack[d] = sequence;
132     istack[d] = ipos;
133       }
134     depth++;
135     sequence = child;
136     ipos = iposChild;
137   }
138 
139   public void pop()
140   {
141     sequence.releasePos(ipos);
142     popNoRelease();
143   }
144 
145   public void popNoRelease()
146   {
147     if (--depth < 0)
148       {
149     xpos = sequence;
150     sequence = null;
151       }
152     else
153       {
154     sequence = sstack[start+depth];
155     ipos = istack[start+depth];
156       }
157   }
158 
159   public final boolean gotoParent()
160   {
161     return sequence == null ? false : sequence.gotoParent(this);
162   }
163 
164   /** Set position before first child (of the element following position).
165    * @return true if there is a child sequence (which might be empty);
166    *   false if current position is end of sequence or following element
167    *   is atomic (cannot have children).
168    */
169   public boolean gotoChildrenStart()
170   {
171     if (sequence == null)
172       {
173     if (! (xpos instanceof AbstractSequence))
174       return false;
175     depth = 0;
176     sequence = (AbstractSequence) xpos;
177     setPos(sequence.startPos());
178       }
179     else
180       {
181     if (! sequence.gotoChildrenStart(this))
182       return false;
183       }
184     return true;
185   }
186 
187   /** Set position before first attribute (of the element following position).
188    * This is used to iterate through the sequence of attributes.
189    */
190   public boolean gotoAttributesStart()
191   {
192     if (sequence == null)
193       {
194     if (xpos instanceof AbstractSequence)
195       {
196         // ??? FIXME
197       }
198     return false;
199       }
200     return sequence.gotoAttributesStart(this);
201   }
202 
203   /*
204   public boolean gotoAttribute(Object name)
205   {
206     return sequence.gotoAttribute(this);
207   }
208   */
209 
210   /** Get the value of an ancestor node.
211    * @param up the number parents to go up.
212    * @return if up is 0, same getNext.   Otherwise get parent
213    * applied as specified.
214    */
215   public Object   getAncestor(int up)
216   {
217     if (up == 0)
218       return sequence.getPosNext(ipos);
219     int i = depth - up;
220     if (i <= 0)
221       return getRoot();
222     i += start;
223     return sstack[i].getPosNext(istack[i]);
224   }
225 
226   public void release()
227   {
228     while (sequence != null)
229       {
230         sequence.releasePos(ipos);
231         pop();
232       }
233     xpos = null;
234   }
235 
236   /** Copy this position into pos. */
237   /*
238   public void clone (Position pos)
239   {
240     // FIXME!
241   }
242 
243   public Object clone()
244   {
245     TreePosition pos = new TreePosition();
246     clone(pos);
247     return pos;
248   }
249   */
250 
251   public void dump()
252   {
253     System.err.println("TreePosition dump depth:"+depth+" start:"+start);
254     for (int i = 0;  i <= depth;  i++)
255       {
256     AbstractSequence seq = i==0 ? sequence : sstack[depth-i];
257     System.err.print("#"+i+" seq:"+seq);
258     System.err.println(" ipos:" + (i == 0 ? ipos : istack[depth-i]));
259       }
260   }
261 }
262 // This is for people using the Emacs editor:
263 // Local Variables:
264 // c-file-style: "gnu"
265 // tab-width: 8
266 // indent-tabs-mode: t
267 // End:
268
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags