1 ///////////////////////////////////////////////////////////////////////////////////////////////
2 // checkstyle: Checks Java source code and other text files for adherence to a set of rules.
3 // Copyright (C) 2001-2026 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.ArrayDeque;
23 import java.util.Deque;
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 /**
38 * Queue for sibling nodes.
39 */
40 private final Queue<NodeInfo> queue = new ArrayDeque<>();
41 /**
42 * Stack for child nodes, to represent them in reverse order.
43 */
44 private final Deque<NodeInfo> stack = new ArrayDeque<>();
45
46 /**
47 * Create an iterator over the "descendant" axis in reverse order.
48 *
49 * @param start the initial context node.
50 */
51 public ReverseDescendantIterator(NodeInfo start) {
52 pushToStack(start.iterateAxis(AxisInfo.CHILD));
53 }
54
55 /**
56 * Pushes all children to the stack.
57 *
58 * @param iterateAxis {@link AxisInfo#CHILD} axis iterator.
59 */
60 private void pushToStack(AxisIterator iterateAxis) {
61 NodeInfo nodeInfo = iterateAxis.next();
62 while (nodeInfo != null) {
63 stack.addLast(nodeInfo);
64 nodeInfo = iterateAxis.next();
65 }
66 }
67
68 /**
69 * Get the next item in the sequence.
70 *
71 * @return the next Item. If there are no more nodes, return null.
72 */
73 @Override
74 public NodeInfo next() {
75 NodeInfo result = null;
76 do {
77 if (stack.isEmpty()) {
78 if (queue.isEmpty()) {
79 break;
80 }
81 pushToStack(queue.poll().iterateAxis(AxisInfo.CHILD));
82 }
83 else {
84 result = stack.removeLast();
85 }
86 } while (result == null);
87
88 if (result != null) {
89 queue.add(result);
90 }
91 return result;
92 }
93
94 }