Changeset 5af0bc9 in mainline

Timestamp:

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

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

921174c

Parents:

79c9e0f

git-author:

Dzejrou <dzejrou@…> (2018-04-22 15:42:24)

git-committer:

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

Message:

cpp: fixed iterators, added remove and unique

File:

• uspace/lib/cpp/include/impl/list.hpp (modified) (9 diffs)

uspace/lib/cpp/include/impl/list.hpp

@@ -87 +87 @@
                 prev = node;
             }
+
+            void unlink()
+            {
+                prev->next = next;
+                next->prev = prev;
+            }
         };
 
@@ -154 +160 @@
                 }
 
+                list_const_iterator operator-(difference_type n) const
+                {
+                    /**
+                     * Note: This operator is for internal purposes only,
+                     *       so we do not provide inverse operator or shortcut
+                     *       -= operator.
+                     */
+                    auto tmp = current_;
+
+                    for (difference_type i = 0; i < n; ++i)
+                        tmp = tmp->prev;
+
+                    return list_const_iterator{tmp};
+                }
+
             private:
                 list_node<value_type>* current_;
@@ -239 +260 @@
                 {
                     return list_const_iterator<T>{current_};
+                }
+
+                list_iterator operator-(difference_type n) const
+                {
+                    /**
+                     * Note: This operator is for internal purposes only,
+                     *       so we do not provide inverse operator or shortcut
+                     *       -= operator.
+                     */
+                    auto tmp = current_;
+
+                    for (difference_type i = 0; i < n; ++i)
+                        tmp = tmp->prev;
+
+                    return list_iterator{tmp};
                 }
 
@@ -624 +660 @@
                     head_ = head_->prev;
 
-                return iterator{node->prev};
+                return iterator{node->prev, head_};
             }
 
@@ -658 +694 @@
                 }
 
-                return iterator{position.node()->next};
+                return iterator{position.node()->next, head_};
             }
 
@@ -669 +705 @@
             {
                 auto node = position.node();
+
+                if (node == head_)
+                {
+                    if (size_ == 1)
+                    {
+                        delete head_;
+                        head_ = nullptr;
+                        size_ = 0;
+
+                        return end();
+                    }
+                    else
+                        head_ = node->next;
+                }
+
+                auto next = node->next;
+
                 --size_;
 
-                if (node != get_last_())
-                {
-                    auto next = node->next;
-                    auto prev = node->prev;
-
-                    next->prev = prev;
-                    prev->next = next;
-
-                    delete node;
-
-                    return iterator{next};
-                }
-                else
-                {
-                    auto prev = node->prev;
-                    head_->prev = prev;
-                    prev->next = head_;
-
-                    delete node;
-
-                    return end();
-                }
+                node->unlink();
+                delete node;
+
+                return iterator{next, head_};
             }
 
@@ -709 +744 @@
                 while (first_node != next)
                 {
+                    // TODO: test with head in the range
+                    /* if (first_node == head_) */
+                    /*     head_ = last.node()->next; */
+
                     auto tmp = first_node;
                     first_node = first_node->next;
@@ -716 +755 @@
                 }
 
-                return iterator{next};
+                return iterator{next, head_};
             }
 
@@ -870 +909 @@
             }
 
+            void remove(const value_type& val)
+            {
+                if (!head_)
+                    return;
+
+                auto it = begin();
+                while (it != end())
+                {
+                    if (*it == val)
+                        it = erase(it);
+                    else
+                        ++it;
+                }
+            }
+
+            template<class Predicate>
+            void remove_if(Predicate pred)
+            {
+                if (!head_)
+                    return;
+
+                auto it = begin();
+                while (it != end())
+                {
+                    if (pred(*it))
+                        it = erase(it);
+                    else
+                        ++it;
+                }
+            }
+
+            void unique()
+            {
+                if (!head_)
+                    return;
+
+                auto it = begin();
+                ++it;
+
+                while (it != end())
+                {
+                    if (*it == *(it - 1))
+                        it = erase(it);
+                    else
+                        ++it;
+                }
+            }
+
+            template<class BinaryPredicate>
+            void unique(BinaryPredicate pred)
+            {
+                if (!head_)
+                    return;
+
+                auto it = begin();
+                ++it;
+
+                while (it != end())
+                {
+                    if (pred(*it, *(it - 1)))
+                        it = erase(it);
+                    else
+                        ++it;
+                }
+            }
+
+            // TODO: make a generic base for algorithms like merge
+            //       and quicksort that uses a swapper (the <algorithm>
+            //       versions would use std::swap and list versions would
+            //       use a swapper that swaps list nodes)
+
         private:
             allocator_type allocator_;