tool/src/main/java/org/antlr/misc/BitSet.java - platform/external/antlr - Git at Google

 /*
  * [The "BSD license"]
  *  Copyright (c) 2010 Terence Parr
  *  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.
  */
 package org.antlr.misc;

 import org.antlr.analysis.Label;
 import org.antlr.tool.Grammar;

 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;

 /**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
  */
 public class BitSet implements IntSet, Cloneable {
     protected final static int BITS = 64;    // number of bits / long
     protected final static 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 final static int MOD_MASK = BITS - 1;

     /** The actual data bits */
     protected long bits[];

     /** Construct a bitset of size one word (64 bits) */
     public BitSet() {
         this(BITS);
     }

     /** Construction from a static array of longs */
     public BitSet(long[] bits_) {
         bits = bits_;
     }

     /** Construct a bitset given the size
      * @param nbits The size of the bitset in bits
      */
     public BitSet(int nbits) {
         bits = new long[((nbits - 1) >> LOG_BITS) + 1];
     }

     /** or this element into this set (grow as necessary to accommodate) */
     public void add(int el) {
         //System.out.println("add("+el+")");
         int n = wordNumber(el);
         //System.out.println("word number is "+n);
         //System.out.println("bits.length "+bits.length);
         if (n >= bits.length) {
             growToInclude(el);
         }
         bits[n] |= bitMask(el);
     }

     public void addAll(IntSet set) {
         if ( set instanceof BitSet ) {
             this.orInPlace((BitSet)set);
         }
 		else if ( set instanceof IntervalSet ) {
 			IntervalSet other = (IntervalSet)set;
 			// walk set and add each interval
 			for (Iterator iter = other.intervals.iterator(); iter.hasNext();) {
 				Interval I = (Interval) iter.next();
 				this.orInPlace(BitSet.range(I.a,I.b));
 			}
 		}
 		else {
 			throw new IllegalArgumentException("can't add "+
 											   set.getClass().getName()+
 											   " to BitSet");
 		}
     }

 	public void addAll(int[] elements) {
 		if ( elements==null ) {
 			return;
 		}
 		for (int i = 0; i < elements.length; i++) {
 			int e = elements[i];
 			add(e);
 		}
 	}

 	public void addAll(Iterable elements) {
 		if ( elements==null ) {
 			return;
 		}
 		Iterator it = elements.iterator();
 		while (it.hasNext()) {
 			Object o = (Object) it.next();
 			if ( !(o instanceof Integer) ) {
 				throw new IllegalArgumentException();
 			}
 			Integer eI = (Integer)o;
 			add(eI.intValue());
 		}
 		/*
 		int n = elements.size();
 		for (int i = 0; i < n; i++) {
 			Object o = elements.get(i);
 			if ( !(o instanceof Integer) ) {
 				throw new IllegalArgumentException();
 			}
 			Integer eI = (Integer)o;
 			add(eI.intValue());
 		}
 		 */
 	}

     public IntSet and(IntSet a) {
         BitSet s = (BitSet)this.clone();
         s.andInPlace((BitSet)a);
         return s;
     }

     public void andInPlace(BitSet a) {
         int min = Math.min(bits.length, a.bits.length);
         for (int i = min - 1; i >= 0; i--) {
             bits[i] &= a.bits[i];
         }
         // clear all bits in this not present in a (if this bigger than a).
         for (int i = min; i < bits.length; i++) {
             bits[i] = 0;
         }
     }

     private final static long bitMask(int bitNumber) {
         int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
         return 1L << bitPosition;
     }

     public void clear() {
         for (int i = bits.length - 1; i >= 0; i--) {
             bits[i] = 0;
         }
     }

     public void clear(int el) {
         int n = wordNumber(el);
         if (n >= bits.length) {	// grow as necessary to accommodate
             growToInclude(el);
         }
         bits[n] &= ~bitMask(el);
     }

     public Object clone() {
         BitSet s;
         try {
             s = (BitSet)super.clone();
             s.bits = new long[bits.length];
             System.arraycopy(bits, 0, s.bits, 0, bits.length);
         }
         catch (CloneNotSupportedException e) {
             throw new InternalError();
         }
         return s;
     }

     public int size() {
         int deg = 0;
         for (int i = bits.length - 1; i >= 0; i--) {
             long word = bits[i];
             if (word != 0L) {
                 for (int bit = BITS - 1; bit >= 0; bit--) {
                     if ((word & (1L << bit)) != 0) {
                         deg++;
                     }
                 }
             }
         }
         return deg;
     }

     public boolean equals(Object other) {
         if ( other == null || !(other instanceof 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;
     }

     /**
      * Grows the set to a larger number of bits.
      * @param bit element that must fit in set
      */
     public void growToInclude(int bit) {
         int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
         long newbits[] = new long[newSize];
         System.arraycopy(bits, 0, newbits, 0, bits.length);
         bits = newbits;
     }

     public boolean member(int el) {
         int n = wordNumber(el);
         if (n >= bits.length) return false;
         return (bits[n] & bitMask(el)) != 0;
     }

     /** Get the first element you find and return it.  Return Label.INVALID
      *  otherwise.
      */
     public int getSingleElement() {
         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
             if (member(i)) {
                 return i;
             }
         }
         return Label.INVALID;
     }

     public boolean isNil() {
         for (int i = bits.length - 1; i >= 0; i--) {
             if (bits[i] != 0) return false;
         }
         return true;
     }

     public IntSet complement() {
         BitSet s = (BitSet)this.clone();
         s.notInPlace();
         return s;
     }

     public IntSet complement(IntSet set) {
 		if ( set==null ) {
 			return this.complement();
 		}
         return set.subtract(this);
     }

     public void notInPlace() {
         for (int i = bits.length - 1; i >= 0; i--) {
             bits[i] = ~bits[i];
         }
     }

     /** complement bits in the range 0..maxBit. */
     public void notInPlace(int maxBit) {
         notInPlace(0, maxBit);
     }

     /** complement bits in the range minBit..maxBit.*/
     public 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);
             bits[n] ^= bitMask(i);
         }
     }

     private final 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;
     }

     public static BitSet of(Collection elements) {
         BitSet s = new BitSet();
         Iterator iter = elements.iterator();
         while (iter.hasNext()) {
             Integer el = (Integer) iter.next();
             s.add(el.intValue());
         }
         return s;
     }

 	public static BitSet of(IntSet set) {
 		if ( set==null ) {
 			return null;
 		}

 		if ( set instanceof BitSet ) {
 			return (BitSet)set;
 		}
 		if ( set instanceof IntervalSet ) {
 			BitSet s = new BitSet();
 			s.addAll(set);
 			return s;
 		}
 		throw new IllegalArgumentException("can't create BitSet from "+set.getClass().getName());
 	}

     public static BitSet of(Map elements) {
         return BitSet.of(elements.keySet());
     }

 	public static BitSet range(int a, int b) {
 		BitSet s = new BitSet(b + 1);
 		for (int i = a; i <= b; i++) {
 			int n = wordNumber(i);
 			s.bits[n] |= bitMask(i);
 		}
 		return s;
 	}

     /** return this | a in a new set */
     public IntSet or(IntSet a) {
 		if ( a==null ) {
 			return this;
 		}
         BitSet s = (BitSet)this.clone();
         s.orInPlace((BitSet)a);
         return s;
     }

     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];
         }
     }

     // remove this element from this set
     public void remove(int el) {
         int n = wordNumber(el);
         if (n >= bits.length) {
             growToInclude(el);
         }
         bits[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 = Math.min(nwords, bits.length);
         System.arraycopy(bits, 0, newbits, 0, n);
         bits = newbits;
     }

     public int numBits() {
         return bits.length << LOG_BITS; // num words * bits per word
     }

     /** return how much space is being used by the bits array not
      *  how many actually have member bits on.
      */
     public int lengthInLongWords() {
         return bits.length;
     }

     /**Is this contained within a? */
     public boolean subset(BitSet a) {
         if (a == null) 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 void subtractInPlace(BitSet a) {
         if (a == null) return;
         // for all words of 'a', turn off corresponding bits of 'this'
         for (int i = 0; i < bits.length && i < a.bits.length; i++) {
             bits[i] &= ~a.bits[i];
         }
     }

     public IntSet subtract(IntSet a) {
         if (a == null || !(a instanceof BitSet)) return null;

         BitSet s = (BitSet)this.clone();
         s.subtractInPlace((BitSet)a);
         return s;
     }

 	public List toList() {
 		throw new NoSuchMethodError("BitSet.toList() unimplemented");
 	}

     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;
     }

     public long[] toPackedArray() {
         return bits;
     }

     public String toString() {
         return toString(null);
     }

     /** 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 String toString(Grammar g) {
         StringBuffer buf = new StringBuffer();
         String separator = ",";
 		boolean 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 ( g!=null ) {
                     buf.append(g.getTokenDisplayName(i));
                 }
                 else {
                     buf.append(i);
                 }
 				havePrintedAnElement = true;
             }
         }
 		buf.append('}');
         return buf.toString();
     }

     /**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 String toString(String separator, List vocabulary) {
         if (vocabulary == null) {
             return toString(null);
         }
         String str = "";
         for (int i = 0; i < (bits.length << LOG_BITS); i++) {
             if (member(i)) {
                 if (str.length() > 0) {
                     str += separator;
                 }
                 if (i >= vocabulary.size()) {
                     str += "'" + (char)i + "'";
                 }
                 else if (vocabulary.get(i) == null) {
                     str += "'" + (char)i + "'";
                 }
                 else {
                     str += (String)vocabulary.get(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 String toStringOfHalfWords() {
         StringBuffer s = new StringBuffer();
         for (int i = 0; i < bits.length; i++) {
             if (i != 0) s.append(", ");
             long tmp = bits[i];
             tmp &= 0xFFFFFFFFL;
             s.append(tmp);
 			s.append("UL");
             s.append(", ");
             tmp = bits[i] >>> 32;
             tmp &= 0xFFFFFFFFL;
 			s.append(tmp);
 			s.append("UL");
         }
 		return s.toString();
     }

     /**
      * 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 String toStringOfWords() {
 		StringBuffer s = new StringBuffer();
         for (int i = 0; i < bits.length; i++) {
             if (i != 0) s.append(", ");
             s.append(bits[i]);
 			s.append("L");
         }
         return s.toString();
     }

     public String toStringWithRanges() {
         return toString();
     }

     private final static int wordNumber(int bit) {
         return bit >> LOG_BITS; // bit / BITS
     }
 }
	/*
	* [The "BSD license"]
	* Copyright (c) 2010 Terence Parr
	* 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.
	*/
	package org.antlr.misc;

	import org.antlr.analysis.Label;
	import org.antlr.tool.Grammar;

	import java.util.Collection;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;

	/**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
	*/
	public class BitSet implements IntSet, Cloneable {
	protected final static int BITS = 64; // number of bits / long
	protected final static 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 final static int MOD_MASK = BITS - 1;

	/** The actual data bits */
	protected long bits[];

	/** Construct a bitset of size one word (64 bits) */
	public BitSet() {
	this(BITS);
	}

	/** Construction from a static array of longs */
	public BitSet(long[] bits_) {
	bits = bits_;
	}

	/** Construct a bitset given the size
	* @param nbits The size of the bitset in bits
	*/
	public BitSet(int nbits) {
	bits = new long[((nbits - 1) >> LOG_BITS) + 1];
	}

	/** or this element into this set (grow as necessary to accommodate) */
	public void add(int el) {
	//System.out.println("add("+el+")");
	int n = wordNumber(el);
	//System.out.println("word number is "+n);
	//System.out.println("bits.length "+bits.length);
	if (n >= bits.length) {
	growToInclude(el);
	}
	bits[n] \|= bitMask(el);
	}

	public void addAll(IntSet set) {
	if ( set instanceof BitSet ) {
	this.orInPlace((BitSet)set);
	}
	else if ( set instanceof IntervalSet ) {
	IntervalSet other = (IntervalSet)set;
	// walk set and add each interval
	for (Iterator iter = other.intervals.iterator(); iter.hasNext();) {
	Interval I = (Interval) iter.next();
	this.orInPlace(BitSet.range(I.a,I.b));
	}
	}
	else {
	throw new IllegalArgumentException("can't add "+
	set.getClass().getName()+
	" to BitSet");
	}
	}

	public void addAll(int[] elements) {
	if ( elements==null ) {
	return;
	}
	for (int i = 0; i < elements.length; i++) {
	int e = elements[i];
	add(e);
	}
	}

	public void addAll(Iterable elements) {
	if ( elements==null ) {
	return;
	}
	Iterator it = elements.iterator();
	while (it.hasNext()) {
	Object o = (Object) it.next();
	if ( !(o instanceof Integer) ) {
	throw new IllegalArgumentException();
	}
	Integer eI = (Integer)o;
	add(eI.intValue());
	}
	/*
	int n = elements.size();
	for (int i = 0; i < n; i++) {
	Object o = elements.get(i);
	if ( !(o instanceof Integer) ) {
	throw new IllegalArgumentException();
	}
	Integer eI = (Integer)o;
	add(eI.intValue());
	}
	*/
	}

	public IntSet and(IntSet a) {
	BitSet s = (BitSet)this.clone();
	s.andInPlace((BitSet)a);
	return s;
	}

	public void andInPlace(BitSet a) {
	int min = Math.min(bits.length, a.bits.length);
	for (int i = min - 1; i >= 0; i--) {
	bits[i] &= a.bits[i];
	}
	// clear all bits in this not present in a (if this bigger than a).
	for (int i = min; i < bits.length; i++) {
	bits[i] = 0;
	}
	}

	private final static long bitMask(int bitNumber) {
	int bitPosition = bitNumber & MOD_MASK; // bitNumber mod BITS
	return 1L << bitPosition;
	}

	public void clear() {
	for (int i = bits.length - 1; i >= 0; i--) {
	bits[i] = 0;
	}
	}

	public void clear(int el) {
	int n = wordNumber(el);
	if (n >= bits.length) { // grow as necessary to accommodate
	growToInclude(el);
	}
	bits[n] &= ~bitMask(el);
	}

	public Object clone() {
	BitSet s;
	try {
	s = (BitSet)super.clone();
	s.bits = new long[bits.length];
	System.arraycopy(bits, 0, s.bits, 0, bits.length);
	}
	catch (CloneNotSupportedException e) {
	throw new InternalError();
	}
	return s;
	}

	public int size() {
	int deg = 0;
	for (int i = bits.length - 1; i >= 0; i--) {
	long word = bits[i];
	if (word != 0L) {
	for (int bit = BITS - 1; bit >= 0; bit--) {
	if ((word & (1L << bit)) != 0) {
	deg++;
	}
	}
	}
	}
	return deg;
	}

	public boolean equals(Object other) {
	if ( other == null \|\| !(other instanceof 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;
	}

	/**
	* Grows the set to a larger number of bits.
	* @param bit element that must fit in set
	*/
	public void growToInclude(int bit) {
	int newSize = Math.max(bits.length << 1, numWordsToHold(bit));
	long newbits[] = new long[newSize];
	System.arraycopy(bits, 0, newbits, 0, bits.length);
	bits = newbits;
	}

	public boolean member(int el) {
	int n = wordNumber(el);
	if (n >= bits.length) return false;
	return (bits[n] & bitMask(el)) != 0;
	}

	/** Get the first element you find and return it. Return Label.INVALID
	* otherwise.
	*/
	public int getSingleElement() {
	for (int i = 0; i < (bits.length << LOG_BITS); i++) {
	if (member(i)) {
	return i;
	}
	}
	return Label.INVALID;
	}

	public boolean isNil() {
	for (int i = bits.length - 1; i >= 0; i--) {
	if (bits[i] != 0) return false;
	}
	return true;
	}

	public IntSet complement() {
	BitSet s = (BitSet)this.clone();
	s.notInPlace();
	return s;
	}

	public IntSet complement(IntSet set) {
	if ( set==null ) {
	return this.complement();
	}
	return set.subtract(this);
	}

	public void notInPlace() {
	for (int i = bits.length - 1; i >= 0; i--) {
	bits[i] = ~bits[i];
	}
	}

	/** complement bits in the range 0..maxBit. */
	public void notInPlace(int maxBit) {
	notInPlace(0, maxBit);
	}

	/** complement bits in the range minBit..maxBit.*/
	public 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);
	bits[n] ^= bitMask(i);
	}
	}

	private final 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;
	}

	public static BitSet of(Collection elements) {
	BitSet s = new BitSet();
	Iterator iter = elements.iterator();
	while (iter.hasNext()) {
	Integer el = (Integer) iter.next();
	s.add(el.intValue());
	}
	return s;
	}

	public static BitSet of(IntSet set) {
	if ( set==null ) {
	return null;
	}

	if ( set instanceof BitSet ) {
	return (BitSet)set;
	}
	if ( set instanceof IntervalSet ) {
	BitSet s = new BitSet();
	s.addAll(set);
	return s;
	}
	throw new IllegalArgumentException("can't create BitSet from "+set.getClass().getName());
	}

	public static BitSet of(Map elements) {
	return BitSet.of(elements.keySet());
	}

	public static BitSet range(int a, int b) {
	BitSet s = new BitSet(b + 1);
	for (int i = a; i <= b; i++) {
	int n = wordNumber(i);
	s.bits[n] \|= bitMask(i);
	}
	return s;
	}

	/** return this \| a in a new set */
	public IntSet or(IntSet a) {
	if ( a==null ) {
	return this;
	}
	BitSet s = (BitSet)this.clone();
	s.orInPlace((BitSet)a);
	return s;
	}

	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];
	}
	}

	// remove this element from this set
	public void remove(int el) {
	int n = wordNumber(el);
	if (n >= bits.length) {
	growToInclude(el);
	}
	bits[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 = Math.min(nwords, bits.length);
	System.arraycopy(bits, 0, newbits, 0, n);
	bits = newbits;
	}

	public int numBits() {
	return bits.length << LOG_BITS; // num words * bits per word
	}

	/** return how much space is being used by the bits array not
	* how many actually have member bits on.
	*/
	public int lengthInLongWords() {
	return bits.length;
	}

	/*Is this contained within a? /
	public boolean subset(BitSet a) {
	if (a == null) 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 void subtractInPlace(BitSet a) {
	if (a == null) return;
	// for all words of 'a', turn off corresponding bits of 'this'
	for (int i = 0; i < bits.length && i < a.bits.length; i++) {
	bits[i] &= ~a.bits[i];
	}
	}

	public IntSet subtract(IntSet a) {
	if (a == null \|\| !(a instanceof BitSet)) return null;

	BitSet s = (BitSet)this.clone();
	s.subtractInPlace((BitSet)a);
	return s;
	}

	public List toList() {
	throw new NoSuchMethodError("BitSet.toList() unimplemented");
	}

	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;
	}

	public long[] toPackedArray() {
	return bits;
	}

	public String toString() {
	return toString(null);
	}

	/** 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 String toString(Grammar g) {
	StringBuffer buf = new StringBuffer();
	String separator = ",";
	boolean 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 ( g!=null ) {
	buf.append(g.getTokenDisplayName(i));
	}
	else {
	buf.append(i);
	}
	havePrintedAnElement = true;
	}
	}
	buf.append('}');
	return buf.toString();
	}

	/**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 String toString(String separator, List vocabulary) {
	if (vocabulary == null) {
	return toString(null);
	}
	String str = "";
	for (int i = 0; i < (bits.length << LOG_BITS); i++) {
	if (member(i)) {
	if (str.length() > 0) {
	str += separator;
	}
	if (i >= vocabulary.size()) {
	str += "'" + (char)i + "'";
	}
	else if (vocabulary.get(i) == null) {
	str += "'" + (char)i + "'";
	}
	else {
	str += (String)vocabulary.get(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 String toStringOfHalfWords() {
	StringBuffer s = new StringBuffer();
	for (int i = 0; i < bits.length; i++) {
	if (i != 0) s.append(", ");
	long tmp = bits[i];
	tmp &= 0xFFFFFFFFL;
	s.append(tmp);
	s.append("UL");
	s.append(", ");
	tmp = bits[i] >>> 32;
	tmp &= 0xFFFFFFFFL;
	s.append(tmp);
	s.append("UL");
	}
	return s.toString();
	}

	/**
	* 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 String toStringOfWords() {
	StringBuffer s = new StringBuffer();
	for (int i = 0; i < bits.length; i++) {
	if (i != 0) s.append(", ");
	s.append(bits[i]);
	s.append("L");
	}
	return s.toString();
	}

	public String toStringWithRanges() {
	return toString();
	}

	private final static int wordNumber(int bit) {
	return bit >> LOG_BITS; // bit / BITS
	}
	}