Scine::Molassembler::Temple::Poset< T > Class Template Reference

Data structure for partially ordered sets with support for gradual ordering discovery. More...

#include <Poset.h>

Data Structures
struct	Subset
	Subset of T values. More...

Public Types
using	const_iterator = typename std::vector< Subset >::const_iterator

Public Member Functions
template<typename Container >
	Poset (const Container &container)
	Container constructor. More...
template<typename Iter >
	Poset (Iter &&begin, Iter &&end)
	Range constructor. More...
template<typename Iter >
void	setUnorderedValues (Iter &&begin, Iter &&end)
	Sets the values in the specified range as the only unordered Subset. More...
template<typename Comparator >
void	orderUnordered (Comparator &&comparator)
	Adds order to unordered Subsets. More...
void	finalize ()
	Sets all subsets as ordered. More...
const_iterator	begin () const
const_iterator	end () const
std::string	toString () const
	Convert the Poset to a string representation for debug purposes. More...
const_iterator	find (const T &a) const
	Find an element. More...
boost::tribool	compare (const T &a, const T &b) const
	Less-than compare two elements in the poset. More...
std::vector< std::vector< T > >	extract ()
	Extracts the contained order, moving from each contained subset and clearing the Poset.

Private Attributes
std::vector< Subset >	subsets

Detailed Description

template<typename T>
class Scine::Molassembler::Temple::Poset< T >

Data structure for partially ordered sets with support for gradual ordering discovery.

If ordering of values is a complicated, emergent matter, this class can help you manage the mess and minimize the number of comparisons needed to establish ordering between values.

std::vector<int> values {4, 5, 6, 10, 11, 12};
Poset<int> poset {values};
// Split value by evenness
poset.orderUnordered([](int x, int y) { return (x % 2 == 0) > (y % 2 == 0); });
// poset is now: {4, 6, 10, 12}, {5, 11}
// Split values by greater-than
poset.orderUnordered(std::greater<>());
// poset is now totally ordered: {12}, {10}, {6}, {4}, {11}, {5}

Note

This class would probably benefit immensely from a pool allocator.

Constructor & Destructor Documentation

template<typename T >

template<typename Container >

Scine::Molassembler::Temple::Poset< T >::Poset ( const Container &  container )

inline

Container constructor.

Copies all values from the container

template<typename T >

template<typename Iter >

Scine::Molassembler::Temple::Poset< T >::Poset ( Iter &&  begin, Iter &&  end  )

inline

Range constructor.

Copies all values from the passed range

Member Function Documentation

template<typename T >

boost::tribool Scine::Molassembler::Temple::Poset< T >::compare ( const T &  a, const T &  b  ) const

inline

Less-than compare two elements in the poset.

Parameters

a	The first element
b	The second element

Exceptions

std::invalid_argument

If either element is not in the poset.

Complexity \(O(N)\)

Returns

A tribool in the following state:

• true if the first element is less than the second
• false if the second element is equal to or greater than the second
• indeterminate if ordering is unknown

template<typename T >

void Scine::Molassembler::Temple::Poset< T >::finalize ( )

inline

Sets all subsets as ordered.

Once all comparators are exhausted to find order in yet unordered Subsets, then those values that are still indistinguishable should be considered equal.

Complexity \(\Theta(S)\)

template<typename T >

const_iterator Scine::Molassembler::Temple::Poset< T >::find ( const T &  a ) const

inline

Find an element.

Complexity \(\Theta(N)\)

Parameters

a	element to search for

Returns

An iterator pointing to the Subset the element is contained in. If the element is in no Subset of the Poset, the iterator is the end iterator.

template<typename T >

template<typename Comparator >

void Scine::Molassembler::Temple::Poset< T >::orderUnordered ( Comparator &&  comparator )

inline

Adds order to unordered Subsets.

Template Parameters

Comparator

A callable object with the signature (const T&, const T&) -> bool

Parameters

comparator

An instance of Comparator, which returns true if the first argument is ordered less than the second argument. If two elements cannot be distinguished with the ordering imposed by comparator, then they should be equal, i.e. !(a < b) && !(b < a).

Complexity \(O(N^2)\)

template<typename T >

template<typename Iter >

void Scine::Molassembler::Temple::Poset< T >::setUnorderedValues ( Iter &&  begin, Iter &&  end  )

inline

Sets the values in the specified range as the only unordered Subset.

Complexity \(\Theta(N)\)

Template Parameters

Iter	The type of the iterator specifying the range

Parameters

begin	The begin iterator of the range of values
end	The end iterator of the range of values

template<typename T >

std::string Scine::Molassembler::Temple::Poset< T >::toString ( ) const

inline

Convert the Poset to a string representation for debug purposes.

Complexity \(\Theta(N)\)

---

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

• Molassembler/Temple/Poset.h