1 package org.jaxen.util;
2
3 /*
4 * $Header: /home/projects/jaxen/scm/jaxen/src/java/main/org/jaxen/util/PrecedingAxisIterator.java,v 1.8 2005/07/24 11:51:14 elharo Exp $
5 * $Revision: 1.8 $
6 * $Date: 2005/07/24 11:51:14 $
7 *
8 * ====================================================================
9 *
10 * Copyright (C) 2000-2005 bob mcwhirter & James Strachan.
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 *
17 * 1. Redistributions of source code must retain the above copyright
18 * notice, this list of conditions, and the following disclaimer.
19 *
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions, and the disclaimer that follows
22 * these conditions in the documentation and/or other materials
23 * provided with the distribution.
24 *
25 * 3. The name "Jaxen" must not be used to endorse or promote products
26 * derived from this software without prior written permission. For
27 * written permission, please contact license@jaxen.org.
28 *
29 * 4. Products derived from this software may not be called "Jaxen", nor
30 * may "Jaxen" appear in their name, without prior written permission
31 * from the Jaxen Project Management (pm@jaxen.org).
32 *
33 * In addition, we request (but do not require) that you include in the
34 * end-user documentation provided with the redistribution and/or in the
35 * software itself an acknowledgement equivalent to the following:
36 * "This product includes software developed by the
37 * Jaxen Project <http://www.jaxen.org/>."
38 * Alternatively, the acknowledgment may be graphical using the logos
39 * available at http://www.jaxen.org/
40 *
41 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
42 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
43 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
44 * DISCLAIMED. IN NO EVENT SHALL THE Jaxen AUTHORS OR THE PROJECT
45 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
46 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
47 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
48 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
49 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
50 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
51 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 * SUCH DAMAGE.
53 *
54 * ====================================================================
55 * This software consists of voluntary contributions made by many
56 * individuals on behalf of the Jaxen Project and was originally
57 * created by bob mcwhirter <bob@werken.com> and
58 * James Strachan <jstrachan@apache.org>. For more information on the
59 * Jaxen Project, please see <http://www.jaxen.org/>.
60 *
61 * $Id: PrecedingAxisIterator.java,v 1.8 2005/07/24 11:51:14 elharo Exp $
62 */
63
64 import org.jaxen.JaxenConstants;
65 import org.jaxen.JaxenRuntimeException;
66 import org.jaxen.Navigator;
67 import org.jaxen.UnsupportedAxisException;
68
69 import java.util.ArrayList;
70 import java.util.Iterator;
71 import java.util.ListIterator;
72 import java.util.NoSuchElementException;
73
74 /***
75 * This implementation of 'preceding' works like so:
76 * the preceding axis includes preceding-siblings of this node and their
77 * descendants. Also, for each ancestor node of this node, it includes
78 * all preceding-siblings of that ancestor, and their descendants. Finally, it
79 * includes the ancestor nodes themselves.
80 * <p/>
81 * The reversed descendant-or-self axes that are required are calculated using a
82 * stack of reversed 'child-or-self' axes. When asked for a node, it is always taken
83 * from a child-or-self axis. If it was the last node on that axis, the node is returned.
84 * Otherwise, this axis is pushed on the stack, and the process is repeated with the child-or-self
85 * of the node. Eventually this recurses down to the last descendant of any node, then works
86 * back up to the root.
87 * <p/>
88 * I reckon most object models could provide a faster implementation of the reversed
89 * 'children-or-self' used here.
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 public PrecedingAxisIterator(Object contextNode,
101 Navigator navigator) throws UnsupportedAxisException
102 {
103 this.navigator = navigator;
104 this.ancestorOrSelf = navigator.getAncestorOrSelfAxisIterator(contextNode);
105 this.precedingSibling = JaxenConstants.EMPTY_ITERATOR;
106 this.childrenOrSelf = JaxenConstants.EMPTY_LIST_ITERATOR;
107 this.stack = new ArrayList();
108 }
109
110
111 public boolean hasNext()
112 {
113 try
114 {
115 while (!childrenOrSelf.hasPrevious())
116 {
117 if (stack.isEmpty())
118 {
119 while (!precedingSibling.hasNext())
120 {
121 if (!ancestorOrSelf.hasNext())
122 {
123 return false;
124 }
125 Object contextNode = ancestorOrSelf.next();
126 precedingSibling = new PrecedingSiblingAxisIterator(contextNode, navigator);
127 }
128 Object node = precedingSibling.next();
129 childrenOrSelf = childrenOrSelf(node);
130 }
131 else
132 {
133 childrenOrSelf = (ListIterator) stack.remove(stack.size()-1);
134 }
135 }
136 return true;
137 }
138 catch (UnsupportedAxisException e)
139 {
140 throw new JaxenRuntimeException(e);
141 }
142 }
143
144 private ListIterator childrenOrSelf(Object node)
145 {
146 try
147 {
148 ArrayList reversed = new ArrayList();
149 reversed.add(node);
150 Iterator childAxisIterator = navigator.getChildAxisIterator(node);
151 if (childAxisIterator != null)
152 {
153 while (childAxisIterator.hasNext())
154 {
155 reversed.add(childAxisIterator.next());
156 }
157 }
158 return reversed.listIterator(reversed.size());
159 }
160 catch (UnsupportedAxisException e)
161 {
162 throw new JaxenRuntimeException(e);
163 }
164 }
165
166 public Object next() throws NoSuchElementException
167 {
168 if (!hasNext())
169 {
170 throw new NoSuchElementException();
171 }
172 while (true)
173 {
174 Object result = childrenOrSelf.previous();
175 if (childrenOrSelf.hasPrevious())
176 {
177 // if this isn't 'self' construct 'descendant-or-self'
178 stack.add(childrenOrSelf);
179 childrenOrSelf = childrenOrSelf(result);
180 continue;
181 }
182 return result;
183 }
184 }
185
186
187 public void remove() throws UnsupportedOperationException
188 {
189 throw new UnsupportedOperationException();
190 }
191 }