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 do not need to call RemoveAll() to destroy all elements at the end.
  88  *              // map.RemoveAll();
  89  *      }
  90  * @endcode
  91  */
  92 class _OSP_EXPORT_ HashMap
  93         : public IMap
  94         , public Object
  95 {
  96 public:
  97         using IMap::Add;
  98         using IMap::Remove;
  99         using IMap::RemoveAll;
 100         using IMap::SetValue;
 101         using IMap::ContainsKey;
 102         /**
 103          * The object is not fully constructed after this constructor is called. For full construction, @n
 104          * the Construct() method must be called right after calling this constructor.
 105          *
 106          * @since 2.0
 107          *
 108          * @param[in]   deleter The function pointer to type of the element deleter
 109          * @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
 110          *                      On the other hand, to create a non-owning collection, you do not need to set the element deleter value, as @c NoOpDeleter is the default element deleter.
 111          *                      It means that you do not transfer the ownership of 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 an empty %HashMap class with the initial capacity and 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   A specified input parameter is invalid, @n
 135          *                                                              the @c capacity or the @c loadFactor is negative.
 136          * @remarks             The GetHashCode() method of key objects is used for hashing and
 137          *                              the Equals() method of key objects is used for comparing keys.
 138          * @see                 HashMap()
 139          */
 140         result Construct(int capacity = 16, float loadFactor = 0.75);
 141
 142         /**
 143          * Initializes an instance of a %HashMap class by copying the elements of the specified @c map.
 144          *
 145          * @since 2.0
 146          *
 147          * @return              An error code
 148          * @param[in]   map                             The map to copy
 149          * @param[in]   loadFactor              The maximum ratio of elements to buckets
 150          * @exception   E_SUCCESS               The method is successful.
 151          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 152          *                                                              the @c loadFactor is negative.
 153          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 154          *                                                                      the @c map is modified during the operation of this method.
 155          * @remarks             This method performs a shallow copy. It copies only the pointer; not the element itself.
 156          * @see                 HashMap()
 157          */
 158         result Construct(const IMap& map, float loadFactor = 0.75);
 159
 160         /**
 161          * Initializes an instance of an empty %HashMap class with the specified initial capacity, load factor, hash code provider, and comparer.
 162          *
 163          * @since 2.0
 164          *
 165          * @return              An error code
 166          * @param[in]   capacity                The initial capacity @n
 167          *                                                              If it is @c 0, the default capacity(16) is used.
 168          * @param[in]   loadFactor              The maximum ratio of elements to buckets @n
 169          *                                                              If it is @c 0, the default load factor(0.75) is used.
 170          * @param[in]   provider                An instance of the IHashCodeProvider derived class that supplies the hash codes for all the keys in this map
 171          * @param[in]   comparer                An instance of the IComparer derived class to use when comparing the keys
 172          *
 173          * @exception   E_SUCCESS               The method is successful.
 174          * @exception   E_INVALID_ARG   A specified input parameter is invalid, or
 175          *                                                                the @c capacity or the @c loadFactor is negative.
 176          * @remarks             The instances of hash code provider and comparer will not be deallocated later from this map.
 177          * @see                 HashMap()
 178          */
 179         result Construct(int capacity, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer);
 180
 181         /**
 182          * Initializes an instance of a %HashMap class by copying the elements of the specified map with the specified load factor, hash code provider, and comparer.
 183          *
 184          * @since 2.0
 185          *
 186          * @return              An error code
 187          * @param[in]   map                     The map to copy
 188          * @param[in]   loadFactor      The maximum ratio of elements to buckets @n
 189          *                                                      If it is @c 0, the default load factor(0.75) is used.
 190          * @param[in]   provider        An instance of the IHashCodeProvider derived class that supplies the hash codes for all keys in this map
 191          * @param[in]   comparer        An instance of the IComparer derived class to use when comparing keys
 192          * @exception   E_SUCCESS                       The method is successful.
 193          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 194          *                                                                      the @c loadFactor is negative.
 195          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 196          *                                                                      the @c map is modified during the operation of this method.
 197          * @remarks             This method performs a shallow copy. It copies only the pointer; not the element itself.
 198          * @remarks             The instances of hash code provider and comparer will not be deallocated later from this map.
 199          * @see                 HashMap()
 200          */
 201         result Construct(const IMap& map, float loadFactor, const IHashCodeProvider& provider, const IComparer& comparer);
 202
 203         /**
 204          * Adds the specified key-value pair to a map.
 205          *
 206          * @since 2.0
 207          *
 208          * @return              An error code
 209          * @param[in]   pKey    The pointer to key of the value to add
 210          * @param[in]   pValue  The pointer to value to add
 211          * @exception   E_SUCCESS                       The method is successful.
 212          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 213          *                                                                      the comparer has failed to compare the keys.
 214          * @exception   E_OBJ_ALREADY_EXIST     The specified @c pKey already exists.
 215          * @remarks             This method performs a shallow copy. It adds only the pointer; not the element itself.
 216          * @see                 Remove()
 217          */
 218         virtual result Add(Object* pKey, Object* pValue);
 219
 220         /**
 221          * Gets an enumerator (an instance of the IMapEnumerator derived class) of this map.
 222          *
 223          * @since 2.0
 224          *
 225          * @return              An instance of the IMapEnumerator derived class, if successful @n
 226          *                              else @c null if an exception occurs
 227          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 228          * @see                 Tizen::Base::Collection::IEnumerator
 229          * @see                 Tizen::Base::Collection::IMapEnumerator
 230          */
 231         virtual IEnumerator* GetEnumeratorN(void) const;
 232
 233         /**
 234          * Gets the elements of the map in an instance of the IMapEnumerator derived class.
 235          *
 236          * @since 2.0
 237          *
 238          * @return              An instance of the IMapEnumerator derived class, @n
 239          *                              else @c null if an exception occurs
 240          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 241          * @see                 Tizen::Base::Collection::IEnumerator
 242          * @see                 Tizen::Base::Collection::IMapEnumerator
 243          */
 244         virtual IMapEnumerator* GetMapEnumeratorN(void) const;
 245
 246         /**
 247          * Gets the value associated with the specified @c key.
 248          *
 249          * @since 2.0
 250          *
 251          * @return              The value associated with the key, @n
 252          *                              else @c null if an exception occurs
 253          * @param[in]   key             The key to locate
 254          * @exception   E_SUCCESS                       The method is successful.
 255          * @exception   E_INVALID_ARG           The specified input parameter is invalid, or
 256          *                                                                      the comparer has failed to compare the keys.
 257          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 258          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 259          * @see                 SetValue()
 260          */
 261         virtual const Object* GetValue(const Object& key) const;
 262
 263         /**
 264          * Gets the value associated with the specified @c key.
 265          *
 266          * @since 2.0
 267          *
 268          * @return              The value associated with the key, @n
 269          *                              else @c null if an exception occurs
 270          * @param[in]   key             The key to locate
 271          * @exception   E_SUCCESS                       The method is successful.
 272          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 273          *                                                                      the comparer has failed to compare the keys.
 274          * @exception   E_OBJ_NOT_FOUND         The specified @c key is not found in the map.
 275          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 276          * @see                 SetValue()
 277          */
 278         virtual Object* GetValue(const Object& key);
 279
 280         /**
 281          * Gets a list of all the keys in a map.
 282          *
 283          * @since 2.0
 284          *
 285          * @return              A pointer to an IList object containing all the keys in the map, @n
 286          *                              else @c null if an exception occurs
 287          * @remarks             The order of the keys is the same as the corresponding values in the IList interface returned by the GetValuesN() method.
 288          *              The IList stores just the pointers to the elements in the map, not the elements themselves.
 289          *                              The specific error code can be accessed using the GetLastResult() method.
 290          * @see                 GetValuesN()
 291          */
 292         virtual IList* GetKeysN(void) const;
 293
 294         /**
 295          * Gets all the values in the map.
 296          *
 297          * @since 2.0
 298          *
 299          * @return              A pointer to an IList object containing all the values in the map, @n
 300          *                              else @c null if an exception occurs
 301          * @remarks             The IList stores just the pointers to the elements in the map, not the elements themselves.
 302          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 303          * @see                 GetKeysN()
 304          */
 305         virtual IList* GetValuesN(void) const;
 306
 307         /**
 308          * Removes the values associated with the specified @c key.
 309          *
 310          * @since 2.0
 311          *
 312          * @return              An error code
 313          * @param[in]   key The key to remove
 314          * @exception   E_SUCCESS                       The method is successful.
 315          * @exception   E_INVALID_ARG           The specified input parameter is invalid, or
 316          *                                                                      the comparer has failed to compare keys.
 317          * @exception   E_OBJ_NOT_FOUND The specified @c key is not found in the map.
 318          * @see                 Add()
 319          */
 320         virtual result Remove(const Object& key);
 321
 322         /**
 323          * Removes all the object pointers in the collection. @n
 324          * The %RemoveAll() method can be called before deleting a collection.
 325          *
 326          * @since 2.0
 327          */
 328         virtual void RemoveAll(void);
 329
 330         /**
 331          * Sets the value associated with the specified @c key by allocating it a new value.
 332          *
 333          * @since 2.0
 334          *
 335          * @return              An error code
 336          * @param[in]   key     The key whose value is to replace
 337          * @param[in]   pValue  The pointer to new value to replace
 338          * @exception   E_SUCCESS                       The method is successful.
 339          * @exception   E_INVALID_ARG           A specified input parameter is invalid, or
 340          *                                                                      the comparer has failed to compare keys.
 341          * @exception   E_OBJ_NOT_FOUND The specified @c key is not found in the map.
 342          * @remarks             To add a new key-value pair, use the Add() method.
 343          * @see                 Add()
 344          * @see                 GetValue()
 345          */
 346         virtual result SetValue(const Object& key, Object* pValue);
 347
 348         /**
 349          * Gets the number of pairs currently stored in the map.
 350          *
 351          * @since 2.0
 352          *
 353          * @return              The pairs stored in the map
 354          */
 355         virtual int GetCount(void) const;
 356
 357         /**
 358          * Checks whether the map contains the specified @c key.
 359          *
 360          * @since 2.0
 361          *
 362          * @return              @c true if the map contains the specified @c key, @n
 363          *                              else @c false
 364          * @param[in]   key     The key to locate
 365          * @exception   E_SUCCESS               The method is successful.
 366          * @exception   E_INVALID_ARG   The specified input parameter is invalid, or
 367          *                                                              the comparer has failed to compare the keys.
 368          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 369          * @see                 ContainsValue()
 370          */
 371         virtual bool ContainsKey(const Object& key) const;
 372
 373         /**
 374          * Checks whether the map contains the specified @c value.
 375          *
 376          * @since 2.0
 377          *
 378          * @return              @c true if the map contains the specified @c value, @n
 379          *                              else @c false
 380          * @param[in]   value   The value to locate
 381          *
 382          * @see                 ContainsKey()
 383          */
 384         virtual bool ContainsValue(const Object& value) const;
 385
 386         /**
 387          * Compares two instances of the %HashMap class.
 388          *
 389          * @since 2.0
 390          *
 391          * @return              @c true if the two instances match, @n
 392          *                              else @c false
 393          * @param[in]   obj The object to compare with the current instance
 394          * @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.
 395          */
 396         virtual bool Equals(const Object& obj) const;
 397
 398         /**
 399          * Gets the hash value of the current instance.
 400          *
 401          * @since 2.0
 402          *
 403          * @return      The hash value of the current instance
 404          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
 405          *                      the used hash function must generate a random distribution for all inputs.
 406          */
 407         virtual int GetHashCode(void) const;
 408
 409         /**
 410          * Gets the element deleter of the collection.
 411          *
 412          * @since 2.0
 413          *
 414          * @return              A function pointer to the existing element deleter
 415          */
 416         virtual DeleterFunctionType GetDeleter(void) const;
 417
 418 private:
 419         /**
 420          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
 421          *
 422          * @param[in]   map             The instance of the %HashMap class to copy from
 423          */
 424         HashMap(const HashMap& map);
 425
 426         /**
 427          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
 428          *
 429          * @param[in]   map             An instance of %HashMap
 430          */
 431         HashMap& operator =(const HashMap& map);
 432
 433         /**
 434          * Copies all the pairs from the specified @c map to this map
 435          *
 436          * @return              An error code
 437          * @param[in]   map The map to copy
 438          * @exception   E_SUCCESS                       The method is successful.
 439          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation. @n
 440          *                                                                      The @c map is modified during the operation of this method.
 441          */
 442         result AddAll(const IMap& map);
 443
 444         /**
 445          * Gets the hash value for the specified object.
 446          *
 447          * @return              The hash value for the specified object
 448          * @param[in]   obj
 449          */
 450         int Hash(const Object& obj) const;
 451
 452         /**
 453          * Rehashes the content of a map to a new array with a greater capacity.
 454          *
 455          * @return              An error code
 456          * @param[in[   newCapacity     The new capacity @n
 457          *                                                      It must be a power of two and must be greater than the current capacity.
 458          * @exception   E_SUCCESS                       The method is successful.
 459          * @remarks     This method is called automatically when the number of keys in a map reaches its threshold.
 460          */
 461         result Resize(int newCapacity);
 462
 463         /**
 464          *  Clears all key-value pairs in a map.
 465          */
 466         void Reset(void);
 467
 468         /**
 469          * Sets the element deleter of the collection.
 470          *
 471          * @since 2.0
 472          *
 473          * @param[in]   deleter A function pointer to the element deleter to set
 474          */
 475         virtual void SetDeleter(DeleterFunctionType deleter);
 476
 477         _HashMapEntry** __pTable;
 478         int __count;
 479         int __capacity;
 480         float __loadFactor;
 481         int __threshold;
 482         IHashCodeProvider* __pProvider;
 483         IComparer* __pComparer;
 484         bool __needToRemoveProviderComparer;
 485         int __modCount;
 486         DeleterFunctionType __deleter;
 487         static const int DEFAULT_CAPACITY = 16;
 488         static const float DEFAULT_LOAD_FACTOR;
 489
 490         friend class _HashMapEnumerator;
 491         friend class _HashMapImpl;
 492         class _HashMapImpl* __pHashMapImpl;
 493
 494 }; // HashMap
 495
 496 }}} // Tizen::Base::Collection
 497
 498 #endif //_FBASE_COL_HASH_MAP_H_