public SparseBitSet() 
{
         
    bits = new long[4];
    offs = new int [4];
    size = 0;
}

Creates an empty set.

 public SparseBitSet(int nbits) 
{
    this();
}

Creates an empty set with the specified size.

Parameters:

nbits - the size of the set

 public SparseBitSet(SparseBitSet set) 
{
    bits = new long[set.size];
    offs = new int [set.size];
    size = 0;
}

Creates an empty set with the same size as the given set.

 public  void and(SparseBitSet set) 
{
    binop(this, set, AND);
}

Logically ANDs this bit set with the specified set of bits.

 public  void clear(int bit) 
{
    int bnum = bit  > > LG_BITS;
    int idx  = bsearch(bnum);
    if (idx  >= size || offs[idx]!=bnum)
	    new_block(idx, bnum);
    bits[idx] &= ~(1L < <  (bit & BITS_M1) );
}

Clears a bit.

 public  void clearAll() 
{
    size = 0;
}

Clears all bits.

 public Object clone() 
{
    try { 
	    SparseBitSet set = (SparseBitSet)super.clone();
	    set.bits = (long[]) bits.clone();
	    set.offs = (int []) offs.clone();
	    return set;
    } catch (CloneNotSupportedException e) {
	    // this shouldn't happen, since we are Cloneable
	    throw new InternalError();
    }
}

Clones the SparseBitSet.

 public Enumeration elements() 
{
    return new Enumeration() {
        int idx=-1, bit=BITS;
        { advance(); }
        public boolean hasMoreElements() {
          return (idx< size);
        }
        public Object nextElement() {
          int r = bit + (offs[idx] < <  LG_BITS);
          advance();
          return new Integer(r);
        }
        private void advance() {
          while (idx< size) {
            while (++bit< BITS)
              if (0!=(bits[idx] & (1L< < bit)))
                return;
            idx++; bit=-1;
          }
        }
      };
}

Return an Enumeration of Integers which represent set bit indices in this SparseBitSet.

 public boolean equals(Object obj) 
{
    if ((obj != null) && (obj instanceof SparseBitSet))
	    return equals(this, (SparseBitSet)obj); 
    return false;
}

Compares this object against the specified object.

 public static boolean equals(SparseBitSet a,
    SparseBitSet b) 
{
    for (int i=0, j=0; i< a.size || j< b.size; ) {
	    if (i< a.size && (j >=b.size || a.offs[i] <  b.offs[j])) {
        if (a.bits[i++]!=0) return false;
	    } else if (j< b.size && (i >=a.size || a.offs[i]  > b.offs[j])) {
        if (b.bits[j++]!=0) return false;
	    } else { // equal keys
        if (a.bits[i++]!=b.bits[j++]) return false;
	    }
    }
    return true;
}

Compares two SparseBitSets for equality.

 public boolean get(int bit) 
{
    int bnum = bit  > > LG_BITS;
    int idx  = bsearch(bnum);
    if (idx  >= size || offs[idx]!=bnum)
	    return false;
    return 0 != ( bits[idx] & (1L < <  (bit & BITS_M1) ) );
}

Gets a bit.

 public int hashCode() 
{
    long h = 1234;
    for (int i=0; i< size; i++)
	    h ^= bits[i] * offs[i];
    return (int)((h  > > 32) ^ h);
}

Gets the hashcode.

 public static  void main(String[] args) 
{
    final int ITER = 500;
    final int RANGE= 65536;
    SparseBitSet a = new SparseBitSet();
    CUtility.assert(!a.get(0) && !a.get(1));
    CUtility.assert(!a.get(123329));
    a.set(0); CUtility.assert(a.get(0) && !a.get(1));
    a.set(1); CUtility.assert(a.get(0) && a.get(1));
    a.clearAll();
    CUtility.assert(!a.get(0) && !a.get(1));
    java.util.Random r = new java.util.Random();
    java.util.Vector v = new java.util.Vector();
    for (int n=0; n< ITER; n++) {
	    int rr = ((r.nextInt() > > >1) % RANGE) < <  1;
	    a.set(rr); v.addElement(new Integer(rr));
	    // check that all the numbers are there.
	    CUtility.assert(a.get(rr) && !a.get(rr+1) && !a.get(rr-1));
	    for (int i=0; i< v.size(); i++)
        CUtility.assert(a.get(((Integer)v.elementAt(i)).intValue()));
    }
    SparseBitSet b = (SparseBitSet) a.clone();
    CUtility.assert(a.equals(b) && b.equals(a));
    for (int n=0; n< ITER/2; n++) {
	    int rr = (r.nextInt() > > >1) % v.size();
	    int m = ((Integer)v.elementAt(rr)).intValue();
	    b.clear(m); v.removeElementAt(rr);
	    // check that numbers are removed properly.
	    CUtility.assert(!b.get(m));
    }
    CUtility.assert(!a.equals(b));
    SparseBitSet c = (SparseBitSet) a.clone();
    SparseBitSet d = (SparseBitSet) a.clone();
    c.and(a);
    CUtility.assert(c.equals(a) && a.equals(c));
    c.xor(a);
    CUtility.assert(!c.equals(a) && c.size()==0);
    d.or(b);
    CUtility.assert(d.equals(a) && !b.equals(d));
    d.and(b);
    CUtility.assert(!d.equals(a) && b.equals(d));
    d.xor(a);
    CUtility.assert(!d.equals(a) && !b.equals(d));
    c.or(d); c.or(b);
    CUtility.assert(c.equals(a) && a.equals(c));
    c = (SparseBitSet) d.clone();
    c.and(b);
    CUtility.assert(c.size()==0);
    System.out.println("Success.");
}

Self-test.

 public  void or(SparseBitSet set) 
{
    binop(this, set, OR);
}

Logically ORs this bit set with the specified set of bits.

 public  void set(int bit) 
{
    int bnum = bit  > > LG_BITS;
    int idx  = bsearch(bnum);
    if (idx  >= size || offs[idx]!=bnum)
	    new_block(idx, bnum);
    bits[idx] |= (1L < <  (bit & BITS_M1) );
}

Sets a bit.

 public int size() 
{
    return (size==0)?0:((1+offs[size-1]) < <  LG_BITS);
}

Calculates and returns the set's size

 public String toString() 
{
    StringBuffer sb = new StringBuffer();
    sb.append('{");
    for (Enumeration e=elements(); e.hasMoreElements(); ) {
	    if (sb.length()  > 1) sb.append(", ");
	    sb.append(e.nextElement());
    }
    sb.append('}");
    return sb.toString();
}

Converts the SparseBitSet to a String.

 public  void xor(SparseBitSet set) 
{
    binop(this, set, XOR);
}

Logically XORs this bit set with the specified set of bits.