Changeset be9eb15 in mainline

Timestamp:

2018-07-05T21:41:22Z (7 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

49fbfb5

Parents:

2a482ee

git-author:

Dzejrou <dzejrou@…> (2018-04-29 00:38:54)

git-committer:

Dzejrou <dzejrou@…> (2018-07-05 21:41:22)

Message:

cpp: added find, some contructors and assignment operators and reverse iterator support to rbtree

File:

• uspace/lib/cpp/include/internal/rbtree.hpp (modified) (7 diffs)

uspace/lib/cpp/include/internal/rbtree.hpp

@@ -56 +56 @@
             using const_iterator       = ConstIterator;
 
+            using reverse_iterator       = std::reverse_iterator<iterator>;
+            using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
             using node_type = rbtree_node<value_type>;
 
@@ -63 +66 @@
             { /* DUMMY BODY */ }
 
-            rbtree(const rbtree& other);
-
-            rbtree(rbtree&& other);
-
-            rbtree& operator=(const rbtree& other);
-
-            rbtree& operator=(rbtree&& other);
+            rbtree(const rbtree& other); // TODO:
+
+            rbtree(rbtree&& other)
+                : root_{other.root_}, size_{other.size_},
+                  key_compare_{move(other.key_compare_)},
+                  key_extractor_{move(other.key_extractor_)}
+            {
+                other.root_ = nullptr;
+                other.size_ = size_type{};
+            }
+
+            rbtree& operator=(const rbtree& other)
+            {
+                auto tmp{other};
+                tmp.swap(*this);
+
+                return *this;
+            }
+
+            rbtree& operator=(rbtree&& other)
+            {
+                rbtree tmp{move(other)};
+                tmp.swap(*this);
+
+                return *this;
+            }
 
             bool empty() const noexcept
@@ -106 +128 @@
             }
 
+            reverse_iterator rbegin()
+            {
+                return make_reverse_iterator(end());
+            }
+
+            const_reverse_iterator rbegin() const
+            {
+                return make_reverse_iterator(cend());
+            }
+
+            reverse_iterator rend()
+            {
+                return make_reverse_iterator(begin());
+            }
+
+            const_reverse_iterator rend() const
+            {
+                return make_reverse_iterator(cbegin());
+            }
+
             const_iterator cbegin() const
             {
@@ -114 +156 @@
             {
                 return const_iterator{find_largest_(), true};
+            }
+
+            const_reverse_iterator crbegin() const
+            {
+                return make_reverse_iterator(cend());
+            }
+
+            const_reverse_iterator crend() const
+            {
+                return make_reverse_iterator(cbegin());
             }
 
@@ -191 +243 @@
             iterator find(const key_type& key)
             {
-                // TODO: implement
-            }
-
-            const_iterator find(const key_type&& key) const
-            {
-                // TODO: implement
+                auto node = find_(key);
+                if (node)
+                    return iterator{node, false};
+                else
+                    return end();
+            }
+
+            const_iterator find(const key_type& key) const
+            {
+                auto node = find_(key);
+                if (node)
+                    return const_iterator{node, false};
+                else
+                    return end();
             }
 
@@ -273 +333 @@
             key_extract key_extractor_;
 
+            node_type* find_(const key_type& key) const
+            {
+                auto current = root_;
+                while (current != nullptr)
+                {
+                    if (key_compare_(key, key_extractor_(current->value)))
+                        current = current->left;
+                    else if (key == key_extractor_(current->value))
+                        return current;
+                    else
+                        current = current->right;
+                }
+
+                return nullptr;
+            }
+
             node_type* find_smallest_() const
             {
@@ -304 +380 @@
             }
 
+            void repair_after_erase_(node_type* node)
+            {
+                // TODO: implement
+            }
+
             friend Policy;
     };