Changeset 4079

Timestamp:

Aug 26, 2021, 10:38:04 AM (3 months ago)

Author:

Peter

Message:

store the right_most node, so it can be accessed in constant time (rather than logarithmic); refs #710

Location:

branches/kendall-score/yat/utility

Files:

• Ranking.h (modified) (2 diffs)
• ranking/Impl.cc (modified) (7 diffs)
• ranking/Impl.h (modified) (2 diffs)

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

@@ -523 +523 @@
         impl_.head_.left_ = impl_.root_node();
         impl_.head_.right_ = impl_.root_node();
+        impl_.right_most() = impl_.root_node();
         impl_.head_.update_height();
         impl_.head_.update_size();
@@ -806 +807 @@
     head_node()->update_height();
     head_node()->update_size();
+    if (root_node())
+      impl_.right_most() = root_node()->right_most();
+    else
+      impl_.right_most() = head_node();
     YAT_ASSERT(validate());
     return root;

branches/kendall-score/yat/utility/ranking/Impl.cc

@@ -77 +77 @@
       head_.left_->parent_ = &head_;
       head_.right_ = from.head_.right_;
-    }
-    else
+      right_most_ = root_node()->right_most();
+    }
+    else {
       head_.right_ = &head_;
+      right_most() = &head_;
+    }
     head_.height_ = from.head_.height_;
     head_.size_ = from.head_.size_;
@@ -120 +123 @@
 
     // update pointer to left_most node
-    if (head_.left_ == node) {
-      head_.left_ = child ? child : node->parent_;
-    }
+    if (left_most() == node)
+      left_most() = child ? child : node->parent_;
+    if (right_most() == node)
+      right_most() = child ? child : node->parent_;
     assert(child==nullptr || child->is_left_node() || child->is_right_node());
   }
@@ -150 +154 @@
     head_.left_ = nullptr;
     head_.right_ = &head_; // most left node
+    right_most_ = &head_;
     head_.update_height();
     head_.update_size();
@@ -201 +206 @@
       parent.right_ = element.release();
       child = parent.right_;
+      if (&parent == right_most())
+        right_most() = child;
     }
 
@@ -426 +433 @@
     }
 
+    if (root_node()) {
+      if (left_most() != root_node()->left_most()) {
+        std::cerr << "leftmost incorrect\n";
+        return false;
+      }
+      if (right_most() != root_node()->right_most()) {
+        std::cerr << "rightmost incorrect\n";
+        return false;
+      }
+    }
+
 
     /*
@@ -467 +485 @@
 
 
-  NodeBase* Impl::right_most(void)
-  {
-    // FIXME this scaled logN, make it constant time
-    return root_node()->right_most();
+  NodeBase*& Impl::right_most(void)
+  {
+    return right_most_;
   }
 
@@ -476 +493 @@
   const NodeBase* Impl::right_most(void) const
   {
-    // FIXME this scaled logN, make it constant time
-    return root_node()->right_most();
+    return right_most_;
   }
 

branches/kendall-score/yat/utility/ranking/Impl.h

@@ -62 +62 @@
       NodeBase*& left_most(void);
       const NodeBase* left_most(void) const;
-      NodeBase* right_most(void);
+      NodeBase*& right_most(void);
       const NodeBase* right_most(void) const;
 
@@ -126 +126 @@
       NodeBase* right_rotate(NodeBase* y);
     private:
+      NodeBase* right_most_;
       void move_data(Impl&&);
       void erase_rebalance(NodeBase* node);