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}