From 5f4229227fe747ce08b1f296596343d9fdf79535 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 2 Oct 2018 16:05:31 +0000 Subject: Code review : Factorize copy_from and move_from for copy/move assignment/ctor Make rec_copy private Factorize root members recursive deletion In move, test that (map_el.second.children() != &(complex_source.root_)) instead of (map_el.second.children()->oncles == &(complex_source.root_)) => more efficient Support self copy assignment detection No more use of std::swap in move assignment git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/simplex_tree_fix_vincent@3924 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 3aa3727294e54b4ffbc48c3cdb901facf3cd59d7 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 167 ++++++++++----------- .../test/simplex_tree_ctor_and_move_unit_test.cpp | 10 ++ 2 files changed, 89 insertions(+), 88 deletions(-) diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 20b527a2..4df4e529 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -296,57 +296,22 @@ class Simplex_tree { dimension_(-1) { } /** \brief User-defined copy constructor reproduces the whole tree structure. */ - Simplex_tree(const Simplex_tree& complex_source) - : null_vertex_(complex_source.null_vertex_), - root_(nullptr, null_vertex_, complex_source.root_.members_), - filtration_vect_(), - dimension_(complex_source.dimension_) { + Simplex_tree(const Simplex_tree& complex_source) { #ifdef DEBUG_TRACES std::cout << "Simplex_tree copy constructor" << std::endl; #endif // DEBUG_TRACES - auto root_source = complex_source.root_; - rec_copy(&root_, &root_source); - } - - /** \brief depth first search, inserts simplices when reaching a leaf. */ - void rec_copy(Siblings *sib, Siblings *sib_source) { - for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin(); - sh != sib->members().end(); ++sh, ++sh_source) { - if (has_children(sh_source)) { - Siblings * newsib = new Siblings(sib, sh_source->first); - newsib->members_.reserve(sh_source->second.children()->members().size()); - for (auto & child : sh_source->second.children()->members()) - newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration())); - rec_copy(newsib, sh_source->second.children()); - sh->second.assign_children(newsib); - } - } + copy_from(complex_source); } /** \brief User-defined move constructor relocates the whole tree structure. * \exception std::invalid_argument In debug mode, if the complex_source is invalid. */ - Simplex_tree(Simplex_tree && complex_source) - : null_vertex_(std::move(complex_source.null_vertex_)), - root_(std::move(complex_source.root_)), - filtration_vect_(std::move(complex_source.filtration_vect_)), - dimension_(std::move(complex_source.dimension_)) { + Simplex_tree(Simplex_tree && complex_source) { #ifdef DEBUG_TRACES std::cout << "Simplex_tree move constructor" << std::endl; #endif // DEBUG_TRACES - // Need to update root members (children->oncles and children need to point on the new root pointer) - for (auto& map_el : root_.members()) { - if (map_el.second.children()->oncles() == &(complex_source.root_)) { - // reset children->oncles with the moved root_ pointer value - map_el.second.children()->oncles_ = &root_; - } else { - // if simplex is of dimension 0, oncles_ shall be nullptr - GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr, - std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree")); - // and children points on root_ - to be moved - map_el.second.assign_children(&root_); - } - } + move_from(complex_source); + // just need to set dimension_ on source to make it available again // (filtration_vect_ and members are already set from the move) complex_source.dimension_ = -1; @@ -354,11 +319,7 @@ class Simplex_tree { /** \brief Destructor; deallocates the whole tree structure. */ ~Simplex_tree() { - for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { - if (has_children(sh)) { - rec_delete(sh->second.children()); - } - } + root_members_recursive_deletion(); } /** \brief User-defined copy assignment reproduces the whole tree structure. */ @@ -367,25 +328,13 @@ class Simplex_tree { #ifdef DEBUG_TRACES std::cout << "Simplex_tree copy assignment" << std::endl; #endif // DEBUG_TRACES - null_vertex_ = complex_source.null_vertex_; - filtration_vect_.clear(); - dimension_ = complex_source.dimension_; - auto root_source = complex_source.root_; - - // We start by deleting root_ if not empty - for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { - if (has_children(sh)) { - rec_delete(sh->second.children()); - } - } + // Self-assignment detection + if (&complex_source != this) { + // We start by deleting root_ if not empty + root_members_recursive_deletion(); - // root members copy - root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end()); - // Needs to reassign children - for (auto& map_el : root_.members()) { - map_el.second.assign_children(&root_); + copy_from(complex_source); } - rec_copy(&root_, &root_source); return *this; } @@ -399,37 +348,79 @@ class Simplex_tree { #endif // DEBUG_TRACES // Self-assignment detection if (&complex_source != this) { - std::swap( null_vertex_, complex_source.null_vertex_ ); - std::swap( root_, complex_source.root_ ); - std::swap( filtration_vect_, complex_source.filtration_vect_ ); - std::swap( dimension_, complex_source.dimension_ ); - - // Need to update root members (children->oncles and children need to point on the new root pointer) - for (auto& map_el : root_.members()) { - if (map_el.second.children()->oncles() == &(complex_source.root_)) { - // reset children->oncles with the moved root_ pointer value - map_el.second.children()->oncles_ = &root_; - } else { - // if simplex is of dimension 0, oncles_ shall be nullptr - GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr, - std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree")); - // and children points on root_ - to be moved - map_el.second.assign_children(&root_); - } - } - // complex_source root_ deletion - for (auto sh = complex_source.root_.members().begin(); sh != complex_source.root_.members().end(); ++sh) { - if (has_children(sh)) { - rec_delete(sh->second.children()); - } - } - complex_source.root_.members().clear(); - complex_source.dimension_ = -1; + // root_ deletion in case it was not empty + root_members_recursive_deletion(); + + move_from(complex_source); } return *this; } /** @} */ // end constructor/destructor + private: + // Copy from complex_source to "this" + void copy_from(const Simplex_tree& complex_source) { + null_vertex_ = complex_source.null_vertex_; + filtration_vect_.clear(); + dimension_ = complex_source.dimension_; + auto root_source = complex_source.root_; + + // root members copy + root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end()); + // Needs to reassign children + for (auto& map_el : root_.members()) { + map_el.second.assign_children(&root_); + } + rec_copy(&root_, &root_source); + } + + /** \brief depth first search, inserts simplices when reaching a leaf. */ + void rec_copy(Siblings *sib, Siblings *sib_source) { + for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin(); + sh != sib->members().end(); ++sh, ++sh_source) { + if (has_children(sh_source)) { + Siblings * newsib = new Siblings(sib, sh_source->first); + newsib->members_.reserve(sh_source->second.children()->members().size()); + for (auto & child : sh_source->second.children()->members()) + newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration())); + rec_copy(newsib, sh_source->second.children()); + sh->second.assign_children(newsib); + } + } + } + + // Move from complex_source to "this" + void move_from(Simplex_tree& complex_source) { + null_vertex_ = std::move(complex_source.null_vertex_); + root_ = std::move(complex_source.root_); + filtration_vect_ = std::move(complex_source.filtration_vect_); + dimension_ = std::move(complex_source.dimension_); + + // Need to update root members (children->oncles and children need to point on the new root pointer) + for (auto& map_el : root_.members()) { + if (map_el.second.children() != &(complex_source.root_)) { + // reset children->oncles with the moved root_ pointer value + map_el.second.children()->oncles_ = &root_; + } else { + // if simplex is of dimension 0, oncles_ shall be nullptr + GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr, + std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree")); + // and children points on root_ - to be moved + map_el.second.assign_children(&root_); + } + } + } + + // delete all root_.members() recursively + void root_members_recursive_deletion() { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { + if (has_children(sh)) { + rec_delete(sh->second.children()); + } + } + root_.members().clear(); + } + // Recursive deletion void rec_delete(Siblings * sib) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { diff --git a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp index 6c27a458..e729cf00 100644 --- a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp @@ -88,6 +88,11 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te BOOST_CHECK(st == st4); BOOST_CHECK(st3 == st); + st = st; + print_simplex_filtration(st4, "Third self copy assignment from the default Simplex_tree"); + + BOOST_CHECK(st3 == st); + std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF MOVE CONSTRUCTOR" << std::endl; Simplex_tree st5(std::move(st1)); @@ -124,4 +129,9 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_te BOOST_CHECK(st == st8); BOOST_CHECK(st7 == st); + st = std::move(st); + print_simplex_filtration(st, "Third self move assignment from the default Simplex_tree"); + + BOOST_CHECK(st7 == st); + } -- cgit v1.2.3