tDictionary.h
Engine/source/core/util/tDictionary.h
Classes:
class
class
class
class
class
Namespaces:
Detailed Description
1 2//----------------------------------------------------------------------------- 3// Copyright (c) 2012 GarageGames, LLC 4// 5// Permission is hereby granted, free of charge, to any person obtaining a copy 6// of this software and associated documentation files (the "Software"), to 7// deal in the Software without restriction, including without limitation the 8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 9// sell copies of the Software, and to permit persons to whom the Software is 10// furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21// IN THE SOFTWARE. 22//----------------------------------------------------------------------------- 23 24#ifndef _TDICTIONARY_H_ 25#define _TDICTIONARY_H_ 26 27#ifndef _STRINGFUNCTIONS_H_ 28#include "core/strings/stringFunctions.h" 29#endif 30#ifndef _HASHFUNCTION_H_ 31#include "core/util/hashFunction.h" 32#endif 33#ifndef _TORQUE_STRING_H_ 34#include "core/util/str.h" 35#endif 36 37#ifndef _DATACHUNKER_H_ 38#include "core/dataChunker.h" 39#endif 40 41 42// TODO: Maybe move these into a more general Tuple class? 43 44template<class A, class B> 45struct CompoundKey 46{ 47 A key1; 48 B key2; 49 50 CompoundKey() {}; 51 CompoundKey(const A & a, const B & b) { key1 = a; key2 = b; }; 52 53 bool operator==(const CompoundKey & compound) const { return key1==compound.key1 && key2==compound.key2; } 54}; 55 56template<class A, class B, class C> 57struct CompoundKey3 58{ 59 A key1; 60 B key2; 61 C key3; 62 63 CompoundKey3() {}; 64 CompoundKey3(const A & a, const B & b, const C & c) { key1 = a; key2 = b; key3 = c;}; 65 66 bool operator==(const CompoundKey3 & compound) const { return key1==compound.key1 && key2==compound.key2 && key3==compound.key3; } 67}; 68 69 70namespace DictHash 71{ 72 inline U32 hash(U32 data) 73 { 74 return data; 75 } 76 77 inline U32 hash(const StringCase &data) 78 { 79 return data.getHashCaseSensitive(); 80 } 81 82 inline U32 hash(const StringNoCase &data) 83 { 84 return data.getHashCaseInsensitive(); 85 } 86 87 inline U32 hash(const String &data) 88 { 89 return data.getHashCaseInsensitive(); 90 } 91 92 inline U32 hash(const char *data) 93 { 94 return Torque::hash( (const U8 *)data, dStrlen( data ), 0 ); 95 } 96 97 inline U32 hash(const void *data) 98 { 99 return (uintptr_t)data; 100 } 101 102 template<class A, class B> 103 inline U32 hash(const CompoundKey<A,B> & compound) 104 { 105 return hash(compound.key1) + hash(compound.key2); 106 } 107 108 template<class A, class B, class C> 109 inline U32 hash(const CompoundKey3<A,B,C> & compound) 110 { 111 return hash(compound.key1) + hash(compound.key2) + hash(compound.key3); 112 } 113 114 U32 nextPrime(U32); 115}; 116 117namespace KeyCmp 118{ 119 template<typename Key> 120 inline bool equals( const Key &keya, const Key &keyb ) 121 { 122 return ( keya == keyb ); 123 } 124 125 template<> 126 inline bool equals<>( const StringCase &keya, const StringCase &keyb ) 127 { 128 return ( keya.equal( keyb, String::Case ) ); 129 } 130 131 template<> 132 inline bool equals<>( const StringNoCase &keya, const StringNoCase &keyb ) 133 { 134 return ( keya.equal( keyb, String::NoCase ) ); 135 } 136 137 template<> 138 inline bool equals<>( const String &keya, const String &keyb ) 139 { 140 return ( keya.equal( keyb, String::NoCase ) ); 141 } 142 143 template<> 144 inline bool equals<>( const char * const &keya, const char * const &keyb ) 145 { 146 return ( String::compare( keya, keyb ) == 0 ); 147 } 148}; 149 150/// A HashTable template class. 151/// 152/// The hash table class maps between a key and an associated value. Access 153/// using the key is performed using a hash table. The class provides 154/// methods for both unique and equal keys. The global ::hash(Type) function 155/// is used for hashing, see util/hash.h 156/// @ingroup UtilContainers 157template<typename Key, typename Value > 158class HashTable 159{ 160public: 161 struct Pair 162 { 163 Key key; 164 Value value; 165 Pair() {} 166 Pair(Key k,Value v) 167 : key(k), 168 value(v) 169 {} 170 }; 171 172private: 173 struct Node 174 { 175 Node* mNext; 176 Pair mPair; 177 Node(): mNext(0) {} 178 Node(Pair p,Node* n) 179 : mNext(n), 180 mPair(p) 181 {} 182 }; 183 184 Node** mTable; ///< Hash table 185 S32 mTableSize; ///< Hash table size 186 U32 mSize; ///< Number of keys in the table 187 ClassChunker<Node> mNodeAllocator; 188 189 U32 _hash(const Key& key) const; 190 U32 _index(const Key& key) const; 191 Node* _next(U32 index) const; 192 void _resize(U32 size); 193 void _destroy(); 194 195public: 196 // Iterator support 197 template<typename U,typename E, typename M> 198 class _Iterator { 199 friend class HashTable; 200 E* mLink; 201 M* mHashTable; 202 operator E*(); 203 public: 204 typedef U ValueType; 205 typedef U* Pointer; 206 typedef U& Reference; 207 208 _Iterator() 209 { 210 mHashTable = 0; 211 mLink = 0; 212 } 213 214 _Iterator(M* table,E* ptr) 215 { 216 mHashTable = table; 217 mLink = ptr; 218 } 219 220 _Iterator& operator++() 221 { 222 mLink = mLink->mNext? mLink->mNext : 223 mHashTable->_next(mHashTable->_index(mLink->mPair.key) + 1); 224 return *this; 225 } 226 227 _Iterator operator++(int) 228 { 229 _Iterator itr(*this); 230 ++(*this); 231 return itr; 232 } 233 234 bool operator==(const _Iterator& b) const 235 { 236 return mHashTable == b.mHashTable && mLink == b.mLink; 237 } 238 239 bool operator!=(const _Iterator& b) const 240 { 241 return !(*this == b); 242 } 243 244 U* operator->() const 245 { 246 return &mLink->mPair; 247 } 248 249 U& operator*() const 250 { 251 return mLink->mPair; 252 } 253 }; 254 255 // Types 256 typedef Pair ValueType; 257 typedef Pair& Reference; 258 typedef const Pair& ConstReference; 259 260 typedef _Iterator<Pair,Node,HashTable> Iterator; 261 typedef _Iterator<const Pair,const Node,const HashTable> ConstIterator; 262 typedef S32 DifferenceType; 263 typedef U32 SizeType; 264 265 // Initialization 266 HashTable(); 267 ~HashTable(); 268 HashTable(const HashTable& p); 269 270 // Management 271 U32 size() const; ///< Return the number of elements 272 U32 tableSize() const; ///< Return the size of the hash bucket table 273 void clear(); ///< Empty the HashTable 274 void resize(U32 size); 275 bool isEmpty() const; ///< Returns true if the table is empty 276 F32 collisions() const; ///< Returns the average number of nodes per bucket 277 278 // Insert & erase elements 279 Iterator insertEqual(const Key& key, const Value&); 280 Iterator insertUnique(const Key& key, const Value&); 281 void erase(Iterator); ///< Erase the given entry 282 void erase(const Key& key); ///< Erase all matching keys from the table 283 void erase(const Key & key, const Value & value); ///< Erase entry for this key-value pair 284 285 // HashTable lookup 286 Iterator findOrInsert(const Key& key); 287 Iterator find(const Key&); ///< Find the first entry for the given key 288 ConstIterator find(const Key&) const; ///< Find the first entry for the given key 289 bool find(const Key & key, Value & value); ///< Find the first entry for the given key 290 S32 count(const Key&) const; ///< Count the number of matching keys in the table 291 292 // Forward Iterator access 293 Iterator begin(); ///< Iterator to first element 294 ConstIterator begin() const; ///< Iterator to first element 295 Iterator end(); ///< Iterator to last element + 1 296 ConstIterator end() const; ///< Iterator to last element + 1 297 298 void operator=(const HashTable& p); 299}; 300 301template<typename Key, typename Value> HashTable<Key,Value>::HashTable() : mNodeAllocator(512) 302{ 303 mTableSize = 0; 304 mTable = 0; 305 mSize = 0; 306} 307 308template<typename Key, typename Value> HashTable<Key,Value>::HashTable(const HashTable& p) : mNodeAllocator(512) 309{ 310 mSize = 0; 311 mTableSize = 0; 312 mTable = 0; 313 *this = p; 314} 315 316template<typename Key, typename Value> HashTable<Key,Value>::~HashTable() 317{ 318 _destroy(); 319} 320 321//----------------------------------------------------------------------------- 322 323template<typename Key, typename Value> 324inline U32 HashTable<Key,Value>::_hash(const Key& key) const 325{ 326 return DictHash::hash(key); 327} 328 329template<typename Key, typename Value> 330inline U32 HashTable<Key,Value>::_index(const Key& key) const 331{ 332 return _hash(key) % mTableSize; 333} 334 335template<typename Key, typename Value> 336typename HashTable<Key,Value>::Node* HashTable<Key,Value>::_next(U32 index) const 337{ 338 for (; index < mTableSize; index++) 339 if (Node* node = mTable[index]) 340 return node; 341 return 0; 342} 343 344template<typename Key, typename Value> 345void HashTable<Key,Value>::_resize(U32 size) 346{ 347 S32 currentSize = mTableSize; 348 mTableSize = DictHash::nextPrime(size); 349 Node** table = new Node*[mTableSize]; 350 dMemset(table,0,mTableSize * sizeof(Node*)); 351 352 for (S32 i = 0; i < currentSize; i++) 353 for (Node* node = mTable[i]; node; ) 354 { 355 // Get groups of matching keys 356 Node* last = node; 357 while (last->mNext && last->mNext->mPair.key == node->mPair.key) 358 last = last->mNext; 359 360 // Move the chain to the new table 361 Node** link = &table[_index(node->mPair.key)]; 362 Node* tmp = last->mNext; 363 last->mNext = *link; 364 *link = node; 365 node = tmp; 366 } 367 368 delete[] mTable; 369 mTable = table; 370} 371 372template<typename Key, typename Value> 373void HashTable<Key,Value>::_destroy() 374{ 375 // Call destructors. 376 for (S32 i = 0; i < mTableSize; i++) 377 for (Node* ptr = mTable[i]; ptr; ) 378 { 379 Node *tmp = ptr; 380 ptr = ptr->mNext; 381 destructInPlace( tmp ); 382 } 383 384 mNodeAllocator.freeBlocks(); 385 delete[] mTable; 386 mTable = NULL; 387} 388 389 390//----------------------------------------------------------------------------- 391// management 392 393template<typename Key, typename Value> 394inline U32 HashTable<Key,Value>::size() const 395{ 396 return mSize; 397} 398 399template<typename Key, typename Value> 400inline U32 HashTable<Key,Value>::tableSize() const 401{ 402 return mTableSize; 403} 404 405template<typename Key, typename Value> 406inline void HashTable<Key,Value>::clear() 407{ 408 _destroy(); 409 mTableSize = 0; 410 mSize = 0; 411} 412 413/// Resize the bucket table for an estimated number of elements. 414/// This method will optimize the hash bucket table size to hold the given 415/// number of elements. The size argument is a hint, and will not be the 416/// exact size of the table. If the table is sized down below it's optimal 417/// size, the next insert will cause it to be resized again. Normally this 418/// function is used to avoid resizes when the number of elements that will 419/// be inserted is known in advance. 420template<typename Key, typename Value> 421inline void HashTable<Key,Value>::resize(U32 size) 422{ 423 // Attempt to resize the datachunker as well. 424 mNodeAllocator.setChunkSize(sizeof(Node) * size); 425 _resize(size); 426} 427 428template<typename Key, typename Value> 429inline bool HashTable<Key,Value>::isEmpty() const 430{ 431 return mSize == 0; 432} 433 434template<typename Key, typename Value> 435inline F32 HashTable<Key,Value>::collisions() const 436{ 437 S32 chains = 0; 438 for (S32 i = 0; i < mTableSize; i++) 439 if (mTable[i]) 440 chains++; 441 return F32(mSize) / chains; 442} 443 444 445//----------------------------------------------------------------------------- 446// add & remove elements 447 448/// Insert the key value pair but don't insert duplicates. 449/// This insert method does not insert duplicate keys. If the key already exists in 450/// the table the function will fail and end() is returned. 451template<typename Key, typename Value> 452typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::insertUnique(const Key& key, const Value& x) 453{ 454 if (mSize >= mTableSize) 455 _resize(mSize + 1); 456 Node** table = &mTable[_index(key)]; 457 for (Node* itr = *table; itr; itr = itr->mNext) 458 if ( KeyCmp::equals<Key>( itr->mPair.key, key) ) 459 return end(); 460 461 mSize++; 462 Node* newNode = mNodeAllocator.alloc(); 463 newNode->mPair = Pair(key, x); 464 newNode->mNext = *table; 465 *table = newNode; 466 return Iterator(this,*table); 467} 468 469/// Insert the key value pair and allow duplicates. 470/// This insert method allows duplicate keys. Keys are grouped together but 471/// are not sorted. 472template<typename Key, typename Value> 473typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::insertEqual(const Key& key, const Value& x) 474{ 475 if (mSize >= mTableSize) 476 _resize(mSize + 1); 477 // The new key is inserted at the head of any group of matching keys. 478 Node** prev = &mTable[_index(key)]; 479 for (Node* itr = *prev; itr; prev = &itr->mNext, itr = itr->mNext) 480 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) 481 break; 482 mSize++; 483 Node* newNode = mNodeAllocator.alloc(); 484 newNode->mPair = Pair(key, x); 485 newNode->mNext = *prev; 486 *prev = newNode; 487 return Iterator(this,*prev); 488} 489 490template<typename Key, typename Value> 491void HashTable<Key,Value>::erase(const Key& key) 492{ 493 if (mTable==<a href="/coding/file/types_8lint_8h/#types_8lint_8h_1a070d2ce7b6bb7e5c05602aa8c308d0c4">NULL</a>) 494 return; 495 Node** prev = &mTable[_index(key)]; 496 for (Node* itr = *prev; itr; prev = &itr->mNext, itr = itr->mNext) 497 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) { 498 // Delete matching keys, which should be grouped together. 499 do { 500 Node* tmp = itr; 501 itr = itr->mNext; 502 mNodeAllocator.free(tmp); 503 mSize--; 504 } while (itr && KeyCmp::equals<Key>( itr->mPair.key, key ) ); 505 *prev = itr; 506 return; 507 } 508} 509 510template<typename Key, typename Value> 511void HashTable<Key,Value>::erase(Iterator node) 512{ 513 if (mTable==<a href="/coding/file/types_8lint_8h/#types_8lint_8h_1a070d2ce7b6bb7e5c05602aa8c308d0c4">NULL</a>) 514 return; 515 Node** prev = &mTable[_index(node->key)]; 516 for (Node* itr = *prev; itr; prev = &itr->mNext, itr = itr->mNext) 517 { 518 if (itr == node.mLink) 519 { 520 *prev = itr->mNext; 521 mNodeAllocator.free(itr); 522 mSize--; 523 return; 524 } 525 } 526} 527 528template<typename Key, typename Value> 529void HashTable<Key,Value>::erase(const Key & key, const Value & value) 530{ 531 if (mTable==<a href="/coding/file/types_8lint_8h/#types_8lint_8h_1a070d2ce7b6bb7e5c05602aa8c308d0c4">NULL</a>) 532 return; 533 Node** prev = &mTable[_index(key)]; 534 for (Node* itr = *prev; itr; prev = &itr->mNext, itr = itr->mNext) 535 { 536 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) && itr->mPair.value == value) 537 { 538 *prev = itr->mNext; 539 mNodeAllocator.free(itr); 540 mSize--; 541 return; 542 } 543 } 544} 545 546//----------------------------------------------------------------------------- 547 548/// Find the key, or insert a one if it doesn't exist. 549/// Returns the first key in the table that matches, or inserts one if there 550/// are none. 551template<typename Key, typename Value> 552typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::findOrInsert(const Key& key) 553{ 554 if (mSize >= mTableSize) 555 _resize(mSize + 1); 556 Node** table = &mTable[_index(key)]; 557 for (Node* itr = *table; itr; itr = itr->mNext) 558 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) 559 return Iterator(this,itr); 560 mSize++; 561 Node* newNode = mNodeAllocator.alloc(); 562 newNode->mPair = Pair(key, Value()); 563 newNode->mNext = *table; 564 *table = newNode; 565 return Iterator(this,*table); 566} 567 568template<typename Key, typename Value> 569typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::find(const Key& key) 570{ 571 if (mTableSize) 572 for (Node* itr = mTable[_index(key)]; itr; itr = itr->mNext) 573 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) 574 return Iterator(this,itr); 575 return Iterator(this,0); 576} 577 578template<typename Key, typename Value> 579typename HashTable<Key,Value>::ConstIterator HashTable<Key,Value>::find(const Key& key) const 580{ 581 if (mTableSize) 582 { 583 for (Node* itr = mTable[_index(key)]; itr; itr = itr->mNext) 584 { 585 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) 586 return ConstIterator(this,itr); 587 } 588 } 589 return ConstIterator(this,0); 590} 591 592template<typename Key, typename Value> 593bool HashTable<Key,Value>::find(const Key & key, Value & value) 594{ 595 if (mTableSize) 596 { 597 for (Node* itr = mTable[_index(key)]; itr; itr = itr->mNext) 598 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) 599 { 600 value = itr->mPair.value; 601 return true; 602 } 603 } 604 return false; 605} 606 607template<typename Key, typename Value> 608S32 HashTable<Key,Value>::count(const Key& key) const 609{ 610 S32 count = 0; 611 if (mTableSize) 612 for (Node* itr = mTable[_index(key)]; itr; itr = itr->mNext) 613 if ( KeyCmp::equals<Key>( itr->mPair.key, key ) ) { 614 // Matching keys should be grouped together. 615 do { 616 count++; 617 itr = itr->mNext; 618 } while (itr && KeyCmp::equals<Key>( itr->mPair.key, key ) ); 619 break; 620 } 621 return count; 622} 623 624 625//----------------------------------------------------------------------------- 626// Iterator access 627 628template<typename Key, typename Value> 629inline typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::begin() 630{ 631 return Iterator(this,_next(0)); 632} 633 634template<typename Key, typename Value> 635inline typename HashTable<Key,Value>::ConstIterator HashTable<Key,Value>::begin() const 636{ 637 return ConstIterator(this,_next(0)); 638} 639 640template<typename Key, typename Value> 641inline typename HashTable<Key,Value>::Iterator HashTable<Key,Value>::end() 642{ 643 return Iterator(this,0); 644} 645 646template<typename Key, typename Value> 647inline typename HashTable<Key,Value>::ConstIterator HashTable<Key,Value>::end() const 648{ 649 return ConstIterator(this,0); 650} 651 652 653//----------------------------------------------------------------------------- 654// operators 655 656template<typename Key, typename Value> 657void HashTable<Key,Value>::operator=(const HashTable& p) 658{ 659 _destroy(); 660 mTableSize = p.mTableSize; 661 mTable = new Node*[mTableSize]; 662 mSize = p.mSize; 663 for (S32 i = 0; i < mTableSize; i++) 664 if (Node* itr = p.mTable[i]) 665 { 666 Node** head = &mTable[i]; 667 do 668 { 669 *head = new Node(itr->mPair,0); 670 head = &(*head)->mNext; 671 itr = itr->mNext; 672 } while (itr); 673 } 674 else 675 mTable[i] = 0; 676} 677 678//----------------------------------------------------------------------------- 679// Iterator class 680 681/// A Map template class. 682/// The map class maps between a key and an associated value. Keys 683/// are unique. 684/// The hash table class is used as the default implementation so the 685/// the key must be hashable, see util/hash.h for details. 686/// @ingroup UtilContainers 687template<typename Key, typename Value, class Sequence = HashTable<Key,Value> > 688class Map 689{ 690public: 691 // types 692 typedef typename Sequence::Pair Pair; 693 typedef Pair ValueType; 694 typedef Pair& Reference; 695 typedef const Pair& ConstReference; 696 697 typedef typename Sequence::Iterator Iterator; 698 typedef typename Sequence::ConstIterator ConstIterator; 699 typedef S32 DifferenceType; 700 typedef U32 SizeType; 701 702 // initialization 703 Map() {} 704 ~Map() {} 705 Map(const Map& p); 706 707 // management 708 U32 size() const; ///< Return the number of elements 709 void resize(U32 size); 710 void clear(); ///< Empty the Map 711 bool isEmpty() const; ///< Returns true if the map is empty 712 713 // insert & erase elements 714 Iterator insert(const Key& key, const Value&); // Documented below... 715 void erase(Iterator); ///< Erase the given entry 716 void erase(const Key& key); ///< Erase the key from the map 717 718 // Map lookup 719 Iterator find(const Key&); ///< Find entry for the given key 720 ConstIterator find(const Key&) const; ///< Find entry for the given key 721 bool contains(const Key&a) const 722 { 723 return mMap.count(a) > 0; 724 } 725 /// Try to get the value of the specified key. Returns true and fills in the value 726 /// if the key exists. Returns false otherwise. 727 /// Unlike operator [], this function does not create the key/value if the key 728 /// is not found. 729 bool tryGetValue(const Key& key, Value& val) const 730 { 731 ConstIterator iter = find(key); 732 if (iter != end()) 733 { 734 val = (*iter).value; 735 return true; 736 } 737 return false; 738 } 739 740 // forward Iterator access 741 Iterator begin(); ///< Iterator to first element 742 ConstIterator begin() const; ///< Iterator to first element 743 Iterator end(); ///< IIterator to last element + 1 744 ConstIterator end() const; ///< Iterator to last element + 1 745 746 // operators 747 /// Index using the given key. If the key is not currently in the map it is added. 748 /// If you just want to try to get the value without the side effect of creating the 749 /// key, use tryGetValue() instead. 750 Value& operator[](const Key&); 751 752private: 753 Sequence mMap; 754}; 755 756template<typename Key, typename Value, class Sequence> Map<Key,Value,Sequence>::Map(const Map& p) 757{ 758 *this = p; 759} 760 761 762//----------------------------------------------------------------------------- 763// management 764 765template<typename Key, typename Value, class Sequence> 766inline U32 Map<Key,Value,Sequence>::size() const 767{ 768 return mMap.size(); 769} 770 771template<typename Key, typename Value, class Sequence> 772inline void Map<Key,Value,Sequence>::resize(U32 size) 773{ 774 return mMap.resize(size); 775} 776 777template<typename Key, typename Value, class Sequence> 778inline void Map<Key,Value,Sequence>::clear() 779{ 780 mMap.clear(); 781} 782 783template<typename Key, typename Value, class Sequence> 784inline bool Map<Key,Value,Sequence>::isEmpty() const 785{ 786 return mMap.isEmpty(); 787} 788 789 790//----------------------------------------------------------------------------- 791// add & remove elements 792 793/// Insert the key value pair but don't allow duplicates. 794/// The map class does not allow duplicates keys. If the key already exists in 795/// the map the function will fail and return end(). 796template<typename Key, typename Value, class Sequence> 797typename Map<Key,Value,Sequence>::Iterator Map<Key,Value,Sequence>::insert(const Key& key, const Value& x) 798{ 799 return mMap.insertUnique(key,x); 800} 801 802template<typename Key, typename Value, class Sequence> 803void Map<Key,Value,Sequence>::erase(const Key& key) 804{ 805 mMap.erase(key); 806} 807 808template<typename Key, typename Value, class Sequence> 809void Map<Key,Value,Sequence>::erase(Iterator node) 810{ 811 mMap.erase(node); 812} 813 814 815//----------------------------------------------------------------------------- 816// Searching 817 818template<typename Key, typename Value, class Sequence> 819typename Map<Key,Value,Sequence>::Iterator Map<Key,Value,Sequence>::find(const Key& key) 820{ 821 return mMap.find(key); 822} 823 824template<typename Key, typename Value, class Sequence> 825typename Map<Key,Value,Sequence>::ConstIterator Map<Key,Value,Sequence>::find(const Key& key) const 826{ 827 return mMap.find(key); 828} 829 830//----------------------------------------------------------------------------- 831// Iterator access 832 833template<typename Key, typename Value, class Sequence> 834inline typename Map<Key,Value,Sequence>::Iterator Map<Key,Value,Sequence>::begin() 835{ 836 return mMap.begin(); 837} 838 839template<typename Key, typename Value, class Sequence> 840inline typename Map<Key,Value,Sequence>::ConstIterator Map<Key,Value,Sequence>::begin() const 841{ 842 return mMap.begin(); 843} 844 845template<typename Key, typename Value, class Sequence> 846inline typename Map<Key,Value,Sequence>::Iterator Map<Key,Value,Sequence>::end() 847{ 848 return mMap.end(); 849} 850 851template<typename Key, typename Value, class Sequence> 852inline typename Map<Key,Value,Sequence>::ConstIterator Map<Key,Value,Sequence>::end() const 853{ 854 return mMap.end(); 855} 856 857 858//----------------------------------------------------------------------------- 859// operators 860 861template<typename Key, typename Value, class Sequence> 862inline Value& Map<Key,Value,Sequence>::operator[](const Key& key) 863{ 864 return mMap.findOrInsert(key)->value; 865} 866 867 868//----------------------------------------------------------------------------- 869// iterator class 870 871/// A HashMap template class. 872/// The map class maps between a key and an associated value. Keys 873/// are unique. 874/// The hash table class is used as the default implementation so the 875/// the key must be hashable, see util/hash.h for details. 876/// @ingroup UtilContainers 877template<typename Key, typename Value, class Sequence = HashTable<Key, Value> > 878class HashMap : private Sequence 879{ 880 typedef HashTable<Key, Value> Parent; 881 882private: 883 Sequence mHashMap; 884 885public: 886 // types 887 typedef typename Parent::Pair Pair; 888 typedef Pair ValueType; 889 typedef Pair& Reference; 890 typedef const Pair& ConstReference; 891 892 typedef typename Parent::Iterator iterator; 893 typedef typename Parent::ConstIterator const_iterator; 894 typedef S32 DifferenceType; 895 typedef U32 SizeType; 896 897 // initialization 898 HashMap() {} 899 ~HashMap() {} 900 HashMap(const HashMap& p); 901 902 // management 903 U32 size() const; ///< Return the number of elements 904 void clear(); ///< Empty the HashMap 905 bool isEmpty() const; ///< Returns true if the map is empty 906 907 // insert & erase elements 908 iterator insert(const Key& key, const Value&); // Documented below... 909 void erase(iterator); ///< Erase the given entry 910 void erase(const Key& key); ///< Erase the key from the map 911 912 // HashMap lookup 913 iterator find(const Key&); ///< Find entry for the given key 914 const_iterator find(const Key&) const; ///< Find entry for the given key 915 bool contains(const Key&a) 916 { 917 return mHashMap.count(a) > 0; 918 } 919 920 // forward iterator access 921 iterator begin(); ///< iterator to first element 922 const_iterator begin() const; ///< iterator to first element 923 iterator end(); ///< IIterator to last element + 1 924 const_iterator end() const; ///< iterator to last element + 1 925 926 // operators 927 Value& operator[](const Key&); ///< Index using the given key. If the key is not currently in the map it is added. 928}; 929 930template<typename Key, typename Value, class Sequence> HashMap<Key, Value, Sequence>::HashMap(const HashMap& p) 931{ 932 *this = p; 933} 934 935 936//----------------------------------------------------------------------------- 937// management 938 939template<typename Key, typename Value, class Sequence> 940inline U32 HashMap<Key, Value, Sequence>::size() const 941{ 942 return mHashMap.size(); 943} 944 945template<typename Key, typename Value, class Sequence> 946inline void HashMap<Key, Value, Sequence>::clear() 947{ 948 mHashMap.clear(); 949} 950 951template<typename Key, typename Value, class Sequence> 952inline bool HashMap<Key, Value, Sequence>::isEmpty() const 953{ 954 return mHashMap.isEmpty(); 955} 956 957 958//----------------------------------------------------------------------------- 959// add & remove elements 960 961/// Insert the key value pair but don't allow duplicates. 962/// The map class does not allow duplicates keys. If the key already exists in 963/// the map the function will fail and return end(). 964template<typename Key, typename Value, class Sequence> 965typename HashMap<Key, Value, Sequence>::iterator HashMap<Key, Value, Sequence>::insert(const Key& key, const Value& x) 966{ 967 return mHashMap.insertUnique(key, x); 968} 969 970template<typename Key, typename Value, class Sequence> 971void HashMap<Key, Value, Sequence>::erase(const Key& key) 972{ 973 mHashMap.erase(key); 974} 975 976template<typename Key, typename Value, class Sequence> 977void HashMap<Key, Value, Sequence>::erase(iterator node) 978{ 979 mHashMap.erase(node); 980} 981 982 983//----------------------------------------------------------------------------- 984// Searching 985 986template<typename Key, typename Value, class Sequence> 987typename HashMap<Key, Value, Sequence>::iterator HashMap<Key, Value, Sequence>::find(const Key& key) 988{ 989 return mHashMap.find(key); 990} 991 992//----------------------------------------------------------------------------- 993// iterator access 994 995template<typename Key, typename Value, class Sequence> 996inline typename HashMap<Key, Value, Sequence>::iterator HashMap<Key, Value, Sequence>::begin() 997{ 998 return mHashMap.begin(); 999} 1000 1001template<typename Key, typename Value, class Sequence> 1002inline typename HashMap<Key, Value, Sequence>::const_iterator HashMap<Key, Value, Sequence>::begin() const 1003{ 1004 return mHashMap.begin(); 1005} 1006 1007template<typename Key, typename Value, class Sequence> 1008inline typename HashMap<Key, Value, Sequence>::iterator HashMap<Key, Value, Sequence>::end() 1009{ 1010 return mHashMap.end(); 1011} 1012 1013template<typename Key, typename Value, class Sequence> 1014inline typename HashMap<Key, Value, Sequence>::const_iterator HashMap<Key, Value, Sequence>::end() const 1015{ 1016 return mHashMap.end(); 1017} 1018 1019 1020//----------------------------------------------------------------------------- 1021// operators 1022 1023template<typename Key, typename Value, class Sequence> 1024inline Value& HashMap<Key, Value, Sequence>::operator[](const Key& key) 1025{ 1026 return mHashMap.findOrInsert(key)->value; 1027} 1028 1029#endif 1030 1031