001/* ElementIterator.java --
002   Copyright (C) 2005 Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038package javax.swing.text;
039
040import java.util.Stack;
041
042/**
043 * This class can be used to iterate over the {@link Element} tree of
044 * a {@link Document} or an {@link Element}.  This iterator performs
045 * an "in-order" traversal -- first it visits a node, then each of the
046 * node's children in order.  No locking is performed during the
047 * iteration; that is up to the caller.
048 */
049public class ElementIterator implements Cloneable
050{
051  /**
052   * Uses to track the iteration on the stack.
053   */
054  private class ElementRef
055  {
056    /**
057     * The element.
058     */
059    Element element;
060
061    /**
062     * The child index. -1 means the element itself. >= 0 values mean the
063     * n-th child of the element.
064     */
065    int index;
066
067    /**
068     * Creates a new ElementRef.
069     *
070     * @param el the element
071     */
072    ElementRef(Element el)
073    {
074      element = el;
075      index = -1;
076    }
077  }
078
079  // The root element.
080  private Element root;
081
082  /**
083   * Holds ElementRefs.
084   */
085  private Stack stack;
086
087  /**
088   * Create a new ElementIterator to iterate over the given document.
089   * @param document the Document over which we iterate
090   */
091  public ElementIterator(Document document)
092  {
093    root = document.getDefaultRootElement();
094  }
095
096  /**
097   * Create a new ElementIterator to iterate over the given document.
098   * @param root the Document over which we iterate
099   */
100  public ElementIterator(Element root)
101  {
102    this.root = root;
103  }
104
105  /**
106   * Returns a new ElementIterator which is a clone of this
107   * ElementIterator.
108   */
109  public Object clone()
110  {
111    try
112      {
113        return super.clone();
114      }
115    catch (CloneNotSupportedException _)
116      {
117        // Can't happen.
118        return null;
119      }
120  }
121
122  /**
123   * Returns the current element.
124   */
125  public Element current()
126  {
127    Element current;
128    if (stack == null)
129      current = first();
130    else
131      {
132        current = null;
133        if (! stack.isEmpty())
134          {
135            ElementRef ref = (ElementRef) stack.peek();
136            Element el = ref.element;
137            int index = ref.index;
138            if (index == -1)
139              current = el;
140            else
141              current = el.getElement(index);
142          }
143      }
144    return current;
145  }
146
147  /**
148   * Returns the depth to which we have descended in the tree.
149   */
150  public int depth()
151  {
152    int depth = 0;
153    if (stack != null)
154      depth = stack.size();
155    return depth;
156  }
157
158  /**
159   * Returns the first element in the tree.
160   */
161  public Element first()
162  {
163    Element first = null;
164    if (root != null)
165      {
166        stack = new Stack();
167        if (root.getElementCount() > 0)
168          stack.push(new ElementRef(root));
169        first = root;
170      }
171    return first;
172  }
173
174  /**
175   * Advance the iterator and return the next element of the tree,
176   * performing an "in-order" traversal.
177   */
178  public Element next()
179  {
180    Element next;
181    if (stack == null)
182      next = first();
183    else
184      {
185        next = null;
186        if (! stack.isEmpty())
187          {
188            ElementRef ref = (ElementRef) stack.peek();
189            Element el = ref.element;
190            int index = ref.index;
191            if (el.getElementCount() > index + 1)
192              {
193                Element child = el.getElement(index + 1);
194                if (child.isLeaf())
195                  ref.index++;
196                else
197                  stack.push(new ElementRef(child));
198                next = child;
199                next = child;
200              }
201            else
202              {
203                stack.pop();
204                if (! stack.isEmpty())
205                  {
206                    ElementRef top = (ElementRef) stack.peek();
207                    top.index++;
208                    next = next();
209                  }
210              }
211          }
212        // else return null.
213      }
214    return next;
215  }
216
217  /**
218   * Returns the previous item.  Does not modify the iterator state.
219   */
220  public Element previous()
221  {
222    Element previous = null;
223    int stackSize;
224    if (stack != null && (stackSize = stack.size()) > 0)
225      {
226        ElementRef ref = (ElementRef) stack.peek();
227        Element el = ref.element;
228        int index = ref.index;
229        if (index > 0)
230          {
231            previous = deepestLeaf(el.getElement(--index));
232          }
233        else if (index == 0)
234          {
235            previous = el;
236          }
237        else if (index == -1)
238          {
239            ElementRef top = (ElementRef) stack.pop();
240            ElementRef item = (ElementRef) stack.peek();
241            stack.push(top);
242            index = item.index;
243            el = item.element;
244            previous = index == -1 ? el : deepestLeaf(el.getElement(index));
245          }
246      }
247    return previous;
248  }
249
250  /**
251   * Determines and returns the deepest leaf of the element <code>el</code>.
252   *
253   * @param el the base element
254   *
255   * @returnthe deepest leaf of the element <code>el</code>
256   */
257  private Element deepestLeaf(Element el)
258  {
259    Element leaf;
260    if (el.isLeaf())
261      leaf = el;
262    else
263      {
264        int count = el.getElementCount();
265        if (count == 0)
266          leaf = el;
267        else
268          leaf = deepestLeaf(el.getElement(count - 1));
269      }
270    return leaf;
271  }
272}