CppCommon 1.0.5.0
C++ Common Library
Loading...
Searching...
No Matches
bintree_rb.h
Go to the documentation of this file.
1
9#ifndef CPPCOMMON_CONTAINERS_BINTREE_RB_H
10#define CPPCOMMON_CONTAINERS_BINTREE_RB_H
11
12#include "bintree.h"
13
14namespace CppCommon {
15
17
200template <typename T, typename TCompare = std::less<T>>
202{
203public:
204 // Standard container type definitions
205 typedef T value_type;
206 typedef TCompare value_compare;
210 typedef const value_type* const_pointer;
211 typedef ptrdiff_t difference_type;
212 typedef size_t size_type;
217
219 struct Node
220 {
222 T* left;
223 T* right;
224 bool rb;
225
226 Node() : parent(nullptr), left(nullptr), right(nullptr), rb(false) {}
227 };
228
229 explicit BinTreeRB(const TCompare& compare = TCompare()) noexcept
230 : _compare(compare),
231 _size(0),
232 _root(nullptr)
233 {}
234 template <class InputIterator>
235 BinTreeRB(InputIterator first, InputIterator last, const TCompare& compare = TCompare()) noexcept;
236 BinTreeRB(const BinTreeRB&) noexcept = default;
237 BinTreeRB(BinTreeRB&&) noexcept = default;
238 ~BinTreeRB() noexcept = default;
239
240 BinTreeRB& operator=(const BinTreeRB&) noexcept = default;
241 BinTreeRB& operator=(BinTreeRB&&) noexcept = default;
242
244 explicit operator bool() const noexcept { return !empty(); }
245
247 bool empty() const noexcept { return _root == nullptr; }
248
250 size_t size() const noexcept { return _size; }
251
253 T* root() noexcept { return _root; }
254 const T* root() const noexcept { return _root; }
256 T* lowest() noexcept;
257 const T* lowest() const noexcept;
259 T* highest() noexcept;
260 const T* highest() const noexcept;
261
263 bool compare(const T& item1, const T& item2) const noexcept { return _compare(item1, item2); }
264
266 iterator begin() noexcept;
267 const_iterator begin() const noexcept;
268 const_iterator cbegin() const noexcept;
270 iterator end() noexcept;
271 const_iterator end() const noexcept;
272 const_iterator cend() const noexcept;
273
275 reverse_iterator rbegin() noexcept;
276 const_reverse_iterator rbegin() const noexcept;
277 const_reverse_iterator crbegin() const noexcept;
279 reverse_iterator rend() noexcept;
280 const_reverse_iterator rend() const noexcept;
281 const_reverse_iterator crend() const noexcept;
282
284 iterator find(const T& item) noexcept;
285 const_iterator find(const T& item) const noexcept;
286
288 iterator lower_bound(const T& item) noexcept;
289 const_iterator lower_bound(const T& item) const noexcept;
291 iterator upper_bound(const T& item) noexcept;
292 const_iterator upper_bound(const T& item) const noexcept;
293
295
299 std::pair<iterator, bool> insert(T& item) noexcept;
301
306 std::pair<iterator, bool> insert(const const_iterator& position, T& item) noexcept;
307
309
313 T* erase(const T& item) noexcept;
315
319 iterator erase(const iterator& it) noexcept;
320
322 void clear() noexcept;
323
325 void swap(BinTreeRB& bintree) noexcept;
326 template <typename U, typename UCompare>
327 friend void swap(BinTreeRB<U, UCompare>& bintree1, BinTreeRB<U, UCompare>& bintree2) noexcept;
328
329private:
330 TCompare _compare; // Binary tree compare
331 size_t _size; // Binary tree size
332 T* _root; // Binary tree root node
333
334 const T* InternalLowest() const noexcept;
335 const T* InternalHighest() const noexcept;
336 const T* InternalFind(const T& item) const noexcept;
337 const T* InternalLowerBound(const T& item) const noexcept;
338 const T* InternalUpperBound(const T& item) const noexcept;
339
340 void RotateLeft(T* node);
341 void RotateRight(T* node);
342 void Unlink(T* node, T* parent);
343 static void Swap(T*& node1, T*& node2);
344};
345
346} // namespace CppCommon
347
348#include "bintree_rb.inl"
349
350#endif // CPPCOMMON_CONTAINERS_BINTREE_RB_H
Intrusive non balanced binary tree container definition.
Intrusive binary tree constant iterator.
Definition bintree.h:335
Intrusive binary tree constant reverse iterator.
Definition bintree.h:448
Intrusive binary tree iterator.
Definition bintree.h:279
Intrusive balanced Red-Black binary tree container.
Definition bintree_rb.h:202
BinTreeIterator< BinTreeRB< T, TCompare >, T > iterator
Definition bintree_rb.h:213
BinTreeReverseIterator< BinTreeRB< T, TCompare >, T > reverse_iterator
Definition bintree_rb.h:215
bool compare(const T &item1, const T &item2) const noexcept
Compare two items: if the first item is less than the second one?
Definition bintree_rb.h:263
T * highest() noexcept
Get the highest binary tree item.
value_type & reference
Definition bintree_rb.h:207
size_t size() const noexcept
Get the binary tree size.
Definition bintree_rb.h:250
const value_type * const_pointer
Definition bintree_rb.h:210
BinTreeConstReverseIterator< BinTreeRB< T, TCompare >, T > const_reverse_iterator
Definition bintree_rb.h:216
const_iterator cend() const noexcept
const T * root() const noexcept
Definition bintree_rb.h:254
const_reverse_iterator crbegin() const noexcept
ptrdiff_t difference_type
Definition bintree_rb.h:211
BinTreeRB(const TCompare &compare=TCompare()) noexcept
Definition bintree_rb.h:229
friend void swap(BinTreeRB< U, UCompare > &bintree1, BinTreeRB< U, UCompare > &bintree2) noexcept
iterator begin() noexcept
Get the begin binary tree iterator.
reverse_iterator rbegin() noexcept
Get the reverse begin binary tree iterator.
T * erase(const T &item) noexcept
Erase the given item from the binary tree.
void clear() noexcept
Clear the binary tree.
iterator upper_bound(const T &item) noexcept
Find the iterator which points to the first item that greater than the given item in the binary tree ...
BinTreeConstIterator< BinTreeRB< T, TCompare >, T > const_iterator
Definition bintree_rb.h:214
reverse_iterator rend() noexcept
Get the reverse end binary tree iterator.
bool empty() const noexcept
Is the binary tree empty?
Definition bintree_rb.h:247
iterator end() noexcept
Get the end binary tree iterator.
T * lowest() noexcept
Get the lowest binary tree item.
T * root() noexcept
Get the root binary tree item.
Definition bintree_rb.h:253
const_reverse_iterator crend() const noexcept
std::pair< iterator, bool > insert(T &item) noexcept
Insert a new item into the binary tree.
value_type * pointer
Definition bintree_rb.h:209
const value_type & const_reference
Definition bintree_rb.h:208
iterator lower_bound(const T &item) noexcept
Find the iterator which points to the first item that not less than the given item in the binary tree...
const_iterator cbegin() const noexcept
iterator find(const T &item) noexcept
Find the iterator which points to the first equal item in the binary tree or return end iterator.
Intrusive binary tree reverse iterator.
Definition bintree.h:392
C++ Common project definitions.
Red-Black binary tree node.
Definition bintree_rb.h:220
T * right
Pointer to the right child binary tree node.
Definition bintree_rb.h:223
T * left
Pointer to the left child binary tree node.
Definition bintree_rb.h:222
bool rb
Red-Black flag.
Definition bintree_rb.h:224
T * parent
Pointer to the parent binary tree node.
Definition bintree_rb.h:221