Changeset 4071

Timestamp:

Aug 18, 2021, 4:31:29 AM (18 months ago)

Author:

Peter

Message:

Add variables height_ and size_ in NodeBase?, which describes the longest distance to its leaves and the size of the subtree in which it is the root, respectively. Use these variables to calculate the ranking, which means the ranking now scales like the height rather than the number of nodes. refs #710

Location:

branches/kendall-score/yat/utility

Files:

• Ranking.h (modified) (15 diffs)
• ranking/Impl.cc (modified) (5 diffs)
• ranking/Impl.h (modified) (1 diff)
• ranking/NodeBase.h (modified) (3 diffs)

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

@@ -234 +234 @@
     bool empty(void) const
     {
-      return size()==0;
+      return root_node() == nullptr;
     }
 
@@ -346 +346 @@
     size_t ranking(const_iterator it) const
     {
-      // FIXME
-      return std::distance(cbegin(), it);
+      return impl_.ranking(it.node_);
     }
 
@@ -356 +355 @@
     size_t size(void) const
     {
-      return impl_.node_count_;
+      return root_node() ? root_node()->size_ : 0;
     }
 
@@ -363 +362 @@
     ranking::Impl impl_;
 
-    void print(const ranking::NodeBase* p) const
+    void print(const ranking::NodeBase* p, std::ostream& os) const
     {
       if (p) {
         if (p->is_head_node()==false) {
-          print(p->right_);
-        }
-        std::cerr << std::string(p->generation()*4, ' ');
+          print(p->right_, os);
+        }
+        os << std::string(p->generation()*4, ' ');
         if (!p->is_head_node())
-          std::cerr << static_cast<const ranking::NodeValue<T>*>(p)->value();
+          os << value(p);
         else
-          std::cerr << "H";
-        std::cerr << ":   "
+          os << "H";
+        os << ":   "
                   << p->parent_ << " "
                   << p << " "
@@ -380 +379 @@
                   << p->right_ << "\n";
         if (p->is_head_node()==false) {
-          print(p->left_);
+          print(p->left_, os);
         }
         if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
-          std::cerr << "print error: " << p << "\n";
+          os << "print error: " << p << "\n";
           exit(1);
         }
@@ -495 +494 @@
         root_node() = element.release();
         root_node()->right_ = &impl_.head_;
+        root_node()->height_ = 1;
+        root_node()->size_ = 1;
         impl_.head_.left_ = root_node();
-        ++impl_.node_count_;
+
         YAT_ASSERT(root_node()->validate());
         YAT_ASSERT(impl_.head_.validate());
@@ -508 +509 @@
 
       // element right of root
