ext/OGDF/ogdf/internal/planarity/PQBasicKey.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration and implementation of the class PQBasicKey.
  11  *
  12  * \author Sebastian Leipert
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48
  49 #ifndef OGDF_PQ_BASICKEY_H
  50 #define OGDF_PQ_BASICKEY_H
  51
  52
  53
  54 #include <stdlib.h>
  55 #include <ogdf/internal/planarity/PQBasicKeyRoot.h>
  56
  57
  58 namespace ogdf {
  59
  60 /**
  61  * The class template PQBasicKey is an abstract base class. It enables the user
  62  * of the PQ-tree to store different informations at every node of
  63  * the tree.
  64  *
  65  * The implementation of the PQ-tree provides the storage of three
  66  * different types of information.
  67  *   - General information that is stored at P- and Q-nodes and
  68  *     leaves likewise (see also PQNodeKey).
  69  *   - Information that is only supported for internal nodes (see
  70  *     also internalKey).
  71  *   - The keys of the leaves (see also leafKey).
  72  *     The keys are constructed to carry the
  73  *     elements of  a user defined set of any type, where permissible
  74  *     permutations have to be
  75  *     found. In order to use the datastructure PQ-tree as class template
  76  *     PQTree, the user has to specify a set of arbitrary elements that
  77  *     form the leaves of the PQ-tree. The keys function as storage class
  78  *     of the elements of the set.
  79  *
  80  * All three storage classes are derived class templates of
  81  * PQBasicKey. The class PQBasicKey has a pointer \a m_nodePointer to a PQNode,
  82  * beeing either a leaf or an internal
  83  * PQInternalNode. The base class itself does not provide any storage of
  84  * the informations, it is hidden in the derived classes. PQBasicKey
  85  * only declares a few pure virtual functions that are overloaded in
  86  * the derived classes and which give access to the information stored
  87  * in the derived classes.
  88  *
  89  * The information stored in an element of a derived class of
  90  * PQBasicKey is assigned to a unique node in the PQ-tree. This
  91  * unique node can be identified with the \a m_nodePointer. The
  92  * maintenance of this pointer is left to the user in the derived
  93  * concrete classes PQNodeKey and internalKey. By keeping the
  94  * responsibillity for these classes by the client,
  95  * nodes with certain informations can
  96  * be accessed by the client in constant time. This makes
  97  * the adaption of algorithms fast and easy.
  98  *
  99  * Only the derived concrete class template leafKey
 100  * is treated in a different way by the class template PQTree.
 101  * When initializing the PQTree with a set of elements of type leafKey, the
 102  * class template PQTree sets the pointer \a m_nodePointer of every element.
 103  * This is due to the fact that a PQ-tree is always defined over some set,
 104  * whose elements are
 105  * stored in the leaves. Hence the class PQtree expects such a set
 106  * and supports its maintainance. Storing extra information at every
 107  * node may be omitted and makes the PQtree easy applicable.
 108  *
 109  * We now give a short overview of the class template declaration
 110  * PQBasicKey. The class template PQBasicKey is used as a base
 111  * class template that specifies three different types of information.
 112  * The type of information used at a node is depending on the type of
 113  * the node. These
 114  * informations have to be specified by the user.
 115  *
 116  * The formal type parameters of the class template PQBasicKey are
 117  * categorized as follows.
 118  *   - \a T is a formal type parameter for the information stored in
 119  *     leafKey.
 120  *   - \a X is a formal type parameter for the information stored in
 121  *     PQNodeKey.
 122  *   - \a Y is a formal type parameter for the information stored in
 123  *     internalKey.
 124  *
 125  * The class template PQBasicKey contains a few pure virtual member
 126  * functions that are overloaded in the derived class leafKey,
 127  * PQNodeKey and internalKey. These functions enable the client to
 128  * access the information stored at a node.
 129  */
 130
 131 template<class T,class X, class Y> class PQNode;
 132
 133
 134
 135 template<class T,class X,class Y>
 136 class PQBasicKey: public PQBasicKeyRoot {
 137
 138 public:
 139
 140         // Constructor
 141         PQBasicKey() : m_nodePointer(0) { }
 142
 143
 144         /**
 145          * The function nodePointer()
 146          * returns a pointer to an element of type
 147          * PQNode. This element can be either of type leaf or
 148          * PQInternalNode. PQBasicKey, or rather its derived classes store
 149          * informations of this PQNode. The user is able identify with the
 150          * help of this function for every information its corresponding node.
 151          * Nevertheless, the private member \a m_nodePointer that stores
 152          * the pointer to this member <b>is not set</b> within the PQ-tree,
 153          * unless it is a derived class template of type leafKey.
 154          *
 155          * Setting the \a m_nodePointer has to be done explicitly by
 156          * the client with the help of the
 157          * function setNodePointer().
 158          * This offers as much freedom to the
 159          * client as possible, since this enables the client to keep control
 160          * over the informations stored at different nodes and to access
 161          * nodes with specified informations in constant time.
 162          */
 163         PQNode<T,X,Y>* nodePointer() { return m_nodePointer; }
 164
 165         /**
 166          * The function print() is a virtual function, that can be overloaded
 167          * by the user in order to print out the information stored at any of
 168          * the derived classes. Deriving this function, the user can choose any
 169          * format for printing out the information. Currently, the return value
 170          * of the function print() is an empty string.
 171          */
 172
 173         virtual ostream &print(ostream &os) { return os; }
 174
 175         /**
 176          * The function setNodePointer() sets the private member
 177          * \a m_nodePointer. The private member \a m_nodePointer stores the
 178          * address of the corresponding node in the PQTree.
 179          * Using this function enables the client to identify
 180          * certain informations with a node in the PQ-tree.
 181          */
 182         void setNodePointer(PQNode<T,X,Y>* node) { m_nodePointer = node; }
 183
 184         //! Returns the key of a leaf.
 185         virtual T userStructKey()  = 0;
 186
 187         //! Returns the information of any node.
 188         virtual X userStructInfo()  = 0;
 189
 190         //! Returns the information of any internal node.
 191         virtual Y userStructInternal()  = 0;
 192
 193
 194 private:
 195
 196         /** Stores the adress of a node. This node has to
 197          * be specified by the client via the function \a setNodePointer.
 198          */
 199         PQNode<T,X,Y>* m_nodePointer;
 200
 201 };
 202
 203 }
 204
 205 #endif