Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members

gbdd::Domain Class Reference

A set of variables of a BDD to represent a component of a relation. More...

#include <domain.h>

List of all members.

Public Types

typedef unsigned long int Var
typedef const_iterator iterator
 Alias for const_iterator.


Public Member Functions

 Domain ()
 Creates an empty domain.

 Domain (Var from, unsigned int n_vars=1, unsigned int step=1)
 Creates a finite domain.

 Domain (const Domain &infinite_base, const Domain &from)
 Lay out one domain onto an infinite base.

 Domain (const set< Var > &s)
 Creates a finite domain given a set of variables.

bool is_finite () const
 Checks if domain is finite.

bool is_infinite () const
 Checks if domain is infinite.

bool is_empty () const
 Checks if domain is empty.

bool is_compatible (const Domain &d2) const
 Checks if two domains are compatible.

bool is_disjoint (const Domain &d2) const
 Checks if two domains are disjoint.

unsigned int size () const
 Get size of domain.

Var lowest () const
 Get the lowest variable in domain.

Var highest () const
 Get the highest variable in domain.

Var higher () const
 Get a variable higher then any variable in domain.

bool operator() (Var v) const
 Membership test.

Domainoperator|= (const Domain &vs)
 Union assignment.

Domainoperator &= (const Domain &vs)
 Intersection assignment.

Domainoperator-= (const Domain &vs)
 Difference assignment.

template<class _UnaryFunction> Domain transform (_UnaryFunction op) const
 transform elements of domain

Domain operator * (unsigned int v) const
 Multiply every variable in domain.

Domain operator/ (unsigned int v) const
 Divide every variable in domain.

Domain operator+ (unsigned int v) const
 Add to every variable in domain.

Domain operator- (unsigned int v) const
 Subtract from every variable in domain.

Domain first_n (unsigned int n) const
 Get a domain with the lowest variables.

Domain last_n (unsigned int n) const
 Get a domain with the highest variables.

Domain cut_to_same_size (const Domain &d) const
 Remove highest variables to get same size as another domain.

const_iterator begin () const
 Get iterator pointing to beginning of set.

const_iterator end () const
 Get iterator pointing to end of set.


Static Public Member Functions

Domain infinite (Var from=0, Var step=1)
 Creates an infinite domain.

VarMap map_vars (const Domain &vs1, const Domain &vs2)
Domain sup (const Domain &vs1, const Domain &vs2)
 Get largest domain.


Friends

class Domain::const_iterator
ostream & operator<< (ostream &s, const Domain &vs)
 Sends a textual description of a domain into a stream.

Domain operator| (const Domain &vs1, const Domain &vs2)
 Union of domains.

Domain operator & (const Domain &vs1, const Domain &vs2)
 Intersection of domains.

Domain operator- (const Domain &vs1, const Domain &vs2)
 Difference.

bool operator== (const Domain &v1, const Domain &v2)
 Equality.

bool operator!= (const Domain &v1, const Domain &v2)
 Inequality.


Detailed Description

A set of variables of a BDD to represent a component of a relation.

A domain is created by giving the base variable, the number of variables, and a step value. The last two variables can be omitted. Some common usage patters:

Domain d1(0, 5); Domain d2(5, 5); Domain d3(0, 5, 2); Domain d4(1, 5, 2);

Giving the following sets:

d1 = {0,1,2,3,4} d2 = {5,6,7,8,9} d3 = {0,2,4,6,8} d4 = {1,3,5,7,9}

d3 and d4 are interleaved, a common way to represent a the state components of a transition relation.


Member Typedef Documentation

typedef const_iterator gbdd::Domain::iterator
 

Alias for const_iterator.

typedef unsigned long int gbdd::Domain::Var
 


Constructor & Destructor Documentation

gbdd::Domain::Domain  ) 
 

Creates an empty domain.

gbdd::Domain::Domain Var  from,
unsigned int  n_vars = 1,
unsigned int  step = 1
[explicit]
 

Creates a finite domain.

Parameters:
from The first variable
n_vars The number of variables
step Step starting from for the variables
Returns:
The finite domain {from + i * step | 0 <= n_vars < n_vars }

gbdd::Domain::Domain const Domain infinite_base,
const Domain from
[explicit]
 

Lay out one domain onto an infinite base.

Parameters:
infinite_base The base to lay out domain onto
from The domain to lay out
Returns:
The domain such that each i variable in from is now the i variable in infinite_base

gbdd::Domain::Domain const set< Var > &  s  ) 
 

Creates a finite domain given a set of variables.

Parameters:
s The set of variables
Returns:
A domain containing the variables in s


Member Function Documentation

Domain::const_iterator gbdd::Domain::begin  )  const
 

Get iterator pointing to beginning of set.

Returns:
Iterator pointing to beginning

Domain gbdd::Domain::cut_to_same_size const Domain d  )  const
 

Remove highest variables to get same size as another domain.

Parameters:
d Domain to compare with
Returns:
A domain with the lowest variables keeping as many as there are in d

Domain::const_iterator gbdd::Domain::end  )  const
 

Get iterator pointing to end of set.

Returns:
Iterator pointing to end

Domain gbdd::Domain::first_n unsigned int  n  )  const
 

Get a domain with the lowest variables.

Parameters:
n How many variables in the new domain
Returns:
A new domain with the n lowest variables

Domain::Var gbdd::Domain::higher  )  const
 

Get a variable higher then any variable in domain.

Requires a finite domain

Returns:
A variable such that there are no variable in the domain less than this variable

