using System;
using ArrayListSystem.Collections.ArrayList;
//using CharFormatter = antlr.CharFormatter;
namespace Spring.Expressions.Parser.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
}
}
}
|