io.druid.extendedset.intset

Interface IntSet

All Superinterfaces:

Cloneable, Comparable<IntSet>

All Known Implementing Classes:

AbstractIntSet, ConciseSet

public interface IntSet
extends Cloneable, Comparable<IntSet>

Version:

$Id: IntSet.java 135 2011-01-04 15:54:48Z cocciasik $

Author:

Alessandro Colantonio

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static interface	IntSet.IntIterator An Iterator-like interface that allows to "skip" some elements of the set

Method Summary

Modifier and Type	Method and Description
boolean	add(int i) Adds the specified element to this set if it is not already present.
boolean	addAll(IntSet c) Adds all of the elements in the specified collection to this set if they're not already present.
double	bitmapCompressionRatio() Computes the compression factor of the equivalent bitmap representation (1 means not compressed, namely a memory footprint similar to BitSet, 2 means twice the size of BitSet, etc.)
void	clear() Removes all of the elements from this set.
void	clear(int from, int to) Removes from the set all the elements between first and last, both included.
IntSet	clone() See the clone() of Object
double	collectionCompressionRatio() Computes the compression factor of the equivalent integer collection (1 means not compressed, namely a memory footprint similar to ArrayList, 2 means twice the size of ArrayList, etc.)
void	complement() Complements the current set.
IntSet	complemented() Generates the complement set.
int	complementSize() Computes the complement set size.
boolean	contains(int i) Returns true if this set contains the specified element.
boolean	containsAll(IntSet c) Returns true if this set contains all of the elements of the specified collection.
boolean	containsAny(IntSet other) Returns true if the specified IntSet instance contains any elements that are also contained within this IntSet instance
boolean	containsAtLeast(IntSet other, int minElements) Returns true if the specified IntSet instance contains at least minElements elements that are also contained within this IntSet instance
IntSet	convert(Collection<Integer> c) Converts a given collection into an instance of the current class.
IntSet	convert(int... a) Converts a given array into an instance of the current class.
String	debugInfo() Prints debug info about the given IntSet implementation
IntSet.IntIterator	descendingIterator()
IntSet	difference(IntSet other) Generates the difference set
int	differenceSize(IntSet other) Computes the difference set size.
IntSet	empty() Generates an empty set
void	fill(int from, int to) Adds to the set all the elements between first and last, both included.
int	first() Returns the first (lowest) element currently in this set.
void	flip(int e) Adds the element if it not existing, or removes it if existing
int	get(int i) Gets the ith element of the set
int	indexOf(int e) Provides position of element within the set.
IntSet	intersection(IntSet other) Generates the intersection set
int	intersectionSize(IntSet other) Computes the intersection set size.
boolean	isEmpty()
IntSet.IntIterator	iterator()
double	jaccardDistance(IntSet other) Computes the Jaccard distance between this set and the given set.
double	jaccardSimilarity(IntSet other) Computes the Jaccard similarity coefficient between this set and the given set.
int	last() Returns the last (highest) element currently in this set.
List<? extends IntSet>	powerSet() Computes the power-set of the current set.
List<? extends IntSet>	powerSet(int min, int max) Computes a subset of the power-set of the current set, composed by those subsets that have cardinality between min and max.
int	powerSetSize() Computes the power-set size of the current set.
boolean	remove(int i) Removes the specified element from this set if it is present.
boolean	removeAll(IntSet c) Removes from this set all of its elements that are contained in the specified collection.
boolean	retainAll(IntSet c) Retains only the elements in this set that are contained in the specified collection.
int	size()
IntSet	symmetricDifference(IntSet other) Generates the symmetric difference set
int	symmetricDifferenceSize(IntSet other) Computes the symmetric difference set size.
int[]	toArray()
int[]	toArray(int[] a) Returns an array containing all of the elements in this set.
IntSet	union(IntSet other) Generates the union set
int	unionSize(IntSet other) Computes the union set size.
double	weightedJaccardDistance(IntSet other) Computes the weighted version of the Jaccard distance between this set and the given set.
double	weightedJaccardSimilarity(IntSet other) Computes the weighted version of the Jaccard similarity coefficient between this set and the given set.

Methods inherited from interface java.lang.Comparable

compareTo

Method Detail

intersection

IntSet intersection(IntSet other)

Generates the intersection set

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

retainAll(IntSet)

union

IntSet union(IntSet other)

Generates the union set

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

addAll(IntSet)

difference

IntSet difference(IntSet other)

Generates the difference set

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

removeAll(IntSet)

symmetricDifference

IntSet symmetricDifference(IntSet other)

Generates the symmetric difference set

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

flip(int)

complemented

IntSet complemented()

Generates the complement set. The returned set is represented by all the elements strictly less than last() that do not exist in the current set.

Returns:

the complement set

See Also:

complement()

complement

void complement()

