diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs')
-rw-r--r-- | runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs | 143 |
1 files changed, 0 insertions, 143 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs deleted file mode 100644 index af975d7..0000000 --- a/runtime/CSharp3/Sources/Antlr3.Runtime/Misc/FastQueue.cs +++ /dev/null @@ -1,143 +0,0 @@ -/* - * [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.Misc -{ - using System.Collections.Generic; - using ArgumentException = System.ArgumentException; - using InvalidOperationException = System.InvalidOperationException; - - /** A queue that can dequeue and get(i) in O(1) and grow arbitrarily large. - * A linked list is fast at dequeue but slow at get(i). An array is - * the reverse. This is O(1) for both operations. - * - * List grows until you dequeue last element at end of buffer. Then - * it resets to start filling at 0 again. If adds/removes are balanced, the - * buffer will not grow too large. - * - * No iterator stuff as that's not how we'll use it. - */ - public class FastQueue<T> - { - /** <summary>dynamically-sized buffer of elements</summary> */ - internal List<T> _data = new List<T>(); - /** <summary>index of next element to fill</summary> */ - internal int _p = 0; - - public virtual int Count - { - get - { - return _data.Count - _p; - } - } - - /// <summary> - /// How deep have we gone? - /// </summary> - public virtual int Range - { - get; - protected set; - } - - /** <summary> - * Return element {@code i} elements ahead of current element. {@code i==0} - * gets current element. This is not an absolute index into {@link #data} - * since {@code p} defines the start of the real list. - * </summary> - */ - public virtual T this[int i] - { - get - { - int absIndex = _p + i; - if (absIndex >= _data.Count) - throw new ArgumentException(string.Format("queue index {0} > last index {1}", absIndex, _data.Count - 1)); - if (absIndex < 0) - throw new ArgumentException(string.Format("queue index {0} < 0", absIndex)); - - if (absIndex > Range) - Range = absIndex; - - return _data[absIndex]; - } - } - - /** <summary>Get and remove first element in queue</summary> */ - public virtual T Dequeue() - { - if (Count == 0) - throw new InvalidOperationException(); - - T o = this[0]; - _p++; - // have we hit end of buffer? - if ( _p == _data.Count ) - { - // if so, it's an opportunity to start filling at index 0 again - Clear(); // size goes to 0, but retains memory - } - return o; - } - - public virtual void Enqueue( T o ) - { - _data.Add( o ); - } - - public virtual T Peek() - { - return this[0]; - } - - public virtual void Clear() - { - _p = 0; - _data.Clear(); - } - - /** <summary>Return string of current buffer contents; non-destructive</summary> */ - public override string ToString() - { - System.Text.StringBuilder buf = new System.Text.StringBuilder(); - int n = Count; - for ( int i = 0; i < n; i++ ) - { - buf.Append( this[i] ); - if ( ( i + 1 ) < n ) - buf.Append( " " ); - } - return buf.ToString(); - } - } -} |