001///////////////////////////////////////////////////////////////////////////////////////////////
002// checkstyle: Checks Java source code and other text files for adherence to a set of rules.
003// Copyright (C) 2001-2024 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.Deque;
023import java.util.LinkedList;
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     * Queue for sibling nodes.
038     */
039    private final Queue<NodeInfo> queue = new LinkedList<>();
040    /**
041     * Stack for child nodes, to represent them in reverse order.
042     */
043    private final Deque<NodeInfo> stack = new LinkedList<>();
044
045    /**
046     * Create an iterator over the "descendant" axis in reverse order.
047     *
048     * @param start the initial context node.
049     */
050    public ReverseDescendantIterator(NodeInfo start) {
051        pushToStack(start.iterateAxis(AxisInfo.CHILD));
052    }
053
054    /**
055     * Pushes all children to the stack.
056     *
057     * @param iterateAxis {@link AxisInfo#CHILD} axis iterator.
058     */
059    private void pushToStack(AxisIterator iterateAxis) {
060        NodeInfo nodeInfo = iterateAxis.next();
061        while (nodeInfo != null) {
062            stack.addLast(nodeInfo);
063            nodeInfo = iterateAxis.next();
064        }
065    }
066
067    /**
068     * Get the next item in the sequence.
069     *
070     * @return the next Item. If there are no more nodes, return null.
071     */
072    @Override
073    public NodeInfo next() {
074        NodeInfo result = null;
075        do {
076            if (stack.isEmpty()) {
077                if (queue.isEmpty()) {
078                    break;
079                }
080                pushToStack(queue.poll().iterateAxis(AxisInfo.CHILD));
081            }
082            else {
083                result = stack.removeLast();
084            }
085        } while (result == null);
086
087        if (result != null) {
088            queue.add(result);
089        }
090        return result;
091    }
092}