ezEngine  Milestone 7
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:
34 
36  struct Iterator
37  {
38  typedef std::forward_iterator_tag iterator_category;
39  typedef Iterator value_type;
40  typedef ptrdiff_t difference_type;
41  typedef Iterator* pointer;
42  typedef Iterator& reference;
43 
44  EZ_DECLARE_POD_TYPE();
45 
47  EZ_FORCE_INLINE Iterator() : m_pElement(nullptr) { } // [tested]
48 
50  EZ_FORCE_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
51 
53  EZ_FORCE_INLINE bool operator==(const typename ezSetBase<KeyType, Comparer>::Iterator& it2) const { return (m_pElement == it2.m_pElement); }
54 
56  EZ_FORCE_INLINE bool operator!=(const typename ezSetBase<KeyType, Comparer>::Iterator& it2) const { return (m_pElement != it2.m_pElement); }
57 
59  EZ_FORCE_INLINE const KeyType& Key () const { EZ_ASSERT_DEV(IsValid(), "Cannot access the 'key' of an invalid iterator."); return m_pElement->m_Key; } // [tested]
60 
62  EZ_FORCE_INLINE const KeyType& operator*() { return Key(); }
63 
65  void Next(); // [tested]
66 
68  void Prev(); // [tested]
69 
71  EZ_FORCE_INLINE void operator++() { Next(); } // [tested]
72 
74  EZ_FORCE_INLINE void operator--() { Prev(); } // [tested]
75 
76  protected:
77  friend class ezSetBase<KeyType, Comparer>;
78 
79  EZ_FORCE_INLINE explicit Iterator(Node* pInit) : m_pElement(pInit) { }
80 
81  Node* m_pElement;
82  };
83 
84 protected:
85 
87  ezSetBase(const Comparer& comparer, ezAllocatorBase* pAllocator); // [tested]
88 
90  ezSetBase(const ezSetBase<KeyType, Comparer>& cc, ezAllocatorBase* pAllocator); // [tested]
91 
93  ~ezSetBase(); // [tested]
94 
96  void operator= (const ezSetBase<KeyType, Comparer>& rhs); // [tested]
97 
98 public:
100  bool IsEmpty() const; // [tested]
101 
103  ezUInt32 GetCount() const; // [tested]
104 
106  void Clear(); // [tested]
107 
109  Iterator GetIterator() const; // [tested]
110 
112  Iterator GetLastIterator() const; // [tested]
113 
115  Iterator Insert(const KeyType& key); // [tested]
116 
118  bool Remove(const KeyType& key); // [tested]
119 
121  Iterator Remove(const Iterator& pos); // [tested]
122 
124  Iterator Find(const KeyType& key) const; // [tested]
125 
127  bool Contains(const KeyType& key) const; // [tested]
128 
130  bool Contains(const ezSetBase<KeyType, Comparer>& operand) const; // [tested]
131 
133  Iterator LowerBound(const KeyType& key) const; // [tested]
134 
136  Iterator UpperBound(const KeyType& key) const; // [tested]
137 
139  void Union(const ezSetBase<KeyType, Comparer>& operand);
140 
142  void Difference(const ezSetBase<KeyType, Comparer>& operand);
143 
145  void Intersection(const ezSetBase<KeyType, Comparer>& operand);
146 
148  ezAllocatorBase* GetAllocator() const { return m_Elements.GetAllocator(); }
149 
151  bool operator==(const ezSetBase<KeyType, Comparer>& rhs) const; // [tested]
152 
154  bool operator!=(const ezSetBase<KeyType, Comparer>& rhs) const; // [tested]
155 
157  ezUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
158 
159 private:
160  Node* Internal_Find(const KeyType& key) const;
161  Node* Internal_LowerBound(const KeyType& key) const;
162  Node* Internal_UpperBound(const KeyType& key) const;
163 
164 private:
165  void Constructor();
166 
168  Node* AcquireNode(const KeyType& key, int m_uiLevel, Node* pParent);
169 
171  void ReleaseNode(Node* pNode);
172 
176  Node* SkewNode(Node* root);
177  Node* SplitNode(Node* root);
178  Node* Insert(Node* root, const KeyType& key, Node*& pInsertedNode);
179  Node* Remove(Node* root, const KeyType& key, bool& bRemoved);
180 
182  Node* GetLeftMost() const;
183 
185  Node* GetRightMost() const;
186 
188  Node* m_pRoot;
189 
191  NilNode m_NilNode;
192 
194  ezUInt32 m_uiCount;
195 
198 
201 
203  Comparer m_Comparer;
204 };
205 
207 template <typename KeyType, typename Comparer = ezCompareHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
208 class ezSet : public ezSetBase<KeyType, Comparer>
209 {
210 public:
211  ezSet();
212  ezSet(const Comparer& comparer, ezAllocatorBase* pAllocator);
213 
215  ezSet(const ezSetBase<KeyType, Comparer>& other);
216 
217  void operator=(const ezSet<KeyType, Comparer, AllocatorWrapper>& rhs);
218  void operator=(const ezSetBase<KeyType, Comparer>& rhs);
219 };
220 
221 
222 template <typename KeyType, typename Comparer>
223 typename ezSetBase<KeyType, Comparer>::Iterator begin(ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
224 
225 template <typename KeyType, typename Comparer>
226 typename ezSetBase<KeyType, Comparer>::Iterator begin(const ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
227 
228 template <typename KeyType, typename Comparer>
229 typename ezSetBase<KeyType, Comparer>::Iterator cbegin(const ezSetBase<KeyType, Comparer>& container) { return container.GetIterator(); }
230 
231 template <typename KeyType, typename Comparer>
233 
234 template <typename KeyType, typename Comparer>
236 
237 template <typename KeyType, typename Comparer>
239 
240 
241 #include <Foundation/Containers/Implementation/Set_inl.h>
242