Complements the current set. The modified set is represented by all the elements strictly less than last() that do not exist in the current set.

See Also:

complemented()

containsAny

boolean containsAny(IntSet other)

Returns true if the specified IntSet instance contains any elements that are also contained within this IntSet instance

Parameters:

other - IntSet to intersect with

Returns:

a boolean indicating whether this IntSet intersects the specified IntSet.

containsAtLeast

boolean containsAtLeast(IntSet other,
                        int minElements)

Returns true if the specified IntSet instance contains at least minElements elements that are also contained within this IntSet instance

Parameters:

other - IntSet instance to intersect with

minElements - minimum number of elements to be contained within this IntSet instance

Returns:

a boolean indicating whether this IntSet intersects the specified IntSet.

Throws:

IllegalArgumentException - if minElements < 1

intersectionSize

int intersectionSize(IntSet other)

Computes the intersection set size.

This is faster than calling intersection(IntSet) and then size()

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

unionSize

int unionSize(IntSet other)

Computes the union set size.

This is faster than calling union(IntSet) and then size()

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

symmetricDifferenceSize

int symmetricDifferenceSize(IntSet other)

Computes the symmetric difference set size.

This is faster than calling symmetricDifference(IntSet) and then size()

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

differenceSize

int differenceSize(IntSet other)

Computes the difference set size.

This is faster than calling difference(IntSet) and then size()

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

complementSize

int complementSize()

Computes the complement set size.

This is faster than calling complemented() and then size()

Returns:

the size

empty

IntSet empty()

Generates an empty set

Returns:

the empty set

clone

IntSet clone()

See the clone() of Object

Returns:

cloned object

bitmapCompressionRatio

double bitmapCompressionRatio()

Computes the compression factor of the equivalent bitmap representation (1 means not compressed, namely a memory footprint similar to BitSet, 2 means twice the size of BitSet, etc.)

Returns:

the compression factor

collectionCompressionRatio

double collectionCompressionRatio()

Computes the compression factor of the equivalent integer collection (1 means not compressed, namely a memory footprint similar to ArrayList, 2 means twice the size of ArrayList, etc.)

Returns:

the compression factor

iterator

IntSet.IntIterator iterator()

Returns:

a IntSet.IntIterator instance to iterate over the set

descendingIterator

IntSet.IntIterator descendingIterator()

Returns:

a IntSet.IntIterator instance to iterate over the set in descending order

debugInfo

String debugInfo()

Prints debug info about the given IntSet implementation

Returns:

a string that describes the internal representation of the instance

fill

void fill(int from,
          int to)

Adds to the set all the elements between first and last, both included.

Parameters:

from - first element

to - last element

clear

void clear(int from,
           int to)

Removes from the set all the elements between first and last, both included.

Parameters:

from - first element

to - last element

flip

void flip(int e)

Adds the element if it not existing, or removes it if existing

Parameters:

e - element to flip

See Also:

symmetricDifference(IntSet)

get

int get(int i)

Gets the i^th element of the set

Parameters:

i - position of the element in the sorted set

Returns:

the i^th element of the set

Throws:

IndexOutOfBoundsException - if i is less than zero, or greater or equal to size()

indexOf

int indexOf(int e)

Provides position of element within the set.

It returns -1 if the element does not exist within the set.

Parameters:

e - element of the set

Returns:

the element position

convert

IntSet convert(int... a)

Converts a given array into an instance of the current class.

Parameters:

a - array to use to generate the new instance

Returns:

the converted collection

convert

IntSet convert(Collection<Integer> c)

Converts a given collection into an instance of the current class.

Parameters:

c - array to use to generate the new instance

Returns:

the converted collection

first

int first()

Returns the first (lowest) element currently in this set.

Returns:

the first (lowest) element currently in this set

Throws:

NoSuchElementException - if this set is empty

last

int last()

Returns the last (highest) element currently in this set.

Returns:

the last (highest) element currently in this set

Throws:

NoSuchElementException - if this set is empty

size

int size()

Returns:

the number of elements in this set (its cardinality)

isEmpty

boolean isEmpty()

Returns:

true if this set contains no elements

contains

boolean contains(int i)

Returns true if this set contains the specified element.

Parameters:

i - element whose presence in this set is to be tested

Returns:

true if this set contains the specified element

add

boolean add(int i)

Adds the specified element to this set if it is not already present. It ensures that sets never contain duplicate elements.

Parameters:

i - element to be added to this set

Returns:

true if this set did not already contain the specified element

Throws:

IllegalArgumentException - if some property of the specified element prevents it from being added to this set

remove

boolean remove(int i)

Removes the specified element from this set if it is present.

Parameters:

i - object to be removed from this set, if present

Returns:

true if this set contained the specified element

Throws:

UnsupportedOperationException - if the remove operation is not supported by this set

containsAll

boolean containsAll(IntSet c)

