inc/FBaseColMultiHashMap.h

   1 //
   2 // Open Service Platform
   3 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
   4 //
   5 // Licensed under the Apache License, Version 2.0 (the License);
   6 // you may not use this file except in compliance with the License.
   7 // You may obtain a copy of the License at
   8 //
   9 // http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing, software
  12 // distributed under the License is distributed on an "AS IS" BASIS,
  13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 // See the License for the specific language governing permissions and
  15 // limitations under the License.
  16 //
  17
  18 /**
  19  * @file                FBaseColMultiHashMap.h
  20  * @brief               This is the header file for the %MultiHashMap class.
  21  *
  22  * This header file contains the declarations of the %MultiHashMap class.
  23  */
  24 #ifndef _FBASE_COL_MULTI_HASH_MAP_H_
  25 #define _FBASE_COL_MULTI_HASH_MAP_H_
  26
  27 #include <FBaseObject.h>
  28 #include <FBaseColIComparer.h>
  29 #include <FBaseColIHashCodeProvider.h>
  30 #include <FBaseColIMultiMap.h>
  31
  32
  33 namespace Tizen { namespace Base { namespace Collection
  34 {
  35
  36 class _MultiHashMapEntry;
  37
  38 /**
  39  * @class MultiHashMap
  40  * @brief This class represents a collection of associated keys and values that are organized based on the hash code of the key.
  41  *
  42  * @since 2.0
  43  *
  44  *  The %MultiHashMap class represents a collection of associated keys and values that are organized based on the hash code of the key.
  45  * There is no limit on the number of elements with the same key, but duplicated elements with the same key are not allowed.
  46  * The key and value cannot be @c null.
  47  * @n
  48  * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/hashmap_multihashmap.htm">HashMap and MultiHashMap</a>.
  49  *
  50  * The following example demonstrates how to use the %MultiHashMap class.
  51  *
  52  * @code
  53  *      #include <FBase.h>
  54  *
  55  *      using namespace Tizen::Base;
  56  *      using namespace Tizen::Base::Collection;
  57  *
  58  *      void
  59  *      MyClass::MultiHashMapSample(void)
  60  *      {
  61  *              MultiHashMap map(SingleObjectDeleter);
  62  *
  63  *              // Constructs a MultiHashMap instance with default values for capacity, load factor, hash code provider, and comparer
  64  *              map.Construct();
  65  *
  66  *              map.Add(new String(L"Zero"), new Integer(0));           // map.GetCount() : 1, map : (Zero -> 0)
  67  *              map.Add(new String(L"One"), new Integer(1));            // map.GetCount() : 2, map : (Zero -> 0), (one -> 1)
  68  *              map.Add(new String(L"Two"), new Integer(2));            // map.GetCount() : 3, map : (Zero -> 0), (one -> 1), (Two -> 2)
  69  *              map.Add(new String(L"Two"), new Integer(20));           // map.GetCount() : 4, map : (Zero -> 0), (One -> 1), (Two -> 2, 20)
  70  *
  71  *              // Gets values with the specified key
  72  *              Integer*        pValue = null;
  73  *              IEnumerator *pValueEnum = map.GetValuesN(String(L"Two"));
  74  *              while(pValueEnum->MoveNext() == E_SUCCESS)
  75  *              {
  76  *                      pValue = static_cast<Integer*> (pValueEnum->GetCurrent());
  77  *              }
  78  *
  79  *              delete pValueEnum;
  80  *
  81  *              // Removes values with the specified key     // String(L"Two"), Integer(2), Integer(20) are removed
  82  *              map.Remove(String(L"Two"));
  83  *
  84  *              // Uses an enumerator to access elements in the map
  85  *              IMapEnumerator* pMapEnum = map.GetMapEnumeratorN();
  86  *              String* pKey = null;
  87  *              while (pMapEnum->MoveNext() == E_SUCCESS)
  88  *              {
  89  *                      pKey = static_cast< String* > (pMapEnum->GetKey());
  90  *                      pValue = static_cast< Integer* > (pMapEnum->GetValue());
  91  *              }
  92  *
  93  *              delete pMapEnum;
  94  *
  95  *              // Deallocates all objects
  96  *              // Because the destructor calls RemoveAll() internally, you don't need to call RemoveAll() to destroy all elements at the end.
  97  *              map.RemoveAll();
  98  *      }
  99  * @endcode
 100  */
 101 class _OSP_EXPORT_ MultiHashMap
 102         : public IMultiMap
 103         , public Object
 104 {
 105 public:
 106         using IMultiMap::Add;
 107         using IMultiMap::Remove;
 108         using IMultiMap::RemoveAll;
 109         using IMultiMap::SetValue;
 110         using IMultiMap::Contains;
 111         using IMultiMap::ContainsKey;
 112
 113         /**
 114          * The object is not fully constructed after this constructor is called. For full construction, @n
 115          * the Construct() method must be called right after calling this constructor.
 116          *
 117          * @since 2.0
 118          *
 119          * @param[in]   deleter The function pointer to type of the element deleter
 120          * @remarks     To create an owing collection, set the element deleter value as @c SingleObjectDeleter. This gives the collection the ownership of elements and the collection will destroy elements. @n
 121          *                      On the other hand, to create a non-owning collection, you don't need to set the element deleter value, as @c NoOpDeleter is the default element deleter.
 122          *                      It means that you don't transfer the ownership of elements to the collection.
 123          * @see         NoOpDeleter()
 124          * @see         SingleObjectDeleter()
 125          * @see         ArrayDeleter()
 126          */
 127         explicit MultiHashMap(DeleterFunctionType deleter = NoOpDeleter);
 128
 129         /**
 130          * This destructor overrides Tizen::Base::Object::~Object().
 131          *
 132          * @since 2.0
 133          */
 134         virtual ~MultiHashMap(void);
 135
 136         /**
 137          * Initializes a new instance of %MultiHashMap with the specified capacity and load factor.
 138          *
 139          * @since 2.0
 140          *
 141          * @return              An error code
 142          * @param[in]   capacity                The initial capacity
 143          * @param[in]   loadFactor              The maximum ratio of elements to buckets
 144          * @exception   E_SUCCESS               The method is successful.
 145          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 146          *                                                                the @c capacity or the @c loadFactor is negative.
 147          * @remarks             The GetHashCode() method of the key object is used for hashing and the
 148          *                              Equals() method of the key object is used for comparing the keys.
 149          * @see                 MultiHashMap()
 150          */
 151         result Construct(int capacity = 16, float loadFactor = 0.75);
 152
 153         /**
 154          * Initializes a new instance of %MultiHashMap by copying the elements of the given map.
 155          *
 156          * @since 2.0
 157          *
 158          * @return              An error code
 159          * @param[in]   map                             The map to copy
 160          * @param[in]   loadFactor              The maximum ratio of elements to buckets @n
 161          *                                                              If it is @c 0, the default load factor(0.75) is used.
 162          * @exception   E_SUCCESS                       The method is successful.
 163          * @exception   E_INVALID_ARG           The specified @c loadFactor is negative.
 164          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 165          *                                                                      the @c map is modified during the operation of this method.
 166          * @remarks             This method performs a shallow copy. It copies just the pointer; not the element itself.
 167          * @see                 MultiHashMap()
 168          */
 169         result Construct(const IMultiMap& map, float loadFactor = 0.75);
 170
 171
 172         /**
 173          * Initializes a new instance of the %MultiHashMap class, with the specified initial capacity, load factor, hash code provider, and comparer.
 174          *
 175          * @since 2.0
 176          *
 177          * @return              An error code
 178          * @param[in]   capacity        The initial capacity @n
 179          *                                                      If it is @c 0, the default capacity (16) is used.
 180          * @param[in]   loadFactor      The maximum ratio of elements to buckets @n
 181          *                                                      If it is @c 0, the default load factor (0.75) is used.
 182          * @param[in]   provider        An instance of the IHashCodeProvider derived class that supplies the hash codes
 183          *                                                      for all keys in this map
 184          * @param[in]   comparer        An instance of the IComparer derived class to use when comparing keys
 185          * @exception   E_SUCCESS               The method is successful.
 186          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 187          *                                                                the @c capacity or the @c loadFactor is negative.
 188          * @remarks             The instances of hash code provider and comparer will not be deallocated later from this map.
 189          * @see                 MultiHashMap()
 190          */
 191         result Construct(int capacity, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer);
 192
 193         /**
 194          * Initializes a new instance of the %MultiHashMap class by copying the elements of the specified map,
 195          * with the specified load factor, hash code provider, and comparer.
 196          *
 197          * @since 2.0
 198          *
 199          * @return              An error code
 200          * @param[in]   map                     A map to copy
 201          * @param[in]   loadFactor      The maximum ratio of elements to buckets @n
 202          *                                                      If it is @c 0, the default load factor (0.75) is used.
 203          * @param[in]   provider        An instance of the IHashCodeProvider derived class that supplies the hash codes
 204          *                                                      for all keys in this map
 205          * @param[in]   comparer        An instance of the IComparer derived class to use when comparing keys
 206          * @exception   E_SUCCESS                       The method is successful.
 207          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 208          *                                                                      the @c loadFactor is negative.
 209          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 210          *                                                                      the @c map is modified during the operation of this method.
 211          * @remarks             This method performs a shallow copy. It copies just the pointer; not the element itself.
 212          *                      The instances of hash code provider and comparer will not be deallocated later from this map.
 213          * @see                 MultiHashMap()
 214          */
 215         result Construct(const IMultiMap& map, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer);
 216
 217         /**
 218          * Adds the specified key-value pair to this map.
 219          *
 220          * @since 2.0
 221          *
 222          * @return              An error code
 223          * @param[in]   pKey    The pointer to key to add
 224          * @param[in]   pValue  The pointer to corresponding value to add
 225          * @exception   E_SUCCESS                       The method is successful.
 226          * @exception   E_OBJ_ALREADY_EXIST     The specified pair of @c pKey and @c pValue already exists.
 227          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 228          *                                                                      the comparer has failed to compare the keys.
 229          * @remarks             This method performs a shallow copy. It adds just the pointer; not the element itself.
 230          * @see                 Remove()
 231          */
 232         virtual result Add(Object* pKey, Object* pValue);
 233
 234         /**
 235          * Gets an enumerator of this map.
 236          *
 237          * @since 2.0
 238          *
 239          * @return              An enumerator (an instance of the IEnumerator derived class) of this map, @n
 240          *                              else @c null if some exception occurs
 241          * @remarks             If the key has multiple values, the enumeration proceeds as follows: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
 242          *                      The specific error code can be accessed using the GetLastResult() method.
 243          * @see                 IEnumerator()
 244          * @see                 IMapEnumerator()
 245          */
 246         virtual IEnumerator* GetEnumeratorN(void) const;
 247
 248         /**
 249          * Gets an enumerator of this map.
 250          *
 251          * @since 2.0
 252          *
 253          * @return              An enumerator (an instance of the IMapEnumerator derived class) of this map, @n
 254          *                              else @c null if some exception occurs
 255          * @remarks             If the key has multiple values, the enumeration proceeds as follows: {A: a}, {B: b}, {B: c}, {B, d}, {C: e}, ...
 256          *              The specific error code can be accessed using the GetLastResult() method.
 257          * @see                 IEnumerator()
 258          * @see                 IMapEnumerator()
 259          */
 260         virtual IMapEnumerator* GetMapEnumeratorN(void) const;
 261
 262         /**
 263          * Gets an enumerator of the values associated with the specified key.
 264          *
 265          * @since 2.0
 266          *
 267          * @return              An enumerator (an instance of the IEnumerator derived class) of the values associated with the specified key, @n
 268          *                              else @c null if some exception occurs
 269          * @param[in]   key     A key to locate
 270          * @exception   E_SUCCESS                       The method is successful.
 271          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 272          *                                                                      the comparer has failed to compare the keys.
 273          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 274          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 275          * @see                 SetValue()
 276          */
 277         virtual IEnumerator* GetValuesN(const Object& key) const;
 278
 279         /**
 280          * Gets a list of all the keys in this map.
 281          *
 282          * @since 2.0
 283          *
 284          * @return              A list of all the keys in this map
 285          * @remarks             The order of the keys is the same as the corresponding values in the IList interface returned by the GetValuesN() method.
 286          *              The %IList stores just the pointers to the elements in the map, not the elements themselves.
 287          *              The specific error code can be accessed using the GetLastResult() method.
 288          * @see                 GetValuesN()
 289          */
 290         virtual IList* GetKeysN(void) const;
 291
 292         /**
 293          * Gets a list of all the values in this map.
 294          *
 295          * @since 2.0
 296          *
 297          * @return              A list of all the values in this map
 298          * @remarks             The IList stores just the pointers to the elements in the map, not the elements themselves.
 299          *                      The specific error code can be accessed using the GetLastResult() method.
 300          * @see                 GetKeysN()
 301          */
 302         virtual IList* GetValuesN(void) const;
 303
 304         /**
 305          * Removes all the values with the specified key.
 306          *
 307          * @since 2.0
 308          *
 309          * @return              An error code
 310          * @param[in]   key The key to remove
 311          * @exception   E_SUCCESS                       The method is successful.
 312          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 313          *                                                                      the comparer has failed to compare keys.
 314          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 315          * @see                 Add()
 316          */
 317         virtual result Remove(const Object& key);
 318
 319         /**
 320          * Removes the specified value associated with the specified key.
 321          *
 322          * @since 2.0
 323          *
 324          * @return              An error code
 325          * @param[in]   key The key whose mapping is to remove from the map
 326          * @param[in]   value   The value to remove
 327          * @exception   E_SUCCESS                       The method is successful.
 328          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 329          *                                                                      the comparer has failed to compare the keys.
 330          * @exception   E_OBJ_NOT_FOUND         The specified @c key and @c value pair is not found in the map.
 331          * @remarks             The specified key is also removed if there are no more values associated with it.
 332          * @see                 Add()
 333          */
 334         virtual result Remove(const Object& key, const Object& value);
 335
 336         /**
 337          * Removes all the object pointers in the @c collection. @n
 338          *
 339          * @since 2.0
 340          *
 341          * @remarks             This method can be called before deleting @c collection.
 342          */
 343         virtual void RemoveAll(void);
 344
 345         /**
 346          * Sets the value associated with the given key with a new value.
 347          *
 348          * @since 2.0
 349          *
 350          * @return              An error code
 351          * @param[in]   key             The key for which the associated value needs to replace
 352          * @param[in]   value   The value to replace
 353          * @param[in]   pNewValue       The pointer to new value to replace the existing value
 354          * @exception   E_SUCCESS                       The method is successful.
 355          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 356          *                                                                      the comparer has failed to compare the keys.
 357          * @exception   E_OBJ_NOT_FOUND         The specified @c key and @c value pair is not found in the map.
 358          * @remarks             To add a new key-value pair, use the Add() method.
 359          * @see                 Add()
 360          * @see                 GetValuesN()
 361          */
 362         virtual result SetValue(const Object& key, const Object& value, Object* pNewValue);
 363
 364         /**
 365          * Gets the number of values currently stored in this map.
 366          *
 367          * @since 2.0
 368          *
 369          * @return              The number of values currently stored in this map
 370          */
 371         virtual int GetCount(void) const;
 372
 373         /**
 374          * Gets the number of values whose key matches the key.
 375          *
 376          * @since 2.0
 377          *
 378          * @return              An error code
 379          * @param[in]   key     A key to locate
 380          * @param[out]  count   The number of values whose key is the @c key
 381          * @exception   E_SUCCESS                       The method is successful.
 382          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 383          *                                                                      the comparer has failed to compare the keys.
 384          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 385          */
 386         virtual result GetCount(const Object& key, int& count) const;
 387
 388         /**
 389          * Checks whether the map contains the specified key and value.
 390          *
 391          * @since 2.0
 392          *
 393          * @return              @c true if the map contains the specified key and value pair, @n
 394          *                              else @c false
 395          * @param[in]   key     The key to locate
 396          * @param[in]   value   The value to locate
 397          * @exception   E_SUCCESS               The method is successful.
 398          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 399          *                                                              the comparer has failed to compare the keys.
 400          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 401          * @see                 ContainsKey()
 402          * @see                 ContainsValue()
 403          */
 404         virtual bool Contains(const Object& key, const Object& value) const;
 405
 406         /**
 407          * Checks whether the map contains the specified key.
 408          *
 409          * @since 2.0
 410          *
 411          * @return              @c true if the map contains the specified key, @n
 412          *                              else @c false
 413          * @param[in]   key     The key to locate
 414          * @exception   E_SUCCESS               The method is successful.
 415          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 416          *                                                              the comparer has failed to compare the keys.
 417          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 418          * @see                 ContainsValue()
 419          * @see                 Contains()
 420          */
 421         virtual bool ContainsKey(const Object& key) const;
 422
 423         /**
 424          * Checks whether the map contains the specified value.
 425          *
 426          * @since 2.0
 427          *
 428          * @return              @c true if the map contains the specified value, @n
 429          *                              else @c false
 430          * @param[in]   value   The value to locate
 431          *
 432          * @see                         ContainsKey()
 433          * @see                         Contains()
 434          */
 435         virtual bool ContainsValue(const Object& value) const;
 436
 437         /**
 438          * Compares the specified instance to the current instance for equality.
 439          *
 440          * @since 2.0
 441          *
 442          * @return              @c true if the two instances are equal, @n
 443          *                              @c false
 444          * @param[in]   obj The object to compare with the current instance
 445          * @remarks             This method returns @c true only if the specified object is also an instance of %MultiHashMap class,
 446          *                              both maps have the same number of elements, and both maps contain the same elements.
 447          */
 448         virtual bool Equals(const Object& obj) const;
 449
 450         /**
 451          * Gets the hash value of the current instance.
 452          *
 453          * @since 2.0
 454          *
 455          * @return      The hash value of the current instance
 456          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
 457          *                      the used hash function must generate a random distribution for all inputs.
 458          */
 459         virtual int GetHashCode(void) const;
 460
 461         /**
 462          * Gets the element deleter of the collection.
 463          *
 464          * @since 2.0
 465          *
 466          * @return              An function pointer to the existing element deleter
 467          */
 468         virtual DeleterFunctionType GetDeleter(void) const;
 469
 470 private:
 471         /**
 472          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
 473          *
 474          * @param[in]   map An instance of %MultiHashMap to initialize the current instance
 475          */
 476         MultiHashMap(const MultiHashMap& map);
 477
 478         /**
 479          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
 480          *
 481          * @param[in]   map An instance of %MultiHashMap
 482          */
 483         MultiHashMap& operator =(const MultiHashMap& map);
 484
 485         /**
 486          * Copies all the pairs from the specified map to this map.
 487          *
 488          * @return              An error code
 489          * @param[in]   map The map to copy
 490          * @exception   E_SUCCESS                       The method is successful.
 491          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation. @n
 492          *                                                                      The @c map is modified during the operation of this method.
 493          */
 494         result AddAll(const IMultiMap& map);
 495
 496         /**
 497          * Gets a hash value for the specified object.
 498          *
 499          * @return              An @c int hash value for the specified object
 500          * @param[in]   obj     The object to get hash value
 501          */
 502         int Hash(const Object& obj) const;
 503
 504         /**
 505          * Rehashes the contents of this map into a new array with a
 506          * larger capacity.@n
 507          * This method is called automatically when the number of keys in this map reaches its threshold.
 508          *
 509          * @return              An error code
 510          * @param[in]   newCapacity             The new capacity @n
 511          *                                                              It must be a power of two and be greater than current capacity.
 512          * @exception   E_SUCCESS                       The method is successful.
 513          */
 514         result Resize(int newCapacity);
 515
 516         /**
 517          * Clears all key-value pairs in this map.
 518          */
 519         void Reset(void);
 520
 521         /**
 522          * Sets the element deleter of the collection.
 523          *
 524          * @since 2.0
 525          *
 526          * @param[in]   deleter An function pointer to the element deleter to set
 527          */
 528         virtual void SetDeleter(DeleterFunctionType deleter);
 529
 530         _MultiHashMapEntry** __pTable;
 531         int __count;
 532         int __capacity;
 533         float __loadFactor;
 534         int __threshold;
 535         IHashCodeProvider* __pProvider;
 536         IComparer* __pComparer;
 537         bool __needToRemoveProviderComparer;
 538         int __modCount;
 539         DeleterFunctionType __deleter;
 540         static const int DEFAULT_CAPACITY = 16;
 541         static const float DEFAULT_LOAD_FACTOR;
 542
 543         friend class _MultiHashMapEnumerator;
 544         friend class _MultiHashMapImpl;
 545         class _MultiHashMapImpl* __pMultiHashMapImpl;
 546
 547 }; // MultiHashMap
 548
 549 }}} // Tizen::Base::Collection
 550
 551 #endif //_FBASE_COL_MULTI_HASH_MAP_H_