Inherits pm::modified_container_impl< Top, Params, TReversible >, and pm::matrix_col_methods< TMatrix, ColCategory >.
|
| FacetList (Int n_vertices=0) |
| Create an empty list. More...
|
|
template<typename Iterator > |
| FacetList (Iterator &&src, Iterator &&src_end) |
| Initialize the facets from the input sequence. The items obtained by dereferencing src must be sets of cardinals (of type GenericSet).
|
|
template<typename Iterator > |
| FacetList (Int n_vertices, Iterator &&src, std::enable_if_t< assess_iterator< Iterator, check_iterator_feature, end_sensitive >::value &&assess_iterator_value< Iterator, isomorphic_types, Set< Int >>::value, std::nullptr_t >=nullptr) |
| As above, but avoiding reallocation during the construction. The facets supplied by src may not contain vertices outside the range [0, n_vertices-1].
|
|
void | swap (FacetList &l) |
| Swap the contents of two lists in a most efficient way.
|
|
void | clear () |
| Make the list empty, release all allocated resources.
|
|
Int | size () const |
| Return number of facets in list.
|
|
bool | empty () const |
| True if empty.
|
|
Int | n_vertices () const |
| Returns the number of vertices.
|
|
void | squeeze () |
| Renumber the facet ids consequently, starting with 0, thus eliminating the gaps.
|
|
template<typename IndexConsumer > |
void | squeeze (const IndexConsumer &ic) |
| If you want to gather the old ids, pass a binary functor as index_consumer.
|
|
void | skip_facet_id (Int amount=1) |
| Make an artificial gap in the generated facet id sequence. The facet inserted next will have an id amount greater than it would have had without this call.
|
|
template<typename TSet > |
iterator | insert (const GenericSet< TSet, Int, operations::cmp > &f) |
| Add a new facet without checking the inclusion relation to the existing facets. More...
|
|
template<typename TSet > |
void | push_back (const GenericSet< TSet, Int, operations::cmp > &f) |
| Add a facet to the list with least efforts. More...
|
|
template<typename TSet > |
Int | erase (const GenericSet< TSet, Int, operations::cmp > &f) |
| Find the facet equal to the given vertex set and remove it from the list. More...
|
|
void | erase (const iterator &where) |
| Remove the facet pointed to by the given iterator.
|
|
template<typename TSet > |
Int | eraseSupersets (const GenericSet< TSet, Int, operations::cmp > &f) |
| Erase all supersets of a given set. More...
|
|
template<typename TSet , typename Consumer > |
Int | eraseSupersets (const GenericSet< TSet, Int, operations::cmp > &f, Consumer consumer) |
| Erase all supersets of a given set. More...
|
|
template<typename TSet > |
Int | eraseSubsets (const GenericSet< TSet, Int, operations::cmp > &f) |
| Erase all subsets of a given set. More...
|
|
template<typename TSet , typename Consumer > |
Int | eraseSubsets (const GenericSet< TSet, Int, operations::cmp > &f, Consumer consumer) |
| Erase all subsets of a given set. More...
|
|
template<typename TSet > |
bool | insertMax (const GenericSet< TSet, Int, operations::cmp > &f) |
|
template<typename TSet > |
bool | insertMin (const GenericSet< TSet, Int, operations::cmp > &f) |
|
template<typename TSet , typename Consumer > |
bool | insertMax (const GenericSet< TSet, Int, operations::cmp > &f, Consumer consumer) |
|
template<typename TSet , typename Consumer > |
bool | insertMin (const GenericSet< TSet, Int, operations::cmp > &f, Consumer consumer) |
|
template<typename TSet > |
bool | replaceMax (const GenericSet< TSet, Int, operations::cmp > &f) |
|
template<typename TSet > |
bool | replaceMin (const GenericSet< TSet, Int, operations::cmp > &f) |
|
This is a collection of sets of integral numbers from a closed contiguous range [0..n-1], as one usually has to deal with when modeling simplicial complexes and related mathematical objects. Thus we will refer to the contained sets as facets, and to the set elements as vertices.
The class can efficiently maintain the property of all facets being mutually inclusion-free, although this property is not mandatory, it can be violated by the application if needed. The primary design goal of this class is efficient search, insertion, and removal of facets included in or including a given vertex set.
The data structure is a rectangular grid, similar to IncidenceMatrix, interwoven with a forest of suffix trees, indexed with the vertex number. This also provides the lexicographical facet ordering as a pleasant side effect. The whole thing is attached to a smart pointer with reference counting.
For complexity statements below we (ab-)use the term dimension (abbreviated as dim) for the number of vertices in a facet. Conversely, the degree (abbreviated as deg) of a vertex is the number of facets containing it.
FacetList implements STL's reversible container interface. During the iteration the facets appear in the chronological order, that is, as they were added to the list. Unlike std::list
, the size() method runs in constant time.
The elements of the list (facets) are of type GenericSet and implement the reversible container interface, too. However, there is no random access or cheap existence checks for single vertices; facets have to be scanned sequentially.
The iterators over the facet list have an additional method index()
retrieving the unique integer id assigned to each facet when it was inserted into the FacetList. A new id is generated by each call to any of the insert() methods, regardless whether the facet is eventually inserted or discarded as being dependent. Using methods squeeze() and skip_facet_id() you can affect the id generated for the next facet.