13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.tree; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.Token; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.CommonToken; 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.misc.FastQueue; 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.Iterator; 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/** Return a node stream from a doubly-linked tree whose nodes 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * know what child index they are. No remove() is supported. 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Emit navigation nodes (DOWN, UP, and EOF) to let show tree structure. 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class TreeIterator implements Iterator { 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected TreeAdaptor adaptor; 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Object root; 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Object tree; 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected boolean firstTime = true; 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // navigation nodes to return during walk and at end 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object up; 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object down; 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object eof; 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** If we emit UP/DOWN nodes, we need to spit out multiple nodes per 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * next() call. 543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected FastQueue nodes; 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeIterator(Object tree) { 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this(new CommonTreeAdaptor(),tree); 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeIterator(TreeAdaptor adaptor, Object tree) { 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.tree = tree; 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.root = tree; 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes = new FastQueue(); 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein down = adaptor.create(Token.DOWN, "DOWN"); 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein up = adaptor.create(Token.UP, "UP"); 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein eof = adaptor.create(Token.EOF, "EOF"); 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void reset() { 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein firstTime = true; 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tree = root; 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.clear(); 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean hasNext() { 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( firstTime ) return root!=null; 793447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( nodes!=null && nodes.size()>0 ) return true; 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tree==null ) return false; 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getChildCount(tree)>0 ) return true; 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return adaptor.getParent(tree)!=null; // back at root? 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object next() { 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( firstTime ) { // initial condition 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein firstTime = false; 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getChildCount(tree)==0 ) { // single node tree (special) 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(eof); 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return tree; 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return tree; 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // if any queued up, use those first 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( nodes!=null && nodes.size()>0 ) return nodes.remove(); 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // no nodes left? 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( tree==null ) return eof; 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // next node will be child 0 if any children 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( adaptor.getChildCount(tree)>0 ) { 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tree = adaptor.getChild(tree, 0); 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(tree); // real node is next after DOWN 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return down; 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // if no children, look for next sibling of tree or ancestor 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object parent = adaptor.getParent(tree); 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // while we're out of siblings, keep popping back up towards root 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein while ( parent!=null && 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein adaptor.getChildIndex(tree)+1 >= adaptor.getChildCount(parent) ) 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein { 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(up); // we're moving back up 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tree = parent; 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein parent = adaptor.getParent(tree); 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // no nodes left? 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( parent==null ) { 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tree = null; // back at root? nothing left then 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(eof); // add to queue, might have UP nodes in there 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return nodes.remove(); 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // must have found a node with an unvisited sibling 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // move to it and return it 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int nextSiblingIndex = adaptor.getChildIndex(tree) + 1; 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein tree = adaptor.getChild(parent, nextSiblingIndex); 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein nodes.add(tree); // add to queue, might have UP nodes in there 1283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return nodes.remove(); 1293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void remove() { throw new UnsupportedOperationException(); } 1323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 133