ezEngine  Milestone 9
Set.h
1 #pragma once
2 
3 #include <Foundation/Containers/Deque.h>
4 
11 template <typename KeyType, typename Comparer>
12 class ezSetBase
13 {
14 private:
15  struct Node;
16 
18  struct NilNode
19  {
20  NilNode();
21 
22  ezUInt16 m_uiLevel;
23  Node* m_pParent;
24  Node* m_pLink[2];
25  };
26 
28  struct Node : public NilNode
29  {
30  KeyType m_Key;
31  };
32 
33 public:
35  struct Iterator
36  {
37  typedef std::forward_iterator_tag iterator_category;
38  typedef Iterator value_type;
39  typedef ptrdiff_t difference_type;
40  typedef Iterator* pointer;
41  typedef Iterator& reference;
42 
43  EZ_DECLARE_POD_TYPE();
44 
46  EZ_ALWAYS_INLINE Iterator() : m_pElement(nullptr) {} // [tested]
47 
49  EZ_ALWAYS_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
50 
52  EZ_ALWAYS_INLINE bool operator==(const typename ezSetBase<KeyType, Comparer>::Iterator& it2) const { return (m_pElement == it2.m_pElement); }
53 
55  EZ_ALWAYS_INLINE bool operator!=(const typename ezSetBase<KeyType, Comparer>::Iterator& it2) const { return (m_pElement != it2.m_pElement); }
56 
58  EZ_FORCE_INLINE const KeyType& Key() const
59  {
60  EZ_ASSERT_DEBUG(IsValid(), "Cannot access the 'key' of an invalid iterator.");
61  return m_pElement->m_Key;
62  } // [tested]
63 
65  EZ_ALWAYS_INLINE const KeyType& operator*() { return Key(); }
66 
68  void Next(); // [tested]
69 
71  void Prev(); // [tested]
72 
74  EZ_ALWAYS_INLINE void operator++() { Next(); } // [tested]
75 
77  EZ_ALWAYS_INLINE void operator--() { Prev(); } // [tested]
78 
79  protected:
80  friend class ezSetBase<KeyType, Comparer>;
81 
82  EZ_ALWAYS_INLINE explicit Iterator(Node* pInit) : m_pElement(pInit) {}
83 
84  Node* m_pElement;
85  };
86 
87 protected:
89  ezSetBase(const Comparer& comparer, ezAllocatorBase* pAllocator); // [tested]
90 
92  ezSetBase(const ezSetBase<KeyType, Comparer>& cc, ezAllocatorBase* pAllocator); // [tested]
93 
95  ~ezSetBase(); // [tested]
96 
98  void operator=(const ezSetBase<KeyType, Comparer>& rhs); // [tested]
99 
100 public:
102  bool IsEmpty() const; // [tested]
103 
105  ezUInt32 GetCount() const; // [tested]
106 
108  void Clear(); // [tested]
109 
111  Iterator GetIterator() const; // [tested]
112 
114  Iterator GetLastIterator() const; // [tested]
115 
117  template <typename CompatibleKeyType>
118  Iterator Insert(CompatibleKeyType&& key); // [tested]
119 
121  template <typename CompatibleKeyType>
122  bool Remove(const CompatibleKeyType& key); // [tested]
123 
125  Iterator Remove(const Iterator& pos); // [tested]
126 
128  template <typename CompatibleKeyType>
129  Iterator Find(const CompatibleKeyType& key) const; // [tested]
130 
132  template <typename CompatibleKeyType>
133  bool Contains(const CompatibleKeyType& key) const; // [tested]
134 
136  bool ContainsSet(const ezSetBase<KeyType, Comparer>& operand) const; // [tested]
137 
139  template <typename CompatibleKeyType>
140  Iterator LowerBound(const CompatibleKeyType& key) const; // [tested]
141 
143  template <typename CompatibleKeyType>
144  Iterator UpperBound(const CompatibleKeyType& key) const; // [tested]
145 
147  void Union(const ezSetBase<KeyType, Comparer>& operand);
148 
150  void Difference(const ezSetBase<KeyType, Comparer>& operand);
151 
153  void Intersection(const ezSetBase<KeyType, Comparer>& operand);
154 
156  ezAllocatorBase* GetAllocator() const { return m_Elements.GetAllocator(); }
157 
159  bool operator==(const ezSetBase<KeyType, Comparer>& rhs) const; // [tested]
160 
162  bool operator!=(const ezSetBase<KeyType, Comparer>& rhs) const; // [tested]
163 
165  ezUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
166 
168  void Swap(ezSetBase<KeyType, Comparer>& other); // [tested]
169 
170 private:
171  template <typename CompatibleKeyType>
172  Node* Internal_Find(const CompatibleKeyType& key) const;
173  template <typename CompatibleKeyType>
174  Node* Internal_LowerBound(const CompatibleKeyType& key) const;
175  template <typename CompatibleKeyType>
176  Node* Internal_UpperBound(const CompatibleKeyType& key) const;
177 
178 private:
179  void Constructor();
180 
182  template <typename CompatibleKeyType>
183  Node* AcquireNode(CompatibleKeyType&& key, int m_uiLevel, Node* pParent);
184 
186  void ReleaseNode(Node* pNode);
187 
191  Node* SkewNode(Node* root);
192  Node* SplitNode(Node* root);
193 
194  template <typename CompatibleKeyType>
195  Node* Insert(Node* root, CompatibleKeyType&& key, Node*& pInsertedNode);
196  template <typename CompatibleKeyType>
197  Node* Remove(Node* root, const CompatibleKeyType& key, bool& bRemoved);
198 
200  Node* GetLeftMost() const;
201 
203  Node* GetRightMost() const;
204 
206  void SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew);
207 
209  Node* m_pRoot;
210 
212  NilNode m_NilNode;
213 
215  ezUInt32 m_uiCount;
216 
219 
221  Node* m_pFreeElementStack;
222 
224  Comparer m_Comparer;
225 };
226 
228 template <typename KeyType, typename Comparer = ezCompareHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
229 class ezSet : public ezSetBase<KeyType, Comparer>
230 {
231 public:
232  ezSet();
233  ezSet(const Comparer& comparer, ezAllocatorBase* pAllocator);
234 
236  ezSet(const ezSetBase<KeyType, Comparer>& other);
237 
238  void operator=(const ezSet<KeyType, Comparer, AllocatorWrapper>& rhs);
239  void operator=(const ezSetBase<KeyType, Comparer>& rhs);
240 };
241 
242 
243 template <typename KeyType, typename Comparer>
244 typename ezSetBase<KeyType, Comparer>::Iterator begin(ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
245 
246 template <typename KeyType, typename Comparer>
247 typename ezSetBase<KeyType, Comparer>::Iterator begin(const ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
248 
249 template <typename KeyType, typename Comparer>
250 typename ezSetBase<KeyType, Comparer>::Iterator cbegin(const ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
251 
252 template <typename KeyType, typename Comparer>
254 
255 template <typename KeyType, typename Comparer>
257 
258 template <typename KeyType, typename Comparer>
260 
261 
262 #include <Foundation/Containers/Implementation/Set_inl.h>
263 
Iterator LowerBound(const CompatibleKeyType &key) const
Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid ...
EZ_ALWAYS_INLINE bool operator!=(const typename ezSetBase< KeyType, Comparer >::Iterator &it2) const
Checks whether the two iterators point to the same element.
Definition: Set.h:55
bool operator!=(const ezSetBase< KeyType, Comparer > &rhs) const
Comparison operator.
Definition: Set_inl.h:726
void Next()
Advances the iterator to the next element in the set. The iterator will not be valid anymore...
Definition: Set_inl.h:8
Base class for all memory allocators.
Definition: AllocatorBase.h:21
Iterator GetLastIterator() const
Returns a constant Iterator to the very last element. For reverse traversal.
Definition: Set_inl.h:206
Iterator UpperBound(const CompatibleKeyType &key) const
Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid i...
#define EZ_ASSERT_DEBUG(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:88
bool Remove(const CompatibleKeyType &key)
Erases the element with the given key, if it exists. O(log n) operation.
Definition: Set_inl.h:399
Definition: Set.h:229
ezUInt32 GetCount() const
Returns the number of elements currently stored in the set. O(1) operation.
Definition: Set_inl.h:193
EZ_ALWAYS_INLINE void operator--()
Shorthand for &#39;Prev&#39;.
Definition: Set.h:77
Iterator GetIterator() const
Returns a constant Iterator to the very first element.
Definition: Set_inl.h:200
void Intersection(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the intersection of itself and the operand.
Definition: Set_inl.h:373
bool IsEmpty() const
Returns whether there are no elements in the set. O(1) operation.
Definition: Set_inl.h:187
bool Contains(const CompatibleKeyType &key) const
Checks whether the given key is in the container.
EZ_ALWAYS_INLINE Iterator()
Constructs an invalid iterator.
Definition: Set.h:46
Base class for all iterators.
Definition: Set.h:35
Iterator Insert(CompatibleKeyType &&key)
Inserts the key into the tree and returns an Iterator to it. O(log n) operation.
Definition: Set_inl.h:386
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: Deque_inl.h:928
void Union(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the union of itself and the operand.
Definition: Set_inl.h:355
void operator=(const ezSetBase< KeyType, Comparer > &rhs)
Copies all keys from the given set into this one.
Definition: Set_inl.h:159
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: Deque.h:160
ezSetBase(const Comparer &comparer, ezAllocatorBase *pAllocator)
Initializes the set to be empty.
Definition: Set_inl.h:139
void Swap(ezSetBase< KeyType, Comparer > &other)
Swaps this map with the other one.
Definition: Set_inl.h:766
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: Set.h:156
EZ_ALWAYS_INLINE const KeyType & operator*()
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: Set.h:65
bool operator==(const ezSetBase< KeyType, Comparer > &rhs) const
Comparison operator.
Definition: Set_inl.h:705
A set container that only stores whether an element resides in it or not. Similar to STL::set...
Definition: Set.h:12
void Difference(const ezSetBase< KeyType, Comparer > &operand)
Makes this set the difference of itself and the operand, i.e. subtracts operand.
Definition: Set_inl.h:364
EZ_ALWAYS_INLINE bool operator==(const typename ezSetBase< KeyType, Comparer >::Iterator &it2) const
Checks whether the two iterators point to the same element.
Definition: Set.h:52
~ezSetBase()
Destroys all elements in the set.
Definition: Set_inl.h:153
void Prev()
Advances the iterator to the previous element in the set. The iterator will not be valid anymore...
Definition: Set_inl.h:62
Iterator Find(const CompatibleKeyType &key) const
Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found...
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: Set.h:165
EZ_ALWAYS_INLINE void operator++()
Shorthand for &#39;Next&#39;.
Definition: Set.h:74
void Clear()
Destroys all elements in the set and resets its size to zero.
Definition: Set_inl.h:168
EZ_FORCE_INLINE const KeyType & Key() const
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: Set.h:58
bool ContainsSet(const ezSetBase< KeyType, Comparer > &operand) const
Checks whether the given key is in the container.
Definition: Set_inl.h:277
EZ_ALWAYS_INLINE bool IsValid() const
Checks whether this iterator points to a valid element.
Definition: Set.h:49