This is the user interface class to manipulate homomorphisms. More...

#include <Hom.h>

Inheritance diagram for Hom:

Collaboration diagram for Hom:

Public Types
typedef GDDD	NodeType

Public Member Functions
Public Constructors.
Default constructor builds identity homomorphism.
	Hom (const GHom &h=GHom::id)
	Build an Hom from a GHom. More...

	Hom (const Hom &h)
	Copy constructor. Maintains reference count. More...

	Hom (const GDDD &d)
	Constructs a constant homomorphism. More...

	Hom (int var, int val, const GHom &h=GHom::id)
	Left concatenation of a single arc DDD. More...

	~Hom ()
	Destructor maintains reference counting. More...

Assignment operators.
Hom &	operator= (const GHom &)
	Overloaded behavior for assignment operator, maintains reference counting. More...

Hom &	operator= (const Hom &)
	Overloaded behavior for assignment operator, maintains reference counting. More...

Static Public Attributes
Public Constructors
static const GHom	id
	Elementary homomorphism Identity, defined as a constant. More...

Private Attributes
const _GHom *	concret
	The real implementation class. More...

Comparisons for hash and map storage
bool	operator== (const GHom &h) const
	Comparison between Homomorphisms. More...

bool	operator!= (const GHom &h) const
	Comparison between Homomorphisms. More...

bool	operator< (const GHom &h) const
	Total ordering function between Hom. More...

bool	is_selector () const
	This predicate is true if the homomorphism global behavior is only to prune some paths. More...

const range_t	get_range () const
	Returns the range for this homomorphism, i.e. the dual of skip_variable. More...

GHom	invert (const GDDD &pot) const
	returns the predescessor homomorphism, using pot to determine variable domains More...

GDDD	has_image (const GDDD &d) const
	returns true if and only if h(d) != SDD::null More...

GHom	negate () const
	returns a negation of a selector homomorphism h, such that h.negate() (d) = d - h(d) More...

GDDD	operator() (const GDDD &d) const
	Evaluation operator. More...

GDDD	eval (const GDDD &d) const
	Evaluation function : users should use operator() instead of this. More...

bool	skip_variable (int var) const

GHom	compose (const GHom &r) const

int	refCounter () const
	Accessor to visualize the reference count of the concret instance. More...

typedef d3::set< int >::type	range_t

typedef range_t::const_iterator	range_it

static const range_t	full_range = GHom::range_t()
	The full_range : that targets everyone. More...

static GHom	add (const d3::set< GHom >::type &set)
	A constructor for a union of several homomorphisms. More...

static GHom	ccompose (const d3::set< GHom >::type &set)
	A constructor for a commutative composition of several homomorphisms. More...

Memory Management
void	mark () const
	For garbage collection internals. Marks a GHom as in use in garbage collection phase. More...

size_t	hash () const
	For storage in a hash table. More...

static unsigned int	statistics ()
	Returns unicity table current size. Gives the number of different _GHom created and not yet destroyed. More...

static void	pstats (bool reinit=true)
	Prints some statistics to std::cout. More...

static void	garbage ()
	For garbage collection. More...

Detailed Description

This is the user interface class to manipulate homomorphisms.

The only difference with Hom is that it implements reference counting so that instances of Hom are not collected upon MemoryManager::garbage().

Member Typedef Documentation

◆ NodeType

typedef GDDD GHom::NodeType

inherited

◆ range_it

typedef range_t::const_iterator GHom::range_it

inherited

◆ range_t

typedef d3::set<int>::type GHom::range_t

inherited

Constructor & Destructor Documentation

◆ Hom() [1/4]

Hom::Hom ( const GHom & h = GHom::id )

Build an Hom from a GHom.

References GHom::concret, and _GHom::refCounter.

◆ Hom() [2/4]

Hom::Hom ( const Hom & h )

Copy constructor. Maintains reference count.

References GHom::concret, and _GHom::refCounter.

◆ Hom() [3/4]

Hom::Hom ( const GDDD & d )

Constructs a constant homomorphism.

References GHom::concret, and _GHom::refCounter.

◆ Hom() [4/4]

Hom::Hom	(	int	var,
		int	val,
		const GHom &	h = `GHom::id`
	)

Left concatenation of a single arc DDD.

This is provided as a convenience and to avoid the inefficiency if we build a node pointing to GSDD::one and then concatenate something to it. Applied to a SDD d, this homomorphism will return var–val->h(d).

Parameters

var	the variable labeling the node to left concat
val	the set of values labeling the arc
h	the homomorphism to apply on the argument d. This defaults to GSHom::id.

References GHom::concret, and _GHom::refCounter.

◆ ~Hom()

Hom::~Hom ( )

Destructor maintains reference counting.

Note that the destructor does not truly reclaim memory, MemoryManager::garbage() does that.

References GHom::concret, and _GHom::refCounter.

Member Function Documentation

◆ add()

GHom GHom::add ( const d3::set< GHom >::type & set )

staticinherited

A constructor for a union of several homomorphisms.

