Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
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< Subsetsubsets
 

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
aThe first element
bThe second element
Exceptions
std::invalid_argumentIf 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
aelement 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
ComparatorA callable object with the signature (const T&, const T&) -> bool
Parameters
comparatorAn 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
IterThe type of the iterator specifying the range
Parameters
beginThe begin iterator of the range of values
endThe 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: