Changeset 4070

Timestamp:

Aug 9, 2021, 8:32:59 AM (18 months ago)

Author:

Peter

Message:

refs #710; add erase functions

Location:

branches/kendall-score

Files:

• test/ranking.cc (modified) (2 diffs)
• yat/utility/Ranking.h (modified) (13 diffs)
• yat/utility/ranking/Impl.cc (modified) (4 diffs)
• yat/utility/ranking/Impl.h (modified) (2 diffs)
• yat/utility/ranking/Iterator.h (modified) (4 diffs)
• yat/utility/ranking/NodeBase.h (modified) (1 diff)

branches/kendall-score/test/ranking.cc

@@ -226 +226 @@
 
 
+void test_erase(test::Suite& suite)
+{
+  suite.out() << YAT_TEST_PROLOGUE;
+
+  utility::Ranking<double> ranking;
+  ranking.insert(1);
+  ranking.insert(2);
+  ranking.insert(3);
+  auto it = ranking.find(2);
+  suite.out() << "test erase(iterator)\n";
+  ranking.erase(it);
+  int n = ranking.size();
+  if (n != 2) {
+    suite.add(false);
+    suite.err() << "error: size() = " << n << "; expected 2\n";
+  }
+  n = std::distance(ranking.begin(), ranking.end());
+  if (n != 2) {
+    suite.add(false);
+    suite.err() << "error: distance = " << n << "; expected 2\n";
+  }
+
+  suite.out() << "test erase(value)\n";
+  ranking.insert(2);
+  ranking.erase(2);
+  n = ranking.size();
+  if (n != 2) {
+    suite.add(false);
+    suite.err() << "error: size() = " << n << "; expected 2\n";
+  }
+  n = std::distance(ranking.begin(), ranking.end());
+  if (n != 2) {
+    suite.add(false);
+    suite.err() << "error: distance = " << n << "; expected 2\n";
+  }
+
+  suite.out() << "test erase(iterator, iterator)\n";
+  ranking.insert(2);
+  ranking.insert(4);
+  ranking.insert(0);
+  auto lower = ranking.lower_bound(1);
+  auto upper = ranking.find(3);
+  // erase { 1, 2}
+  ranking.erase(lower, upper);
+  n = ranking.size();
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: size() = " << n << "; expected 3\n";
+  }
+  n = std::distance(ranking.begin(), ranking.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: distance = " << n << "; expected 3\n";
+  }
+}
+
+
 int main(int argc, char* argv[])
 {
@@ -233 +290 @@
     test2(suite);
     test_copy(suite);
+    test_erase(suite);
   }
   catch (std::exception& e) {

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

@@ -42 +42 @@
      Class is a binary tree with the special extension that it allow
      fast access to the rank of an element in the tree.
+
+     \since New in yat 0.19
    */
   template<typename T, class Compare = std::less<T> >
@@ -206 +208 @@
 
     /**
+       Remove all nodes
+     */
+    void clear(void)
+    {
+      if (size()) {
+        YAT_ASSERT(first_node() != &impl_.head_);
+        erase(first_node());
+      }
+      impl_.reset();
+    }
+
+
+    /**
        access comparison function which is used to sort elements
      */
@@ -222 +237 @@
     }
 
+
+    /**
+       Remove element pointed to by \c position.
+
+       \return An iterator pointing to the element that follows the
+       last element removed.
+     */
+    iterator erase(const_iterator position);
+
+    /**
+       Erase all elements that are equivalent with \c value
+       \return number of elements removed
+     */
+    size_type erase(const T& value);
+
+    /**
+       Remove elements in range [first, last).
+
+       \return An iterator pointing to the element that follows the
+       last element removed.
+     */
+    iterator erase(const_iterator first, const_iterator last);
 
     /**
@@ -326 +363 @@
     ranking::Impl impl_;
 
-    void clear(void)
-    {
-      if (size()) {
-        YAT_ASSERT(first_node() != &impl_.head_);
-        erase(first_node());
-      }
-      impl_.reset();
+    void print(const ranking::NodeBase* p) const
+    {
+      if (p) {
+        if (p->is_head_node()==false) {
+          print(p->right_);
+        }
+        std::cerr << std::string(p->generation()*4, ' ');
+        if (!p->is_head_node())
+          std::cerr << static_cast<const ranking::NodeValue<T>*>(p)->value();
+        else
+          std::cerr << "H";
+        std::cerr << ":   "
+                  << p->parent_ << " "
+                  << p << " "
+                  << p->left_ << " "
+                  << p->right_ << "\n";
+        if (p->is_head_node()==false) {
+          print(p->left_);
+        }
+        if (p->parent_ && !p->is_left_node() && !p->is_right_node()) {
+          std::cerr << "print error: " << p << "\n";
+          exit(1);
+        }
+      }
     }
 
@@ -353 +407 @@
     copy(const ranking::NodeValue<T>* root, ranking::NodeBase* h) const;
 
+    /**
+       Remove node position is pointing to
+     */
+    void erase_node(const_iterator position);
 
     // return the root node
