Source for gnu.xml.dom.DomIterator

   1: /* DomIterator.java --
   2:    Copyright (C) 1999, 2000, 2001, 2006 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., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 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 org.w3c.dom.DOMException;
  41: import org.w3c.dom.Node;
  42: import org.w3c.dom.events.Event;
  43: import org.w3c.dom.events.EventListener;
  44: import org.w3c.dom.events.EventTarget;
  45: import org.w3c.dom.events.MutationEvent;
  46: import org.w3c.dom.traversal.NodeFilter;
  47: import org.w3c.dom.traversal.NodeIterator;
  48: 
  49: /**
  50:  * <p> "NodeIterator" implementation, usable with any L2 DOM which
  51:  * supports MutationEvents. </p>
  52:  *
  53:  * @author David Brownell
  54:  */
  55: public final class DomIterator
  56:   implements NodeIterator, EventListener
  57: {
  58: 
  59:   private Node reference;
  60:   private boolean right;
  61:   private boolean done;
  62: 
  63:   private final Node root;
  64:   private final int whatToShow;
  65:   private final NodeFilter filter;
  66:   private final boolean expandEntityReferences;
  67: 
  68:   /**
  69:    * Constructs and initializes an iterator.
  70:    */
  71:   protected DomIterator(Node root,
  72:                         int whatToShow,
  73:                         NodeFilter filter,
  74:                         boolean entityReferenceExpansion)
  75:   {
  76:     if (!root.isSupported("MutationEvents", "2.0"))
  77:       {
  78:         throw new DomDOMException(DOMException.NOT_SUPPORTED_ERR,
  79:                         "Iterator needs mutation events", root, 0);
  80:       }
  81: 
  82:     this.root = root;
  83:     this.whatToShow = whatToShow;
  84:     this.filter = filter;
  85:     this.expandEntityReferences = entityReferenceExpansion;
  86: 
  87:     // start condition:  going right, seen nothing yet.
  88:     reference = null;
  89:     right = true;
  90: 
  91:     EventTarget target = (EventTarget) root;
  92:     target.addEventListener("DOMNodeRemoved", this, false);
  93:   }
  94: 
  95:   /**
  96:    * <b>DOM L2</b>
  97:    * Flags the iterator as done, unregistering its event listener so
  98:    * that the iterator can be garbage collected without relying on weak
  99:    * references (a "Java 2" feature) in the event subsystem.
 100:    */
 101:   public void detach()
 102:   {
 103:     EventTarget target = (EventTarget) root;
 104:     target.removeEventListener("DOMNodeRemoved", this, false);
 105:     done = true;
 106:   }
 107: 
 108:   /**
 109:    * <b>DOM L2</b>
 110:    * Returns the flag controlling whether iteration descends
 111:    * through entity references.
 112:    */
 113:   public boolean getExpandEntityReferences()
 114:   {
 115:     return expandEntityReferences;
 116:   }
 117: 
 118:   /**
 119:    * <b>DOM L2</b>
 120:    * Returns the filter provided during construction.
 121:    */
 122:   public NodeFilter getFilter()
 123:   {
 124:     return filter;
 125:   }
 126: 
 127:   /**
 128:    * <b>DOM L2</b>
 129:    * Returns the root of the tree this is iterating through.
 130:    */
 131:   public Node getRoot()
 132:   {
 133:     return root;
 134:   }
 135: 
 136:   /**
 137:    * <b>DOM L2</b>
 138:    * Returns the mask of flags provided during construction.
 139:    */
 140:   public int getWhatToShow()
 141:   {
 142:     return whatToShow;
 143:   }
 144: 
 145:   /**
 146:    * <b>DOM L2</b>
 147:    * Returns the next node in a forward iteration, masked and filtered.
 148:    * Note that the node may be read-only due to entity expansions.
 149:    * A null return indicates the iteration is complete, but may still
 150:    * be processed backwards.
 151:    */
 152:   public Node nextNode()
 153:   {
 154:     if (done)
 155:       {
 156:         throw new DomDOMException(DOMException.INVALID_STATE_ERR);
 157:       }
 158:     right = true;
 159:     return walk(true);
 160:   }
 161: 
 162:   /**
 163:    * <b>DOM L2</b>
 164:    * Returns the next node in a backward iteration, masked and filtered.
 165:    * Note that the node may be read-only due to entity expansions.
 166:    * A null return indicates the iteration is complete, but may still
 167:    * be processed forwards.
 168:    */
 169:   public Node previousNode()
 170:   {
 171:     if (done)
 172:       {
 173:         throw new DomDOMException(DOMException.INVALID_STATE_ERR);
 174:       }
 175:     Node previous = reference;
 176:     right = false;
 177:     walk(false);
 178:     return previous;
 179:   }
 180: 
 181:   private boolean shouldShow(Node node)
 182:     // raises Runtime exceptions indirectly, via acceptNode()
 183:   {
 184:     if ((whatToShow & (1 << (node.getNodeType() - 1))) == 0)
 185:       {
 186:         return false;
 187:       }
 188:     if (filter == null)
 189:       {
 190:         return true;
 191:       }
 192:     return filter.acceptNode(node) == NodeFilter.FILTER_ACCEPT;
 193:   }
 194: 
 195:   //
 196:   // scenario:  root = 1, sequence = 1 2 ... 3 4
 197:   // forward walk: 1 2 ... 3 4 null
 198:   // then backward: 4 3 ... 2 1 null
 199:   //
 200:   // At the leftmost end, "previous" == null
 201:   // At the rightmost end, "previous" == 4
 202:   //
 203:   // The current draft spec really seem to make no sense re the
 204:   // role of the reference node, so what it says is ignored here.
 205:   //
 206:   private Node walk(boolean forward)
 207:   {
 208:     Node here = reference;
 209: 
 210:     while ((here = successor(here, forward)) != null
 211:            && !shouldShow(here))
 212:       {
 213:         continue;
 214:       }
 215:     if (here != null || !forward)
 216:       {
 217:         reference = here;
 218:       }
 219:     return here;
 220:   }
 221: 
 222:   private boolean isLeaf(Node here)
 223:   {
 224:     boolean leaf = !here.hasChildNodes();
 225:     if (!leaf && !expandEntityReferences)
 226:       {
 227:         leaf = (here.getNodeType() == Node.ENTITY_REFERENCE_NODE);
 228:       }
 229:     return leaf;
 230:   }
 231: 
 232:   //
 233:   // Returns the immediate successor in a forward (or backward)
 234:   // document order walk, sans filtering ... except that it knows
 235:   // how to stop, returning null when done.  This is a depth first
 236:   // preorder traversal when run in the forward direction.
 237:   //
 238:   private Node successor(Node here, boolean forward)
 239:   {
 240:     Node next;
 241: 
 242:     // the "leftmost" end is funky
 243:     if (here == null)
 244:       {
 245:         return forward ? root : null;
 246:       }
 247: 
 248:     //
 249:     // Forward, this is preorder: children before siblings.
 250:     // Backward, it's postorder: we saw the children already.
 251:     //
 252:     if (forward && !isLeaf(here))
 253:       {
 254:         return here.getFirstChild();
 255:       }
 256: 
 257:     // There's no way up or sideways from the root, so if we
 258:     // couldn't move down to a child, there's nowhere to go.
 259:     //
 260:     if (here == root)
 261:       return null;
 262: 
 263:     //
 264:     // Siblings ... if forward, we visit them, if backwards
 265:     // we visit their children first.
 266:     //
 267:     if (forward)
 268:       {
 269:         if ((next = here.getNextSibling()) != null)
 270:           {
 271:             return next;
 272:           }
 273:       }
 274:     else if ((next = here.getPreviousSibling()) != null)
 275:       {
 276:         if (isLeaf(next))
 277:           {
 278:             return next;
 279:           }
 280:         next = next.getLastChild();
 281:         while (!isLeaf(next))
 282:           {
 283:             next = next.getLastChild();
 284:           }
 285:         return next;
 286:       }
 287: 
 288:     //
 289:     // We can't go down or lateral -- it's up, then.  The logic is
 290:     // the converse of what's above:  backwards is easy (the parent
 291:     // is next), forwards isn't.
 292:     //
 293:     next = here.getParentNode();
 294:     if (!forward)
 295:       {
 296:         return next;
 297:       }
 298: 
 299:     Node temp = null;
 300:     while (next != null
 301:            && next != root
 302:            && (temp = next.getNextSibling()) == null)
 303:       {
 304:         next = next.getParentNode();
 305:       }
 306: 
 307:     // If we have exceeded the root node then stop traversing.
 308:     if (next == root.getParentNode())
 309:       {
 310:         return null;
 311:       }
 312:     return temp;
 313:   }
 314: 
 315:   /**
 316:    * Not for public use.  This lets the iterator know when its
 317:    * reference node will be removed from the tree, so that a new
 318:    * one may be selected.
 319:    *
 320:    * <p> This version works by watching removal events as they
 321:    * bubble up.  So, don't prevent them from bubbling.
 322:    */
 323:   public void handleEvent(Event e)
 324:   {
 325:     MutationEvent event;
 326:     Node ancestor, removed;
 327: 
 328:     if (reference == null
 329:         || !"DOMNodeRemoved".equals(e.getType())
 330:         || e.getEventPhase() != Event.BUBBLING_PHASE)
 331:       {
 332:         return;
 333:       }
 334: 
 335:     event = (MutationEvent) e;
 336:     removed = (Node) event.getTarget();
 337: 
 338:     // See if the removal will cause trouble for this iterator
 339:     // by being the reference node or an ancestor of it.
 340:     for (ancestor = reference;
 341:          ancestor != null && ancestor != root;
 342:          ancestor = ancestor.getParentNode())
 343:       {
 344:         if (ancestor == removed)
 345:           {
 346:             break;
 347:           }
 348:       }
 349:     if (ancestor != removed)
 350:       {
 351:         return;
 352:       }
 353: 
 354:     // OK, it'll cause trouble.  We want to make the "next"
 355:     // node in our current traversal direction seem right.
 356:     // So we pick the nearest node that's not getting removed,
 357:     // but go in the _opposite_ direction from our current
 358:     // traversal ... so the "next" doesn't skip anything.
 359:     Node candidate;
 360: 
 361: search:
 362:     while ((candidate = walk(!right)) != null)
 363:       {
 364:         for (ancestor = candidate;
 365:              ancestor != null && ancestor != root;
 366:              ancestor = ancestor.getParentNode())
 367:           {
 368:             if (ancestor == removed)
 369:               {
 370:                 continue search;
 371:               }
 372:           }
 373:         return;
 374:       }
 375: 
 376:     // The current DOM WD talks about a special case here;
 377:     // I've not yet seen it.
 378:     }
 379: 
 380: }