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 }