Changeset 4077 for branches/kendall-score/yat/utility/ranking/Impl.cc

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/Impl.cc (modified) (2 diffs)

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

@@ -189 +189 @@
 
   void Impl::insert_and_rebalance(std::unique_ptr<NodeBase>&& element,
-                                  NodeBase& parent, NodeBase*& child)
-  {
-    assert(child == nullptr);
-    child = element.release();
+                                  NodeBase& parent, bool left)
+  {
+    NodeBase* child = nullptr;
+    if (left) {
+      parent.left_ = element.release();
+      child = parent.left_;
+      if (&parent == left_most())
+        left_most() = child;
+    }
+    else {
+      parent.right_ = element.release();
+      child = parent.right_;
+    }
+
     child->parent_ = &parent;
     parent.increment_size();
     parent.update_height_recursively();
-
     insert_rebalance(&parent, child);
   }
@@ -458 +467 @@
 
 
+  NodeBase* Impl::right_most(void)
+  {
+    // FIXME this scaled logN, make it constant time
+    return root_node()->right_most();
+  }
+
+
+  const NodeBase* Impl::right_most(void) const
+  {
+    // FIXME this scaled logN, make it constant time
+    return root_node()->right_most();
+  }
+
+
   NodeBase*& Impl::root_node(void)
   {