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