ezEngine  Milestone 7
Deque.h
1 #pragma once
2 
3 #include <Foundation/Algorithm/Sorting.h>
4 #include <Foundation/Memory/AllocatorWrapper.h>
5 #include <Foundation/Containers/Implementation/ArrayIterator.h>
6 
7 #define ezInvalidIndex 0xFFFFFFFF
8 
21 template <typename T, bool Construct>
23 {
24 protected:
25 
27  ezDequeBase(ezAllocatorBase* pAllocator); // [tested]
28 
30  ezDequeBase(const ezDequeBase<T, Construct>& rhs, ezAllocatorBase* pAllocator); // [tested]
31 
33  ezDequeBase(ezDequeBase<T, Construct>&& rhs, ezAllocatorBase* pAllocator); // [tested]
34 
36  ~ezDequeBase(); // [tested]
37 
39  void operator=(const ezDequeBase<T, Construct>& rhs); // [tested]
40 
42  void operator=(ezDequeBase<T, Construct>&& rhs); // [tested]
43 
44 public:
46  void Clear(); // [tested]
47 
56  void Reserve(ezUInt32 uiCount); // [tested]
57 
64  void Compact(); // [tested]
65 
67  void SetCount(ezUInt32 uiCount); // [tested]
68 
70  T& operator[](ezUInt32 uiIndex); // [tested]
71 
73  const T& operator[](ezUInt32 uiIndex) const; // [tested]
74 
76  T& ExpandAndGetRef(); // [tested]
77 
79  void PushBack(); // [tested]
80 
82  void PushBack(const T& element); // [tested]
83 
85  void PopBack(ezUInt32 uiElements = 1); // [tested]
86 
88  void PushFront(const T& element); // [tested]
89 
91  void PushFront(); // [tested]
92 
94  void PopFront(ezUInt32 uiElements = 1); // [tested]
95 
97  bool IsEmpty() const; // [tested]
98 
100  ezUInt32 GetCount() const; // [tested]
101 
103  const T& PeekFront() const; // [tested]
104 
106  T& PeekFront(); // [tested]
107 
109  const T& PeekBack() const; // [tested]
110 
112  T& PeekBack(); // [tested]
113 
115  bool Contains(const T& value) const; // [tested]
116 
118  ezUInt32 IndexOf(const T& value, ezUInt32 uiStartIndex = 0) const; // [tested]
119 
121  ezUInt32 LastIndexOf(const T& value, ezUInt32 uiStartIndex = ezInvalidIndex) const; // [tested]
122 
124  void RemoveAtSwap(ezUInt32 uiIndex); // [tested]
125 
127  void RemoveAt(ezUInt32 uiIndex); // [tested]
128 
130  bool Remove(const T& value); // [tested]
131 
133  bool RemoveSwap(const T& value); // [tested]
134 
136  void Insert(const T& value, ezUInt32 uiIndex); // [tested]
137 
139  template <typename Comparer>
140  void Sort(const Comparer& comparer); // [tested]
141 
143  void Sort(); // [tested]
144 
146  ezAllocatorBase* GetAllocator() const { return m_pAllocator; }
147 
148  typedef const_iterator_base<ezDequeBase<T, Construct>, T, false> const_iterator;
149  typedef const_iterator_base<ezDequeBase<T, Construct>, T, true> const_reverse_iterator;
150  typedef iterator_base<ezDequeBase<T, Construct>, T, false> iterator;
151  typedef iterator_base<ezDequeBase<T, Construct>, T, true> reverse_iterator;
152 
156  ezUInt32 GetContiguousRange(ezUInt32 uiStartIndex) const; // [tested]
157 
159  bool operator==(const ezDequeBase<T, Construct>& rhs) const; // [tested]
160 
162  bool operator!=(const ezDequeBase<T, Construct>& rhs) const; // [tested]
163 
165  ezUInt64 GetHeapMemoryUsage() const; // [tested]
166 
167 private:
168 
170  void Constructor(ezAllocatorBase* pAllocator);
171 
173  void CompactIndexArray(ezUInt32 uiMinChunksToKeep);
174 
176  void MoveIndexChunksLeft(ezUInt32 uiChunkDiff);
177 
179  void MoveIndexChunksRight(ezUInt32 uiChunkDiff);
180 
182  ezUInt32 GetFirstUsedChunk() const;
183 
185  ezUInt32 GetLastUsedChunk(ezUInt32 uiAtSize) const;
186 
188  ezUInt32 GetLastUsedChunk() const;
189 
191  ezUInt32 GetRequiredChunks(ezUInt32 uiAtSize) const;
192 
194  void DeallocateUnusedChunks(ezUInt32 uiMaxChunks);
195 
197  void ResetReduceSizeCounter();
198 
213  void ReduceSize(ezInt32 iReduction);
214 
216  ezUInt32 GetCurMaxCount() const;
217 
219  T* GetUnusedChunk();
220 
222  T& ElementAt(ezUInt32 uiIndex);
223 
225  void DeallocateAll();
226 
227  ezAllocatorBase* m_pAllocator;
228  T** m_pChunks;
229  ezUInt32 m_uiChunks;
230  ezUInt32 m_uiFirstElement;
231  ezUInt32 m_uiCount;
234  ezUInt32 m_uiMaxCount;
235 
236 #if EZ_ENABLED(EZ_COMPILE_FOR_DEBUG)
237  ezUInt32 m_uiChunkSize; // needed for debugger visualization
238 #endif
239 };
240 
242 template <typename T, typename AllocatorWrapper = ezDefaultAllocatorWrapper, bool Construct = true>
243 class ezDeque : public ezDequeBase<T, Construct>
244 {
245 public:
246  ezDeque();
247  ezDeque(ezAllocatorBase* pAllocator);
248 
250  ezDeque(const ezDequeBase<T, Construct>& other);
251 
254 
255  void operator=(const ezDeque<T, AllocatorWrapper, Construct>& rhs);
256  void operator=(const ezDequeBase<T, Construct>& rhs);
257 
258  void operator=(ezDeque<T, AllocatorWrapper, Construct>&& rhs);
259  void operator=(ezDequeBase<T, Construct>&& rhs);
260 };
261 
262 template <typename T, bool Construct>
263 typename ezDequeBase<T, Construct>::iterator begin(ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::iterator(container, (size_t) 0); }
264 
265 template <typename T, bool Construct>
266 typename ezDequeBase<T, Construct>::const_iterator begin(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_iterator(container, (size_t) 0); }
267 
268 template <typename T, bool Construct>
269 typename ezDequeBase<T, Construct>::const_iterator cbegin(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_iterator(container, (size_t) 0); }
270 
271 template <typename T, bool Construct>
272 typename ezDequeBase<T, Construct>::reverse_iterator rbegin(ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::reverse_iterator(container, (size_t) 0); }
273 
274 template <typename T, bool Construct>
275 typename ezDequeBase<T, Construct>::const_reverse_iterator rbegin(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_reverse_iterator(container, (size_t) 0); }
276 
277 template <typename T, bool Construct>
278 typename ezDequeBase<T, Construct>::const_reverse_iterator crbegin(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_reverse_iterator(container, (size_t) 0); }
279 
280 template <typename T, bool Construct>
281 typename ezDequeBase<T, Construct>::iterator end(ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::iterator(container, (size_t) container.GetCount()); }
282 
283 template <typename T, bool Construct>
284 typename ezDequeBase<T, Construct>::const_iterator end(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_iterator(container, (size_t) container.GetCount()); }
285 
286 template <typename T, bool Construct>
287 typename ezDequeBase<T, Construct>::const_iterator cend(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_iterator(container, (size_t) container.GetCount()); }
288 
289 template <typename T, bool Construct>
290 typename ezDequeBase<T, Construct>::reverse_iterator rend(ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::reverse_iterator(container, (size_t) container.GetCount()); }
291 
292 template <typename T, bool Construct>
293 typename ezDequeBase<T, Construct>::const_reverse_iterator rend(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_reverse_iterator(container, (size_t) container.GetCount()); }
294 
295 template <typename T, bool Construct>
296 typename ezDequeBase<T, Construct>::const_reverse_iterator crend(const ezDequeBase<T, Construct>& container) { return typename ezDequeBase<T, Construct>::const_reverse_iterator(container, (size_t) container.GetCount()); }
297 
298 #include <Foundation/Containers/Implementation/Deque_inl.h>
299