1 #ifndef DALI_INTERNAL_ORDERED_SET_H
2 #define DALI_INTERNAL_ORDERED_SET_H
5 * Copyright (c) 2023 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.
22 #include <unordered_map>
25 #include <dali/public-api/common/dali-common.h>
26 #include <dali/public-api/common/list-wrapper.h>
33 * @brief Container of data which has strong point to Find & Erase.
34 * It will be useful when we need to iterate the order of data insertion.
35 * and need to check whether some object is exist or not very fast.
36 * @note Since the data's memory is not continuos, iteration is slower than normal vector contianer.
38 * @tparam T The type of class
39 * @tparam owned True if data is owned, So we will automatcally release the memory
40 * False if data is not owned by this set. Default as true.
41 * @tparam Hash Custom hash function of const T* type for MapContainer.
42 * Note that if two const T* return true at KeyEqual, Hash should return same value.
43 * Default as std::hash<const T*>
44 * @tparam KeyEqual Custom equal function of const T* type for MapContainer.
45 * Return true if two const T* type is equal. Default as std::equal_to<const T*>
47 template<class T, bool owned = true, class Hash = std::hash<const T*>, class KeyEqual = std::equal_to<const T*>>
51 // Real data owned container.
52 using ListContainer = typename std::list<T*>;
53 using Iterator = typename ListContainer::iterator;
54 using ConstIterator = typename ListContainer::const_iterator;
56 // Find helper map container.
57 using MapContainer = typename std::unordered_map<const T*, Iterator, Hash, KeyEqual>;
59 using SizeType = std::size_t;
62 * @brief Construct a new OrderedSet object
64 OrderedSet() = default;
67 * @brief Move construct
69 OrderedSet(OrderedSet&& rhs) noexcept
70 : mMap(std::move(rhs.mMap)),
71 mList(std::move(rhs.mList))
81 OrderedSet& operator=(OrderedSet&& rhs) noexcept
84 mMap = std::move(rhs.mMap);
85 mList = std::move(rhs.mList);
98 * @brief Iterator of begin & end
102 return mList.begin();
108 ConstIterator Begin() const
110 return mList.begin();
112 ConstIterator End() const
117 // Support for C++11 Range-based for loop: for( item : container ).
126 ConstIterator begin() const
130 ConstIterator end() const
136 * @brief Get the number of elements.
138 * @return The number of elements that this container owned.
140 SizeType Count() const
146 * @brief Reserves space in the ordered set.
148 * @param[in] count Count of elements to reserve
150 void Reserve(SizeType count)
152 if(mMap.size() < count)
159 * @brief Find and get iterator of object. If not exist, return End().
161 * @param[in] object The object pointer what we want to find.
162 * @return Iterator of object, or End().
164 Iterator Find(T* object)
166 auto mapIter = mMap.find(object);
167 if(mapIter == mMap.end())
171 return mapIter->second;
173 ConstIterator Find(const T* object) const
175 auto mapIter = mMap.find(object);
176 if(mapIter == mMap.end())
180 return mapIter->second;
184 * @brief PushBack and keep ownership of object.
185 * @note Iterator will keep order of PushBack API call.
187 * @param[in] object The object pointer what we want to insert.
189 void PushBack(T* object)
191 DALI_ASSERT_DEBUG(Find(object) == End());
192 auto newIter = mList.insert(mList.end(), object);
193 mMap.insert({object, newIter});
197 * @brief Erase and remove memory of object.
199 * @param[in] object The object pointer what we want to erase.
201 void EraseObject(T* object)
203 // TODO : Should we allow duplicated erase?
204 //DALI_ASSERT_DEBUG(Find(object) != End());
207 void EraseObject(const T* object)
209 // TODO : Should we allow duplicated erase?
210 //DALI_ASSERT_DEBUG(Find(object) != End());
215 * @brief Erase and remove memory of object by iterator.
217 * @param[in] iter The iterator what we want to erase.
219 Iterator Erase(Iterator iter)
221 Iterator ret = mList.end();
222 if(iter != mList.end())
225 auto mapIter = mMap.find(*iter);
226 DALI_ASSERT_DEBUG(mapIter != mMap.end());
229 // Erase owned object.
234 ret = mList.erase(iter);
238 ConstIterator Erase(ConstIterator iter)
240 ConstIterator ret = mList.end();
241 if(iter != mList.end())
244 auto mapIter = mMap.find(*iter);
245 DALI_ASSERT_DEBUG(mapIter != mMap.end());
248 // Erase owned object.
253 ret = mList.erase(iter);
259 * @brief Release and move ownership of object.
260 * This API do not remove memory.
262 * @param[in] iter The iterator what we want to release.
264 T* Release(Iterator iter)
269 auto mapIter = mMap.find(result);
270 DALI_ASSERT_DEBUG(mapIter != mMap.end());
273 // Erase without delete reference
277 T* Release(ConstIterator iter)
279 const T* result = (*iter);
282 auto mapIter = mMap.find(result);
283 DALI_ASSERT_DEBUG(mapIter != mMap.end());
286 // Erase without delete reference
292 * @brief Remove all data and release memory if we owned data.
299 for(auto&& iter : mList)
310 // Delete copy operation.
311 OrderedSet(const OrderedSet&) = delete;
312 OrderedSet& operator=(const OrderedSet&) = delete;
315 MapContainer mMap{}; ///< Helper cache map to find item fast.
316 ListContainer mList{}; ///< Ordered by PushBack API called. Actual ownership will be stored here.
318 } // namespace Internal
322 #endif // DALI_INTERNAL_ORDERED_SET_H