* mln/core/concept/tree.hh: New component concept. * mln/core/image/attribute_image.hh: New attribute image. * mln/core/site_set/p_nodes.hh: Nodes site set. * mln/core/site_set/p_nodes_piter.hh: Nodes set iterators. * mln/tag/tree.hh: Tags for min/max tree. * mln/util/ctree/ctree.hh: New tree structure. * mln/util/ctree/internal/tree_base.hh: Base type for tree structure. * mln/util/ctree/node.hh, * mln/util/ctree/tree_ids.hh: Node site type. --- milena/ChangeLog | 14 + milena/mln/core/concept/tree.hh | 148 +++++ milena/mln/core/image/attribute_image.hh | 477 ++++++++++++++++ milena/mln/core/site_set/p_nodes.hh | 484 ++++++++++++++++ milena/mln/core/site_set/p_nodes_piter.hh | 244 ++++++++ milena/mln/tag/tree.hh | 52 ++ milena/mln/util/ctree/ctree.hh | 806 +++++++++++++++++++++++++++ milena/mln/util/ctree/internal/tree_base.hh | 141 +++++ milena/mln/util/ctree/node.hh | 351 ++++++++++++ milena/mln/util/ctree/tree_ids.hh | 53 ++ 10 files changed, 2770 insertions(+), 0 deletions(-) create mode 100644 milena/mln/core/concept/tree.hh create mode 100644 milena/mln/core/image/attribute_image.hh create mode 100644 milena/mln/core/site_set/p_nodes.hh create mode 100644 milena/mln/core/site_set/p_nodes_piter.hh create mode 100644 milena/mln/tag/tree.hh create mode 100644 milena/mln/util/ctree/ctree.hh create mode 100644 milena/mln/util/ctree/internal/tree_base.hh create mode 100644 milena/mln/util/ctree/node.hh create mode 100644 milena/mln/util/ctree/tree_ids.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index b3cd42e..0529b68 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,17 @@ +2010-04-09 edwin carlinet &lt;carlinet(a)lrde.epita.fr&gt; + + Unified structure for simple/dual input min/max tree. + + * mln/core/concept/tree.hh: New component concept. + * mln/core/image/attribute_image.hh: New attribute image. + * mln/core/site_set/p_nodes.hh: Nodes site set. + * mln/core/site_set/p_nodes_piter.hh: Nodes set iterators. + * mln/tag/tree.hh: Tags for min/max tree. + * mln/util/ctree/ctree.hh: New tree structure. + * mln/util/ctree/internal/tree_base.hh: Base type for tree structure. + * mln/util/ctree/node.hh, + * mln/util/ctree/tree_ids.hh: Node site type. + 2009-11-18 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; * doc/white_paper/white_paper.tex: Fix an invalid URL. diff --git a/milena/mln/core/concept/tree.hh b/milena/mln/core/concept/tree.hh new file mode 100644 index 0000000..2378bd8 --- /dev/null +++ b/milena/mln/core/concept/tree.hh @@ -0,0 +1,148 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_CORE_CONCEPT_TREE_HH +# define MLN_CORE_CONCEPT_TREE_HH + +# include <mln/core/concept/object.hh> + +namespace mln +{ + + // Forward declaration. + template <typename E> struct Tree; + + // Tree category flag type. + template <> + struct Tree<void> + { + typedef Object<void> super; + }; + + template <typename E> + struct Tree : public Object<E> + { + typedef Tree<void> category; + + /* + // Original image related + typedef site; + typedef psite; + + typedef value; + typedef rvalue; + typedef lvalue; + + // Node/Site related material. + typedef domain_t; + const domain_t& domain() const; + + typedef nodes_t; + const nodes_t& nodes() const; + + bool has(const node_t&) const; + bool has(const psite&) const; + + // Value related material. + rvalue f() (const psite&) const; + lvalue f() (const psite&); + rvalue f[] (const node_t&) const; + lvalue f[] (const node_t&); + + // Node relationship. + node_t node(const psite&) const; + void set_node(const psite&, const node_t&); + node_t parent(const node_id_t&) const; + void set_parent(const node_t&, const node_t&); + + // Node test materials + bool is_a_leaf(const node_t&) const; + bool is_a_root(const node_t&) const; + */ + + protected: + Tree(); + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Tree<E>::Tree() + { + typedef mln_site(E) site; + typedef mln_psite(E) psite; + + typedef mln_value(E) value; + typedef mln_rvalue(E) rvalue; + typedef mln_lvalue(E) lvalue; + + typedef typename E::node_t node_t; + + // Site/Node related material. + typedef mln_domain(E) domain_t; + typedef typename E::nodes_t nodes_t; + + const domain_t& (E::*m1)() const = & E::domain; + m1 = 0; + nodes_t (E::*m2)() const = & E::nodes; + m2 = 0; + bool (E::*m3)(const node_t&) const = & E::has; + m3 = 0; + bool (E::*m4)(const psite&) const = & E::has; + m4 = 0; + + // Value related material. + rvalue (E::*m5)(const psite&) const = & E::f; + m5 = 0; + lvalue (E::*m6)(const psite&) = & E::f; + m6 = 0; + rvalue (E::*m7)(const node_t&) const = & E::f; + m7 = 0; + lvalue (E::*m8)(const node_t&) = & E::f; + m8 = 0; + + // Node relationship. + node_t (E::*m9)(const psite&) const = & E::node; + m9 = 0; + void (E::*m10)(const psite&, const node_t&) = & E::set_node; + m10 = 0; + node_t (E::*m11)(const node_t&) const = & E::parent; + m11 = 0; + void (E::*m12)(const node_t&, const node_t&) = & E::set_parent; + m12 = 0; + + // Node tests + bool (E::*m13)(const node_t&) const = & E::is_a_leaf; + m13 = 0; + bool (E::*m14)(const node_t&) const = & E::is_a_root; + m14 = 0; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_TREE_HH diff --git a/milena/mln/core/image/attribute_image.hh b/milena/mln/core/image/attribute_image.hh new file mode 100644 index 0000000..1331a6f --- /dev/null +++ b/milena/mln/core/image/attribute_image.hh @@ -0,0 +1,477 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH +# define MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH + +# include <mln/core/internal/image_primary.hh> +# include <mln/core/concept/tree.hh> +# include <mln/tag/tree.hh> +# include <mln/metal/converts_to.hh> +# include <mln/metal/unref.hh> + +namespace mln +{ + // Forward declaration. + template <typename T, typename V> class attribute_image; + + namespace internal + { + + /// Data structure for \c mln::attribute_image + template <typename T, typename V> + struct data< mln::attribute_image<T, V> > + { + data(); + data(const T& tree); + ~data(); + + std::vector<V> values_; + T tree_; // An attribute image can hold the tracked-data of the tree. + typename T::nodes_t domain_; + }; + + } // end of namespace mln::internal + + namespace trait + { + + template <typename T, typename V> + struct image_< attribute_image<T, V> > : default_image_< V, attribute_image<T, V> > + { + // misc + typedef trait::image::category::primary category; + typedef trait::image::speed::fastest speed; + typedef trait::image::size::regular size; + + // value + typedef trait::image::vw_io::none vw_io; + typedef trait::image::vw_set::none vw_set; + // Fixme: value_access is direct, but if so, the duplicate function doesn't work anymore. + typedef trait::image::value_access::computed value_access; + typedef trait::image::value_alignment::irrelevant value_alignment; + typedef trait::image::value_browsing::site_wise_only value_browsing; + typedef trait::image::value_storage::one_block value_storage; + typedef trait::image::value_io::read_write value_io; + + // site / domain + typedef trait::image::pw_io::read_write pw_io; + typedef trait::image::localization::none localization; + typedef trait::image::dimension::none dimension; + + // extended domain + typedef trait::image::ext_domain::none ext_domain; + typedef trait::image::ext_value::irrelevant ext_value; + typedef trait::image::ext_io::irrelevant ext_io; + }; + + } // end of namespace mln::trait + + + namespace convert + { + + namespace over_load + { + template <typename T, typename V, typename I> + void + from_to_(const mln::attribute_image<T, V>& from, Image<I>& to_) + { + typedef mln::attribute_image<T, V> A; + I& to = exact(to_); + + mlc_converts_to(V, mln_value(I))::check(); + mlc_converts_to(typename T::domain_t, mln_domain(I))::check(); + + mln_precondition(from.is_valid()); + to.init_(from.tree().domain()); + + mln_fwd_piter(I) p(to.domain()); + for_all(p) + convert::from_to(from(from.tree().node(p)), to(p)); + } + + } // enf of namespace mln::convert::over_load + + } // end of namespace mln::convert + + + /// Basic attribute image class. + /// + /// The parameter \c V is the type of pixel values (usually the + /// result type of the attribute). This image class stores data in + /// memory. + /// + /// \ingroup modimageconcrete + // + template <typename T, typename V> + class attribute_image : public internal::image_primary< V, typename T::nodes_t, attribute_image<T, V> > + { + typedef internal::image_primary< V, typename T::nodes_t, attribute_image<T, V> > super_; + typedef attribute_image<T, V> self_; + + public: + + /// Value associated type. + typedef V value; + /// Return type of read-only access. + typedef const V& rvalue; + /// Return type of read-write access. + typedef V& lvalue; + + /// Associated tree type. + typedef T tree_t; + + /// Site (node) assocatied type. + typedef typename T::node_t node_t; + typedef node_t site; + typedef node_t psite; + + /// Site set (node set) associated type. + typedef typename T::nodes_t nodes_t; + + /// Skeleton. + typedef attribute_image< tag::tree_<T>, tag::value_<V> > skeleton; + + /// Constructors + /// \{ + /// Constructor without argument. + attribute_image(); + /// Allocate an attribute image respecting the size of the tree. + attribute_image(const Tree<T>& tree); + /// \} + + /// Initialize an empty image. + void init_(const Tree<T>& tree); + + /// Test if the node \p n is valid. + bool has(const node_t& n) const; + + /// Give the node site set. + const nodes_t& domain() const; + + /// Read-only access to the image value at node \p n. + rvalue operator()(const node_t& n) const; + + /// Read-write access to the image value at node \p n. + lvalue operator()(const node_t& n); + + // Specific methods: + // ---------------- + + /// Read access to the value at point \p p. + /// Note: can be ambigous if the node content is a node set. + rvalue operator()(const mln_psite(T)& p) const; + + /// Return the tree. + const T& tree() const; + + /// Change the target tree. + void change_tree(const Tree<T>& tree); + + // As a fastest image. + // ------------------ + + /// Give the number of elements. + unsigned nelements() const; + + /// Read-only access to the image value lacated at index \p i. + rvalue element(unsigned i) const; + + /// Read-write access to the image value lacated at index \p i. + lvalue element(unsigned i); + + /// Return the border. (Required by image fastest / return always 0). + unsigned border() const; + + /// Give the delta_index corresponding to the delta point. + int delta_index(const mln_delta(node_t)& dp) const; + + /// Give the point corresponding to the index \p i; + node_t point_at_index(unsigned i) const; + + /// Give the index corresponding to the point \p p; + unsigned index_of_point(const node_t& p) const; + + /// Give a hook to the value buffer. + const V* buffer() const; + + /// Give a hook to the value buffer. + V* buffer(); + + /// Give a hook to the std::vector. + std::vector<V>& vector() { + mln_precondition(this->is_valid()); + return this->data_->values_; + } + }; + + /// Avoid instanciation of attribute image of bool because of the very + /// bad idea of the STL to optimize vector<bool> with non adressable + /// type. + /// Use vector<char> instead of vector<bool> + template <typename T> + class attribute_image<T, bool>; + + + // Forward declaration. + template <typename T, typename V, typename V2> + void init_(tag::image_t, mln::attribute_image<T, V>& target, const mln::attribute_image<T, V2>& model); + + +# ifndef MLN_INCLUDE_ONLY + + // init_ + + template <typename T, typename V, typename V2> + inline + void + init_(tag::image_t, mln::attribute_image<T, V>& target, const mln::attribute_image<T, V2>& model) + { + target.init_(model.tree()); + } + + // internal::data + + namespace internal + { + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::data() + { + } + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::data(const T& tree) + : values_ (tree.n_nodes()), + tree_ (tree) + { + typedef typename T::nodes_t S; + typedef typename T::node_t node_t; + domain_ = S(tree_, node_t(tree_, 0), tree_.n_nodes()); + } + + template <typename T, typename V> + inline + data< attribute_image<T, V> >::~data() + { + } + + } // end of namespace mln::internal + + + template <typename T, typename V> + inline + attribute_image<T, V>::attribute_image() + { + } + + + template <typename T, typename V> + inline + attribute_image<T, V>::attribute_image(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + mln_precondition(tree.is_valid()); + this->data_ = new internal::data< self_ >(tree); + } + + template <typename T, typename V> + inline + unsigned + attribute_image<T, V>::border() const + { + return 0; + } + + template <typename T, typename V> + inline + void + attribute_image<T, V>::init_(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + + mln_precondition(!this->is_valid()); + mln_precondition(tree.is_valid()); + this->data_ = new internal::data< self_ >(tree); + } + + template <typename T, typename V> + inline + bool + attribute_image<T, V>::has(const node_t& n) const + { + mln_precondition(this->is_valid()); + return this->domain().has(n); + } + + template <typename T, typename V> + inline + const typename T::nodes_t& + attribute_image<T, V>::domain() const + { + mln_precondition(this->is_valid()); + return this->data_->domain_; + } + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::operator()(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename T, typename V> + inline + V& + attribute_image<T, V>::operator()(const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + // Specific methods: + // ---------------- + + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::operator()(const mln_psite(T)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->data_->tree_.has(p)); + return this->data_->values_[this->data_->tree_.node_at_(p)]; + } + + template <typename T, typename V> + inline + const T& + attribute_image<T, V>::tree() const + { + mln_precondition(this->is_valid()); + return this->data_->tree_; + } + + template <typename T, typename V> + inline + void + attribute_image<T, V>::change_tree(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + mln_precondition(tree.is_valid()); + this->data_->tree_ = tree; + } + + template <typename T, typename V> + inline + unsigned + attribute_image<T, V>::nelements() const + { + mln_precondition(this->is_valid()); + return this->domain().nsites(); + } + + template <typename T, typename V> + inline + const V& + attribute_image<T, V>::element(unsigned i) const + { + mln_precondition(this->is_valid()); + mln_precondition(i < this->nelements()); + return this->data_->values_[i]; + } + + template <typename T, typename V> + inline + V& + attribute_image<T, V>::element(unsigned i) + { + mln_precondition(this->is_valid()); + mln_precondition(i < this->nelements()); + return this->data_->values_[i]; + } + + template <typename T, typename V> + inline + int + attribute_image<T, V>::delta_index(const mln_delta(node_t)& dp) const + { + mln_precondition(this->is_valid()); + return dp; + } + + template <typename T, typename V> + inline + typename T::node_t + attribute_image<T, V>::point_at_index(unsigned i) const + { + mln_precondition(this->is_valid()); + node_t tmp(this->data_->tree_, i); + return tmp; + } + + template <typename T, typename V> + inline + const V* + attribute_image<T, V>::buffer() const + { + mln_precondition(this->is_valid()); + return &(this->data_->values_[0]); + } + + template <typename T, typename V> + inline + V* + attribute_image<T, V>::buffer() + { + mln_precondition(this->is_valid()); + return &(this->data_->values_[0]); + } + + template <typename T, typename V> + inline + unsigned + attribute_image<T, V>::index_of_point(const node_t& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + + unsigned i = p.index(); + //mln_postcondition(p == this->point_at_index(i)); + return i; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH diff --git a/milena/mln/core/site_set/p_nodes.hh b/milena/mln/core/site_set/p_nodes.hh new file mode 100644 index 0000000..7025ee9 --- /dev/null +++ b/milena/mln/core/site_set/p_nodes.hh @@ -0,0 +1,484 @@ +// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_CORE_SITE_SET_P_NODES_HH +# define MLN_CORE_SITE_SET_P_NODES_HH + +/// \file +/// +/// Definition of a run of nodes. +/// +/// \todo Use a lazy approach (in subj) like in p_array psite. +/// + +# include <mln/util/ctree/node.hh> +# include <mln/core/internal/site_set_base.hh> +# include <mln/core/internal/pseudo_site_base.hh> + +namespace mln +{ + + // Forward declarations. + template <typename T> class p_nodes; + template <typename T> class p_nodes_psite; + template <typename T> class p_nodes_fwd_piter_; + template <typename T> class p_nodes_bkd_piter_; + + namespace trait + { + + template <typename T> + struct site_set_< p_nodes<T> > + { + typedef trait::site_set::nsites::known nsites; + typedef trait::site_set::bbox::unknown bbox; + typedef trait::site_set::contents::fixed contents; + typedef trait::site_set::arity::unique arity; + }; + + template <typename T> + struct set_precise_unary_< op::ord, p_nodes<T> > + { + typedef set_precise_unary_< op::ord, p_nodes<T> > ret; // Itself. + bool strict(const p_nodes<T>& lhs, const p_nodes<T>& rhs) const; + }; + + } // end of namespace trait + + + + /// \brief Site set class in run. + /// + /// \ingroup modsitesetbasic + template <typename T> + class p_nodes : public internal::site_set_base_< util::ctree::node<T>, p_nodes<T> > + { + public: + + /// Element associated type. + typedef util::ctree::node<T> element; + + /// Psite associated type. + typedef p_nodes_psite<T> psite; + + /// Forward Site_Iterator associated type. + typedef p_nodes_fwd_piter_<T> fwd_piter; + + /// Backward Site_Iterator associated type. + typedef p_nodes_bkd_piter_<T> bkd_piter; + + /// Site_Iterator associated type. + typedef fwd_piter piter; + + + /// Constructor without argument. + p_nodes(); + + /// Constructors. + /// \{ + p_nodes(const Tree<T>& tree); + /// Create the node set [\p start, \p start + \p len [ + p_nodes(const Tree<T>& tree, const element& start, unsigned len); + /// Create the node set [\p start, \p end [ + p_nodes(const Tree<T>& tree, const element& start, const element& end); + /// \} + + /// Init. + /// \{ + void init(const Tree<T>& tree, const element& start, unsigned len); + void init(const Tree<T>& tree, const element& start, const element& end); + /// \} + + /// Test if \p p belongs to this site set. + bool has(const psite& p) const; + + /// Test if \p p belongs to this site set. + bool has(const element& p) const; + + /// Test if index \p i belongs to this site set. + bool has_index(unsigned i) const; + + /// Give the number of sites. + unsigned nsites() const; + + /// Return the \p i-th site. + element operator[](int i) const; + + /// Return the starting site. + const element& start() const; + + /// Return (compute) the ending site. + element end() const; + + /// Test if this run is valid, i.e., with length >= 0. + bool is_valid() const; + + /// Return the size of this site set in memory. + std::size_t memory_size() const; + + /// Return the attached tree. + const T& tree() const; + + protected: + const T* tree_; + + /// The first site of the run. + util::ctree::node<T> start_; + + /// The length of the run. + unsigned len_; + }; + + template <typename T> + class p_nodes_psite : public internal::pseudo_site_base_< const util::ctree::node<T>&, p_nodes_psite<T> > + { + typedef p_nodes_psite<T> self; + typedef internal::pseudo_site_base_<const util::ctree::node<T>&, self> super; + + public: + + // This associated type is important to know that this particular + // pseudo site knows the site set it refers to. + typedef p_nodes<T> target; + + // As a Proxy: + const util::ctree::node<T>& subj_(); + + p_nodes_psite(); + p_nodes_psite(const p_nodes<T>& run, int i); + + /// Index materials + /// \{ + int index() const; + void change_index(int i); + void inc_index(); + void dec_index(); + /// \} + + /// Run materials + /// \{ + const p_nodes<T>* target_() const; + const p_nodes<T>& run() const; + void change_target(const p_nodes<T>& new_target); + /// \} + + bool is_valid() const; + + private: + const p_nodes<T>* run_; + int i_; + mutable util::ctree::node<T> p_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename T> + inline + p_nodes<T>::p_nodes() : + tree_ (0), len_ (0) + { + } + + template <typename T> + inline + p_nodes<T>::p_nodes(const Tree<T>& tree) + : tree_ (&(exact(tree))), len_ (0) + { + mln_precondition(tree_.is_valid()); + } + + template <typename T> + inline + p_nodes<T>::p_nodes(const Tree<T>& tree, + const util::ctree::node<T>& start, + unsigned len) + : tree_ (&(exact(tree))), start_(start), len_ (len) + { + mln_precondition(tree_->is_valid() && start.is_valid()); + mln_postcondition(is_valid()); + } + + template <typename T> + inline + p_nodes<T>::p_nodes(const Tree<T>& tree, + const util::ctree::node<T>& start, + const util::ctree::node<T>& end) + : tree_ (&(exact(tree))), start_(start) + { + mln_precondition(tree_.is_valid() && start.is_valid() && end.is_valid()); + mln_precondition(start.index() <= end.index()); + len_ = end.index() - start.index(); + mln_postcondition(is_valid()); + } + + template <typename T> + inline + void + p_nodes<T>::init(const Tree<T>& tree, const util::ctree::node<T>& start, unsigned len) + { + tree_ = &(exact(tree)); + mln_precondition(start.is_valid()); + mln_precondition(tree_->is_valid()); + start_ = start; + len_ = len; + mln_postcondition(is_valid()); + } + + template <typename T> + inline + void + p_nodes<T>::init(const Tree<T>& tree, + const util::ctree::node<T>& start, + const util::ctree::node<T>& end) + { + tree_ = &(exact(tree)); + mln_precondition(tree_->is_valid()); + mln_precondition(start.is_valid() && end.is_valid()); + mln_precondition(start.index() <= end.index()); + start_ = start; + len_ = end.index() - start.index(); + mln_postcondition(is_valid()); + } + + template <typename T> + inline + bool + p_nodes<T>::is_valid() const + { + return tree_->is_valid() && start_.is_valid(); + } + + template <typename T> + inline + bool + p_nodes<T>::has(const psite& p) const + { + mln_precondition(p.target_() == this); + return p.index() >= 0 && p.index() < (int)len_; + } + + template <typename T> + inline + bool + p_nodes<T>::has(const util::ctree::node<T>& node) const + { + mln_precondition(is_valid()); + return (this->start_.index() <= node.index()) && (node.index() < this->end().index()); + } + + template <typename T> + inline + bool + p_nodes<T>::has_index(unsigned i) const + { + mln_precondition(is_valid()); + return i < len_; + } + + template <typename T> + inline + unsigned + p_nodes<T>::nsites() const + { + mln_precondition(is_valid()); + return len_; + } + + template <typename T> + inline + const T& + p_nodes<T>::tree() const + { + mln_precondition(is_valid()); + return *tree_; + } + + template <typename T> + inline + util::ctree::node<T> + p_nodes<T>::operator[](int i) const + { + mln_precondition(is_valid()); + mln_precondition(i >= 0); + mln_precondition(i < len_); + util::ctree::node<T> p = start_; + p.change_index(start_.index() + i); + return p; + } + + template <typename T> + inline + const util::ctree::node<T>& + p_nodes<T>::start() const + { + return start_; + } + + template <typename T> + inline + util::ctree::node<T> + p_nodes<T>::end() const + { + util::ctree::node<T> n = start_; + n.change_index(start_.index() + len_); + return n; + } + + template <typename T> + inline + std::size_t + p_nodes<T>::memory_size() const + { + return sizeof(*this); + } + + template <typename T> + std::ostream& operator<<(std::ostream& ostr, const p_nodes<T>& r) + { + ostr << '(' << r.start() << ", " << r.nsites() << ')'; + return ostr; + } + + // p_nodes_psite<P> + + template <typename T> + inline + p_nodes_psite<T>::p_nodes_psite() + : run_(0), + i_(0) + { + } + + template <typename T> + inline + p_nodes_psite<T>::p_nodes_psite(const p_nodes<T>& run, int i) + : run_(&run), + i_(i), + p_(run.start()) + { + p_.change_index(p_.index() + i_); + } + + template <typename T> + inline + bool + p_nodes_psite<T>::is_valid() const + { + return run_ != 0 && run_->has_index(i_); + } + + template <typename T> + inline + int + p_nodes_psite<T>::index() const + { + return i_; + } + + template <typename T> + inline + void + p_nodes_psite<T>::change_index(int i) + { + p_.change_index(run_->start().index() + i); + i_ = i; + } + + template <typename T> + inline + void + p_nodes_psite<T>::dec_index() + { + --i_; + p_.dec_index(); + } + + template <typename T> + inline + void + p_nodes_psite<T>::inc_index() + { + ++i_; + p_.inc_index(); + } + + template <typename T> + inline + const p_nodes<T>* + p_nodes_psite<T>::target_() const + { + return run_; + } + + template <typename T> + inline + void + p_nodes_psite<T>::change_target(const p_nodes<T>& new_target) + { + run_ = &new_target; + i_ = 0; + p_ = run_->start(); + } + + template <typename T> + inline + const util::ctree::node<T>& + p_nodes_psite<T>::subj_() + { + return p_; + } + + template <typename T> + inline + const p_nodes<T>& + p_nodes_psite<T>::run() const + { + mln_precondition(run_ != 0); + return *run_; + } + + namespace trait + { + + template <typename T> + inline + bool + set_precise_unary_< op::ord, p_nodes<T> >::strict(const p_nodes<T>& lhs, const p_nodes<T>& rhs) const + { + return util::ord_strict(lhs.start().index(), rhs.start().index()); + } + + } // end of namespace trait + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/site_set/p_nodes_piter.hh> + + +#endif // ! MLN_CORE_SITE_SET_P_NODES_HH diff --git a/milena/mln/core/site_set/p_nodes_piter.hh b/milena/mln/core/site_set/p_nodes_piter.hh new file mode 100644 index 0000000..d8fbf12 --- /dev/null +++ b/milena/mln/core/site_set/p_nodes_piter.hh @@ -0,0 +1,244 @@ +// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_CORE_SITE_SET_P_NODES_PITER_HH +# define MLN_CORE_SITE_SET_P_NODES_PITER_HH + +/*! \file + * + * \brief Definition of point iterators on mln::p_nodes. + */ + +# include <mln/core/site_set/p_nodes.hh> +# include <mln/core/internal/site_set_iterator_base.hh> + + +namespace mln +{ + + /*! \brief Forward iterator on points of a p_nodes<T>. + * + */ + template <typename T> + class p_nodes_fwd_piter_ + : + public internal::site_set_iterator_base< p_nodes<T>, + p_nodes_fwd_piter_<T> > + { + typedef p_nodes_fwd_piter_<T> self_; + typedef internal::site_set_iterator_base< p_nodes<T>, self_ > super_; + public: + + /// Constructor without arguments. + p_nodes_fwd_piter_(); + + /// Coordinate associated type. + p_nodes_fwd_piter_(const p_nodes<T>& r); + + /// Test if the iterator is valid. + bool is_valid_() const; + + /// Invalidate the iterator. + void invalidate_(); + + /// Start an iteration. + void start_(); + + /// Go to the next point. + void next_(); + + /// Go to the brother. + void go_to_brother(); + + /// Go to + void go_to(const typename T::node_t& node); + + protected: + using super_::p_; + using super_::s_; + }; + + + + /*! \brief Backward iterator on points of a p_nodes<T>. + * + */ + template <typename T> + class p_nodes_bkd_piter_ + : + public internal::site_set_iterator_base< p_nodes<T>, + p_nodes_bkd_piter_<T> > + { + typedef p_nodes_bkd_piter_<T> self_; + typedef internal::site_set_iterator_base< p_nodes<T>, self_ > super_; + public: + + /// Constructor without arguments. + p_nodes_bkd_piter_(); + + /// Coordinate associated type. + p_nodes_bkd_piter_(const p_nodes<T>& r); + + /// Test if the iterator is valid. + bool is_valid_() const; + + /// Invalidate the iterator. + void invalidate_(); + + /// Start an iteration. + void start_(); + + /// Go to the next point. + void next_(); + + protected: + using super_::p_; + using super_::s_; + }; + + + +# ifndef MLN_INCLUDE_ONLY + + // p_nodes_fwd_piter_<T> + + template <typename T> + inline + p_nodes_fwd_piter_<T>::p_nodes_fwd_piter_() + { + } + + template <typename T> + inline + p_nodes_fwd_piter_<T>::p_nodes_fwd_piter_(const p_nodes<T>& r) + { + this->change_target(r); + } + + template <typename T> + inline + bool + p_nodes_fwd_piter_<T>::is_valid_() const + { + mln_invariant(p_.index() >= 0); + return p_.index() < int(s_->nsites()); + } + + template <typename T> + inline + void + p_nodes_fwd_piter_<T>::invalidate_() + { + p_.change_index(s_->nsites()); + } + + template <typename T> + inline + void + p_nodes_fwd_piter_<T>::start_() + { + p_.change_index(0); + } + + template <typename T> + inline + void + p_nodes_fwd_piter_<T>::next_() + { + p_.inc_index(); + } + + template <typename T> + inline + void + p_nodes_fwd_piter_<T>::go_to_brother() + { + unsigned l = s_->tree().length_(p_.subj_()); + p_.change_index(p_.index() + l); + } + + template <typename T> + inline + void + p_nodes_fwd_piter_<T>::go_to(const typename T::node_t& node) + { + p_.change_index(node.index()); + } + + // p_nodes_bkd_piter_<T> + + template <typename T> + inline + p_nodes_bkd_piter_<T>::p_nodes_bkd_piter_() + { + } + + template <typename T> + inline + p_nodes_bkd_piter_<T>::p_nodes_bkd_piter_(const p_nodes<T>& r) + { + this->change_target(r); + } + + template <typename T> + inline + bool + p_nodes_bkd_piter_<T>::is_valid_() const + { + mln_invariant(p_.index() < int(s_->nsites())); + return p_.index() >= 0; + } + + template <typename T> + inline + void + p_nodes_bkd_piter_<T>::invalidate_() + { + p_.change_index(-1); + } + + template <typename T> + inline + void + p_nodes_bkd_piter_<T>::start_() + { + p_.change_index(s_->nsites() - 1); + } + + template <typename T> + inline + void + p_nodes_bkd_piter_<T>::next_() + { + p_.dec_index(); + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_SITE_SET_P_NODES_PITER_HH diff --git a/milena/mln/tag/tree.hh b/milena/mln/tag/tree.hh new file mode 100644 index 0000000..275c250 --- /dev/null +++ b/milena/mln/tag/tree.hh @@ -0,0 +1,52 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_TAG_TREE_HH +# define MLN_TAG_TREE_HH + +namespace mln +{ + + namespace tag + { + + namespace tree + { + + template <typename T> + struct tree_t : Object<T> { protected: tree_t(){} }; + struct max_t : tree_t<max_t> {}; + struct min_t : tree_t<min_t> {}; + + static max_t max; + static min_t min; + + } // end of namespace mln::tag::tree + + } // end of namespace mln::tag + +} // end of namespace mln + +#endif // !MLN_TAG_TREE_HH diff --git a/milena/mln/util/ctree/ctree.hh b/milena/mln/util/ctree/ctree.hh new file mode 100644 index 0000000..e1c7148 --- /dev/null +++ b/milena/mln/util/ctree/ctree.hh @@ -0,0 +1,806 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + + +// \todo definition of site, psite is ambigous, replace with content_t +// or other. +// \todo node operator ? +// +// \todo handle forest in case of non contiguous domain pictures. + + + +#ifndef MLN_UTIL_CTREE_CTREE_HH +# define MLN_UTIL_CTREE_CTREE_HH + +# include <mln/core/concept/image.hh> +# include <mln/core/concept/site_set.hh> +# include <mln/util/ctree/internal/tree_base.hh> +# include <mln/util/array.hh> +# include <mln/core/image/attribute_image.hh> +# include <algorithm> + +# define mln_node(T) typename T::node_t + +namespace mln +{ + + /// Forward declaration. + namespace util { namespace ctree { template <typename I> class ctree; } } + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + namespace generic + { + + template <typename T, typename I, typename N> + util::ctree::ctree<I> + union_find_fast(const tag::tree::tree_t<T>& tree_tag, + const Image<I>& f, + const Neighborhood<N>& nbh); + + } // end of namespace morpho::tree::impl::generic + + template <typename T, typename I, typename N> + util::ctree::ctree<I> + hqueue_fast(const tag::tree::tree_t<T>&, + const Image<I>& f, + const Neighborhood<N>& nbh); + + } // end of namespace morpho::tree::impl + + } // end of namespace morpho::tree + + } // end of namespace morpho + + + namespace internal + { + /// Data structure for component tree. + template <> + template <typename I> + struct data< util::ctree::ctree<I> > + { + typedef util::ctree::ctree<I> T; + typedef typename T::node_t::index_t index_t; + + data(const I&); + ~data(); + + mln_ch_value(I, index_t) map_; + std::vector<index_t> parent_; + std::vector<unsigned> length_; + std::vector<mln_value(I)> values_; + + const mln_domain(I)& domain_; + int nnodes; + }; + + } // end of namespace mln::internal + + namespace util + { + + namespace ctree + { + + template <typename I> + struct ctree : public internal::tree_base< I, ctree<I> > + { + /// The super class. + typedef internal::tree_base<I, ctree<I> > super; + + /// Self class + typedef ctree<I> self; + + /// Site related type definitions. + /// \{ + /// The type of site. + typedef mln_site(I) site; + /// The type of pseudo-site. + typedef mln_psite(I) psite; + /// The type of domain. + typedef mln_domain(I) domain_t; + /// \} + + /// Node related type definions. + /// \{ + /// The type of node. + typedef util::ctree::node<self> node_t; + /// The type of node set. + typedef p_nodes<self> nodes_t; + /// \} + + /// Node/Site value related type definitions. + /// \{ + /// The type of node value + typedef mln_value(I) value; + /// The type of node rvalue. + typedef mln_rvalue(I) rvalue; + /// The type of node lvalue. + typedef mln_lvalue(I) lvalue; + /// \} + + typedef mln_ch_value(I, typename node_t::index_t) map_t; + + /// Constructors + /// \{ + ctree(); + /// \} + + /// Reserve space for tree. + void reserve(const Image<I>& ima, unsigned nnodes); + + + /// Constructor from union-find results. + /// \param[in] f The input image. + /// \param[in] parent The (not necessary canonized) parent image. + /// \param[in] area The number of nodes in each sub-tree. + /// \param[in] s The sorted site set. + /// \param[in] nb_nodes The total number of nodes. + template <typename S> + ctree(const Image<I>& f_, + const S& s, + mln_ch_value(I, unsigned)& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes); + + // ctree(const Image<I>& f, + // const Site_Set<S>& s, + // mln_ch_value(I, psite)& parent, + // mln_ch_value(I, unsigned)& area, + // unsigned nb_nodes); + + /// \} + + ctree(const Image<I>& f, + const mln_ch_value(I, unsigned)& map, + const std::vector<unsigned>& nodes, + const std::vector<unsigned>& parent, + const std::vector<unsigned>& area); + + /// Misc. + /// \{ + const domain_t& domain() const; + const map_t& map() const; + nodes_t nodes() const; + bool has(const psite&) const; + bool has(const node_t&) const; + + int n_nodes() const; + /// \} + + /// Value access material. + /// \{ + rvalue f(const psite&) const; + lvalue f(const psite&); + rvalue f(const node_t&) const; + lvalue f(const node_t&); + /// \} + + /// Node relationship material. + /// \{ + node_t node(const psite&) const; + void set_node(const psite&, const node_t&); + node_t parent(const node_t&) const; + void set_parent(const node_t& n, const node_t& parent); + + /// Return the node set of the sub-tree of \p n. + /// \post Non empty set: n belongs to desc(n). + nodes_t desc(const node_t& n) const; + + /// Return the node set of ancestors of \p n. + nodes_t anc(const node_t& n) const; + + /// Return the number of descendants of \p n. + /// Equivalent to desc(n).nsites() - 1. + unsigned length_(const node_t& n) const; + /// \} + + /// Node tests material. + /// \{ + bool is_a_leaf(const node_t&) const; + bool is_a_root(const node_t&) const; + /// \} + + /// Fast access material. + /// \{ + + /// The type of index. + typedef typename node_t::index_t index_t; + + bool has_index(index_t i) const; + + /// Return the number of descendants of the node at index \p i. + /// Equivalent to desc(tree.node_at(i)).nsites(). + unsigned length_at_(index_t i) const; + unsigned& length_at_(index_t i); + rvalue f_at_(index_t i) const; + lvalue f_at_(index_t i); + index_t parent_at_(index_t i) const; + index_t& parent_at_(index_t i); + index_t node_at_(const psite& p) const; + index_t& node_at_(const psite& p); + /// \} + + /// To attribute image + attribute_image<ctree<I>, value> to_image() const; + void to_image(attribute_image<ctree<I>, value>& a) const; + + + /// Friend functions. + /// \{ + template <typename T, typename J, typename N> + friend util::ctree::ctree<J> + morpho::tree::impl::generic::union_find_fast(const tag::tree::tree_t<T>&, const Image<J>&, const Neighborhood<N>&); + + template <typename T, typename J, typename N> + friend util::ctree::ctree<J> + morpho::tree::impl::hqueue_fast(const tag::tree::tree_t<T>&, const Image<J>&, const Neighborhood<N>&); + /// \} + + }; + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + inline + data< util::ctree::ctree<I> >::data(const I& f) + : domain_ (f.domain()) + { + } + + template <typename I> + inline + data< util::ctree::ctree<I> >::~data() + { + } + + } // end of namespace mln::internal + + namespace util + { + + namespace ctree + { + namespace internal + { + template <typename T> + struct create_node : Function_v2v< create_node<T> > + { + typedef typename T::index_t param; + typedef typename T::node_t result; + + create_node(const T& tree) + : tree_ (tree) + { + } + + result + operator()(const param& idx) const + { + result tmp(tree_, idx); + return tmp; + } + + private: + const T& tree_; + }; + } + + + template <typename I> + inline + ctree<I>::ctree() + { + } + + template <typename I> + inline + void + ctree<I>::reserve(const Image<I>& f_, unsigned nnodes) + { + const I& f = exact(f_); + + mln_precondition(f.is_valid()); + this->data_ = new mln::internal::data< ctree<I> >(f); + + initialize(this->data_->map_, f); + this->data_->parent_.resize(nnodes); + this->data_->length_.resize(nnodes); + this->data_->values_.resize(nnodes); + this->data_->nnodes = nnodes; +# ifndef DNDEBUG + data::fill(this->data_->map_, 0); + std::fill(this->data_->parent_.begin(), this->data_->parent_.end(), 0); + std::fill(this->data_->length_.begin(), this->data_->length_.end(), 0); +# endif + } + + + template <typename I> + template <typename S> + inline + ctree<I>::ctree(const Image<I>& f_, + const S& s, + mln_ch_value(I, unsigned)& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes) + { + const I& f = exact(f_); + + mln_precondition(f.is_valid()); + mln_precondition(parent.is_valid()); + mln_precondition(area.is_valid()); + mln_precondition(f.domain() == parent.domain()); + mln_precondition(f.domain() == area.domain()); + + this->data_ = new mln::internal::data< ctree<I> >(f); + + initialize(this->data_->map_, f); + this->data_->parent_.resize(nb_nodes); + this->data_->length_.resize(nb_nodes); + this->data_->values_.resize(nb_nodes); + this->data_->nnodes = nb_nodes; + + //debug::println("Parent: ", parent); + //debug::println("Area: ", area); + + unsigned root_offset = 0; + + const unsigned nvalues = mln_card(mln_value(I)); + + // FIXME: max tree only + for (unsigned v = 0; v < nvalues; ++v) + { + const util::array<unsigned>& s_v = s[v]; + unsigned n_p = s_v.nelements(); + + for (int i = n_p - 1; i >= 0; --i) + { + unsigned p = s_v[i]; + unsigned q = parent.element(p); + + if (f.element(parent.element(q)) == f.element(q)) // Canonization + q = (parent.element(p) = parent.element(q)); + + if (f.element(p) == f.element(q) && p != q) // Not a node. + { + mln_assertion(q == parent.element(p)); + this->data_->map_.element(p) = + this->data_->map_.element(q); + } + else + { + unsigned& offset = (p == q) ? root_offset : area.element(q); + + // Insert Node. + mln_assertion(offset < nb_nodes); + this->data_->map_.element(p) = offset; + this->data_->parent_[offset] = this->data_->map_.element(q); + this->data_->values_[offset] = f.element(p); + this->data_->length_[offset] = area.element(p); + area.element(p) = offset + 1; + offset += this->data_->length_[offset] + 1; + } + } + } + } + +// template <typename T> +// std::ostream& +// operator<< (std::ostream& os, const std::vector<T>& v) +// { +// for (unsigned i = 0; i < v.size(); i++) +// os << v[i] << " "; +// return os; +// } + + template <typename I> + inline + ctree<I>::ctree(const Image<I>& f_, + const mln_ch_value(I, unsigned)& map, + const std::vector<unsigned>& location, + const std::vector<unsigned>& parent, + const std::vector<unsigned>& area) + { + const I& f = exact(f_); + unsigned n_nodes = location.size(); + + mln_precondition(f.is_valid()); + mln_precondition(map.is_valid()); + mln_precondition(parent.size() == n_nodes); + mln_precondition(area.size() == n_nodes); + + this->data_ = new mln::internal::data< ctree<I> >(f); + + initialize(this->data_->map_, f); + this->data_->parent_.resize(n_nodes); + this->data_->length_.resize(n_nodes); + this->data_->values_.resize(n_nodes); + this->data_->nnodes = n_nodes; + + + // debug::println("F:", f); + // debug::println("map:", map); + // std::cout << "Location: " << location << std::endl; + // std::cout << "Parent: " << parent << std::endl; + // std::cout << "Area: " << area << std::endl; + + + std::vector<char> deja_vu(n_nodes, 0); + mln_pixter(const I) pix(f); + for_all(pix) + { + unsigned idx = map.element(pix.offset()); + unsigned loc = n_nodes - location[idx] - 1; + this->data_->map_.element(pix.offset()) = loc; + + if (!deja_vu[idx]) + { + this->data_->values_[loc] = pix.val(); + this->data_->parent_[loc] = n_nodes - location[parent[idx]] - 1; + this->data_->length_[loc] = area[idx]; + deja_vu[idx] = true; + } + } + + // debug::println("map:", this->data_->map_); + // std::cout << "Parent: " << this->data_->parent_ << std::endl; + // std::cout << "Area: " << this->data_->length_ << std::endl; + // std::cout << "Values: " << this->data_->values_ << std::endl; + + } + + template <typename I> + inline + const mln_domain(I)& + ctree<I>::domain() const + { + mln_precondition(this->is_valid()); + return this->data_->domain_; + } + + template <typename I> + inline + typename ctree<I>::nodes_t + ctree<I>::nodes() const + { + mln_precondition(this->is_valid()); + nodes_t nodes_(*this, node_t(*this, 0), this->data_->nnodes); + return nodes_; + } + + template <typename I> + inline + const typename ctree<I>::map_t& + ctree<I>::map() const + { + mln_precondition(this->is_valid()); + return this->data_->map_; + } + + template <typename I> + inline + int + ctree<I>::n_nodes() const + { + mln_precondition(this->is_valid()); + return this->data_->nnodes; + } + + template <typename I> + inline + bool + ctree<I>::has(const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + return this->data_->domain_.has(p); + } + + template <typename I> + inline + bool + ctree<I>::has(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(n.is_valid()); + mln_invariant(n.tree().data_.ptr_ == this->data_.ptr_); + return n.index() < this->data_->nnodes; + } + + template <typename I> + inline + mln_rvalue(I) + ctree<I>::f (const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + return this->data_->values_[this->data_->map_(p)]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree<I>::f (const mln_psite(I)& p) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + return this->data_->values_[this->data_->map_(p)]; + } + + template <typename I> + inline + mln_rvalue(I) + ctree<I>::f (const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree<I>::f (const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return this->data_->values_[n.index()]; + } + + template <typename I> + inline + typename ctree<I>::node_t + ctree<I>::node(const mln_psite(I)& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + node_t tmp(*this, this->data_->map_(p)); + mln_postcondition(this->has(tmp)); + return tmp; + } + + template <typename I> + inline + void + ctree<I>::set_node(const mln_psite(I)& p, const node_t& n) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_precondition(this->has(n)); + this->data_->map_(p) = n.index(); + } + + + template <typename I> + inline + typename ctree<I>::node_t + ctree<I>::parent(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + node_t tmp(*this, this->data_->parent_[n.index()]); + mln_postcondition(tmp.index() <= n.index()); + mln_postcondition(this->has(tmp)); + return tmp; + } + + template <typename I> + inline + void + ctree<I>::set_parent(const node_t& n, const node_t& parent) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + mln_precondition(this->has(parent)); + this->data_->parent_[n.index()] = parent.index(); + } + + template <typename I> + inline + typename ctree<I>::nodes_t + ctree<I>::desc(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + nodes_t tmp(*this, n, this->data_->length_[n.index()] + 1); + mln_postcondition(tmp.nsites() >= 1); + return tmp; + } + + template <typename I> + inline + bool + ctree<I>::is_a_root(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return (this->data_->parent_[n.index()] == n.index()); + } + + template <typename I> + inline + bool + ctree<I>::is_a_leaf(const node_t& n) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(n)); + return (this->data_->length_[n.index()] == 0); + } + + template <typename I> + inline + bool + ctree<I>::has_index(index_t i) const + { + mln_precondition(this->is_valid()); + return 0 <= i && i <= this->n_nodes(); + } + + + template <typename I> + inline + unsigned + ctree<I>::length_(const node_t& node) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(node)); + return this->data_->length_[node.index()]; + } + + template <typename I> + inline + unsigned + ctree<I>::length_at_(index_t i) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->length_[i]; + } + + template <typename I> + inline + unsigned& + ctree<I>::length_at_(index_t i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->length_[i]; + } + + + + template <typename I> + inline + mln_rvalue(I) + ctree<I>::f_at_(index_t i) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->values_[i]; + } + + template <typename I> + inline + mln_lvalue(I) + ctree<I>::f_at_(index_t i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->values_[i]; + } + + template <typename I> + inline + typename ctree<I>::index_t + ctree<I>::parent_at_(index_t i) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + mln_postcondition(this->has_index(this->data_->parent_[i])); + return this->data_->parent_[i]; + } + + template <typename I> + inline + typename ctree<I>::index_t& + ctree<I>::parent_at_(index_t i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + mln_postcondition(this->has_index(this->data_->parent_[i])); + return this->data_->parent_[i]; + } + + template <typename I> + inline + typename ctree<I>::index_t + ctree<I>::node_at_(const psite& p) const + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_postcondition(this->has_index(this->data_->map_(p))); + return this->data_->map_(p); + } + + template <typename I> + inline + typename ctree<I>::index_t& + ctree<I>::node_at_(const psite& p) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has(p)); + mln_postcondition(this->has_index(this->data_->map_(p))); + return this->data_->map_(p); + } + + template <typename I> + inline + attribute_image<ctree<I>, mln_value(I)> + ctree<I>::to_image() const + { + mln_precondition(this->is_valid()); + + attribute_image<ctree<I>, value> to(*this); + this->to_image(to); + return to; + } + + template <typename I> + inline + void + ctree<I>::to_image(attribute_image<ctree<I>, value>& a) const + { + mln_precondition(this->is_valid()); + mln_precondition(a.is_valid()); + mln_precondition(a.tree().data_.ptr_ == this->data_.ptr_); + + std::copy(this->data_->values_.begin(), this->data_->values_.end(), a.buffer()); + } + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_CTREE_HH diff --git a/milena/mln/util/ctree/internal/tree_base.hh b/milena/mln/util/ctree/internal/tree_base.hh new file mode 100644 index 0000000..23c76b3 --- /dev/null +++ b/milena/mln/util/ctree/internal/tree_base.hh @@ -0,0 +1,141 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH +# define MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH + +# include <mln/core/concept/object.hh> +# include <mln/core/concept/tree.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/core/internal/data.hh> + +# include <mln/core/site_set/p_nodes.hh> + +# include <mln/util/ctree/node.hh> +# include <mln/util/tracked_ptr.hh> + +namespace mln +{ + + namespace util + { + + namespace ctree + { + + namespace internal + { + + template <typename I, typename E> + class tree_base : public Tree<E> + { + public: + /// Site related type definitions. + /// \{ + /// The type of site. + typedef mln_site(I) site; + /// The type of pseudo-site. + typedef mln_psite(I) psite; + /// The type of domain. + typedef mln_domain(I) domain_t; + /// \} + + /// Node related type definions. + /// \{ + /// The type of the node. + typedef node<E> node_t; + /// The type of node set. + typedef p_nodes<E> nodes_t; + /// \} + + /// Node/Site value related type definitions. + /// \{ + /// The type of node value + typedef mln_value(I) value; + /// The type of node rvalue. + typedef mln_rvalue(I) rvalue; + /// The type of node lvalue. + typedef mln_lvalue(I) lvalue; + /// \} + + /// Check validity. + bool is_valid() const; + void invalidate(); + + /// Hook to data; for debugging purpose. + const util::tracked_ptr< mln::internal::data<E> >& data_hook_() const; + + protected: + tree_base(); + + protected: + util::tracked_ptr< mln::internal::data<E> > data_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template<typename I, typename E> + inline + tree_base<I,E>::tree_base() + : data_ (0) + { + } + + template <typename I, typename E> + inline + bool + tree_base<I,E>::is_valid() const + { + return data_ != 0; + } + + template <typename I, typename E> + inline + void + tree_base<I,E>::invalidate() + { + data_.clean_(); + } + + template<typename I, typename E> + inline + const util::tracked_ptr< mln::internal::data<E> >& + tree_base<I,E>::data_hook_() const + { + return data_; + } + + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util::ctree::internal + + } // end of namespace mln::util::ctree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_INTERNAL_TREE_BASE_HH diff --git a/milena/mln/util/ctree/node.hh b/milena/mln/util/ctree/node.hh new file mode 100644 index 0000000..d22c48e --- /dev/null +++ b/milena/mln/util/ctree/node.hh @@ -0,0 +1,351 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_UTIL_CTREE_NODE_HH +# define MLN_UTIL_CTREE_NODE_HH + +# include <mln/core/concept/proxy.hh> +# include <mln/core/concept/site.hh> +# include <mln/core/internal/pseudo_site_base.hh> + +namespace mln +{ + + /// Node category flag type. + template <typename E> struct Node {}; + + template <> + struct Node<void> + { + typedef Site<void> super; + }; + + /// Fwd declaration. + namespace util + { + namespace ctree + { + template <typename T> + class node; + } + + } + + namespace trait + { + template <typename T> + struct set_precise_unary_< op::ord, util::ctree::node<T> > + { + typedef set_precise_unary_< op::ord, util::ctree::node<T> > ret; // Itself. + bool strict(const util::ctree::node<T>& lhs, const util::ctree::node<T>& rhs) const; + }; + + } // end of namespace trait + + namespace util + { + + namespace ctree + { + + template <typename T> + class node + { + public: + /// Object category. + typedef Node<void> category; + + /// The node index. + typedef int index_t; + + /// Tree associated type. + typedef T tree_t; + + /// FIXME: + typedef int delta; + + /// Constructors + /// \{ + node(); + explicit node(const Tree<T>& tree); + node(const Tree<T>& tree, int idx); + /// \} + + /// Misc + /// \{ + /// Return whether the node is valid. + bool is_valid() const; + + /// Index manipulation. + /// \{ + int index() const; + void inc_index(); + void dec_index(); + void change_index(int idx); + /// \} + + /// Return a reference to the graph holding this node. + const T& tree() const; + + /// Change target. + void change_tree(const Tree<T>& tree); + /// \} + + + private: + const T* tree_; + int idx_; + }; + + /* + ** Operators. + */ + template <typename T> + bool + operator== (const node<T>& n1, const node<T>& n2); + + template <typename T> + bool + operator!= (const node<T>& n1, const node<T>& n2); + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + + + namespace internal + { + + /// subject_impl specialization (Proxy) + /// \{ + + template <typename T, typename E> + struct subject_impl< const util::ctree::node<T>, E > + { + int index() const; + const T& tree() const; + + private: + const E& exact_() const; + }; + + template <typename T, typename E> + struct subject_impl< util::ctree::node<T>, E > : + subject_impl< const util::ctree::node<T>, E > + { + void change_index(int idx); + + private: + E& exact_(); + }; + + /// \} + + } // end of namespace mln::internal + +# ifndef MLN_INCLUDE_ONLY + + namespace util + { + + namespace ctree + { + + template <typename T> + inline + node<T>::node() + : tree_ (0) + { + } + + template <typename T> + inline + node<T>::node(const Tree<T>& tree) + : tree_ (&(exact(tree))) + { + } + + + template <typename T> + inline + node<T>::node(const Tree<T>& tree, int idx) + : tree_ (&(exact(tree))), + idx_ (idx) + { + mln_precondition(tree_->is_valid()); + } + + template <typename T> + inline + int + node<T>::index() const + { + return idx_; + } + + template <typename T> + inline + void + node<T>::inc_index() + { + ++idx_; + } + + template <typename T> + inline + void + node<T>::dec_index() + { + --idx_; + } + + template <typename T> + inline + void + node<T>::change_index(int idx) + { + idx_ = idx; + } + + template <typename T> + inline + const T& + node<T>::tree() const + { + mln_precondition(this->is_valid()); + return *tree_; + } + + template <typename T> + inline + void + node<T>::change_tree(const Tree<T>& tree) + { + tree_ = &(exact(tree)); + } + + template <typename T> + inline + bool + node<T>::is_valid() const + { + return tree_ != 0 && tree_->is_valid(); + } + + /* + ** Operators + */ + template <typename T> + inline + bool + operator== (const node<T>& n1, const node<T>& n2) + { + return n1.index() == n2.index(); + } + + template <typename T> + inline + bool + operator!= (const node<T>& n1, const node<T>& n2) + { + return n1.index() != n2.index(); + } + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + + namespace internal + { + + /*-----------------------------------------` + | subject_impl< const util::ctree::node<G> | + \-----------------------------------------*/ + + template <typename T, typename E> + inline + const E& + subject_impl< const util::ctree::node<T>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename T, typename E> + inline + int + subject_impl< const util::ctree::node<T>, E >::index() const + { + return exact_().get_subject().index(); + } + + template <typename T, typename E> + inline + const T& + subject_impl< const util::ctree::node<T>, E >::tree() const + { + return exact_().get_subject().tree(); + } + + /*------------------------------------------` + | subject_impl< util::ctree::node<T> | + \-----------------------------------------*/ + + template <typename T, typename E> + inline + E& + subject_impl< util::ctree::node<T>, E >::exact_() + { + return internal::force_exact<E>(*this); + } + + template <typename T, typename E> + inline + void + subject_impl< util::ctree::node<T>, E >::change_index(int idx) + { + return exact_().get_subject().change_index(idx); + } + + } // end of namespace mln::internal + + namespace trait + { + + template <typename T> + inline + bool + set_precise_unary_< op::ord, util::ctree::node<T> >::strict(const util::ctree::node<T>& lhs, const util::ctree::node<T>& rhs) const + { + return util::ord_strict(lhs.index(), rhs.index()); + } + + } // end of namespace trait + + +# endif // !MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_NODE_HH diff --git a/milena/mln/util/ctree/tree_ids.hh b/milena/mln/util/ctree/tree_ids.hh new file mode 100644 index 0000000..f9a2eae --- /dev/null +++ b/milena/mln/util/ctree/tree_ids.hh @@ -0,0 +1,53 @@ +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of Olena. +// +// Olena is free software: you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation, version 2 of the License. +// +// Olena 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 Olena. If not, see <http://www.gnu.org/licenses/>. +// +// As a special exception, you may use this file as part of a free +// software project 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. + +#ifndef MLN_UTIL_CTREE_TREE_IDS_HH +# define MLN_UTIL_CTREE_TREE_IDS_HH + +# include <mln/util/object_id.hh> + + +namespace mln +{ + + namespace util + { + + namespace ctree + { + + /// Object Id node tag. + struct node_tag; + + /// Node id type. + typedef object_id<node_tag, unsigned> node_id_t; + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_TREE_IDS_HH -- 1.5.6.5