[Olena-patches] r4620: Alternate representation of tree (some tries...)

URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox ChangeLog: 2009-10-07 Edwin Carlinet &lt;carlinet(a)lrde.epita.fr&gt; Alternate representation of tree (some tries...). * edwin/exec/benchmark/Makefile, * edwin/exec/benchmark/newv.cc, * edwin/exec/benchmark/oldv.cc, * edwin/exec/benchmark: Applications, and comparaisons between the old and new version. * edwin/mln/core, * edwin/mln/core/concept/dindex_site.hh, * edwin/mln/core/concept/index_site.hh, * edwin/mln/core/dindex_site.hh, * edwin/mln/core/internal/index_site_base.hh, * edwin/mln/core/internal, * edwin/mln/core/site_set/p_run_idx.hh, * edwin/mln/core/site_set/p_run_idx_piter.hh, * edwin/mln/core/site_set: Temporary type for index site (used by the node type), its site set and its iterators. * edwin/mln/core/concept/tree.hh, * edwin/mln/core/concept: Tree concept. * edwin/mln/core/image, * edwin/mln/core/image/attribute_image.hh: Attribute image type. * edwin/mln/debug, * edwin/mln/debug/ctree.hh: Debug tools with println overloads. * edwin/mln/morpho/tree/component_tree.hh: Shortcuts for building min and max tree. * edwin/mln/morpho/tree/compute_attribute_image.hh: Compute an attribute using the new tree representation. * edwin/mln/morpho/tree/impl, * edwin/mln/morpho/tree/impl/union_find.hh: (Simple) tree computation based on union-find method. * edwin/mln/morpho/tree/propagate_node.hh: Temporary methods for fast propagation. Will be useless as soon as the subdomain morpher will be specialized. * edwin/mln/util, * edwin/mln/util/ctree, * edwin/mln/util/ctree/ctree.hh, * edwin/mln/util/ctree/internal, * edwin/mln/util/ctree/internal/tree_base.hh, * edwin/mln/util/ctree/node.hh: Materials for the new tree representation. --- exec/benchmark/Makefile | 21 + exec/benchmark/newv.cc | 86 ++++ exec/benchmark/oldv.cc | 82 ++++ mln/core/concept/dindex_site.hh | 253 ++++++++++++ mln/core/concept/index_site.hh | 311 +++++++++++++++ mln/core/concept/tree.hh | 148 +++++++ mln/core/dindex_site.hh | 119 +++++ mln/core/image/attribute_image.hh | 435 +++++++++++++++++++++ mln/core/internal/index_site_base.hh | 254 ++++++++++++ mln/core/site_set/p_run_idx.hh | 458 ++++++++++++++++++++++ mln/core/site_set/p_run_idx_piter.hh | 222 ++++++++++ mln/debug/ctree.hh | 155 +++++++ mln/morpho/tree/component_tree.hh | 124 ++++++ mln/morpho/tree/compute_attribute_image.hh | 178 ++++++++ mln/morpho/tree/impl/dual_hqueue.hh | 408 ++++++++++++++++++++ mln/morpho/tree/impl/dual_union_find.hh | 361 +++++++++++++++++ mln/morpho/tree/impl/union_find.hh | 172 ++++++++ mln/morpho/tree/propagate_node.hh | 112 +++++ mln/util/ctree/ctree.hh | 589 +++++++++++++++++++++++++++++ mln/util/ctree/internal/tree_base.hh | 140 ++++++ mln/util/ctree/node.hh | 183 +++++++++ 21 files changed, 4811 insertions(+) Index: trunk/milena/sandbox/edwin/exec/benchmark/newv.cc =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/newv.cc (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/newv.cc (revision 4620) @@ -0,0 +1,86 @@ +#include <mln/core/image/image2d.hh> +#include <mln/core/image/attribute_image.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/util/ctree/ctree.hh> + +#include <mln/morpho/tree/component_tree.hh> +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/tree/filter/min.hh> +#include <mln/morpho/attribute/volume.hh> +#include <mln/morpho/attribute/card.hh> + + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/pw/all.hh> +#include <mln/core/var.hh> + +#include <mln/util/timer.hh> +#include <iostream> + +#include <mln/debug/ctree.hh> +#include <mln/debug/println.hh> + +void usage(char** argv) +{ + std::cout << "Usage: " << argv[0] << " image lambda [new.pgm]" + << std::endl; + abort(); +} + +static mln::util::timer tm; + +void bench(const char* msg) +{ + std::cout << msg << " in " << tm << " s" << std::endl; + tm.restart(); +} + +int main(int argc, char** argv) +{ + using namespace mln; + using value::int_u8; + + if (argc < 3) + usage(argv); + + const char* finput = argv[1]; + const unsigned lambda = atoi(argv[2]); + const char* foutput = (argc > 3) ? argv[3] : "new.pgm"; + + tm.start(); + + + typedef image2d<int_u8> I; + I input; + io::pgm::load(input, finput); + bench("Image Loadin"); + + // Tree Computation + typedef util::ctree::ctree<I> tree_t; + tree_t tree = morpho::tree::max_tree(input, c4()); + bench("Tree construction"); + + // Compute Attribute + typedef attribute_image<tree_t, unsigned> A; + morpho::attribute::volume<I> attribute; + A attr_img = morpho::tree::compute_attribute_image(tree, attribute); + bench("Attribute Computation (volume)"); + + // Filtering + attribute_image<tree_t, int_u8> out = tree.to_image(); + mln_VAR(predicate, pw::value(attr_img) > pw::cst(lambda)); + morpho::tree::filter::min(out, predicate); + bench("Filtering"); + + // Converting + I output; + convert::over_load::from_to_(out, output); // FIXME ! + bench("Restore"); + + io::pgm::save(output, foutput); + bench("Image Savin"); +} Index: trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/oldv.cc (revision 4620) @@ -0,0 +1,82 @@ +#include <mln/core/image/image2d.hh> +#include <mln/core/alias/neighb2d.hh> +#include <mln/value/int_u8.hh> + +#include <mln/morpho/tree/data.hh> +#include <mln/morpho/tree/component_tree.hh> + +#include <mln/io/pgm/load.hh> +#include <mln/io/pgm/save.hh> + +#include <mln/morpho/tree/compute_attribute_image.hh> +#include <mln/morpho/tree/propagate_representative.hh> +#include <mln/morpho/tree/filter/min.hh> +#include <mln/morpho/attribute/volume.hh> +#include <mln/morpho/attribute/card.hh> + +#include <mln/pw/all.hh> +#include <mln/core/var.hh> + +#include <mln/debug/println.hh> +#include <mln/util/timer.hh> +#include <iostream> + +void usage(char** argv) +{ + std::cout << "Usage: " << argv[0] << " image lambda [old.pgm]" + << std::endl; + abort(); +} + +static mln::util::timer tm; + +void bench(const char* msg) +{ + std::cout << msg << " in " << tm << " s" << std::endl; + tm.restart(); +} + +int main(int argc, char** argv) +{ + using namespace mln; + using value::int_u8; + + if (argc < 3) + usage(argv); + + const char* finput = argv[1]; + const unsigned lambda = atoi(argv[2]); + const char* foutput = (argc > 3) ? argv[3] : "old.pgm"; + + tm.start(); + + + typedef image2d<int_u8> I; + I input; + io::pgm::load(input, finput); + bench("Image Loadin"); + + // Tree Computation + typedef morpho::tree::data<I, p_array<mln_psite_(I)> > tree_t; + tree_t tree = morpho::tree::max_tree(input, c4()); + bench("Tree construction"); + + // Compute Attribute + typedef mln_ch_value_(I, unsigned) A; + morpho::attribute::volume<I> attribute; + A attr_img = morpho::tree::compute_attribute_image(attribute, tree); + bench("Attribute Computation (volume)"); + + // Filtering + I out = duplicate(input); + mln_VAR(predicate, pw::value(attr_img) > pw::cst(lambda)); + morpho::tree::filter::min(tree, out, predicate); + bench("Filtering"); + + // Restore + morpho::tree::propagate_representative(tree, out); + bench("Restore"); + + io::pgm::save(out, foutput); + bench("Image Savin"); +} Index: trunk/milena/sandbox/edwin/exec/benchmark/Makefile =================================================================== --- trunk/milena/sandbox/edwin/exec/benchmark/Makefile (revision 0) +++ trunk/milena/sandbox/edwin/exec/benchmark/Makefile (revision 4620) @@ -0,0 +1,21 @@ +-include makefile.rules + +MLN_DIR = ~/olena/trunk/milena +CXXFLAGS += -W -Wall +CXXFLAGS += $(if $(DEBUG), -g -ggdb, -DNDEBUG $(if $(RELEASE), -O3, -O1)) +MY_CXXFLAGS := $(CXXFLAGS) -I $(MLN_DIR)/sandbox/edwin -I $(MLN_DIR) +CXXFLAGS += -I $(MLN_DIR) +CC = g++ +LDFLAGS = + +all: oldv newv + +newv.o: newv.cc + $(CXX) $(MY_CXXFLAGS) -c $< + +clean: + rm -f *.o + +newv: newv.o + +oldv: oldv.o Index: trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/component_tree.hh (revision 4620) @@ -0,0 +1,124 @@ +// 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. + + +/// \file +/// +/// Compute a canonized (parenthood) component tree from an image. + + +#ifndef MLN_MORPHO_TREE_COMPONENT_TREE_HH +# define MLN_MORPHO_TREE_COMPONENT_TREE_HH + +# include <mln/tag/tree.hh> +# include <mln/util/ctree/ctree.hh> +# include <mln/morpho/tree/impl/union_find.hh> +# include <mln/morpho/tree/impl/hqueue.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + /// Compute a canonized min-tree. + /// + /// \param[in] f The input image. + /// \param[in] nbh The neighborhood. + /// + /// \return The corresponding min-tree structure. + /// + template <typename I, typename N> + inline + util::ctree::ctree<I> + min_tree(const Image<I>& f, const Neighborhood<N>& nbh); + + /// Compute a canonized max-tree. + /// + /// \param[in] f The input image. + /// \param[in] nbh The neighborhood. + /// + /// \return The corresponding max-tree structure. + /// + template <typename I, typename N> + inline + util::ctree::ctree<I> + max_tree(const Image<I>& f, const Neighborhood<N>& nbh); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename I, typename N> + inline + util::ctree::ctree<I> + min_tree(const Image<I>& f_, const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::min_tree"); + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + util::ctree::ctree<I> tree = + morpho::tree::impl::generic::union_find(tag::tree::min, f, nbh); + + trace::exiting("morpho::tree::min_tree"); + return tree; + } + + template <typename I, typename N> + inline + util::ctree::ctree<I> + max_tree(const Image<I>& f_, const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::max_tree"); + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + + mln_precondition(f.is_valid()); + mln_precondition(nbh.is_valid()); + + util::ctree::ctree<I> tree = + morpho::tree::impl::generic::union_find(tag::tree::max, f, nbh); + + trace::exiting("morpho::tree::max_tree"); + return tree; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_COMPONENT_TREE_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/compute_attribute_image.hh (revision 4620) @@ -0,0 +1,178 @@ +// 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 COMPUTE_ATTRIBUTE_IMAGE_HH +# define COMPUTE_ATTRIBUTE_IMAGE_HH +/// +/// +/// \brief Compute an attribute on a morphological tree. +/// +/// \todo Specialize for fast image. +/// + + +# include <mln/core/image/attribute_image.hh> +# include <mln/core/concept/tree.hh> +# include <mln/core/concept/accumulator.hh> + +# include <mln/data/fill.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree, + const Accumulator<A>& accu); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_none, + const T&, A& accu, + const mln_psite(T)&) + { + accu.take(); + } + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_pix, + const T& tree, A& accu, + const mln_psite(T)& p) + { + accu.take(make::pix(p, tree.f(p))); + } + + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_v, + const T& tree, A& accu, + const mln_psite(T)& p) + { + accu.take(tree.f(p)); + } + + template <typename T, typename A> + inline + void + take_as_init(trait::accumulator::when_pix::use_p, + const T&, A& accu, + const mln_psite(T)& p) + { + accu.take(p); + } + + template <typename T, typename A> + void + take_as_init(const T& tree, A& a, const mln_psite(T)& p) + { + take_as_init(mln_trait_accumulator_when_pix(A)(), tree, a, p); + } + + } // end of namespace namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const T& tree, const A& accu, attribute_image<T, A>* accu_img = 0) + { + attribute_image<T, A> a(tree); + (void) accu_img; + + // Transmit dynamic data of accumulator (ex: rank filter). + data::fill(a, accu); + + // Initialize. Each node takes its content. + { + mln_fwd_piter(T::domain_t) p(tree.domain()); + for_all(p) + internal::take_as_init(tree, a.element(tree.node_at_(p)), p); + } + + // Transmit to parent. + for (unsigned i = tree.n_nodes() - 1; i > 0; --i) + { + unsigned q = tree.parent_at_(i); + if (q != i) // The current node is not a root. + a.element(q).take(a.element(i)); + } + + attribute_image<T, mln_result(A)> out(tree); + for (unsigned i = 0; i < tree.n_nodes(); i++) + out.element(i) = a.element(i).to_result(); + + return out; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + + + // Facades + template <typename T, typename A> + attribute_image<T, mln_result(A)> + compute_attribute_image(const Tree<T>& tree_, const Accumulator<A>& acc) + { + trace::entering("mln::morpho::tree::compute_attribute_image"); + const T& tree = exact(tree_); + const A& accu = exact(acc); + + mln_precondition(tree.is_valid()); + + return impl::generic::compute_attribute_image(tree, accu); + trace::exiting("mln::morpho::tree::compute_attribute_image"); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !COMPUTE_ATTRIBUTE_IMAGE_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_hqueue.hh (revision 4620) @@ -0,0 +1,408 @@ +// 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_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH +# define MLN_MORPHO_TREE_IMPL_COMPUTE_PARENT_DUAL_HQUEUE_HH + +/// +/// \brief The dual input tree algorithm specialized for low quantized image. +/// +/// This implementation is based on P. Salembier algorithm using +/// hierachical queues. This implies a low-quantized input image so +/// that the number of queues is limited. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. +/// +/// TODO: During the canonization pass, we build the tree site set +/// from the sorted site set of f, so that we compute twice f +/// histogram (can be avoided). + +# include <mln/data/sort_psites.hh> +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/hqueues.hh> +# include <mln/util/ord.hh> + +# include <mln/value/value_array.hh> +# include <mln/value/set.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + /// Compute a tree using hqueues. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename N> + inline + data<I, p_array<mln_psite(I)> > + dual_hqueue(const Image<I>& f, + const Image<I>& m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I, typename N, class E> + struct shared_flood_args + { + typedef mln_psite(I) P; + typedef mln_value(I) V; + typedef p_array<P> S; + + const I& f; + const I& m; + const N& nbh; + mln_ch_value(I, P)& parent; + + // Aux data + util::hqueues<P, V>& hqueues; + const E& extend; // site -> site functor. + value::value_array<V, bool> is_node_at_level; + value::value_array<V, P> node_at_level; + mln_ch_value(I, bool) deja_vu; + const value::set<V>& vset; + + shared_flood_args(const I& f_, + const I& m_, + const N& neigb_, + mln_ch_value(I, P)& parent_, + util::hqueues<mln_psite(I), V>& hqueues_, + const E& extend_) + : f (f_), + m (m_), + nbh (neigb_), + parent (parent_), + hqueues (hqueues_), + extend (extend_), + is_node_at_level (false), + vset (hqueues.vset()) + { + initialize(deja_vu, f); + mln::data::fill(deja_vu, false); + } + }; + + template <typename I> + inline + histo::array<mln_value(I)> + compute_histo(const I& f, const I& m, mln_value(I)& hmin, mln_psite(I)& pmin) + { + histo::array<mln_value(I)> hm = histo::compute(m); + const histo::array<mln_value(I)> hf = histo::compute(f); + + { // Retrieve hmin. + unsigned i = 0; + while (hm[i] == 0) + ++i; + hmin = hm.vset()[i]; + } + + // Merge histograms. + for (unsigned i = 0; i < hm.nvalues(); ++i) + hm[i] += hf[i]; + + // Retrieve pmin. + mln_piter(I) p(m.domain()); + for (p.start(); m(p) != hmin; p.next()) + ; + mln_assertion(p.is_valid()); + pmin = p; + + return hm; + } + + // Site -> site functor: give for all p in Domain(f), its + // equivalence in the extended domain. + // TODO: make it generic. It works only on boxed domain. + template <typename I> + struct extend + { + extend(const mln_psite(I)::delta& dp) + : dp_ (dp) + { + } + + mln_psite(I) operator() (const mln_psite(I)& p) const + { + return p + dp_; + } + + private: + const mln_psite(I)::delta dp_; + }; + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + template <typename I, typename N, typename E> + unsigned + flood(internal::shared_flood_args<I, N, E>& args, const unsigned h_idx) + { + mln_assertion(args.is_node_at_level[h_idx]); + + while (!args.hqueues[h_idx].empty()) + { + mln_psite(I) p = args.hqueues[h_idx].pop_front(); + unsigned p_idx = args.vset.index_of(args.f(p)); + + if (p_idx != h_idx) + { // Intensity mismatch: irregular case. + mln_psite(I) pext = args.extend(p); + args.parent(pext) = args.node_at_level[h_idx]; + + if (p_idx > h_idx) // Singleton with parent at h. + args.parent(p) = args.node_at_level[h_idx]; + else + { + if (!args.is_node_at_level[p_idx]) + { + args.is_node_at_level[p_idx] = true; + args.node_at_level[p_idx] = p; + } + } + } + + if (p_idx <= h_idx) + { + if (!args.f.domain().has(args.node_at_level[p_idx]) || + util::ord_strict(p, args.node_at_level[p_idx])) + { // Regular case but a representative provided by the extension. + args.parent(args.node_at_level[p_idx]) = p; + args.node_at_level[p_idx] = p; + //args.parent(p) = p; + } + args.parent(p) = args.node_at_level[p_idx]; + } + + + // Process the neighbors + mln_niter(N) n(args.nbh, p); + for_all(n) + if (args.f.domain().has(n) && !args.deja_vu(n)) + { + unsigned mn = args.vset.index_of(args.m(n)); + unsigned fn = args.vset.index_of(args.f(n)); + args.hqueues[mn].push(n); + args.deja_vu(n) = true; + + mln_psite(I) ext = args.extend(n); + // Create a node at c. + { + mln_psite(I) node = (fn == mn) ? n : ext; + if (!args.is_node_at_level[mn]) + { + args.is_node_at_level[mn] = true; + args.node_at_level[mn] = node; + } + } + + while (mn > h_idx) + mn = flood(args, mn); + } + } + + // Retrieve dad. + args.is_node_at_level[h_idx] = false; + unsigned c = h_idx; + while (c > 0 && !args.is_node_at_level[c]) + --c; + + mln_psite(I) x = args.node_at_level[h_idx]; + if (c > 0) + args.parent(x) = args.node_at_level[c]; + else + args.parent(x) = x; + + return c; + } + + template <typename I, typename N> + inline + data< I, p_array<mln_psite(I)> > + dual_hqueue(const Image<I>& f_, + const Image<I>& m_, + const Neighborhood<N>& neibh_) + { + trace::entering("mln::morpho::tree::impl::dual_hqueue"); + + const I& f = exact(f_); + const I& m = exact(m_); + const N& nbh = exact(neibh_); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + util::timer tm; + tm.start(); + + // Histo. + mln_psite(I) pmin; + mln_value(I) hmin; + const histo::array<mln_value(I)> histo = internal::compute_histo(f, m, hmin, pmin); + util::hqueues<P, mln_value(I)> hqueues(histo); + + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_ext = f.domain(); + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + // Process. + internal::extend<I> extend(dp); + internal::shared_flood_args< I, N, internal::extend<I> > + args(f, m, nbh, parent, hqueues, extend); + + unsigned r = args.vset.index_of(hmin); + args.deja_vu(pmin) = true; + args.hqueues[r].push(pmin); + args.node_at_level[r] = (f(pmin) == hmin) ? pmin : extend(pmin); + args.is_node_at_level[r] = true; + flood(args, r); + + // Attach the nodes under hmin. + unsigned i = r; + do + { + if (args.is_node_at_level[i]) + { + parent(args.node_at_level[r]) = args.node_at_level[i]; + r = i; + } + } + while (i-- > 0); + parent(args.node_at_level[r]) = args.node_at_level[r]; //root + + // Canonization and make tree site set. + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + + p_array<mln_psite(I)> s_f = mln::data::sort_psites_increasing(f); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P x = p; + P q = parent(p); + + // Case: l: m <---- m <---- f + // Or + // Case l1: m <----- f impossible. + // | + // l2: m + mln_assertion(!(d_ext.has(q) && fext(p) == fext(q) && d_ext.has(parent(q)) && q != parent(q))); + + while (d_ext.has(q) && !deja_vu(q) && (fext(q) != fext(parent(q)) || q == parent(q))) + { + s.append(q); + deja_vu(q) = true; + x = q; + q = parent(q); + } + + if (d_ext.has(q) && fext(q) == fext(parent(q)) && q != parent(q)) + { + q = (parent(x) = parent(q)); + mln_assertion(f.domain().has(q)); + } + + if (fext(q) == fext(parent(q))) + parent(x) = parent(q); + + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + + } + + std::cout << "Construction de l'arbre en " << tm << " s." << std::endl; + + data<I, S> tree(fext, parent, s); + + trace::exiting("mln::morpho::tree::impl::dual_hqueue"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_COMPUTE_PARENT_DUAL_HQUEUE_HH + + + Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/union_find.hh (revision 4620) @@ -0,0 +1,172 @@ +// 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_MORPHO_TREE_IMPL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMPL_UNION_FIND_HH + +# include <mln/data/sort_psites.hh> +# include <mln/util/ctree/ctree.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + template <typename T, typename I, typename N> + util::ctree::ctree<I> + union_find(const tag::tree::tree_t<T>&, + const Image<I>& f, + const Neighborhood<N>& nbh); + } + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::max_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_increasing(f); + return data; + } + + template <typename I> + p_array<mln_psite(I)> + inline + sort_sites_set(const tag::tree::min_t&, const I& f) + { + p_array<mln_psite(I)> data = + data::sort_psites_decreasing(f); + return data; + } + + template <typename T> + inline + mln_psite(T) + zfind_root(T& zpar, const mln_psite(T)& x) + { + mlc_equal(mln_value(T), mln_psite(T))::check(); + if (zpar(x) == x) + return x; + else + return zpar(x) = zfind_root(zpar, zpar(x)); + } + + } + + + namespace impl + { + + namespace generic + { + + template <typename T, typename I, typename N> + util::ctree::ctree<I> + union_find(const tag::tree::tree_t<T>&, + const Image<I>& f_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::union_find"); + + typedef mln_psite(I) P; + typedef p_array<mln_psite(I)> S; + + const I& f = exact(f_); + const N& nbh = exact(nbh_); + S s = internal::sort_sites_set(T (), f); + + // Auxiliary data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) parent; + mln_ch_value(I, unsigned) area; + mln_ch_value(I, P) zpar; + unsigned nb_nodes = s.nsites(); + + initialize(deja_vu, f); + initialize(parent, f); + initialize(area, f); + initialize(zpar, f); + + // Initialization. + data::fill(deja_vu, false); + data::fill(area, 0); + + // Body. + mln_bkd_piter(S) p(s); // Backward. + mln_niter(N) n(nbh, p); + for_all(p) + { + // Make-Set. + parent(p) = p; + zpar(p) = p; + + for_all(n) + if (f.domain().has(n) && deja_vu(n)) + { + // Do-Union. + P r = internal::zfind_root(zpar, n); + if (r != p) + { + parent(r) = p; + zpar(r) = p; + area(p) += area(r); + if (f(r) != f(p)) + ++area(p); + else + --nb_nodes; + } + } + deja_vu(p) = true; + } + + util::ctree::ctree<I> tree(f, s, parent, area, nb_nodes); + + trace::exiting("morpho::tree::impl::generic::union_find"); + return tree; + } + + } + + } +# endif // ! MLN_INCLUDE_ONLY + } + + } + +} +#endif // !MLN_MORPHO_TREE_IMPL_UNION_FIND_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/impl/dual_union_find.hh (revision 4620) @@ -0,0 +1,361 @@ +// 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_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH +# define MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH + +/// +/// \brief The generic dual input tree algorithm for high quantized image. +/// +/// This implementation is based on tarjan's union method, so that +/// image quantization does not impact on the computation time. +/// +/// TODO: Think about how to extend f domain in a more +/// generic way. The actual implementation doubles the size of the +/// first dimension. It implies a boxed domain. +/// +/// TODO: Use the less functor. The actual implementation is for max-tree. + +# include <mln/data/fill.hh> + +# include <mln/geom/nsites.hh> +# include <mln/geom/translate.hh> + +# include <mln/morpho/tree/data.hh> + +# include <mln/util/timer.hh> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + namespace impl + { + + namespace generic + { + + /// Compute a tree using union-find method. + /// + /// \param f The original image. + /// \param m The connectivity mask. + /// \param s_f The sorted site set of \p f + /// \param s_m The sorted site set of \p m. + /// \param nbh The neighborhood of the mask. + /// + /// \return The tree structure. + /// + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image<I>& f, + const Image<I>& m, + const Site_Set<S>& s_f, + const Site_Set<S>& s_m, + const Neighborhood<N>& nbh); + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + // For benchmark purpose. More than 50% of the time is spent + // in find_root function. + static util::timer t_prop; + + + template <typename I> + inline + mln_psite(I) find_root(I& zpar, + const mln_psite(I)& p) + { + if (zpar(p) == p) + return p; + + t_prop.resume(); + mln_psite(I) x = zpar(p); + while (zpar(x) != x) + x = zpar(x); + + mln_psite(I) tmp; + for (mln_psite(I) y = p; y != x; y = tmp) + { + tmp = zpar(y); + zpar(y) = x; + } + t_prop.stop(); + + return x; + } + + template <typename I> + inline + void + update_m_parent(const I& f, + mln_ch_value(I, mln_psite(I))& parent, + mln_ch_value(I, bool)& deja_vu, + p_array< mln_psite(I) >& sset, + const mln_domain(I)& d_ext, + const mln_psite(I)& p) + { + typedef mln_psite(I) P; + + P q = parent(p); + P x = parent(q); + + mln_assertion(d_ext.has(q)); + + while (d_ext.has(x) && f(q) == f(x) && q != x) + { + q = x; + x = parent(q); + } + + if (!d_ext.has(x)) + { + if (f(x) == f(parent(x))) + x = (parent(q) = parent(x)); + if (f(q) != f(x)) + { + x = q; + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + } + else + { + if (x != q) + { + update_m_parent(f, parent, deja_vu, sset, d_ext, q); + x = q; + } + if (!deja_vu(q)) + { + deja_vu(q) = true; + sset.append(q); + } + } + + for (P i = p, tmp = parent(i); i != q; i = tmp, tmp = parent(i)) + parent(i) = x; + } + + } // end of namespace mln::morpho::tree::internal + + namespace impl + { + + namespace generic + { + + + template <typename I, typename S, typename N> + data< I, p_array<mln_psite(I)> > + dual_union_find(const Image<I>& f_, + const Image<I>& m_, + const Site_Set<S>& s_f_, + const Site_Set<S>& s_m_, + const Neighborhood<N>& nbh_) + { + trace::entering("morpho::tree::impl::generic::dual_union_find"); + + util::timer tm; + tm.start(); + internal::t_prop.reset(); + + typedef mln_psite(I) P; + typedef unsigned L; + + const I& f = exact(f_); + const I& m = exact(m_); + const S& s_f = exact(s_f_); + const S& s_m = exact(s_m_); + const N& nbh = exact(nbh_); + + // Aux data. + mln_psite(I)::delta dp(literal::zero); + mln_domain(I) d_f = f.domain(); + mln_domain(I) d_ext = f.domain(); // translate dp + mln_domain(I) d = f.domain(); + + // Extend the domain. + dp[0] = d.pmax()[0] - d.pmin()[0] + 1; + d.pmax() += dp; + d_ext.pmin() += dp; + d_ext.pmax() += dp; + + // Data. + mln_concrete(I) fext; + mln_ch_value(I, P) parent; + p_array<mln_psite(I)> s; + + // Initialization. + fext = geom::translate(m, dp.to_vec(), f, d); + initialize(parent, fext); + s.reserve(geom::nsites(fext)); + + //Process + { + // Aux data. + mln_ch_value(I, bool) deja_vu; + mln_ch_value(I, P) zpar; + + initialize(deja_vu, fext); + initialize(zpar, fext); + mln::data::fill(deja_vu, false); + + mln_bkd_piter(S) p_f(s_f); // Backward. + mln_bkd_piter(S) p_m(s_m); // Backward. + p_f.start(); + p_m.start(); + + // Main loop. + while (p_m.is_valid() || p_f.is_valid()) + { + mln_bkd_piter(S)& it = (!p_f.is_valid() || (p_m.is_valid() && f(p_f) <= m(p_m))) ? p_m : p_f; + + P p = it; + P ext = p + dp; + + // std::cout << "-------------------" << std::endl; + // std::cout << "Take " << p << " of value " << (&it == &p_m ? m(p) : f(p)) + // << " from " << (&it == &p_m ? "mask" : "f") << std::endl; + // debug::println("Parent: ", parent); + // debug::println("Zpar: ", zpar); + + mln_assertion(!(deja_vu(p) && deja_vu(ext))); + if (deja_vu(ext)) // Seen by mask before f. + { + mln_assertion(m(p) >= f(p)); + // Make set. + parent(p) = p; + zpar(p) = p; + + P r = internal::find_root(zpar, ext); + zpar(r) = p; + parent(r) = p; + + deja_vu(p) = true; + } + else if (deja_vu(p)) // Seen by f before mask. + { + mln_assertion(f(p) > m(p)); + parent(p) = ext; + zpar(p) = ext; + parent(ext) = ext; + zpar(ext) = ext; + + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + //std::cout << "Root: " << r << std::endl; + if (r != ext) + { + parent(r) = ext; + zpar(r) = ext; + } + } + deja_vu(ext) = true; + } + else if (f(p) <= m(p)) // First time p encountered. + { + zpar(ext) = ext; + mln_niter(N) n(nbh, ext); + for_all(n) + if (d_ext.has(n) && deja_vu(n)) + { + P r = internal::find_root(zpar, n); + if (r != ext) + { + zpar(r) = ext; + parent(r) = ext; + } + } + deja_vu(ext) = true; + } + else + { + deja_vu(p) = true; + } + it.next(); + } + } + std::cout << ">> MAJ zpar: " << internal::t_prop << " s" << std::endl; + std::cout << "Parent construction: " << tm << " s" << std::endl; + tm.restart(); + + // Canonization + { + mln_ch_value(I, bool) deja_vu(d_ext); + mln::data::fill(deja_vu, false); + mln_fwd_piter(S) p(s_f); // Forward. + for_all(p) + { + P q = parent(p); + if (!f.domain().has(q)) + internal::update_m_parent(fext, parent, deja_vu, s, d_ext, p); + else if (fext(parent(q)) == f(q)) + parent(p) = parent(q); + s.append(p); + + mln_assertion((q = parent(p)) == parent(q) || fext(q) != fext(parent(q))); + } + } + std::cout << "Canonization: " << tm << " s" << std::endl; + + //mln_postcondition(internal::compute_parent_postconditions(fext, s, parent)); + + tree::data<I, p_array<mln_psite(I)> > tree(fext, parent, s); + trace::exiting("morpho::tree::impl::generic::dual_union_find"); + + return tree; + } + + } // end of namespace mln::morpho::tree::impl::generic + + } // end of namespace mln::morpho::tree::impl + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // !MLN_MORPHO_TREE_IMLP_DUAL_UNION_FIND_HH Index: trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/morpho/tree/propagate_node.hh (revision 4620) @@ -0,0 +1,112 @@ +// Copyright (C) 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_MORPHO_TREE_PROPAGATE_NODE_HH +# define MLN_MORPHO_TREE_PROPAGATE_NODE_HH + +/// \file +/// +/// Functions to propagate node in the tree. +/// +/// \todo: The new implementation permits: + to propagate toward +/// subcomponents very fast (data::fill)\ + to propagate toward +/// supernodes as fast as the previous component\ + the attribute +/// image is still valid without the use of propagate_representative +/// that does not make sense any more. +/// +/// We are able in both cases to do something like: +/// + data::fill(attr_img | asc(n), v) +/// + data::fill(attr_img | desc(n), v) +/// +/// However the subimage morpher is not specialized for fast image and +/// does not take benefits in the fact that: +/// + desc(n) is a p_run (so can be memseté) +/// + attr_img can accessed by indexed (element() method for fast-image) + +# include <mln/core/image/attribute_image.hh> +# include <algorithm> + +namespace mln +{ + + namespace morpho + { + + namespace tree + { + + template <typename T, typename V> + inline + unsigned + propagate_node_to_descendants(attribute_image<T, V>& a, + const typename T::node_t& n, + const V& value) + { + typedef typename T::nodes_t desc_t; + mln_precondition(a.is_valid()); + mln_precondition(a.has(n)); + + // (n € desc(n)) but we don't set its value. + unsigned i = a.tree().desc(n).nsites(); + + if (i > 0) + { + mln_assertion(a.tree().has_index(n.index() + i)); + V* v = a.buffer() + n.index(); + std::fill(v + 1, v + i, value); + } + return i - 1; + } + + template <typename T, typename V> + inline + unsigned + propagate_node_to_ancestors(attribute_image<T, V>& a, + typename T::node_t n, + const V& v) + { + mln_precondition(a.is_valid()); + mln_precondition(a.has(n)); + + if (a.tree().is_a_root(n)) + return 0; + + unsigned i = 0; + do { + n = a.tree().parent(n); + a(n) = v; + ++i; + } while (!a.tree().is_a_root(n)); + + return i; + } + + } // end of namespace mln::morpho::tree + + } // end of namespace mln::morpho + +} // end of namespace mln + +#endif // ! MLN_MORPHO_TREE_PROPAGATE_NODE_HH Index: trunk/milena/sandbox/edwin/mln/debug/ctree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/debug/ctree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/debug/ctree.hh (revision 4620) @@ -0,0 +1,155 @@ +// 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_DEBUG_CTREE_HH +# define MLN_DEBUG_CTREE_HH + +# include <mln/util/ctree/ctree.hh> +# include <mln/core/image/attribute_image.hh> +# include <mln/core/site_set/p_array.hh> +# include <mln/math/max.hh> +# include <vector> +# include <iostream> + + +namespace mln +{ + + namespace debug + { + + /// \brief Print a morphological tree. + /// + /// \param[in] tree The tree to be print. + /// + template <typename T> + void + println(const Tree<T>& tree); + + /// \brief Print an attribute image. + /// + /// \param[in] a The attribute image. + /// + template <typename T, typename V> + void + println(const attribute_image<T, V>& a); + + +# ifndef MLN_INCLUDE_ONLY + + namespace internal + { + + template <typename T, typename V> + void + println(const T& tree, const std::vector<V>& values) + { + typedef std::vector< p_array<mln_psite(T)> > hset_t; + hset_t hset(tree.nodes().nsites()); + + // Make site set of each node. + { + mln_piter(T::domain_t) p(tree.domain()); + for_all(p) + hset[tree.node(p).index()].insert(p); + } + + // Retrieve the height + unsigned height = 0; + { + attribute_image<T, unsigned> h(tree); + data::fill(h, 0); + + mln_bkd_piter(T::nodes_t) n(tree.nodes()); + for_all(n) + if (!tree.is_a_root(n)) + h(tree.parent(n)) = math::max(h(tree.parent(n)), h(n) + 1); + else + height = math::max(height, h(n)); + } + { + std::cout << "Node"; + for (unsigned i = 0; i < height; i++) + std::cout << " "; + std::cout << "Value\tSites" << std::endl; + } + + mln_fwd_piter(T::nodes_t) n(tree.nodes()); + typename T::node_t old; + unsigned depth = 0; + for_all(n) + { + if (tree.is_a_root(n)) + depth = 0; + else + { + while (old != tree.parent(n)) + { + --depth; + old = tree.parent(old); + } + ++depth; + } + + for (unsigned i = 0; i < depth; i++) + std::cout << " "; + std::cout << n; + for (unsigned i = depth; i < height + 1; i++) + std::cout << " "; + + old = n; + std::cout << values[old.index()] << "\t" + << hset[old.index()] << std::endl; + } + + } + + } // end of namespace mln::debug::internal + + template <typename T> + void + println(const Tree<T>& tree_) + { + const T& tree = exact(tree_); + + mln_precondition(tree.is_valid()); + internal::println(tree, tree.data_hook_()->values_); + } + + template <typename T, typename V> + void + println(const attribute_image<T, V>& a) + { + mln_precondition(a.is_valid()); + internal::println(a.tree(), a.hook_data_()->values_); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::debug + +} // end of namespace mln + +#endif // !MLN_DEBUG_CTREE_HH Index: trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx.hh (revision 4620) @@ -0,0 +1,458 @@ +// 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_RUN_IDX_HH +# define MLN_CORE_SITE_SET_P_RUN_IDX_HH + +/// \file +/// +/// Definition of a run of index sites. +/// +/// \todo Use a lazy approach (in subj) like in p_array psite. +/// +/// FIXME: Wanted to have: +/// p_run_idx_psite < internal::index_site_base +/// < internal::pseudo_site_base +/// but diamond inheritance doesn't work even with virtual keyword... + +# include <mln/core/internal/index_site_base.hh> +# include <mln/core/internal/site_set_base.hh> +# include <mln/core/internal/pseudo_site_base.hh> +# include <mln/util/index.hh> + + +namespace mln +{ + + // Forward declarations. + template <typename P> class p_run_idx; + template <typename P> class p_run_idx_psite; + template <typename P> class p_run_idx_fwd_piter_; + template <typename P> class p_run_idx_bkd_piter_; + + namespace trait + { + + template <typename P> + struct site_set_< p_run_idx<P> > + { + 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 P> + struct set_precise_unary_< op::ord, p_run_idx<P> > + { + typedef set_precise_unary_< op::ord, p_run_idx<P> > ret; // Itself. + bool strict(const p_run_idx<P>& lhs, const p_run_idx<P>& rhs) const; + }; + + } // end of namespace trait + + + + /// \brief Site set class in run. + /// + /// \ingroup modsitesetbasic + template <typename P> + class p_run_idx : public internal::site_set_base_< P, p_run_idx<P> > + { + public: + + /// Element associated type. + typedef P element; + + /// Psite associated type. + typedef p_run_idx_psite<P> psite; + + /// Forward Site_Iterator associated type. + typedef p_run_idx_fwd_piter_<P> fwd_piter; + + /// Backward Site_Iterator associated type. + typedef p_run_idx_bkd_piter_<P> bkd_piter; + + /// Site_Iterator associated type. + typedef fwd_piter piter; + + + /// Constructor without argument. + p_run_idx(); + + /// Constructor. + p_run_idx(const P& start, const mln_delta(P)& len); + + /// Constructor. + p_run_idx(const P& start, const P& end); + + /// Init + void init(const P& start, const mln_delta(P)& len); + + /// Constructor. + void init(const P& start, const P& 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 P& 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. + P operator[](int i) const; + + /// Return the starting site. + const P& start() const; + + /// Return (compute) the ending site. + P 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; + + protected: + + /// The first site of the run. + P start_; + + /// The length of the run. + mln_delta(P) len_; + }; + + + template <typename P> + std::ostream& operator<<(std::ostream& ostr, const p_run_idx<P>& r); + + template <typename P> + class p_run_idx_psite : public internal::pseudo_site_base_< const P&, p_run_idx_psite<P> > + { + typedef p_run_idx_psite<P> self; + typedef internal::pseudo_site_base_<const P&, self> super; + + public: + + // This associated type is important to know that this particular + // pseudo site knows the site set it refers to. + typedef p_run_idx<P> target; + + // As a Proxy: + const P& subj_(); + + p_run_idx_psite(); + p_run_idx_psite(const p_run_idx<P>& run, int i); + + int index() const; + void change_index(int i); + void inc_index(); + void dec_index(); + + const p_run_idx<P>* target_() const; + void change_target(const p_run_idx<P>& new_target); + + bool is_valid() const; + + operator util::index() const; + + const p_run_idx<P>& run() const; + + private: + + const p_run_idx<P>* run_; + int i_; + mutable P p_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + p_run_idx<P>::p_run_idx() + { + len_.change_value(0); + } + + template <typename P> + inline + p_run_idx<P>::p_run_idx(const P& start, const mln_delta(P)& len) + { + mln_precondition(len.value() != 0); + init(start, len); + } + + + template <typename P> + inline + void + p_run_idx<P>::init(const P& start, const mln_delta(P)& len) + { + mln_precondition(len.value() != 0); + start_ = start; + len_ = len; + } + + template <typename P> + inline + p_run_idx<P>::p_run_idx(const P& start, const P& end) + { + mln_precondition(start <= end); + init(start, end - start + 1); + } + + template <typename P> + inline + void + p_run_idx<P>::init(const P& start, const P& end) + { + mln_precondition(start <= end); + init(start, end - start + 1); + } + + template <typename P> + inline + bool + p_run_idx<P>::is_valid() const + { + return len_.value() != 0; + } + + template <typename P> + inline + bool + p_run_idx<P>::has(const psite& p) const + { + mln_precondition(p.target_() == this); // FIXME: Refine. + if (p.index() >= len_.value()) + return false; + // The type of rhs below is mln_site(p_run_idx<P>). + mln_invariant(p.to_site() == (*this)[p.index()]); + return true; + } + + template <typename P> + inline + bool + p_run_idx<P>::has(const P& p) const + { + mln_precondition(is_valid()); + return start_ <= p && p <= end(); + } + + template <typename P> + inline + bool + p_run_idx<P>::has_index(unsigned i) const + { + return i < len_.value(); + } + + template <typename P> + inline + unsigned + p_run_idx<P>::nsites() const + { + mln_precondition(is_valid()); + return len_.value(); + } + + template <typename P> + inline + P + p_run_idx<P>::operator[](int i) const + { + mln_precondition(is_valid()); + mln_precondition(i >= 0); + mln_precondition(i < len_.value()); + P p = start_ + (mln_delta(P))i; + return p; + } + + template <typename P> + inline + const P& + p_run_idx<P>::start() const + { + return start_; + } + + template <typename P> + inline + P + p_run_idx<P>::end() const + { + P p = start_ + (len_ - 1); + return p; + } + + template <typename P> + inline + std::size_t + p_run_idx<P>::memory_size() const + { + return sizeof(*this); + } + + template <typename P> + std::ostream& operator<<(std::ostream& ostr, const p_run_idx<P>& r) + { + ostr << '(' << r.start() << ", " << r.nsites() << ')'; + return ostr; + } + + // p_run_idx_psite<P> + + template <typename P> + inline + p_run_idx_psite<P>::p_run_idx_psite() + : run_(0), + i_(0) + { + } + + template <typename P> + inline + p_run_idx_psite<P>::p_run_idx_psite(const p_run_idx<P>& run, int i) + : run_(&run), + i_(i), + p_(run.start()) + { + p_ += i_; + } + + template <typename P> + inline + bool + p_run_idx_psite<P>::is_valid() const + { + return run_ != 0 && run_->has_index(i_); + } + + template <typename P> + inline + int + p_run_idx_psite<P>::index() const + { + return i_; + } + + template <typename P> + inline + void + p_run_idx_psite<P>::change_index(int i) + { + p_ += (mln_delta(P))(i - i_); + i_ = i; + } + + template <typename P> + inline + void + p_run_idx_psite<P>::dec_index() + { + --i_; + p_.dec_index(); + } + + template <typename P> + inline + void + p_run_idx_psite<P>::inc_index() + { + ++i_; + p_.inc_index(); + } + + template <typename P> + inline + const p_run_idx<P>* + p_run_idx_psite<P>::target_() const + { + return run_; + } + + template <typename P> + inline + void + p_run_idx_psite<P>::change_target(const p_run_idx<P>& new_target) + { + run_ = & new_target; + i_ = 0; + p_ = run_->start(); + } + + template <typename P> + inline + const P& + p_run_idx_psite<P>::subj_() + { + return p_; + } + + template <typename P> + inline + p_run_idx_psite<P>::operator util::index() const + { + return i_; + } + + template <typename P> + inline + const p_run_idx<P>& + p_run_idx_psite<P>::run() const + { + mln_precondition(run_ != 0); + return *run_; + } + namespace trait + { + + template <typename P> + inline + bool + set_precise_unary_< op::ord, p_run_idx<P> >::strict(const p_run_idx<P>& lhs, const p_run_idx<P>& rhs) const + { + return util::ord_strict(lhs.start(), rhs.start()); + } + + } // end of namespace trait + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +# include <mln/core/site_set/p_run_idx_piter.hh> + + +#endif // ! MLN_CORE_SITE_SET_P_RUN_IDX_HH Index: trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/site_set/p_run_idx_piter.hh (revision 4620) @@ -0,0 +1,222 @@ +// 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_RUN_IDX_PITER_HH +# define MLN_CORE_SITE_SET_P_RUN_IDX_PITER_HH + +/*! \file + * + * \brief Definition of point iterators on mln::p_run_idx. + */ + +# include <mln/core/site_set/p_run_idx.hh> +# include <mln/core/internal/site_set_iterator_base.hh> + + +namespace mln +{ + + /*! \brief Forward iterator on points of a p_run_idx<P>. + * + */ + template <typename P> + class p_run_idx_fwd_piter_ + : + public internal::site_set_iterator_base< p_run_idx<P>, + p_run_idx_fwd_piter_<P> > + { + typedef p_run_idx_fwd_piter_<P> self_; + typedef internal::site_set_iterator_base< p_run_idx<P>, self_ > super_; + public: + + /// Constructor without arguments. + p_run_idx_fwd_piter_(); + + /// Coordinate associated type. + p_run_idx_fwd_piter_(const p_run_idx<P>& 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_; + }; + + + + /*! \brief Backward iterator on points of a p_run_idx<P>. + * + */ + template <typename P> + class p_run_idx_bkd_piter_ + : + public internal::site_set_iterator_base< p_run_idx<P>, + p_run_idx_bkd_piter_<P> > + { + typedef p_run_idx_bkd_piter_<P> self_; + typedef internal::site_set_iterator_base< p_run_idx<P>, self_ > super_; + public: + + /// Constructor without arguments. + p_run_idx_bkd_piter_(); + + /// Coordinate associated type. + p_run_idx_bkd_piter_(const p_run_idx<P>& 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_run_idx_fwd_piter_<P> + + template <typename P> + inline + p_run_idx_fwd_piter_<P>::p_run_idx_fwd_piter_() + { + } + + template <typename P> + inline + p_run_idx_fwd_piter_<P>::p_run_idx_fwd_piter_(const p_run_idx<P>& r) + { + this->change_target(r); + } + + template <typename P> + inline + bool + p_run_idx_fwd_piter_<P>::is_valid_() const + { + mln_invariant(p_.index() >= 0); + return p_.index() < int(s_->nsites()); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_<P>::invalidate_() + { + p_.change_index(s_->nsites()); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_<P>::start_() + { + p_.change_index(0); + } + + template <typename P> + inline + void + p_run_idx_fwd_piter_<P>::next_() + { + p_.inc_index(); + } + + + // p_run_idx_bkd_piter_<P> + + template <typename P> + inline + p_run_idx_bkd_piter_<P>::p_run_idx_bkd_piter_() + { + } + + template <typename P> + inline + p_run_idx_bkd_piter_<P>::p_run_idx_bkd_piter_(const p_run_idx<P>& r) + { + this->change_target(r); + } + + template <typename P> + inline + bool + p_run_idx_bkd_piter_<P>::is_valid_() const + { + mln_invariant(p_.index() < int(s_->nsites())); + return p_.index() >= 0; + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_<P>::invalidate_() + { + p_.change_index(-1); + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_<P>::start_() + { + p_.change_index(s_->nsites() - 1); + } + + template <typename P> + inline + void + p_run_idx_bkd_piter_<P>::next_() + { + p_.dec_index(); + } + + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + + +#endif // ! MLN_CORE_SITE_SET_P_RUN_IDX_PITER_HH Index: trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/image/attribute_image.hh (revision 4620) @@ -0,0 +1,435 @@ +// 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/metal/converts_to.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. + }; + + } // 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; + typedef trait::image::value_access::direct 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; + + + /// 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< 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 a hook to the value buffer. + const value* buffer() const; + + /// Give a hook to the value buffer. + value* buffer(); + }; + + // 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) + { + } + + 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(tree.is_valid()); + this->data_->tree_ = tree; + this->data_->values_.resize(tree.n_nodes()); + } + + 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_->tree_.nodes(); + } + + 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->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.value(); + } + + 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 + { + return &(this->data_->values_[0]); + } + + template <typename T, typename V> + inline + V* attribute_image<T, V>::buffer() + { + return &(this->data_->values_[0]); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_IMAGE_ATTRIBUTE_IMAGE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/index_site.hh (revision 4620) @@ -0,0 +1,311 @@ +// 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. + +/// +/// \brief Definition of the concept mln::index_site. +/// +/// FIXME: doc! +/// + + +#ifndef MLN_CORE_CONCEPT_INDEX_SITE_HH +# define MLN_CORE_CONCEPT_INDEX_SITE_HH + +# include <mln/core/concept/site.hh> +# include <mln/value/concept/integer.hh> +# include <mln/core/concept/dindex_site.hh> + + +namespace mln +{ + // Forward declaration. + template <typename E> struct Index_Site; + + namespace trait + { + + template < typename P, typename D > + struct set_binary_< op::plus, + mln::Index_Site, P, mln::Dindex_Site, D > + { + typedef P ret; + }; + + template < typename P, typename D > + struct set_binary_< op::minus, + mln::Index_Site, P, mln::Dindex_Site, D > + { + typedef P ret; + }; + + template < typename L, typename R > + struct set_binary_< op::minus, + mln::Index_Site, L, mln::Index_Site, R > + { + typedef mln_delta(L) ret; + }; + + template < typename L, typename R > + struct set_binary_< op::times, + mln::Index_Site, L, + mln::Object, mln::value::scalar_<R> > + { + typedef L ret; + }; + + template < typename L, typename R > + struct set_binary_< op::div, + mln::Index_Site, L, + mln::Object, mln::value::scalar_<R> > + { + typedef L ret; + }; + + template <typename P> + struct set_unary_< op::ord, mln::Index_Site, P > + { + typedef mln::internal::ord_less< P > ret; + }; + + } + + // Index Site category flag type. + template <> + struct Index_Site<void> + { + typedef Site<void> super; + }; + + template <typename E> + struct Index_Site : public Site<E> + { + typedef Index_Site<void> category; + + /* + typedef delta; + typedef index_t; + + const index_t& index() const; + void change_index(const index_t&); + + void dec_index(); + void inc_index(); + + */ + + protected: + Index_Site(); + }; + + // Conversion. + + namespace convert + { + + namespace over_load + { + + template <typename P> + void + from_to_(const Index_Site<P>& from, mln_delta(P)& to); + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + + /// Operators. + /// \{ + template <typename P> + std::ostream& + operator<<(std::ostream& ostr, const Index_Site<P>& dp); + + template <typename L, typename R> + bool operator==(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename L, typename R> + bool operator<(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename P, typename D> + P operator+(const Index_Site<P>& p, const Dindex_Site<D>& dp); + + template <typename P, typename D> + P operator-(const Index_Site<P>& p, const Dindex_Site<D>& dp); + + template <typename P, typename S> + P operator*(const Index_Site<P>& p, const value::scalar_<S>& s); + + template <typename P, typename S> + P operator/(const Index_Site<P>& p, const value::scalar_<S>& s); + + template <typename L, typename R> + mln_delta(L) operator-(const Index_Site<L>& lhs, const Index_Site<R>& rhs); + + template <typename P, typename D> + P& operator+=(Index_Site<P>& p, const Dindex_Site<D>& dp); + + template <typename P, typename D> + P& operator-=(Index_Site<P>& p, const Dindex_Site<D>& dp); + + template <typename P, typename S> + P& operator*=(Index_Site<P>& p, const value::scalar_<S>& s); + + template <typename P, typename S> + P& operator/=(Index_Site<P>& p, const value::scalar_<S>& s); + + /// \} + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Index_Site<E>::Index_Site() + { + typedef mln_delta(E) delta; + typedef typename E::index_t index_t; + + void (E::*m1)() = & E::inc_index; + m1 = 0; + void (E::*m2)() = & E::dec_index; + m2 = 0; + const index_t& (E::*m3)() const = & E::index; + m3 = 0; + void (E::*m4)(const index_t&) = & E::change_index; + m4 = 0; + } + + namespace convert + { + + namespace over_load + { + + template <typename P> + void + from_to_(const Index_Site<P>& from, mln_delta(P)& to) + { + to.value() = exact(from).index(); + } + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + template <typename P> + std::ostream& + operator<<(std::ostream& ostr, const Index_Site<P>& p) + { + ostr << '(' << debug::format(exact(p).index()) << ')'; + return ostr; + } + + template <typename L, typename R> + bool operator==(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + return exact(lhs).index() == exact(rhs).index(); + } + + template <typename L, typename R> + bool operator<(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + return exact(lhs).index() < exact(rhs).index(); + } + + template <typename P, typename D> + P operator+(const Index_Site<P>& p, const Dindex_Site<D>& dp) + { + P tmp = exact(p); + tmp.change_index(tmp.index() + exact(dp).value()); + return tmp; + } + + template <typename P, typename D> + P operator-(const Index_Site<P>& p, const Dindex_Site<D>& dp) + { + P tmp = exact(p); + tmp.change_index(tmp.index() - exact(dp).value()); + return tmp; + } + + template <typename P, typename S> + P operator*(const Index_Site<P>& p, const value::scalar_<S>& s) + { + S equiv = s.to_equiv(); + P tmp = exact(p); + tmp.change_index(tmp.index() * equiv); + return tmp; + } + + + template <typename P, typename S> + P operator/(const Index_Site<P>& p, const value::scalar_<S>& s) + { + S equiv = s.to_equiv(); + P tmp = exact(p); + tmp.change_index(tmp.index() / equiv); + return tmp; + } + + + template <typename L, typename R> + mln_delta(L) operator-(const Index_Site<L>& lhs, const Index_Site<R>& rhs) + { + mln_delta(L) delta(exact(lhs).index() - exact(rhs).index()); + mln_postcondition(rhs + delta == lhs); + return delta; + } + + template <typename P, typename D> + P& operator+=(Index_Site<P>& p, const Dindex_Site<D>& dp) + { + exact(p).change_index(exact(p).index() + exact(dp).value()); + return exact(p); + } + + template <typename P, typename D> + P& operator-=(Index_Site<P>& p, const Dindex_Site<D>& dp) + { + exact(p).change_index(exact(p).index() - exact(dp).value()); + return exact(p); + } + + template <typename P, typename S> + P& operator*=(Index_Site<P>& p, const value::scalar_<S>& s) + { + exact(p).change_index(exact(p).index() * s); + return exact(p); + } + + template <typename P, typename S> + P& operator/=(Index_Site<P>& p, const value::scalar_<S>& s) + { + exact(p).change_index(exact(p).index() / s); + return exact(p); + } +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_INDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/dindex_site.hh (revision 4620) @@ -0,0 +1,253 @@ +// 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. + +/// +/// \file +/// +/// Definition of the concept mln::Dindex_Site +/// + +#ifndef MLN_CORE_CONCEPT_DINDEX_SITE_HH +# define MLN_CORE_CONCEPT_DINDEX_SITE_HH + +namespace mln +{ + + // Forward declaration. + template <typename E> struct Dindex_Site; + + + namespace trait + { + + // FIXME: Add promotion. + + template < typename L, typename R > + struct set_binary_< op::plus, + mln::Dindex_Site, L, mln::Dindex_Site, R > + { + typedef L ret; + }; + + template < typename L, typename R > + struct set_binary_< op::minus, + mln::Dindex_Site, L, mln::Dindex_Site, R > + { + typedef L ret; + }; + + template < typename L, typename S> + struct set_binary_< op::plus, + mln::Dindex_Site, L, mln::value::Scalar, S > + { + typedef L ret; + }; + + template < typename L, typename S> + struct set_binary_< op::minus, + mln::Dindex_Site, L, mln::value::Scalar, S > + { + typedef L ret; + }; + + template < typename D, typename S > + struct set_binary_< op::times, + mln::Dindex_Site, D, + mln::value::Scalar, S > + { + typedef D ret; + }; + + template <typename D> + struct set_unary_< op::ord, mln::Dindex_Site, D > + { + typedef mln::internal::ord_less< D > ret; + }; + + } // end of namespace mln::trait + + + + /// Delta point site category flag type. + template <> + struct Dindex_Site<void> + { + typedef Object<void> super; + }; + + + /// FIXME: Doc! + template <typename E> + struct Dindex_Site : public Object<E> + { + typedef Dindex_Site<void> category; + + /* + typedef value_t; + typedef site; + typedef psite; + + const value_t& value(); + void change_value(const value_t&); + */ + + protected: + Dindex_Site(); + }; + + + + // Operators. + + template <typename D> + std::ostream& + operator<<(std::ostream& ostr, const Dindex_Site<D>& dp); + + template <typename L, typename R> + bool + operator==(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + + template <typename L, typename R> + L operator+(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + template <typename L, typename R> + L operator-(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs); + + template <typename L, typename S> + L operator+(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs); + + template <typename L, typename S> + L operator-(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs); + + template <typename D, typename S> + D operator*(const Dindex_Site<D>& lhs, const value::Scalar<S>& rhs); + + + namespace convert + { + + namespace over_load + { + + template <typename D> + void + from_to_(const Dindex_Site<D>& from, mln_site(D)& to); + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Dindex_Site<E>::Dindex_Site() + { + typedef typename E::value_t value_t; + const value_t& (E::*m)() const = & E::value; + m = 0; + } + + + template <typename D> + inline + std::ostream& operator<<(std::ostream& ostr, const Dindex_Site<D>& dp) + { + ostr << '(' << debug::format(exact(dp).value()) << ')'; + return ostr; + } + + + template <typename L, typename R> + inline + bool operator==(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + return exact(lhs).value() == exact(rhs).value(); + } + + template <typename L, typename R> + inline + L operator+(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + L tmp(exact(lhs).value() + exact(rhs).value()); + return tmp; + } + + template <typename L, typename R> + inline + L operator-(const Dindex_Site<L>& lhs, const Dindex_Site<R>& rhs) + { + L tmp(exact(lhs).value() - exact(rhs).value()); + return tmp; + } + + template <typename L, typename S> + inline + L operator+(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs) + { + L tmp(exact(lhs).value() + exact(rhs).to_equiv()); + return tmp; + } + + template <typename L, typename S> + inline + L operator-(const Dindex_Site<L>& lhs, const value::Scalar<S>& rhs) + { + L tmp(exact(lhs).value() - exact(rhs).to_equiv()); + return tmp; + } + + template <typename D, typename S> + D operator*(const Dindex_Site<D>& lhs, const value::Scalar<S>& rhs) + { + D tmp(exact(lhs).value() * exact(rhs).to_equiv()); + return tmp; + } + + namespace convert + { + + namespace over_load + { + + template <typename D> + inline + void + from_to_(const Dindex_Site<D>& dp, mln_site(D)& p) + { + p.change_index(exact(dp).value()); + } + + } // end of namespace mln::convert::over_load + + } // end of namespace mln::convert + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_CONCEPT_DINDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/core/concept/tree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/concept/tree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/concept/tree.hh (revision 4620) @@ -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; + const 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 Index: trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/internal/index_site_base.hh (revision 4620) @@ -0,0 +1,254 @@ +// 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_INTERNAL_INDEX_SITE_BASE_HH +# define MLN_CORE_INTERNAL_INDEX_SITE_BASE_HH + +# include <mln/core/concept/index_site.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/value/concept/integer.hh> + +namespace mln +{ + /// \{ Forward declarations. + namespace literal + { + struct zero_t; + struct one_t; + } + + template <typename E> struct dindex_site; + /// \} + + + namespace internal + { + + template <typename E> struct index_site_base; + + template <typename E = void> + struct index_site_base : public Index_Site<E> + { + typedef index_site_base<E> self; + + typedef index_site_base<E> site; + typedef index_site_base<E> psite; + + typedef dindex_site<E> delta; + typedef dindex_site<E> dpsite; + + typedef unsigned index_t; + + /// Constructors + /// \{ + index_site_base(); + explicit index_site_base(unsigned i); + index_site_base(const literal::zero_t&); + index_site_base(const literal::one_t&); + /// \} + + /// Index materials + /// \{ + /// Return the current index. + const index_t& index() const; + /// Change the current index. + void change_index(const index_t&); + /// Increment the current index. + void inc_index(); + /// Decrement the current index. + void dec_index(); + /// \} + + /// Operators + /// \{ + self& operator+= (const delta&); + self& operator-= (const delta&); + /// \} + + protected: + index_t i_; + }; + + + /// subject_impl specialization (Proxy) + /// \{ + + template <typename P, typename E> + struct subject_impl< const index_site_base<P>, E > + { + //const typename index_site_base<P>::index_t& index() const; + + private: + const E& exact_() const; + }; + + template <typename P, typename E> + struct subject_impl< index_site_base<P>, E > : + subject_impl< const index_site_base<P>, E > + { + //void change_index(const typename index_site_base<P>::index_t& idx); + void inc_index(); + void dec_index(); + + private: + E& exact_(); + }; + + /// \} + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + index_site_base<E>::index_site_base() + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(unsigned i) + : i_ (i) + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(const literal::zero_t&) + : i_ (0) + { + } + + template <typename E> + inline + index_site_base<E>::index_site_base(const literal::one_t&) + : i_ (1) + { + } + + template <typename E> + inline + const typename index_site_base<E>::index_t& + index_site_base<E>::index() const + { + return i_; + } + + template <typename E> + inline + void + index_site_base<E>::dec_index() + { + --i_; + } + + template <typename E> + inline + void + index_site_base<E>::inc_index() + { + ++i_; + } + + + template <typename E> + inline + void + index_site_base<E>::change_index(const index_t& idx) + { + i_ = idx; + } + + template <typename E> + inline + index_site_base<E>& + index_site_base<E>::operator+=(const delta& dp) + { + i_ += dp.value(); + return *this; + } + + template <typename E> + inline + index_site_base<E>& + index_site_base<E>::operator-=(const delta& dp) + { + mln_precondition(dp.value() >= i_); + i_ -= dp.value(); + return *this; + } + + + template <typename P, typename E> + const E& + subject_impl< const index_site_base<P>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename P, typename E> + E& + subject_impl< index_site_base<P>, E >::exact_() + { + return internal::force_exact<E>(*this); + } + + // template <typename P, typename E> + // const typename index_site_base<P>::index_t& + // subject_impl< const index_site_base<P>, E >::index() const + // { + // return exact_().get_subject().index(); + // } + + // template <typename P, typename E> + // void + // subject_impl< index_site_base<P>, E >::change_index(const typename index_site_base<P>::index_t& idx) + // { + // return exact_().get_subject().change_index(idx); + // } + + template <typename P, typename E> + void + subject_impl< index_site_base<P>, E >::inc_index() + { + return exact_().get_subject().inc_index(); + } + + template <typename P, typename E> + void + subject_impl< index_site_base<P>, E >::dec_index() + { + return exact_().get_subject().dec_index(); + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::internal + +} // end of namespace mln + +# include <mln/core/dindex_site.hh> + +#endif // !MLN_CORE_INDEX_SITE_BASE_HH Index: trunk/milena/sandbox/edwin/mln/core/dindex_site.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/core/dindex_site.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/core/dindex_site.hh (revision 4620) @@ -0,0 +1,119 @@ +// 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_DINDEX_SITE_HH +# define MLN_CORE_DINDEX_SITE_HH + +# include <mln/core/concept/index_site.hh> +# include <mln/core/concept/dindex_site.hh> + +namespace mln +{ + /// \{ Forward declarations. + namespace literal { + struct zero_t; + struct one_t; + } + /// \} + + + template <typename P> struct dindex_site; + + template <typename P> + struct dindex_site : public Dindex_Site< dindex_site<P> > + { + typedef P site; + typedef P psite; + + typedef int value_t; + + /// Constructors + /// \{ + dindex_site(); + dindex_site(int i); + dindex_site(const literal::zero_t&); + dindex_site(const literal::one_t&); + /// \} + + /// Value access + /// \{ + const value_t& value() const; + void change_value(const value_t& v); + /// \} + + protected: + value_t v_; + }; + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + dindex_site<P>::dindex_site() + { + } + + template <typename P> + inline + dindex_site<P>::dindex_site(int i) + : v_ (i) + { + } + + template <typename P> + inline + dindex_site<P>::dindex_site(const literal::zero_t&) + : v_ (0) + { + } + + template <typename P> + inline + dindex_site<P>::dindex_site(const literal::one_t&) + : v_ (1) + { + } + + template <typename P> + inline + const typename dindex_site<P>::value_t& + dindex_site<P>::value() const + { + return v_; + } + + template <typename P> + inline + void + dindex_site<P>::change_value(const value_t& v) + { + v_ = v; + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_CORE_DINDEX_SITE_HH Index: trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/ctree.hh (revision 4620) @@ -0,0 +1,589 @@ +// 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. + +/// FIXME: because there're some stuffs not enough clear... +/// In the previous implementation of the morpho tree, the site set and +/// the domain set had the same type, so that +/// E(nodes) is included in E(sites). In fact, (I think) that's a +/// mistake that comes from the representation using parent image. For +/// real, the tree can be considered as a triplet (node_set, function, +/// relationship) (N, F, R) such that F: node -> (site_set, value) and +/// R: parent node -> node and N: the node set. +/// +/// Currently, the node type is not a site but it should +/// be. And so, the set of nodes: nodes_t < Site_Set. +/// We should implement (but I don't know how to make it well) the type +/// Attribute_image < Image that have two kind of sites +/// (node and site of the original image) with +/// overloaded operator(): node -> value +/// mln_psite(nodes_t) -> value +/// +/// + +/// The differences and what they imply. +/// Attribute_image a; Tree t +/// Node_Set nodes; Site_Set s; +/// +/// I'd like to be able to write: +/// a | (subset of t.nodes) as whell as a | (subset of t.domain()) + +// \todo definition of site, psite is ambigous, replace with content_t +// or other. +// \todo node operator ? + + + +#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 <algorithm> + +namespace mln +{ + + /// Forward declaration. + namespace util { namespace ctree { template <typename I> class ctree; } } + + 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> n_nodes_; + std::vector<mln_value(I)> values_; + + const mln_domain(I)& domain_; + typename T::nodes_t nodes_; + }; + + } // 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; + + /// 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 typename super::node_t node_t; + /// The type of node set. + typedef typename super::nodes_t 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; + /// \} + + /// Constructors + /// \{ + ctree(); + + /// 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 Site_Set<S>& s, + mln_ch_value(I, psite)& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes); + /// \} + + /// Misc. + /// \{ + const domain_t& domain() const; + const nodes_t& nodes() const; + bool has(const psite&) const; + bool has(const node_t&) const; + unsigned 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. + 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; + /// \} + + /// Node tests material. + /// \{ + bool is_a_leaf(const node_t&) const; + bool is_a_root(const node_t&) const; + /// \} + + /// Fast access material. + /// \{ + bool has_index(unsigned i) const; + rvalue f_at_(unsigned i) const; + lvalue f_at_(unsigned i); + unsigned parent_at_(unsigned i) const; + unsigned& parent_at_(unsigned i); + unsigned node_at_(const psite& p) const; + unsigned& node_at_(const psite& p); + /// \} + + /// To attribute image + attribute_image<ctree<I>, value> to_image() const; + + /// Site -> node function. + /// \{ + /// Return the map Site -> Node as a V2V function. + //pw::value< mln_ch_value(I, node_t) > mapper() const; + /// \} + + }; + + } // 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> + template <typename S> + inline + ctree<I>::ctree(const Image<I>& f_, + const Site_Set<S>& s_, + mln_ch_value(I, mln_psite(I))& parent, + mln_ch_value(I, unsigned)& area, + unsigned nb_nodes) + { + const I& f = exact(f_); + const S& s = exact(s_); + + mln_precondition(f.is_valid()); + mln_precondition(s.is_valid()); + mln_precondition(parent.is_valid()); + mln_precondition(area.is_valid()); + mln_precondition(f.domain() == parent.domain()); + mln_precondition(f.domain() == area.domain()); + mln_precondition(f.domain().nsites() == s.nsites()); + + this->data_ = new mln::internal::data< ctree<I> >(f); + + initialize(this->data_->map_, f); + this->data_->parent_.resize(nb_nodes); + this->data_->n_nodes_.resize(nb_nodes); + this->data_->values_.resize(nb_nodes); + this->data_->nodes_.init(node_t(*this, 0), nb_nodes); + + //debug::println("Parent: ", parent); + //debug::println("Area: ", area); + + unsigned root_offset = 0; + mln_fwd_piter(S) p(s); + for_all(p) + { + psite q = parent(p); + + if (f(parent(q)) == f(q)) // Canonization + q = (parent(p) = parent(q)); + + if (f(p) == f(q) && p != q) // Not a node. + { + this->data_->map_(p) = this->data_->map_(parent(p)); + } + else + { + unsigned& offset = (p == q) ? root_offset : area(q); + + // Insert Node. + mln_assertion(offset < nb_nodes); + this->data_->map_(p) = offset; + this->data_->parent_[offset] = this->data_->map_(q); + this->data_->values_[offset] = f(p); + this->data_->n_nodes_[offset] = area(p); + area(p) = offset + 1; + offset += this->data_->n_nodes_[offset] + 1; + } + } + } + + + template <typename I> + inline + const mln_domain(I)& + ctree<I>::domain() const + { + return this->data_->domain_; + } + + template <typename I> + inline + const typename ctree<I>::nodes_t& + ctree<I>::nodes() const + { + return this->data_->nodes_; + } + + template <typename I> + inline + unsigned + ctree<I>::n_nodes() const + { + mln_precondition(this->is_valid()); + return this->data_->nodes_.nsites(); + } + + 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()); + return n.index() < this->data_->nodes_.nsites(); + } + + 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()); + 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(n, this->data_->n_nodes_[n.index()] + 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_->n_nodes_[n.index()] == 0); + } + + template <typename I> + inline + bool + ctree<I>::has_index(unsigned i) const + { + mln_precondition(this->is_valid()); + return i <= this->n_nodes(); + } + + template <typename I> + inline + mln_rvalue(I) + ctree<I>::f_at_(unsigned 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_(unsigned i) + { + mln_precondition(this->is_valid()); + mln_precondition(this->has_index(i)); + return this->data_->values_[i]; + } + + template <typename I> + inline + unsigned + ctree<I>::parent_at_(unsigned 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 + unsigned& + ctree<I>::parent_at_(unsigned 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 + unsigned + 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 + unsigned& + 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); + std::copy(this->data_->values_.begin(), this->data_->values_.end(), to.buffer()); + return to; + } + + + } // 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 Index: trunk/milena/sandbox/edwin/mln/util/ctree/node.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/node.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/node.hh (revision 4620) @@ -0,0 +1,183 @@ +// 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/internal/index_site_base.hh> + +namespace mln +{ + + /// Node category flag type. + template <typename E> struct Node {}; + + template <> + struct Node<void> + { + typedef Index_Site<void> super; + }; + + namespace util + { + + namespace ctree + { + + template <typename T> + class node : public internal::index_site_base< node<T> > + { + public: + /// Object category. + typedef Node<void> category; + + typedef internal::index_site_base<node> super; + + typedef typename super::index_t index_t; + + /// Constructors + /// \{ + node(); + node(const Tree<T>& tree); + node(const Tree<T>& tree, const index_t& id); + /// \} + + /// Return whether the node is valid. + const T& tree() const; + void change_target(const Tree<T>& tree); + + private: + const T* tree_; + }; + + } // 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 > : + subject_impl< const internal::index_site_base< util::ctree::node<T> > , E > + { + 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 >, + subject_impl< internal::index_site_base< util::ctree::node<T> > , E > + { + }; + + /// \} + + } // 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, const index_t& i) + : super(i), + tree_ (&(exact(tree))) + { + } + + template <typename T> + inline + const T& + node<T>::tree() const + { + return tree_; + } + + template <typename T> + inline + void + node<T>::change_target(const Tree<T>& tree) + { + tree_ = &(exact(tree)); + } + + + } // end of namespace mln::util::ctree + + } // end of namespace mln::util + + namespace internal + { + + 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 + const T& + subject_impl< const util::ctree::node<T>, E >::tree() const + { + return exact_().get_subject().tree(); + } + + } // end of namespace mln::internal + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // !MLN_UTIL_CTREE_NODE_HH Index: trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh =================================================================== --- trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh (revision 0) +++ trunk/milena/sandbox/edwin/mln/util/ctree/internal/tree_base.hh (revision 4620) @@ -0,0 +1,140 @@ +// 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_run_idx.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 ctree::node<E> node_t; + /// The type of node set. + typedef p_run_idx<node_t> 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; + + public: // Tmp for construction. + util::tracked_ptr< mln::internal::data<E> > data_; + protected: + tree_base(); + }; + +# 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