Returns true if this set contains all of the elements of the specified collection.

Parameters:

c - collection to be checked for containment in this set

Returns:

true if this set contains all of the elements of the specified collection

Throws:

NullPointerException - if the specified collection contains one or more null elements and this set does not permit null elements (optional), or if the specified collection is null

See Also:

contains(int)

addAll

boolean addAll(IntSet c)

Adds all of the elements in the specified collection to this set if they're not already present.

Parameters:

c - collection containing elements to be added to this set

Returns:

true if this set changed as a result of the call

Throws:

NullPointerException - if the specified collection contains one or more null elements and this set does not permit null elements, or if the specified collection is null

IllegalArgumentException - if some property of an element of the specified collection prevents it from being added to this set

See Also:

add(int)

retainAll

boolean retainAll(IntSet c)

Retains only the elements in this set that are contained in the specified collection. In other words, removes from this set all of its elements that are not contained in the specified collection.

Parameters:

c - collection containing elements to be retained in this set

Returns:

true if this set changed as a result of the call

Throws:

NullPointerException - if this set contains a null element and the specified collection does not permit null elements (optional), or if the specified collection is null

See Also:

remove(int)

removeAll

boolean removeAll(IntSet c)

Removes from this set all of its elements that are contained in the specified collection.

Parameters:

c - collection containing elements to be removed from this set

Returns:

true if this set changed as a result of the call

Throws:

NullPointerException - if this set contains a null element and the specified collection does not permit null elements (optional), or if the specified collection is null

See Also:

remove(int), contains(int)

clear

void clear()

Removes all of the elements from this set. The set will be empty after this call returns.

Throws:

UnsupportedOperationException - if the clear method is not supported by this set

toArray

int[] toArray()

Returns:

an array containing all the elements in this set, in the same order.

toArray

int[] toArray(int[] a)

Returns an array containing all of the elements in this set.

If this set fits in the specified array with room to spare (i.e., the array has more elements than this set), the element in the array immediately following the end of the set are left unchanged.

Parameters:

a - the array into which the elements of this set are to be stored.

Returns:

the array containing all the elements in this set

Throws:

NullPointerException - if the specified array is null

IllegalArgumentException - if this set does not fit in the specified array

powerSet

List<? extends IntSet> powerSet()

Computes the power-set of the current set.

It is a particular implementation of the algorithm Apriori (see: Rakesh Agrawal, Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, in Proceedings of the 20^th International Conference on Very Large Data Bases, p.487-499, 1994). The returned power-set does not contain the empty set.

The subsets composing the powerset are returned in a list that is sorted according to the lexicographical order provided by the integer set.

Returns:

the power-set

See Also:

powerSet(int, int), powerSetSize()

powerSet

List<? extends IntSet> powerSet(int min,
                                int max)

Computes a subset of the power-set of the current set, composed by those subsets that have cardinality between min and max.

It is a particular implementation of the algorithm Apriori (see: Rakesh Agrawal, Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, in Proceedings of the 20^th International Conference on Very Large Data Bases, p.487-499, 1994). The power-set does not contains the empty set.

The subsets composing the powerset are returned in a list that is sorted according to the lexicographical order provided by the integer set.

Parameters:

min - minimum subset size (greater than zero)

max - maximum subset size

Returns:

the power-set

See Also:

powerSet(), #powerSetSize(int, int)

powerSetSize

int powerSetSize()

Computes the power-set size of the current set.

The power-set does not contains the empty set.

Returns:

the power-set size

See Also:

powerSet()

jaccardSimilarity

double jaccardSimilarity(IntSet other)

Computes the Jaccard similarity coefficient between this set and the given set.

The coefficient is defined as |A intersection B| / |A union B|.

Parameters:

other - the other set

Returns:

the Jaccard similarity coefficient

See Also:

jaccardDistance(IntSet)

jaccardDistance

double jaccardDistance(IntSet other)

Computes the Jaccard distance between this set and the given set.

The coefficient is defined as 1 - jaccardSimilarity(IntSet).

Parameters:

other - the other set

Returns:

the Jaccard distance

See Also:

jaccardSimilarity(IntSet)

weightedJaccardSimilarity

double weightedJaccardSimilarity(IntSet other)

Computes the weighted version of the Jaccard similarity coefficient between this set and the given set.

The coefficient is defined as sum of min(A_i, B_i) / sum of max(A_i, B_i).

Parameters:

other - the other set

Returns:

the weighted Jaccard similarity coefficient

See Also:

weightedJaccardDistance(IntSet)

weightedJaccardDistance

double weightedJaccardDistance(IntSet other)

Computes the weighted version of the Jaccard distance between this set and the given set.

The coefficient is defined as 1 - weightedJaccardSimilarity(IntSet).

Parameters:

other - the other set

Returns:

the weighted Jaccard distance

See Also:

weightedJaccardSimilarity(IntSet)