io.druid.extendedset.intset

Class AbstractIntSet

java.lang.Object

io.druid.extendedset.intset.AbstractIntSet

All Implemented Interfaces:

IntSet, Cloneable, Comparable<IntSet>

Direct Known Subclasses:

ConciseSet

public abstract class AbstractIntSet
extends Object
implements IntSet

This class provides a skeletal implementation of the IntSet interface to minimize the effort required to implement this interface.

Version:

$Id: AbstractIntSet.java 156 2011-09-01 00:13:57Z cocciasik $

Author:

Alessandro Colantonio

Nested Class Summary

Nested classes/interfaces inherited from interface io.druid.extendedset.intset.IntSet

IntSet.IntIterator

Constructor Summary

Constructors

Constructor and Description
AbstractIntSet()

Method Summary

Modifier and Type	Method and Description
abstract 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.
abstract 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.
abstract IntSet	clone() See the clone() of Object
abstract 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.)
int	compareTo(IntSet o)
void	complement() Complements the current set.
IntSet	complemented() Generates the complement set.
int	complementSize() Computes the complement set size.
abstract 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 c) Returns true if the specified IntSet instance contains any elements that are also contained within this IntSet instance
boolean	containsAtLeast(IntSet c, int minElements) Returns true if the specified IntSet instance contains at least minElements elements that are also contained within this IntSet instance
abstract IntSet	convert(Collection<Integer> c) Converts a given collection into an instance of the current class.
abstract IntSet	convert(int... a) Converts a given array into an instance of the current class.
abstract String	debugInfo() Prints debug info about the given IntSet implementation
abstract IntSet.IntIterator	descendingIterator()
IntSet	difference(IntSet other) Generates the difference set
int	differenceSize(IntSet other) Computes the difference set size.
abstract IntSet	empty() Generates an empty set
boolean	equals(Object obj)
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
abstract int	get(int i) Gets the ith element of the set
int	hashCode()
abstract int	indexOf(int e) Provides position of element within the set.
IntSet	intersection(IntSet other) Generates the intersection set
int	intersectionSize(IntSet c) Computes the intersection set size.
abstract boolean	isEmpty()
abstract 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.
abstract 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.
abstract 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.
abstract int	size()
IntSet	symmetricDifference(IntSet c) 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.
String	toString()
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 class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

AbstractIntSet

public AbstractIntSet()

Method Detail

union

public IntSet union(IntSet other)

Generates the union set

Specified by:

union in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

IntSet.addAll(IntSet)

difference

public IntSet difference(IntSet other)

Generates the difference set

Specified by:

difference in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

IntSet.removeAll(IntSet)

intersection

public IntSet intersection(IntSet other)

Generates the intersection set

Specified by:

intersection in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

IntSet.retainAll(IntSet)

symmetricDifference

public IntSet symmetricDifference(IntSet c)

Generates the symmetric difference set

Specified by:

symmetricDifference in interface IntSet

Parameters:

c - IntSet instance that represents the right operand

Returns:

the result of the operation

See Also:

IntSet.flip(int)

complemented

public IntSet complemented()

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

Specified by:

complemented in interface IntSet

Returns:

the complement set

See Also:

IntSet.complement()

complement

public void complement()

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

Specified by:

complement in interface IntSet

See Also:

IntSet.complemented()

containsAll

public boolean containsAll(IntSet c)

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

Specified by:

containsAll in interface IntSet

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

See Also:

IntSet.contains(int)

containsAny

public boolean containsAny(IntSet c)

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

Specified by:

containsAny in interface IntSet

Parameters:

c - IntSet to intersect with

Returns:

a boolean indicating whether this IntSet intersects the specified IntSet.

containsAtLeast

public boolean containsAtLeast(IntSet c,
                               int minElements)

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

Specified by:

containsAtLeast in interface IntSet

Parameters:

c - 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.

intersectionSize

public int intersectionSize(IntSet c)

Computes the intersection set size.

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

Specified by:

intersectionSize in interface IntSet

Parameters:

c - IntSet instance that represents the right operand

Returns:

the size

unionSize

public int unionSize(IntSet other)

Computes the union set size.

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

Specified by:

unionSize in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

symmetricDifferenceSize

public int symmetricDifferenceSize(IntSet other)

Computes the symmetric difference set size.

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

Specified by:

symmetricDifferenceSize in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

differenceSize

public int differenceSize(IntSet other)

Computes the difference set size.

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

Specified by:

differenceSize in interface IntSet

Parameters:

other - IntSet instance that represents the right operand

Returns:

the size

complementSize

public int complementSize()

Computes the complement set size.

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

Specified by:

complementSize in interface IntSet

Returns:

the size

empty

public abstract IntSet empty()

Generates an empty set

Specified by:

empty in interface IntSet

Returns:

the empty set

clone

public abstract IntSet clone()

See the clone() of Object

Specified by:

clone in interface IntSet

Overrides:

clone in class Object

Returns:

cloned object

bitmapCompressionRatio

public abstract 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.)

Specified by:

bitmapCompressionRatio in interface IntSet

Returns:

the compression factor

collectionCompressionRatio

public abstract 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.)

Specified by:

collectionCompressionRatio in interface IntSet

Returns:

the compression factor

iterator

public abstract IntSet.IntIterator iterator()

Specified by:

iterator in interface IntSet

