001    /* ElementIterator.java --
002       Copyright (C) 2005 Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package javax.swing.text;
039    
040    import 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     */
049    public 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    }