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 
  26 package javax.swing.text;
  27 
  28 import java.util.Stack;
  29 import 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 
  71 public 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 }