diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/Tree/TreeIterator.cs')
| -rw-r--r-- | runtime/CSharp3/Sources/Antlr3.Runtime/Tree/TreeIterator.cs | 180 |
1 files changed, 180 insertions, 0 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/TreeIterator.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/TreeIterator.cs new file mode 100644 index 0000000..02549d5 --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/TreeIterator.cs @@ -0,0 +1,180 @@ +/* + * [The "BSD licence"] + * Copyright (c) 2005-2008 Terence Parr + * All rights reserved. + * + * Conversion to C#: + * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +namespace Antlr.Runtime.Tree +{ + using System.Collections.Generic; + + /** Return a node stream from a doubly-linked tree whose nodes + * know what child index they are. No remove() is supported. + * + * Emit navigation nodes (DOWN, UP, and EOF) to let show tree structure. + */ + public class TreeIterator : IEnumerator<object> + { + protected ITreeAdaptor adaptor; + protected object root; + protected object tree; + protected bool firstTime = true; + private bool reachedEof; + + // navigation nodes to return during walk and at end + public object up; + public object down; + public object eof; + + /** If we emit UP/DOWN nodes, we need to spit out multiple nodes per + * next() call. + */ + protected Queue<object> nodes; + + public TreeIterator( CommonTree tree ) + : this( new CommonTreeAdaptor(), tree ) + { + } + + public TreeIterator( ITreeAdaptor adaptor, object tree ) + { + this.adaptor = adaptor; + this.tree = tree; + this.root = tree; + nodes = new Queue<object>(); + down = adaptor.Create( TokenTypes.Down, "DOWN" ); + up = adaptor.Create( TokenTypes.Up, "UP" ); + eof = adaptor.Create( TokenTypes.EndOfFile, "EOF" ); + } + + #region IEnumerator<object> Members + + public object Current + { + get; + private set; + } + + #endregion + + #region IDisposable Members + + public void Dispose() + { + } + + #endregion + + #region IEnumerator Members + + public bool MoveNext() + { + if ( firstTime ) + { + // initial condition + firstTime = false; + if ( adaptor.GetChildCount( tree ) == 0 ) + { + // single node tree (special) + nodes.Enqueue( eof ); + } + Current = tree; + } + else + { + // if any queued up, use those first + if ( nodes != null && nodes.Count > 0 ) + { + Current = nodes.Dequeue(); + } + else + { + // no nodes left? + if ( tree == null ) + { + Current = eof; + } + else + { + // next node will be child 0 if any children + if ( adaptor.GetChildCount( tree ) > 0 ) + { + tree = adaptor.GetChild( tree, 0 ); + nodes.Enqueue( tree ); // real node is next after DOWN + Current = down; + } + else + { + // if no children, look for next sibling of tree or ancestor + object parent = adaptor.GetParent( tree ); + // while we're out of siblings, keep popping back up towards root + while ( parent != null && + adaptor.GetChildIndex( tree ) + 1 >= adaptor.GetChildCount( parent ) ) + { + nodes.Enqueue( up ); // we're moving back up + tree = parent; + parent = adaptor.GetParent( tree ); + } + + // no nodes left? + if ( parent == null ) + { + tree = null; // back at root? nothing left then + nodes.Enqueue( eof ); // add to queue, might have UP nodes in there + Current = nodes.Dequeue(); + } + else + { + // must have found a node with an unvisited sibling + // move to it and return it + int nextSiblingIndex = adaptor.GetChildIndex( tree ) + 1; + tree = adaptor.GetChild( parent, nextSiblingIndex ); + nodes.Enqueue( tree ); // add to queue, might have UP nodes in there + Current = nodes.Dequeue(); + } + } + } + } + } + + bool result = Current != eof || !reachedEof; + reachedEof = Current == eof; + return result; + } + + public void Reset() + { + firstTime = true; + tree = root; + nodes.Clear(); + } + + #endregion + } +} |