1 ///////////////////////////////////////////////////////////////////////////////////////////////
2 // checkstyle: Checks Java source code and other text files for adherence to a set of rules.
3 // Copyright (C) 2001-2024 the original author or authors.
4 //
5 // This library is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU Lesser General Public
7 // License as published by the Free Software Foundation; either
8 // version 2.1 of the License, or (at your option) any later version.
9 //
10 // This library is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 // Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public
16 // License along with this library; if not, write to the Free Software
17 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 ///////////////////////////////////////////////////////////////////////////////////////////////
19
20 package com.puppycrawl.tools.checkstyle.xpath.iterators;
21
22 import java.util.Deque;
23 import java.util.LinkedList;
24 import java.util.Queue;
25
26 import net.sf.saxon.om.AxisInfo;
27 import net.sf.saxon.om.NodeInfo;
28 import net.sf.saxon.tree.iter.AxisIterator;
29
30 /**
31 * Recursive-free implementation of the descendant axis iterator. Difference between this iterator
32 * and {@link DescendantIterator} in traversal order of the child nodes. In some cases it is useful
33 * to iterate from last child backwards to the first one, for example in {@link PrecedingIterator}.
34 */
35 public class ReverseDescendantIterator implements AxisIterator {
36 /**
37 * Queue for sibling nodes.
38 */
39 private final Queue<NodeInfo> queue = new LinkedList<>();
40 /**
41 * Stack for child nodes, to represent them in reverse order.
42 */
43 private final Deque<NodeInfo> stack = new LinkedList<>();
44
45 /**
46 * Create an iterator over the "descendant" axis in reverse order.
47 *
48 * @param start the initial context node.
49 */
50 public ReverseDescendantIterator(NodeInfo start) {
51 pushToStack(start.iterateAxis(AxisInfo.CHILD));
52 }
53
54 /**
55 * Pushes all children to the stack.
56 *
57 * @param iterateAxis {@link AxisInfo#CHILD} axis iterator.
58 */
59 private void pushToStack(AxisIterator iterateAxis) {
60 NodeInfo nodeInfo = iterateAxis.next();
61 while (nodeInfo != null) {
62 stack.addLast(nodeInfo);
63 nodeInfo = iterateAxis.next();
64 }
65 }
66
67 /**
68 * Get the next item in the sequence.
69 *
70 * @return the next Item. If there are no more nodes, return null.
71 */
72 @Override
73 public NodeInfo next() {
74 NodeInfo result = null;
75 do {
76 if (stack.isEmpty()) {
77 if (queue.isEmpty()) {
78 break;
79 }
80 pushToStack(queue.poll().iterateAxis(AxisInfo.CHILD));
81 }
82 else {
83 result = stack.removeLast();
84 }
85 } while (result == null);
86
87 if (result != null) {
88 queue.add(result);
89 }
90 return result;
91 }
92 }