Antlr3.Runtime/Antlr.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> */
        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();
        }
    }
}