source: trunk/yao/share/antlr-2.7.7/lib/csharp/antlr.runtime/antlr.collections.impl/BitSet.cs @ 1

using System;
using ArrayList                                 = System.Collections.ArrayList;

//using CharFormatter                           = antlr.CharFormatter;

namespace antlr.collections.impl
{
        /*ANTLR Translator Generator
        * Project led by Terence Parr at http://www.jGuru.com
        * Software rights: http://www.antlr.org/license.html
        *
        * $Id:$
        */

        //
        // ANTLR C# Code Generator by Micheal Jordan
        //                            Kunle Odutola       : kunle UNDERSCORE odutola AT hotmail DOT com
        //                            Anthony Oguntimehin
        //
        // With many thanks to Eric V. Smith from the ANTLR list.
        //
        
        /*A BitSet to replace java.util.BitSet.
        * Primary differences are that most set operators return new sets
        * as opposed to oring and anding "in place".  Further, a number of
        * operations were added.  I cannot contain a BitSet because there
        * is no way to access the internal bits (which I need for speed)
        * and, because it is final, I cannot subclass to add functionality.
        * Consider defining set degree.  Without access to the bits, I must
        * call a method n times to test the ith bit...ack!
        *
        * Also seems like or() from util is wrong when size of incoming set is bigger
        * than this.bits.length.
        *
        * @author Terence Parr
        * @author <br><a href="mailto:pete@yamuna.demon.co.uk">Pete Wells</a>
        */

        public class BitSet : ICloneable
        {
                protected internal const int BITS = 64; // number of bits / long
                protected internal const int NIBBLE = 4;
                protected internal const int LOG_BITS = 6; // 2^6 == 64
                
                /*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.
                */
                protected internal static readonly int MOD_MASK = BITS - 1;
                
                /*The actual data bits */
                protected internal long[] dataBits;
                
                /*Construct a bitset of size one word (64 bits) */
                public BitSet() : this(BITS)
                {
                }
                
                /*Construction from a static array of longs */
                public BitSet(long[] bits_)
                {
                        dataBits = bits_;
                }
                
                /*Construct a bitset given the size
                * @param nbits The size of the bitset in bits
                */
                public BitSet(int nbits)
                {
                        dataBits = new long[((nbits - 1) >> LOG_BITS) + 1];
                }
                
                /*or this element into this set (grow as necessary to accommodate) */
                public virtual void  add(int el)
                {
                        int n = wordNumber(el);
                        if (n >= dataBits.Length)
                        {
                                growToInclude(el);
                        }
                        dataBits[n] |= bitMask(el);
                }
                
                public virtual BitSet and(BitSet a)
                {
                        BitSet s = (BitSet) this.Clone();
                        s.andInPlace(a);
                        return s;
                }
                
                public virtual void  andInPlace(BitSet a)
                {
                        int min = (int) (Math.Min(dataBits.Length, a.dataBits.Length));
                         for (int i = min - 1; i >= 0; i--)
                        {
                                dataBits[i] &= a.dataBits[i];
                        }
                        // clear all bits in this not present in a (if this bigger than a).
                         for (int i = min; i < dataBits.Length; i++)
                        {
                                dataBits[i] = 0;
                        }
                }
                
                private static long bitMask(int bitNumber)
                {
                        int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
                        return 1L << bitPosition;
                }
                
                public virtual void  clear()
                {
                         for (int i = dataBits.Length - 1; i >= 0; i--)
                        {
                                dataBits[i] = 0;
                        }
                }
                
                public virtual void  clear(int el)
                {
                        int n = wordNumber(el);
                        if (n >= dataBits.Length)
                        {
                                // grow as necessary to accommodate
                                growToInclude(el);
                        }
                        dataBits[n] &= ~ bitMask(el);
                }
                
                public virtual object Clone()
                {
                        BitSet s;
                        try
                        {
                                s = new BitSet();
                                s.dataBits = new long[dataBits.Length];
                                Array.Copy(dataBits, 0, s.dataBits, 0, dataBits.Length);
                        }
                        catch //(System.Exception e)
                        {
                                throw new System.ApplicationException();
                        }
                        return s;
                }
                
                public virtual int degree()
                {
                        int deg = 0;
                         for (int i = dataBits.Length - 1; i >= 0; i--)
                        {
                                long word = dataBits[i];
                                if (word != 0L)
                                {
                                         for (int bit = BITS - 1; bit >= 0; bit--)
                                        {
                                                if ((word & (1L << bit)) != 0)
                                                {
                                                        deg++;
                                                }
                                        }
                                }
                        }
                        return deg;
                }
                
                override public int GetHashCode()
                {
                        return dataBits.GetHashCode();
                }

