|
| | PQNode (int count) |
| | The (second) constructor is called, if no information is available or neccessary.
|
| |
| | PQNode (int count, PQNodeKey< T, X, Y > *infoPtr) |
| | The (first) constructor combines the node with its information and will automatically set the PQBasicKey::m_nodePointer (see basicKey) of the element of type PQNodeKey.
|
| |
| virtual | ~PQNode () |
| | The destructor does not delete any accompanying information class as PQLeafKey, PQNodeKey and PQInternalKey.
|
| |
| bool | changeEndmost (PQNode< T, X, Y > *oldEnd, PQNode< T, X, Y > *newEnd) |
| | The function changeEndmost() replaces the old endmost child oldEnd of the node by a new child newEnd.
|
| |
| bool | changeSiblings (PQNode< T, X, Y > *oldSib, PQNode< T, X, Y > *newSib) |
| | The function changeSiblings() replaces the old sibling oldSib of the node by a new sibling newSib.
|
| |
| int | childCount () const |
| | Returns the number of children of a node.
|
| |
| void | childCount (int count) |
| | Sets the number of children of a node.
|
| |
| bool | endmostChild () const |
| | The function endmostChild() checks if a node is endmost child of a Q-node.
|
| |
| PQNode< T, X, Y > * | getEndmost (PQNode< T, X, Y > *other) const |
| | Returns one of the endmost children of node, if node is a Q-node.
|
| |
| PQNode< T, X, Y > * | getEndmost (SibDirection side) const |
| | Returns one of the endmost children of node, if node is a Q-node.
|
| |
| virtual PQInternalKey< T, X, Y > * | getInternal () const =0 |
| | getInternal() returns a pointer to the PQInternalKey information of a node, in case that the node is supposed to have PQInternalKey information, such as elements of the derived class template PQInternalNode.
|
| |
| virtual PQLeafKey< T, X, Y > * | getKey () const =0 |
| | getKey() returns a pointer to the PQLeafKeyof a node, in case that the node is supposed to have a key, such as elements of the derived class template PQLeaf.
|
| |
| PQNode< T, X, Y > * | getNextSib (PQNode< T, X, Y > *other) const |
| | The function getNextSib() returns one of the siblings of the node.
|
| |
| PQNodeKey< T, X, Y > * | getNodeInfo () const |
| | Returns the identification number of a node.
|
| |
| PQNode< T, X, Y > * | getSib (SibDirection side) const |
| | The function getSib() returns one of the siblings of the node.
|
| |
| int | identificationNumber () const |
| | Returns the identification number of a node.
|
| |
| virtual PQNodeMark | mark () const =0 |
| | mark() returns the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.
|
| |
| virtual void | mark (PQNodeMark)=0 |
| | mark() sets the variable PQLeaf::m_mark in the derived class PQLeaf and PQInternalNode.
|
| |
| PQNode< T, X, Y > * | parent () const |
| | The function parent() returns a pointer to the parent of a node.
|
| |
| PQNode< T, X, Y > * | parent (PQNode< T, X, Y > *newParent) |
| | Sets the parent pointer of a node.
|
| |
| PQNodeType | parentType () const |
| | Returns the type of the parent of a node.
|
| |
| void | parentType (PQNodeType newParentType) |
| | Sets the type of the parent of a node.
|
| |
| int | pertChildCount () const |
| | Returs the number of pertinent children of a node.
|
| |
| void | pertChildCount (int count) |
| | Sets the number of pertinent children of a node.
|
| |
| SibDirection | putSibling (PQNode< T, X, Y > *newSib) |
| | The default function putSibling() stores a new sibling at a free sibling pointer of the node.
|
| |
| SibDirection | putSibling (PQNode< T, X, Y > *newSib, SibDirection preference) |
| | The function putSibling() with preference stores a new sibling at a free sibling pointer of the node.
|
| |
| PQNode< T, X, Y > * | referenceChild () const |
| | Returns a pointer to the reference child if node is a P-node.
|
| |
| PQNode< T, X, Y > * | referenceParent () const |
| | Returns the pointer to the parent if node is a reference child.
|
| |
| virtual bool | setInternal (PQInternalKey< T, X, Y > *pointerToInternal)=0 |
| |
| virtual bool | setKey (PQLeafKey< T, X, Y > *pointerToKey)=0 |
| | Sets a specified pointer variable in a derived class to the specified adress of pointerToKey that is of type PQLeafKey.
|
| |
| bool | setNodeInfo (PQNodeKey< T, X, Y > *pointerToInfo) |
| | Sets the pointer m_pointerToInfo to the specified adress of pointerToInfo.
|
| |
| virtual PQNodeStatus | status () const =0 |
| | Returns the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.
|
| |
| virtual void | status (PQNodeStatus)=0 |
| | Sets the variable PQLeaf::m_status in the derived class PQLeaf and PQInternalNode.
|
| |
| virtual PQNodeType | type () const =0 |
| | Returns the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode.
|
| |
| virtual void | type (PQNodeType)=0 |
| | Sets the variable PQInternalNode::m_type in the derived class PQLeaf and PQInternalNode.
|
| |
| | PQNodeRoot () |
| |
| virtual | ~PQNodeRoot () |
| |
|
| List< PQNode< T, X, Y > * > * | fullChildren |
| | Stores all full children of a node during a reduction.
|
| |
| int | m_childCount |
| |
| int | m_debugTreeNumber |
| | Needed for debuging purposes.
|
| |
| PQNode< T, X, Y > * | m_firstFull |
| | Stores a pointer to the first full child of a Q-node.
|
| |
| int | m_identificationNumber |
| | Each node that has been introduced once into the tree gets a unique number.
|
| |
| PQNode< T, X, Y > * | m_leftEndmost |
| |
| PQNode< T, X, Y > * | m_parent |
| | Is a pointer to the parent.
|
| |
| PQNodeType | m_parentType |
| | Stores the type of the parent which can be either a P- or Q-node.
|
| |
| int | m_pertChildCount |
| | Stores the number of pertinent children of the node.
|
| |
| int | m_pertLeafCount |
| | Stores the number of pertinent leaves in the frontier of the node.
|
| |
| PQNodeKey< T, X, Y > * | m_pointerToInfo |
| | Stores a pointer to the corresponding information of the node.
|
| |
| PQNode< T, X, Y > * | m_referenceChild |
| | Stores a pointer to one child, the reference child of the doubly linked cirkular list of children of a P-node.
|
| |
| PQNode< T, X, Y > * | m_referenceParent |
| | Is a pointer to the parent, in case that the parent is a P-node and the node itself is its reference child.
|
| |
| PQNode< T, X, Y > * | m_rightEndmost |
| | Stores the right endmost child of a Q-node.
|
| |
| PQNode< T, X, Y > * | m_sibLeft |
| | Stores a pointer ot the left sibling of PQNode.
|
| |
| PQNode< T, X, Y > * | m_sibRight |
| | Stores a pointer ot the right sibling of PQNode.
|
| |
| List< PQNode< T, X, Y > * > * | partialChildren |
| | Stores all partial children of a node during a reduction.
|
| |
The class template PQBasicKey is an abstract base class.
It enables the user of the PQ-tree to store different informations at every node of the tree.
The implementation of the PQ-tree provides the storage of three different types of information.
- General information that is stored at P- and Q-nodes and leaves likewise (see also PQNodeKey).
- Information that is only supported for internal nodes (see also internalKey).
- The keys of the leaves (see also leafKey). The keys are constructed to carry 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. The keys function as storage class of the elements of the set.
All three storage classes are derived class templates of PQBasicKey. The class PQBasicKey has a pointer PQBasicKey::m_nodePointer to a PQNode, beeing either a leaf or an internal PQInternalNode. The base class itself does not provide any storage of the informations, it is hidden in the derived classes. PQBasicKey only declares a few pure virtual functions that are overloaded in the derived classes and which give access to the information stored in the derived classes.
The information stored in an element of a derived class of PQBasicKey is assigned to a unique node in the PQ-tree. This unique node can be identified with the PQBasicKey::m_nodePointer. The maintenance of this pointer is left to the user in the derived concrete classes PQNodeKey and internalKey. By keeping the responsibillity for these classes by the client, nodes with certain informations can be accessed by the client in constant time. This makes the adaption of algorithms fast and easy.
Only the derived concrete class template leafKey is treated in a different way by the class template PQTree. When initializing the PQTree with a set of elements of type leafKey, the class template PQTree sets the pointer PQBasicKey::m_nodePointer of every element. This is due to the fact that a PQ-tree is always defined over some set, whose elements are stored in the leaves. Hence the class PQtree expects such a set and supports its maintainance. Storing extra information at every node may be omitted and makes the PQtree easy applicable.
We now give a short overview of the class template declaration PQBasicKey. The class template PQBasicKey is used as a base class template that specifies three different types of information. The type of information used at a node is depending on the type of the node. These informations have to be specified by the user.
The formal type parameters of the class template PQBasicKey are categorized as follows.
- T is a formal type parameter for the information stored in leafKey.
- X is a formal type parameter for the information stored in PQNodeKey.
- Y is a formal type parameter for the information stored in internalKey.
The class template PQBasicKey contains a few pure virtual member functions that are overloaded in the derived class leafKey, PQNodeKey and internalKey. These functions enable the client to access the information stored at a node.
Definition at line 55 of file PQNode.h.
The function putSibling() with preference stores a new sibling at a free sibling pointer of the node.
This is only possible, if the node has at most one sibling. The function then detects a non used sibling pointer and places newSib onto it. putSibling() returns 0 if there have been two siblings detected, occupying the two possible pointers. In this case the new sibling newSib could not be stored. If there was at a maximum one sibling stored, the function will place newSib on the free pointer and return either LEFT or RIGHT, depending wich pointer has been used.
This function scans the brother first, which has been specified in the preference. If the preference has value LEFT, it scans the pointer to the left brother first. If the value is RIGHT, it scans the pointer to the right brother first.
Definition at line 278 of file PQNode.h.
Sets a specified pointer variable in a derived class to the specified adress of pointerToKey that is of type PQLeafKey.
If a derived class, such as PQInternalNode, is not supposed to store informations of type PQLeafKey, setKey() ignores the informations as long as pointerToKey = 0. The return value then is 1. In case that pointerToKey != 0, the return value is 0.
If a derived class, such as PQLeaf is supposed to store informations of type PQLeafKey, pointerToKey has to be instantiated by the client. The function setKey() does not instantiate the corresponding variable in the derived class. The return value is always 1 unless pointerKey was equal to 0.
Implemented in ogdf::PQInternalNode< T, X, Y >, and ogdf::PQLeaf< T, X, Y >.
Inheritance diagram for ogdf::PQNode< T, X, Y >:
