ext/OGDF/ogdf/basic/HashArray2D.h

   1 /*
   2  * $Revision: 2615 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class HashArray2D.
  11  *
  12  * This is a class implementing a 2-dimensional Hash array.
  13  * It uses templates for the keys and the data of the objects
  14  * stored in it.
  15  *
  16  * \author René Weiskircher
  17  *
  18  * \par License:
  19  * This file is part of the Open Graph Drawing Framework (OGDF).
  20  *
  21  * \par
  22  * Copyright (C)<br>
  23  * See README.txt in the root directory of the OGDF installation for details.
  24  *
  25  * \par
  26  * This program is free software; you can redistribute it and/or
  27  * modify it under the terms of the GNU General Public License
  28  * Version 2 or 3 as published by the Free Software Foundation;
  29  * see the file LICENSE.txt included in the packaging of this file
  30  * for details.
  31  *
  32  * \par
  33  * This program is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  * GNU General Public License for more details.
  37  *
  38  * \par
  39  * You should have received a copy of the GNU General Public
  40  * License along with this program; if not, write to the Free
  41  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  42  * Boston, MA 02110-1301, USA.
  43  *
  44  * \see  http://www.gnu.org/copyleft/gpl.html
  45  ***************************************************************/
  46
  47
  48 #ifdef _MSC_VER
  49 #pragma once
  50 #endif
  51
  52 #include <ogdf/basic/HashArray.h>
  53 #include <ogdf/basic/tuples.h>
  54 #include <ogdf/basic/HashIterator2D.h>
  55
  56 #ifndef OGDF_HASH_ARRAY_2D_H
  57 #define OGDF_HASH_ARRAY_2D_H
  58
  59
  60 namespace ogdf {
  61
  62
  63 //! Indexed 2-dimensional arrays using hashing for element access.
  64 /**
  65  * @tparam I1 is the first index type.
  66  * @tparam I2 is the second index type.
  67  * @tparam E  is the element type.
  68  * @tparam H1 is the hash function type for \a I1. Optional; uses the class DefHashFunc by default.
  69  * @tparam H2 is the hash function type for \a I2. Optional; uses the class DefHashFunc by default.
  70  *
  71  * A 2D-hash array can be used like a usual 2-dimensional array but with a general
  72  * index type.
  73  */
  74 template<
  75         class I1,
  76         class I2,
  77         class E,
  78         class H1 = DefHashFunc<I1>,
  79         class H2 = DefHashFunc<I2> >
  80 class HashArray2D : private Hashing< Tuple2<I1,I2>, E, HashFuncTuple<I1,I2,H1,H2> >
  81 {
  82 public:
  83         //! The type of const-iterators for 2D-hash arrays.
  84         typedef HashConstIterator2D<I1,I2,E,H1,H2> const_iterator;
  85
  86         //! Creates a 2D-hash array.
  87         HashArray2D() { }
  88
  89         //! Creates a 2D-hash array and sets the default value to \a x.
  90         HashArray2D(const E &defaultValue, const H1 &hashFunc1 = H1(), const H2 &hashFunc2 = H2()) :
  91                 Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >(
  92                         256,
  93                         HashFuncTuple<I1,I2,H1,H2>(hashFunc1,hashFunc2)),
  94                 m_defaultValue(defaultValue) { }
  95
  96         //! Copy constructor.
  97         HashArray2D(const HashArray2D<I1,I2,E,H1,H2> &A) :
  98                 Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >(A),
  99                 m_defaultValue(A.m_defaultValue) { }
 100
 101         //! Assignment operator.
 102         HashArray2D &operator=(const HashArray2D<I1,I2,E,H1,H2> &A) {
 103                 m_defaultValue = A.m_defaultValue;
 104                 Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::operator=(A);
 105
 106                 return *this;
 107         }
 108
 109         ~HashArray2D() { }
 110
 111         //! Returns a const reference to entry (\a i,\a j).
 112         const E &operator()(const I1 &i, const I2 &j) const {
 113                 HashElement<Tuple2<I1,I2>,E> *pElement =
 114                         Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::lookup(Tuple2<I1,I2>(i,j));
 115                 return (pElement) ? pElement->info() : m_defaultValue;
 116         }
 117
 118         //! Returns a reference to entry (\a i,\a j).
 119         E &operator()(const I1 &i, const I2 &j) {
 120                 Tuple2<I1,I2> t(i,j);
 121                 HashElement<Tuple2<I1,I2>,E> *pElement =
 122                         Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::lookup(t);
 123                 if (!pElement)
 124                         pElement = Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::fastInsert(t,m_defaultValue);
 125                 return pElement->info();
 126         }
 127
 128         //! Returns true iff entry (\a i,\a j) is defined.
 129         bool isDefined(const I1 &i, const I2 &j) const {
 130                 return Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::member(Tuple2<I1,I2>(i,j));
 131         }
 132
 133         //! Undefines the entry at index (\a i,\a j).
 134         void undefine(const I1 &i, const I2 &j) {
 135                 return Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::del(Tuple2<I1,I2>(i,j));
 136         }
 137
 138         //! Returns an iterator pointing to the first element.
 139         HashConstIterator2D<I1,I2,E,H1,H2> begin() const {
 140                 return HashConstIterator2D<I1,I2,E>(
 141                         Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::begin());
 142         }
 143
 144         //! Returns the number of defined elements in the table.
 145         int size() const {
 146                 return Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::size();
 147         }
 148
 149         //! Returns if any indices are defined
 150         int empty() const {
 151                 return Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::empty();
 152         }
 153
 154
 155         //! Undefines all indices.
 156         void clear() {
 157                 Hashing<Tuple2<I1,I2>,E,HashFuncTuple<I1,I2,H1,H2> >::clear();
 158         }
 159
 160 private:
 161         E m_defaultValue; //!< The default value of the array.
 162 };
 163
 164 }
 165
 166 #endif