View Javadoc

1   package org.jaxen.util;
2   
3   /*
4    * $Header: /home/projects/jaxen/scm/jaxen/src/java/main/org/jaxen/util/PrecedingAxisIterator.java,v 1.6 2005/01/19 01:53:35 bewins Exp $
5    * $Revision: 1.6 $
6    * $Date: 2005/01/19 01:53:35 $
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.6 2005/01/19 01:53:35 bewins 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  import java.util.Stack;
74  
75  /***
76   * This implementation of 'preceding' works like so:
77   * the preceding axis includes preceding-siblings of this node and their
78   * descendants. Also, for each ancestor node of this node, it includes
79   * all preceding-siblings of that ancestor, and their descendants. Finally, it
80   * includes the ancestor nodes themselves.
81   * <p/>
82   * The reversed descendant-or-self axes that are required are calculated using a
83   * stack of reversed 'child-or-self' axes. When asked for a node, it is always taken
84   * from a child-or-self axis. If it was the last node on that axis, the node is returned.
85   * Otherwise, this axis is pushed on the stack, and the process is repeated with the child-or-self
86   * of the node. Eventually this recurses down to the last descendant of any node, then works
87   * back up to the root.
88   * <p/>
89   * I reckon most object models could provide a faster implementation of the reversed
90   * 'children-or-self' used here.
91   */
92  public class PrecedingAxisIterator implements Iterator
93  {
94      private Iterator ancestorOrSelf;
95      private Iterator precedingSibling;
96      private ListIterator childrenOrSelf;
97      private Stack stack;
98  
99      private Navigator navigator;
100 
101     public PrecedingAxisIterator(Object contextNode,
102                                  Navigator navigator) throws UnsupportedAxisException
103     {
104         this.navigator = navigator;
105         this.ancestorOrSelf = navigator.getAncestorOrSelfAxisIterator(contextNode);
106         this.precedingSibling = JaxenConstants.EMPTY_ITERATOR;
107         this.childrenOrSelf = JaxenConstants.EMPTY_LIST_ITERATOR;
108         this.stack = new Stack();
109     }
110 
111 
112     public boolean hasNext()
113     {
114         try
115         {
116             while (!childrenOrSelf.hasPrevious())
117             {
118                 if (stack.isEmpty())
119                 {
120                     while (!precedingSibling.hasNext())
121                     {
122                         if (!ancestorOrSelf.hasNext())
123                         {
124                             return false;
125                         }
126                         Object contextNode = ancestorOrSelf.next();
127                         precedingSibling = new PrecedingSiblingAxisIterator(contextNode, navigator);
128                     }
129                     Object node = precedingSibling.next();
130                     childrenOrSelf = childrenOrSelf(node);
131                 }
132                 else
133                 {
134                     childrenOrSelf = (ListIterator) stack.pop();
135                 }
136             }
137             return true;
138         }
139         catch (UnsupportedAxisException e)
140         {
141             throw new JaxenRuntimeException(e);
142         }
143     }
144 
145     private ListIterator childrenOrSelf(Object node)
146     {
147         try
148         {
149             ArrayList reversed = new ArrayList();
150             reversed.add(node);
151             Iterator childAxisIterator = navigator.getChildAxisIterator(node);
152             if (childAxisIterator != null)
153             {
154                 while (childAxisIterator.hasNext())
155                 {
156                     reversed.add(childAxisIterator.next());
157                 }
158             }
159             return reversed.listIterator(reversed.size());
160         }
161         catch (UnsupportedAxisException e)
162         {
163             throw new JaxenRuntimeException(e);
164         }
165     }
166 
167     public Object next() throws NoSuchElementException
168     {
169         if (!hasNext())
170         {
171             throw new NoSuchElementException();
172         }
173         while (true)
174         {
175             Object result = childrenOrSelf.previous();
176             if (childrenOrSelf.hasPrevious())
177             {
178                 // if this isn't 'self' construct 'descendant-or-self'
179                 stack.push(childrenOrSelf);
180                 childrenOrSelf = childrenOrSelf(result);
181                 continue;
182             }
183             return result;
184         }
185     }
186 
187 
188     public void remove() throws UnsupportedOperationException
189     {
190         throw new UnsupportedOperationException();
191     }
192 }