dali/internal/common/indexed-integer-map.h

   1 #ifndef DALI_INDEXED_INTEGER_MAP_H
   2 #define DALI_INDEXED_INTEGER_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/indexed-map-base.h>
  22
  23 namespace Dali
  24 {
  25 namespace Internal
  26 {
  27 /**
  28  * @brief Specific key-element container which can access by index when key is std::uint32_t.
  29  * Register element by key. and Get element by key or index.
  30  *
  31  * Register operation return false when already same key registered.
  32  * Get operation return iterator of this container.
  33  *
  34  * This container hold integer keys in increase order, and binary search.
  35  * This system have panalty when insert / delete. and have benefit when search.
  36  *
  37  * @note : Current IndexedIntegerMap allow only for single element per key.
  38  * And also, did not allow to Unregister operation.
  39  *
  40  * @note Time complexity :
  41  * Register() : O(Number of data)
  42  * Get() : O(log(Number of data))
  43  *
  44  * @tparam ElementType The type of the data that the container holds
  45  */
  46 template<typename ElementType>
  47 class IndexedIntegerMap : public IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>
  48 {
  49 public:
  50   using iterator       = typename IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>::iterator;
  51   using const_iterator = typename IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>::const_iterator;
  52
  53 public: // override
  54   /**
  55    * @brief Constructor.
  56    */
  57   IndexedIntegerMap()
  58   : IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>()
  59   {
  60   }
  61
  62   /**
  63    * @copydoc IndexedMapBase::Clear()
  64    */
  65   void Clear() override
  66   {
  67     mKeyElementPool.clear();
  68     mKeyIndexList.clear();
  69   }
  70
  71 public: // Main API
  72   /**
  73    * @brief Register element by the integer key.
  74    *
  75    * @param[in] key The integer key that this container will hold. Duplicated key doesn't allow.
  76    * @param[in] element The element pairwise with key.
  77    * @return True if Register success. Otherwise, return false.
  78    */
  79   bool Register(const std::uint32_t& key, const ElementType& element) override
  80   {
  81     // Find key with binary search.
  82     // We can do binary search cause mKeyIndexList is sorted.
  83     const auto& iter = std::lower_bound(mKeyIndexList.cbegin(), mKeyIndexList.cend(), std::pair<std::uint32_t, std::uint32_t>(key, 0u));
  84
  85     if(iter == mKeyIndexList.cend() || iter->first != key)
  86     {
  87       // Emplace new element back.
  88       std::uint32_t newElementIndex = mKeyElementPool.size();
  89       mKeyElementPool.emplace_back(key, element);
  90
  91       // Add new index into mKeyIndexList list.
  92       mKeyIndexList.insert(iter, std::pair<std::uint32_t, std::uint32_t>(key, newElementIndex));
  93
  94       // Append element as child
  95       return true;
  96     }
  97     else
  98     {
  99       // Else, duplicated key!
 100       return false;
 101     }
 102   }
 103
 104   /**
 105    * @brief Register moved element by the integer key.
 106    *
 107    * @param[in] key The integer key that this container will hold. Duplicated key doesn't allow.
 108    * @param[in] element The element pairwise with key.
 109    * @return True if Register success. Otherwise, return false.
 110    */
 111   bool Register(const std::uint32_t& key, ElementType&& element) override
 112   {
 113     // Find key with binary search.
 114     // We can do binary search cause mKeyIndexList is sorted.
 115     const auto& iter = std::lower_bound(mKeyIndexList.cbegin(), mKeyIndexList.cend(), std::pair<std::uint32_t, std::uint32_t>(key, 0u));
 116
 117     if(iter == mKeyIndexList.cend() || iter->first != key)
 118     {
 119       // Emplace new element back.
 120       std::uint32_t newElementIndex = mKeyElementPool.size();
 121       mKeyElementPool.emplace_back(key, std::move(element));
 122
 123       // Add new index into mKeyIndexList list.
 124       mKeyIndexList.insert(iter, std::pair<std::uint32_t, std::uint32_t>(key, newElementIndex));
 125
 126       // Append element as child
 127       return true;
 128     }
 129     else
 130     {
 131       // Else, duplicated key!
 132       return false;
 133     }
 134   }
 135
 136   /**
 137    * @brief Get element by the integer key.
 138    *
 139    * @param[in] key The integer key that this container will hold.
 140    * @return If exist, iterator of container. Otherwise, return End().
 141    */
 142   iterator Get(const std::uint32_t& key) override
 143   {
 144     // Find key with binary search.
 145     // We can do binary search cause mKeyIndexList is sorted.
 146     const auto& iter = std::lower_bound(mKeyIndexList.cbegin(), mKeyIndexList.cend(), std::pair<std::uint32_t, std::uint32_t>(key, 0u));
 147
 148     if(iter == mKeyIndexList.cend() || iter->first != key)
 149     {
 150       // Key doesn't exist!
 151       return this->End();
 152     }
 153
 154     // We found it!
 155     // iter->second will be the index of elements.
 156     return this->Begin() + (iter->second);
 157   }
 158
 159   /**
 160    * @brief Get element by the integer key.
 161    *
 162    * @param[in] key The integer key that this container will hold.
 163    * @return If exist, iterator of container. Otherwise, return End().
 164    */
 165   const_iterator Get(const std::uint32_t& key) const override
 166   {
 167     // Find key with binary search.
 168     // We can do binary search cause mKeyIndexList is sorted.
 169     const auto& iter = std::lower_bound(mKeyIndexList.cbegin(), mKeyIndexList.cend(), std::pair<std::uint32_t, std::uint32_t>(key, 0u));
 170
 171     if(iter == mKeyIndexList.cend() || iter->first != key)
 172     {
 173       // Key doesn't exist!
 174       return this->End();
 175     }
 176
 177     // We found it!
 178     // iter->second will be the index of elements.
 179     return this->Begin() + (iter->second);
 180   }
 181
 182 private:
 183   /**
 184    * @brief Convert from Key to index of container.
 185    *
 186    * @note mKeyIndexList's key should be increase order.
 187    */
 188   std::vector<std::pair<std::uint32_t, std::uint32_t>> mKeyIndexList{};
 189
 190 protected:
 191   /**
 192    * @brief Member values from base class.
 193    */
 194   using IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>::mKeyElementPool;
 195 };
 196
 197 } // namespace Internal
 198
 199 } // namespace Dali
 200
 201 #endif //  DALI_INDEXED_INTEGER_MAP_H