1/*
2 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26package javax.swing.text;
27
28import java.util.Stack;
29import java.util.Enumeration;
30
31/**
32 * <p>
33 * ElementIterator, as the name suggests, iterates over the Element
34 * tree.  The constructor can be invoked with either Document or an Element
35 * as an argument.  If the constructor is invoked with a Document as an
36 * argument then the root of the iteration is the return value of
37 * document.getDefaultRootElement().
38 *
39 * The iteration happens in a depth-first manner.  In terms of how
40 * boundary conditions are handled:
41 * a) if next() is called before first() or current(), the
42 *    root will be returned.
43 * b) next() returns null to indicate the end of the list.
44 * c) previous() returns null when the current element is the root
45 *    or next() has returned null.
46 *
47 * The ElementIterator does no locking of the Element tree. This means
48 * that it does not track any changes.  It is the responsibility of the
49 * user of this class, to ensure that no changes happen during element
50 * iteration.
51 *
52 * Simple usage example:
53 *
54 *    public void iterate() {
55 *        ElementIterator it = new ElementIterator(root);
56 *        Element elem;
57 *        while (true) {
58 *           if ((elem = next()) != null) {
59 *               // process element
60 *               System.out.println("elem: " + elem.getName());
61 *           } else {
62 *               break;
63 *           }
64 *        }
65 *    }
66 *
67 * @author Sunita Mani
68 *
69 */
70
71public class ElementIterator implements Cloneable {
72
73
74    private Element root;
75    private Stack<StackItem> elementStack = null;
76
77    /**
78     * The StackItem class stores the element
79     * as well as a child index.  If the
80     * index is -1, then the element represented
81     * on the stack is the element itself.
82     * Otherwise, the index functions as an index
83     * into the vector of children of the element.
84     * In this case, the item on the stack
85     * represents the "index"th child of the element
86     *
87     */
88    private class StackItem implements Cloneable {
89        Element item;
90        int childIndex;
91
92        private StackItem(Element elem) {
93            /**
94             * -1 index implies a self reference,
95             * as opposed to an index into its
96             * list of children.
97             */
98            this.item = elem;
99            this.childIndex = -1;
100        }
101
102        private void incrementIndex() {
103            childIndex++;
104        }
105
106        private Element getElement() {
107            return item;
108        }
109
110        private int getIndex() {
111            return childIndex;
112        }
113
114        protected Object clone() throws java.lang.CloneNotSupportedException {
115            return super.clone();
116        }
117    }
118
119    /**
120     * Creates a new ElementIterator. The
121     * root element is taken to get the
122     * default root element of the document.
123     *
124     * @param document a Document.
125     */
126    public ElementIterator(Document document) {
127        root = document.getDefaultRootElement();
128    }
129
130
131    /**
132     * Creates a new ElementIterator.
133     *
134     * @param root the root Element.
135     */
136    public ElementIterator(Element root) {
137        this.root = root;
138    }
139
140
141    /**
142     * Clones the ElementIterator.
143     *
144     * @return a cloned ElementIterator Object.
145     */
146    public synchronized Object clone() {
147
148        try {
149            ElementIterator it = new ElementIterator(root);
150            if (elementStack != null) {
151                it.elementStack = new Stack<StackItem>();
152                for (int i = 0; i < elementStack.size(); i++) {
153                    StackItem item = elementStack.elementAt(i);
154                    StackItem clonee = (StackItem)item.clone();
155                    it.elementStack.push(clonee);
156                }
157            }
158            return it;
159        } catch (CloneNotSupportedException e) {
160            throw new InternalError(e);
161        }
162    }
163
164
165    /**
166     * Fetches the first element.
167     *
168     * @return an Element.
169     */
170    public Element first() {
171        // just in case...
172        if (root == null) {
173            return null;
174        }
175
176        elementStack = new Stack<StackItem>();
177        if (root.getElementCount() != 0) {
178            elementStack.push(new StackItem(root));
179        }
180        return root;
181    }
182
183    /**
184     * Fetches the current depth of element tree.
185     *
186     * @return the depth.
187     */
188    public int depth() {
189        if (elementStack == null) {
190            return 0;
191        }
192        return elementStack.size();
193    }
194
195
196    /**
197     * Fetches the current Element.
198     *
199     * @return element on top of the stack or
200     *          <code>null</code> if the root element is <code>null</code>
201     */
202    public Element current() {
203
204        if (elementStack == null) {
205            return first();
206        }
207
208        /*
209          get a handle to the element on top of the stack.
210        */
211        if (! elementStack.empty()) {
212            StackItem item = elementStack.peek();
213            Element elem = item.getElement();
214            int index = item.getIndex();
215            // self reference
216            if (index == -1) {
217                return elem;
218            }
219            // return the child at location "index".
220            return elem.getElement(index);
221        }
222        return null;
223    }
224
225
226    /**
227     * Fetches the next Element. The strategy
228     * used to locate the next element is
229     * a depth-first search.
230     *
231     * @return the next element or <code>null</code>
232     *          at the end of the list.
233     */
234    public Element next() {
235
236        /* if current() has not been invoked
237           and next is invoked, the very first
238           element will be returned. */
239        if (elementStack == null) {
240            return first();
241        }
242
243        // no more elements
244        if (elementStack.isEmpty()) {
245            return null;
246        }
247
248        // get a handle to the element on top of the stack
249
250        StackItem item = elementStack.peek();
251        Element elem = item.getElement();
252        int index = item.getIndex();
253
254        if (index+1 < elem.getElementCount()) {
255            Element child = elem.getElement(index+1);
256            if (child.isLeaf()) {
257                /* In this case we merely want to increment
258                   the child index of the item on top of the
259                   stack.*/
260                item.incrementIndex();
261            } else {
262                /* In this case we need to push the child(branch)
263                   on the stack so that we can iterate over its
264                   children. */
265                elementStack.push(new StackItem(child));
266            }
267            return child;
268        } else {
269            /* No more children for the item on top of the
270               stack therefore pop the stack. */
271            elementStack.pop();
272            if (!elementStack.isEmpty()) {
273                /* Increment the child index for the item that
274                   is now on top of the stack. */
275                StackItem top = elementStack.peek();
276                top.incrementIndex();
277                /* We now want to return its next child, therefore
278                   call next() recursively. */
279                return next();
280            }
281        }
282        return null;
283    }
284
285
286    /**
287     * Fetches the previous Element. If however the current
288     * element is the last element, or the current element
289     * is null, then null is returned.
290     *
291     * @return previous <code>Element</code> if available
292     *
293     */
294    public Element previous() {
295
296        int stackSize;
297        if (elementStack == null || (stackSize = elementStack.size()) == 0) {
298            return null;
299        }
300
301        // get a handle to the element on top of the stack
302        //
303        StackItem item = elementStack.peek();
304        Element elem = item.getElement();
305        int index = item.getIndex();
306
307        if (index > 0) {
308            /* return child at previous index. */
309            return getDeepestLeaf(elem.getElement(--index));
310        } else if (index == 0) {
311            /* this implies that current is the element's
312               first child, therefore previous is the
313               element itself. */
314            return elem;
315        } else if (index == -1) {
316            if (stackSize == 1) {
317                // current is the root, nothing before it.
318                return null;
319            }
320            /* We need to return either the item
321               below the top item or one of the
322               former's children. */
323            StackItem top = elementStack.pop();
324            item = elementStack.peek();
325
326            // restore the top item.
327            elementStack.push(top);
328            elem = item.getElement();
329            index = item.getIndex();
330            return ((index == -1) ? elem : getDeepestLeaf(elem.getElement
331                                                          (index)));
332        }
333        // should never get here.
334        return null;
335    }
336
337    /**
338     * Returns the last child of <code>parent</code> that is a leaf. If the
339     * last child is a not a leaf, this method is called with the last child.
340     */
341    private Element getDeepestLeaf(Element parent) {
342        if (parent.isLeaf()) {
343            return parent;
344        }
345        int childCount = parent.getElementCount();
346        if (childCount == 0) {
347            return parent;
348        }
349        return getDeepestLeaf(parent.getElement(childCount - 1));
350    }
351
352    /*
353      Iterates through the element tree and prints
354      out each element and its attributes.
355    */
356    private void dumpTree() {
357
358        Element elem;
359        while (true) {
360            if ((elem = next()) != null) {
361                System.out.println("elem: " + elem.getName());
362                AttributeSet attr = elem.getAttributes();
363                String s = "";
364                Enumeration<?> names = attr.getAttributeNames();
365                while (names.hasMoreElements()) {
366                    Object key = names.nextElement();
367                    Object value = attr.getAttribute(key);
368                    if (value instanceof AttributeSet) {
369                        // don't go recursive
370                        s = s + key + "=**AttributeSet** ";
371                    } else {
372                        s = s + key + "=" + value + " ";
373                    }
374                }
375                System.out.println("attributes: " + s);
376            } else {
377                break;
378            }
379        }
380    }
381}
382