SparseBitSet (MorphAdorner)

java.lang.Object
- edu.northwestern.at.utils.SparseBitSet

All Implemented Interfaces:

XCloneable, java.io.Serializable, java.lang.Cloneable
```
public class SparseBitSet
extends java.lang.Object
implements XCloneable, java.io.Serializable
```
A set of bits. The set automatically grows as more bits are needed.

Version:

1.00, 25 Jul 1999

Author:

C. Scott Ananian
Modications by Philip R. "Pib" Burns to add missing BitSet methods.

See Also:
Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

protected static interface SparseBitSet.BinOp

Nested Classes
Modifier and Type	Class and Description
`protected static interface`	`SparseBitSet.BinOp`

Field Summary

Fields
Modifier and Type	Field and Description
`protected static SparseBitSet.BinOp`	`AND`
`protected static SparseBitSet.BinOp`	`ANDNOT`
`protected long[]`	`bits` Array of bit-blocks; each holding BITS bits.
`protected static int`	`BITS` Number of bits in a block.
`protected static int`	`BITS_M1` BITS-1, using the identity: x % BITS == x & (BITS-1)
`protected static int`	`LG_BITS` log base 2 of BITS, for the identity: x/BITS == x >> LG_BITS
`protected int[]`	`offs` Sorted array of bit-block offsets.
`protected static SparseBitSet.BinOp`	`OR`
`protected int`	`size` Number of blocks currently in use.
`protected static SparseBitSet.BinOp`	`XOR`

Constructor Summary

