ext/OGDF/ogdf/basic/FaceSet.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief declaration and implementation of class FaceSetSimple,
  11  * FaceSetPure and FaceSet
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_FACE_SET_H
  50 #define OGDF_FACE_SET_H
  51
  52
  53 #include <ogdf/basic/FaceArray.h>
  54 #include <ogdf/basic/List.h>
  55
  56
  57
  58 namespace ogdf {
  59
  60
  61 //! Maintains a subset S of the faces contained in an associated combinatorial embedding E
  62 /** (only insertion of elements and clear operation)
  63  */
  64 class OGDF_EXPORT FaceSetSimple {
  65 public:
  66         //! creates a new empty face set associated with combinatorial embedding E
  67         FaceSetSimple(const CombinatorialEmbedding &E) : m_isContained(E,false) { }
  68
  69         //! destructor
  70         ~FaceSetSimple() { }
  71
  72         //! inserts face f into set S
  73         /** running time: O(1)
  74          *  Precond.: f is a face in the associated combinatorial embedding
  75          */
  76         void insert(face f) {
  77                 OGDF_ASSERT(f->embeddingOf() == m_isContained.embeddingOf());
  78                 bool &isContained = m_isContained[f];
  79                 if (isContained == false) {
  80                         isContained = true;
  81                         m_faces.pushFront(f);
  82                 }
  83         }
  84
  85
  86         //! removes all faces from set S
  87         /** running time: O(|S|)
  88          */
  89         void clear() {
  90                 SListIterator<face> it;
  91                 for(it = m_faces.begin(); it.valid(); ++it) {
  92                         m_isContained[*it] = false;
  93                 }
  94                 m_faces.clear();
  95         }
  96
  97
  98         //! returns true iff face f is contained in S
  99         /** running time: O(1)
 100          * Precond.: f is a face in the asociated embedding
 101          */
 102         bool isMember(face f) const {
 103                 OGDF_ASSERT(f->embeddingOf() == m_isContained.embeddingOf());
 104                 return m_isContained[f];
 105         }
 106
 107         //! returns the list of faces contained in S
 108         const SListPure<face> &faces() const {
 109                 return m_faces;
 110         }
 111
 112 private:
 113         //! m_isContained[f] is true <=> f is contained in S
 114         FaceArray<bool> m_isContained;
 115         //! list of faces contained in S
 116         SListPure<face> m_faces;
 117 };
 118
 119
 120
 121 //! maintains a subset S of the faces contained in an associated combinatorial embedding E
 122 /** (no efficient access to size of S)
 123  */
 124 class OGDF_EXPORT FaceSetPure {
 125 public:
 126         //! creates a new empty face set associated with combinatorial embedding E
 127         FaceSetPure(const CombinatorialEmbedding &E) : m_it(E,ListIterator<face>()) { }
 128
 129         //! destructor
 130         ~FaceSetPure() { }
 131
 132         //! inserts face f into set S
 133         /** running time: O(1)
 134          * Precond.: f is a face in the associated combinatorial embedding
 135          */
 136         void insert(face f) {
 137                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 138                 ListIterator<face> &itF = m_it[f];
 139                 if (!itF.valid())
 140                         itF = m_faces.pushBack(f);
 141         }
 142
 143         //! removes face f from set S
 144         /** running time: O(1)
 145          * Precond.: f is a face in the asociated embedding
 146          */
 147         void remove(face f) {
 148                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 149                 ListIterator<face> &itF = m_it[f];
 150                 if (itF.valid()) {
 151                         m_faces.del(itF);
 152                         itF = ListIterator<face>();
 153                 }
 154         }
 155
 156
 157         //! removes all faces from set S
 158         /** running time: O(|S|)
 159          */
 160         void clear() {
 161                 ListIterator<face> it;
 162                 for(it = m_faces.begin(); it.valid(); ++it) {
 163                         m_it[*it] = ListIterator<face>();
 164                 }
 165                 m_faces.clear();
 166         }
 167
 168
 169         //! returns true iff face f is contained in S
 170         /** running time: O(1)
 171          * Precond.: f is a face in the asociated embedding
 172          */
 173         bool isMember(face f) const {
 174                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 175                 return m_it[f].valid();
 176         }
 177
 178         //! returns the list of faces contained in S
 179         const ListPure<face> &faces() const {
 180                 return m_faces;
 181         }
 182
 183 private:
 184         //! m_it[f] contains list iterator pointing to f if f is contained in S, an invalid list iterator otherwise
 185         FaceArray<ListIterator<face> > m_it;
 186         //! list of faces contained in S
 187         ListPure<face> m_faces;
 188 };
 189
 190
 191
 192 //! maintains a subset S of the faces contained in an associated combinatorial embedding E
 193 class OGDF_EXPORT FaceSet {
 194 public:
 195         //! creates a new empty face set associated with combinatorial embedding E
 196         FaceSet(const CombinatorialEmbedding &E) : m_it(E,ListIterator<face>()) { }
 197
 198         //! destructor
 199         ~FaceSet() { }
 200
 201         //! inserts face f into set S
 202         /** running time: O(1)
 203          * Precond.: f is a face in the associated combinatorial embedding
 204          */
 205         void insert(face f) {
 206                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 207                 ListIterator<face> &itF = m_it[f];
 208                 if (!itF.valid())
 209                         itF = m_faces.pushBack(f);
 210         }
 211
 212         //! removes face f from set S
 213         /* running time: O(1)
 214          * Precond.: f is a face in the asociated embedding
 215          */
 216         void remove(face f) {
 217                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 218                 ListIterator<face> &itF = m_it[f];
 219                 if (itF.valid()) {
 220                         m_faces.del(itF);
 221                         itF = ListIterator<face>();
 222                 }
 223         }
 224
 225
 226         //! removes all faces from set S
 227         /** running time: O(|S|)
 228          */
 229         void clear() {
 230                 ListIterator<face> it;
 231                 for(it = m_faces.begin(); it.valid(); ++it) {
 232                         m_it[*it] = ListIterator<face>();
 233                 }
 234                 m_faces.clear();
 235         }
 236
 237
 238         //! returns true iff face f is contained in S
 239         /** running time: O(1)
 240          * Precond.: f is a face in the asociated embedding
 241          */
 242         bool isMember(face f) const {
 243                 OGDF_ASSERT(f->embeddingOf() == m_it.embeddingOf());
 244                 return m_it[f].valid();
 245         }
 246
 247         //! returns the size of set S
 248         /** running time: O(1)
 249          */
 250         int size() const {
 251                 return m_faces.size();
 252         }
 253
 254         //! returns the list of faces contained in S
 255         const List<face> &faces() const {
 256                 return m_faces;
 257         }
 258
 259 private:
 260         //! m_it[f] contains list iterator pointing to f if f is contained in S,an invalid list iterator otherwise
 261         FaceArray<ListIterator<face> > m_it;
 262         //! list of faces contained in S
 263         List<face> m_faces;
 264 };
 265
 266
 267 } // end namespace ogdf
 268
 269
 270 #endif
 271