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