Note that for canonisation and optimization reasons, union is an n-ary and commutative composition operator. Use of this constructor may be slightly more efficient than using operator+ multiple times. H({h1,h2, ..hn}) (d) = sum_i h_i (d).

Parameters

set	the set of homomorphisms to put in the union.

Todo:: std::set not very efficient for storage, replace by a sorted vector ?

References canonical, GHom::GHom(), and GDDD::null.

Referenced by Add::invert(), _setVarConst::invert(), And::negate(), and Add::skip_variable().

◆ ccompose()

GHom GHom::ccompose ( const d3::set< GHom >::type & set )

staticinherited

A constructor for a commutative composition of several homomorphisms.

It's up to user to ensure pairwise commutatitivity off all arguments in the set

Parameters

set	the set of homomorphisms to put in the composition.

Todo:: std::set not very efficient for storage, replace by a sorted vector ?

References canonical, and GHom::id.

Referenced by Add::negate().

◆ compose()

GHom GHom::compose ( const GHom & r ) const

inherited

References _GHom::compose(), and GHom::concret.

Referenced by nsMLHom::ConstantUp::eval().

◆ eval()

GDDD GHom::eval ( const GDDD & d ) const

inherited

Evaluation function : users should use operator() instead of this.

This evaluation function does not use the cache, it is called in case of cache miss in the call to operator().

Parameters

d	the argument DDD

Returns: h(d)

References GHom::concret, and _GHom::eval_skip().

Referenced by _DED_Hom::eval().

◆ garbage()

void GHom::garbage ( )

staticinherited

For garbage collection.

WARNING Do not use this function directly !! Use MemoryManager::garbage() to ensure proper reference counting and cache cleanup. Garbage collection algorithm is a simple two phase mark and sweep : in phase mark, all nodes with positive reference counts are marked, as well as their descendants, recursively. In phase sweep, all nodes which are unmarked are destroyed. This avoids maintaining reference counts during operation : only external references made through the DDD class are counted, and no recursive reference counting is needed.

References cache, canonical, Cache< FuncType, ParamType, ResType, EvalFunc >::clear(), imgcache, and _GHom::marking.

Referenced by MemoryManager::garbage().

◆ get_range()

const GHom::range_t GHom::get_range ( ) const

inherited

Returns the range for this homomorphism, i.e. the dual of skip_variable.

References GHom::concret, and _GHom::get_range().

Referenced by commutative(), NotCond::get_range(), Compose::get_range(), Fixpoint::get_range(), and notInRange().

◆ has_image()

GDDD GHom::has_image ( const GDDD & d ) const

inherited

returns true if and only if h(d) != SDD::null

References imgcache, Cache< FuncType, ParamType, ResType, EvalFunc >::insert(), and GDDD::null.

Referenced by Inter::has_image(), NotCond::has_image(), Add::has_image(), LeftConcat::has_image(), RightConcat::has_image(), Fixpoint::has_image(), sns::LocalApply::has_image(), and _GHom::has_image_skip().

◆ hash()

size_t GHom::hash ( ) const

inlineinherited

For storage in a hash table.

References GHom::concret, and ddd::knuth32_hash().

Referenced by _DED_Hom::hash(), Mult::hash(), Inter::hash(), NotCond::hash(), Compose::hash(), LeftConcat::hash(), RightConcat::hash(), Minus::hash(), Fixpoint::hash(), nsMLHom::GHomAdapter::hash(), nsMLHom::ConstantUp::hash(), and sns::LocalApply::hash().

◆ invert()

GHom GHom::invert ( const GDDD & pot ) const

inherited

returns the predescessor homomorphism, using pot to determine variable domains

References GHom::concret, and _GHom::invert().

Referenced by Mult::invert(), Inter::invert(), Compose::invert(), Minus::invert(), Fixpoint::invert(), and sns::LocalApply::invert().

◆ is_selector()

bool GHom::is_selector ( ) const

inherited

This predicate is true if the homomorphism global behavior is only to prune some paths.

References GHom::concret, and _GHom::is_selector().

Referenced by commutative(), Mult::is_selector(), Inter::is_selector(), Compose::is_selector(), Minus::is_selector(), Fixpoint::is_selector(), sns::LocalApply::is_selector(), ITE(), and operator*().

◆ mark()

void GHom::mark ( ) const

inherited

For garbage collection internals. Marks a GHom as in use in garbage collection phase.

References GHom::concret, _GHom::mark(), and _GHom::marking.

Referenced by Fixpoint::eval(), Mult::mark(), Inter::mark(), NotCond::mark(), Compose::mark(), LeftConcat::mark(), RightConcat::mark(), Minus::mark(), Fixpoint::mark(), sns::LocalApply::mark(), and MemoryManager::mark().

◆ negate()

GHom GHom::negate ( ) const

inherited

returns a negation of a selector homomorphism h, such that h.negate() (d) = d - h(d)

References GHom::concret, and _GHom::negate().

Referenced by NotCond::has_image(), and Inter::negate().

◆ operator!=()

bool GHom::operator!= ( const GHom & h ) const