Domain::Var gbdd::Domain::highest  )  const
 

Get the highest variable in domain.

Requires a non-empty domain

Returns:
The highest variable in domain

Domain gbdd::Domain::infinite Var  from = 0,
Var  step = 1
[static]
 

Creates an infinite domain.

Parameters:
from The first variable
step Step starting from for the variables
Returns:
The infinite domain {from + i * step | i >= 0 }

bool gbdd::Domain::is_compatible const Domain d2  )  const
 

Checks if two domains are compatible.

Two domains are compatible iff they contain the same number of variables

Parameters:
d2 Second domain
Returns:
Whether either this domain and d2 are both infinite or have the same number of variables

bool gbdd::Domain::is_disjoint const Domain d2  )  const
 

Checks if two domains are disjoint.

Parameters:
d2 Second domain
Returns:
Whether this domain and d2 do not have common variables

bool gbdd::Domain::is_empty  )  const
 

Checks if domain is empty.

Returns:
Whether the domain is empty

bool gbdd::Domain::is_finite  )  const
 

Checks if domain is finite.

Returns:
Whether the domain is finite

bool gbdd::Domain::is_infinite  )  const
 

Checks if domain is infinite.

Returns:
Whether the domain is infinite

Domain gbdd::Domain::last_n unsigned int  n  )  const
 

Get a domain with the highest variables.

Parameters:
n How many variables in the new domain
Returns:
A new domain with the n highest variables

Domain::Var gbdd::Domain::lowest  )  const
 

Get the lowest variable in domain.

Requires a non-empty domain

Returns:
The lowest variable in domain

Domain::VarMap gbdd::Domain::map_vars const Domain vs1,
const Domain vs2
[static]
 

map_vars:

Parameters:
vs1 First set of variables
vs2 Second set of variables
Build mapping between set of variables. Size of vs1 must be equal to the size of vs2.

Returns:
Mapping from vs1 to vs2, identity mapping for variables not in vs1

Domain & gbdd::Domain::operator &= const Domain vs  ) 
 

Intersection assignment.

Same as domain = domain & vs

Parameters:
vs Domain to intersect
Returns:
Itself

Domain gbdd::Domain::operator * unsigned int  v  )  const
 

Multiply every variable in domain.

Parameters:
v Value to multiply with
Returns:
A domain containing all variables mulitplied by v

bool gbdd::Domain::operator() Var  v  )  const
 

Membership test.

Parameters:
v Variable to test
Returns:
Whether v is in the domain

Domain gbdd::Domain::operator+ unsigned int  v  )  const
 

Add to every variable in domain.

Parameters:
v Value to add with
Returns:
A domain with all variables added v

Domain gbdd::Domain::operator- unsigned int  v  )  const
 

Subtract from every variable in domain.

Parameters:
v Value to subtract
Returns:
A domain with all variables subtracted v

Domain & gbdd::Domain::operator-= const Domain vs  ) 
 

Difference assignment.

Same as domain = domain - vs

Parameters:
vs Domain to subtract with
Returns:
Itself

Domain gbdd::Domain::operator/ unsigned int  v  )  const
 

Divide every variable in domain.

Parameters:
v Value to divide with
Returns:
A domain containing all variables divided by v

Domain & gbdd::Domain::operator|= const Domain vs  ) 
 

Union assignment.

Same as domain = domain | vs

Parameters:
vs Domain to add
Returns:
Itself

unsigned int gbdd::Domain::size  )  const
 

Get size of domain.

Gets the number of variables in the domain. This requires that the domain is finite.

Returns:
The number of variables in this domain

Domain gbdd::Domain::sup const Domain vs1,
const Domain vs2
[static]
 

Get largest domain.

Parameters:
vs1 First set
vs2 Second set
Returns:
Either vs1 or vs2 such that the returned set has at more or the same cardinality as both of them

template<class _UnaryFunction>
Domain gbdd::Domain::transform _UnaryFunction  op  )  const
 

transform elements of domain

Parameters:
op Unary operation
Returns:
The domain such that each variable v is substituted by op(v)


Friends And Related Function Documentation

friend class Domain::const_iterator [friend]
 

Domain operator & const Domain vs1,
const Domain vs2
[friend]
 

Intersection of domains.

Parameters:
vs1 First domain
vs2 Second domain
Returns:
The domain containing all the variables that is both in vs1 and vs2

bool operator!= const Domain v1,
const Domain v2
[friend]
 

Inequality.

Parameters:
v1 First domain
v2 Second domain
Returns:
Whether v1 and v2 are not equal.

Domain operator- const Domain vs1,
const Domain vs2
[friend]
 

Difference.

Parameters:
vs1 First domain
vs2 Second domain
Returns:
The domain containing all the variables that is in vs1 but not in vs2

ostream& operator<< ostream &  s,
const Domain vs
[friend]
 

Sends a textual description of a domain into a stream.

Parameters:
s Stream to send to
vs Domain to describe

bool operator== const Domain v1,
const Domain v2
[friend]
 

Equality.

Parameters:
v1 First domain
v2 Second domain
Returns:
Whether v1 and v2 are equal.

Domain operator| const Domain vs1,
const Domain vs2
[friend]
 

Union of domains.

Parameters:
vs1 First domain
vs2 Second domain
Returns:
The domain containing all the variables that is in vs1 or vs2


The documentation for this class was generated from the following files:
Generated on Thu Aug 12 13:21:43 2004 for gbdd by doxygen 1.3.6