FaceMap Class

A special case of an associative container, whose keys are ordered sets. It is implemented as a recursively nested AVL tree: The topmost tree uses the first set element as a local search key, and his nodes contain second-level trees, using in turn the second set element as a local search key, and so on.

The main purpose of the FaceMap is to collect faces from a polytope face lattice or a simplicial complex, hence the name. The idea came from Marc E. Pfetsch and Volker Kaibel, the authors of the face lattice enumeration algorithm implemented in polymake.

Construction

The template parameter Traits should be a traits class defining all necessary information about the data to be stored in the FaceMap:

typename key_type;

typename key_comparator_type;

Element type and element comparator of the ordered sets being the search keys of the map.

typename data_type;

Associated data type ("payload") stored in the map.

static data_type initialize_data();

Should return an initial value to be stored in the new map entry.

static bool unvisited(const data_type&);

Should return true if the map entry looks like unchanged since it was created. Note that if the initial value belongs to the valid payload value set, all map entries will look like "visited", in particular those that were never stored directly, but whose search keys are proper subsets of the keys of some really stored entries.

An example of a valid traits class for FaceMap is struct face_traits defined in face_lattice_tools.h.

Data access

FaceMap implements the immutable Forward Container interface. The iterator and const_iterator is the same read-only iterator class. Unlike std::map or Map, it does not point to a (key, value) pair. Dereferencing the iterator yields a GenericSet being the entry key; method iterator::data() gives access to the payload data. Note: The FaceMap::size() method physically enumerates all entries!

Prerequisits

Introduction

Construction

Data access