URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena ChangeLog: 2007-11-05 Guillaume Duhamel <guillaume.duhamel@lrde.epita.fr> Add method delete_node into tree. * mln/util/tree.hh: Add method which delete a node in a tree and add his child into the parent. * tests/tree_delete_node.cc: New test for it. --- mln/util/tree.hh | 53 ++++++++++++++++++++++++++++++++++- tests/tree_delete_node.cc | 69 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 120 insertions(+), 2 deletions(-) Index: trunk/milena/tests/tree_delete_node.cc =================================================================== --- trunk/milena/tests/tree_delete_node.cc (revision 0) +++ trunk/milena/tests/tree_delete_node.cc (revision 1432) @@ -0,0 +1,69 @@ +// Copyright (C) 2007 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/*! + * \file tests/tree_delete_node.cc + * + * \brief test of mln::util::tree + * + */ + +#include <mln/util/tree.hh> +#include <mln/core/contract.hh> + +int main (void) +{ + using namespace mln; + + unsigned elt1 = 1; + unsigned elt2 = 2; + unsigned elt3 = 3; + unsigned elt4 = 4; + unsigned elt5 = 5; + unsigned elt6= 42; + + util::node<unsigned> node(elt1); + util::node<unsigned>* node2 = node.add_child(elt2); + node.add_child(elt3); +// util::node<unsigned>* node2 = node.search(elt2); + mln_assertion(node2); + node2->add_child(elt4); + node2->add_child(elt5); + util::node<unsigned>* node3 = node.search(elt4); + mln_assertion(node3); + node3 = node2->search(elt1); + mln_assertion(!node3); + util::tree<unsigned>* tre = new util::tree<unsigned>(&node); + mln_assertion(tre); + tre->add_tree_up(elt6); + mln_assertion (tre->check_consistency()); + std::cout << "before delete" << std::endl; + node.print (0); + std::cout << "after delete" << std::endl; + node2->delete_node(); + node.print (0); +} Index: trunk/milena/mln/util/tree.hh =================================================================== --- trunk/milena/mln/util/tree.hh (revision 1431) +++ trunk/milena/mln/util/tree.hh (revision 1432) @@ -30,6 +30,7 @@ # include <vector> # include <iostream> +# include <algorithm> # include <mln/core/contract.hh> /*! @@ -80,8 +81,8 @@ /// \} void set_parent(node<T>* parent); - void print_rec(int n) const; - void print() const; + node<T>* delete_node(); + void print(int level); bool check_consistency(); int search_rec(node<T>** res, T& elt); node<T>* search(T& elt); @@ -240,12 +241,60 @@ node<T>* node<T>::add_child(node<T>* node) { + if (node->parent_) + { + for (typename std::vector<util::node<T>* >::iterator it = node->parent()->children().begin(); + it != node->parent()->children().end(); ++it) + if ((*it) == this) + { + node->parent()->children().erase(it); + break; + } + } node->parent_ = this; this->children().push_back(node); return node; } template <typename T> + node<T>* + node<T>::delete_node() + { + mln_assertion(parent_ != 0); + node<T>* res = parent_; + + typename std::vector<node<T>* >::iterator it = parent_->children().begin(); + for (; it < parent_->children().end(); ++it) + if ((*it) == this) + { + parent_->children().erase(it); + break; + } + + for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + it != this->child_.end(); ++it) + parent_->add_child(*it); + return (res); + } + + template <typename T> + void + node<T>::print(int level) + { + std::cout << level << std::endl; + + std::cout << " elt " << this->elt() << std::endl; + + + for (typename std::vector<node<T>* >::iterator it = this->child_.begin(); + it != this->child_.end(); ++it) + { + (*it)->print(level + 1); + } + } + + + template <typename T> void node<T>::set_parent(node<T>* parent) {