Changeset 4077 for branches/kendall-score/yat/utility/Ranking.h

Timestamp:

Aug 26, 2021, 6:07:09 AM (19 months ago)

Author:

Peter

Message:

implement insert with hint; refs #710

File:

• branches/kendall-score/yat/utility/Ranking.h (modified) (12 diffs)

branches/kendall-score/yat/utility/Ranking.h

@@ -32 +32 @@
 #include <cstddef>
 #include <functional>
+#include <iostream>
+#include <iterator>
 #include <memory>
 
-#include <iostream> // debug
 namespace theplu {
 namespace yat {
@@ -109 +110 @@
 
     /**
+       \return iterator pointing to the first element, i.e., the
+       node with the smallest value.
+     */
+    iterator begin(void)
+    {
+      return iterator(impl_.left_most());
+    }
+
+
+    /**
        \return iterator pointing to the first element
      */
-    iterator begin(void)
-    {
-      return iterator(impl_.left_most());
+    const_iterator begin(void) const
+    {
+      return cbegin();
     }
 
@@ -120 +131 @@
        \return iterator pointing to the first element
      */
-    const_iterator begin(void) const
-    {
-      return cbegin();
-    }
-
-
-    /**
-       \return iterator pointing to the first element
-     */
     const_iterator cbegin(void) const
     {
@@ -163 +165 @@
 
     /**
-       \return reverse iterator pointing to first element
+       \return reverse iterator pointing to first element, i.e., the
+       node with the largest value.
      */
     reverse_iterator rbegin(void)
@@ -247 +250 @@
 
     /**
-       Remove element pointed to by \c position.
+       Remove node pointed to by \c position.
 
        \return An iterator pointing to the element that follows the
@@ -298 +301 @@
     /**
        \brief insert with hint
+
+       If \c hint will follow the inserted element, the insertion is done
+       in constant time. Otherwise, the usual insert function is
+       called which takes logN.
      */
     iterator insert(const_iterator hint, const T& element)
     {
-      // FIXME use the hint
-      return insert(element);
+      std::unique_ptr<ranking::NodeValue<T>>
+        newnode(new ranking::NodeValue<T>(element));
+      return insert(hint, std::move(newnode));
     }
 
@@ -311 +319 @@
     iterator insert(const_iterator hint,  T&& element)
     {
-      // FIXME use the hint
-      return insert(std::move(element));
+      std::unique_ptr<ranking::NodeValue<T>>
+        newnode(new ranking::NodeValue<T>(std::move(element)));
+      return insert(hint, std::move(newnode));
     }
 
@@ -370 +379 @@
     Compare compare_;
     ranking::Impl impl_;
+
+    iterator
+    insert_and_rebalance(std::unique_ptr<ranking::NodeValue<T>>&& element,
+                         ranking::NodeBase& parent, bool left)
+    {
+      iterator result(element.get());
+      impl_.insert_and_rebalance(std::move(element), parent, left);
+      YAT_ASSERT(validate());
+      return result;
+    }
+
+
 
     void print(const ranking::NodeBase* p, std::ostream& os) const
@@ -481 +502 @@
     {
       while (x) {
-        if (x->right_ && x->right_ !=  &impl_.head_)
+        if (x->right_)
           erase(right(x));
         ranking::NodeValue<T>* tmp = left(x);
@@ -496 +517 @@
     iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element)
     {
-      iterator result(element.get());
 
       if (empty()) {
@@ -511 +531 @@
 
         YAT_ASSERT(validate());
-        return result;
-      }
-
-      ranking::NodeBase* x = impl_.root_node();
+        return iterator(root_node());
+      }
+
+      return insert(impl_.root_node(), std::move(element));
+    }
+
+
+    // Insert \a element into the subtree in which x is the root.
+    iterator insert(ranking::NodeBase* x,
+                    std::unique_ptr<ranking::NodeValue<T>>&& element)
+    {
       YAT_ASSERT(x);
       YAT_ASSERT(!x->is_head_node());
@@ -522 +549 @@
         if (compare_(element->value(), value(x))) {
           x = x->left_;
-          if (x == nullptr) {
-            impl_.insert_and_rebalance(std::move(element), *parent,
-                                       parent->left_);
-            if (impl_.left_most() == parent)
-              impl_.left_most() = parent->left_;
-            YAT_ASSERT(validate());
-            return result;
-          }
+          if (x == nullptr)
+            return insert_and_rebalance(std::move(element), *parent, true);
         }
         else {
           x = x->right_;
-          if (x == nullptr) {
-            impl_.insert_and_rebalance(std::move(element), *parent,
-                                       parent->right_);
-            YAT_ASSERT(validate());
-            return result;
-          }
+          if (x == nullptr)
+            return insert_and_rebalance(std::move(element), *parent, false);
         }
       }
       YAT_ASSERT(0 && "we can't reach here");
-      return result;
+      return iterator(element.get());
+    }
+
+
+    iterator insert(const_iterator hint,
+                    std::unique_ptr<ranking::NodeValue<T>>&& element)
+    {
+      // special case when hint == end()
+      if (hint.node_ == head_node()) {
+        YAT_ASSERT(hint == cend());
+        if (empty() || compare_(element->value(), value(impl_.right_most())))
+          return insert(std::move(element));
+        return insert_and_rebalance(std::move(element), *impl_.right_most(),
+                                    false);
+      }
+
+      YAT_ASSERT(hint != end());
+
+      // value <= hint i.e. !(hint<value)
+      if (!compare_(*hint, element->value())) {
+        // if hint == begin
+        if (hint.node_ == impl_.left_most()) {
+          YAT_ASSERT(hint == cbegin());
+          return insert_and_rebalance(std::move(element),
+                                      *impl_.left_most(),
+                                      true);
+        }
+
+        // prev <= value <= hint insert
+        YAT_ASSERT(hint != cbegin());
+        auto before = std::prev(hint);
+        if (!compare_(element->value(), *before)) {
+          return insert(const_cast<ranking::NodeBase*>(hint.node_),
+                        std::move(element));
+        }
+        else {
+          return insert(std::move(element));
+        }
+      }
+      // else value > hint
+      else {
+        YAT_ASSERT(compare_(*hint, element->value()));
+        // hint == rightmost
+        if (hint.node_ == impl_.right_most()) {
+          return insert_and_rebalance(std::move(element),
+                                      *impl_.right_most(),
+                                      false);
+        }
+        auto after = std::next(hint);
+        YAT_ASSERT(after != cend());
+        // hint < value <= after
+        if (!compare_(*after, element->value())) {
+          return insert(const_cast<ranking::NodeBase*>(after.node_),
+                        std::move(element));
+        }
+      }
+
+      return insert(std::move(element));
     }