inc/FBaseColHashMap.h

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