ext/OGDF/ogdf/internal/planarity/PQLeaf.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 PQleaf.
  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_LEAF_H
  50 #define OGDF_PQ_LEAF_H
  51
  52
  53
  54 #include <ogdf/internal/planarity/PQNode.h>
  55
  56 namespace ogdf {
  57
  58
  59 /**
  60  * The datastructure PQ-tree was designed to present a set of
  61  * permutations on an arbitrary set of elements. These elements are the
  62  * leafs of a PQ-tree. The client has to specify, what kind
  63  * of elements he uses. The element of a node is stored in the PQLeafKey
  64  * of a PQLeaf. The PQLeaf is the only concrete class
  65  * template of the abstract base class template PQNode
  66  * that is allowed to have a key.
  67  */
  68
  69 template<class T,class X,class Y>
  70 class PQLeaf : public PQNode<T,X,Y>
  71 {
  72 public:
  73
  74         /**
  75          * The client may choose between two different constructors.
  76          * In both cases the constructor expects an integer value \a count,
  77          * setting the value of the variable \a m_identificationNumber in the base class,
  78          * an integer value \a status setting the variable \a m_status of
  79          * PQLeaf and a pointer to an element of type PQLeafKey.
  80          *
  81          * One of the constructors expects additional information of type
  82          * PQNodeKey and will automatically set
  83          * the \a m_nodePointer (see basicKey) of the element of type
  84          * PQNodeKey to the newly allocated PQLeaf (see also
  85          * PQNode). The second constructor is called, if no
  86          * information for the PQLeaf is available or necessary.
  87          * Both constructors will automatically set the \a m_nodePointer of the
  88          * \a keyPtr to the newly allocated PQLeaf.
  89          */
  90         PQLeaf(
  91                 int count,
  92                 PQNodeRoot::PQNodeStatus stat,
  93                 PQLeafKey<T,X,Y>* keyPtr,
  94                 PQNodeKey<T,X,Y>* infoPtr)
  95                 : PQNode<T,X,Y>(count,infoPtr)
  96         {
  97                 m_status = stat;
  98                 m_pointerToKey = keyPtr;
  99                 m_mark = PQNodeRoot::UNMARKED;
 100                 keyPtr->setNodePointer(this);
 101         }
 102
 103         // Constructor
 104         PQLeaf(
 105                 int count,
 106                 PQNodeRoot::PQNodeStatus stat,
 107                 PQLeafKey<T,X,Y>* keyPtr)
 108                 : PQNode<T,X,Y>(count)
 109         {
 110                 m_status = stat;
 111                 m_pointerToKey = keyPtr;
 112                 m_mark = PQNodeRoot::UNMARKED;
 113                 keyPtr->setNodePointer(this);
 114         }
 115
 116         /**
 117          * The destructor does not delete any
 118          * accompanying information class as PQLeafKey,
 119          * PQNodeKey and PQInternalKey.
 120          * This has been avoided, since applications may need the existence of
 121          * these information classes after the corresponding node has been
 122          * deleted. If the deletion of an accompanying information class should
 123          * be performed with the deletion of a node, either derive a new class
 124          * with an appropriate destructor, or make use of the function
 125          * CleanNode() of the class template PQTree.
 126          */
 127         virtual ~PQLeaf() {}
 128
 129         /**
 130          * getKey() returns a pointer to the PQLeafKey
 131          * of PQLeaf. The adress of the PQLeafKey is stored in the
 132          * private variable \a m_pointerToKey.
 133          * The key contains informations of the element that is represented by
 134          * the PQLeaf in the PQ-tree and is of type PQLeafKey.
 135          */
 136         virtual PQLeafKey<T,X,Y>* getKey() const { return m_pointerToKey; }
 137
 138         /**
 139          * setKey() sets the pointer variable \a m_pointerToKey to the
 140          * specified address of \a pointerToKey that is of type PQLeafKey.
 141          *
 142          * Observe that \a pointerToKey has
 143          * to be instantiated by the client. The function setKey() does
 144          * not instantiate the corresponding variable in the derived class.
 145          * Using this function will automatically set the \a m_nodePointer
 146          * of the element of type key (see PQLeafKey)
 147          * to this PQLeaf. The return value is always 1 unless \a pointerKey
 148          * was equal to 0.
 149          */
 150         virtual bool setKey(PQLeafKey<T,X,Y>* pointerToKey)
 151         {
 152                 m_pointerToKey = pointerToKey;
 153                 if (pointerToKey != 0)
 154                 {
 155                         m_pointerToKey->setNodePointer(this);
 156                         return true;
 157                 }
 158                 else
 159                         return false;
 160         }
 161
 162         /**
 163          * getInternal() returns 0. The function is designed to
 164          * return a pointer to the PQInternalKey
 165          * information of a node, in case that
 166          * the node is supposed to have internal information. The class
 167          * template PQLeaf does not have PQInternalKey information.
 168          */
 169         virtual PQInternalKey<T,X,Y>* getInternal() const { return 0; }
 170
 171         /**
 172          * setInternal() accepts only pointers \a pointerToInternal = 0.
 173          *
 174          * The function setInternal() is designed to set a
 175          * specified pointer variable in a derived class
 176          * of PQNode to the adress stored in \a pointerToInternal.
 177          * which is of type PQInternalKey.
 178          * The class template PQLeaf does not store
 179          * informations of type PQInternalKey.
 180          *
 181          * setInternal() ignores the informations as long as
 182          * \a pointerToInternal = 0. The return value then is 1.
 183          * In case that \a pointerToInternal != 0, the return value is 0.
 184          */
 185         virtual bool setInternal(PQInternalKey<T,X,Y>* pointerToInternal)
 186         {
 187                 if (pointerToInternal != 0)
 188                         return false;
 189                 else
 190                         return true;
 191         }
 192
 193         //! Returns the variable \a m_mark.
 194         /**
 195          * The variable \a m_mark describes the designation used in
 196          * the first pass of Booth and Luekers algorithm called Bubble(). A
 197          * PQLeaf is either marked \b BLOCKED, \b UNBLOCKED or \b QUEUED (see
 198          * PQNode).
 199          */
 200         virtual PQNodeRoot::PQNodeMark  mark() const { return m_mark; }
 201
 202         //! Sets the variable \a m_mark.
 203         virtual void mark(PQNodeRoot::PQNodeMark m) { m_mark = m; }
 204
 205         //! Returns the variable \a m_status in the derived class PQLeaf.
 206         /**
 207          * The functions manage the status of a node in the PQ-tree. A status is
 208          * any kind of information of the current situation in the frontier of
 209          * a node (the frontier of a node are all descendant leaves of the
 210          * node). A status can be anything such as \b EMPTY, \b FULL or
 211          * \b PARTIAL (see PQNode). Since there might be more than those three
 212          * possibilities,
 213          * (e.g. in computing planar subgraphs) this
 214          * function may to be overloaded by the client.
 215          */
 216         virtual PQNodeRoot::PQNodeStatus status() const { return m_status; }
 217
 218         //! Sets the variable \a m_status in the derived class PQLeaf.
 219         virtual void status(PQNodeRoot::PQNodeStatus s) { m_status = s; }
 220
 221         //! Returns the variable \a m_type in the derived class PQLeaf.
 222         /**
 223          * The type of a node is either \b PNode, \b QNode or
 224          * \b leaf (see PQNodeRoot).
 225          * Since the type of an element of type PQLeaf is \b leaf every
 226          * input is ignored and the return value will always be \b leaf.
 227          */
 228         virtual PQNodeRoot::PQNodeType type() const { return PQNodeRoot::leaf; }
 229
 230         //! Sets the variable \a m_type in the derived class PQLeaf.
 231         virtual void type(PQNodeRoot::PQNodeType) { }
 232
 233 private:
 234
 235         /**
 236          * \a m_mark is a variable, storing if the PQLeaf is
 237          * \b QUEUEUD, \b BLOCKED or \b UNBLOCKED (see PQNode)
 238          * during the first phase of the procedure Bubble().
 239          */
 240         PQNodeRoot::PQNodeMark m_mark;
 241
 242         /**
 243          * \a m_pointerToKey stores the adress of the corresponding
 244          * PQLeafKey.
 245          * This PQLeafKey can be overloaded by the
 246          * client in order to represent different sets of elements, where
 247          * possible permutations have to be examined by the PQ-tree.
 248          */
 249         PQLeafKey<T,X,Y>* m_pointerToKey;
 250
 251         /**
 252          * \a m_status is a variable storing the status of a PQLeaf.
 253          * A PQLeaf can be either \b FULL or \b EMPTY (see PQNode).
 254          */
 255         PQNodeRoot::PQNodeStatus m_status;
 256
 257 };
 258
 259 }
 260
 261 #endif