Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB > Class Template Reference

An Antichain of minimal elements. More...

#include <antichain.h>

Public Member Functions
void	add_unchecked (const A &a, const pb_set &b, bool dirty=false)
	Add to the antichain an element without checking if the invariant is preserved.
void	add (const A &a, const pb_set &b, bool dirty=false)
	Add element (a,b) to the antichain. More...
bool	contains (const A &a, const pb_set &b) const
	Tests if the element (a,b) or a smaller element is already contained in the antichain. More...
unsigned	size () const
	Returns the size of the antichain. More...
void	clean_dirty ()
	Remove elements marked as dirty.
void	print (std::ostream &out, const printer_base< A > &printerA=printer< A >(), const printer_base< B > &printerB=printer< B >()) const
	Print the antichain on the screen. More...

Detailed Description

template<class A, class B, class HashA = std::hash<A>, class HashB = std::hash<B>, class CompareA = std::equal_to<A>, class CompareB = std::equal_to<B>>
class Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB >

An Antichain of minimal elements.

An antichain constains pairs of type (a,b), where a ∈ A and b ⊆ B. So a is a single element and b a set. There is a relation defined between the elements (a1,b1) ⊑ (a2,b2) iff a1=a2 ∧ b1 ⊆ b2. The antichain as an invariant that needs to be maintained by add() as follows: ∀ a1,b1,a2,b2. ¬[(a1,b1) ⊑ (a2,b2)] ∧ ¬[(a2,b2) ⊑ (a1,b1)].

The antichain keeps for each pair (a,b) a dirty flag that tracks if this element is dirty. If it is then it is removed when the antichain_algo restarts.

Template Parameters

A	The type of elements A
B	The type of elements B

Member Function Documentation

template<class A, class B, class HashA = std::hash<A>, class HashB = std::hash<B>, class CompareA = std::equal_to<A>, class CompareB = std::equal_to<B>>

void Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB >::add ( const A &  a, const pb_set &  b, bool  dirty = false  )

inline

Add element (a,b) to the antichain.

It preserve the antichain invariant by removing all a1,b1 (a,b) ⊑ (a1,b1) and by not adding (a,b) if there is any a1,b1 (a1,b1) ⊑ (a,b)

template<class A, class B, class HashA = std::hash<A>, class HashB = std::hash<B>, class CompareA = std::equal_to<A>, class CompareB = std::equal_to<B>>

bool Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB >::contains ( const A &  a, const pb_set &  b  ) const

inline

Tests if the element (a,b) or a smaller element is already contained in the antichain.

Returns

True if there is any a1,b1 in the antichain, such that (a1,b1) ⊑ (a,b)

template<class A, class B, class HashA = std::hash<A>, class HashB = std::hash<B>, class CompareA = std::equal_to<A>, class CompareB = std::equal_to<B>>

void Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB >::print ( std::ostream &  out, const printer_base< A > &  printerA = printer<A>(), const printer_base< B > &  printerB = printer<B>()  ) const

inline

Print the antichain on the screen.

Parameters

out	The stream to print to
printerA	The state printer for states of type A
printerB	The state printer for states of type B

template<class A, class B, class HashA = std::hash<A>, class HashB = std::hash<B>, class CompareA = std::equal_to<A>, class CompareB = std::equal_to<B>>

unsigned Limi::internal::antichain< A, B, HashA, HashB, CompareA, CompareB >::size ( ) const

inline

Returns the size of the antichain.

Returns

unsigned The number of different elements of A in the antichain.

---

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

• Limi/internal/antichain.h