1 package org.jaxen.util; 2 3 /* 4 * $Header$ 5 * $Revision$ 6 * $Date$ 7 * 8 * ==================================================================== 9 * 10 * Copyright 2000-2005 bob mcwhirter & James Strachan. 11 * All rights reserved. 12 * 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: 17 * 18 * * Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 21 * * Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution. 24 * 25 * * Neither the name of the Jaxen Project nor the names of its 26 * contributors may be used to endorse or promote products derived 27 * from this software without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 30 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 31 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 32 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 33 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 34 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 35 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 36 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 37 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 38 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 39 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 40 * 41 * ==================================================================== 42 * This software consists of voluntary contributions made by many 43 * individuals on behalf of the Jaxen Project and was originally 44 * created by bob mcwhirter <bob@werken.com> and 45 * James Strachan <jstrachan@apache.org>. For more information on the 46 * Jaxen Project, please see <http://www.jaxen.org/>. 47 * 48 * $Id$ 49 */ 50 51 import org.jaxen.JaxenConstants; 52 import org.jaxen.JaxenRuntimeException; 53 import org.jaxen.Navigator; 54 import org.jaxen.UnsupportedAxisException; 55 56 import java.util.ArrayList; 57 import java.util.Iterator; 58 import java.util.ListIterator; 59 import java.util.NoSuchElementException; 60 61 /** 62 * <p> 63 * Represents the XPath <code>preceding</code> axis. 64 * The "<code>preceding</code> axis contains all nodes in the same document as the context 65 * node that are before the context node in document order, excluding any ancestors 66 * and excluding attribute nodes and namespace nodes." 67 * 68 * <p> 69 * This implementation of '<code>preceding</code>' works like so: 70 * the <code>preceding</code> axis includes preceding siblings of this node and 71 * their descendants. Also, for each ancestor node of this node, it includes 72 * all preceding siblings of that ancestor, and their descendants. Finally, it 73 * includes the ancestor nodes themselves. 74 * </p> 75 * 76 * <p> 77 * The reversed <code>descendant-or-self</code> axes that are required are calculated using a 78 * stack of reversed 'child-or-self' axes. When asked for a node, it is always taken 79 * from a child-or-self axis. If it was the last node on that axis, the node is returned. 80 * Otherwise, this axis is pushed on the stack, and the process is repeated with the child-or-self 81 * of the node. Eventually this recurses down to the last descendant of any node, then works 82 * back up to the root. 83 * </p> 84 * 85 * <p> 86 * Most object models could provide a faster implementation of the reversed 87 * 'children-or-self' used here.</p> 88 * 89 * @version 1.2b12 90 */ 91 public class PrecedingAxisIterator implements Iterator 92 { 93 private Iterator ancestorOrSelf; 94 private Iterator precedingSibling; 95 private ListIterator childrenOrSelf; 96 private ArrayList stack; 97 98 private Navigator navigator; 99 100 /** 101 * Create a new <code>preceding</code> axis iterator. 102 * 103 * @param contextNode the node to start from 104 * @param navigator the object model specific navigator 105 */ 106 public PrecedingAxisIterator(Object contextNode, 107 Navigator navigator) throws UnsupportedAxisException 108 { 109 this.navigator = navigator; 110 this.ancestorOrSelf = navigator.getAncestorOrSelfAxisIterator(contextNode); 111 this.precedingSibling = JaxenConstants.EMPTY_ITERATOR; 112 this.childrenOrSelf = JaxenConstants.EMPTY_LIST_ITERATOR; 113 this.stack = new ArrayList(); 114 } 115 116 117 /** 118 * Returns true if there are any preceding nodes remaining; false otherwise. 119 * 120 * @return true if any preceding nodes remain; false otherwise 121 * 122 * @see java.util.Iterator#hasNext() 123 */ 124 public boolean hasNext() 125 { 126 try 127 { 128 while (!childrenOrSelf.hasPrevious()) 129 { 130 if (stack.isEmpty()) 131 { 132 while (!precedingSibling.hasNext()) 133 { 134 if (!ancestorOrSelf.hasNext()) 135 { 136 return false; 137 } 138 Object contextNode = ancestorOrSelf.next(); 139 precedingSibling = new PrecedingSiblingAxisIterator(contextNode, navigator); 140 } 141 Object node = precedingSibling.next(); 142 childrenOrSelf = childrenOrSelf(node); 143 } 144 else 145 { 146 childrenOrSelf = (ListIterator) stack.remove(stack.size()-1); 147 } 148 } 149 return true; 150 } 151 catch (UnsupportedAxisException e) 152 { 153 throw new JaxenRuntimeException(e); 154 } 155 } 156 157 private ListIterator childrenOrSelf(Object node) 158 { 159 try 160 { 161 ArrayList reversed = new ArrayList(); 162 reversed.add(node); 163 Iterator childAxisIterator = navigator.getChildAxisIterator(node); 164 if (childAxisIterator != null) 165 { 166 while (childAxisIterator.hasNext()) 167 { 168 reversed.add(childAxisIterator.next()); 169 } 170 } 171 return reversed.listIterator(reversed.size()); 172 } 173 catch (UnsupportedAxisException e) 174 { 175 throw new JaxenRuntimeException(e); 176 } 177 } 178 179 /** 180 * Returns the next preceding node. 181 * 182 * @return the next preceding node 183 * 184 * @throws NoSuchElementException if no preceding nodes remain 185 * 186 * @see java.util.Iterator#next() 187 */ 188 public Object next() throws NoSuchElementException 189 { 190 if (!hasNext()) 191 { 192 throw new NoSuchElementException(); 193 } 194 while (true) 195 { 196 Object result = childrenOrSelf.previous(); 197 if (childrenOrSelf.hasPrevious()) 198 { 199 // if this isn't 'self' construct 'descendant-or-self' 200 stack.add(childrenOrSelf); 201 childrenOrSelf = childrenOrSelf(result); 202 continue; 203 } 204 return result; 205 } 206 } 207 208 209 /** 210 * This operation is not supported. 211 * 212 * @throws UnsupportedOperationException always 213 */ 214 public void remove() throws UnsupportedOperationException 215 { 216 throw new UnsupportedOperationException(); 217 } 218 219 }