001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2026 the original author or authors.
004//
005// This library is free software; you can redistribute it and/or
006// modify it under the terms of the GNU Lesser General Public
007// License as published by the Free Software Foundation; either
008// version 2.1 of the License, or (at your option) any later version.
009//
010// This library is distributed in the hope that it will be useful,
011// but WITHOUT ANY WARRANTY; without even the implied warranty of
012// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013// Lesser General Public License for more details.
014//
015// You should have received a copy of the GNU Lesser General Public
016// License along with this library; if not, write to the Free Software
017// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
018///////////////////////////////////////////////////////////////////////////////////////////////
019
020package com.puppycrawl.tools.checkstyle.xpath.iterators;
021
022import java.util.ArrayDeque;
023import java.util.Deque;
024import java.util.Queue;
025
026import net.sf.saxon.om.AxisInfo;
027import net.sf.saxon.om.NodeInfo;
028import net.sf.saxon.tree.iter.AxisIterator;
029
030/**
031 * Recursive-free implementation of the descendant axis iterator. Difference between this iterator
032 * and {@link DescendantIterator} in traversal order of the child nodes. In some cases it is useful
033 * to iterate from last child backwards to the first one, for example in {@link PrecedingIterator}.
034 */
035public class ReverseDescendantIterator implements AxisIterator {
036
037    /**
038     * Queue for sibling nodes.
039     */
040    private final Queue<NodeInfo> queue = new ArrayDeque<>();
041    /**
042     * Stack for child nodes, to represent them in reverse order.
043     */
044    private final Deque<NodeInfo> stack = new ArrayDeque<>();
045
046    /**
047     * Create an iterator over the "descendant" axis in reverse order.
048     *
049     * @param start the initial context node.
050     */
051    public ReverseDescendantIterator(NodeInfo start) {
052        pushToStack(start.iterateAxis(AxisInfo.CHILD));
053    }
054
055    /**
056     * Pushes all children to the stack.
057     *
058     * @param iterateAxis {@link AxisInfo#CHILD} axis iterator.
059     */
060    private void pushToStack(AxisIterator iterateAxis) {
061        NodeInfo nodeInfo = iterateAxis.next();
062        while (nodeInfo != null) {
063            stack.addLast(nodeInfo);
064            nodeInfo = iterateAxis.next();
065        }
066    }
067
068    /**
069     * Get the next item in the sequence.
070     *
071     * @return the next Item. If there are no more nodes, return null.
072     */
073    @Override
074    public NodeInfo next() {
075        NodeInfo result = null;
076        do {
077            if (stack.isEmpty()) {
078                if (queue.isEmpty()) {
079                    break;
080                }
081                pushToStack(queue.poll().iterateAxis(AxisInfo.CHILD));
082            }
083            else {
084                result = stack.removeLast();
085            }
086        } while (result == null);
087
088        if (result != null) {
089            queue.add(result);
090        }
091        return result;
092    }
093
094}