Returns:

a IntSet.IntIterator instance to iterate over the set

descendingIterator

public abstract IntSet.IntIterator descendingIterator()

Specified by:

descendingIterator in interface IntSet

Returns:

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

debugInfo

public abstract String debugInfo()

Prints debug info about the given IntSet implementation

Specified by:

debugInfo in interface IntSet

Returns:

a string that describes the internal representation of the instance

clear

public void clear()

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

Specified by:

clear in interface IntSet

clear

public void clear(int from,
                  int to)

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

Specified by:

clear in interface IntSet

Parameters:

from - first element

to - last element

fill

public void fill(int from,
                 int to)

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

Specified by:

fill in interface IntSet

Parameters:

from - first element

to - last element

flip

public void flip(int e)

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

Specified by:

flip in interface IntSet

Parameters:

e - element to flip

See Also:

IntSet.symmetricDifference(IntSet)

get

public abstract int get(int i)

Gets the i^th element of the set

Specified by:

get in interface IntSet

Parameters:

i - position of the element in the sorted set

Returns:

the i^th element of the set

indexOf

public abstract int indexOf(int e)

Provides position of element within the set.

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

Specified by:

indexOf in interface IntSet

Parameters:

e - element of the set

Returns:

the element position

convert

public abstract IntSet convert(int... a)

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

Specified by:

convert in interface IntSet

Parameters:

a - array to use to generate the new instance

Returns:

the converted collection

convert

public abstract IntSet convert(Collection<Integer> c)

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

Specified by:

convert in interface IntSet

Parameters:

c - array to use to generate the new instance

Returns:

the converted collection

first

public int first()

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

Specified by:

first in interface IntSet

Returns:

the first (lowest) element currently in this set

last

public abstract int last()

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

Specified by:

last in interface IntSet

Returns:

the last (highest) element currently in this set

size

public abstract int size()

Specified by:

size in interface IntSet

Returns:

the number of elements in this set (its cardinality)

isEmpty

public abstract boolean isEmpty()

Specified by:

isEmpty in interface IntSet

Returns:

true if this set contains no elements

contains

public abstract boolean contains(int i)

Returns true if this set contains the specified element.

Specified by:

contains in interface IntSet

Parameters:

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

Returns:

true if this set contains the specified element

add

public abstract 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.

Specified by:

add in interface IntSet

Parameters:

i - element to be added to this set

Returns:

true if this set did not already contain the specified element

remove

public abstract boolean remove(int i)

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

Specified by:

remove in interface IntSet

Parameters:

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

Returns:

true if this set contained the specified element

addAll

public boolean addAll(IntSet c)

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

Specified by:

addAll in interface IntSet

Parameters:

c - collection containing elements to be added to this set

Returns:

true if this set changed as a result of the call

See Also:

IntSet.add(int)

removeAll

public boolean removeAll(IntSet c)

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

Specified by:

removeAll in interface IntSet

Parameters:

c - collection containing elements to be removed from this set

Returns:

true if this set changed as a result of the call

See Also:

IntSet.remove(int), IntSet.contains(int)

retainAll

public 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.

Specified by:

retainAll in interface IntSet

Parameters:

c - collection containing elements to be retained in this set

Returns:

true if this set changed as a result of the call

See Also:

IntSet.remove(int)

toArray

public int[] toArray()

Specified by:

toArray in interface IntSet

Returns:

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

toArray

public 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.

Specified by:

toArray in interface IntSet

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

toString

public String toString()

Overrides:

toString in class Object

compareTo

public int compareTo(IntSet o)

Specified by:

compareTo in interface Comparable<IntSet>

powerSet

public 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.

Specified by:

powerSet in interface IntSet

Returns:

the power-set

See Also:

IntSet.powerSet(int, int), IntSet.powerSetSize()

powerSet

public 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.

Specified by:

powerSet in interface IntSet

Parameters:

min - minimum subset size (greater than zero)

max - maximum subset size

Returns:

the power-set

See Also:

IntSet.powerSet(), #powerSetSize(int, int)

powerSetSize

public int powerSetSize()

Computes the power-set size of the current set.

The power-set does not contains the empty set.

Specified by:

powerSetSize in interface IntSet

Returns:

the power-set size

See Also:

IntSet.powerSet()

jaccardSimilarity

public 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|.

Specified by:

jaccardSimilarity in interface IntSet

Parameters:

other - the other set

Returns:

the Jaccard similarity coefficient

See Also:

IntSet.jaccardDistance(IntSet)

jaccardDistance

public double jaccardDistance(IntSet other)

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

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

Specified by:

jaccardDistance in interface IntSet

Parameters:

other - the other set

Returns:

the Jaccard distance

See Also:

IntSet.jaccardSimilarity(IntSet)

weightedJaccardSimilarity

public 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).

Specified by:

weightedJaccardSimilarity in interface IntSet

Parameters:

other - the other set

Returns:

the weighted Jaccard similarity coefficient

See Also:

IntSet.weightedJaccardDistance(IntSet)

weightedJaccardDistance

public 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 - IntSet.weightedJaccardSimilarity(IntSet).

Specified by:

weightedJaccardDistance in interface IntSet

Parameters:

other - the other set

Returns:

the weighted Jaccard distance

See Also:

IntSet.weightedJaccardSimilarity(IntSet)

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object