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 a key.
52 * The %MultiHashMapT class represents a template-based collection of associated keys and values that are organized based on the hash code of a key.
53 * There is no limit on the number of elements having the same key, but duplicate elements with the same key are not allowed.
54 * The key and value cannot be @c null. Several methods in the %MultiHashMapT class need an assignment(=) operator of KeyType, as well as 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 Either of the following conditions has occurred:
167 * - A specified input parameter is invalid.
168 * - The specified @c capacity or the specified @c loadFactor is negative.
169 * @remarks The key type must be a primitive data type.
170 * @see MultiHashMapT()
172 result Construct(int capacity = 16, float loadFactor = 0.75)
174 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
175 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
177 result r = E_SUCCESS;
182 __capacity = DEFAULT_CAPACITY;
187 while (__capacity < capacity)
194 if (Float::Compare(loadFactor, 0) == 0)
196 __loadFactor = DEFAULT_LOAD_FACTOR;
200 __loadFactor = loadFactor;
204 __threshold = static_cast< int >(__capacity * __loadFactor);
206 // set hash code provider
207 __pProvider = new __MultiHashMapDefaultProviderT< KeyType >();
208 TryCatch(__pProvider != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
211 __pComparer = new Tizen::Base::ComparerT< KeyType >();
212 TryCatch(__pComparer != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
214 __defaultConstruct = true;
216 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
217 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
219 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
232 * Initializes this instance of %MultiHashMapT by copying the elements of the specified map.
236 * @return An error code
237 * @param[in] map The map to copy
238 * @param[in] loadFactor The maximum ratio of elements to buckets @n
239 * If it is @c 0, the default load factor(0.75) is used.
240 * @exception E_SUCCESS The method is successful.
241 * @exception E_INVALID_ARG Either of the following conditions has occurred:
242 * - A specified input parameter is invalid
243 * - The specified @c loadFactor is negative.
244 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
245 * - The current state of the instance prohibits the execution of the specified operation.
246 * - The specified @c map is modified during the operation of this method.
247 * @see MultiHashMapT()
249 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
251 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
253 result r = E_SUCCESS;
255 if (Float::Compare(loadFactor, 0) == 0)
257 loadFactor = DEFAULT_LOAD_FACTOR;
260 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
261 r = Construct(capacity, loadFactor);
262 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
265 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
286 * Initializes this instance of %MultiHashMapT that is empty,
287 * with the specified initial capacity, load factor, hash code provider, and comparer.
291 * @return An error code
292 * @param[in] capacity The initial capacity @n
293 * If it is @c 0, the default capacity(16) is used.
294 * @param[in] loadFactor The maximum ratio of elements to buckets @n
295 * If it is @c 0, the default load factor(0.75) is used.
296 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
297 * for all the keys in this map
298 * @param[in] comparer An instance of the IComparer derived class to use when comparing the keys
299 * @exception E_SUCCESS The method is successful.
300 * @exception E_INVALID_ARG Either of the following conditions has occurred:
301 * - A specified input parameter is invalid.
302 * - The specified @c capacity or the specified @c loadFactor is negative.
303 * @remarks The instances of hash code provider and the comparer are not deallocated later from this map.
304 * @see MultiHashMapT()
306 result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
307 const IComparerT< KeyType >& comparer)
309 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
310 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
312 result r = E_SUCCESS;
316 __capacity = DEFAULT_CAPACITY;
321 while (__capacity < capacity)
328 if (Float::Compare(loadFactor, 0) == 0)
330 __loadFactor = DEFAULT_LOAD_FACTOR;
334 __loadFactor = loadFactor;
338 __threshold = static_cast< int >(__capacity * __loadFactor);
340 // set hash code provider
341 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
344 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
346 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
347 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
349 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
362 * Initializes this instance of %MultiHashMapT by copying the elements of the specified map,
363 * with the specified load factor, hash code provider, and comparer.
367 * @return An error code
368 * @param[in] map The map to copy
369 * @param[in] loadFactor The maximum ratio of elements to buckets @n
370 * If it is @c 0, the default load factor(0.75) is used.
371 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
372 * for all the keys in this map
373 * @param[in] comparer An instance of the IComparer derived class to use when comparing the keys
374 * @exception E_SUCCESS The method is successful.
375 * @exception E_INVALID_ARG Either of the following conditions has occurred:
376 * - A specified input parameter is invalid.
377 * - The specified @c loadFactor is negative.
378 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
379 * - The current state of the instance prohibits the execution of the specified operation.
380 * - The specified @c map is modified during the operation of this method.
381 * @remarks The instances of the hash code provider and the comparer are not deallocated later from this map.
382 * @see MultiHashMapT()
384 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
385 const IComparerT< KeyType >& comparer)
387 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
389 result r = E_SUCCESS;
391 if (Float::Compare(loadFactor, 0) == 0)
393 loadFactor = DEFAULT_LOAD_FACTOR;
396 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
398 r = Construct(capacity, loadFactor, provider, comparer);
399 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
402 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
419 * Adds the specified key-value pair to this map.
423 * @return An error code
424 * @param[in] key The key of the value to add
425 * @param[in] value The value to add
426 * @exception E_SUCCESS The method is successful.
427 * @exception E_OBJ_ALREADY_EXIST The specified @c key and @c value pair already exists.
428 * @exception E_INVALID_ARG Either of the following conditions has occurred:
429 * - A specified input parameter is invalid.
430 * - The comparer has failed to compare the keys.
431 * @remarks SetItem() can be used to set a value to a key that does not already exist. @n
432 * However, setting a value to a key that already exists overwrites this value.
436 virtual result Add(const KeyType& key, const ValueType& value)
438 result r = E_SUCCESS;
439 int hash = Hash(key);
440 int i = hash & (__capacity - 1);
441 __ValueNodeT< ValueType >* pNode = null;
442 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
443 while (null != pEntry)
445 if (hash == pEntry->hash)
448 r = __pComparer->Compare(key, pEntry->key, cmpResult);
449 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
453 pNode = pEntry->pList;
456 if (pNode->value == value)
458 return E_OBJ_ALREADY_EXIST;
461 if (pNode->pNext != null)
463 pNode = pNode->pNext;
474 pEntry = pEntry->pNext;
477 __ValueNodeT< ValueType >* pNewNode = new __ValueNodeT< ValueType >(value);
478 TryReturn(pNewNode != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
480 // key is not exist in this map.
483 __MultiHashMapEntryT< KeyType, ValueType >* pNewEntry = new __MultiHashMapEntryT< KeyType, ValueType >(key, pNewNode, __pTable[i],
485 TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
486 __pTable[i] = pNewEntry;
488 // key is already exist in this map, but value is not.
491 // pNode is the last value associated to the key
492 pNode->pNext = pNewNode;
497 if (__count++ >= __threshold)
499 r = Resize(__capacity * 2);
500 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
507 * Gets the enumerator of this map.
511 * @return The enumerator (an instance of the IMapEnumeratorT derived class) of this map, @n
512 * else @c null if an exception occurs
513 * @exception E_SUCCESS The method is successful.
514 * @exception E_OUT_OF_MEMORY The memory is insufficient.
516 * - If the key has multiple values, the enumeration proceeds as follows: @n
517 * {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
518 * - The specific error code can be accessed using the GetLastResult() method.
519 * @see Tizen::Base::Collection::IEnumerator
520 * @see Tizen::Base::Collection::IMapEnumerator
522 virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
524 result r = E_SUCCESS;
526 __MultiHashMapEnumeratorT< KeyType, ValueType >* pEnum = new __MultiHashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
527 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
529 SetLastResult(E_SUCCESS);
538 * Gets the IMapEnumerator of this map.
542 * @return The enumerator (an instance of the IMapEnumeratorT derived class) of this map, @n
543 * else @c null if an exception occurs
544 * @exception E_SUCCESS The method is successful.
545 * @exception E_OUT_OF_MEMORY The memory is insufficient.
547 * - If the key has multiple values, the enumeration proceeds like this: @n
548 * {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
549 * - The specific error code can be accessed using the GetLastResult() method.
550 * @see Tizen::Base::Collection::IEnumerator
551 * @see Tizen::Base::Collection::IMapEnumerator
553 virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
555 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
559 * Gets the enumerator of the values associated with the specified key.
563 * @return The enumerator (an instance of the IEnumeratorT derived class) of the values associated with the specified key, @n
564 * else @c null if an exception occurs
565 * @param[in] key The key to locate
566 * @exception E_SUCCESS The method is successful.
567 * @exception E_INVALID_ARG Either of the following conditions has occurred:
568 * - A specified input parameter is invalid.
569 * - The comparer has failed to compare the keys.
570 * @exception E_OBJ_NOT_FOUND The specified @c key has not been found in the map.
571 * @remarks The specific error code can be accessed using the GetLastResult() method.
574 virtual IEnumeratorT< ValueType >* GetValuesN(const KeyType& key) const
576 result r = E_OBJ_NOT_FOUND;
578 int hash = Hash(key);
579 int i = hash & (__capacity - 1);
580 IEnumeratorT< ValueType >* pEnum = null;
582 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
584 if (hash == pEntry->hash)
587 r = __pComparer->Compare(key, pEntry->key, cmpResult);
588 TryCatch(r == E_SUCCESS, r = E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
592 pEnum = new __EntryValueEnumeratorT< KeyType, ValueType >(*pEntry, pEntry->modCount);
593 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
611 * Gets a list of all the unique keys in this map.
615 * @return The list of all the unique keys in this map, @n
616 * else @c null if an exception occurs
617 * @exception E_SUCCESS The method is successful.
618 * @exception E_OUT_OF_MEMORY The memory is insufficient.
619 * @remarks The specific error code can be accessed using the GetLastResult() method.
622 virtual IListT< KeyType >* GetKeysN(void) const
626 result r = E_SUCCESS;
629 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
630 r = pList->Construct(__count);
631 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
633 for (int i = 0; i < __capacity; i++)
635 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
637 r = pList->Add(pEntry->key);
638 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
653 * Gets a list of all the values in this map.
657 * @return The list of all the values in this map, @n
658 * else @c null if an exception occurs
659 * @exception E_SUCCESS The method is successful.
660 * @exception E_OUT_OF_MEMORY The memory is insufficient.
661 * @remarks The specific error code can be accessed using the GetLastResult() method.
664 virtual IListT< ValueType >* GetValuesN(void) const
668 result r = E_SUCCESS;
670 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
671 r = pList->Construct(__count);
672 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
674 for (int i = 0; i < __capacity; i++)
676 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
678 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
680 r = pList->Add(pNode->value);
681 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
696 * Removes all the values for the specified key.
700 * @return An error code
701 * @param[in] key The key to remove
702 * @exception E_SUCCESS The method is successful.
703 * @exception E_INVALID_ARG Either of the following conditions has occurred:
704 * - The specified input parameter is invalid.
705 * - The comparer has failed to compare the keys.
706 * @exception E_OBJ_NOT_FOUND The specified @c key has not been found in the map.
709 virtual result Remove(const KeyType& key)
711 result r = E_OBJ_NOT_FOUND;
712 int hash = Hash(key);
713 int i = hash & (__capacity - 1);
715 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
716 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
718 if (hash == pEntry->hash)
721 r = __pComparer->Compare(key, pEntry->key, cmpResult);
722 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
731 __pTable[i] = pEntry->pNext;
735 pPrev->pNext = pEntry->pNext;
738 __ValueNodeT< ValueType >* pNode = pEntry->pList;
739 while (null != pNode)
741 __ValueNodeT< ValueType >* pTemp = pNode;
742 pNode = pNode->pNext;
758 * Removes the specified value associated with the specified key. @n
759 * The key is also removed if there is no value associated with it.
763 * @return An error code
764 * @param[in] key The key whose mapping is removed from the map
765 * @param[in] value The value to remove
766 * @exception E_SUCCESS The method is successful.
767 * @exception E_INVALID_ARG Either of the following conditions has occurred:
768 * - A specified input parameter is invalid.
769 * - The comparer has failed to compare the keys.
770 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
773 virtual result Remove(const KeyType& key, const ValueType& value)
775 result r = E_OBJ_NOT_FOUND;
776 int hash = Hash(key);
777 int i = hash & (__capacity - 1);
779 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
780 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
782 if (hash == pEntry->hash)
785 r = __pComparer->Compare(key, pEntry->key, cmpResult);
786 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
791 __ValueNodeT< ValueType >* pPrevNode = pEntry->pList;
792 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
794 if (value == pNode->value)
798 if (pPrevNode == pNode)
800 pEntry->pList = pNode->pNext;
804 pPrevNode->pNext = pNode->pNext;
811 if (null == pEntry->pList)
815 __pTable[i] = pEntry->pNext;
819 pPrev->pNext = pEntry->pNext;
841 * Removes all the key-value pairs in this map.
845 virtual void RemoveAll(void)
856 * Replaces the value associated with the key, with the specified @c newValue.
860 * @return An error code
861 * @param[in] key The key
862 * @param[in] value The value to replace
863 * @param[in] newValue The new value to replace the existing value
864 * @exception E_SUCCESS The method is successful.
865 * @exception E_INVALID_ARG Either of the following conditions has occurred:
866 * - The specified input parameter is invalid.
867 * - The comparer has failed to compare the keys.
868 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
869 * @remarks To add a new key-value pair, use the Add() method.
872 virtual result SetValue(const KeyType& key, const ValueType& value, const ValueType& newValue)
874 result r = E_SUCCESS;
875 int hash = Hash(key);
876 int i = hash & (__capacity - 1);
877 __ValueNodeT< ValueType >* pNode = null;
878 bool pairExist = false;
879 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
880 while (null != pEntry)
882 if (hash == pEntry->hash)
885 r = __pComparer->Compare(key, pEntry->key, cmpResult);
886 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
890 pNode = pEntry->pList;
893 if (pNode->value == value)
896 pNode->value = newValue;
900 if (pNode->pNext != null)
902 pNode = pNode->pNext;
913 pEntry = pEntry->pNext;
925 * Gets the number of values currently stored in this map.
929 * @return The number of values currently stored in this map
931 virtual int GetCount(void) const
937 * Gets the number of values whose keys match the specified key.
941 * @return An error code
942 * @param[in] key The key to locate
943 * @param[out] count The number of values whose key is @c key
944 * @exception E_SUCCESS The method is successful.
945 * @exception E_INVALID_ARG Either of the following conditions has occurred:
946 * - A specified input parameter is invalid.
947 * - The comparer has failed to compare the keys.
948 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
950 virtual result GetCount(const KeyType& key, int& count) const
952 result r = E_OBJ_NOT_FOUND;
953 int hash = Hash(key);
954 int i = hash & (__capacity - 1);
956 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
958 if (hash == pEntry->hash)
961 r = __pComparer->Compare(key, pEntry->key, cmpResult);
962 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
967 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
984 * Checks whether the map contains the specified key and value.
988 * @return An error code
989 * @param[in] key The key to locate
990 * @param[in] value The value to locate
991 * @param[out] out Set to @c true if the map contains the specified key and value pair, @n
993 * @exception E_SUCCESS The method is successful.
994 * @exception E_INVALID_ARG Either of the following conditions has occurred:
995 * - The current state of the instance prohibits the execution of the specified operation.
996 * - The comparer has failed to compare the keys.
998 * @see ContainsValue()
1000 virtual result Contains(const KeyType& key, const ValueType& value, bool& out) const
1004 result r = E_SUCCESS;
1005 int hash = Hash(key);
1006 int i = hash & (__capacity - 1);
1008 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1010 if (hash == pEntry->hash)
1013 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1016 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1018 return E_INVALID_ARG;
1023 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1025 if (value == pNode->value)
1041 * Checks whether the map contains the specified key.
1045 * @return An error code
1046 * @param[in] key The key to locate
1047 * @param[out] out Set to @c true if the map contains the specified key, @n
1049 * @exception E_SUCCESS The method is successful.
1050 * @exception E_INVALID_ARG Either of the following conditions has occurred:
1051 * - A specified input parameter is invalid.
1052 * - The comparer has failed to compare the keys.
1053 * @see ContainsValue()
1056 virtual result ContainsKey(const KeyType& key, bool& out) const
1059 result r = E_SUCCESS;
1060 int hash = Hash(key);
1061 int i = hash & (__capacity - 1);
1063 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1065 if (hash == pEntry->hash)
1068 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1071 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1073 return E_INVALID_ARG;
1087 * Checks whether the map contains the specified value.
1091 * @return @c true if the map contains the specified value, @n
1093 * @param[in] value The value to locate
1095 * @see ContainsKey()
1098 virtual bool ContainsValue(const ValueType& value) const
1101 for (int i = 0; i < __capacity; i++)
1103 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1105 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1107 if (value == pNode->value)
1126 * Compares the specified instance to the current instance for equality.
1130 * @return @c true if the two instances are equal, @n
1132 * @param[in] obj The object to compare with the current instance
1133 * @remarks This method returns @c true only if the specified object is also an instance of the %MultiHashMapT class,
1134 * both the maps have the same number of elements, and both the maps contain the same elements.
1136 virtual bool Equals(const Object& obj) const
1138 result r = E_SUCCESS;
1141 const MultiHashMapT< KeyType, ValueType >* other = dynamic_cast< const MultiHashMapT< KeyType, ValueType >* >(&obj);
1142 if (null == other) // obj is not MultiHashMapT<KeyType, ValueType>
1146 else if (other == this)
1150 else if (__count != other->__count)
1156 for (int i = 0; i < __capacity; i++)
1158 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1160 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1162 r = other->Contains(pEntry->key, pNode->value, out);
1180 * Gets the hash value of the current instance.
1184 * @return The hash value of the current instance
1185 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. @n
1186 * For better performance, the used hash function must generate a random distribution for all the inputs.
1188 virtual int GetHashCode(void) const
1192 for (int i = 0; i < __capacity; i++)
1194 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1196 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1198 hash += reinterpret_cast< int >(&pNode->value);
1200 hash += reinterpret_cast< int >(&pEntry->key);
1207 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
1209 * @param[in] map An instance of %MultiHashMapT to initialize the current instance
1211 MultiHashMapT(const MultiHashMapT< KeyType, ValueType >& map);
1214 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
1216 * @param[in] map An instance of %MultiHashMapT
1218 MultiHashMapT< KeyType, ValueType >& operator =(const MultiHashMapT< KeyType, ValueType >& map);
1221 * Copies all the pairs from the specified map to this map.
1223 * @return An error code
1224 * @param[in] map The map to copy
1225 * @exception E_SUCCESS The method is successful.
1226 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1227 * The @c map is modified during the operation of this method.
1229 result AddAll(const IMultiMapT< KeyType, ValueType >& map)
1231 result r = E_SUCCESS;
1233 IMultiMapT< KeyType, ValueType >* pMap = const_cast< IMultiMapT< KeyType, ValueType >* >(&map);
1234 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
1236 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
1243 r = pMapEnum->MoveNext();
1244 // enumerator is reached to the end of collection
1245 if (E_OUT_OF_RANGE == r)
1250 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1252 r = pMapEnum->GetKey(key);
1253 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1255 r = pMapEnum->GetValue(value);
1256 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1258 r = Add(key, value);
1259 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1262 if (null != pMapEnum)
1269 if (null != pMapEnum)
1277 * Gets a hash value for the specified object.
1279 * @return The hash value for the specified object
1280 * @param[in] obj The object to get hash value
1282 int Hash(const KeyType& obj) const
1284 int h = __pProvider->GetHashCode(obj);
1286 h ^= (h >> 20) ^ (h >> 12);
1288 return h ^ (h >> 7) ^ (h >> 4);
1292 * Resizes the contents of this map into a new array with a
1293 * larger capacity. @n
1294 * This method is called automatically when the
1295 * number of keys in this map reaches its threshold.
1297 * @return An error code
1298 * @param[in] newCapacity The new capacity @n
1299 * It must be a power of 2 and must be greater than current capacity.
1300 * @exception E_SUCCESS The method is successful.
1301 * @exception E_OUT_OF_MEMORY The memory is insufficient.
1303 result Resize(int newCapacity)
1305 result r = E_SUCCESS;
1306 __MultiHashMapEntryT< KeyType, ValueType >** newTable = new __MultiHashMapEntryT< KeyType, ValueType >*[newCapacity];
1307 TryCatch(newTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
1308 for (int i = 0; i < newCapacity; i++)
1313 for (int i = 0; i < __capacity; i++)
1315 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1316 while (null != pEntry)
1318 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1319 int i = pEntry->hash & (newCapacity - 1);
1320 pEntry->pNext = newTable[i];
1321 newTable[i] = pEntry;
1327 __pTable = newTable;
1328 __capacity = newCapacity;
1329 __threshold = static_cast< int >(__capacity * __loadFactor);
1338 * Clears all key-value pairs in this map.
1343 for (int i = 0; i < __capacity; i++)
1345 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1346 while (null != pEntry)
1348 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1349 __ValueNodeT< ValueType >* pNode = pEntry->pList;
1350 while (null != pNode)
1352 __ValueNodeT< ValueType >* pTemp = pNode;
1353 pNode = pNode->pNext;
1363 __MultiHashMapEntryT< KeyType, ValueType >** __pTable;
1368 IHashCodeProviderT< KeyType >* __pProvider;
1369 IComparerT< KeyType >* __pComparer;
1370 bool __defaultConstruct;
1373 static const int DEFAULT_CAPACITY = 16;
1374 static const float DEFAULT_LOAD_FACTOR;
1376 friend class __MultiHashMapEnumeratorT< KeyType, ValueType >;
1381 // @class __ValueNodeT
1382 // @brief This class is a node for MultiHashMapT.
1385 template< class ValueType >
1391 * This is the constructor for this class.
1395 * @param[in] v The object to include in this node
1397 __ValueNodeT(const ValueType& v)
1404 * This is the destructor for this class.
1408 virtual ~__ValueNodeT(void)
1413 * Internal variable.
1417 __ValueNodeT< ValueType >* pNext;
1420 * Internal variable.
1429 // @class __MultiHashMapEntryT
1430 // @brief This class is an entry for MultiHashMapT class.
1433 template< class KeyType, class ValueType >
1434 class __MultiHashMapEntryT
1439 * This is the constructor for this class.
1443 * @param[in] keyType The key to include in this entry
1444 * @param[in] list The list of values whose key is specified @n
1445 * It cannot be @c null.
1446 * @param[in] next A pointer to the next entry
1447 * @param[in] h The hash value of the key
1449 __MultiHashMapEntryT(const KeyType& keyType, __ValueNodeT< ValueType >* list, __MultiHashMapEntryT< KeyType, ValueType >* next, int h)
1459 * This is the destructor for this class.
1463 virtual ~__MultiHashMapEntryT(void)
1468 * Internal variable.
1475 * Internal variable.
1479 __ValueNodeT< ValueType >* pList;
1482 * Internal variable.
1486 __MultiHashMapEntryT< KeyType, ValueType >* pNext;
1489 * Internal variable.
1496 * Internal variable.
1502 friend class __EntryValueEnumeratorT< KeyType, ValueType >;
1504 }; // __MultiHashMapEntryT
1507 // @class __MultiHashMapEnumeratorT
1508 // @brief This class is an implementation of IMapEnumeratorT for %MultiHashMapT.
1511 template< class KeyType, class ValueType >
1512 class __MultiHashMapEnumeratorT
1513 : public IMapEnumeratorT< KeyType, ValueType >
1518 * This is the constructor for this class.
1522 * @param[in] map The map to enumerate
1523 * @param[in] modCount The modification count to detect the change in the map
1525 __MultiHashMapEnumeratorT(const MultiHashMapT< KeyType, ValueType >& map, int modCount)
1527 , __modCount(modCount)
1535 * This is the destructor for this class.
1539 virtual ~__MultiHashMapEnumeratorT(void)
1544 * Gets the current object in the map.
1548 * @return An error code
1549 * @param[out] obj The current object
1550 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1551 * - The current state of the instance prohibits the execution of the specified operation. @n
1552 * - This enumerator is currently positioned before the first element or
1553 * past the last element.
1554 * - The map is modified after this enumerator is created.
1555 * @exception E_SUCCESS The method is successful.
1557 result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1559 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1560 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1561 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1562 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1564 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pNode->value);
1569 * Moves this enumerator to the next element of the map. @n
1570 * After the enumerator is first created or reset using the Reset() method,
1571 * the first call to this method positions the enumerator to the first element in the collection.
1575 * @return An error code
1576 * @exception E_SUCCESS The method is successful.
1577 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1578 * - The current state of the instance prohibits the execution of the specified operation.
1579 * - The map is modified after this enumerator is created.
1580 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the map.
1583 result MoveNext(void)
1585 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1586 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1588 result r = E_SUCCESS;
1589 if ((null != __pNode) && (__pNode->pNext != null))
1591 __pNode = __pNode->pNext;
1593 else if ((null != __pEntry) && (__pEntry->pNext != null))
1595 __pEntry = __pEntry->pNext;
1596 __pNode = __pEntry->pList;
1602 if (++__index >= static_cast< int >(__map.__capacity))
1604 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1608 __pEntry = __map.__pTable[__index];
1609 if (null != __pEntry)
1611 __pNode = __pEntry->pList;
1621 * Positions this enumerator before the first element in the map.
1625 * @return An error code
1626 * @exception E_SUCCESS The method is successful.
1627 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1628 * - The current state of the instance prohibits the execution of the specified operation.
1629 * - The map is modified after this enumerator is created.
1633 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1634 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1643 * Gets the current key in the map.
1647 * @return An error code
1648 * @param[out] key The current key
1649 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1650 * - The current state of the instance prohibits the execution of the specified operation. @n
1651 * - This enumerator is currently positioned before the first element or
1652 * past the last element. @n
1653 * - The map is modified after this enumerator is created.
1654 * @exception E_SUCCESS The method is successful.
1656 result GetKey(KeyType& key) const
1658 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1659 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1660 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1661 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1663 key = __pEntry->key;
1668 * Gets the current value in the map.
1672 * @return An error code
1673 * @param[out] value The current value
1674 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1675 * - The current state of the instance prohibits the execution of the specified operation. @n
1676 * - This enumerator is currently positioned before the first element or
1677 * past the last element. @n
1678 * - The map is modified after the enumerator is created.
1679 * @exception E_SUCCESS The method is successful.
1681 result GetValue(ValueType& value) const
1683 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1684 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1685 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1686 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1688 value = __pNode->value;
1693 const MultiHashMapT< KeyType, ValueType >& __map;
1695 __MultiHashMapEntryT< KeyType, ValueType >* __pEntry;
1696 __ValueNodeT< ValueType >* __pNode;
1699 }; // __MultiHashMapEnumeratorT
1702 // @class __EntryValueEnumeratorT
1703 // @brief This class is an implementation of IEnumeratorT to enumerate values whose key is the same.
1706 template< class KeyType, class ValueType >
1707 class __EntryValueEnumeratorT
1708 : public IEnumeratorT< ValueType >
1713 * Initializes an instance of __EntryValueEnumeratorT with the specified parameters.
1717 * @param[in] entry The entry to enumerate
1718 * @param[in] modCount The modification count to detect the change in the entry
1720 __EntryValueEnumeratorT(const __MultiHashMapEntryT< KeyType, ValueType >& entry, int modCount)
1722 , __modCount(modCount)
1729 * This is the destructor for this class.
1733 virtual ~__EntryValueEnumeratorT(void)
1738 * Gets the current value in the entry.
1742 * @return An error code
1743 * @param[out] obj The current value
1744 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1745 * - The current state of the instance prohibits the execution of the specified operation. @n
1746 * - This enumerator is currently positioned before the first element or
1747 * past the last element.
1748 * - The entry is modified after this enumerator is created.
1749 * @exception E_SUCCESS The method is successful.
1751 result GetCurrent(ValueType& obj) const
1753 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1754 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1755 TryReturn(__pNode != null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1757 obj = __pNode->value;
1762 * Moves this enumerator to the next element of the entry. @n
1763 * After the enumerator is first created or reset using the Reset() method,
1764 * the first call to this method positions the enumerator to the first element in the collection.
1768 * @return An error code
1769 * @exception E_SUCCESS The method is successful.
1770 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1771 * - The current state of the instance prohibits the execution of the specified operation.
1772 * - The entry is modified after this enumerator is created.
1773 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the entry.
1776 result MoveNext(void)
1778 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1779 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1781 result r = E_SUCCESS;
1782 if (null == __pNode)
1784 __pNode = __entry.pList;
1785 AppAssert(null != __pNode);
1787 else if ((null != __pNode) && (__pNode->pNext != null))
1789 __pNode = __pNode->pNext;
1793 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1801 * Positions this enumerator before the first element in the entry.
1805 * @return An error code
1806 * @exception E_SUCCESS The method is successful.
1807 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
1808 * - The current state of the instance prohibits the execution of the specified operation.
1809 * - The entry is modified after this enumerator is created.
1813 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1814 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1821 const __MultiHashMapEntryT< KeyType, ValueType >& __entry;
1823 __ValueNodeT< ValueType >* __pNode;
1825 }; // __EntryValueEnumeratorT
1828 // @class __MultiHashMapDefaultProviderT
1829 // @brief This class is an implementation of IHashCodeProviderT for HashMap.
1832 template< class KeyType >
1833 class __MultiHashMapDefaultProviderT
1834 : public IHashCodeProviderT< KeyType >
1839 * This is the default constructor for this class.
1843 __MultiHashMapDefaultProviderT(void) {}
1846 * This is the destructor for this class.
1850 virtual ~__MultiHashMapDefaultProviderT(void) {}
1855 * Gets the hash code of the specified instance.
1859 * @return The hash code
1860 * @see Tizen::Base::Object::GetHashCode()
1862 virtual int GetHashCode(const KeyType& obj) const
1867 }; // __MultiHashMapDefaultProviderT
1869 template< class KeyType, class ValueType >
1870 const float MultiHashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1872 }}} // Tizen::Base::Collection
1874 #endif //_FBASE_COL_MULTI_HASH_MAP_T_H_