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.
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.
AVL tree is a kind of balanced binary search trees, allowing for logarithmic time
element find, insert, and delete operations. AVL trees are thoroughly discussed in D.E. Knuth's
The Art of Computer Programming
Vol. III, 6.2.3, pp 465ff.
AVL trees play the same role in the polymake library that the red-black trees have in STL:
a basis for the associative container classes. The current implementation differs from the
red-black trees in following detals:
In the leaf nodes so called thread pointers to the lexicographically next and
previous tree nodes are maintained. This reduces the amortized tree
traversal time by approximately 50%.
The key lookup procedure uses the comparator functor
instead of std::less, achieving the acceleration by 1.5 times in average
for non-trivial key types.
A tree created from a preordered key sequence is kept as a double-linked list up to the
first random access operation (key search). Since some container objects are accessed only
in sequential traversal loops during all their lifetime, this eliminates the overhead of
rebalancing the tree at its creation stage. The list-to-tree conversion takes linear time
and don't involve rebalancing at all.
Look for an element, using an alternative key comparator.
For each possible pair of keys, the given comparator is required to obtain either the same result
as the container's built-in comparator, or zero, signaling a 'fuzzy match'.
Find an element with the given key or create it at the right position.
Store data in the associated data field of the tree element (applicable
to Map,SparseVector, rows and columns of a SparseMatrix,
and other associative containers.)
Return an iterator pointing to the found/created element.
Create a new element and place it before the element pointed to by where.
In contrast to the STL implementation, the iterator where is not
just a hint where to look up for an appropriate insertion position.
Instead, this operation does not perform any key comparisons (unless compiled with debugging enabled),
so it should be used only if the correct insertion is asserted by the program context.
Find an element with a given key and delete it, or do nothing if not found.
void erase(const iterator& pos);
Delete an element the iterator is pointing to. After this operation the iterator
become invalid (it can't be dereferenced nor moved to the next/previous element),
unless post-incremented or post-decremented within the method call expression.
A combined insert-erase operation: If an element with the given key exists,
delete it and return an end() iterator; otherwise
create a new element with this key and return an iterator pointing to it.