de.unidu.is.pdatalog.ds
Class SubSet

java.lang.Object
  de.unidu.is.pdatalog.ds.SubSet

public class SubSet

extends java.lang.Object

A subset of a given set {0,...,n-1}. Every number i can be present (flags[i] is true) or absent (flags[i] is false). n is the cardinality of the superset.

The SubSet can be represented as reverse binary string (by toString()) or a corresponding integer (by getValue()). E.g.: The superset may be {1,2,3,4}, and the SubSet may be {1,3,4}. Then the binary string is "1011" and the integer value is 13.

Since:

2000-07-27

Version:

$Revision: 1.4 $, $Date: 2005/02/28 22:27:55 $

Author:

Henrik Nottelmann

Field Summary

protected boolean[]	flags The flags indicating if a number is present of absent.
protected int	max The maximum number of any corresponding integer value plus one.

Constructor Summary

SubSet(int card)
Creates a new SubSet of a set {0,...

SubSet(int card, int value)
Creates a new SubSet of a set {0,...

SubSet(int card, java.lang.String value)
Creates a new SubSet of a set {0,...

Method Summary

void	add(int num) Adds the specified number to this SubSet if it is not already present.
boolean	contains(int num) Tests is the specified number num is in this SubSet.
int	count() Returns the cardinality of in this SubSet.
static int	count(int value, int card) Returns the cardinality of in the SubSet created by new SubSet(card,value).
boolean	equals(java.lang.Object o) Compares the specified Object with this SubSet for equality.
int	getCard() Returns the cardinality of the superset.
int	getMax() Returns the maximum number of any corresponding integer value plus one.
SubSet	getNext() Returns the next subset corresponding to the integer value.
SubSet	getPrev() Returns the next subset corresponding to the integer value.
int	getValue() Returns the integer value corresponding to this SubSet.
static boolean	isSubSetFrom(int value1, int value2) Tests if the SubSet corresponding to the first specified integer is a subset of the SubSet corresponding to the second specified integer.
boolean	isSubSetFrom(SubSet subSet) Tests if this SubSet is a subset of the specified SubSet.
void	minus(SubSet subSet) Removes all numbers in the specified SubSet from this SubSet if they are present.
void	next() Sets this SubSet to the next subset corresponding to the integer value.
static int	pow2(int exp) An auxiliary method returning 2^exp.
void	prev() Sets this SubSet to the previous subset corresponding to the integer value.
void	remove(int num) Removes the specified number to this SubSet if it is present.
void	setCard(int card) Sets the cardinality of the superset and clears this SubSet.
void	setValue(int value) Sets this SubSet corresponding to an integer value.
void	setValue(java.lang.String value) Sets this SubSet corresponding to a reverse binary string.
java.lang.String	toString() Returns a string representation of this SubSet as a reverse binary string.
static java.lang.String	toString(int value, int card) Returns a string representation of the SubSet created by new SubSet(card,value).
protected int	trim(int value) An auxiliary method calculating value % max.
protected static int	trim(int value, int card) An auxiliary method calculating value % 2^card.

Methods inherited from class java.lang.Object

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

Field Detail

flags

protected boolean[] flags

The flags indicating if a number is present of absent. flags[i] is true if i is present in this SubSet.

max

protected int max

The maximum number of any corresponding integer value plus one. It is max == 2^(flags.length).

Constructor Detail

SubSet

public SubSet(int card)

Creates a new SubSet of a set {0,...,card-1}. The SubSet is initially empty.

Parameters:

card - the cardinality of the superset

See Also:

SubSet(int,int), SubSet(int,String)

SubSet

public SubSet(int card,
              int value)

Creates a new SubSet of a set {0,...,card-1}. The SubSet contains the numbers corresponding to the integer value.

Parameters:

card - the cardinality of the superset

value - the value describing this SubSet

See Also:

SubSet(int), SubSet(int,String)

SubSet

public SubSet(int card,
              java.lang.String value)

Creates a new SubSet of a set {0,...,card-1}. The SubSet contains the numbers corresponding to the String value.

Parameters:

card - the cardinality of the superset

value - the value describing this SubSet

See Also:

SubSet(int), SubSet(int,int)

Method Detail

pow2

public static int pow2(int exp)

An auxiliary method returning 2^exp.

Parameters:

exp - the exponent

Returns:

2^exp

getCard

public int getCard()

Returns the cardinality of the superset.

Returns:

the cardinality of the superset

setCard

public void setCard(int card)

Sets the cardinality of the superset and clears this SubSet.

Parameters:

card - the cardinality of the superset

getMax

public int getMax()

Returns the maximum number of any corresponding integer value plus one.

Returns:

the maximum number of any corresponding integer value plus one

getValue

public int getValue()

Returns the integer value corresponding to this SubSet. This is the integer value of the reverse of the binary string returned by toString().

Returns:

the integer value corresponding to this SubSet

trim

protected int trim(int value)

An auxiliary method calculating value % max.

Parameters:

value - the value to be trimmed

Returns:

value % max

trim

protected static int trim(int value,
                          int card)

An auxiliary method calculating value % 2^card.

Parameters:

value - the value to be trimmed

card - the cardinality

Returns:

value % 2^card

setValue

public void setValue(int value)

Sets this SubSet corresponding to an integer value.

Parameters:

value - the integer value describing the new content of this SubSet

setValue

public void setValue(java.lang.String value)

Sets this SubSet corresponding to a reverse binary string.

Parameters:

value - the reverse binary string describing the new content of this SubSet

contains

public boolean contains(int num)

Tests is the specified number num is in this SubSet.

Parameters:

num - the number to be testes

Returns:

true is number is in this SubSet, i.e. flags[num] is true

add

public void add(int num)

Adds the specified number to this SubSet if it is not already present.

Parameters:

num - the number to be added

remove

public void remove(int num)

Removes the specified number to this SubSet if it is present.

Parameters:

num - the number to be removed

next

public void next()

Sets this SubSet to the next subset corresponding to the integer value.

prev

public void prev()

Sets this SubSet to the previous subset corresponding to the integer value.

getNext

public SubSet getNext()

Returns the next subset corresponding to the integer value.

Returns:

the next subset corresponding to the integer value

getPrev

public SubSet getPrev()

Returns the next subset corresponding to the integer value.

Returns:

the next subset corresponding to the integer value

count

public int count()

Returns the cardinality of in this SubSet. I.e. the number of elements in this SubSet.

Returns:

the number in this SubSet

count

public static int count(int value,
                        int card)

Returns the cardinality of in the SubSet created by new SubSet(card,value). I.e. the number of elements in the specified SubSet.

Parameters:

value - the value of the specified SubSet

card - the cardinality of the superset of the specified SubSet

Returns:

the number in the specified SubSet

See Also:

count()

isSubSetFrom

public boolean isSubSetFrom(SubSet subSet)

Tests if this SubSet is a subset of the specified SubSet.

A SubSet A is a subset of another SubSet B if

• A.getCard() == B.getCard(), and
• all numbers contained in A are also contained in B.

Parameters:

subSet - the SubSet to be tested

Returns:

true if this SubSet is a subset of the specified SubSet

isSubSetFrom

public static boolean isSubSetFrom(int value1,
                                   int value2)

Tests if the SubSet corresponding to the first specified integer is a subset of the SubSet corresponding to the second specified integer.

A SubSet A is a subset of another SubSet B if

• A.getCard() == B.getCard(), and
• all numbers contained in A are also contained in B.

Parameters:

value1 - the integer corresponding to the first SubSet to be tested

value2 - the integer corresponding to the second SubSet to be tested

Returns:

true if value1 if a subset of value2

minus

public void minus(SubSet subSet)

Removes all numbers in the specified SubSet from this SubSet if they are present. So this methods performs a this = this \ subSet operation.

Parameters:

subSet - the subSet containing all numbers to be removed from this SubSet

equals

public boolean equals(java.lang.Object o)

Compares the specified Object with this SubSet for equality.

Two SubSets A and B are equal iff

• A.getCard() == B.getCard(), and
• all numbers contained in A are also contained in B, and
• all numbers contained in B are also contained in A.

Parameters:

o - the Object to be compared for equality with this SubSet

Returns:

true if the specified Object is equal to this SubSet

toString

public java.lang.String toString()

Returns a string representation of this SubSet as a reverse binary string.

E.g.: The superset may be {1,2,3,4}, and the SubSet may be {1,3,4}. Then the binary string returned by this method is "1011".

Returns:

a string representation of this SubSet

toString

public static java.lang.String toString(int value,
                                        int card)

Returns a string representation of the SubSet created by new SubSet(card,value).

Parameters:

value - the value of the specified SubSet

card - the cardinality of the superset of the specified SubSet

Returns:

a string representation of this SubSet

See Also:

toString()