@@ -619 +677 @@
   };
 
+  // avoid doxygen reading code below as it has problems to to match
+  // declarations and implementations unless matching perfectly.
+
+  /// \cond IGNORE_DOXYGEN
 
   // implementations
-  template<typename T, typename Compare>
-  Ranking<T,Compare>::Ranking(const Ranking& other)
+  template<typename T, typename C>
+  Ranking<T,C>::Ranking(const Ranking& other)
     : compare_(other.compare())
   {
@@ -631 +693 @@
 
 
-  template<typename T, typename Compare>
-  Ranking<T,Compare>::Ranking(Ranking&& other)
+  template<typename T, typename C>
+  Ranking<T,C>::Ranking(Ranking&& other)
     : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
   {
@@ -639 +701 @@
 
 
-  template<typename T, typename Compare>
-  Ranking<T, Compare>&
-  Ranking<T, Compare>::operator=(const Ranking& other)
+  template<typename T, typename C>
+  Ranking<T, C>& Ranking<T, C>::operator=(const Ranking& other)
   {
     if (this != &other) {
@@ -651 +712 @@
 
 
-  template<typename T, typename Compare>
-  Ranking<T, Compare>&
-  Ranking<T, Compare>::operator=(Ranking&& other)
+  template<typename T, typename C>
+  Ranking<T, C>& Ranking<T, C>::operator=(Ranking&& other)
   {
     clear();
@@ -662 +722 @@
 
 
-  template<typename T, typename Compare>
-  ranking::NodeValue<T>* Ranking<T,Compare>::copy(const Ranking& other)
+  template<typename T, typename C>
+  ranking::NodeValue<T>* Ranking<T,C>::copy(const Ranking& other)
   {
     YAT_ASSERT(validate());
@@ -679 +739 @@
 
 
-  template<typename T, typename Compare>
-  ranking::NodeValue<T>*
-  Ranking<T,Compare>::copy(const ranking::NodeValue<T>* x,
-                           ranking::NodeBase* parent) const
+  template<typename T, typename C>
+  ranking::NodeValue<T>* Ranking<T,C>::copy(const ranking::NodeValue<T>* x,
+                                            ranking::NodeBase* parent) const
   {
     YAT_ASSERT(x);
@@ -718 +777 @@
 
 
-  template<typename T, typename Compare>
+  template<typename T, typename C>
   ranking::NodeValue<T>*
-  Ranking<T,Compare>::clone_node(const ranking::NodeValue<T>* x) const
+  Ranking<T,C>::clone_node(const ranking::NodeValue<T>* x) const
   {
     YAT_ASSERT(x);
@@ -730 +789 @@
   }
 
+
+  template<typename T, typename C>
+  void Ranking<T, C>::erase_node(typename Ranking<T, C>::const_iterator p)
+  {
+    YAT_ASSERT(p != end());
+    const ranking::NodeBase* node = p.node_;
+    YAT_ASSERT(node);
+
+    // two children
+    if (node->left_ && node->right_) {
+      ranking::NodeBase* leftmost = node->right_->left_most();
+      YAT_ASSERT(leftmost->left_ == nullptr);
+      if (leftmost->parent_ != node)
+        impl_.relink(leftmost, leftmost->right_);
+      impl_.relink(node, leftmost);
+    }
+    else {
+      // single child node is simple, the child takes the node's place
+      impl_.relink(node, node->left_ ? node->left_ : node->right_);
+    }
+    // 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());
+  }
+
+
+  template<typename T, typename C>
+  typename Ranking<T, C>::iterator
+  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator p)
+  {
+    YAT_ASSERT(p != end());
+    const_iterator res = p;
+    ++res;
+    erase_node(p);
+    // iterator and const_iterator are same at the moment
+    return res;
+  }
+
+
+  template<typename T, typename C>
+  typename Ranking<T, C>::size_type Ranking<T, C>::erase(const T& value)
+  {
+    auto it = lower_bound(value);
+    typename Ranking<T, C>::size_type n = 0;
+    while (it!=end() && !compare_(value, *it)) {
+      erase_node(it++);
+      ++n;
+    }
+    return n;
+  }
+
+
+  template<typename T, typename C>
+  typename Ranking<T, C>::iterator
+  Ranking<T, C>::erase(typename Ranking<T, C>::const_iterator first,
+                       typename Ranking<T, C>::const_iterator last)
+  {
+    if (first == cbegin() && last == cend())
+      clear();
+    else
+      while (first != last) {
+        erase_node(first++);
+      }
+    return last;
+  }
+
+
+  template<typename T, typename C>
+  typename Ranking<T, C>::const_iterator Ranking<T, C>::find(const T& x) const
+  {
+    auto it = lower_bound(x);
+    if (it != cend() && compare_(x, *it))
+      it = cend();
+    return it;
+  }
+
+  /// \endcond
+
 }}} // of namespace utility, yat, and theplu
 #endif

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

@@ -69 +69 @@
 
 
+  void Impl::relink(const NodeBase* node, NodeBase* child)
+  {
+    assert(node->parent_);
+    assert(node != &head_);
+    assert(child != &head_);
+
+    // make child the child of node's parent
+    if (node->is_left_node())
+      node->parent_->left_ = child;
+    else if (node->is_right_node())
+      node->parent_->right_ = child;
+
+    // make node's parent the parent of child
+    if (child)
+      child->parent_ = node->parent_;
+
+    // inherit the kids
+    if (child) {
+      if (node->left_ && node->left_!=child) {
+        assert(!child->left_);
+        child->left_ = node->left_;
+      }
+      if (node->right_ && node->right_!=child) {
+        assert(!child->right_);
+        child->right_ = node->right_;
+      }
+    }
+
+    // update pointer to left_most node
+    if (head_.left_ == node) {
+      head_.left_ = child ? child : node->parent_;
+    }
+    assert(child==nullptr || child->is_left_node() || child->is_right_node());
+  }
+
+
   void Impl::reset(void)
   {
@@ -92 +128 @@
       assert(head_.left_);
       if (head_.parent_->right_ != &head_) {
-        std::cerr << "head.parent->right != head\n";
         return false;
       }
@@ -98 +133 @@
 
     if (head_.parent_) {
+      if (head_.parent_->left_most() != head_.left_) {
+        std::cerr << "head_.left incorrect\n";
+        return false;
+      }
       if (!head_.parent_->recursive_validate())
         return false;
@@ -103 +142 @@
     else if (!head_.validate())
       return false;
+
     return true;
   }

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

@@ -46 +46 @@
       Impl& operator=(const Impl& rhs) = delete;
       Impl& operator=(Impl&& rhs);
+
       // Head is the only node with no value. Its parent is the root
       // node and the rest of the tree is in the left branch from the
@@ -55 +56 @@
       bool validate(void) const;
       void reset(void);
+      /*
+        \brief replace node with child
+
+       Function assumes that child can replace node without collision
+       or destrying the order in the tree, which means
+       if there is a node->left its value is <= child->value
+       if there is a node->right its value is <= child->value
+       if there is a node->left (ecl child) there is no child->left
+       if there is a node->right (excl child) there is no child->right
+      */
+      void relink(const NodeBase* node, NodeBase* child);
     private:
       void move_data(Impl&&);

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

@@ -52 +52 @@
     public:
       explicit Iterator(const NodeBase* node = nullptr);
+      const NodeBase* node_;
     private:
-      const NodeBase* node_;
       friend class boost::iterator_core_access;
       const T& dereference(void) const;
@@ -73 +73 @@
     {
       YAT_ASSERT(node_);
+      YAT_ASSERT(node_->is_head_node()==false);
       // All nodes are NodeValue except head which is pointee of end
       // iterator and not dereferencable
@@ -95 +96 @@
         return;
       }
+      // since node_ is not root, it must have a parent and be either
+      // left or right.
+      YAT_ASSERT(node_->parent_);
+      YAT_ASSERT(node_->is_left_node() || node_->is_right_node());
 
       // If we have a right branch, go to the leftmost leaf in it.
@@ -106 +111 @@
       const NodeBase* child = node_;
       YAT_ASSERT(child->parent_);
+      YAT_ASSERT(child->is_left_node() || child->is_right_node());
       while (child->is_right_node()) {
         YAT_ASSERT(!child->is_left_node());

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

@@ -43 +43 @@
       NodeBase* right_;
 
+      // return 0 for root, 1 for its children, etc
+      int generation(void) const;
+
       // return true if head node
       bool is_head_node(void) const;