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.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 }