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>
37 namespace Tizen { namespace Base { namespace Collection
40 template< class KeyType, class ValueType > class __MultiHashMapEntryT;
41 template< class KeyType, class ValueType > class __MultiHashMapEnumeratorT;
42 template< class KeyType, class ValueType > class __EntryValueEnumeratorT;
43 template< class KeyType > class __MultiHashMapDefaultProviderT;
45 template< class ValueType > class __ValueNodeT;
48 * @class MultiHashMapT
49 * @brief This class represents a template-based collection of associated keys and values that are organized based on the hash code of the key.
53 * The %MultiHashMapT class represents a template-based collection of associated keys and values that are organized based on the hash code of the key.
54 * There is no limit on the number of elements with the same key, but duplicated elements with the same key are not allowed.
55 * 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.
57 * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/hashmap_multihashmap.htm">HashMap and MultiHashMap</a>.
59 * The following example demonstrates how to use the %MultiHashMapT class.
66 * using namespace Tizen::Base;
67 * using namespace Tizen::Base::Collection;
70 * MyClass::MultiHashMapTSample(void)
72 * MultiHashMapT< int, int > map;
74 * // Constructs a MultiHashMap instance with default capacity, load factor, hash code provider, and comparer
80 * map.Add(1, 1000); // map.GetCount() : 1, map : (1 -> 1000)
81 * map.Add(2, 2000); // map.GetCount() : 2, map : (1 -> 1000), (2 -> 2000)
82 * map.Add(3, 3000); // map.GetCount() : 3, map : (1 -> 1000), (2 -> 2000), (3 -> 3000)
83 * map.Add(3, 30); // map.GetCount() : 4, map : (1 -> 1000), (2 -> 2000), (3 -> 3000, 30)
85 * // Gets values with the specified key
87 * IEnumeratorT< int >* pValueEnum = map.GetValuesN(key);
88 * while (pValueEnum->MoveNext() == E_SUCCESS)
90 * pValueEnum->GetCurrent(value);
95 * // Removes the values with the specified key
97 * map.Remove(key); // 30, 3000 removed
99 * // Uses an enumerator to access elements in the map
100 * IMapEnumeratorT< int, int >* pMapEnum = map.GetMapEnumeratorN();
101 * while (pMapEnum->MoveNext() == E_SUCCESS)
103 * pMapEnum->GetKey(key);
104 * pMapEnum->GetValue(value);
112 template< class KeyType, class ValueType >
114 : public IMultiMapT< KeyType, ValueType >
119 * The object is not fully constructed after this constructor is called. For full construction, @n
120 * the Construct() method must be called right after calling this constructor.
132 , __defaultConstruct(false)
138 * This destructor overrides Tizen::Base::Object::~Object().
142 virtual ~MultiHashMapT(void)
144 if (null != __pTable)
150 if (__defaultConstruct)
159 * Initializes this instance of %MultiHashMapT with the given capacity and load factor.
163 * @return An error code
164 * @param[in] capacity The initial capacity
165 * @param[in] loadFactor The maximum ratio of elements to buckets
166 * @exception E_SUCCESS The method is successful.
167 * @exception E_INVALID_ARG A specified input parameter is invalid, or
168 * the specified @c capacity or the @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 A 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 A specified input parameter is invalid, or
242 * the specified @c loadFactor is negative.
243 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
244 * the @c map is modified during the operation of this method.
245 * @see MultiHashMapT()
247 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor = 0.75)
249 TryReturn((loadFactor >= 0), E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
251 result r = E_SUCCESS;
253 if (Float::Compare(loadFactor, 0) == 0)
255 loadFactor = DEFAULT_LOAD_FACTOR;
258 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
259 r = Construct(capacity, loadFactor);
260 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
263 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
284 * Initializes this instance of %MultiHashMapT that is empty,
285 * with the specified initial capacity, load factor, hash code provider, and comparer.
289 * @return An error code
290 * @param[in] capacity The initial capacity @n
291 * If it is @c 0, the default capacity(16) is used.
292 * @param[in] loadFactor The maximum ratio of elements to buckets @n
293 * If it is @c 0, the default load factor(0.75) is used.
294 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
295 * for all keys in this map
296 * @param[in] comparer An instance of the IComparer derived class to use when comparing keys
297 * @exception E_SUCCESS The method is successful.
298 * @exception E_INVALID_ARG A specified input parameter is invalid, or
299 * the specified @c capacity or the @c loadFactor is negative.
300 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
301 * @see MultiHashMapT()
303 result Construct(int capacity, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
304 const IComparerT< KeyType >& comparer)
306 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
307 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
309 result r = E_SUCCESS;
313 __capacity = DEFAULT_CAPACITY;
318 while (__capacity < capacity)
325 if (Float::Compare(loadFactor, 0) == 0)
327 __loadFactor = DEFAULT_LOAD_FACTOR;
331 __loadFactor = loadFactor;
335 __threshold = static_cast< int >(__capacity * __loadFactor);
337 // set hash code provider
338 __pProvider = const_cast< IHashCodeProviderT< KeyType >* >(&provider);
341 __pComparer = const_cast< IComparerT< KeyType >* >(&comparer);
343 __pTable = new __MultiHashMapEntryT< KeyType, ValueType >*[__capacity];
344 TryCatch(__pTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
346 memset(__pTable, null, sizeof(__MultiHashMapEntryT< KeyType, ValueType >*) * __capacity);
359 * Initializes this instance of %MultiHashMapT by copying the elements of the specified map,
360 * with the specified load factor, hash code provider, and comparer.
364 * @return An error code
365 * @param[in] map A map to copy
366 * @param[in] loadFactor The maximum ratio of elements to buckets @n
367 * If it is @c 0, the default load factor(0.75) is used.
368 * @param[in] provider An instance of the IHashCodeProvider derived class that supplies the hash codes
369 * for all keys in this map
370 * @param[in] comparer An instance of the IComparer derived class to use when comparing keys
371 * @exception E_SUCCESS The method is successful.
372 * @exception E_INVALID_ARG A specified input parameter is invalid, or
373 * the specified @c loadFactor is negative.
374 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
375 * the @c map is modified during the operation of this method.
376 * @remarks The instances of hash code provider and comparer will not be deallocated later from this map.
377 * @see MultiHashMapT()
379 result Construct(const IMultiMapT< KeyType, ValueType >& map, float loadFactor, const IHashCodeProviderT< KeyType >& provider,
380 const IComparerT< KeyType >& comparer)
382 TryReturn(loadFactor >= 0, E_INVALID_ARG, "[%s] The loadFactor(%f) MUST be greater than or equal to 0.0.", GetErrorMessage(E_INVALID_ARG), loadFactor);
384 result r = E_SUCCESS;
386 if (Float::Compare(loadFactor, 0) == 0)
388 loadFactor = DEFAULT_LOAD_FACTOR;
391 int capacity = static_cast< int >(map.GetCount() / loadFactor) + 1;
393 r = Construct(capacity, loadFactor, provider, comparer);
394 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
397 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
414 * Adds the specified key-value pair to this map.
418 * @return An error code
419 * @param[in] key A key of the value to add
420 * @param[in] value A value to add
421 * @exception E_SUCCESS The method is successful.
422 * @exception E_OBJ_ALREADY_EXIST The specified pair of @c key and @c value already exists.
423 * @exception E_INVALID_ARG A specified input parameter is invalid, or
424 * the comparer has failed to compare the keys.
425 * @remarks SetItem() can be used to set value to a key that does not already exist.
426 * However, setting a value to a key that already exists overwrites the value.
430 virtual result Add(const KeyType& key, const ValueType& value)
432 result r = E_SUCCESS;
433 int hash = Hash(key);
434 int i = hash & (__capacity - 1);
435 __ValueNodeT< ValueType >* pNode = null;
436 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
437 while (null != pEntry)
439 if (hash == pEntry->hash)
442 r = __pComparer->Compare(key, pEntry->key, cmpResult);
443 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
447 pNode = pEntry->pList;
450 if (pNode->value == value)
452 return E_OBJ_ALREADY_EXIST;
455 if (pNode->pNext != null)
457 pNode = pNode->pNext;
468 pEntry = pEntry->pNext;
471 __ValueNodeT< ValueType >* pNewNode = new __ValueNodeT< ValueType >(value);
472 TryReturn(pNewNode != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
474 // key is not exist in this map.
477 __MultiHashMapEntryT< KeyType, ValueType >* pNewEntry = new __MultiHashMapEntryT< KeyType, ValueType >(key, pNewNode, __pTable[i],
479 TryReturn(pNewEntry != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
480 __pTable[i] = pNewEntry;
482 // key is already exist in this map, but value is not.
485 // pNode is the last value associated to the key
486 pNode->pNext = pNewNode;
491 if (__count++ >= __threshold)
493 r = Resize(__capacity * 2);
494 TryReturn(r == E_SUCCESS, r, "[%s] Propagating.", GetErrorMessage(r));
501 * Gets an enumerator of this map.
505 * @return An enumerator (an instance of the %IMapEnumeratorT derived class) of this map, @n
506 * else @c null if an exception occurs
507 * @exception E_SUCCESS The method is successful.
508 * @exception E_OUT_OF_MEMORY The memory is insufficient.
509 * @remarks If the key has multiple values, the Enumeration proceeds as follows: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
510 * The specific error code can be accessed using the GetLastResult() method.
511 * @see Tizen::Base::Collection::IEnumerator
512 * @see Tizen::Base::Collection::IMapEnumerator
514 virtual IEnumeratorT< MapEntryT< KeyType, ValueType > >* GetEnumeratorN(void) const
516 result r = E_SUCCESS;
518 __MultiHashMapEnumeratorT< KeyType, ValueType >* pEnum = new __MultiHashMapEnumeratorT< KeyType, ValueType >(*this, __modCount);
519 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
521 SetLastResult(E_SUCCESS);
530 * Gets an IMapEnumerator of this map.
534 * @return An enumerator (an instance of the %IMapEnumeratorT derived class) of this map, @n
535 * else @c null if an exception occurs
536 * @exception E_SUCCESS The method is successful.
537 * @exception E_OUT_OF_MEMORY The memory is insufficient.
538 * @remarks If the key has multiple values, the Enumeration proceeds like this: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
539 * @remarks The specific error code can be accessed using the GetLastResult() method.
540 * @see Tizen::Base::Collection::IEnumerator
541 * @see Tizen::Base::Collection::IMapEnumerator
543 virtual IMapEnumeratorT< KeyType, ValueType >* GetMapEnumeratorN(void) const
545 return dynamic_cast< IMapEnumeratorT< KeyType, ValueType >* >(GetEnumeratorN());
549 * Gets an enumerator of the values associated with the specified key.
553 * @return An enumerator (an instance of the IEnumeratorT derived class) of the values associated with the specified key, @n
554 * else @c null if an exception occurs
555 * @param[in] key A key to locate
556 * @exception E_SUCCESS The method is successful.
557 * @exception E_INVALID_ARG A specified input parameter is invalid, or
558 * the comparer has failed to compare the keys.
559 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
560 * @remarks The specific error code can be accessed using the GetLastResult() method.
563 virtual IEnumeratorT< ValueType >* GetValuesN(const KeyType& key) const
565 result r = E_OBJ_NOT_FOUND;
567 int hash = Hash(key);
568 int i = hash & (__capacity - 1);
569 IEnumeratorT< ValueType >* pEnum = null;
571 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
573 if (hash == pEntry->hash)
576 r = __pComparer->Compare(key, pEntry->key, cmpResult);
577 TryCatch(r == E_SUCCESS, r = E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
581 pEnum = new __EntryValueEnumeratorT< KeyType, ValueType >(*pEntry, pEntry->modCount);
582 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
600 * Gets a list of all unique keys in this map.
604 * @return A list of all unique keys in this map, @n
605 * else @c null if an exception occurs
606 * @exception E_SUCCESS The method is successful.
607 * @exception E_OUT_OF_MEMORY The memory is insufficient.
608 * @remarks The specific error code can be accessed using the GetLastResult() method.
611 virtual IListT< KeyType >* GetKeysN(void) const
615 result r = E_SUCCESS;
618 ArrayListT< KeyType >* pList = new ArrayListT< KeyType >();
619 r = pList->Construct(__count);
620 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
622 for (int i = 0; i < __capacity; i++)
624 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
626 r = pList->Add(pEntry->key);
627 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
642 * Gets a list of all the values in this map.
646 * @return A list of all the values in this map, @n
647 * else @c null if an exception occurs
648 * @exception E_SUCCESS The method is successful.
649 * @exception E_OUT_OF_MEMORY The memory is insufficient.
650 * @remarks The specific error code can be accessed using the GetLastResult() method.
653 virtual IListT< ValueType >* GetValuesN(void) const
657 result r = E_SUCCESS;
659 ArrayListT< ValueType >* pList = new ArrayListT< ValueType >();
660 r = pList->Construct(__count);
661 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
663 for (int i = 0; i < __capacity; i++)
665 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
667 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
669 r = pList->Add(pNode->value);
670 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
685 * Removes all the values for the specified key.
689 * @return An error code
690 * @param[in] key The key to remove
691 * @exception E_SUCCESS The method is successful.
692 * @exception E_INVALID_ARG The specified input parameter is invalid, or
693 * the comparer has failed to compare the keys.
694 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
697 virtual result Remove(const KeyType& key)
699 result r = E_OBJ_NOT_FOUND;
700 int hash = Hash(key);
701 int i = hash & (__capacity - 1);
703 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
704 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
706 if (hash == pEntry->hash)
709 r = __pComparer->Compare(key, pEntry->key, cmpResult);
710 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
719 __pTable[i] = pEntry->pNext;
723 pPrev->pNext = pEntry->pNext;
726 __ValueNodeT< ValueType >* pNode = pEntry->pList;
727 while (null != pNode)
729 __ValueNodeT< ValueType >* pTemp = pNode;
730 pNode = pNode->pNext;
746 * Removes the specified value associated with the specified key. @n
747 * The key is also removed if there is no value associated with it.
751 * @return An error code
752 * @param[in] key The key whose mapping is to remove from the map
753 * @param[in] value The value to remove
754 * @exception E_SUCCESS The method is successful.
755 * @exception E_INVALID_ARG A specified input parameter is invalid, or
756 * the comparer has failed to compare the keys.
757 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
760 virtual result Remove(const KeyType& key, const ValueType& value)
762 result r = E_OBJ_NOT_FOUND;
763 int hash = Hash(key);
764 int i = hash & (__capacity - 1);
766 __MultiHashMapEntryT< KeyType, ValueType >* pPrev = __pTable[i];
767 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
769 if (hash == pEntry->hash)
772 r = __pComparer->Compare(key, pEntry->key, cmpResult);
773 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
778 __ValueNodeT< ValueType >* pPrevNode = pEntry->pList;
779 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
781 if (value == pNode->value)
785 if (pPrevNode == pNode)
787 pEntry->pList = pNode->pNext;
791 pPrevNode->pNext = pNode->pNext;
798 if (null == pEntry->pList)
802 __pTable[i] = pEntry->pNext;
806 pPrev->pNext = pEntry->pNext;
828 * Removes all key-value pairs in this map.
832 virtual void RemoveAll(void)
843 * Replaces the value associated with the key with the specified @c newValue.
847 * @return An error code
848 * @param[in] key A key
849 * @param[in] value A value to replace
850 * @param[in] newValue A new value to replace the existing value
851 * @exception E_SUCCESS The method is successful.
852 * @exception E_INVALID_ARG A specified input parameter is invalid, or
853 * the comparer has failed to compare the keys.
854 * @exception E_OBJ_NOT_FOUND The specified @c key and @c value pair is not found in the map.
855 * @remarks To add a new key-value pair, use the Add() method.
859 virtual result SetValue(const KeyType& key, const ValueType& value, const ValueType& newValue)
861 result r = E_SUCCESS;
862 int hash = Hash(key);
863 int i = hash & (__capacity - 1);
864 __ValueNodeT< ValueType >* pNode = null;
865 bool pairExist = false;
866 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
867 while (null != pEntry)
869 if (hash == pEntry->hash)
872 r = __pComparer->Compare(key, pEntry->key, cmpResult);
873 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
877 pNode = pEntry->pList;
880 if (pNode->value == value)
883 pNode->value = newValue;
887 if (pNode->pNext != null)
889 pNode = pNode->pNext;
900 pEntry = pEntry->pNext;
912 * Gets the number of values currently stored in this map.
916 * @return The number of values currently stored in this map
918 virtual int GetCount(void) const
924 * Gets the number of values whose keys match the specified key.
928 * @return An error code
929 * @param[in] key A key to locate
930 * @param[out] count The number of values whose key is @c key
931 * @exception E_SUCCESS The method is successful.
932 * @exception E_INVALID_ARG A specified input parameter is invalid, or
933 * the comparer has failed to compare the keys.
934 * @exception E_OBJ_NOT_FOUND The specified @c key is not found in the map.
936 virtual result GetCount(const KeyType& key, int& count) const
938 result r = E_OBJ_NOT_FOUND;
939 int hash = Hash(key);
940 int i = hash & (__capacity - 1);
942 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
944 if (hash == pEntry->hash)
947 r = __pComparer->Compare(key, pEntry->key, cmpResult);
948 TryReturn(r == E_SUCCESS, E_INVALID_ARG, "[%s] Propagating.", GetErrorMessage(r));
953 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
970 * Checks whether the map contains the specified key and value.
974 * @return An error code
975 * @param[in] key The key to locate
976 * @param[in] value The value to locate
977 * @param[out] out Set to @c true if the map contains the specified key and value pair, @n
979 * @exception E_SUCCESS The method is successful.
980 * @exception E_INVALID_ARG The current state of the instance prohibits the execution of the specified operation, or
981 * the comparer has failed to compare the keys.
983 * @see ContainsValue()
985 virtual result Contains(const KeyType& key, const ValueType& value, bool& out) const
989 result r = E_SUCCESS;
990 int hash = Hash(key);
991 int i = hash & (__capacity - 1);
993 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
995 if (hash == pEntry->hash)
998 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1001 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1003 return E_INVALID_ARG;
1008 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1010 if (value == pNode->value)
1026 * Checks whether the map contains the specified key.
1030 * @return An error code
1031 * @param[in] key The key to locate
1032 * @param[out] out Set to @c true if the map contains the specified key, @n
1034 * @exception E_SUCCESS The method is successful.
1035 * @exception E_INVALID_ARG A specified input parameter is invalid, or
1036 * the comparer has failed to compare the keys.
1037 * @see ContainsValue()
1040 virtual result ContainsKey(const KeyType& key, bool& out) const
1043 result r = E_SUCCESS;
1044 int hash = Hash(key);
1045 int i = hash & (__capacity - 1);
1047 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1049 if (hash == pEntry->hash)
1052 r = __pComparer->Compare(key, pEntry->key, cmpResult);
1055 AppLogException("[%s] Propagating.", GetErrorMessage(r));
1057 return E_INVALID_ARG;
1071 * Checks whether the map contains the specified value.
1075 * @return @c true if the map contains the specified value, @n
1077 * @param[in] value The value to locate
1079 * @see ContainsKey()
1082 virtual bool ContainsValue(const ValueType& value) const
1085 for (int i = 0; i < __capacity; i++)
1087 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1089 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1091 if (value == pNode->value)
1110 * Compares the specified instance to the current instance for equality.
1114 * @return @c true if the two instances are equal, @n
1116 * @param[in] obj The object to compare with the current instance
1117 * @remarks This method returns @c true only if the specified object is also an instance of the %MultiHashMapT class,
1118 * both maps have the same number of elements, and both maps contain the same elements.
1120 virtual bool Equals(const Object& obj) const
1122 result r = E_SUCCESS;
1125 const MultiHashMapT< KeyType, ValueType >* other = dynamic_cast< const MultiHashMapT< KeyType, ValueType >* >(&obj);
1126 if (null == other) // obj is not MultiHashMapT<KeyType, ValueType>
1130 else if (other == this)
1134 else if (__count != other->__count)
1140 for (int i = 0; i < __capacity; i++)
1142 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1144 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1146 r = other->Contains(pEntry->key, pNode->value, out);
1164 * Gets the hash value of the current instance.
1168 * @return The hash value of the current instance
1169 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
1170 * the used hash function must generate a random distribution for all inputs.
1172 virtual int GetHashCode(void) const
1176 for (int i = 0; i < __capacity; i++)
1178 for (__MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i]; null != pEntry; pEntry = pEntry->pNext)
1180 for (__ValueNodeT< ValueType >* pNode = pEntry->pList; null != pNode; pNode = pNode->pNext)
1182 hash += reinterpret_cast< int >(&pNode->value);
1184 hash += reinterpret_cast< int >(&pEntry->key);
1191 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
1193 * @param[in] map An instance of %MultiHashMapT to initialize the current instance
1195 MultiHashMapT(const MultiHashMapT< KeyType, ValueType >& map);
1198 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
1200 * @param[in] map An instance of %MultiHashMapT
1202 MultiHashMapT< KeyType, ValueType >& operator =(const MultiHashMapT< KeyType, ValueType >& map);
1205 * Copies all the pairs from the specified map to this map.
1207 * @return An error code
1208 * @param[in] map The map to copy
1209 * @exception E_SUCCESS The method is successful.
1210 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation. @n
1211 * The @c map is modified during the operation of this method.
1213 result AddAll(const IMultiMapT< KeyType, ValueType >& map)
1215 result r = E_SUCCESS;
1217 IMultiMapT< KeyType, ValueType >* pMap = const_cast< IMultiMapT< KeyType, ValueType >* >(&map);
1218 IMapEnumeratorT< KeyType, ValueType >* pMapEnum = pMap->GetMapEnumeratorN();
1220 TryCatch(pMapEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
1227 r = pMapEnum->MoveNext();
1228 // enumerator is reached to the end of collection
1229 if (E_OUT_OF_RANGE == r)
1234 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1236 r = pMapEnum->GetKey(key);
1237 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1239 r = pMapEnum->GetValue(value);
1240 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1242 r = Add(key, value);
1243 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
1246 if (null != pMapEnum)
1253 if (null != pMapEnum)
1261 * Gets a hash value for the specified object.
1263 * @return The hash value for the specified object
1264 * @param[in] obj The object to get hash value
1266 int Hash(const KeyType& obj) const
1268 int h = __pProvider->GetHashCode(obj);
1270 h ^= (h >> 20) ^ (h >> 12);
1272 return h ^ (h >> 7) ^ (h >> 4);
1276 * Resizes the contents of this map into a new array with a
1277 * larger capacity. @n
1278 * This method is called automatically when the
1279 * number of keys in this map reaches its threshold.
1281 * @return An error code
1282 * @param[in] newCapacity The new capacity @n
1283 * It must be a power of 2 and must be greater than current capacity.
1284 * @exception E_SUCCESS The method is successful.
1285 * @exception E_OUT_OF_MEMORY The memory is insufficient.
1287 result Resize(int newCapacity)
1289 result r = E_SUCCESS;
1290 __MultiHashMapEntryT< KeyType, ValueType >** newTable = new __MultiHashMapEntryT< KeyType, ValueType >*[newCapacity];
1291 TryCatch(newTable != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
1292 for (int i = 0; i < newCapacity; i++)
1297 for (int i = 0; i < __capacity; i++)
1299 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1300 while (null != pEntry)
1302 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1303 int i = pEntry->hash & (newCapacity - 1);
1304 pEntry->pNext = newTable[i];
1305 newTable[i] = pEntry;
1311 __pTable = newTable;
1312 __capacity = newCapacity;
1313 __threshold = static_cast< int >(__capacity * __loadFactor);
1322 * Clears all key-value pairs in this map.
1327 for (int i = 0; i < __capacity; i++)
1329 __MultiHashMapEntryT< KeyType, ValueType >* pEntry = __pTable[i];
1330 while (null != pEntry)
1332 __MultiHashMapEntryT< KeyType, ValueType >* pNext = pEntry->pNext;
1333 __ValueNodeT< ValueType >* pNode = pEntry->pList;
1334 while (null != pNode)
1336 __ValueNodeT< ValueType >* pTemp = pNode;
1337 pNode = pNode->pNext;
1347 __MultiHashMapEntryT< KeyType, ValueType >** __pTable;
1352 IHashCodeProviderT< KeyType >* __pProvider;
1353 IComparerT< KeyType >* __pComparer;
1354 bool __defaultConstruct;
1357 static const int DEFAULT_CAPACITY = 16;
1358 static const float DEFAULT_LOAD_FACTOR;
1360 friend class __MultiHashMapEnumeratorT< KeyType, ValueType >;
1365 // @class __ValueNodeT
1366 // @brief This class is a node for MultiHashMapT.
1369 template< class ValueType >
1375 * This is the constructor for this class.
1379 * @param[in] v An object to include in this node
1381 __ValueNodeT(const ValueType& v)
1388 * This is the destructor for this class.
1392 virtual ~__ValueNodeT(void)
1397 * Internal variable.
1401 __ValueNodeT< ValueType >* pNext;
1404 * Internal variable.
1413 // @class __MultiHashMapEntryT
1414 // @brief This class is an entry for MultiHashMapT class.
1417 template< class KeyType, class ValueType >
1418 class __MultiHashMapEntryT
1423 * This is the constructor for this class.
1427 * @param[in] keyType A key to include in this entry
1428 * @param[in] list A list of values whose key is specified @n
1429 * It cannot be @c null.
1430 * @param[in] next A pointer to the next entry
1431 * @param[in] h An hash value of the key
1433 __MultiHashMapEntryT(const KeyType& keyType, __ValueNodeT< ValueType >* list, __MultiHashMapEntryT< KeyType, ValueType >* next, int h)
1443 * This is the destructor for this class.
1447 virtual ~__MultiHashMapEntryT(void)
1452 * Internal variable.
1459 * Internal variable.
1463 __ValueNodeT< ValueType >* pList;
1466 * Internal variable.
1470 __MultiHashMapEntryT< KeyType, ValueType >* pNext;
1473 * Internal variable.
1480 * Internal variable.
1486 friend class __EntryValueEnumeratorT< KeyType, ValueType >;
1488 }; // __MultiHashMapEntryT
1491 // @class __MultiHashMapEnumeratorT
1492 // @brief This class is an implementation of IMapEnumeratorT for %MultiHashMapT.
1495 template< class KeyType, class ValueType >
1496 class __MultiHashMapEnumeratorT
1497 : public IMapEnumeratorT< KeyType, ValueType >
1502 * This is the constructor for this class.
1506 * @param[in] map A map to enumerate
1507 * @param[in] modCount The modification count to detect the change in the map
1509 __MultiHashMapEnumeratorT(const MultiHashMapT< KeyType, ValueType >& map, int modCount)
1511 , __modCount(modCount)
1519 * This is the destructor for this class.
1523 virtual ~__MultiHashMapEnumeratorT(void)
1528 * Gets the current object in the map.
1532 * @return An error code
1533 * @param[out] obj The current object
1534 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1535 * - The current state of the instance prohibits the execution of the specified operation. @n
1536 * - This enumerator is currently positioned before the first element or
1537 * past the last element. @n
1538 * - The map is modified after this enumerator is created.
1539 * @exception E_SUCCESS The method is successful.
1541 result GetCurrent(MapEntryT< KeyType, ValueType >& obj) const
1543 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1544 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1545 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1546 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1548 obj = MapEntryT< KeyType, ValueType >(__pEntry->key, __pNode->value);
1553 * Moves this enumerator to the next element of the map. @n
1554 * After the enumerator is first created or reset using the Reset() method,
1555 * the first call to this method positions the enumerator to the first element in the @c collection.
1559 * @return An error code
1560 * @exception E_SUCCESS The method is successful.
1561 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1562 * the map is modified after this enumerator is created.
1563 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the map.
1566 result MoveNext(void)
1568 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1569 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1571 result r = E_SUCCESS;
1572 if ((null != __pNode) && (__pNode->pNext != null))
1574 __pNode = __pNode->pNext;
1576 else if ((null != __pEntry) && (__pEntry->pNext != null))
1578 __pEntry = __pEntry->pNext;
1579 __pNode = __pEntry->pList;
1585 if (++__index >= static_cast< int >(__map.__capacity))
1587 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1591 __pEntry = __map.__pTable[__index];
1592 if (null != __pEntry)
1594 __pNode = __pEntry->pList;
1604 * Positions this enumerator before the first element in the map.
1608 * @return An error code
1609 * @exception E_SUCCESS The method is successful.
1610 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1611 * the map is modified after this enumerator is created.
1615 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1616 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1625 * Gets the current key in the map.
1629 * @return An error code
1630 * @param[out] key The current key
1631 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1632 * - The current state of the instance prohibits the execution of the specified operation. @n
1633 * - This enumerator is currently positioned before the first element or
1634 * past the last element. @n
1635 * - The map is modified after this enumerator is created.
1636 * @exception E_SUCCESS The method is successful.
1638 result GetKey(KeyType& key) const
1640 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1641 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1642 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1643 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1645 key = __pEntry->key;
1650 * Gets the current value in the map.
1654 * @return An error code
1655 * @param[out] value The current value
1656 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1657 * - The current state of the instance prohibits the execution of the specified operation. @n
1658 * - This enumerator is currently positioned before the first element or
1659 * past the last element. @n
1660 * - The map is modified after the enumerator is created.
1661 * @exception E_SUCCESS The method is successful.
1663 result GetValue(ValueType& value) const
1665 TryReturn((__modCount == __map.__modCount), E_INVALID_OPERATION,
1666 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1667 TryReturn((__pEntry != null && __pNode != null), E_INVALID_OPERATION,
1668 "[%s] Invalid position(pEntry or pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1670 value = __pNode->value;
1675 const MultiHashMapT< KeyType, ValueType >& __map;
1677 __MultiHashMapEntryT< KeyType, ValueType >* __pEntry;
1678 __ValueNodeT< ValueType >* __pNode;
1681 }; // __MultiHashMapEnumeratorT
1684 // @class __EntryValueEnumeratorT
1685 // @brief This class is an implementation of IEnumeratorT to enumerate values whose key is the same.
1688 template< class KeyType, class ValueType >
1689 class __EntryValueEnumeratorT
1690 : public IEnumeratorT< ValueType >
1695 * Initializes an instance of __EntryValueEnumeratorT with the specified parameters.
1699 * @param[in] entry An entry to enumerate
1700 * @param[in] modCount The modification count to detect the change in the entry
1702 __EntryValueEnumeratorT(const __MultiHashMapEntryT< KeyType, ValueType >& entry, int modCount)
1704 , __modCount(modCount)
1711 * This is the destructor for this class.
1715 virtual ~__EntryValueEnumeratorT(void)
1720 * Gets the current value in the entry.
1724 * @return An error code
1725 * @param[out] obj The current value
1726 * @exception E_INVALID_OPERATION Either of the following conditions has occurred: @n
1727 * - The current state of the instance prohibits the execution of the specified operation. @n
1728 * - This enumerator is currently positioned before the first element or
1729 * past the last element. @n
1730 * - The entry is modified after this enumerator is created.
1731 * @exception E_SUCCESS The method is successful.
1733 result GetCurrent(ValueType& obj) const
1735 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1736 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1737 TryReturn(__pNode != null, E_INVALID_OPERATION, "[%s] Invalid position(pNode is null).", GetErrorMessage(E_INVALID_OPERATION));
1739 obj = __pNode->value;
1744 * Moves this enumerator to the next element of the entry. @n
1745 * After the enumerator is first created or reset using the Reset() method,
1746 * the first call to this method positions the enumerator to the first element in the collection.
1750 * @return An error code
1751 * @exception E_SUCCESS The method is successful.
1752 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1753 * the entry is modified after this enumerator is created.
1754 * @exception E_OUT_OF_RANGE The enumerator has passed the end of the entry.
1757 result MoveNext(void)
1759 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1760 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1762 result r = E_SUCCESS;
1763 if (null == __pNode)
1765 __pNode = __entry.pList;
1766 AppAssert(null != __pNode);
1768 else if ((null != __pNode) && (__pNode->pNext != null))
1770 __pNode = __pNode->pNext;
1774 // Do not log the E_OUT_OF_RANGE, because it is normal or trivial in most cases.
1782 * Positions this enumerator before the first element in the entry.
1786 * @return An error code
1787 * @exception E_SUCCESS The method is successful.
1788 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
1789 * the entry is modified after this enumerator is created.
1793 TryReturn((__modCount == __entry.modCount), E_INVALID_OPERATION,
1794 "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
1801 const __MultiHashMapEntryT< KeyType, ValueType >& __entry;
1803 __ValueNodeT< ValueType >* __pNode;
1805 }; // __EntryValueEnumeratorT
1808 // @class __MultiHashMapDefaultProviderT
1809 // @brief This class is an implementation of IHashCodeProviderT for HashMap.
1812 template< class KeyType >
1813 class __MultiHashMapDefaultProviderT
1814 : public IHashCodeProviderT< KeyType >
1819 * This is the default constructor for this class.
1823 __MultiHashMapDefaultProviderT(void) {}
1826 * This is the destructor for this class.
1830 virtual ~__MultiHashMapDefaultProviderT(void) {}
1835 * Gets the hash code of the specified instance.
1839 * @return The hash code
1840 * @see Tizen::Base::Object::GetHashCode()
1842 virtual int GetHashCode(const KeyType& obj) const
1847 }; // __MultiHashMapDefaultProviderT
1849 template< class KeyType, class ValueType >
1850 const float MultiHashMapT< KeyType, ValueType >::DEFAULT_LOAD_FACTOR = 0.75;
1852 }}} // Tizen::Base::Collection
1854 #endif //_FBASE_COL_MULTI_HASH_MAP_T_H_