1 /** \file 2 * \brief Declaration and implementation of HashArray class. 3 * 4 * \author Carsten Gutwenger 5 * 6 * \par License: 7 * This file is part of the Open Graph Drawing Framework (OGDF). 8 * 9 * \par 10 * Copyright (C)<br> 11 * See README.md in the OGDF root directory for details. 12 * 13 * \par 14 * This program is free software; you can redistribute it and/or 15 * modify it under the terms of the GNU General Public License 16 * Version 2 or 3 as published by the Free Software Foundation; 17 * see the file LICENSE.txt included in the packaging of this file 18 * for details. 19 * 20 * \par 21 * This program is distributed in the hope that it will be useful, 22 * but WITHOUT ANY WARRANTY; without even the implied warranty of 23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 * GNU General Public License for more details. 25 * 26 * \par 27 * You should have received a copy of the GNU General Public 28 * License along with this program; if not, see 29 * http://www.gnu.org/copyleft/gpl.html 30 */ 31 32 #pragma once 33 34 #include <ogdf/basic/Hashing.h> 35 36 37 namespace ogdf { 38 39 40 //! Indexed arrays using hashing for element access. 41 /** 42 * @ingroup containers 43 * 44 * @tparam I is the index type. 45 * @tparam E is the element type. 46 * @tparam H is the hash function type. Optional; its default uses the class DefHashFunc. 47 * 48 * A hashing array can be used like a usual array but has a general 49 * index type. 50 * 51 * The hashing array is only defined for a subset <I>I<SUB>def</SUB></I> of the 52 * index set (set of all elements of the index type). At construction, this set 53 * is empty. Whenever an index is assigned an element, this index is added 54 * to <I>I<SUB>def</SUB></I>. There are also method for testing if an index 55 * is defined (is in <I>I<SUB>def</SUB></I>). 56 * 57 * <H3>Example</H3> 58 * The following code snippet demonstrates how to use a hashing array. First, 59 * the example inserts elements into a hashing array simulating a tiny 60 * German–English dictionary, then it prints some elements via array 61 * access, and finally it iterates over all defined indices and prints the 62 * dictionary entries. We use a the const reference \a Hc, since we want to 63 * avoid that array access for undefined indices creates these elements. 64 * 65 * \code 66 * HashArray<string,string> H("[undefined]"); 67 * const HashArray<string,string> &Hc = H; 68 * 69 * H["Hund"] = "dog"; 70 * H["Katze"] = "cat"; 71 * H["Maus"] = "mouse"; 72 * 73 * std::cout << "Katze: " << Hc["Katze"] << std::endl; 74 * std::cout << "Hamster: " << Hc["Hamster"] << std::endl; 75 * 76 * std::cout << "\nAll elements:" << std::endl; 77 * HashConstIterator<string,string> it; 78 * for(it = Hc.begin(); it.valid(); ++it) 79 * std::cout << it.key() << " -> " << it.info() << std::endl; 80 * \endcode 81 * 82 * The produced output is as follows: 83 * \code 84 * Katze: cat 85 * Hamster: [undefined] 86 * 87 * All elements: 88 * Hund -> dog 89 * Maus -> mouse 90 * Katze -> cat 91 * \endcode 92 */ 93 template<class I, class E, class H = DefHashFunc<I> > 94 class HashArray : private Hashing<I,E,H> 95 { 96 E m_defaultValue; //! The default value for elements. 97 98 public: 99 //! The type of const-iterators for hash arrays. 100 using const_iterator = HashConstIterator<I,E,H>; 101 102 //! Creates a hashing array; the default value is the default value of the element type. HashArray()103 HashArray() : Hashing<I,E,H>() { } 104 105 //! Creates a hashing array with default value \p defaultValue. 106 explicit HashArray(const E &defaultValue, const H &hashFunc = H()) 107 : Hashing<I,E,H>(256, hashFunc), m_defaultValue(defaultValue) { } 108 109 //! Copy constructor. HashArray(const HashArray<I,E,H> & A)110 HashArray(const HashArray<I,E,H> &A) : Hashing<I,E,H>(A), m_defaultValue(A.m_defaultValue) { } 111 112 //! Returns an iterator to the first element in the list of all elements. begin()113 HashConstIterator<I,E,H> begin() const { return Hashing<I,E,H>::begin(); } 114 115 //! Returns the number of defined indices (= number of elements in hash table). size()116 int size() const { return Hashing<I,E,H>::size(); } 117 118 //! Returns if any indices are defined (= if the hash table is empty) empty()119 int empty() const { return Hashing<I,E,H>::empty(); } 120 121 122 //! Returns the element with index \p i. 123 const E &operator[](const I &i) const { 124 HashElement<I,E> *pElement = Hashing<I,E,H>::lookup(i); 125 if (pElement) return pElement->info(); 126 else return m_defaultValue; 127 } 128 129 //! Returns a reference to the element with index \p i. 130 E &operator[](const I &i) { 131 HashElement<I,E> *pElement = Hashing<I,E,H>::lookup(i); 132 if (!pElement) pElement = Hashing<I,E,H>::fastInsert(i,m_defaultValue); 133 return pElement->info(); 134 } 135 136 //! Returns true iff index \p i is defined. isDefined(const I & i)137 bool isDefined(const I &i) const { 138 return Hashing<I,E,H>::member(i); 139 } 140 141 //! Undefines index \p i. undefine(const I & i)142 void undefine(const I &i) { 143 Hashing<I,E,H>::del(i); 144 } 145 146 //! Assignment operator. 147 HashArray<I,E,H> &operator=(const HashArray<I,E,H> &A) { 148 m_defaultValue = A.m_defaultValue; 149 Hashing<I,E,H>::operator =(A); 150 return *this; 151 } 152 153 //! Undefines all indices. clear()154 void clear() { Hashing<I,E,H>::clear(); } 155 }; 156 157 } 158