                /*code "inherited" from java.util.BitSet */
                override public bool Equals(object obj)
                {
                        if ((obj != null) && (obj is BitSet))
                        {
                                BitSet bset = (BitSet) obj;
                                
                                int n = (int) (System.Math.Min(dataBits.Length, bset.dataBits.Length));
                                 for (int i = n; i-- > 0; )
                                {
                                        if (dataBits[i] != bset.dataBits[i])
                                        {
                                                return false;
                                        }
                                }
                                if (dataBits.Length > n)
                                {
                                         for (int i = (int) (dataBits.Length); i-- > n; )
                                        {
                                                if (dataBits[i] != 0)
                                                {
                                                        return false;
                                                }
                                        }
                                }
                                else if (bset.dataBits.Length > n)
                                {
                                         for (int i = (int) (bset.dataBits.Length); i-- > n; )
                                        {
                                                if (bset.dataBits[i] != 0)
                                                {
                                                        return false;
                                                }
                                        }
                                }
                                return true;
                        }
                        return false;
                }
                
                /*
                * Grows the set to a larger number of bits.
                * @param bit element that must fit in set
                */
                public virtual void  growToInclude(int bit)
                {
                        int newSize = (int) (System.Math.Max(dataBits.Length << 1, numWordsToHold(bit)));
                        long[] newbits = new long[newSize];
                        Array.Copy(dataBits, 0, newbits, 0, dataBits.Length);
                        dataBits = newbits;
                }
                
                public virtual bool member(int el)
                {
                        int n = wordNumber(el);
                        if (n >= dataBits.Length)
                                return false;
                        return (dataBits[n] & bitMask(el)) != 0;
                }
                
                public virtual bool nil()
                {
                         for (int i = dataBits.Length - 1; i >= 0; i--)
                        {
                                if (dataBits[i] != 0)
                                        return false;
                        }
                        return true;
                }
                
                public virtual BitSet not()
                {
                        BitSet s = (BitSet) this.Clone();
                        s.notInPlace();
                        return s;
                }
                
                public virtual void  notInPlace()
                {
                         for (int i = dataBits.Length - 1; i >= 0; i--)
                        {
                                dataBits[i] = ~ dataBits[i];
                        }
                }
                
                /*complement bits in the range 0..maxBit. */
                public virtual void  notInPlace(int maxBit)
                {
                        notInPlace(0, maxBit);
                }
                
                /*complement bits in the range minBit..maxBit.*/
                public virtual void  notInPlace(int minBit, int maxBit)
                {
                        // make sure that we have room for maxBit
                        growToInclude(maxBit);
                         for (int i = minBit; i <= maxBit; i++)
                        {
                                int n = wordNumber(i);
                                dataBits[n] ^= bitMask(i);
                        }
                }
                
                private int numWordsToHold(int el)
                {
                        return (el >> LOG_BITS) + 1;
                }
                
                public static BitSet of(int el)
                {
                        BitSet s = new BitSet(el + 1);
                        s.add(el);
                        return s;
                }
                
                /*return this | a in a new set */
                public virtual BitSet or(BitSet a)
                {
                        BitSet s = (BitSet) this.Clone();
                        s.orInPlace(a);
                        return s;
                }
                
                public virtual void  orInPlace(BitSet a)
                {
                        // If this is smaller than a, grow this first
                        if (a.dataBits.Length > dataBits.Length)
                        {
                                setSize((int) (a.dataBits.Length));
                        }
                        int min = (int) (System.Math.Min(dataBits.Length, a.dataBits.Length));
                         for (int i = min - 1; i >= 0; i--)
                        {
                                dataBits[i] |= a.dataBits[i];
                        }
                }
                
                // remove this element from this set
                public virtual void  remove(int el)
                {
                        int n = wordNumber(el);
                        if (n >= dataBits.Length)
                        {
                                growToInclude(el);
                        }
                        dataBits[n] &= ~ bitMask(el);
                }
                
                /*
                * Sets the size of a set.
                * @param nwords how many words the new set should be
                */
                private void  setSize(int nwords)
                {
                        long[] newbits = new long[nwords];
                        int n = (int) (System.Math.Min(nwords, dataBits.Length));
                        Array.Copy(dataBits, 0, newbits, 0, n);
                        dataBits = newbits;
                }
                
                public virtual int size()
                {
                        return dataBits.Length << LOG_BITS; // num words * bits per word
                }
                
                /*return how much space is being used by the dataBits array not
                *  how many actually have member bits on.
                */
                public virtual int lengthInLongWords()
                {
                        return dataBits.Length;
                }
                
                /*Is this contained within a? */
                public virtual bool subset(BitSet a)
                {
                        if (a == null) //(a == null || !(a is BitSet))
                                return false;
                        return this.and(a).Equals(this);
                }
                
