1. /*
  2. * The Apache Software License, Version 1.1
  3. *
  4. *
  5. * Copyright (c) 1999-2002 The Apache Software Foundation. All rights
  6. * reserved.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions
  10. * are met:
  11. *
  12. * 1. Redistributions of source code must retain the above copyright
  13. * notice, this list of conditions and the following disclaimer.
  14. *
  15. * 2. Redistributions in binary form must reproduce the above copyright
  16. * notice, this list of conditions and the following disclaimer in
  17. * the documentation and/or other materials provided with the
  18. * distribution.
  19. *
  20. * 3. The end-user documentation included with the redistribution,
  21. * if any, must include the following acknowledgment:
  22. * "This product includes software developed by the
  23. * Apache Software Foundation (http://www.apache.org/)."
  24. * Alternately, this acknowledgment may appear in the software itself,
  25. * if and wherever such third-party acknowledgments normally appear.
  26. *
  27. * 4. The names "Xerces" and "Apache Software Foundation" must
  28. * not be used to endorse or promote products derived from this
  29. * software without prior written permission. For written
  30. * permission, please contact apache@apache.org.
  31. *
  32. * 5. Products derived from this software may not be called "Apache",
  33. * nor may "Apache" appear in their name, without prior written
  34. * permission of the Apache Software Foundation.
  35. *
  36. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  37. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  38. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  39. * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  40. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  42. * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  43. * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  44. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  45. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  46. * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  47. * SUCH DAMAGE.
  48. * ====================================================================
  49. *
  50. * This software consists of voluntary contributions made by many
  51. * individuals on behalf of the Apache Software Foundation and was
  52. * originally based on software copyright (c) 1999, International
  53. * Business Machines, Inc., http://www.apache.org. For more
  54. * information on the Apache Software Foundation, please see
  55. * <http://www.apache.org/>.
  56. */
  57. package com.sun.org.apache.xerces.internal.dom;
  58. import org.w3c.dom.DOMException;
  59. import org.w3c.dom.Node;
  60. import org.w3c.dom.traversal.NodeFilter;
  61. import org.w3c.dom.traversal.NodeIterator;
  62. /** DefaultNodeIterator implements a NodeIterator, which iterates a
  63. * DOM tree in the expected depth first way.
  64. *
  65. * <p>The whatToShow and filter functionality is implemented as expected.
  66. *
  67. * <p>This class also has method removeNode to enable iterator "fix-up"
  68. * on DOM remove. It is expected that the DOM implementation call removeNode
  69. * right before the actual DOM transformation. If not called by the DOM,
  70. * the client could call it before doing the removal.
  71. *
  72. * @version $Id: NodeIteratorImpl.java,v 1.11 2002/11/06 22:58:28 elena Exp $
  73. */
  74. public class NodeIteratorImpl implements NodeIterator {
  75. //
  76. // Data
  77. //
  78. /** The DocumentImpl which created this iterator, so it can be detached. */
  79. private DocumentImpl fDocument;
  80. /** The root. */
  81. private Node fRoot;
  82. /** The whatToShow mask. */
  83. private int fWhatToShow = NodeFilter.SHOW_ALL;
  84. /** The NodeFilter reference. */
  85. private NodeFilter fNodeFilter;
  86. /** If detach is called, the fDetach flag is true, otherwise flase. */
  87. private boolean fDetach = false;
  88. //
  89. // Iterator state - current node and direction.
  90. //
  91. // Note: The current node and direction are sufficient to implement
  92. // the desired behaviour of the current pointer being _between_
  93. // two nodes. The fCurrentNode is actually the last node returned,
  94. // and the
  95. // direction is whether the pointer is in front or behind this node.
  96. // (usually akin to whether the node was returned via nextNode())
  97. // (eg fForward = true) or previousNode() (eg fForward = false).
  98. // Note also, if removing a Node, the fCurrentNode
  99. // can be placed on a Node which would not pass filters.
  100. /** The last Node returned. */
  101. private Node fCurrentNode;
  102. /** The direction of the iterator on the fCurrentNode.
  103. * <pre>
  104. * nextNode() == fForward = true;
  105. * previousNode() == fForward = false;
  106. * </pre>
  107. */
  108. private boolean fForward = true;
  109. /** When TRUE, the children of entites references are returned in the iterator. */
  110. private boolean fEntityReferenceExpansion;
  111. //
  112. // Constructor
  113. //
  114. /** Public constructor */
  115. public NodeIteratorImpl( DocumentImpl document,
  116. Node root,
  117. int whatToShow,
  118. NodeFilter nodeFilter,
  119. boolean entityReferenceExpansion) {
  120. fDocument = document;
  121. fRoot = root;
  122. fCurrentNode = null;
  123. fWhatToShow = whatToShow;
  124. fNodeFilter = nodeFilter;
  125. fEntityReferenceExpansion = entityReferenceExpansion;
  126. }
  127. public Node getRoot() {
  128. return fRoot;
  129. }
  130. // Implementation Note: Note that the iterator looks at whatToShow
  131. // and filter values at each call, and therefore one _could_ add
  132. // setters for these values and alter them while iterating!
  133. /** Return the whatToShow value */
  134. public int getWhatToShow() {
  135. return fWhatToShow;
  136. }
  137. /** Return the filter */
  138. public NodeFilter getFilter() {
  139. return fNodeFilter;
  140. }
  141. /** Return whether children entity references are included in the iterator. */
  142. public boolean getExpandEntityReferences() {
  143. return fEntityReferenceExpansion;
  144. }
  145. /** Return the next Node in the Iterator. The node is the next node in
  146. * depth-first order which also passes the filter, and whatToShow.
  147. * If there is no next node which passes these criteria, then return null.
  148. */
  149. public Node nextNode() {
  150. if( fDetach) {
  151. throw new DOMException(
  152. DOMException.INVALID_STATE_ERR,
  153. DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
  154. }
  155. // if root is null there is no next node.
  156. if (fRoot == null) return null;
  157. Node nextNode = fCurrentNode;
  158. boolean accepted = false; // the next node has not been accepted.
  159. accepted_loop:
  160. while (!accepted) {
  161. // if last direction is not forward, repeat node.
  162. if (!fForward && nextNode!=null) {
  163. //System.out.println("nextNode():!fForward:"+fCurrentNode.getNodeName());
  164. nextNode = fCurrentNode;
  165. } else {
  166. // else get the next node via depth-first
  167. if (!fEntityReferenceExpansion
  168. && nextNode != null
  169. && nextNode.getNodeType() == Node.ENTITY_REFERENCE_NODE) {
  170. nextNode = nextNode(nextNode, false);
  171. } else {
  172. nextNode = nextNode(nextNode, true);
  173. }
  174. }
  175. fForward = true; //REVIST: should direction be set forward before null check?
  176. // nothing in the list. return null.
  177. if (nextNode == null) return null;
  178. // does node pass the filters and whatToShow?
  179. accepted = acceptNode(nextNode);
  180. if (accepted) {
  181. // if so, then the node is the current node.
  182. fCurrentNode = nextNode;
  183. return fCurrentNode;
  184. } else
  185. continue accepted_loop;
  186. } // while (!accepted) {
  187. // no nodes, or no accepted nodes.
  188. return null;
  189. }
  190. /** Return the previous Node in the Iterator. The node is the next node in
  191. * _backwards_ depth-first order which also passes the filter, and whatToShow.
  192. */
  193. public Node previousNode() {
  194. if( fDetach) {
  195. throw new DOMException(
  196. DOMException.INVALID_STATE_ERR,
  197. DOMMessageFormatter.formatMessage(DOMMessageFormatter.DOM_DOMAIN, "INVALID_STATE_ERR", null));
  198. }
  199. // if the root is null, or the current node is null, return null.
  200. if (fRoot == null || fCurrentNode == null) return null;
  201. Node previousNode = fCurrentNode;
  202. boolean accepted = false;
  203. accepted_loop:
  204. while (!accepted) {
  205. if (fForward && previousNode != null) {
  206. //repeat last node.
  207. previousNode = fCurrentNode;
  208. } else {
  209. // get previous node in backwards depth first order.
  210. previousNode = previousNode(previousNode);
  211. }
  212. // we are going backwards
  213. fForward = false;
  214. // if the new previous node is null, we're at head or past the root,
  215. // so return null.
  216. if (previousNode == null) return null;
  217. // check if node passes filters and whatToShow.
  218. accepted = acceptNode(previousNode);
  219. if (accepted) {
  220. // if accepted, update the current node, and return it.
  221. fCurrentNode = previousNode;
  222. return fCurrentNode;
  223. } else
  224. continue accepted_loop;
  225. }
  226. // there are no nodes?
  227. return null;
  228. }
  229. /** The node is accepted if it passes the whatToShow and the filter. */
  230. boolean acceptNode(Node node) {
  231. if (fNodeFilter == null) {
  232. return ( fWhatToShow & (1 << node.getNodeType()-1)) != 0 ;
  233. } else {
  234. return ((fWhatToShow & (1 << node.getNodeType()-1)) != 0 )
  235. && fNodeFilter.acceptNode(node) == NodeFilter.FILTER_ACCEPT;
  236. }
  237. }
  238. /** Return node, if matches or any parent if matches. */
  239. Node matchNodeOrParent(Node node) {
  240. // Additions and removals in the underlying data structure may occur
  241. // before any iterations, and in this case the reference_node is null.
  242. if (fCurrentNode == null) return null;
  243. // check if the removed node is an _ancestor_ of the
  244. // reference node
  245. for (Node n = fCurrentNode; n != fRoot; n = n.getParentNode()) {
  246. if (node == n) return n;
  247. }
  248. return null;
  249. }
  250. /** The method nextNode(Node, boolean) returns the next node
  251. * from the actual DOM tree.
  252. *
  253. * The boolean visitChildren determines whether to visit the children.
  254. * The result is the nextNode.
  255. */
  256. Node nextNode(Node node, boolean visitChildren) {
  257. if (node == null) return fRoot;
  258. Node result;
  259. // only check children if we visit children.
  260. if (visitChildren) {
  261. //if hasChildren, return 1st child.
  262. if (node.hasChildNodes()) {
  263. result = node.getFirstChild();
  264. return result;
  265. }
  266. }
  267. if (node == fRoot) { //if Root has no kids
  268. return null;
  269. }
  270. // if hasSibling, return sibling
  271. result = node.getNextSibling();
  272. if (result != null) return result;
  273. // return parent's 1st sibling.
  274. Node parent = node.getParentNode();
  275. while (parent != null && parent != fRoot) {
  276. result = parent.getNextSibling();
  277. if (result != null) {
  278. return result;
  279. } else {
  280. parent = parent.getParentNode();
  281. }
  282. } // while (parent != null && parent != fRoot) {
  283. // end of list, return null
  284. return null;
  285. }
  286. /** The method previousNode(Node) returns the previous node
  287. * from the actual DOM tree.
  288. */
  289. Node previousNode(Node node) {
  290. Node result;
  291. // if we're at the root, return null.
  292. if (node == fRoot) return null;
  293. // get sibling
  294. result = node.getPreviousSibling();
  295. if (result == null) {
  296. //if 1st sibling, return parent
  297. result = node.getParentNode();
  298. return result;
  299. }
  300. // if sibling has children, keep getting last child of child.
  301. if (result.hasChildNodes()
  302. && !(!fEntityReferenceExpansion
  303. && result != null
  304. && result.getNodeType() == Node.ENTITY_REFERENCE_NODE))
  305. {
  306. while (result.hasChildNodes()) {
  307. result = result.getLastChild();
  308. }
  309. }
  310. return result;
  311. }
  312. /** Fix-up the iterator on a remove. Called by DOM or otherwise,
  313. * before an actual DOM remove.
  314. */
  315. public void removeNode(Node node) {
  316. // Implementation note: Fix-up means setting the current node properly
  317. // after a remove.
  318. if (node == null) return;
  319. Node deleted = matchNodeOrParent(node);
  320. if (deleted == null) return;
  321. if (fForward) {
  322. fCurrentNode = previousNode(deleted);
  323. } else
  324. // if (!fForward)
  325. {
  326. Node next = nextNode(deleted, false);
  327. if (next!=null) {
  328. // normal case: there _are_ nodes following this in the iterator.
  329. fCurrentNode = next;
  330. } else {
  331. // the last node in the iterator is to be removed,
  332. // so we set the current node to be the previous one.
  333. fCurrentNode = previousNode(deleted);
  334. fForward = true;
  335. }
  336. }
  337. }
  338. public void detach() {
  339. fDetach = true;
  340. fDocument.removeNodeIterator(this);
  341. }
  342. }