Public Member Functions | |
| FacetList (int n_vertices=0) | |
| Create an empty list. | |
| 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) | |
| 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 (IndexConsumer ic) |
| If you want to gather the old ids, pass an output iterator 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 Set> | |
| iterator | insert (const GenericSet< Set, int, operations::cmp > &f) |
| Add a new facet without checking the inclusion relation to the existing facets. | |
| template<typename Set> | |
| void | push_back (const GenericSet< Set, int, operations::cmp > &f) |
| Add a facet to the list. | |
| template<typename Set> | |
| int | erase (const GenericSet< Set, int, operations::cmp > &f) |
| Find the facet equal to the given vertex set and remove it from the list. | |
| void | erase (const iterator &where) |
| Remove the facet pointed to by the given iterator. | |
| template<typename Set> | |
| int | eraseMax (const GenericSet< Set, int, operations::cmp > &f) |
| The same as insertMax(), but without adding any new facet. Returns the number of facets actually removed. | |
| template<typename Set> | |
| int | eraseMin (const GenericSet< Set, int, operations::cmp > &f) |
| The same as insertMin(), but without adding any new facet. Returns the number of facets actually removed. | |
| template<typename Set> | |
| bool | insertMax (const GenericSet< Set, int, operations::cmp > &f) |
| template<typename Set> | |
| bool | insertMin (const GenericSet< Set, int, operations::cmp > &f) |
| template<typename Set, typename Consumer> | |
| bool | insertMax (const GenericSet< Set, int, operations::cmp > &f, Consumer consumer) |
| template<typename Set, typename Consumer> | |
| bool | insertMin (const GenericSet< Set, int, operations::cmp > &f, Consumer consumer) |
| Opposite of the above. | |
| template<typename Set> | |
| bool | replaceMax (const GenericSet< Set, int, operations::cmp > &f) |
| template<typename Set> | |
| bool | replaceMin (const GenericSet< Set, int, operations::cmp > &f) |
| Opposite of the above. | |
| template<typename Set, typename Consumer> | |
| bool | replaceMax (const GenericSet< Set, int, operations::cmp > &f, Consumer consumer) |
| ... with output consumer | |
| template<typename Set, typename Consumer> | |
| bool | replaceMin (const GenericSet< Set, int, operations::cmp > &f, Consumer consumer) |
| ... with output consumer | |
Friends | |
| const LexOrdered & | lex_ordered (const FacetList &c) |
The main invariant is that all facets are mutually inclusion-free. The primary design goal of this class is effective 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.
The iterators over the facet list have an additional method index() retrieving the unique integer id assigned to each facet when it was being 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 take effect on the id generated for the next facet.
| pm::FacetList::FacetList | ( | int | n_vertices = 0 |
) | [inline, explicit] |
Create an empty list.
Allocate the internal data structures capable of handling sets of vertices from the range [0 .. n_vertices-1] in advance. The vertex range can be dynamically expanded later, by insert* and push_back operations, with reallocation costs O(n_vertices).
| iterator pm::FacetList::insert | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
Add a new facet without checking the inclusion relation to the existing facets.
It should be guaranteed by the application logic, that the non-inclusion invariant is not violated! There is no debugging mode that could detect this.
The operation costs are O(dim + deg).
| void pm::FacetList::push_back | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
Add a facet to the list.
This method is primarily thought of as an construction aid, if none of the explicit constructors above suites, and enables the use of the convenient std::back_inserter. The operation costs are O(dim).
The given facet must be lexicographically greater than all facets added before.
| int pm::FacetList::erase | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
Find the facet equal to the given vertex set and remove it from the list.
Returns 1 if a facet was removed or 0 if no matching facet was found.
The operation costs are O(dim + deg).
| bool pm::FacetList::insertMax | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
Add a new facet if and only if there are no facets including it. If this holds, remove also all facets that are included in the new one. Return true if the new facet was really included.
The average operation costs are O(dim2 deg).
| bool pm::FacetList::insertMin | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
The opposite of insertMax(const GenericSet<Set, int, operations::cmp>& f): add a new facet if and only if there are no facets included in it, remove all facets including the new facet.
| bool pm::FacetList::insertMax | ( | const GenericSet< Set, int, operations::cmp > & | f, | |
| Consumer | consumer | |||
| ) | [inline] |
Same as insertMax(const GenericSet<Set, int, operations::cmp>& f) except for a second argument. This iterator gathers the facets removed by the operation. It must implement the output iterator interface; its value_type must be either int, if it is collecting the facet id's, or GenericSet<...,int>, if it is collecting the complete facets.
| bool pm::FacetList::replaceMax | ( | const GenericSet< Set, int, operations::cmp > & | f | ) | [inline] |
Slightly optimized versions of insertMax. Assumes that the FacetList object already has all columns corresponding to the vertices of a new facet, and therefore does not need to be expanded.
| const LexOrdered& lex_ordered | ( | const FacetList & | c | ) | [friend] |
Another view on the list, visiting the facets in lexicographical order. The result type is a masquerade reference pointing to a GenericSet< GenericSet<int> >.
1.5.6