                /*Subtract the elements of 'a' from 'this' in-place.
                * Basically, just turn off all bits of 'this' that are in 'a'.
                */
                public virtual void  subtractInPlace(BitSet a)
                {
                        if (a == null)
                                return ;
                        // for all words of 'a', turn off corresponding bits of 'this'
                         for (int i = 0; i < dataBits.Length && i < a.dataBits.Length; i++)
                        {
                                dataBits[i] &= ~ a.dataBits[i];
                        }
                }
                
                public virtual int[] toArray()
                {
                        int[] elems = new int[degree()];
                        int en = 0;
                         for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
                        {
                                if (member(i))
                                {
                                        elems[en++] = i;
                                }
                        }
                        return elems;
                }
                
                public virtual long[] toPackedArray()
                {
                        return dataBits;
                }
                
                override public string ToString()
                {
                        return ToString(",");
                }
                
                /*Transform a bit set into a string by formatting each element as an integer
                * @separator The string to put in between elements
                * @return A commma-separated list of values
                */
                public virtual string ToString(string separator)
                {
                        string str = "";
                         for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
                        {
                                if (member(i))
                                {
                                        if (str.Length > 0)
                                        {
                                                str += separator;
                                        }
                                        str = str + i;
                                }
                        }
                        return str;
                }
                
                /*Create a string representation where instead of integer elements, the
                * ith element of vocabulary is displayed instead.  Vocabulary is a Vector
                * of Strings.
                * @separator The string to put in between elements
                * @return A commma-separated list of character constants.
                */
                public virtual string ToString(string separator, ArrayList vocabulary)
                {
                        if (vocabulary == null)
                        {
                                return ToString(separator);
                        }
                        string str = "";
                         for (int i = 0; i < (dataBits.Length << LOG_BITS); i++)
                        {
                                if (member(i))
                                {
                                        if (str.Length > 0)
                                        {
                                                str += separator;
                                        }
                                        if (i >= vocabulary.Count)
                                        {
                                                str += "<bad element " + i + ">";
                                        }
                                        else if (vocabulary[i] == null)
                                        {
                                                str += "<" + i + ">";
                                        }
                                        else
                                        {
                                                str += (string) vocabulary[i];
                                        }
                                }
                        }
                        return str;
                }
                
                /*
                * Dump a comma-separated list of the words making up the bit set.
                * Split each 64 bit number into two more manageable 32 bit numbers.
                * This generates a comma-separated list of C++-like unsigned long constants.
                */
                public virtual string toStringOfHalfWords()
                {
                        string s = new string("".ToCharArray());
                         for (int i = 0; i < dataBits.Length; i++)
                        {
                                if (i != 0)
                                        s += ", ";
                                long tmp = dataBits[i];
                                tmp &= 0xFFFFFFFFL;
                                s += (tmp + "UL");
                                s += ", ";
                                tmp = SupportClass.URShift(dataBits[i], 32);
                                tmp &= 0xFFFFFFFFL;
                                s += (tmp + "UL");
                        }
                        return s;
                }
                
                /*
                * Dump a comma-separated list of the words making up the bit set.
                * This generates a comma-separated list of Java-like long int constants.
                */
                public virtual string toStringOfWords()
                {
                        string s = new string("".ToCharArray());
                         for (int i = 0; i < dataBits.Length; i++)
                        {
                                if (i != 0)
                                        s += ", ";
                                s += (dataBits[i] + "L");
                        }
                        return s;
                }
                
                /*Print out the bit set but collapse char ranges. */
/*              public virtual string toStringWithRanges(string separator, CharFormatter formatter)
                {
                        string str = "";
                        int[] elems = this.toArray();
                        if (elems.Length == 0)
                        {
                                return "";
                        }
                        // look for ranges
                        int i = 0;
                        while (i < elems.Length)
                        {
                                int lastInRange;
                                lastInRange = 0;
                                 for (int j = i + 1; j < elems.Length; j++)
                                {
                                        if (elems[j] != elems[j - 1] + 1)
                                        {
                                                break;
                                        }
                                        lastInRange = j;
                                }
                                // found a range
                                if (str.Length > 0)
                                {
                                        str += separator;
                                }
                                if (lastInRange - i >= 2)
                                {
                                        str += formatter.literalChar(elems[i]);
                                        str += "..";
                                        str += formatter.literalChar(elems[lastInRange]);
                                        i = lastInRange; // skip past end of range for next range
                                }
                                else
                                {
                                        // no range, just print current char and move on
                                        str += formatter.literalChar(elems[i]);
                                }
                                i++;
                        }
                        return str;
                }
*/              
                private static int wordNumber(int bit)
                {
                        return bit >> LOG_BITS; // bit / BITS
                }
        }
}