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 Get element by the ConstString key.
 113    *
 114    * @param[in] key The ConstString key that this container will hold.
 115    * @return If exist, iterator of container. Otherwise, return End().
 116    */
 117   iterator Get(const ConstString& key) override
 118   {
 119     // Let's make key as compareable type.
 120     const char* comparableKey = key.GetCString();
 121
 122     // Find key with binary search.
 123     // We can do binary search cause mCharPtrIndexList is sorted.
 124     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
 125
 126     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
 127     {
 128       // Key doesn't exist!
 129       return this->End();
 130     }
 131
 132     // We found it!
 133     // iter->second will be the index of elements.
 134     return this->Begin() + (iter->second);
 135   }
 136
 137   /**
 138    * @brief Get element by the ConstString key.
 139    *
 140    * @param[in] key The ConstString key that this container will hold.
 141    * @return If exist, iterator of container. Otherwise, return End().
 142    */
 143   const_iterator Get(const ConstString& key) const override
 144   {
 145     // Let's make key as compareable type.
 146     const char* comparableKey = key.GetCString();
 147
 148     // Find key with binary search.
 149     // We can do binary search cause mCharPtrIndexList is sorted.
 150     const auto& iter = std::lower_bound(mCharPtrIndexList.cbegin(), mCharPtrIndexList.cend(), std::pair<const char*, std::uint32_t>(comparableKey, 0u));
 151
 152     if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
 153     {
 154       // Key doesn't exist!
 155       return this->End();
 156     }
 157
 158     // We found it!
 159     // iter->second will be the index of elements.
 160     return this->Begin() + (iter->second);
 161   }
 162
 163 private:
 164   /**
 165    * @brief Convert from char* to index of container.
 166    *
 167    * @note mCharPtrIndexList's key should be increase order compare as std::size_t.
 168    */
 169   std::vector<std::pair<const char*, std::uint32_t>> mCharPtrIndexList{};
 170
 171 protected:
 172   /**
 173    * @brief Member values from base class.
 174    */
 175   using IndexedMapBase<ConstString, ConstString, ElementType>::mKeyElementPool;
 176 };
 177
 178 } // namespace Internal
 179
 180 } // namespace Dali
 181
 182 #endif //  DALI_INDEXED_CONST_STRING_MAP_H