 | PixelLight 0.9.11-R1 Copyright (C) 2002-2012 by The PixelLight Team Last modified Thu Feb 23 2012 14:08:56 |  | The content of this PixelLight
document is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported |
|
PixelLightAPI
.
|
00001 /*********************************************************\ 00002 * File: HashMap.h * 00003 * 00004 * Copyright (C) 2002-2012 The PixelLight Team (http://www.pixellight.org/) 00005 * 00006 * This file is part of PixelLight. 00007 * 00008 * PixelLight is free software: you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License as published by 00010 * the Free Software Foundation, either version 3 of the License, or 00011 * (at your option) any later version. 00012 * 00013 * PixelLight is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 * GNU Lesser General Public License for more details. 00017 * 00018 * You should have received a copy of the GNU Lesser General Public License 00019 * along with PixelLight. If not, see <http://www.gnu.org/licenses/>. 00020 \*********************************************************/ 00021 00022 00023 #ifndef __PLCORE_CONTAINER_HASHMAP_H__ 00024 #define __PLCORE_CONTAINER_HASHMAP_H__ 00025 #pragma once 00026 00027 00028 //[-------------------------------------------------------] 00029 //[ Includes ] 00030 //[-------------------------------------------------------] 00031 #include "PLCore/Container/Map.h" 00032 #include "PLCore/Container/Functions.h" 00033 00034 00035 //[-------------------------------------------------------] 00036 //[ Namespace ] 00037 //[-------------------------------------------------------] 00038 namespace PLCore { 00039 00040 00041 //[-------------------------------------------------------] 00042 //[ Forward declarations ] 00043 //[-------------------------------------------------------] 00044 template <class KeyType, class ValueType, class Hasher, class Comparer, class Grower> class HashMapIterator; 00045 template <class KeyType, class ValueType, class Hasher, class Comparer, class Grower> class HashMapKeyIterator; 00046 00047 00048 //[-------------------------------------------------------] 00049 //[ Classes ] 00050 //[-------------------------------------------------------] 00051 /** 00052 * @brief 00053 * Hash map template 00054 * 00055 * @remarks 00056 * The hash map is using a hashing function to calculate indices to elements. If there are 00057 * too many elements in the map which will produce more collisions, a grow function 00058 * decides when to grow the hash map and how much. 00059 * There are some ways to avoid collisions: 00060 * 1. The hash map size should be a prime number: It can be mathematically proven that the 00061 * probability of collisions is less if we let the hash function perform % on a prime number 00062 * rather than on a non-prime number. 00063 * 2. Spreading the values: For example, let the hash function be smart enough to distribute its 00064 * return values as evenly as possible. How to determine the best algorithm for the hash function 00065 * depends on the hash map usage. 00066 * 3. Increasing the array's size: The more "free slots" in the hash map, the less probability of 00067 * collisions. So, to avoid collisions, use a clever grow function. But try to avoid to grow the 00068 * hash map frequently because that's not performant. 00069 * 00070 * @note 00071 * - Collisions are solved by using a linked list per slot 00072 */ 00073 template <class KeyType, class ValueType, class Hasher = HashFunction, class Comparer = CompareFunction, class Grower = GrowFunction> 00074 class HashMap : public Map<KeyType, ValueType> { 00075 00076 00077 //[-------------------------------------------------------] 00078 //[ Friends ] 00079 //[-------------------------------------------------------] 00080 friend class HashMapIterator<KeyType, ValueType, Hasher, Comparer, Grower>; 00081 friend class HashMapKeyIterator<KeyType, ValueType, Hasher, Comparer, Grower>; 00082 00083 00084 //[-------------------------------------------------------] 00085 //[ Public functions ] 00086 //[-------------------------------------------------------] 00087 public: 00088 /** 00089 * @brief 00090 * Constructor 00091 * 00092 * @param[in] nNumOfSlots 00093 * Initial number of slots (must be >= 1, should be a prime number) 00094 */ 00095 HashMap(uint32 nNumOfSlots = 199); 00096 00097 /** 00098 * @brief 00099 * Copy constructor 00100 * 00101 * @param[in] cSource 00102 * Source to copy from 00103 */ 00104 HashMap(const HashMap<KeyType, ValueType, Hasher, Comparer, Grower> &cSource); 00105 00106 /** 00107 * @brief 00108 * Destructor 00109 */ 00110 virtual ~HashMap(); 00111 00112 /** 00113 * @brief 00114 * Copy operator 00115 * 00116 * @param[in] cSource 00117 * 'HashMap' to copy from 00118 * 00119 * @return 00120 * Reference to this instance 00121 */ 00122 Map<KeyType, ValueType> &operator =(const HashMap<KeyType, ValueType, Hasher, Comparer, Grower> &cSource); 00123 00124 /** 00125 * @brief 00126 * Returns the current number of slots 00127 * 00128 * @return 00129 * Current number of slots 00130 */ 00131 uint32 GetNumOfSlots() const; 00132 00133 /** 00134 * @brief 00135 * Returns some statistics 00136 * 00137 * @param[out] nNumOfCollisions 00138 * Will receive the number of collisions 00139 * @param[out] nNumOfFreeSlotsLists 00140 * Will receive the number of free slots lists 00141 * 00142 * @note 00143 * - If there are a lot of collisions and also a lot of free slots lists you should 00144 * try to use a more efficient hash function 00145 */ 00146 void GetStatistics(uint32 &nNumOfCollisions, uint32 &nNumOfFreeSlotsLists) const; 00147 00148 00149 //[-------------------------------------------------------] 00150 //[ Private structures ] 00151 //[-------------------------------------------------------] 00152 private: 00153 /** 00154 * @brief 00155 * Internal hash string template 00156 * 00157 * @remarks 00158 * Slot stores a key/value pair. 00159 */ 00160 struct Slot { 00161 KeyType Key; /**< The key */ 00162 ValueType Value; /**< The value */ 00163 Slot *pNextSlot; /**< Pointer to the next hash slot, can be a null pointer */ 00164 Slot *pPreviousSlot; /**< Pointer to the previous hash slot, can be a null pointer */ 00165 }; 00166 00167 00168 //[-------------------------------------------------------] 00169 //[ Private classes ] 00170 //[-------------------------------------------------------] 00171 private: 00172 /** 00173 * @brief 00174 * Internal hash map slots template 00175 * 00176 * @remarks 00177 * The slots list stores a list of hash slot objects. 00178 */ 00179 class SlotsList { 00180 00181 00182 //[-------------------------------------------------------] 00183 //[ Friends ] 00184 //[-------------------------------------------------------] 00185 friend class HashMap<KeyType, ValueType, Hasher, Comparer, Grower>; 00186 friend class HashMapIterator<KeyType, ValueType, Hasher, Comparer, Grower>; 00187 friend class HashMapKeyIterator<KeyType, ValueType, Hasher, Comparer, Grower>; 00188 00189 00190 //[-------------------------------------------------------] 00191 //[ Public functions ] 00192 //[-------------------------------------------------------] 00193 public: 00194 /** 00195 * @brief 00196 * Constructor 00197 */ 00198 SlotsList(); 00199 00200 /** 00201 * @brief 00202 * Destructor 00203 */ 00204 ~SlotsList(); 00205 00206 /** 00207 * @brief 00208 * Copy operator 00209 * 00210 * @param[in] cSource 00211 * 'SlotsList' to copy from 00212 */ 00213 void operator =(const SlotsList &cSource); 00214 00215 /** 00216 * @brief 00217 * Clears the hash slots 00218 */ 00219 void Clear(); 00220 00221 /** 00222 * @brief 00223 * Adds a new element to the hash map slot list 00224 * 00225 * @param[in] Key 00226 * The key of the element which should be added 00227 * @param[in] Value 00228 * The value which should be added 00229 * 00230 * @see 00231 * - Set() 00232 */ 00233 void Add(const KeyType &Key, const ValueType &Value); 00234 00235 /** 00236 * @brief 00237 * Replaces the value of a map element 00238 * 00239 * @param[in] Key 00240 * The key of the element 00241 * @param[in] NewValue 00242 * The new value of the element 00243 * 00244 * @return 00245 * 'true' if all went fine, else 'false' (key not found?) 00246 * 00247 * @see 00248 * - Set() 00249 */ 00250 bool Replace(const KeyType &Key, const ValueType &NewValue); 00251 00252 /** 00253 * @brief 00254 * Sets (adds or replaces) the value of a map element 00255 * 00256 * @param[in] Key 00257 * The key of the element 00258 * @param[in] Value 00259 * The set value of the element 00260 * 00261 * @return 00262 * 'false' if a new element was added, 'true' if the value was replaced 00263 * 00264 * @remarks 00265 * This function is a combination of the add and replace function and 'just' assigns 00266 * a value to a given key without taking care of whether or not there's already an 00267 * element with the given key inside the map. 00268 * 00269 * @see 00270 * - Add() 00271 * - Replace() 00272 */ 00273 bool Set(const KeyType &Key, const ValueType &Value); 00274 00275 /** 00276 * @brief 00277 * Removes an element from the hash map slot list 00278 * 00279 * @param[in] Key 00280 * The key which should be removed 00281 * 00282 * @return 00283 * 'true' if all went fine, else 'false' 00284 */ 00285 bool Remove(const KeyType &Key); 00286 00287 /** 00288 * @brief 00289 * Removes all elements with a certain value from the map 00290 * 00291 * @param[in] Value 00292 * Value to look for 00293 * 00294 * @return 00295 * Number of removed elements 00296 */ 00297 uint32 RemoveValue(const ValueType &Value); 00298 00299 /** 00300 * @brief 00301 * Returns the value of a given key 00302 * 00303 * @param[in] Key 00304 * The key 00305 * 00306 * @return 00307 * Reference to the value corresponding to the key, reference to the 'Null'-object on error 00308 */ 00309 const ValueType &Get(const KeyType &Key) const; 00310 00311 /** 00312 * @brief 00313 * Returns the value of a given key 00314 * 00315 * @param[in] Key 00316 * The key 00317 * 00318 * @return 00319 * Reference to the value corresponding to the key, reference to the 'Null'-object on error 00320 */ 00321 ValueType &Get(const KeyType &Key); 00322 00323 00324 //[-------------------------------------------------------] 00325 //[ Private functions ] 00326 //[-------------------------------------------------------] 00327 public: 00328 /** 00329 * @brief 00330 * Copy constructor 00331 * 00332 * @param[in] cSource 00333 * Source to copy from 00334 */ 00335 SlotsList(const SlotsList &cSource); 00336 00337 00338 //[-------------------------------------------------------] 00339 //[ Private data ] 00340 //[-------------------------------------------------------] 00341 private: 00342 Slot *m_pFirstSlot; /**< Pointer to the first hash slot, can be a null pointer */ 00343 Slot *m_pLastSlot; /**< Pointer to the last hash slot, can be a null pointer */ 00344 00345 00346 }; 00347 00348 00349 //[-------------------------------------------------------] 00350 //[ Private data ] 00351 //[-------------------------------------------------------] 00352 private: 00353 uint32 m_nNumOfSlots; /**< The current number of slots */ 00354 SlotsList *m_plstSlots; /**< Slots list, can be a null pointer (created when the first element is added) */ 00355 uint32 m_nNumOfElements; /**< Current number of elements within the map */ 00356 00357 00358 //[-------------------------------------------------------] 00359 //[ Public virtual Iterable functions ] 00360 //[-------------------------------------------------------] 00361 public: 00362 virtual Iterator<ValueType> GetIterator(uint32 nIndex = 0) const override; 00363 virtual ConstIterator<ValueType> GetConstIterator(uint32 nIndex = 0) const override; 00364 virtual Iterator<ValueType> GetEndIterator() const override; 00365 virtual ConstIterator<ValueType> GetConstEndIterator() const override; 00366 00367 00368 //[-------------------------------------------------------] 00369 //[ Public virtual Map functions ] 00370 //[-------------------------------------------------------] 00371 public: 00372 virtual void Clear() override; 00373 virtual bool IsEmpty() const override; 00374 virtual uint32 GetNumOfElements() const override; 00375 virtual bool Add(const KeyType &Key, const ValueType &Value) override; 00376 virtual bool Replace(const KeyType &Key, const ValueType &NewValue) override; 00377 virtual bool Set(const KeyType &Key, const ValueType &Value) override; 00378 virtual bool Remove(const KeyType &Key) override; 00379 virtual uint32 RemoveValue(const ValueType &Value) override; 00380 virtual const ValueType &Get(const KeyType &Key) const override; 00381 virtual ValueType &Get(const KeyType &Key) override; 00382 virtual Iterator<KeyType> GetKeyIterator(uint32 nIndex = 0) const override; 00383 virtual ConstIterator<KeyType> GetConstKeyIterator(uint32 nIndex = 0) const override; 00384 virtual Iterator<KeyType> GetEndKeyIterator() const override; 00385 virtual ConstIterator<KeyType> GetConstEndKeyIterator() const override; 00386 00387 00388 //[-------------------------------------------------------] 00389 //[ Private virtual Map functions ] 00390 //[-------------------------------------------------------] 00391 private: 00392 virtual Map<KeyType, ValueType> &operator =(const Map<KeyType, ValueType> &cMap) override; 00393 00394 00395 }; 00396 00397 00398 //[-------------------------------------------------------] 00399 //[ Namespace ] 00400 //[-------------------------------------------------------] 00401 } // PLCore 00402 00403 00404 //[-------------------------------------------------------] 00405 //[ Implementation ] 00406 //[-------------------------------------------------------] 00407 #include "PLCore/Container/HashMap.inl" 00408 00409 00410 #endif // __PLCORE_CONTAINER_HASHMAP_H__
|