template<class T, class X, class Y>
class ogdf::PQLeafKey< T, X, Y >
The class template PQLeafKey is a derived class of class template PQBasicKey. PQLeafKey is a concrete class.
The class template PQLeafKey is used for carrying the elements of a user defined set of any type, where permissible permutations have to be found. In order to use the datastructure PQ-tree as class template PQTree, the user has to specify a set of arbitrary elements that form the leaves of the PQ-tree.
It has to be oberved that leaves have to be treated in almost all manipulations of the PQ-tree as all other nodes in the tree. Therefore the leaves have the same base class PQNode as the P- or Q-nodes. This obviously permits direct manipulation of the leaves in the tree by the client. Hence the client cannot overload the leaves by himself in order to specify the set of elements that he wants to manipulate.
Therefore the class template PQLeafKey is used. The user is allowed to manipulate the class at his will, and he can instantiate any kind template class of PQLeafKey.h.
Besides the specification, what kind of element of the observed set is carried along, PQLeafKey has a pointer to the leaf symbolizing this special element in the PQ-tree. On the other hand, a leaf has a pointer to its corresponding PQLeafKey.
After instantiating a various amount of PQLeafKey's, the PQ-tree is initialized with this set of PQLeafKey's. Every time a subset of elements has to be reduced, the corresponding subset of PQLeafKey's is handed over to the PQTree. This enables the class template PQTree to identify the corresponing leaves in the tree and to start the reduction process.
The class template PQLeafKey is treated in a different way by the class template PQTree than all other information storage classes derived from PQBasicKey. When initializing the PQ-tree, the class template PQTree sets the pointer m_nodePointer of PQLeafKey which is contained in the abstract base class PQBasicKey. This pointer identifies a unique leave in the tree that belongs to the information stored in a PQLeafKey. The maintainance of this pointer is not left to the user. It is managed by the PQ-tree but still allows the user to identify and acces leaves with a certain informations in constant time.
Definition at line 109 of file PQLeafKey.h.