Sources/Antlr3.Runtime/BitSet.cs

/*
 * [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();
        }
    }
}