Changeset 009d78b in mainline

Timestamp:

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

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

d6bb78b

Parents:

f8bbaa0

git-author:

Dzejrou <dzejrou@…> (2018-04-29 19:22:57)

git-committer:

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

Message:

cpp: added the rest of functions to rbtree, fixed some existing ones

File:

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

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

@@ -61 +61 @@
             using node_type = rbtree_node<value_type>;
 
+            // TODO: make find/bounds etc templated with key type
+            //       for transparent comparators and leave their management for the
+            //       outer containers
+
             rbtree(const key_compare& kcmp = key_compare{})
                 : root_{nullptr}, size_{}, key_compare_{},
@@ -66 +70 @@
             { /* DUMMY BODY */ }
 
-            rbtree(const rbtree& other); // TODO:
+            rbtree(const rbtree& other)
+                : rbtree{other.key_compare_}
+            {
+                for (const auto& x: other)
+                    insert(x);
+            }
 
             rbtree(rbtree&& other)
@@ -172 +181 @@
             {
                 auto ret = Policy::emplace(*this, forward<Args>(args)...);
+                if (!ret.second)
+                    return ret;
+                ++size_;
+
+                repair_after_insert_(ret.first.node());
+                update_root_(ret.first.node());
 
                 return ret;
@@ -181 +196 @@
                 if (!ret.second)
                     return ret;
+                ++size_;
 
                 repair_after_insert_(ret.first.node());
@@ -193 +209 @@
                 if (!ret.second)
                     return ret;
+                ++size_;
 
                 repair_after_insert_(ret.first.node());
@@ -202 +219 @@
             size_type erase(const key_type& key)
             {
-                auto ret = Policy::erase(*this, key);
-                if (ret == 0)
-                    return ret;
-                // TODO: problem - we don't have a node ptr
-                //       solution: return a pair<size_type, node_type*>
-
-                return ret;
+                return Policy::erase(*this, key);
             }
 
             iterator erase(const_iterator it)
             {
-                // TODO: implement
+                if (it == cend())
+                    return end();
+
+                auto node = const_cast<node_type*>(it.node());
+                ++it;
+
+                delete_node(node);
+                return iterator{const_cast<node_type*>(it.node()), it.end()};
             }
 
@@ -296 +314 @@
             bool is_eq_to(const rbtree& other) const
             {
-                // TODO: implement
-                return false;
+                if (size_ != other.size())
+                    return false;
+
+                auto it1 = begin();
+                auto it2 = other.begin();
+
+                while (keys_equal(*it1++, *it2++))
+                { /* DUMMY BODY */ }
+
+                return (it1 == end()) && (it2 == other.end());
             }
 
@@ -308 +334 @@
             {
                 return key_compare_(key, key_extractor_(val));
+            }
+
+            bool keys_equal(const key_type& k1, const key_type& k2) const
+            {
+                return !key_compare_(k1, k2) && !key_compare_(k2, k1);
             }
 
@@ -327 +358 @@
             }
 
+            void delete_node(node_type* node)
+            {
+                if (!node)
+                    return;
+
+                --size_;
+
+                if (node->left && node->right)
+                {
+                    node->swap(node->successor());
+
+                    // Node now has at most one child.
+                    delete_node(node);
+
+                    return;
+                }
+
+                auto child = node->right ? node->right : node->left;
+                if (!child)
+                {
+                    // Simply remove the node.
+                    node->unlink();
+
+                    delete node;
+                }
+                else
+                {
+                    // Replace with the child.
+                    child->parent = node->parent;
+                    if (node->is_left_child())
+                        child->parent->left = child;
+                    else if (node->is_left_child())
+                        child->parent->right = child;
+
+                    // Repair if needed.
+                    repair_after_erase_(node, child);
+                    update_root_(child);
+                }
+            }
+
         private:
             node_type* root_;
@@ -340 +411 @@
                     if (key_compare_(key, key_extractor_(current->value)))
                         current = current->left;
-                    else if (key == key_extractor_(current->value))
+                    else if (key_compare_(key_extractor_(current->value), key))
+                        current = current->right;
+                    else
                         return current;
-                    else
-                        current = current->right;
                 }
 
@@ -380 +451 @@
             }
 
-            void repair_after_erase_(node_type* node)
+            void repair_after_erase_(node_type* node, node_type* child)
             {
                 // TODO: implement