Constructors
Constructor and Description
`SparseBitSet()` Create an empty set.
`SparseBitSet(int nbits)` Create an empty set with the specified size.
`SparseBitSet(SparseBitSet set)` Create an empty set with the same size as the given set.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`and(SparseBitSet otherSet)` Logically AND this bit set with another.
`void`	`andNot(SparseBitSet otherSet)` Logically ANDNOT this bit set with another.
`protected static void`	`binop(SparseBitSet a, SparseBitSet b, SparseBitSet.BinOp op)`
`protected int`	`bsearch(int bnum)`
`int`	`cardinality()` Return cardinality (# of bits set on) in this bit set.
`void`	`clear()` Clear all bits.
`void`	`clear(int bit)` Clear a bit.
`void`	`clear(int fromIndex, int toIndex)` Clears a range of bits.
`java.lang.Object`	`clone()` Clone this set.
`java.util.Enumeration`	`elements()` Return an `Enumeration` of `Integer`s indices of bits set on in this SparseBitSet.
`boolean`	`equals(java.lang.Object object)` Compare this set against another.
`static boolean`	`equals(SparseBitSet a, SparseBitSet b)` Compare two SparseBitSets for equality.
`void`	`flip(int bit)` Flip a bit value.
`void`	`flip(int fromIndex, int toIndex)` Flips a range of bits.
`boolean`	`get(int bit)` Get bit value.
`int`	`hashCode()` Return hash code for set.
`protected void`	`insert_block(int idx, int bnum)`
`boolean`	`intersects(SparseBitSet otherSet)` Check if this set and another share at least one set bit.
`protected boolean`	`isValid()` Check validity.
`int`	`length()` Returns index of highest set bit in this set plus one.
`protected void`	`new_block(int bnum)`
`protected void`	`new_block(int idx, int bnum)`
`int`	`nextClearBit(int fromIndex)` Returns index of first bit set to false that occurs on or after specified starting index.
`int`	`nextSetBit(int fromIndex)` Returns index of first bit set to true that occurs on or after specified starting index.
`void`	`or(SparseBitSet otherSet)` Logically OR this bit set with another.
`void`	`set(int bit)` Set a bit.
`int`	`size()` Return set's size.
`java.lang.String`	`toString()` Converts the SparseBitSet to a String.
`void`	`xor(SparseBitSet otherSet)` Logically XOR this bit set with another.

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

- Field Detail
  - offs
```
protected int[] offs
```
    Sorted array of bit-block offsets.
  - bits
```
protected long[] bits
```
    Array of bit-blocks; each holding BITS bits.
  - size
```
protected int size
```
    Number of blocks currently in use.
  - LG_BITS
```
protected static final int LG_BITS
```
    log base 2 of BITS, for the identity: x/BITS == x >> LG_BITS
    
    See Also:
    Constant Field Values
  - BITS
```
protected static final int BITS
```
    Number of bits in a block.
    
    See Also:
    Constant Field Values
  - BITS_M1
```
protected static final int BITS_M1
```
    BITS-1, using the identity: x % BITS == x & (BITS-1)
    
    See Also:
    Constant Field Values
  - AND
```
protected static final SparseBitSet.BinOp AND
```
  - OR
```
protected static final SparseBitSet.BinOp OR
```
  - XOR
```
protected static final SparseBitSet.BinOp XOR
```
  - ANDNOT
```
protected static final SparseBitSet.BinOp ANDNOT
```
- Constructor Detail
  - SparseBitSet
```
public SparseBitSet()
```
    Create an empty set.
  - SparseBitSet
```
public SparseBitSet(int nbits)
```
    Create an empty set with the specified size.
    
    Parameters:
    nbits - The size of the set.
  - SparseBitSet
```
public SparseBitSet(SparseBitSet set)
```
    Create an empty set with the same size as the given set.
- Method Detail
  - new_block
```
protected void new_block(int bnum)
```
  - new_block
```
protected void new_block(int idx,
             int bnum)
```
  - insert_block
```
protected void insert_block(int idx,
                int bnum)
```
  - bsearch
```
protected int bsearch(int bnum)
```
  - set
```
public void set(int bit)
```
    Set a bit.
    
    Parameters:
    bit - The bit to set.
  - clear
```
public void clear(int bit)
```
    Clear a bit.
    
    Parameters:
    bit - The bit to be cleared.
  - clear
```
public void clear()
```
    Clear all bits.
  - clear
```
public void clear(int fromIndex,
         int toIndex)
```
    Clears a range of bits.
    
    Parameters:
    fromIndex - Index of first bit to be cleared.
    toIndex - Index + 1 of last bit to be cleared.
  - flip
```
public void flip(int bit)
```
    Flip a bit value.
    
    Parameters:
    bit - Bit to flip.
  - flip
```
public void flip(int fromIndex,
        int toIndex)
```
    Flips a range of bits.
    
    Parameters:
    fromIndex - Index of first bit to be flipped.
    toIndex - Index + 1 of last bit to be flipped.
  - get
```
public boolean get(int bit)
```
    Get bit value.
    
    Parameters:
    bit - Bit whose value is to be retrieved.
    
    Returns:
    true if bit set, false otherwise.
  - and
```
public void and(SparseBitSet otherSet)
```
    Logically AND this bit set with another.
    
    Parameters:
    otherSet - The other bit set to AND against.
  - or
```
public void or(SparseBitSet otherSet)
```
    Logically OR this bit set with another.
    
    Parameters:
    otherSet - The other bit set to be ORed against.
  - xor
```
public void xor(SparseBitSet otherSet)
```
    Logically XOR this bit set with another.
    
    Parameters:
    otherSet - The other bit set to be XORed against.
  - andNot
```
public void andNot(SparseBitSet otherSet)
```
    Logically ANDNOT this bit set with another.
    
    Parameters:
    otherSet - The other bit set to be ANDNOTed against.
  - binop
```
protected static final void binop(SparseBitSet a,
         SparseBitSet b,
         SparseBitSet.BinOp op)
```
  - hashCode
```
public int hashCode()
```
    Return hash code for set.
    
    Overrides:
    
    hashCode in class java.lang.Object
    
    Returns:
    The hash code.
  - size
```
public int size()
```
    Return set's size.
  - equals
```
public boolean equals(java.lang.Object object)
```
    Compare this set against another.
    
    Overrides:
    
    equals in class java.lang.Object
    
    Parameters:
    object - The object to compare against.
    
    Returns:
    true the objects are equal, false otherwise.
  - equals
```
public static boolean equals(SparseBitSet a,
             SparseBitSet b)
```
    Compare two SparseBitSets for equality.
    
    Returns:
    true if sets are equal, false otherwise.
  - cardinality
```
public int cardinality()
```
    Return cardinality (# of bits set on) in this bit set.
    
    Returns:
    Cardinality of this bit set.
  - intersects
```
public boolean intersects(SparseBitSet otherSet)
```
    Check if this set and another share at least one set bit.
    
    Parameters:
    otherSet - The other set to check for intersection
    
    Returns:
    true If this set and the other intersect.
  - length
```
public int length()
```
    Returns index of highest set bit in this set plus one.
    
    Returns:
    The logical size of this set.
  - nextSetBit
```
public int nextSetBit(int fromIndex)
```
    Returns index of first bit set to true that occurs on or after specified starting index.
    
    Parameters:
    fromIndex - Index to start checking from (inclusive).
    
    Returns:
    Index of next bit set.
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if specified index is negative.
    If no such bit exists then -1 is returned. To iterate over the true bits in a BitSet, use the following loop:
    
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { // operate on index i here }
  - nextClearBit
```
public int nextClearBit(int fromIndex)
```
    Returns index of first bit set to false that occurs on or after specified starting index.
    
    Parameters:
    fromIndex - Index to start checking from (inclusive).
    
    Returns:
    Index of next clear bit.
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - if specified index is negative.
    If no such bit exists then -1 is returned. To iterate over the false bits in a BitSet, use the following loop:
    
    for (int i = bs.nextClearBit(0); i >= 0; i = bs.nextClearBit(i+1)) { // operate on index i here }
  - clone
```
public java.lang.Object clone()
```
    Clone this set.
    
    Specified by:
    
    clone in interface XCloneable
    
    Overrides:
    
    clone in class java.lang.Object
    
    Returns:
    Clone of this bit set.
  - elements
```
public java.util.Enumeration elements()
```
    Return an Enumeration of Integers indices of bits set on in this SparseBitSet.
  - toString
```
public java.lang.String toString()
```
    Converts the SparseBitSet to a String.
    
    Overrides:
    
    toString in class java.lang.Object
  - isValid
```
protected boolean isValid()
```
    Check validity.

Class SparseBitSet

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

offs

bits

size

LG_BITS

BITS

BITS_M1

AND

OR

XOR

ANDNOT

Constructor Detail

SparseBitSet

SparseBitSet

SparseBitSet

Method Detail

new_block

new_block

insert_block

bsearch

set

clear

clear

clear

flip

flip

get

and

or

xor

andNot

binop

hashCode

size

equals

equals

cardinality

intersects

length

nextSetBit

nextClearBit

clone

elements

toString

isValid