-      if (!compare_(element->value(),
-                    static_cast<ranking::NodeValue<T>*>(x)->value())) {
+      if (!compare_(element->value(), value(x))) {
         // make new root parent of head
         impl_.head_.parent_ = element.release();
@@ -518 +518 @@
         impl_.head_.parent_->left_ = x;
         x->parent_ = impl_.head_.parent_;
-
-        ++impl_.node_count_;
+        YAT_ASSERT(x->size_ > 0);
+
+        impl_.head_.parent_->size_ = x->size_ + 1;
+        impl_.head_.parent_->height_ = x->height_ + 1;
+
         YAT_ASSERT(x->validate());
         YAT_ASSERT(impl_.head_.parent_);
@@ -533 +536 @@
       while (true) {
         parent = x;
-        if (compare_(element->value(),
-                     static_cast<ranking::NodeValue<T>*>(x)->value())) {
+        if (compare_(element->value(), value(x))) {
           x = x->left_;
           if (x == nullptr) {
             element->parent_ = parent;
             parent->left_ = element.release();
+            parent->increment_size();
+            parent->update_height();
             if (impl_.head_.left_ == parent)
               impl_.head_.left_ = parent->left_;
-            ++impl_.node_count_;
             YAT_ASSERT(validate());
             return result;
@@ -551 +554 @@
             element->parent_ = parent;
             parent->right_ = element.release();
-            ++impl_.node_count_;
+            parent->increment_size();
+            parent->update_height();
             YAT_ASSERT(validate());
             return result;
@@ -667 +671 @@
 
 
+    const T& value(const ranking::NodeBase* p) const
+    {
+      YAT_ASSERT(p);
+      YAT_ASSERT(!p->is_head_node());
+      return static_cast<const ranking::NodeValue<T>*>(p)->value();
+    }
+
+
     bool validate(void) const
     {
 #ifdef YAT_DEBUG_RANKING
-      return impl_.validate();
+      if (!impl_.validate())
+        return false;
+      bool ok = true;
+      size_t rank = 0;
+      for (auto it = cbegin(); it!=cend(); ++it) {
+        size_t r = ranking(it);
+        if (r != rank) {
+          std::cerr << "ranking: " << r << "; expected: " << rank << "\n";
+          std::cerr << "size: " << it.node_->size_ << "\n";
+          std::cerr << it.node_->parent_ << " "
+                    << it.node_->is_left_node() << " "
+                    << it.node_->is_right_node() << "\n---\n";
+          ok = false;
+        }
+        ++rank;
+      }
+      return ok;
 #else
       return true;
@@ -733 +761 @@
     last_node()->left_ = root->left_most();
     last_node()->parent_ = root;
-    impl_.node_count_ = other.size();
     YAT_ASSERT(validate());
     return root;
@@ -745 +772 @@
     YAT_ASSERT(x);
     ranking::NodeValue<T>* root = clone_node(x);
+    root->height_ = x->height_;
+    root->size_ = x->size_;
     YAT_ASSERT(root);
     root->parent_ = parent;
@@ -758 +787 @@
       while (x) {
         ranking::NodeValue<T>* y = clone_node(x);
+        y->height_ = x->height_;
+        y->size_ = x->size_;
         parent->left_ = y;
         y->parent_ = parent;
@@ -795 +826 @@
     YAT_ASSERT(p != end());
     const ranking::NodeBase* node = p.node_;
+    //    std::cerr << "erase_node: " << node << "\n";
     YAT_ASSERT(node);
 
     // two children
     if (node->left_ && node->right_) {
+      // When node has two branches, we take the most leftmost node in
+      // the right branch and place in nodes place.
       ranking::NodeBase* leftmost = node->right_->left_most();
       YAT_ASSERT(leftmost->left_ == nullptr);
-      if (leftmost->parent_ != node)
+
+      // If the leftmost node has a kid, we need to relink the kid
+      // with its grand parent
+      if (leftmost->parent_ != node) {
         impl_.relink(leftmost, leftmost->right_);
+      }
       impl_.relink(node, leftmost);
+      YAT_ASSERT(leftmost->left_ == node->left_);
+      YAT_ASSERT(!leftmost->left_ || leftmost->left_->parent_==leftmost);
+      leftmost->update_height();
+      leftmost->size_ =
+        1 + ranking::size(leftmost->left_) + ranking::size(leftmost->right_);
+      leftmost->parent_->decrement_size();
+      YAT_ASSERT(validate());
     }
     else {
       // single child node is simple, the child takes the node's place
       impl_.relink(node, node->left_ ? node->left_ : node->right_);
+      node->parent_->decrement_size();
+      node->parent_->update_height();
+      YAT_ASSERT(validate());
     }
     // FIXME we need to delete the node, but be careful to not delete
     // any of ots children; perhaps const_cast first?
 
-    --impl_.node_count_;
-    YAT_ASSERT(validate());
   }
 

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

@@ -63 +63 @@
     assert(head_.right_ == &head_);
     head_.parent_->right_ = &head_;
-    node_count_ = from.node_count_;
+    head_.height_ = from.head_.height_;
+    head_.size_ = from.head_.size_;
     from.reset();
     assert(validate());
@@ -90 +91 @@
         assert(!child->left_);
         child->left_ = node->left_;
+        if (node->left_)
+          node->left_->parent_ = child;
       }
       if (node->right_ && node->right_!=child) {
         assert(!child->right_);
         child->right_ = node->right_;
+        if (node->right_)
+          node->right_->parent_ = child;
       }
     }
@@ -105 +110 @@
 
 
+  size_t Impl::ranking(const NodeBase* node) const
+  {
+    if (node->is_head_node())
+      return size(node->parent_);
+
+    // root node
+    if (node->parent_ == nullptr)
+      return size(node->left_);
+
+    // The rank of the parent is the sum of the rank of the
+    // left->child, the child itself, and the size of the child's
+    // right branch.
+    if (node->is_left_node())
+      return ranking(node->parent_) - (1 + size(node->right_));
+
+    // right node
+    return ranking(node->parent_) + 1 + size(node->left_);
+  }
+
+
   void Impl::reset(void)
   {
@@ -111 +136 @@
     head_.left_ = &head_;
     head_.right_ = &head_;
-    node_count_ = 0;
+    // we don't count the head node
+    head_.height_ = 0;
+    head_.size_ = 0;
     assert(validate());
   }
@@ -118 +145 @@
   bool Impl::validate(void) const
   {
-    if (node_count_ == 0) {
-      assert(head_.parent_ == nullptr);
+    if (head_.parent_ == nullptr) {
       assert(head_.left_ == &head_);
       assert(head_.right_ == &head_);

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

@@ -52 +52 @@
       // corresponds to begin()
       NodeBase head_;
-      size_t node_count_;
       // typically only called with assert, YAT_ASSERT or similar
       bool validate(void) const;
+      // return number of nodes left of node, i.e., number of nodes
+      // with value less than node->value.
+      size_t ranking(const NodeBase* node) const;
       void reset(void);
       /*

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

@@ -25 +25 @@
 // This is a private file used by yat/utility/Ranking.h
 
+#include <cstddef>
+
 namespace theplu {
 namespace yat {
@@ -42 +44 @@
       NodeBase* left_;
       NodeBase* right_;
+      unsigned int height_; // max distance to leaf (plus 1)
+      // number of total offsprings including myself
+      size_t size_;
 
       // return 0 for root, 1 for its children, etc
       int generation(void) const;
+
+      // increase size of node and parent node, recursively.
+      void increment_size(void);
+      // decrease size of node and parent node, recursively.
+      void decrement_size(void);
+
+      void update_height(void);
 
       // return true if head node
@@ -66 +78 @@
       bool recursive_validate(void) const;
     };
+
+    size_t height(const NodeBase* node);
+    size_t size(const NodeBase* node);
+
   } // end of namespace ranking