2 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
4 // Licensed under the Apache License, Version 2.0 (the License);
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
8 // http://www.apache.org/licenses/LICENSE-2.0
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
18 * @file FBaseColMultiHashMapT.h
19 * @brief This is the header file for the %MultiHashMapT class.
21 * This header file contains the declarations of the %MultiHashMapT class.
23 #ifndef _FBASE_COL_MULTI_HASH_MAP_T_H_
24 #define _FBASE_COL_MULTI_HASH_MAP_T_H_
26 #include <FBaseObject.h>
27 #include <FBaseResult.h>
28 #include <FBaseColIComparerT.h>
29 #include <FBaseColIHashCodeProviderT.h>
30 #include <FBaseColIListT.h>
31 #include <FBaseColIMultiMapT.h>
32 #include <FBaseColMapEntryT.h>
33 #include <FBaseComparerT.h>
34 #include <FBaseFloat.h>
36 namespace Tizen { namespace Base { namespace Collection
39 template< class KeyType, class ValueType > class __MultiHashMapEntryT;
40 template< class KeyType, class ValueType > class __MultiHashMapEnumeratorT;
41 template< class KeyType, class ValueType > class __EntryValueEnumeratorT;
42 template< class KeyType > class __MultiHashMapDefaultProviderT;
44 template< class ValueType > class __ValueNodeT;
47 * @class MultiHashMapT
48 * @brief This class represents a template-based collection of associated keys and values that are organized based on the hash code of the key.
52 * The %MultiHashMapT class represents a template-based collection of associated keys and values that are organized based on the hash code of the key.
53 * There is no limit on the number of elements with the same key, but duplicated elements with the same key are not allowed.
54 * The key and value cannot be null. Several methods in the %MultiHashMapT class need an assignment(=) operator of KeyType, and assignment(=) and equivalent(==) operators of ValueType.
56 * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/hashmap_multihashmap.htm">HashMap and MultiHashMap</a>.
58 * The following example demonstrates how to use the %MultiHashMapT class.
65 * using namespace Tizen::Base;
66 * using namespace Tizen::Base::Collection;
69 * MyClass::MultiHashMapTSample(void)
71 * MultiHashMapT< int, int > map;
73 * // Constructs a MultiHashMap instance with default capacity, load factor, hash code provider, and comparer
79 * map.Add(1, 1000); // map.GetCount() : 1, map : (1 -> 1000)
80 * map.Add(2, 2000); // map.GetCount() : 2, map : (1 -> 1000), (2 -> 2000)
81 * map.Add(3, 3000); // map.GetCount() : 3, map : (1 -> 1000), (2 -> 2000), (3 -> 3000)
82 * map.Add(3, 30); // map.GetCount() : 4, map : (1 -> 1000), (2 -> 2000), (3 -> 3000, 30)
84 * // Gets values with the specified key
86 * IEnumeratorT< int >* pValueEnum = map.GetValuesN(key);
87 * while (pValueEnum->MoveNext() == E_SUCCESS)
89 * pValueEnum->GetCurrent(value);
94 * // Removes the values with the specified key
96 * map.Remove(key); // 30, 3000 removed
98 * // Uses an enumerator to access elements in the map
99 * IMapEnumeratorT< int, int >* pMapEnum = map.GetMapEnumeratorN();
100 * while (pMapEnum->MoveNext() == E_SUCCESS)
102 * pMapEnum->GetKey(key);
103 * pMapEnum->GetValue(value);
111 template< class KeyType, class ValueType >
113 : public IMultiMapT< KeyType, ValueType >
118 * The object is not fully constructed after this constructor is called. For full construction, @n
119 * the Construct() method must be called right after calling this constructor.
131 , __defaultConstruct(false)
137 * This destructor overrides Tizen::Base::Object::~Object().
141 virtual ~MultiHashMapT(void)
143 if (null != __pTable)
149 if (__defaultConstruct)
158 * Initializes this instance of %MultiHashMapT with the given capacity and load factor.
162 * @return An error code
163 * @param[in] capacity The initial capacity
164 * @param[in] loadFactor The maximum ratio of elements to buckets
165 * @exception E_SUCCESS The method is successful.
166 * @exception E_INVALID_ARG A specified input parameter is invalid, or
167 * the specified @c capacity or the @c loadFactor is negative.
168 * @remarks The key type must be a primitive data type.
169 * @see MultiHashMapT()
171 result Construct(int capacity = 16, float loadFactor = 0.75)
173 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
174 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
176 result r = E_SUCCESS;
181 __capacity = DEFAULT_CAPACITY;
186 while (__capacity < capacity)
193 if (Float::Compare(loadFactor, 0) == 0)
195 __loadFactor = DEFAULT_LOAD_FACTOR;
199 __loadFactor = loadFactor;
203 __threshold = static_cast< int >(__capacity * __loadFactor);
205 // set hash code provider
206 __pProvider = new __MultiHashMapDefaultProviderT< KeyType >();
207 TryCatch(__pProvider != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
210 __pComparer = new Tizen::Base::ComparerT< KeyType >();
211 TryCatch(__pComparer != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
213 __defaultConstruct = true;
215 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
216 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
218 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
231 * Initializes this instance of %MultiHashMapT by copying the elements of the specified map.
235 * @return An error code
236 * @param[in] map A map to copy
237 * @param[in] loadFactor The maximum ratio of elements to buckets @n
238 * If it is @c 0, the default load factor(0.75) is used.
239 * @exception E_SUCCESS The method is successful.
240 * @exception E_INVALID_ARG A specified input parameter is invalid, or
241 * the specified @c loadFactor is negative.
242 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
243 * the @c map is modified during the operation of this method.
244 * @see MultiHashMapT()
246 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
248 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
250 result r = E_SUCCESS;
252 if (Float::Compare(loadFactor, 0) == 0)
254 loadFactor = DEFAULT_LOAD_FACTOR;
257 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
258 r = Construct(capacity, loadFactor);
259 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
262 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
283 * Initializes this instance of %MultiHashMapT that is empty,
284 * with the specified initial capacity, load factor, hash code provider, and comparer.
288 * @return An error code
289 * @param[in] capacity The initial capacity @n
290 * If it is @c 0, the default capacity(16) is used.
291 * @param[in] loadFactor The maximum ratio of elements to buckets @n
292 * If it is @c 0, the default load factor(0.75) is used.
293 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
294 * for all keys in this map
295 * @param[in] comparer An instance of the IComparer derived class to use when comparing keys
296 * @exception E_SUCCESS The method is successful.
297 * @exception E_INVALID_ARG A specified input parameter is invalid, or
298 * the specified @c capacity or the @c loadFactor is negative.
299 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
300 * @see MultiHashMapT()
302 result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
303 const IComparerT< KeyType >& comparer)
305 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
306 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
308 result r = E_SUCCESS;
312 __capacity = DEFAULT_CAPACITY;
317 while (__capacity < capacity)
324 if (Float::Compare(loadFactor, 0) == 0)
326 __loadFactor = DEFAULT_LOAD_FACTOR;
330 __loadFactor = loadFactor;
334 __threshold = static_cast< int >(__capacity * __loadFactor);
336 // set hash code provider
337 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
340 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
342 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
343 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
345 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
358 * Initializes this instance of %MultiHashMapT by copying the elements of the specified map,
359 * with the specified load factor, hash code provider, and comparer.
363 * @return An error code
364 * @param[in] map A map to copy
365 * @param[in] loadFactor The maximum ratio of elements to buckets @n
366 * If it is @c 0, the default load factor(0.75) is used.
367 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
368 * for all keys in this map
369 * @param[in] comparer An instance of the IComparer derived class to use when comparing keys
370 * @exception E_SUCCESS The method is successful.
371 * @exception E_INVALID_ARG A specified input parameter is invalid, or
372 * the specified @c loadFactor is negative.
373 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
374 * the @c map is modified during the operation of this method.
375 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
376 * @see MultiHashMapT()
378 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
379 const IComparerT< KeyType >& comparer)
381 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
383 result r = E_SUCCESS;
385 if (Float::Compare(loadFactor, 0) == 0)
387 loadFactor = DEFAULT_LOAD_FACTOR;
390 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
392 r = Construct(capacity, loadFactor, provider, comparer);
393 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
396 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
413 * Adds the specified key-value pair to this map.
417 * @return An error code
418 * @param[in] key A key of the value to add
419 * @param[in] value A value to add
420 * @exception E_SUCCESS The method is successful.
421 * @exception E_OBJ_ALREADY_EXIST The specified pair of @c key and @c value already exists.
422 * @exception E_INVALID_ARG A specified input parameter is invalid, or
423 * the comparer has failed to compare the keys.
424 * @remarks SetItem() can be used to set value to a key that does not already exist.
425 * However, setting a value to a key that already exists overwrites the value.
429 virtual result Add(const KeyType& key, const ValueType& value)
431 result r = E_SUCCESS;
432 int hash = Hash(key);
433 int i = hash & (__capacity - 1);
434 __ValueNodeT< ValueType >* pNode = null;
435 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
436 while (null != pEntry)
438 if (hash == pEntry->hash)
441 r = __pComparer->Compare(key, pEntry->key, cmpResult);
442 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
446 pNode = pEntry->pList;
449 if (pNode->value == value)
451 return E_OBJ_ALREADY_EXIST;
454 if (pNode->pNext != null)
456 pNode = pNode->pNext;
467 pEntry = pEntry->pNext;
470 __ValueNodeT< ValueType >* pNewNode = new __ValueNodeT< ValueType >(value);
471 TryReturn(pNewNode != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
473 // key is not exist in this map.
476 __MultiHashMapEntryT< KeyType, ValueType >* pNewEntry = new __MultiHashMapEntryT< KeyType, ValueType >(key, pNewNode, __pTable[i],
478 TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
479 __pTable[i] = pNewEntry;
481 // key is already exist in this map, but value is not.
484 // pNode is the last value associated to the key
485 pNode->pNext = pNewNode;
490 if (__count++ >= __threshold)
492 r = Resize(__capacity * 2);
493 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
500 * Gets an enumerator of this map.
504 * @return An enumerator (an instance of the %IMapEnumeratorT derived class) of this map, @n
505 * else @c null if an exception occurs
506 * @exception E_SUCCESS The method is successful.
507 * @exception E_OUT_OF_MEMORY The memory is insufficient.
508 * @remarks If the key has multiple values, the Enumeration proceeds as follows: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
509 * The specific error code can be accessed using the GetLastResult() method.
510 * @see Tizen::Base::Collection::IEnumerator
511 * @see Tizen::Base::Collection::IMapEnumerator
513 virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
515 result r = E_SUCCESS;
517 __MultiHashMapEnumeratorT< KeyType, ValueType >* pEnum = new __MultiHashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
518 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
520 SetLastResult(E_SUCCESS);
529 * Gets an IMapEnumerator of this map.
533 * @return An enumerator (an instance of the %IMapEnumeratorT derived class) of this map, @n
534 * else @c null if an exception occurs
535 * @exception E_SUCCESS The method is successful.
536 * @exception E_OUT_OF_MEMORY The memory is insufficient.
537 * @remarks If the key has multiple values, the Enumeration proceeds like this: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
538 * @remarks The specific error code can be accessed using the GetLastResult() method.
539 * @see Tizen::Base::Collection::IEnumerator
540 * @see Tizen::Base::Collection::IMapEnumerator
542 virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
544 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
548 * Gets an enumerator of the values associated with the specified key.
552 * @return An enumerator (an instance of the IEnumeratorT derived class) of the values associated with the specified key, @n
553 * else @c null if an exception occurs
554 * @param[in] key A key to locate
555 * @exception E_SUCCESS The method is successful.
556 * @exception E_INVALID_ARG A specified input parameter is invalid, or
557 * the comparer has failed to compare the keys.
558 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
559 * @remarks The specific error code can be accessed using the GetLastResult() method.
562 virtual IEnumeratorT< ValueType >* GetValuesN(const KeyType& key) const
564 result r = E_OBJ_NOT_FOUND;
566 int hash = Hash(key);
567 int i = hash & (__capacity - 1);
568 IEnumeratorT< ValueType >* pEnum = null;
570 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
572 if (hash == pEntry->hash)
575 r = __pComparer->Compare(key, pEntry->key, cmpResult);
576 TryCatch(r == E_SUCCESS, r = E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
580 pEnum = new __EntryValueEnumeratorT< KeyType, ValueType >(*pEntry, pEntry->modCount);
581 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
599 * Gets a list of all unique keys in this map.
603 * @return A list of all unique keys in this map, @n
604 * else @c null if an exception occurs
605 * @exception E_SUCCESS The method is successful.
606 * @exception E_OUT_OF_MEMORY The memory is insufficient.
607 * @remarks The specific error code can be accessed using the GetLastResult() method.
610 virtual IListT< KeyType >* GetKeysN(void) const
614 result r = E_SUCCESS;
617 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
618 r = pList->Construct(__count);
619 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
621 for (int i = 0; i < __capacity; i++)
623 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
625 r = pList->Add(pEntry->key);
626 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
641 * Gets a list of all the values in this map.
645 * @return A list of all the values in this map, @n
646 * else @c null if an exception occurs
647 * @exception E_SUCCESS The method is successful.
648 * @exception E_OUT_OF_MEMORY The memory is insufficient.
649 * @remarks The specific error code can be accessed using the GetLastResult() method.
652 virtual IListT< ValueType >* GetValuesN(void) const
656 result r = E_SUCCESS;
658 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
659 r = pList->Construct(__count);
660 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
662 for (int i = 0; i < __capacity; i++)
664 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
666 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
668 r = pList->Add(pNode->value);
669 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
684 * Removes all the values for the specified key.
688 * @return An error code
689 * @param[in] key The key to remove
690 * @exception E_SUCCESS The method is successful.
691 * @exception E_INVALID_ARG The specified input parameter is invalid, or
692 * the comparer has failed to compare the keys.
693 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
696 virtual result Remove(const KeyType& key)
698 result r = E_OBJ_NOT_FOUND;
699 int hash = Hash(key);
700 int i = hash & (__capacity - 1);
702 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
703 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
705 if (hash == pEntry->hash)
708 r = __pComparer->Compare(key, pEntry->key, cmpResult);
709 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
718 __pTable[i] = pEntry->pNext;
722 pPrev->pNext = pEntry->pNext;
725 __ValueNodeT< ValueType >* pNode = pEntry->pList;
726 while (null != pNode)
728 __ValueNodeT< ValueType >* pTemp = pNode;
729 pNode = pNode->pNext;
745 * Removes the specified value associated with the specified key. @n
746 * The key is also removed if there is no value associated with it.
750 * @return An error code
751 * @param[in] key The key whose mapping is to remove from the map
752 * @param[in] value The value to remove
753 * @exception E_SUCCESS The method is successful.
754 * @exception E_INVALID_ARG A specified input parameter is invalid, or
755 * the comparer has failed to compare the keys.
756 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
759 virtual result Remove(const KeyType& key, const ValueType& value)
761 result r = E_OBJ_NOT_FOUND;
762 int hash = Hash(key);
763 int i = hash & (__capacity - 1);
765 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
766 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
768 if (hash == pEntry->hash)
771 r = __pComparer->Compare(key, pEntry->key, cmpResult);
772 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
777 __ValueNodeT< ValueType >* pPrevNode = pEntry->pList;
778 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
780 if (value == pNode->value)
784 if (pPrevNode == pNode)
786 pEntry->pList = pNode->pNext;
790 pPrevNode->pNext = pNode->pNext;
797 if (null == pEntry->pList)
801 __pTable[i] = pEntry->pNext;
805 pPrev->pNext = pEntry->pNext;
827 * Removes all key-value pairs in this map.
831 virtual void RemoveAll(void)
842 * Replaces the value associated with the key with the specified @c newValue.
846 * @return An error code
847 * @param[in] key A key
848 * @param[in] value A value to replace
849 * @param[in] newValue A new value to replace the existing value
850 * @exception E_SUCCESS The method is successful.
851 * @exception E_INVALID_ARG A specified input parameter is invalid, or
852 * the comparer has failed to compare the keys.
853 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
854 * @remarks To add a new key-value pair, use the Add() method.
858 virtual result SetValue(const KeyType& key, const ValueType& value, const ValueType& newValue)
860 result r = E_SUCCESS;
861 int hash = Hash(key);
862 int i = hash & (__capacity - 1);
863 __ValueNodeT< ValueType >* pNode = null;
864 bool pairExist = false;
865 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
866 while (null != pEntry)
868 if (hash == pEntry->hash)
871 r = __pComparer->Compare(key, pEntry->key, cmpResult);
872 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
876 pNode = pEntry->pList;
879 if (pNode->value == value)
882 pNode->value = newValue;
886 if (pNode->pNext != null)
888 pNode = pNode->pNext;
899 pEntry = pEntry->pNext;
911 * Gets the number of values currently stored in this map.
915 * @return The number of values currently stored in this map
917 virtual int GetCount(void) const
923 * Gets the number of values whose keys match the specified key.
927 * @return An error code
928 * @param[in] key A key to locate
929 * @param[out] count The number of values whose key is @c key
930 * @exception E_SUCCESS The method is successful.
931 * @exception E_INVALID_ARG A specified input parameter is invalid, or
932 * the comparer has failed to compare the keys.
933 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
935 virtual result GetCount(const KeyType& key, int& count) const
937 result r = E_OBJ_NOT_FOUND;
938 int hash = Hash(key);
939 int i = hash & (__capacity - 1);
941 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
943 if (hash == pEntry->hash)
946 r = __pComparer->Compare(key, pEntry->key, cmpResult);
947 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
952 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
969 * Checks whether the map contains the specified key and value.
973 * @return An error code
974 * @param[in] key The key to locate
975 * @param[in] value The value to locate
976 * @param[out] out Set to @c true if the map contains the specified key and value pair, @n
978 * @exception E_SUCCESS The method is successful.
979 * @exception E_INVALID_ARG The current state of the instance prohibits the execution of the specified operation, or
980 * the comparer has failed to compare the keys.
982 * @see ContainsValue()
984 virtual result Contains(const KeyType& key, const ValueType& value, bool& out) const
988 result r = E_SUCCESS;
989 int hash = Hash(key);
990 int i = hash & (__capacity - 1);
992 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
994 if (hash == pEntry->hash)
997 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1000 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1002 return E_INVALID_ARG;
1007 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1009 if (value == pNode->value)
1025 * Checks whether the map contains the specified key.
1029 * @return An error code
1030 * @param[in] key The key to locate
1031 * @param[out] out Set to @c true if the map contains the specified key, @n
1033 * @exception E_SUCCESS The method is successful.
1034 * @exception E_INVALID_ARG A specified input parameter is invalid, or
1035 * the comparer has failed to compare the keys.
1036 * @see ContainsValue()
1039 virtual result ContainsKey(const KeyType& key, bool& out) const
1042 result r = E_SUCCESS;
1043 int hash = Hash(key);
1044 int i = hash & (__capacity - 1);
1046 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1048 if (hash == pEntry->hash)
1051 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1054 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1056 return E_INVALID_ARG;
1070 * Checks whether the map contains the specified value.
1074 * @return @c true if the map contains the specified value, @n
1076 * @param[in] value The value to locate
1078 * @see ContainsKey()
1081 virtual bool ContainsValue(const ValueType& value) const
1084 for (int i = 0; i < __capacity; i++)
1086 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1088 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1090 if (value == pNode->value)
1109 * Compares the specified instance to the current instance for equality.
1113 * @return @c true if the two instances are equal, @n
1115 * @param[in] obj The object to compare with the current instance
1116 * @remarks This method returns @c true only if the specified object is also an instance of the %MultiHashMapT class,
1117 * both maps have the same number of elements, and both maps contain the same elements.
1119 virtual bool Equals(const Object& obj) const
1121 result r = E_SUCCESS;
1124 const MultiHashMapT< KeyType, ValueType >* other = dynamic_cast< const MultiHashMapT< KeyType, ValueType >* >(&obj);
1125 if (null == other) // obj is not MultiHashMapT<KeyType, ValueType>
1129 else if (other == this)
1133 else if (__count != other->__count)
1139 for (int i = 0; i < __capacity; i++)
1141 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1143 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1145 r = other->Contains(pEntry->key, pNode->value, out);
1163 * Gets the hash value of the current instance.
1167 * @return The hash value of the current instance
1168 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
1169 * the used hash function must generate a random distribution for all inputs.
1171 virtual int GetHashCode(void) const
1175 for (int i = 0; i < __capacity; i++)
1177 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1179 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1181 hash += reinterpret_cast< int >(&pNode->value);
1183 hash += reinterpret_cast< int >(&pEntry->key);
1190 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
1192 * @param[in] map An instance of %MultiHashMapT to initialize the current instance
1194 MultiHashMapT(const MultiHashMapT< KeyType, ValueType >& map);
1197 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
1199 * @param[in] map An instance of %MultiHashMapT
1201 MultiHashMapT< KeyType, ValueType >& operator =(const MultiHashMapT< KeyType, ValueType >& map);
1204 * Copies all the pairs from the specified map to this map.
1206 * @return An error code
1207 * @param[in] map The map to copy
1208 * @exception E_SUCCESS The method is successful.
1209 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1210 * The @c map is modified during the operation of this method.
1212 result AddAll(const IMultiMapT< KeyType, ValueType >& map)
1214 result r = E_SUCCESS;
1216 IMultiMapT< KeyType, ValueType >* pMap = const_cast< IMultiMapT< KeyType, ValueType >* >(&map);
1217 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
1219 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
1226 r = pMapEnum->MoveNext();
1227 // enumerator is reached to the end of collection
1228 if (E_OUT_OF_RANGE == r)
1233 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1235 r = pMapEnum->GetKey(key);
1236 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1238 r = pMapEnum->GetValue(value);
1239 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1241 r = Add(key, value);
1242 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1245 if (null != pMapEnum)
1252 if (null != pMapEnum)
1260 * Gets a hash value for the specified object.
1262 * @return The hash value for the specified object
1263 * @param[in] obj The object to get hash value
1265 int Hash(const KeyType& obj) const
1267 int h = __pProvider->GetHashCode(obj);
1269 h ^= (h >> 20) ^ (h >> 12);
1271 return h ^ (h >> 7) ^ (h >> 4);
1275 * Resizes the contents of this map into a new array with a
1276 * larger capacity. @n
1277 * This method is called automatically when the
1278 * number of keys in this map reaches its threshold.
1280 * @return An error code
1281 * @param[in] newCapacity The new capacity @n
1282 * It must be a power of 2 and must be greater than current capacity.
1283 * @exception E_SUCCESS The method is successful.
1284 * @exception E_OUT_OF_MEMORY The memory is insufficient.
1286 result Resize(int newCapacity)
1288 result r = E_SUCCESS;
1289 __MultiHashMapEntryT< KeyType, ValueType >** newTable = new __MultiHashMapEntryT< KeyType, ValueType >*[newCapacity];
1290 TryCatch(newTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
1291 for (int i = 0; i < newCapacity; i++)
1296 for (int i = 0; i < __capacity; i++)
1298 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1299 while (null != pEntry)
1301 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1302 int i = pEntry->hash & (newCapacity - 1);
1303 pEntry->pNext = newTable[i];
1304 newTable[i] = pEntry;
1310 __pTable = newTable;
1311 __capacity = newCapacity;
1312 __threshold = static_cast< int >(__capacity * __loadFactor);
1321 * Clears all key-value pairs in this map.
1326 for (int i = 0; i < __capacity; i++)
1328 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1329 while (null != pEntry)
1331 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1332 __ValueNodeT< ValueType >* pNode = pEntry->pList;
1333 while (null != pNode)
1335 __ValueNodeT< ValueType >* pTemp = pNode;
1336 pNode = pNode->pNext;
1346 __MultiHashMapEntryT< KeyType, ValueType >** __pTable;
1351 IHashCodeProviderT< KeyType >* __pProvider;
1352 IComparerT< KeyType >* __pComparer;
1353 bool __defaultConstruct;
1356 static const int DEFAULT_CAPACITY = 16;
1357 static const float DEFAULT_LOAD_FACTOR;
1359 friend class __MultiHashMapEnumeratorT< KeyType, ValueType >;
1364 // @class __ValueNodeT
1365 // @brief This class is a node for MultiHashMapT.
1368 template< class ValueType >
1374 * This is the constructor for this class.
1378 * @param[in] v An object to include in this node
1380 __ValueNodeT(const ValueType& v)
1387 * This is the destructor for this class.
1391 virtual ~__ValueNodeT(void)
1396 * Internal variable.
1400 __ValueNodeT< ValueType >* pNext;
1403 * Internal variable.
1412 // @class __MultiHashMapEntryT
1413 // @brief This class is an entry for MultiHashMapT class.
1416 template< class KeyType, class ValueType >
1417 class __MultiHashMapEntryT
1422 * This is the constructor for this class.
1426 * @param[in] keyType A key to include in this entry
1427 * @param[in] list A list of values whose key is specified @n
1428 * It cannot be @c null.
1429 * @param[in] next A pointer to the next entry
1430 * @param[in] h An hash value of the key
1432 __MultiHashMapEntryT(const KeyType& keyType, __ValueNodeT< ValueType >* list, __MultiHashMapEntryT< KeyType, ValueType >* next, int h)
1442 * This is the destructor for this class.
1446 virtual ~__MultiHashMapEntryT(void)
1451 * Internal variable.
1458 * Internal variable.
1462 __ValueNodeT< ValueType >* pList;
1465 * Internal variable.
1469 __MultiHashMapEntryT< KeyType, ValueType >* pNext;
1472 * Internal variable.
1479 * Internal variable.
1485 friend class __EntryValueEnumeratorT< KeyType, ValueType >;
1487 }; // __MultiHashMapEntryT
1490 // @class __MultiHashMapEnumeratorT
1491 // @brief This class is an implementation of IMapEnumeratorT for %MultiHashMapT.
1494 template< class KeyType, class ValueType >
1495 class __MultiHashMapEnumeratorT
1496 : public IMapEnumeratorT< KeyType, ValueType >
1501 * This is the constructor for this class.
1505 * @param[in] map A map to enumerate
1506 * @param[in] modCount The modification count to detect the change in the map
1508 __MultiHashMapEnumeratorT(const MultiHashMapT< KeyType, ValueType >& map, int modCount)
1510 , __modCount(modCount)
1518 * This is the destructor for this class.
1522 virtual ~__MultiHashMapEnumeratorT(void)
1527 * Gets the current object in the map.
1531 * @return An error code
1532 * @param[out] obj The current object
1533 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1534 * - The current state of the instance prohibits the execution of the specified operation. @n
1535 * - This enumerator is currently positioned before the first element or
1536 * past the last element. @n
1537 * - The map is modified after this enumerator is created.
1538 * @exception E_SUCCESS The method is successful.
1540 result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1542 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1543 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1544 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1545 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1547 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pNode->value);
1552 * Moves this enumerator to the next element of the map. @n
1553 * After the enumerator is first created or reset using the Reset() method,
1554 * the first call to this method positions the enumerator to the first element in the @c collection.
1558 * @return An error code
1559 * @exception E_SUCCESS The method is successful.
1560 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1561 * the map is modified after this enumerator is created.
1562 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the map.
1565 result MoveNext(void)
1567 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1568 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1570 result r = E_SUCCESS;
1571 if ((null != __pNode) && (__pNode->pNext != null))
1573 __pNode = __pNode->pNext;
1575 else if ((null != __pEntry) && (__pEntry->pNext != null))
1577 __pEntry = __pEntry->pNext;
1578 __pNode = __pEntry->pList;
1584 if (++__index >= static_cast< int >(__map.__capacity))
1586 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1590 __pEntry = __map.__pTable[__index];
1591 if (null != __pEntry)
1593 __pNode = __pEntry->pList;
1603 * Positions this enumerator before the first element in the map.
1607 * @return An error code
1608 * @exception E_SUCCESS The method is successful.
1609 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1610 * the map is modified after this enumerator is created.
1614 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1615 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1624 * Gets the current key in the map.
1628 * @return An error code
1629 * @param[out] key The current key
1630 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1631 * - The current state of the instance prohibits the execution of the specified operation. @n
1632 * - This enumerator is currently positioned before the first element or
1633 * past the last element. @n
1634 * - The map is modified after this enumerator is created.
1635 * @exception E_SUCCESS The method is successful.
1637 result GetKey(KeyType& key) const
1639 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1640 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1641 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1642 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1644 key = __pEntry->key;
1649 * Gets the current value in the map.
1653 * @return An error code
1654 * @param[out] value The current value
1655 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1656 * - The current state of the instance prohibits the execution of the specified operation. @n
1657 * - This enumerator is currently positioned before the first element or
1658 * past the last element. @n
1659 * - The map is modified after the enumerator is created.
1660 * @exception E_SUCCESS The method is successful.
1662 result GetValue(ValueType& value) const
1664 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1665 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1666 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1667 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1669 value = __pNode->value;
1674 const MultiHashMapT< KeyType, ValueType >& __map;
1676 __MultiHashMapEntryT< KeyType, ValueType >* __pEntry;
1677 __ValueNodeT< ValueType >* __pNode;
1680 }; // __MultiHashMapEnumeratorT
1683 // @class __EntryValueEnumeratorT
1684 // @brief This class is an implementation of IEnumeratorT to enumerate values whose key is the same.
1687 template< class KeyType, class ValueType >
1688 class __EntryValueEnumeratorT
1689 : public IEnumeratorT< ValueType >
1694 * Initializes an instance of __EntryValueEnumeratorT with the specified parameters.
1698 * @param[in] entry An entry to enumerate
1699 * @param[in] modCount The modification count to detect the change in the entry
1701 __EntryValueEnumeratorT(const __MultiHashMapEntryT< KeyType, ValueType >& entry, int modCount)
1703 , __modCount(modCount)
1710 * This is the destructor for this class.
1714 virtual ~__EntryValueEnumeratorT(void)
1719 * Gets the current value in the entry.
1723 * @return An error code
1724 * @param[out] obj The current value
1725 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1726 * - The current state of the instance prohibits the execution of the specified operation. @n
1727 * - This enumerator is currently positioned before the first element or
1728 * past the last element. @n
1729 * - The entry is modified after this enumerator is created.
1730 * @exception E_SUCCESS The method is successful.
1732 result GetCurrent(ValueType& obj) const
1734 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1735 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1736 TryReturn(__pNode != null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1738 obj = __pNode->value;
1743 * Moves this enumerator to the next element of the entry. @n
1744 * After the enumerator is first created or reset using the Reset() method,
1745 * the first call to this method positions the enumerator to the first element in the collection.
1749 * @return An error code
1750 * @exception E_SUCCESS The method is successful.
1751 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1752 * the entry is modified after this enumerator is created.
1753 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the entry.
1756 result MoveNext(void)
1758 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1759 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1761 result r = E_SUCCESS;
1762 if (null == __pNode)
1764 __pNode = __entry.pList;
1765 AppAssert(null != __pNode);
1767 else if ((null != __pNode) && (__pNode->pNext != null))
1769 __pNode = __pNode->pNext;
1773 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1781 * Positions this enumerator before the first element in the entry.
1785 * @return An error code
1786 * @exception E_SUCCESS The method is successful.
1787 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1788 * the entry is modified after this enumerator is created.
1792 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1793 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1800 const __MultiHashMapEntryT< KeyType, ValueType >& __entry;
1802 __ValueNodeT< ValueType >* __pNode;
1804 }; // __EntryValueEnumeratorT
1807 // @class __MultiHashMapDefaultProviderT
1808 // @brief This class is an implementation of IHashCodeProviderT for HashMap.
1811 template< class KeyType >
1812 class __MultiHashMapDefaultProviderT
1813 : public IHashCodeProviderT< KeyType >
1818 * This is the default constructor for this class.
1822 __MultiHashMapDefaultProviderT(void) {}
1825 * This is the destructor for this class.
1829 virtual ~__MultiHashMapDefaultProviderT(void) {}
1834 * Gets the hash code of the specified instance.
1838 * @return The hash code
1839 * @see Tizen::Base::Object::GetHashCode()
1841 virtual int GetHashCode(const KeyType& obj) const
1846 }; // __MultiHashMapDefaultProviderT
1848 template< class KeyType, class ValueType >
1849 const float MultiHashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1851 }}} // Tizen::Base::Collection
1853 #endif //_FBASE_COL_MULTI_HASH_MAP_T_H_