ezEngine  Milestone 7
Map.h
1 #pragma once
2 
3 #include <Foundation/Containers/Deque.h>
4 
16 template <typename KeyType, typename ValueType, typename Comparer>
17 class ezMapBase
18 {
19 private:
20  struct Node;
21 
23  struct NilNode
24  {
25  NilNode();
26 
27  Node* m_pParent;
28  Node* m_pLink[2];
29  ezUInt8 m_uiLevel;
30  };
31 
33  struct Node : public NilNode
34  {
35  KeyType m_Key;
36  ValueType m_Value;
37  };
38 
39 public:
40 
43  {
44  typedef std::forward_iterator_tag iterator_category;
45  typedef ConstIterator value_type;
46  typedef ptrdiff_t difference_type;
47  typedef ConstIterator* pointer;
48  typedef ConstIterator& reference;
49 
50  EZ_DECLARE_POD_TYPE();
51 
53  EZ_FORCE_INLINE ConstIterator() : m_pElement(nullptr) { } // [tested]
54 
56  EZ_FORCE_INLINE bool IsValid() const { return (m_pElement != nullptr); } // [tested]
57 
59  EZ_FORCE_INLINE bool operator==(const typename ezMapBase<KeyType, ValueType, Comparer>::ConstIterator& it2) const { return (m_pElement == it2.m_pElement); }
60 
62  EZ_FORCE_INLINE bool operator!=(const typename ezMapBase<KeyType, ValueType, Comparer>::ConstIterator& it2) const { return (m_pElement != it2.m_pElement); }
63 
65  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]
66 
68  EZ_FORCE_INLINE const ValueType& Value() const { EZ_ASSERT_DEV(IsValid(), "Cannot access the 'value' of an invalid iterator."); return m_pElement->m_Value; } // [tested]
69 
71  void Next(); // [tested]
72 
74  void Prev(); // [tested]
75 
77  EZ_FORCE_INLINE void operator++() { Next(); } // [tested]
78 
80  EZ_FORCE_INLINE void operator--() { Prev(); } // [tested]
81 
82  protected:
83  friend class ezMapBase<KeyType, ValueType, Comparer>;
84 
85  EZ_FORCE_INLINE explicit ConstIterator(Node* pInit) : m_pElement(pInit) { }
86 
87  Node* m_pElement;
88  };
89 
91  struct Iterator : public ConstIterator
92  {
93  typedef std::forward_iterator_tag iterator_category;
94  typedef Iterator value_type;
95  typedef ptrdiff_t difference_type;
96  typedef Iterator* pointer;
97  typedef Iterator& reference;
98 
99  // this is required to pull in the const version of this function
100  using ConstIterator::Value;
101 
102  EZ_DECLARE_POD_TYPE();
103 
105  EZ_FORCE_INLINE Iterator() : ConstIterator() { }
106 
108  EZ_FORCE_INLINE ValueType& Value() { EZ_ASSERT_DEV(this->IsValid(), "Cannot access the 'value' of an invalid iterator."); return this->m_pElement->m_Value; }
109 
111  EZ_FORCE_INLINE ValueType& operator*() { return Value(); }
112 
113  private:
114  friend class ezMapBase<KeyType, ValueType, Comparer>;
115 
116  EZ_FORCE_INLINE explicit Iterator(Node* pInit) : ConstIterator(pInit) { }
117  };
118 
119 protected:
120 
122  ezMapBase(const Comparer& comparer, ezAllocatorBase* pAllocator); // [tested]
123 
125  ezMapBase(const ezMapBase<KeyType, ValueType, Comparer>& cc, ezAllocatorBase* pAllocator); // [tested]
126 
128  ~ezMapBase(); // [tested]
129 
132 
133 public:
135  bool IsEmpty() const; // [tested]
136 
138  ezUInt32 GetCount() const; // [tested]
139 
141  void Clear(); // [tested]
142 
144  Iterator GetIterator(); // [tested]
145 
147  ConstIterator GetIterator() const; // [tested]
148 
150  Iterator GetLastIterator(); // [tested]
151 
153  ConstIterator GetLastIterator() const; // [tested]
154 
156  Iterator Insert(const KeyType& key, const ValueType& value); // [tested]
157 
159  bool Remove(const KeyType& key); // [tested]
160 
162  Iterator Remove(const Iterator& pos); // [tested]
163 
165  Iterator FindOrAdd(const KeyType& key, bool* bExisted = nullptr); // [tested]
166 
168  ValueType& operator[](const KeyType& key); // [tested]
169 
171  Iterator Find(const KeyType& key); // [tested]
172 
174  Iterator LowerBound(const KeyType& key); // [tested]
175 
177  Iterator UpperBound(const KeyType& key); // [tested]
178 
180  ConstIterator Find(const KeyType& key) const; // [tested]
181 
183  bool Contains(const KeyType& key) const; // [tested]
184 
186  ConstIterator LowerBound(const KeyType& key) const; // [tested]
187 
189  ConstIterator UpperBound(const KeyType& key) const; // [tested]
190 
192  ezAllocatorBase* GetAllocator() const { return m_Elements.GetAllocator(); }
193 
195  bool operator==(const ezMapBase<KeyType, ValueType, Comparer>& rhs) const; // [tested]
196 
198  bool operator!=(const ezMapBase<KeyType, ValueType, Comparer>& rhs) const; // [tested]
199 
201  ezUInt64 GetHeapMemoryUsage() const { return m_Elements.GetHeapMemoryUsage(); } // [tested]
202 
203 private:
204  Node* Internal_Find(const KeyType& key) const;
205  Node* Internal_LowerBound(const KeyType& key) const;
206  Node* Internal_UpperBound(const KeyType& key) const;
207 
208 private:
209  void Constructor();
210 
212  Node* AcquireNode(const KeyType& key, const ValueType& value, int m_uiLevel, Node* pParent);
213 
215  void ReleaseNode(Node* pNode);
216 
217  // \brief Red-Black Tree stuff(Anderson Tree to be exact).
218  // Code taken from here: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx
219  Node* SkewNode(Node* root);
220  Node* SplitNode(Node* root);
221  void Insert(const KeyType& key, const ValueType& value, Node*& pInsertedNode);
222  Node* Remove(Node* root, const KeyType& key, bool& bRemoved);
223 
225  Node* GetLeftMost() const;
226 
228  Node* GetRightMost() const;
229 
231  Node* m_pRoot;
232 
234  NilNode m_NilNode;
235 
237  ezUInt32 m_uiCount;
238 
241 
244 
246  Comparer m_Comparer;
247 };
248 
249 
251 template <typename KeyType, typename ValueType, typename Comparer = ezCompareHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
252 class ezMap : public ezMapBase<KeyType, ValueType, Comparer>
253 {
254 public:
255  ezMap();
256  ezMap(const Comparer& comparer, ezAllocatorBase* pAllocator);
257 
260 
262  void operator=(const ezMapBase<KeyType, ValueType, Comparer>& rhs);
263 };
264 
265 template <typename KeyType, typename ValueType, typename Comparer>
267 
268 template <typename KeyType, typename ValueType, typename Comparer>
270 
271 template <typename KeyType, typename ValueType, typename Comparer>
273 
274 template <typename KeyType, typename ValueType, typename Comparer>
276 
277 template <typename KeyType, typename ValueType, typename Comparer>
279 
280 template <typename KeyType, typename ValueType, typename Comparer>
282 
283 #include <Foundation/Containers/Implementation/Map_inl.h>
284