libjava/gnu/xml/dom/DomIterator.java

   1 /* DomIterator.java --
   2    Copyright (C) 1999,2000,2001 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package gnu.xml.dom;
  39
  40 import java.util.Vector;
  41
  42 import org.w3c.dom.Node;
  43 import org.w3c.dom.events.Event;
  44 import org.w3c.dom.events.EventListener;
  45 import org.w3c.dom.events.EventTarget;
  46 import org.w3c.dom.events.MutationEvent;
  47 import org.w3c.dom.traversal.NodeFilter;
  48 import org.w3c.dom.traversal.NodeIterator;
  49
  50 /**
  51  * <p> "NodeIterator" implementation, usable with any L2 DOM which
  52  * supports MutationEvents. </p>
  53  *
  54  * @author David Brownell
  55  */
  56 public final class DomIterator
  57   implements NodeIterator, EventListener
  58 {
  59
  60   private Node reference;
  61   private boolean right;
  62   private boolean done;
  63
  64   private final Node root;
  65   private final int whatToShow;
  66   private final NodeFilter filter;
  67   private final boolean expandEntityReferences;
  68
  69   /**
  70    * Constructs and initializes an iterator.
  71    */
  72   protected DomIterator(Node root,
  73                         int whatToShow,
  74                         NodeFilter filter,
  75                         boolean entityReferenceExpansion)
  76   {
  77     if (!root.isSupported("MutationEvents", "2.0"))
  78       {
  79         throw new DomEx(DomEx.NOT_SUPPORTED_ERR,
  80                         "Iterator needs mutation events", root, 0);
  81       }
  82
  83     this.root = root;
  84     this.whatToShow = whatToShow;
  85     this.filter = filter;
  86     this.expandEntityReferences = entityReferenceExpansion;
  87
  88     // start condition:  going right, seen nothing yet.
  89     reference = null;
  90     right = true;
  91
  92     EventTarget target = (EventTarget) root;
  93     target.addEventListener("DOMNodeRemoved", this, false);
  94   }
  95
  96   /**
  97    * <b>DOM L2</b>
  98    * Flags the iterator as done, unregistering its event listener so
  99    * that the iterator can be garbage collected without relying on weak
 100    * references (a "Java 2" feature) in the event subsystem.
 101    */
 102   public void detach()
 103   {
 104     EventTarget target = (EventTarget) root;
 105     target.removeEventListener("DOMNodeRemoved", this, false);
 106     done = true;
 107   }
 108
 109   /**
 110    * <b>DOM L2</b>
 111    * Returns the flag controlling whether iteration descends
 112    * through entity references.
 113    */
 114   public boolean getExpandEntityReferences()
 115   {
 116     return expandEntityReferences;
 117   }
 118
 119   /**
 120    * <b>DOM L2</b>
 121    * Returns the filter provided during construction.
 122    */
 123   public NodeFilter getFilter()
 124   {
 125     return filter;
 126   }
 127
 128   /**
 129    * <b>DOM L2</b>
 130    * Returns the root of the tree this is iterating through.
 131    */
 132   public Node getRoot()
 133   {
 134     return root;
 135   }
 136
 137   /**
 138    * <b>DOM L2</b>
 139    * Returns the mask of flags provided during construction.
 140    */
 141   public int getWhatToShow()
 142   {
 143     return whatToShow;
 144   }
 145
 146   /**
 147    * <b>DOM L2</b>
 148    * Returns the next node in a forward iteration, masked and filtered.
 149    * Note that the node may be read-only due to entity expansions.
 150    * A null return indicates the iteration is complete, but may still
 151    * be processed backwards.
 152    */
 153   public Node nextNode()
 154   {
 155     if (done)
 156       {
 157         throw new DomEx(DomEx.INVALID_STATE_ERR);
 158       }
 159     right = true;
 160     return walk(true);
 161   }
 162
 163   /**
 164    * <b>DOM L2</b>
 165    * Returns the next node in a backward iteration, masked and filtered.
 166    * Note that the node may be read-only due to entity expansions.
 167    * A null return indicates the iteration is complete, but may still
 168    * be processed forwards.
 169    */
 170   public Node previousNode()
 171   {
 172     if (done)
 173       {
 174         throw new DomEx(DomEx.INVALID_STATE_ERR);
 175       }
 176     Node previous = reference;
 177     right = false;
 178     walk(false);
 179     return previous;
 180   }
 181
 182   private boolean shouldShow(Node node)
 183     // raises Runtime exceptions indirectly, via acceptNode()
 184   {
 185     if ((whatToShow & (1 << (node.getNodeType() - 1))) == 0)
 186       {
 187         return false;
 188       }
 189     if (filter == null)
 190       {
 191         return true;
 192       }
 193     return filter.acceptNode(node) == NodeFilter.FILTER_ACCEPT;
 194   }
 195
 196   //
 197   // scenario:  root = 1, sequence = 1 2 ... 3 4
 198   // forward walk: 1 2 ... 3 4 null
 199   // then backward: 4 3 ... 2 1 null
 200   //
 201   // At the leftmost end, "previous" == null
 202   // At the rightmost end, "previous" == 4
 203   //
 204   // The current draft spec really seem to make no sense re the
 205   // role of the reference node, so what it says is ignored here.
 206   //
 207   private Node walk(boolean forward)
 208   {
 209     Node here = reference;
 210
 211     while ((here = successor(here, forward)) != null
 212            && !shouldShow(here))
 213       {
 214         continue;
 215       }
 216     if (here != null || !forward)
 217       {
 218         reference = here;
 219       }
 220     return here;
 221   }
 222
 223   private boolean isLeaf(Node here)
 224   {
 225     boolean leaf = !here.hasChildNodes();
 226     if (!leaf && !expandEntityReferences)
 227       {
 228         leaf = (here.getNodeType() == Node.ENTITY_REFERENCE_NODE);
 229       }
 230     return leaf;
 231   }
 232
 233   //
 234   // Returns the immediate successor in a forward (or backward)
 235   // document order walk, sans filtering ... except that it knows
 236   // how to stop, returning null when done.  This is a depth first
 237   // preorder traversal when run in the forward direction.
 238   //
 239   private Node successor(Node here, boolean forward)
 240   {
 241     Node next;
 242
 243     // the "leftmost" end is funky
 244     if (here == null)
 245       {
 246         return forward ? root : null;
 247       }
 248
 249     //
 250     // Forward, this is preorder: children before siblings.
 251     // Backward, it's postorder: we saw the children already.
 252     //
 253     if (forward && !isLeaf(here))
 254       {
 255         return here.getFirstChild();
 256       }
 257
 258     //
 259     // Siblings ... if forward, we visit them, if backwards
 260     // we visit their children first.
 261     //
 262     if (forward)
 263       {
 264         if ((next = here.getNextSibling()) != null)
 265           {
 266             return next;
 267           }
 268       }
 269     else if ((next = here.getPreviousSibling()) != null)
 270       {
 271         if (isLeaf(next))
 272           {
 273             return next;
 274           }
 275         next = next.getLastChild();
 276         while (!isLeaf(next))
 277           {
 278             next = next.getLastChild();
 279           }
 280         return next;
 281       }
 282
 283     //
 284     // We can't go down or lateral -- it's up, then.  The logic is
 285     // the converse of what's above:  backwards is easy (the parent
 286     // is next), forwards isn't.
 287     //
 288     next = here.getParentNode();
 289     if (!forward)
 290       {
 291         return next;
 292       }
 293
 294     Node temp = null;
 295     while (next != null
 296            && next != root
 297            && (temp = next.getNextSibling()) == null)
 298       {
 299         next = next.getParentNode();
 300       }
 301     if (next == root)
 302       {
 303         return null;
 304       }
 305     return temp;
 306   }
 307
 308   /**
 309    * Not for public use.  This lets the iterator know when its
 310    * reference node will be removed from the tree, so that a new
 311    * one may be selected.
 312    *
 313    * <p> This version works by watching removal events as they
 314    * bubble up.  So, don't prevent them from bubbling.
 315    */
 316   public void handleEvent(Event e)
 317   {
 318     MutationEvent event;
 319     Node ancestor, removed;
 320
 321     if (reference == null
 322         || !"DOMNodeRemoved".equals(e.getType())
 323         || e.getEventPhase() != Event.BUBBLING_PHASE)
 324       {
 325         return;
 326       }
 327
 328     event = (MutationEvent) e;
 329     removed = (Node) event.getTarget();
 330
 331     // See if the removal will cause trouble for this iterator
 332     // by being the reference node or an ancestor of it.
 333     for (ancestor = reference;
 334          ancestor != null && ancestor != root;
 335          ancestor = ancestor.getParentNode())
 336       {
 337         if (ancestor == removed)
 338           {
 339             break;
 340           }
 341       }
 342     if (ancestor != removed)
 343       {
 344         return;
 345       }
 346
 347     // OK, it'll cause trouble.  We want to make the "next"
 348     // node in our current traversal direction seem right.
 349     // So we pick the nearest node that's not getting removed,
 350     // but go in the _opposite_ direction from our current
 351     // traversal ... so the "next" doesn't skip anything.
 352     Node candidate;
 353
 354 search:
 355     while ((candidate = walk(!right)) != null)
 356       {
 357         for (ancestor = candidate;
 358              ancestor != null && ancestor != root;
 359              ancestor = ancestor.getParentNode())
 360           {
 361             if (ancestor == removed)
 362               {
 363                 continue search;
 364               }
 365           }
 366         return;
 367       }
 368
 369     // The current DOM WD talks about a special case here;
 370     // I've not yet seen it.
 371     }
 372
 373 }
 374