Package com.ibm.wala.util.intset

Class SparseIntSet

java.lang.Object

com.ibm.wala.util.intset.SparseIntSet

All Implemented Interfaces:

IntSet, Serializable

Direct Known Subclasses:

MutableSparseIntSet

public class SparseIntSet
extends Object
implements IntSet

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

See Also:

• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
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

Constructors

Modifier	Constructor	Description
	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

Modifier and Type	Method	Description
static SparseIntSet	add(SparseIntSet s, int j)
final 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)
final 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
final int	getIndex(int x)
IntSet	intersection(IntSet that)	This implementation must not despoil the original value of "this"
IntIterator	intIterator()
final boolean	isEmpty()
boolean	isSubset(@Nullable IntSet that)
final int	max()
static SparseIntSet	pair(int i, int j)
static int[]	parseIntArray(String str)	Reverse of toString(): "{2,3}" -> [2,3]
boolean	sameValue(IntSet that)
static SparseIntSet	singleton(int i)
final int	size()
int[]	toIntArray()
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 Details

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 Details

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

@NullUnmarked
public SparseIntSet()

Subclasses should use this with extreme care.

SparseIntSet

protected SparseIntSet(SparseIntSet S)

SparseIntSet

public SparseIntSet(IntSet S)
             throws IllegalArgumentException

Throws:

IllegalArgumentException

Method Details

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

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 NoSuchElementException

Throws:

NoSuchElementException

sameValue

public boolean sameValue(IntSet that)
                  throws IllegalArgumentException,
UnimplementedError

Specified by:

sameValue in interface IntSet

Returns:

true iff this has the same value as that.

Throws:

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 String toString()

Overrides:

toString in class Object

parseIntArray

public static int[] parseIntArray(String str)

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

Throws:

IllegalArgumentException - if str is null

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 IllegalStateException

Specified by:

max in interface IntSet

Returns:

the largest element in the set

Throws:

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

See Also:

• IntSet.foreach(com.ibm.wala.util.intset.IntSetAction)

add

public static SparseIntSet add(SparseIntSet s,
 int j)

Returns:

a new sparse int set which adds j to s

Throws:

IllegalArgumentException - if s is null

isSubset

public boolean isSubset(@Nullable 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 IllegalArgumentException

Throws:

IllegalArgumentException

toIntArray

public int[] toIntArray()

Returns:

contents as an int[]