inlineinherited

Comparison between Homomorphisms.

Note that comparison is based on "concret" address in unicity table.

Parameters

h	the hom to compare to

Returns: true if the nodes are NOT equal.

References GHom::concret.

◆ operator()()

GDDD GHom::operator() ( const GDDD & d ) const

inherited

Evaluation operator.

Homomorphisms overload operator(), so they can be directly applied to DDD nodes. Note that evaluation through this operator uses and updates a cache.

Parameters

d	the DDD to apply this h to.

Returns: h(d), the result of applying this h to d.

References cache, GHom::concret, _GHom::eval(), _GHom::immediat, Cache< FuncType, ParamType, ResType, EvalFunc >::insert(), and GDDD::null.

◆ operator<()

bool GHom::operator< ( const GHom & h ) const

inherited

Total ordering function between Hom.

Note that comparison is based on chronological ordering of creation, and delegated to "concret". Unlike comparison on addresses in unicity table, this ensures reproductible results. This ordering is necessary for hash and map storage of GHom.

Parameters

h	the node to compare to

Returns: true if argument h is greater than "this".

References GHom::concret.

◆ operator=() [1/2]

Hom & Hom::operator= ( const GHom & h )

Overloaded behavior for assignment operator, maintains reference counting.

References GHom::concret, and _GHom::refCounter.

◆ operator=() [2/2]

Hom & Hom::operator= ( const Hom & h )

Overloaded behavior for assignment operator, maintains reference counting.

References GHom::concret, and _GHom::refCounter.

◆ operator==()

bool GHom::operator== ( const GHom & h ) const

inlineinherited

Comparison between Homomorphisms.

Note that comparison is based on "concret" address in unicity table.

Parameters

h	the hom to compare to

Returns: true if the nodes are equal.

◆ pstats()

void GHom::pstats ( bool reinit = true )

staticinherited

Prints some statistics to std::cout.

Mostly used in debug and development phase.

Todo:: allow output in other place than cout. Clean up output.

References GHom::_GHom, cache, and canonical.

Referenced by MemoryManager::pstats().

◆ refCounter()

int GHom::refCounter ( ) const

inherited

Accessor to visualize the reference count of the concret instance.

See _GHom::refCounter for details.

References GHom::concret, and _GHom::refCounter.

◆ skip_variable()

bool GHom::skip_variable ( int var ) const

inherited

References GHom::concret, and _GHom::skip_variable().

Referenced by nsMLHom::GHomAdapter::skip_variable().

◆ statistics()

unsigned int GHom::statistics ( )

staticinherited

Returns unicity table current size. Gives the number of different _GHom created and not yet destroyed.

References canonical.

Referenced by Statistic::load(), and MemoryManager::nbHom().

Member Data Documentation

◆ concret

const _GHom* GHom::concret

privateinherited

The real implementation class.

All true operations are delagated on this pointer. Construction/destruction take care of ensuring concret is only instantiated once in memory.

Referenced by GHom::compose(), GHom::eval(), _GHom::get_concret(), GHom::get_range(), GHom::hash(), Hom(), GHom::invert(), GHom::is_selector(), GHom::mark(), GHom::negate(), GHom::operator!=(), GHom::operator()(), GHom::operator<(), operator=(), GHom::refCounter(), GHom::skip_variable(), and ~Hom().

◆ full_range

const GHom::range_t GHom::full_range = GHom::range_t()

staticinherited

The full_range : that targets everyone.

Referenced by _GHom::get_range().

◆ id

const GHom GHom::id

staticinherited

Elementary homomorphism Identity, defined as a constant.

id(d) = d

Referenced by buildUnionParameters(), GHom::ccompose(), _GHom::compose(), StrongMLHom::eval(), And::eval(), nsMLHom::Identity::eval(), nsMLHom::GHomAdapter::eval(), _GHom::eval_skip(), Add::get_have_id(), Fixpoint::has_image(), sns::Fixpoint::has_image(), _GHom::has_image_skip(), Mult::invert(), And::invert(), Minus::invert(), Fixpoint::invert(), Constant::negate(), operator*(), _VarCompState::phi(), _setVarConst::phi(), varEqVar(), varGeqVar(), and varLeqVar().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Static Public Attributes

Private Attributes

Comparisons for hash and map storage

Memory Management

Detailed Description

Member Typedef Documentation

◆ NodeType

◆ range_it

◆ range_t

Constructor & Destructor Documentation

◆ Hom() [1/4]

◆ Hom() [2/4]

◆ Hom() [3/4]

◆ Hom() [4/4]

◆ ~Hom()

Member Function Documentation

◆ add()

◆ ccompose()

◆ compose()

◆ eval()

◆ garbage()

◆ get_range()

◆ has_image()

◆ hash()

◆ invert()

◆ is_selector()

◆ mark()

◆ negate()

◆ operator!=()

◆ operator()()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ pstats()

◆ refCounter()

◆ skip_variable()

◆ statistics()

Member Data Documentation

◆ concret

◆ full_range

◆ id