1 #ifndef DALI_INDEXED_INTEGER_MAP_H
2 #define DALI_INDEXED_INTEGER_MAP_H
5 * Copyright (c) 2022 Samsung Electronics Co., Ltd.
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <dali/internal/common/indexed-map-base.h>
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.
31 * Register operation return false when already same key registered.
32 * Get operation return iterator of this container.
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.
37 * @note : Current IndexedIntegerMap allow only for single element per key.
38 * And also, did not allow to Unregister operation.
40 * @note Time complexity :
41 * Register() : O(Number of data)
42 * Get() : O(log(Number of data))
44 * @tparam ElementType The type of the data that the container holds
46 template<typename ElementType>
47 class IndexedIntegerMap : public IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>
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;
58 : IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>()
63 * @copydoc IndexedMapBase::Clear()
67 mKeyElementPool.clear();
68 mKeyIndexList.clear();
73 * @brief Register element by the integer key.
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.
79 bool Register(const std::uint32_t& key, const ElementType& element) override
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));
85 if(iter == mKeyIndexList.cend() || iter->first != key)
87 // Emplace new element back.
88 std::uint32_t newElementIndex = mKeyElementPool.size();
89 mKeyElementPool.emplace_back(key, element);
91 // Add new index into mKeyIndexList list.
92 mKeyIndexList.insert(iter, std::pair<std::uint32_t, std::uint32_t>(key, newElementIndex));
94 // Append element as child
99 // Else, duplicated key!
105 * @brief Get element by the integer key.
107 * @param[in] key The integer key that this container will hold.
108 * @return If exist, iterator of container. Otherwise, return End().
110 iterator Get(const std::uint32_t& key) override
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));
116 if(iter == mKeyIndexList.cend() || iter->first != key)
118 // Key doesn't exist!
123 // iter->second will be the index of elements.
124 return this->Begin() + (iter->second);
128 * @brief Get element by the integer key.
130 * @param[in] key The integer key that this container will hold.
131 * @return If exist, iterator of container. Otherwise, return End().
133 const_iterator Get(const std::uint32_t& key) const override
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));
139 if(iter == mKeyIndexList.cend() || iter->first != key)
141 // Key doesn't exist!
146 // iter->second will be the index of elements.
147 return this->Begin() + (iter->second);
152 * @brief Convert from Key to index of container.
154 * @note mKeyIndexList's key should be increase order.
156 std::vector<std::pair<std::uint32_t, std::uint32_t>> mKeyIndexList{};
160 * @brief Member values from base class.
162 using IndexedMapBase<std::uint32_t, std::uint32_t, ElementType>::mKeyElementPool;
165 } // namespace Internal
169 #endif // DALI_INDEXED_INTEGER_MAP_H