Changeset f8bbaa0 in mainline


Ignore:
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:
009d78b
Parents:
49fbfb5
git-author:
Dzejrou <dzejrou@…> (2018-04-29 19:22:33)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
Message:

cpp: added the rest of operations to the rbtree_single policy

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/cpp/include/internal/rbtree_policies.hpp

    r49fbfb5 rf8bbaa0  
    4444
    4545        template<class Tree, class Key>
    46         static pair<
    47             typename Tree::node_type*,
    48             typename Tree::node_type*
    49         > erase(const Tree& tree, const Key& key)
    50         {
    51             // TODO:
    52         }
    53 
    54         template<class Tree, class Key>
    55         static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
    56         {
    57             // TODO:
    58         }
    59 
    60         template<class Tree, class Key>
    61         static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
    62         {
    63             // TODO:
     46        static typename Tree::size_type erase(Tree& tree, const Key& key)
     47        {
     48            using size_type = typename Tree::size_type;
     49
     50            auto it = tree.find(key);
     51            if (it == tree.end())
     52                return size_type{};
     53            else
     54                tree.delete_node(it.node());
     55            return size_type{1};
     56
     57            // This is the multi version -.-
     58            /* size_type res{}; */
     59            /* while (tree.keys_equal(tree.get_key(*it), key)) */
     60            /* { */
     61            /*     auto node = it.node(); */
     62            /*     ++it; */
     63
     64            /*     tree->delete_node(node); */
     65            /*     ++res; */
     66            /* } */
     67
     68            /* return res; */
     69        }
     70
     71        template<class Tree, class Key>
     72        static typename Tree::iterator lower_bound(Tree& tree, const Key& key)
     73        {
     74            using iterator = typename Tree::iterator;
     75
     76            auto node = tree.find_parent_for_insertion(key);
     77            iterator it{node, false};
     78            auto beg = tree.begin();
     79            auto end = tree.end();
     80
     81            if (tree.key_compare_(tree.get_key(*it), key))
     82            {
     83                // Predecessor.
     84                if (it != end)
     85                    return ++it;
     86                else
     87                    return it;
     88            }
     89            else if (tree.key_compare_(key, tree.get_key(*it)))
     90            {
     91                // Successor.
     92                if (it != beg)
     93                    return --it;
     94                else
     95                    return it;
     96            }
     97            else // Perfect match.
     98                return it;
     99
     100            return it;
     101        }
     102
     103        template<class Tree, class Key>
     104        static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
     105        {
     106            using const_iterator = typename Tree::const_iterator;
     107
     108            auto node = tree.find_parent_for_insertion(key);
     109            const_iterator it{node, false};
     110            auto beg = tree.begin();
     111            auto end = tree.end();
     112
     113            if (tree.key_compare_(tree.get_key(*it), key))
     114            {
     115                // Predecessor.
     116                if (it != end)
     117                    return ++it;
     118                else
     119                    return it;
     120            }
     121            else if (tree.key_compare_(key, tree.get_key(*it)))
     122            {
     123                // Successor.
     124                if (it != beg)
     125                    return --it;
     126                else
     127                    return it;
     128            }
     129            else // Perfect match.
     130                return it;
     131
     132            return it;
     133        }
     134
     135        template<class Tree, class Key>
     136        static typename Tree::iterator upper_bound(Tree& tree, const Key& key)
     137        {
     138            /**
     139             * If key isn't in the tree, we get it's
     140             * successor or tree.end(). If key is
     141             * in the tree, we get it.
     142             * In the first case, the successor is also
     143             * the upper bound, so we just return it,
     144             * otherwise (as long as it != end()) we
     145             * increment.
     146             */
     147            auto it = lower_bound(tree, key);
     148            if (it == tree.end())
     149                return it;
     150            else if (tree.keys_equal(key, *it))
     151                return ++it;
     152            else
     153                return it;
     154        }
     155
     156        template<class Tree, class Key>
     157        static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
     158        {
     159            /**
     160             * If key isn't in the tree, we get it's
     161             * successor or tree.end(). If key is
     162             * in the tree, we get it.
     163             * In the first case, the successor is also
     164             * the upper bound, so we just return it,
     165             * otherwise (as long as it != end()) we
     166             * increment.
     167             */
     168            auto it = lower_bound_const(tree, key);
     169            if (it == tree.end())
     170                return it;
     171            else if (tree.keys_equal(key, *it))
     172                return ++it;
     173            else
     174                return it;
    64175        }
    65176
    … …  
    68179            typename Tree::iterator,
    69180            typename Tree::iterator
    70         > equal_range(const Tree& tree, const Key& key)
    71         {
    72             // TODO:
     181        > equal_range(Tree& tree, const Key& key)
     182        {
     183            return make_pair(
     184                lower_bound(tree, key),
     185                upper_bound(tree, key)
     186            );
    73187        }
    74188
    … …  
    79193        > equal_range_const(const Tree& tree, const Key& key)
    80194        {
    81             // TODO:
     195            return make_pair(
     196                lower_bound_const(tree, key),
     197                upper_bound_const(tree, key)
     198            );
    82199        }
    83200
    … …  
    107224            }
    108225
    109             if (tree.get_key(parent->value) == tree.get_key(val))
     226            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    110227                return make_pair(iterator{parent}, false);
    111228
    … …  
    135252            }
    136253
    137             if (tree.get_key(parent->value) == tree.get_key(val))
     254            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    138255                return make_pair(iterator{parent}, false);
    139256
    … …  
    163280            }
    164281
    165             if (tree.get_key(parent->value) == tree.get_key(val))
     282            if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
    166283                return make_pair(iterator{parent}, false);
    167284
Note: See TracChangeset for help on using the changeset viewer.