src/core/net/sf/basedb/util/Tree.java

Code
Comments
Other
Rev Date Author Line
2096 21 Mar 06 nicklas 1 /*
2096 21 Mar 06 nicklas 2   $Id$
2096 21 Mar 06 nicklas 3
4889 06 Apr 09 nicklas 4   Copyright (C) 2006 Jari Häkkinen, Nicklas Nordborg
2096 21 Mar 06 nicklas 5
2304 22 May 06 jari 6   This file is part of BASE - BioArray Software Environment.
2304 22 May 06 jari 7   Available at http://base.thep.lu.se/
2096 21 Mar 06 nicklas 8
2096 21 Mar 06 nicklas 9   BASE is free software; you can redistribute it and/or
2096 21 Mar 06 nicklas 10   modify it under the terms of the GNU General Public License
4479 05 Sep 08 jari 11   as published by the Free Software Foundation; either version 3
2096 21 Mar 06 nicklas 12   of the License, or (at your option) any later version.
2096 21 Mar 06 nicklas 13
2096 21 Mar 06 nicklas 14   BASE is distributed in the hope that it will be useful,
2096 21 Mar 06 nicklas 15   but WITHOUT ANY WARRANTY; without even the implied warranty of
2096 21 Mar 06 nicklas 16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
2096 21 Mar 06 nicklas 17   GNU General Public License for more details.
2096 21 Mar 06 nicklas 18
2096 21 Mar 06 nicklas 19   You should have received a copy of the GNU General Public License
4515 11 Sep 08 jari 20   along with BASE. If not, see <http://www.gnu.org/licenses/>.
2096 21 Mar 06 nicklas 21 */
2096 21 Mar 06 nicklas 22 package net.sf.basedb.util;
2096 21 Mar 06 nicklas 23
2096 21 Mar 06 nicklas 24 import java.util.Collection;
2096 21 Mar 06 nicklas 25 import java.util.Collections;
2096 21 Mar 06 nicklas 26 import java.util.HashMap;
2096 21 Mar 06 nicklas 27 import java.util.Iterator;
2096 21 Mar 06 nicklas 28 import java.util.LinkedList;
2096 21 Mar 06 nicklas 29 import java.util.List;
2096 21 Mar 06 nicklas 30 import java.util.Map;
2096 21 Mar 06 nicklas 31 import java.util.NoSuchElementException;
2096 21 Mar 06 nicklas 32
2096 21 Mar 06 nicklas 33
2096 21 Mar 06 nicklas 34 /**
2096 21 Mar 06 nicklas 35
2096 21 Mar 06 nicklas 36   @author Nicklas
2096 21 Mar 06 nicklas 37   @version 2.0
2096 21 Mar 06 nicklas 38   @base.modified $Date$
2096 21 Mar 06 nicklas 39 */
2096 21 Mar 06 nicklas 40 public class Tree<E>
2096 21 Mar 06 nicklas 41   implements Collection<E>
2096 21 Mar 06 nicklas 42 {
2096 21 Mar 06 nicklas 43
2096 21 Mar 06 nicklas 44   private final E root;
2096 21 Mar 06 nicklas 45   private final Map<E, Entry<E>> entries;
2096 21 Mar 06 nicklas 46
2096 21 Mar 06 nicklas 47   /**
2096 21 Mar 06 nicklas 48     Create a new tree with the with the default initial capacity (16).
2096 21 Mar 06 nicklas 49     @param root The root node element of the tree
2096 21 Mar 06 nicklas 50   */
2096 21 Mar 06 nicklas 51   public Tree(E root)
2096 21 Mar 06 nicklas 52   {
2096 21 Mar 06 nicklas 53     this(root, 16);
2096 21 Mar 06 nicklas 54   }
2096 21 Mar 06 nicklas 55   
2096 21 Mar 06 nicklas 56   /**
2096 21 Mar 06 nicklas 57     Create a new tree with the with the specified initial capacity.
2096 21 Mar 06 nicklas 58     @param root The root node element of the tree
2096 21 Mar 06 nicklas 59     @param initialCapacity The initial capacity
2096 21 Mar 06 nicklas 60    */
2096 21 Mar 06 nicklas 61   public Tree(E root, int initialCapacity)
2096 21 Mar 06 nicklas 62   {
2096 21 Mar 06 nicklas 63     entries = new HashMap<E, Entry<E>>(initialCapacity);
2096 21 Mar 06 nicklas 64     this.root = root;
2096 21 Mar 06 nicklas 65     entries.put(root, new Entry<E>(this, root, null));
2096 21 Mar 06 nicklas 66   }
2096 21 Mar 06 nicklas 67   
2096 21 Mar 06 nicklas 68   
2096 21 Mar 06 nicklas 69   /*
2096 21 Mar 06 nicklas 70     From the Collection interface
2096 21 Mar 06 nicklas 71     -------------------------------------------
2096 21 Mar 06 nicklas 72   */
2096 21 Mar 06 nicklas 73   /**
2096 21 Mar 06 nicklas 74     Not supported.
2302 22 May 06 nicklas 75     @see Entry#addChild(Object)
2096 21 Mar 06 nicklas 76     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 77   */
6127 14 Sep 12 nicklas 78   @Override
2096 21 Mar 06 nicklas 79   public boolean add(E o)
2096 21 Mar 06 nicklas 80   {
2096 21 Mar 06 nicklas 81     throw new UnsupportedOperationException("add");
2096 21 Mar 06 nicklas 82   }
2096 21 Mar 06 nicklas 83   /**
2096 21 Mar 06 nicklas 84     Not supported.
2096 21 Mar 06 nicklas 85     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 86   */
6127 14 Sep 12 nicklas 87   @Override
2096 21 Mar 06 nicklas 88   public boolean addAll(Collection<? extends E> c)
2096 21 Mar 06 nicklas 89   {
2096 21 Mar 06 nicklas 90     throw new UnsupportedOperationException("addAll");
2096 21 Mar 06 nicklas 91   }
2096 21 Mar 06 nicklas 92   /**
2096 21 Mar 06 nicklas 93     Clear all elements except the root element.
2096 21 Mar 06 nicklas 94   */
6127 14 Sep 12 nicklas 95   @Override
2096 21 Mar 06 nicklas 96   public void clear()
2096 21 Mar 06 nicklas 97   {
2096 21 Mar 06 nicklas 98     entries.clear();
2096 21 Mar 06 nicklas 99     entries.put(root, new Entry<E>(this, root, null));
2096 21 Mar 06 nicklas 100   }
6127 14 Sep 12 nicklas 101   @Override
2096 21 Mar 06 nicklas 102   public boolean contains(Object o)
2096 21 Mar 06 nicklas 103   {
2096 21 Mar 06 nicklas 104     return entries.containsKey(o);
2096 21 Mar 06 nicklas 105   }
6127 14 Sep 12 nicklas 106   @Override
2096 21 Mar 06 nicklas 107   public boolean containsAll(Collection<?> c)
2096 21 Mar 06 nicklas 108   {
2096 21 Mar 06 nicklas 109     return entries.keySet().containsAll(c);
2096 21 Mar 06 nicklas 110   }
2096 21 Mar 06 nicklas 111   /**
2096 21 Mar 06 nicklas 112      Equality only tests if the object is the same instance of this tree.
5007 23 Jun 09 nicklas 113      Note! In the future, the implementation may change to also check the
5007 23 Jun 09 nicklas 114      entire tree structure.
2096 21 Mar 06 nicklas 115   */
6127 14 Sep 12 nicklas 116   @Override
2096 21 Mar 06 nicklas 117   public boolean equals(Object o)
2096 21 Mar 06 nicklas 118   {
2096 21 Mar 06 nicklas 119     return this == o;
2096 21 Mar 06 nicklas 120   }
6872 16 Apr 15 nicklas 121   
6127 14 Sep 12 nicklas 122   @Override
6872 16 Apr 15 nicklas 123   public int hashCode() 
6872 16 Apr 15 nicklas 124   {
6872 16 Apr 15 nicklas 125     return super.hashCode();
6872 16 Apr 15 nicklas 126   }
6872 16 Apr 15 nicklas 127
6872 16 Apr 15 nicklas 128   @Override
2096 21 Mar 06 nicklas 129   public boolean isEmpty()
2096 21 Mar 06 nicklas 130   {
2096 21 Mar 06 nicklas 131     return entries.isEmpty();
2096 21 Mar 06 nicklas 132   }
6127 14 Sep 12 nicklas 133   @Override
2096 21 Mar 06 nicklas 134   public Iterator<E> iterator()
2096 21 Mar 06 nicklas 135   {
2096 21 Mar 06 nicklas 136     return new ElementIterator(entryIterator());
2096 21 Mar 06 nicklas 137   }
2096 21 Mar 06 nicklas 138   /**
2096 21 Mar 06 nicklas 139     Not supported.
2096 21 Mar 06 nicklas 140     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 141   */
6127 14 Sep 12 nicklas 142   @Override
2096 21 Mar 06 nicklas 143   public boolean remove(Object o)
2096 21 Mar 06 nicklas 144   {
2096 21 Mar 06 nicklas 145     throw new UnsupportedOperationException("remove");
2096 21 Mar 06 nicklas 146   }
2096 21 Mar 06 nicklas 147   /**
2096 21 Mar 06 nicklas 148     Not supported.
2096 21 Mar 06 nicklas 149     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 150   */
6127 14 Sep 12 nicklas 151   @Override
2096 21 Mar 06 nicklas 152   public boolean removeAll(Collection<?> c)
2096 21 Mar 06 nicklas 153   {
2096 21 Mar 06 nicklas 154     throw new UnsupportedOperationException("removeAll");
2096 21 Mar 06 nicklas 155   }
2096 21 Mar 06 nicklas 156   /**
2096 21 Mar 06 nicklas 157     Not supported.
2096 21 Mar 06 nicklas 158     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 159   */
6127 14 Sep 12 nicklas 160   @Override
2096 21 Mar 06 nicklas 161   public boolean retainAll(Collection<?> c)
2096 21 Mar 06 nicklas 162   {
2096 21 Mar 06 nicklas 163     throw new UnsupportedOperationException("retainAll");
2096 21 Mar 06 nicklas 164   }
6127 14 Sep 12 nicklas 165   @Override
2096 21 Mar 06 nicklas 166   public int size()
2096 21 Mar 06 nicklas 167   {
2096 21 Mar 06 nicklas 168     return entries.size();
2096 21 Mar 06 nicklas 169   }
2096 21 Mar 06 nicklas 170   /**
2096 21 Mar 06 nicklas 171     Not supported.
2096 21 Mar 06 nicklas 172     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 173   */
6127 14 Sep 12 nicklas 174   @Override
2096 21 Mar 06 nicklas 175   public Object[] toArray()
2096 21 Mar 06 nicklas 176   {
2096 21 Mar 06 nicklas 177     throw new UnsupportedOperationException("toArray");
2096 21 Mar 06 nicklas 178   }
2096 21 Mar 06 nicklas 179   /**
2096 21 Mar 06 nicklas 180     Not supported.
2096 21 Mar 06 nicklas 181     @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 182   */
6127 14 Sep 12 nicklas 183   @Override
2096 21 Mar 06 nicklas 184   public <T> T[] toArray(T[] a)
2096 21 Mar 06 nicklas 185   {
2096 21 Mar 06 nicklas 186     throw new UnsupportedOperationException("toArray");
2096 21 Mar 06 nicklas 187   }
2096 21 Mar 06 nicklas 188   // -------------------------------------------
2096 21 Mar 06 nicklas 189   
2096 21 Mar 06 nicklas 190   /**
2096 21 Mar 06 nicklas 191     Get the entry for the root node.
2096 21 Mar 06 nicklas 192     @return The <code>Entry</code> object for the root node.
2096 21 Mar 06 nicklas 193   */
2096 21 Mar 06 nicklas 194   public Entry<E> getRootEntry()
2096 21 Mar 06 nicklas 195   {
2096 21 Mar 06 nicklas 196     return entries.get(root);
2096 21 Mar 06 nicklas 197   }
2096 21 Mar 06 nicklas 198   
2096 21 Mar 06 nicklas 199   /**
2096 21 Mar 06 nicklas 200     Get the entry for an arbitrary node.
2096 21 Mar 06 nicklas 201     @param node The node to get the entry for.
2096 21 Mar 06 nicklas 202     @return An <code>Entry</code> object or null if the node isn't found
2096 21 Mar 06 nicklas 203   */
2096 21 Mar 06 nicklas 204   public Entry<E> getEntry(E node)
2096 21 Mar 06 nicklas 205   {
2096 21 Mar 06 nicklas 206     return entries.get(node);
2096 21 Mar 06 nicklas 207   }
2096 21 Mar 06 nicklas 208   
2096 21 Mar 06 nicklas 209   /**
2298 19 May 06 nicklas 210      Create an iterator for the tree that returns entry object.
2298 19 May 06 nicklas 211      The iterator starts at the root.
2096 21 Mar 06 nicklas 212     @return An <code>Iterator</code> object
2096 21 Mar 06 nicklas 213     @see #iterator()
2096 21 Mar 06 nicklas 214   */
2096 21 Mar 06 nicklas 215   public Iterator<Entry<E>> entryIterator()
2096 21 Mar 06 nicklas 216   {
2096 21 Mar 06 nicklas 217     return new EntryIterator(getRootEntry());
2096 21 Mar 06 nicklas 218   }
2096 21 Mar 06 nicklas 219   
2298 19 May 06 nicklas 220   /**
2298 19 May 06 nicklas 221      Create an iterator for the tree starting at a specific node.
2298 19 May 06 nicklas 222      @param node The node to start at
2298 19 May 06 nicklas 223     @return An <code>Iterator</code> object
2298 19 May 06 nicklas 224     @see #iterator()
2298 19 May 06 nicklas 225   */
2298 19 May 06 nicklas 226   public Iterator<Entry<E>> entryIterator(E node)
2298 19 May 06 nicklas 227   {
2298 19 May 06 nicklas 228     return new EntryIterator(getEntry(node));
2298 19 May 06 nicklas 229   }
2298 19 May 06 nicklas 230   
2096 21 Mar 06 nicklas 231   private void addEntry(Entry<E> entry)
2096 21 Mar 06 nicklas 232   {
2096 21 Mar 06 nicklas 233     entry.getParent().addChildEntry(entry);
2096 21 Mar 06 nicklas 234     entries.put(entry.getNode(), entry);
2096 21 Mar 06 nicklas 235   }
2096 21 Mar 06 nicklas 236   
2096 21 Mar 06 nicklas 237
2096 21 Mar 06 nicklas 238   /**
2096 21 Mar 06 nicklas 239     Represents an entry for a node in the tree. The entry contains information about
2096 21 Mar 06 nicklas 240     the parent and child nodes, and the depth of the entry within the tree.
2096 21 Mar 06 nicklas 241    */
2096 21 Mar 06 nicklas 242   public static class Entry<E>
2096 21 Mar 06 nicklas 243   {
2096 21 Mar 06 nicklas 244     private final Tree<E> tree;
2096 21 Mar 06 nicklas 245     private final E node;
2096 21 Mar 06 nicklas 246     private final Entry<E> parent;
2096 21 Mar 06 nicklas 247     private List<Entry<E>> children;
2096 21 Mar 06 nicklas 248     private final int depth;
2096 21 Mar 06 nicklas 249     
2096 21 Mar 06 nicklas 250     private Entry(Tree<E> tree, E node, Entry<E> parent)
2096 21 Mar 06 nicklas 251     {
2096 21 Mar 06 nicklas 252       this.tree = tree;
2096 21 Mar 06 nicklas 253       this.node = node;
2096 21 Mar 06 nicklas 254       this.parent = parent;
2096 21 Mar 06 nicklas 255       this.depth = parent == null ? 0 : parent.depth + 1; 
2096 21 Mar 06 nicklas 256     }
2096 21 Mar 06 nicklas 257
2096 21 Mar 06 nicklas 258     /**
2096 21 Mar 06 nicklas 259       Get the node element object.
2302 22 May 06 nicklas 260       @return The node elemenet of this entry
2096 21 Mar 06 nicklas 261     */
2096 21 Mar 06 nicklas 262     public E getNode()
2096 21 Mar 06 nicklas 263     {
2096 21 Mar 06 nicklas 264       return node;
2096 21 Mar 06 nicklas 265     }
2096 21 Mar 06 nicklas 266     
2096 21 Mar 06 nicklas 267     /**
2096 21 Mar 06 nicklas 268       Get the entry for the parent node.
2096 21 Mar 06 nicklas 269       @return An <code>Entry</code> object or null if this is the root entry
2096 21 Mar 06 nicklas 270      */
2096 21 Mar 06 nicklas 271     public Entry<E> getParent()
2096 21 Mar 06 nicklas 272     {
2096 21 Mar 06 nicklas 273       return parent;
2096 21 Mar 06 nicklas 274     }
2096 21 Mar 06 nicklas 275     
2096 21 Mar 06 nicklas 276     /**
2096 21 Mar 06 nicklas 277        Get the depth of this entry within the tree. The root node is at depth 0.
2096 21 Mar 06 nicklas 278       @return The depth starting with 0 at the root node
2096 21 Mar 06 nicklas 279     */
2096 21 Mar 06 nicklas 280     public int getDepth()
2096 21 Mar 06 nicklas 281     {
2096 21 Mar 06 nicklas 282       return depth;
2096 21 Mar 06 nicklas 283     }
2096 21 Mar 06 nicklas 284
2096 21 Mar 06 nicklas 285     /**
2096 21 Mar 06 nicklas 286        Add a child to the node.
2096 21 Mar 06 nicklas 287       @param child The child to add
2166 19 Apr 06 nicklas 288       @return The <code>Entry</code> object of the new child node
2096 21 Mar 06 nicklas 289       @throws IllegalArgumentException If the child already exists in the tree
2096 21 Mar 06 nicklas 290     */
2166 19 Apr 06 nicklas 291     public Entry<E> addChild(E child)
2096 21 Mar 06 nicklas 292     {
2096 21 Mar 06 nicklas 293       if (tree.contains(child))
2096 21 Mar 06 nicklas 294       {
2096 21 Mar 06 nicklas 295         throw new IllegalArgumentException("Element '" + child + "' is already in the tree.");
2096 21 Mar 06 nicklas 296       }
2166 19 Apr 06 nicklas 297       Entry<E> childEntry = new Entry<E>(tree, child, this);
2166 19 Apr 06 nicklas 298       tree.addEntry(childEntry);
2166 19 Apr 06 nicklas 299       return childEntry;
2096 21 Mar 06 nicklas 300     }
2096 21 Mar 06 nicklas 301
2096 21 Mar 06 nicklas 302     /**
2096 21 Mar 06 nicklas 303        Get the number of children added to this node.
2096 21 Mar 06 nicklas 304       @return The number of children
2096 21 Mar 06 nicklas 305      */
2096 21 Mar 06 nicklas 306     public int getNumChildren()
2096 21 Mar 06 nicklas 307     {
2096 21 Mar 06 nicklas 308       return children == null ? 0 : children.size();
2096 21 Mar 06 nicklas 309     }
2096 21 Mar 06 nicklas 310     
2096 21 Mar 06 nicklas 311     /**
2096 21 Mar 06 nicklas 312        Get the list of entries for the children  to this node.
2096 21 Mar 06 nicklas 313       @return A <code>List</code> containing the entries for the children
2096 21 Mar 06 nicklas 314         or null if no children has been added to this node
2096 21 Mar 06 nicklas 315     */
2096 21 Mar 06 nicklas 316     public List<Entry<E>> getChildren()
2096 21 Mar 06 nicklas 317     {
2096 21 Mar 06 nicklas 318       return children == null ? null : Collections.unmodifiableList(children);
2096 21 Mar 06 nicklas 319     }
2096 21 Mar 06 nicklas 320     
2096 21 Mar 06 nicklas 321     /**
2096 21 Mar 06 nicklas 322        Check if the specified object is the first child to this node.
2096 21 Mar 06 nicklas 323       @param child The object to check
2096 21 Mar 06 nicklas 324       @return TRUE if the object is the first child, FALSE otherwise
2096 21 Mar 06 nicklas 325     */
2096 21 Mar 06 nicklas 326     public boolean isFirstChild(E child)
2096 21 Mar 06 nicklas 327     {
2096 21 Mar 06 nicklas 328       return children == null || child == null ? false : child.equals(children.get(0).getNode());
2096 21 Mar 06 nicklas 329     }
2096 21 Mar 06 nicklas 330     
2096 21 Mar 06 nicklas 331     /**
2096 21 Mar 06 nicklas 332        Check if the specified object is the last child to this node.
2096 21 Mar 06 nicklas 333       @param child The object to check
2096 21 Mar 06 nicklas 334       @return TRUE if the object is the last child, FALSE otherwise
2096 21 Mar 06 nicklas 335     */
2096 21 Mar 06 nicklas 336     public boolean isLastChild(E child)
2096 21 Mar 06 nicklas 337     {
2096 21 Mar 06 nicklas 338       return children == null || child == null ? false : 
2096 21 Mar 06 nicklas 339         child.equals(children.get(children.size() - 1).getNode());
2096 21 Mar 06 nicklas 340     }
2096 21 Mar 06 nicklas 341
2096 21 Mar 06 nicklas 342     private void addChildEntry(Entry<E> child)
2096 21 Mar 06 nicklas 343     {
2096 21 Mar 06 nicklas 344       if (children == null) children = new LinkedList<Entry<E>>();
2096 21 Mar 06 nicklas 345       children.add(child);
2096 21 Mar 06 nicklas 346     }
2096 21 Mar 06 nicklas 347     
2096 21 Mar 06 nicklas 348   
2096 21 Mar 06 nicklas 349   }
2096 21 Mar 06 nicklas 350
2096 21 Mar 06 nicklas 351   /**
2096 21 Mar 06 nicklas 352     An iterator that return entries for each node.
2096 21 Mar 06 nicklas 353   */
2096 21 Mar 06 nicklas 354   private class EntryIterator
2096 21 Mar 06 nicklas 355     implements Iterator<Entry<E>>
2096 21 Mar 06 nicklas 356   {
2096 21 Mar 06 nicklas 357     /**
2096 21 Mar 06 nicklas 358       The next element to return.
2096 21 Mar 06 nicklas 359     */
2096 21 Mar 06 nicklas 360     private Entry<E> next;
2096 21 Mar 06 nicklas 361     
2096 21 Mar 06 nicklas 362     /**
2096 21 Mar 06 nicklas 363        An iterator over the children of the root entry.
2096 21 Mar 06 nicklas 364     */
2096 21 Mar 06 nicklas 365     private Iterator<Entry<E>> childIterator;
2096 21 Mar 06 nicklas 366     
2096 21 Mar 06 nicklas 367     /**
2096 21 Mar 06 nicklas 368        An iterator over the subtree for each child of the root entry.
2096 21 Mar 06 nicklas 369     */
2096 21 Mar 06 nicklas 370     private Iterator<Entry<E>> subTreeIterator;
2096 21 Mar 06 nicklas 371     
2096 21 Mar 06 nicklas 372     /**
2096 21 Mar 06 nicklas 373        Create an iterator that starts at the specified entry.
5218 18 Jan 10 jari 374        It will return the specified entry as it's first element. Then it
2096 21 Mar 06 nicklas 375        will iterate over the child entries recursively.
2096 21 Mar 06 nicklas 376      */
2096 21 Mar 06 nicklas 377     private EntryIterator(Entry<E> root)
2096 21 Mar 06 nicklas 378     {
2096 21 Mar 06 nicklas 379       next = root;
2891 10 Nov 06 nicklas 380       childIterator = root == null || root.getNumChildren() == 0 ? null : root.getChildren().iterator();
2096 21 Mar 06 nicklas 381     }
2096 21 Mar 06 nicklas 382     
6127 14 Sep 12 nicklas 383     @Override
2096 21 Mar 06 nicklas 384     public boolean hasNext()
2096 21 Mar 06 nicklas 385     {
2096 21 Mar 06 nicklas 386       if (next == null)
2096 21 Mar 06 nicklas 387       {
2096 21 Mar 06 nicklas 388         // If we are in a subtree ...
2096 21 Mar 06 nicklas 389         if (subTreeIterator != null)
2096 21 Mar 06 nicklas 390         {
2096 21 Mar 06 nicklas 391           if (subTreeIterator.hasNext())
2096 21 Mar 06 nicklas 392           {
2096 21 Mar 06 nicklas 393             // ... get the next element
2096 21 Mar 06 nicklas 394             next = subTreeIterator.next();
2096 21 Mar 06 nicklas 395           }
2096 21 Mar 06 nicklas 396           else
2096 21 Mar 06 nicklas 397           {
2096 21 Mar 06 nicklas 398             // ... or we are done with that subtree
2096 21 Mar 06 nicklas 399             subTreeIterator = null;
2096 21 Mar 06 nicklas 400           }
2096 21 Mar 06 nicklas 401         }
2096 21 Mar 06 nicklas 402         // If we don't have a next element get the next child
2096 21 Mar 06 nicklas 403         if (next == null && childIterator != null && childIterator.hasNext())
2096 21 Mar 06 nicklas 404         {
2096 21 Mar 06 nicklas 405           Entry<E> nextChild = childIterator.next();
2096 21 Mar 06 nicklas 406           // If the child has children, we need to iterator over it's subtree
2096 21 Mar 06 nicklas 407           if (nextChild.getNumChildren() > 0) 
2096 21 Mar 06 nicklas 408           {
2096 21 Mar 06 nicklas 409             subTreeIterator = new EntryIterator(nextChild);
2096 21 Mar 06 nicklas 410             next = subTreeIterator.next();
2096 21 Mar 06 nicklas 411           }
2096 21 Mar 06 nicklas 412           else
2096 21 Mar 06 nicklas 413           {
2096 21 Mar 06 nicklas 414             next = nextChild;
2096 21 Mar 06 nicklas 415           }
2096 21 Mar 06 nicklas 416         }
2096 21 Mar 06 nicklas 417       }
2096 21 Mar 06 nicklas 418       return next != null;
2096 21 Mar 06 nicklas 419     }
2096 21 Mar 06 nicklas 420     
6127 14 Sep 12 nicklas 421     @Override
2096 21 Mar 06 nicklas 422     public Entry<E> next()
2096 21 Mar 06 nicklas 423     {
2096 21 Mar 06 nicklas 424       if (!hasNext()) throw new NoSuchElementException();
2096 21 Mar 06 nicklas 425       Entry<E> theNext = next;
2096 21 Mar 06 nicklas 426       next = null;
2096 21 Mar 06 nicklas 427       return theNext;
2096 21 Mar 06 nicklas 428     }
2096 21 Mar 06 nicklas 429     /**
2096 21 Mar 06 nicklas 430       Not supported.
2096 21 Mar 06 nicklas 431       @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 432     */
6127 14 Sep 12 nicklas 433     @Override
2096 21 Mar 06 nicklas 434     public void remove()
2096 21 Mar 06 nicklas 435     {
2096 21 Mar 06 nicklas 436       throw new UnsupportedOperationException("remove");
2096 21 Mar 06 nicklas 437     }
2096 21 Mar 06 nicklas 438   }
2096 21 Mar 06 nicklas 439   
2096 21 Mar 06 nicklas 440   /**
2096 21 Mar 06 nicklas 441     An iterator that return elements for each node. It uses
2096 21 Mar 06 nicklas 442     the {@link EntryIterator} to get the nodes.
2096 21 Mar 06 nicklas 443   */
2096 21 Mar 06 nicklas 444   private class ElementIterator
2096 21 Mar 06 nicklas 445     implements Iterator<E>
2096 21 Mar 06 nicklas 446   {
2096 21 Mar 06 nicklas 447     /**
2096 21 Mar 06 nicklas 448       The entry iterator.
2096 21 Mar 06 nicklas 449     */
2096 21 Mar 06 nicklas 450     private final Iterator<Entry<E>> entryIterator;
2096 21 Mar 06 nicklas 451     
2096 21 Mar 06 nicklas 452     private ElementIterator(Iterator<Entry<E>> entryIterator)
2096 21 Mar 06 nicklas 453     {
2096 21 Mar 06 nicklas 454       this.entryIterator = entryIterator;
2096 21 Mar 06 nicklas 455     }
2096 21 Mar 06 nicklas 456     
6127 14 Sep 12 nicklas 457     @Override
2096 21 Mar 06 nicklas 458     public boolean hasNext()
2096 21 Mar 06 nicklas 459     {
2096 21 Mar 06 nicklas 460       return entryIterator.hasNext();
2096 21 Mar 06 nicklas 461     }
6127 14 Sep 12 nicklas 462     @Override
2096 21 Mar 06 nicklas 463     public E next()
2096 21 Mar 06 nicklas 464     {
2096 21 Mar 06 nicklas 465       if (!hasNext()) throw new NoSuchElementException();
2096 21 Mar 06 nicklas 466       return entryIterator.next().getNode();
2096 21 Mar 06 nicklas 467     }
2096 21 Mar 06 nicklas 468     /**
2096 21 Mar 06 nicklas 469       Not supported.
2096 21 Mar 06 nicklas 470       @throws UnsupportedOperationException Always
2096 21 Mar 06 nicklas 471     */
6127 14 Sep 12 nicklas 472     @Override
2096 21 Mar 06 nicklas 473     public void remove()
2096 21 Mar 06 nicklas 474     {
2096 21 Mar 06 nicklas 475       throw new UnsupportedOperationException("remove");
2096 21 Mar 06 nicklas 476     }
2096 21 Mar 06 nicklas 477   }  
2096 21 Mar 06 nicklas 478 }

Generated on Sat Oct  7 02:39:57 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)