dali/internal/common/indexed-const-string-map.h

   1 #ifndef DALI_INDEXED_CONST_STRING_MAP_H
   2 #define DALI_INDEXED_CONST_STRING_MAP_H
   3
   4 /*
   5  * Copyright (c) 2022 Samsung Electronics Co., Ltd.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 // INTERNAL INCLUDES
  21 #include <dali/internal/common/const-string.h>
  22 #include <dali/internal/common/indexed-map-base.h>
  23
  24 namespace Dali
  25 {
  26 namespace Internal
  27 {
  28 /**
  29  * @brief Specific key-element container which can access by index  when key is Dali::Internal::ConstString.
  30  * Register element by key. and Get element by key or index.
  31  *
  32  * Register operation return false when already same key registered.
  33  * Get operation return iterator of this container.
  34  *
  35  * Actually, ConstString type did comparision-and-compare with known strings internally.
  36  * That mean, we can assume that ConstString already hashed as const char* type. (== std::size_t)
  37  *
  38  * This container just hold const char* type keys in increase order, and binary search.
  39  * This system have panalty when insert / delete. and have benefit when search.
  40  *
  41  * @note : Current IndexedConstStringMap allow only for single element per key.
  42  * And also, did not allow to Unregister operation.
  43  *
  44  * @note Time complexity :
  45  * Register() : O(ConstString converting time + Number of data)
  46  * Get() : O(ConstString converting time + log(Number of data))
  47  *
  48  * @tparam ElementType The type of the data that the container holds
  49  */
  50 template<typename ElementType>
  51 class IndexedConstStringMap : public IndexedMapBase<ConstString, ConstString, ElementType>
  52 {
  53 public:
  54   using iterator       = typename IndexedMapBase<ConstString, ConstString, ElementType>::iterator;
  55   using const_iterator = typename IndexedMapBase<ConstString, ConstString, ElementType>::const_iterator;
  56
  57 public: // override
  58   /**
  59    * @brief Constructor.
  60    */
  61   IndexedConstStringMap()
  62   : IndexedMapBase<ConstString, ConstString, ElementType>()
  63   {
  64   }
  65
  66   /**
  67    * @copydoc IndexedMapBase::Clear()
  68    */
  69   void Clear() override
  70   {
  71     mKeyElementPool.clear();
  72     mCharPtrIndexList.clear();
  73   }
  74
  75 public: // Main API
  76   /**
  77    * @brief Register element by the ConstString key.
  78    *
  79    * @param[in] key The ConstString key that this container will hold. Duplicated key doesn't allow.
  80    * @param[in] element The element pairwise with key.
  81    * @return True if Register success. Otherwise, return false.
  82    */
  83   bool Register(const ConstString& key, const ElementType& element) override
  84   {
  85     // Let's make key as compareable type.
  86     const char* comparableKey = key.GetCString();
  87
  88     // Find key with binary search.
  89     // We can do binary search cause mCharPtrIndexList is sorted.
  90     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
  91
  92     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
  93     {
  94       // Emplace new element back.
  95       std::uint32_t newElementIndex = mKeyElementPool.size();
  96       mKeyElementPool.emplace_back(key, element);
  97
  98       // Add new index into mCharPtrIndexList.
  99       mCharPtrIndexList.insert(iter, std::pair<const char*, std::uint32_t>(comparableKey, newElementIndex));
 100
 101       // Append element as child
 102       return true;
 103     }
 104     else
 105     {
 106       // Else, duplicated key!
 107       return false;
 108     }
 109   }
 110
 111   /**
 112    * @brief Register moved element by the ConstString key.
 113    *
 114    * @param[in] key The ConstString key that this container will hold. Duplicated key doesn't allow.
 115    * @param[in] element The element pairwise with key.
 116    * @return True if Register success. Otherwise, return false.
 117    */
 118   bool Register(const ConstString& key, ElementType&& element) override
 119   {
 120     // Let's make key as compareable type.
 121     const char* comparableKey = key.GetCString();
 122
 123     // Find key with binary search.
 124     // We can do binary search cause mCharPtrIndexList is sorted.
 125     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
 126
 127     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
 128     {
 129       // Emplace new element back.
 130       std::uint32_t newElementIndex = mKeyElementPool.size();
 131       mKeyElementPool.emplace_back(key, std::move(element));
 132
 133       // Add new index into mCharPtrIndexList.
 134       mCharPtrIndexList.insert(iter, std::pair<const char*, std::uint32_t>(comparableKey, newElementIndex));
 135
 136       // Append element as child
 137       return true;
 138     }
 139     else
 140     {
 141       // Else, duplicated key!
 142       return false;
 143     }
 144   }
 145
 146   /**
 147    * @brief Get element by the ConstString key.
 148    *
 149    * @param[in] key The ConstString key that this container will hold.
 150    * @return If exist, iterator of container. Otherwise, return End().
 151    */
 152   iterator Get(const ConstString& key) override
 153   {
 154     // Let's make key as compareable type.
 155     const char* comparableKey = key.GetCString();
 156
 157     // Find key with binary search.
 158     // We can do binary search cause mCharPtrIndexList is sorted.
 159     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
 160
 161     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
 162     {
 163       // Key doesn't exist!
 164       return this->End();
 165     }
 166
 167     // We found it!
 168     // iter->second will be the index of elements.
 169     return this->Begin() + (iter->second);
 170   }
 171
 172   /**
 173    * @brief Get element by the ConstString key.
 174    *
 175    * @param[in] key The ConstString key that this container will hold.
 176    * @return If exist, iterator of container. Otherwise, return End().
 177    */
 178   const_iterator Get(const ConstString& key) const override
 179   {
 180     // Let's make key as compareable type.
 181     const char* comparableKey = key.GetCString();
 182
 183     // Find key with binary search.
 184     // We can do binary search cause mCharPtrIndexList is sorted.
 185     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
 186
 187     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
 188     {
 189       // Key doesn't exist!
 190       return this->End();
 191     }
 192
 193     // We found it!
 194     // iter->second will be the index of elements.
 195     return this->Begin() + (iter->second);
 196   }
 197
 198 private:
 199   /**
 200    * @brief Convert from char* to index of container.
 201    *
 202    * @note mCharPtrIndexList's key should be increase order compare as std::size_t.
 203    */
 204   std::vector<std::pair<const char*, std::uint32_t>> mCharPtrIndexList{};
 205
 206 protected:
 207   /**
 208    * @brief Member values from base class.
 209    */
 210   using IndexedMapBase<ConstString, ConstString, ElementType>::mKeyElementPool;
 211 };
 212
 213 } // namespace Internal
 214
 215 } // namespace Dali
 216
 217 #endif //  DALI_INDEXED_CONST_STRING_MAP_H