Source for gnu.xml.dom.DomIterator

   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., 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:     //
 258:     // Siblings ... if forward, we visit them, if backwards
 259:     // we visit their children first.
 260:     //
 261:     if (forward)
 262:       {
 263:         if ((next = here.getNextSibling()) != null)
 264:           {
 265:             return next;
 266:           }
 267:       }
 268:     else if ((next = here.getPreviousSibling()) != null)
 269:       {
 270:         if (isLeaf(next))
 271:           {
 272:             return next;
 273:           }
 274:         next = next.getLastChild();
 275:         while (!isLeaf(next))
 276:           {
 277:             next = next.getLastChild();
 278:           }
 279:         return next;
 280:       }
 281:     
 282:     //
 283:     // We can't go down or lateral -- it's up, then.  The logic is
 284:     // the converse of what's above:  backwards is easy (the parent
 285:     // is next), forwards isn't.
 286:     //
 287:     next = here.getParentNode();
 288:     if (!forward)
 289:       {
 290:         return next;
 291:       }
 292:     
 293:     Node temp = null;
 294:     while (next != null
 295:            && next != root
 296:            && (temp = next.getNextSibling()) == null)
 297:       {
 298:         next = next.getParentNode();
 299:       }
 300:     if (next == root)
 301:       {
 302:         return null;
 303:       }
 304:     return temp;
 305:   }
 306: 
 307:   /**
 308:    * Not for public use.  This lets the iterator know when its
 309:    * reference node will be removed from the tree, so that a new
 310:    * one may be selected.
 311:    *
 312:    * <p> This version works by watching removal events as they
 313:    * bubble up.  So, don't prevent them from bubbling.
 314:    */
 315:   public void handleEvent(Event e)
 316:   {
 317:     MutationEvent event;
 318:     Node ancestor, removed;
 319:     
 320:     if (reference == null
 321:         || !"DOMNodeRemoved".equals(e.getType())
 322:         || e.getEventPhase() != Event.BUBBLING_PHASE)
 323:       {
 324:         return;
 325:       }
 326: 
 327:     event = (MutationEvent) e;
 328:     removed = (Node) event.getTarget();
 329: 
 330:     // See if the removal will cause trouble for this iterator
 331:     // by being the reference node or an ancestor of it.
 332:     for (ancestor = reference;
 333:          ancestor != null && ancestor != root;
 334:          ancestor = ancestor.getParentNode())
 335:       {
 336:         if (ancestor == removed)
 337:           {
 338:             break;
 339:           }
 340:       }
 341:     if (ancestor != removed)
 342:       {
 343:         return;
 344:       }
 345: 
 346:     // OK, it'll cause trouble.  We want to make the "next"
 347:     // node in our current traversal direction seem right.
 348:     // So we pick the nearest node that's not getting removed,
 349:     // but go in the _opposite_ direction from our current
 350:     // traversal ... so the "next" doesn't skip anything.
 351:     Node candidate;
 352: 
 353: search:
 354:     while ((candidate = walk(!right)) != null)
 355:       {
 356:         for (ancestor = candidate;
 357:              ancestor != null && ancestor != root;
 358:              ancestor = ancestor.getParentNode())
 359:           {
 360:             if (ancestor == removed)
 361:               {
 362:                 continue search;
 363:               }
 364:           }
 365:         return;
 366:       }
 367:     
 368:     // The current DOM WD talks about a special case here;
 369:     // I've not yet seen it.
 370:     }
 371:   
 372: }