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 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 a vertex-facet incidence matrix,
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.
(Average, maximal, actual) dimension of a facet, that is, number of vertices in it.
(Average, maximal) degree of a vertex, that is, number of facets containing it.
explicit FacetList (int n_vertices=0);
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).
template <typename Iterator>
FacetList (Iterator src, end_sensitive);
Initialize the facets from the input sequence. The items obtained by dereferencing src
must be integral sets.
The only purpose of the dummy argument end_sensitive is to signal that the first argument src
has to be treated as an end-sensitive iterator.
A template constructor with a single argument would shadow all other constructors away!
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].
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(d);
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.
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.
Slightly optimized versions of insertMax and insertMin.
They assume that the FacetList object already has all columns corresponding to the
vertices of a new facet, and therefore does not need to be expanded.
FacetList implements the
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.
Another view on the list, visiting the facets in lexicographical order.
The result type is a masquerade reference;
it is a GenericSet of sets of integer.
const FacetList::col_type& col (int v) const;
Return a list of facets incident to the given vertex. It can be thought of as a column of the
vertex-facet incidence matrix, hence the name.
The list is a Forward Container;
for technical reasons, the facets are visited in the reversed chronological order.
Read a property from the polymake server.
Parse errors are reported by raising the std::iostream::failure exception in the constructor,
or via std::iostream::fail() flag in the input operator.