| /* |
| * [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 |
| { |
| using System.Collections.Generic; |
| |
| using Array = System.Array; |
| using CLSCompliant = System.CLSCompliantAttribute; |
| using ICloneable = System.ICloneable; |
| using Math = System.Math; |
| using StringBuilder = System.Text.StringBuilder; |
| |
| /** <summary> |
| * A stripped-down version of org.antlr.misc.BitSet that is just |
| * good enough to handle runtime requirements such as FOLLOW sets |
| * for automatic error recovery. |
| * </summary> |
| */ |
| [System.Serializable] |
| public sealed class BitSet : ICloneable |
| { |
| private const int BITS = 64; // number of bits / long |
| private const int LOG_BITS = 6; // 2^6 == 64 |
| |
| /** <summary> |
| * We will often need to do a mod operator (i mod nbits). Its |
| * turns out that, for powers of two, this mod operation is |
| * same as (i & (nbits-1)). Since mod is slow, we use a |
| * precomputed mod mask to do the mod instead. |
| * </summary> |
| */ |
| private const int MOD_MASK = BITS - 1; |
| |
| /** <summary>The actual data bits</summary> */ |
| ulong[] _bits; |
| |
| /** <summary>Construct a bitset of size one word (64 bits)</summary> */ |
| public BitSet() |
| : this( BITS ) |
| { |
| } |
| |
| /** <summary>Construction from a static array of longs</summary> */ |
| [CLSCompliant( false )] |
| public BitSet( ulong[] bits ) |
| { |
| _bits = bits; |
| } |
| |
| /** <summary>Construction from a list of integers</summary> */ |
| public BitSet( IEnumerable<int> items ) |
| : this() |
| { |
| foreach ( int i in items ) |
| Add( i ); |
| } |
| |
| /** <summary>Construct a bitset given the size</summary> |
| * <param name="nbits">The size of the bitset in bits</param> |
| */ |
| public BitSet( int nbits ) |
| { |
| _bits = new ulong[( ( nbits - 1 ) >> LOG_BITS ) + 1]; |
| } |
| |
| public static BitSet Of( int el ) |
| { |
| BitSet s = new BitSet( el + 1 ); |
| s.Add( el ); |
| return s; |
| } |
| |
| public static BitSet Of( int a, int b ) |
| { |
| BitSet s = new BitSet( Math.Max( a, b ) + 1 ); |
| s.Add( a ); |
| s.Add( b ); |
| return s; |
| } |
| |
| public static BitSet Of( int a, int b, int c ) |
| { |
| BitSet s = new BitSet(); |
| s.Add( a ); |
| s.Add( b ); |
| s.Add( c ); |
| return s; |
| } |
| |
| public static BitSet Of( int a, int b, int c, int d ) |
| { |
| BitSet s = new BitSet(); |
| s.Add( a ); |
| s.Add( b ); |
| s.Add( c ); |
| s.Add( d ); |
| return s; |
| } |
| |
| /** <summary>return this | a in a new set</summary> */ |
| public BitSet Or( BitSet a ) |
| { |
| if ( a == null ) |
| { |
| return this; |
| } |
| BitSet s = (BitSet)this.Clone(); |
| s.OrInPlace( a ); |
| return s; |
| } |
| |
| /** <summary>or this element into this set (grow as necessary to accommodate)</summary> */ |
| public void Add( int el ) |
| { |
| int n = WordNumber( el ); |
| if ( n >= _bits.Length ) |
| { |
| GrowToInclude( el ); |
| } |
| _bits[n] |= BitMask( el ); |
| } |
| |
| /** <summary>Grows the set to a larger number of bits.</summary> |
| * <param name="bit">element that must fit in set</param> |
| */ |
| public void GrowToInclude( int bit ) |
| { |
| int newSize = Math.Max( _bits.Length << 1, NumWordsToHold( bit ) ); |
| SetSize(newSize); |
| } |
| |
| public void OrInPlace( BitSet a ) |
| { |
| if ( a == null ) |
| { |
| return; |
| } |
| // If this is smaller than a, grow this first |
| if ( a._bits.Length > _bits.Length ) |
| { |
| SetSize( a._bits.Length ); |
| } |
| int min = Math.Min( _bits.Length, a._bits.Length ); |
| for ( int i = min - 1; i >= 0; i-- ) |
| { |
| _bits[i] |= a._bits[i]; |
| } |
| } |
| |
| /** <summary>Sets the size of a set.</summary> |
| * <param name="nwords">how many words the new set should be</param> |
| */ |
| private void SetSize( int nwords ) |
| { |
| Array.Resize(ref _bits, nwords); |
| } |
| |
| private static ulong BitMask( int bitNumber ) |
| { |
| int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS |
| return 1UL << bitPosition; |
| } |
| |
| public object Clone() |
| { |
| return new BitSet( (ulong[])_bits.Clone() ); |
| } |
| |
| public int Size() |
| { |
| int deg = 0; |
| for ( int i = _bits.Length - 1; i >= 0; i-- ) |
| { |
| ulong word = _bits[i]; |
| if ( word != 0L ) |
| { |
| for ( int bit = BITS - 1; bit >= 0; bit-- ) |
| { |
| if ( ( word & ( 1UL << bit ) ) != 0 ) |
| { |
| deg++; |
| } |
| } |
| } |
| } |
| return deg; |
| } |
| |
| public override int GetHashCode() |
| { |
| throw new System.NotImplementedException(); |
| } |
| |
| public override bool Equals( object other ) |
| { |
| if ( other == null || !( other is BitSet ) ) |
| { |
| return false; |
| } |
| |
| BitSet otherSet = (BitSet)other; |
| |
| int n = Math.Min( this._bits.Length, otherSet._bits.Length ); |
| |
| // for any bits in common, compare |
| for ( int i = 0; i < n; i++ ) |
| { |
| if ( this._bits[i] != otherSet._bits[i] ) |
| { |
| return false; |
| } |
| } |
| |
| // make sure any extra bits are off |
| |
| if ( this._bits.Length > n ) |
| { |
| for ( int i = n + 1; i < this._bits.Length; i++ ) |
| { |
| if ( this._bits[i] != 0 ) |
| { |
| return false; |
| } |
| } |
| } |
| else if ( otherSet._bits.Length > n ) |
| { |
| for ( int i = n + 1; i < otherSet._bits.Length; i++ ) |
| { |
| if ( otherSet._bits[i] != 0 ) |
| { |
| return false; |
| } |
| } |
| } |
| |
| return true; |
| } |
| |
| public bool Member( int el ) |
| { |
| if ( el < 0 ) |
| { |
| return false; |
| } |
| int n = WordNumber( el ); |
| if ( n >= _bits.Length ) |
| return false; |
| return ( _bits[n] & BitMask( el ) ) != 0; |
| } |
| |
| // remove this element from this set |
| public void Remove( int el ) |
| { |
| int n = WordNumber( el ); |
| if ( n < _bits.Length ) |
| { |
| _bits[n] &= ~BitMask( el ); |
| } |
| } |
| |
| public bool IsNil() |
| { |
| for ( int i = _bits.Length - 1; i >= 0; i-- ) |
| { |
| if ( _bits[i] != 0 ) |
| return false; |
| } |
| return true; |
| } |
| |
| private static int NumWordsToHold( int el ) |
| { |
| return ( el >> LOG_BITS ) + 1; |
| } |
| |
| public int NumBits() |
| { |
| return _bits.Length << LOG_BITS; // num words * bits per word |
| } |
| |
| /** <summary>return how much space is being used by the bits array not how many actually have member bits on.</summary> */ |
| public int LengthInLongWords() |
| { |
| return _bits.Length; |
| } |
| |
| /**Is this contained within a? */ |
| /* |
| public boolean subset(BitSet a) { |
| if (a == null || !(a instanceof BitSet)) return false; |
| return this.and(a).equals(this); |
| } |
| */ |
| |
| public int[] ToArray() |
| { |
| int[] elems = new int[Size()]; |
| int en = 0; |
| for ( int i = 0; i < ( _bits.Length << LOG_BITS ); i++ ) |
| { |
| if ( Member( i ) ) |
| { |
| elems[en++] = i; |
| } |
| } |
| return elems; |
| } |
| |
| private static int WordNumber( int bit ) |
| { |
| return bit >> LOG_BITS; // bit / BITS |
| } |
| |
| public override string ToString() |
| { |
| return ToString( null ); |
| } |
| |
| public string ToString( string[] tokenNames ) |
| { |
| StringBuilder buf = new StringBuilder(); |
| string separator = ","; |
| bool havePrintedAnElement = false; |
| buf.Append( '{' ); |
| |
| for ( int i = 0; i < ( _bits.Length << LOG_BITS ); i++ ) |
| { |
| if ( Member( i ) ) |
| { |
| if ( i > 0 && havePrintedAnElement ) |
| { |
| buf.Append( separator ); |
| } |
| if ( tokenNames != null ) |
| { |
| buf.Append( tokenNames[i] ); |
| } |
| else |
| { |
| buf.Append( i ); |
| } |
| havePrintedAnElement = true; |
| } |
| } |
| buf.Append( '}' ); |
| return buf.ToString(); |
| } |
| } |
| } |