1 #ifndef DALI_INDEXED_CONST_STRING_MAP_H
2 #define DALI_INDEXED_CONST_STRING_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/const-string.h>
22 #include <dali/internal/common/indexed-map-base.h>
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.
32 * Register operation return false when already same key registered.
33 * Get operation return iterator of this container.
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)
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.
41 * @note : Current IndexedConstStringMap allow only for single element per key.
42 * And also, did not allow to Unregister operation.
44 * @note Time complexity :
45 * Register() : O(ConstString converting time + Number of data)
46 * Get() : O(ConstString converting time + log(Number of data))
48 * @tparam ElementType The type of the data that the container holds
50 template<typename ElementType>
51 class IndexedConstStringMap : public IndexedMapBase<ConstString, ConstString, ElementType>
54 using iterator = typename IndexedMapBase<ConstString, ConstString, ElementType>::iterator;
55 using const_iterator = typename IndexedMapBase<ConstString, ConstString, ElementType>::const_iterator;
61 IndexedConstStringMap()
62 : IndexedMapBase<ConstString, ConstString, ElementType>()
67 * @copydoc IndexedMapBase::Clear()
71 mKeyElementPool.clear();
72 mCharPtrIndexList.clear();
77 * @brief Register element by the ConstString key.
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.
83 bool Register(const ConstString& key, const ElementType& element) override
85 // Let's make key as compareable type.
86 const char* comparableKey = key.GetCString();
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));
92 if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
94 // Emplace new element back.
95 std::uint32_t newElementIndex = mKeyElementPool.size();
96 mKeyElementPool.emplace_back(key, element);
98 // Add new index into mCharPtrIndexList.
99 mCharPtrIndexList.insert(iter, std::pair<const char*, std::uint32_t>(comparableKey, newElementIndex));
101 // Append element as child
106 // Else, duplicated key!
112 * @brief Register moved element by the ConstString key.
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.
118 bool Register(const ConstString& key, ElementType&& element) override
120 // Let's make key as compareable type.
121 const char* comparableKey = key.GetCString();
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));
127 if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
129 // Emplace new element back.
130 std::uint32_t newElementIndex = mKeyElementPool.size();
131 mKeyElementPool.emplace_back(key, std::move(element));
133 // Add new index into mCharPtrIndexList.
134 mCharPtrIndexList.insert(iter, std::pair<const char*, std::uint32_t>(comparableKey, newElementIndex));
136 // Append element as child
141 // Else, duplicated key!
147 * @brief Get element by the ConstString key.
149 * @param[in] key The ConstString key that this container will hold.
150 * @return If exist, iterator of container. Otherwise, return End().
152 iterator Get(const ConstString& key) override
154 // Let's make key as compareable type.
155 const char* comparableKey = key.GetCString();
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));
161 if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
163 // Key doesn't exist!
168 // iter->second will be the index of elements.
169 return this->Begin() + (iter->second);
173 * @brief Get element by the ConstString key.
175 * @param[in] key The ConstString key that this container will hold.
176 * @return If exist, iterator of container. Otherwise, return End().
178 const_iterator Get(const ConstString& key) const override
180 // Let's make key as compareable type.
181 const char* comparableKey = key.GetCString();
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));
187 if(iter == mCharPtrIndexList.cend() || iter->first != comparableKey)
189 // Key doesn't exist!
194 // iter->second will be the index of elements.
195 return this->Begin() + (iter->second);
200 * @brief Convert from char* to index of container.
202 * @note mCharPtrIndexList's key should be increase order compare as std::size_t.
204 std::vector<std::pair<const char*, std::uint32_t>> mCharPtrIndexList{};
208 * @brief Member values from base class.
210 using IndexedMapBase<ConstString, ConstString, ElementType>::mKeyElementPool;
213 } // namespace Internal
217 #endif // DALI_INDEXED_CONST_STRING_MAP_H