Changeset 4069

Timestamp:

Aug 6, 2021, 12:02:23 PM (11 months ago)

Author:

Peter

Message:

implement copy and move constructors/assignment

Location:

branches/kendall-score

Files:

• test/ranking.cc (modified) (4 diffs)
• yat/utility/Ranking.h (modified) (8 diffs)
• yat/utility/ranking/Impl.cc (modified) (2 diffs)
• yat/utility/ranking/Impl.h (modified) (2 diffs)
• yat/utility/ranking/Iterator.h (modified) (2 diffs)

branches/kendall-score/test/ranking.cc

@@ -33 +33 @@
 void test1(test::Suite& suite)
 {
+  suite.out() << YAT_TEST_PROLOGUE;
   suite.out() << "Constructor(0)\n";
   utility::Ranking<double> ranking;
@@ -120 +121 @@
 void test2(test::Suite& suite)
 {
-  suite.out() << "=== " << __func__ << " ===\n";
+  suite.out() << YAT_TEST_PROLOGUE;
   // mimick how Ranking is used in Kendall::score
   utility::Ranking<double> ranking;
@@ -169 +170 @@
 
 
+void test_copy(test::Suite& suite)
+{
+  suite.out() << YAT_TEST_PROLOGUE;
+  utility::Ranking<double> ranking;
+  ranking.insert(0);
+  ranking.insert(1);
+  ranking.insert(-1);
+
+  suite.out() << "test copy constructor\n";
+  utility::Ranking<double> ranking2(ranking);
+  int n = std::distance(ranking.begin(), ranking.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "ranking distance: " << n << "\n";
+  }
+
+  n = std::distance(ranking2.begin(), ranking2.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: copy constructor failed\n";
+    suite.err() << "ranking2 distance: " << n << "\n";
+    for (auto it = ranking2.cbegin(); it!=ranking2.cend(); ++it)
+      suite.err() << "value: " << *it << "\n";
+  }
+
+  utility::Ranking<double> ranking3;
+  ranking3.insert(10);
+  suite.out() << "test copy assignment\n";
+  ranking3 = ranking2;
+  n = std::distance(ranking3.begin(), ranking3.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: assignment failed\n";
+    suite.err() << "ranking3 distance: " << n << "\n";
+  }
+
+  suite.out() << "test move constructor\n";
+  utility::Ranking<double> ranking4(std::move(ranking3));
+  n = std::distance(ranking4.begin(), ranking4.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: move constructor failed\n";
+    suite.err() << "ranking4 distance: " << n << "\n";
+  }
+
+  suite.out() << "test move assignment\n";
+  ranking4 = std::move(ranking2);
+  n = std::distance(ranking4.begin(), ranking4.end());
+  if (n != 3) {
+    suite.add(false);
+    suite.err() << "error: move assignment failed\n";
+    suite.err() << "ranking4 distance: " << n << "\n";
+  }
+}
+
+
 int main(int argc, char* argv[])
 {
@@ -175 +232 @@
     test1(suite);
     test2(suite);
+    test_copy(suite);
   }
   catch (std::exception& e) {

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

@@ -34 +34 @@
 #include <memory>
 
+#include <iostream> // debug
 namespace theplu {
 namespace yat {
@@ -79 +80 @@
        \brief Copy constructor
      */
-    Ranking(const Ranking& other)
-      : compare_(other.compare())
-    {
-      if (!other.empty())
-        impl_.head_.parent_ = copy(other);
-    }
+    Ranking(const Ranking& other);
 
     /**
        \brief move constructor
      */
-    Ranking(Ranking&& other) = default;
+    Ranking(Ranking&& other);
 
     /**
@@ -330 +326 @@
     ranking::Impl impl_;
 
+    void clear(void)
+    {
+      if (size()) {
+        YAT_ASSERT(first_node() != &impl_.head_);
+        erase(first_node());
+      }
+      impl_.reset();
+    }
+
+    // return a copy of x but with children and parent set to nullptr.
     ranking::NodeValue<T>*
-    clone_node(const ranking::NodeValue<T>* x) const
-    {
-      YAT_ASSERT(0 && "implement me");
-      YAT_ASSERT(x);
-      ranking::NodeValue<T>* tmp = new ranking::NodeValue<T>(*x);
-      tmp->left_ = nullptr;
-      tmp->right_ = nullptr;
-      return tmp;
-    }
-
-
-    ranking::NodeValue<T>* copy(const Ranking& other)
-    {
-      YAT_ASSERT(0 && "implement me");
-      ranking::NodeValue<T>* root = copy(other.first_node(), last_node());
-      //impl_.left_ = root->left_most();
-      //impl_.right_ = root->right_most();
-      //size_ = other.size_;
-      return root;
-    }
-
-
+    clone_node(const ranking::NodeValue<T>* x) const;
+
+    /**
+       copy data in other.Impl_ into impl_
+
+       Basically copy constructor of Impl but nodes (except for head
+       node) are copied as NodeValue<T> and Impl is not aware of T.
+     */
+    ranking::NodeValue<T>* copy(const Ranking& other);
+
+    /**
+       Create a copy of root and return it
+     */
     ranking::NodeValue<T>*
-    copy(const ranking::NodeValue<T>* x, ranking::NodeBase* p)
-    {
-      YAT_ASSERT(0 && "implement me");
-      ranking::NodeValue<T>* top = clone_node(x);
-      top->parent_ = p;
-      try {
-        if (x->right_)
-          top->right_ = copy(right(x), top);
-        p = top;
-        x = left(x);
-        while (x != 0) {
-          ranking::NodeValue<T>* y = clone_node(x);
-          p->left_ = y;
-          y->parent_ = p;
-          if (x->right_)
-            y->right_ = copy(right(x), y);
-          p = y;
-          x = left(x);
-        }
-      }
-      catch (std::exception& e) {
-        // cleanup
-        erase(top);
-        std::rethrow_exception(std::current_exception());
-      }
-      return top;
-    }
+    copy(const ranking::NodeValue<T>* root, ranking::NodeBase* h) const;
 
 
@@ -443 +414 @@
 
     // delete x and its offsprings
-    void erase(ranking::NodeValue<T>* x)
-    {
-      YAT_ASSERT(0 && "implement me");
+    void erase(ranking::NodeValue<T>* x) const
+    {
       while (x) {
-        erase(right(x));
+        if (x->right_ && x->right_ !=  &impl_.head_)
+          erase(right(x));
         ranking::NodeValue<T>* tmp = left(x);
         delete x;
@@ -533 +504 @@
 
 
-    iterator insert(std::unique_ptr<ranking::NodeValue<T>>&& element,
-                    ranking::NodeBase* parent, ranking::NodeBase*& child)
-    {
-      YAT_ASSERT(0 && "implement me");
-      YAT_ASSERT(parent);
-      YAT_ASSERT(child==parent->left_ || child==parent->right_);
-      // if child is null, assign element
-      if (!child) {
-        child = element.release();
-        child->parent_ = parent;
-        YAT_ASSERT(child==parent->left_ || child==parent->right_);
-        ++impl_.node_count_;
-        return iterator(child);
-      }
-      if (compare_(element->value(),
-                   static_cast<ranking::NodeValue<T>*>(child)->value()))
-        return insert(std::move(element), child, child->left_);
-      return insert(std::move(element), child, child->right_);
-    }
-
-
     const_iterator
     lower_bound(const ranking::NodeValue<T>* x, const ranking::NodeBase* y,
@@ -589 +539 @@
     const ranking::NodeBase* const root_node(void) const
     {
-      YAT_ASSERT(0 && "implement me");
       return impl_.head_.parent_;
     }
@@ -604 +553 @@
       return impl_.head_.left_;
     }
+
+
+    const ranking::NodeValue<T>* parent(const ranking::NodeBase* x) const
+    {
+      YAT_ASSERT(x);
+      YAT_ASSERT(x->parent_);
+      YAT_ASSERT(x->parent_ != &impl_.head_);
+      return static_cast<const ranking::NodeValue<T>*>(x->parent_);
+    }
+
+
+    ranking::NodeValue<T>* parent(ranking::NodeBase* x) const
+    {
+      YAT_ASSERT(x);
+      YAT_ASSERT(x->parent_);
+      YAT_ASSERT(x->parent_ != &impl_.head_);
+      return static_cast<ranking::NodeValue<T>*>(x->parent_);
+    }
+
 
     /*
@@ -648 +616 @@
       return true;
 #endif
-
-    }
-
+    }
   };
+
+
+  // implementations
+  template<typename T, typename Compare>
+  Ranking<T,Compare>::Ranking(const Ranking& other)
+    : compare_(other.compare())
+  {
+    if (!other.empty())
+      root_node() = copy(other);
+    YAT_ASSERT(validate());
+  }
+
+
+  template<typename T, typename Compare>
+  Ranking<T,Compare>::Ranking(Ranking&& other)
+    : compare_(std::move(other.compare())), impl_(std::move(other.impl_))
+  {
+    YAT_ASSERT(validate());
+  }
+
+
+  template<typename T, typename Compare>
+  Ranking<T, Compare>&
+  Ranking<T, Compare>::operator=(const Ranking& other)
+  {
+    if (this != &other) {
+      Ranking tmp(other);
+      *this = std::move(tmp);
+    }
+    return *this;
+  }
+
+
+  template<typename T, typename Compare>
+  Ranking<T, Compare>&
+  Ranking<T, Compare>::operator=(Ranking&& other)
+  {
+    clear();
+    compare_ = std::move(other.compare_);
+    impl_ = std::move(other.impl_);
+    return *this;
+  }
+
+
+  template<typename T, typename Compare>
+  ranking::NodeValue<T>* Ranking<T,Compare>::copy(const Ranking& other)
+  {
+    YAT_ASSERT(validate());
+    YAT_ASSERT(impl_.head_.parent_ == nullptr);
+    YAT_ASSERT(other.first_node());
+    ranking::NodeValue<T>* root = copy(other.first_node(), last_node());
+    root->parent_ = nullptr;
+    root->right_ = last_node();
+    last_node()->left_ = root->left_most();
+    last_node()->parent_ = root;
+    impl_.node_count_ = other.size();
+    YAT_ASSERT(validate());
+    return root;
+  }
+
+
+  template<typename T, typename Compare>
+  ranking::NodeValue<T>*
+  Ranking<T,Compare>::copy(const ranking::NodeValue<T>* x,
+                           ranking::NodeBase* parent) const
+  {
+    YAT_ASSERT(x);
+    ranking::NodeValue<T>* root = clone_node(x);
+    YAT_ASSERT(root);
+    root->parent_ = parent;
+    try {
+      if (x->right_ && !x->right_->is_head_node()) {
+        YAT_ASSERT(x != right(x));
+        YAT_ASSERT(x->right_ != &impl_.head_);
+        root->right_ = copy(right(x), root);
+      }
+
+      parent = root;
+      x = left(x);
+      while (x) {
+        ranking::NodeValue<T>* y = clone_node(x);
+        parent->left_ = y;
+        y->parent_ = parent;
+        if (x->right_) {
+          YAT_ASSERT(x->right_ != &impl_.head_);
+          y->right_ = copy(right(x), y);
+        }
+        parent = y;
+        x = left(x);
+      }
+    }
+    catch (std::exception& e) {
+      erase(root);
+      std::rethrow_exception(std::current_exception());
+    }
+
+    return root;
+  }
+
+
+  template<typename T, typename Compare>
+  ranking::NodeValue<T>*
+  Ranking<T,Compare>::clone_node(const ranking::NodeValue<T>* x) const
+  {
+    YAT_ASSERT(x);
+    ranking::NodeValue<T>* res = new ranking::NodeValue<T>(x->value());
+    res->left_ = nullptr;
+    res->right_ = nullptr;
+    res->parent_ = nullptr;
+    return res;
+  }
 
 }}} // of namespace utility, yat, and theplu

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

@@ -39 +39 @@
 
 
-  Impl::Impl(Impl&& other)
+  Impl::Impl(Impl&& from)
   {
-    assert(0 && "implement me");
-    if (other.head_.parent_ == nullptr)
-      reset();
-    else
-      move_data(std::move(other));
+    reset();
+    if (from.head_.parent_)
+      move_data(std::move(from));
+  }
+
+
+  Impl& Impl::operator=(Impl&& rhs)
+  {
+    assert(!head_.parent_);
+    move_data(std::move(rhs));
+    assert(validate());
+    return *this;
   }
 
@@ -51 +58 @@
   void Impl::move_data(Impl&& from)
   {
-    assert(0 && "implement me");
+    assert(head_.parent_ == nullptr);
     head_.parent_ = from.head_.parent_;
     head_.left_ = from.head_.left_;
-    head_.right_ = from.head_.right_;
-    head_.parent_->parent_ = &head_;
+    assert(head_.right_ == &head_);
+    head_.parent_->right_ = &head_;
     node_count_ = from.node_count_;
     from.reset();
+    assert(validate());
   }
 

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

@@ -45 +45 @@
       Impl(Impl&& other);
       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
@@ -53 +54 @@
       // typically only called with assert, YAT_ASSERT or similar
       bool validate(void) const;
+      void reset(void);
     private:
       void move_data(Impl&&);
-      void reset(void);
     };
   } // end of namespace ranking

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

@@ -34 +34 @@
 #include <iterator>
 
+#include <iostream> // debug
 namespace theplu {
 namespace yat {
@@ -64 +65 @@
     Iterator<T>::Iterator(const NodeBase* node)
       : node_(node)
-    {}
+    {
+    }