This assertion is checked only in the INDEX_CHECKS compilation mode.
(Average, maximal) degree of a vertex, that is, number of facets containing it.
Either a functor class satisfying the extended requirements
for unary operations, or
an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
This assertion is checked only in the AVL_CHECKS compilation mode.
(Average, maximal, actual) dimension of a facet, that is, number of vertices in it.
Either a functor class satisfying the extended requirements
for binary operations, or
an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt
(preferably expressed via the convenience typedef from namespace polymake::operations.
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 REFCOUNT.
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).
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);
Renumber the facet ids consequently, starting with 0, thus eliminating the gaps. 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.
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.
The second optional argument can be used to gather 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.
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.
int eraseMax (const GenericSet&);
int eraseMin (const GenericSet&);
template <typename FacetConsumer>
int eraseMax (const GenericSet&, FacetConsumer);
template <typename FacetConsumer>
int eraseMin (const GenericSet&, FacetConsumer);
The same as insertMax and insertMin, but without adding any new facet.
Return the number of facets actually removed.
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.
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.
Another view on the list, visiting the facets in lexicographical order.
The result type is a masquerade reference; it is a set 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.
The iterator over the column has index() method returning the id of the
facet being visited.