Polymake Template Library (PTL): Main Page
Polymake Template Library (PTL)  3.1
Polymake Template Library (PTL) Documentation

Design Principles

Container-centric view

PTL is based on STL and makes exhaustive use of the three main concepts of the latter: containers, iterators, and functors. There is a subtle difference, however, in the implementation of algorithms: in STL, they are designed to work with iterators, while in PTL the most of them accept containers as arguments. PTL containers are more than pure data structures, they bear some additional semantics, in that they belong to one of the generic families. See http://www.cplusplus.com/reference/stl/ for a description of STL's container concept.

Besides real containers, which own their data as prescribed by the standard, PTL makes heavy use of Container Manipulations. The latter implement though the standard container interface, but do not possess any data at all; instead, they refer to other container objects supplying the data items. There are three kinds of pseudo-containers in PTL: alias_sec alias, masquerade_sec masquerade, and lazycontainers".

Lazy evaluation

Many operators defined for PTL container classes, such as vector and matrix arithmetic, set-theoretical operations, etc., don't perform the computations immediately, but rather create a temporary object which "remembers" the operands and the operation and evaluates it later, on demand. This is a well-known technique called lazy evaluation, sometimes also referred to as expression templates. It helps to spare unnecessary computations and copying of objects.

The lazy objects fit well in the container concept of PTL, as they always belong to the same generic family and implement the same container interface as the result of the real operation would do.

See also

Container Classes

Set Types

  • Bitset is a container class for dense sets of integers. Data representation is a bit string as implemented in the GNU Multiprecision Library (mpz_t).
  • Set is a container class for sparse sets of ordered elements. Data representation as a modified kind of AVL tree.
  • PowerSet is a Set of Sets, providing methods for adding elements while preserving subset or superset independence.

Vector Types

The vector class family implement vectors in the usual algebraic notion. It contains three persistent vector types with different data storage organization. These implementations result in performance differences for various functions on vectors.

  • Vector holds the elements in a contiguous array.
  • SparseVector is an associative container with element indices (coordinates) as keys; elements equal to the default value (ElementType(), which is 0 for most numerical types) are not stored, but implicitly encoded by the gaps in the key set. It is based on an AVL tree.
  • FixedVector is a built-in array of a fixed dimension decorated with the common vector interface.

Matrix Types

The matrix class family implement matrices in the usual algebraic notion. It contains three persistent matrix types with different data storage organization.

  • Matrix holds the elements in a contiguous array.
  • SparseMatrix is a two-dimensional associative array with row and column indices as keys; elements equal to the default value (ElementType(), which is 0 for most numerical types) are not stored, but implicitly encoded by the gaps in the key set. Each row and column is organized as an AVL::tree.
  • ListMatrix is a list of row vectors. Based on std::list. Can be parameterized with any persistent vector type".

Other Container Types

Generic Class Families

Number Types

These are borrowed from GMP and wrapped.

Classes Useful for Computions in Geometric Combinatorics