com.ibm.wala.util.intset
Class SparseIntSet

java.lang.Object
  com.ibm.wala.util.intset.SparseIntSet

All Implemented Interfaces:

IntSet

Direct Known Subclasses:

MutableSparseIntSet

public class SparseIntSet
extends java.lang.Object
implements IntSet

A sparse ordered, duplicate-free, fully-encapsulated set of integers; not necessary mutable

Field Summary

protected int[]	elements The backing store of int arrays
protected int	size The number of entries in the backing store that are valid.

Constructor Summary

	SparseIntSet() Subclasses should use this with extreme care.
protected	SparseIntSet(int size)
protected	SparseIntSet(int[] backingArray) Subclasses should use this with extreme care.
	SparseIntSet(IntSet S)
protected	SparseIntSet(SparseIntSet S)

Method Summary

static SparseIntSet	add(SparseIntSet s, int j)
boolean	contains(int x) Does this set contain value x?
boolean	containsAny(IntSet set)
boolean	containsAny(SparseIntSet set)
static SparseIntSet	diff(SparseIntSet A, SparseIntSet B) Compute the asymmetric difference of two sets, a \ b.
static int[]	diffInternal(SparseIntSet A, SparseIntSet B)
int	elementAt(int idx)
void	foreach(IntSetAction action) Invoke an action on each element of the Set
void	foreachExcluding(IntSet X, IntSetAction action) Invoke an action on each element of the Set, excluding elements of Set X
int	getIndex(int x)
IntSet	intersection(IntSet that) This implementation must not despoil the original value of "this"
IntIterator	intIterator()
boolean	isEmpty()
boolean	isSubset(IntSet that)
int	max()
static SparseIntSet	pair(int i, int j)
static int[]	parseIntArray(java.lang.String str) Reverse of toString(): "{2,3}" -> [2,3]
boolean	sameValue(IntSet that)
static SparseIntSet	singleton(int i)
int	size()
int[]	toIntArray()
java.lang.String	toString()
IntSet	union(IntSet that) This implementation must not despoil the original value of "this"

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

elements

protected int[] elements

The backing store of int arrays

size

protected int size

The number of entries in the backing store that are valid.

Constructor Detail

SparseIntSet

protected SparseIntSet(int size)

SparseIntSet

protected SparseIntSet(int[] backingArray)

Subclasses should use this with extreme care. Do not allow the backing array to escape elsewhere.

SparseIntSet

public SparseIntSet()

Subclasses should use this with extreme care.

SparseIntSet

protected SparseIntSet(SparseIntSet S)

SparseIntSet

public SparseIntSet(IntSet S)
             throws java.lang.IllegalArgumentException

Throws:

java.lang.IllegalArgumentException

Method Detail

contains

public final boolean contains(int x)

Does this set contain value x?

Specified by:

contains in interface IntSet

Returns:

true iff this set contains integer i

See Also:

IntSet.contains(int)

getIndex

public final int getIndex(int x)

Returns:

index i s.t. elements[i] == x, or -1 if not found.

size

public final int size()

Specified by:

size in interface IntSet

Returns:

the number of elements in this set

isEmpty

public final boolean isEmpty()

Specified by:

isEmpty in interface IntSet

Returns:

true iff this set is empty

elementAt

public final int elementAt(int idx)
                    throws java.util.NoSuchElementException

Throws:

java.util.NoSuchElementException

sameValue

public boolean sameValue(IntSet that)
                  throws java.lang.IllegalArgumentException,
                         UnimplementedError

Specified by:

sameValue in interface IntSet

Returns:

true iff this has the same value as that.

Throws:

java.lang.IllegalArgumentException

UnimplementedError

diff

public static SparseIntSet diff(SparseIntSet A,
                                SparseIntSet B)

Compute the asymmetric difference of two sets, a \ b.

diffInternal

public static int[] diffInternal(SparseIntSet A,
                                 SparseIntSet B)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

parseIntArray

public static int[] parseIntArray(java.lang.String str)
                           throws java.lang.NumberFormatException

Reverse of toString(): "{2,3}" -> [2,3]

Throws:

java.lang.IllegalArgumentException - if str is null

java.lang.NumberFormatException

singleton

public static SparseIntSet singleton(int i)

pair

public static SparseIntSet pair(int i,
                                int j)

intersection

public IntSet intersection(IntSet that)

Description copied from interface: IntSet

This implementation must not despoil the original value of "this"

Specified by:

intersection in interface IntSet

Returns:

a new IntSet which is the intersection of this and that

union

public IntSet union(IntSet that)

Description copied from interface: IntSet

This implementation must not despoil the original value of "this"

Specified by:

union in interface IntSet

Returns:

a new IntSet containing all elements of this and that

intIterator

public IntIterator intIterator()

Specified by:

intIterator in interface IntSet

Returns:

a perhaps more efficient iterator

max

public final int max()
              throws java.lang.IllegalStateException

Specified by:

max in interface IntSet

Returns:

the largest element in the set

Throws:

java.lang.IllegalStateException

foreach

public void foreach(IntSetAction action)

Description copied from interface: IntSet

Invoke an action on each element of the Set

Specified by:

foreach in interface IntSet

foreachExcluding

public void foreachExcluding(IntSet X,
                             IntSetAction action)

Description copied from interface: IntSet

Invoke an action on each element of the Set, excluding elements of Set X

Specified by:

foreachExcluding in interface IntSet

add

public static SparseIntSet add(SparseIntSet s,
                               int j)

Returns:

a new sparse int set which adds j to s

Throws:

java.lang.IllegalArgumentException - if s is null

isSubset

public boolean isSubset(IntSet that)

Specified by:

isSubset in interface IntSet

Returns:

true iff this is a subset of that.

containsAny

public boolean containsAny(IntSet set)

Specified by:

containsAny in interface IntSet

Returns:

true iff this set contains integer i

containsAny

public boolean containsAny(SparseIntSet set)
                    throws java.lang.IllegalArgumentException

Throws:

java.lang.IllegalArgumentException

toIntArray

public int[] toIntArray()

Returns:

contents as an int[]