data.hh 15.2 KB
Newer Older
1
2
// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory
// (LRDE)
3
//
4
// This file is part of the Milena Library.  This library is free
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License version 2 as published by the
// Free Software Foundation.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 51 Franklin Street, Fifth Floor,
// Boston, MA 02111-1307, USA.
//
// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

#ifndef MLN_MORPHO_TREE_DATA_HH
# define MLN_MORPHO_TREE_DATA_HH

/// \file mln/morpho/tree/data.hh
///
Thierry Geraud's avatar
Thierry Geraud committed
34
/// \todo Think about site iterator (using image site iterator instead
35
/// of S container iterator) to go faster.
36
37

# include <mln/morpho/tree/compute_parent.hh>
Guillaume Lazzara's avatar
Guillaume Lazzara committed
38
# include <mln/core/site_set/p_array.hh>
39
40
41
42
43
44
45
46
# include <mln/core/internal/site_set_iterator_base.hh>
# include <mln/core/internal/piter_identity.hh>
# include <deque>

# define mln_up_site_piter(T)	typename T::up_site_piter
# define mln_dn_site_piter(T)	typename T::dn_site_piter
# define mln_up_node_piter(T)	typename T::up_node_piter
# define mln_dn_node_piter(T)	typename T::dn_node_piter
47
48
# define mln_up_leaf_piter(T)	typename T::up_leaf_piter
# define mln_dn_leaf_piter(T)	typename T::dn_leaf_piter
49
50
51
# define mln_site_piter(T)	typename T::site_piter
# define mln_node_piter(T)	typename T::node_piter
# define mln_leaf_piter(T)	typename T::leaf_piter
52
# define mln_depth1st_piter(T)	typename T::depth1st_piter
53
54
55
56
57

# define mln_up_site_piter_(T)	T::up_site_piter
# define mln_dn_site_piter_(T)  T::dn_site_piter
# define mln_up_node_piter_(T)  T::up_node_piter
# define mln_dn_node_piter_(T)  T::dn_node_piter
58
59
# define mln_up_leaf_piter_(T)	T::up_leaf_piter
# define mln_dn_leaf_piter_(T)	T::dn_leaf_piter
60
61
62
# define mln_site_piter_(T)	T::site_piter
# define mln_node_piter_(T)	T::node_piter
# define mln_leaf_piter_(T)	T::leaf_piter
63
# define mln_depth1st_piter_(T) T::depth1st_piter
64

Thierry Geraud's avatar
Thierry Geraud committed
65

66
67
68
69
70
71
72
73
74
namespace mln
{

  namespace morpho
  {

    namespace tree
    {

75
76
77
78
79
80
81
82
83
84
85
86
87
88
      // Forward declarations.

      /// Iterate on tree's sites from leaves to roots.
      template <typename T> struct up_site_piter;

      /// Iterate on tree's sites from roots to leaves.
      template <typename T> struct dn_site_piter;

      /// Iterate on tree's nodes (component representants) from leaves to roots.
      template <typename T> struct up_node_piter;

      /// Iterate on tree's nodes (component representants) from leaves to roots.
      template <typename T> struct dn_node_piter;

89
90
91
92
93
94
      /// Iterate on tree's leaves in the same way of up_node_piter.
      template <typename T> struct up_leaf_piter;

      /// Iterate on tree's leaves in the same way of dn_node_piter.
      template <typename T> struct dn_leaf_piter;

95
96
      /// Depth1st tree traversal iterator.
      template <typename T> struct depth1st_piter;
97
98


99
100
101
      template <typename I, typename S>
      class data
      {
102
	typedef data<I, S> self_;
103

104
      public:
105
106
	/// Associated type of the function f.
	typedef I function;
107
108
109
110
111
	/// Psite associated type.
	typedef mln_psite(I) psite;
	typedef mln_site(I) site;
	/// Site set associated type.
	typedef S sites_t;
112
	/// Node set associated type.
113
	typedef p_array<mln_psite(I)> nodes_t;
114
115
	/// Leaf set associated type.
	typedef p_array<mln_psite(I)> leaves_t;
116
117
118
119
120
121
122

	/// Parent image associated type.
	typedef mln_ch_value(I, mln_psite(I)) parent_t;

	// Iterate on all sites.
	typedef mln::morpho::tree::up_site_piter<self_> up_site_piter;
	typedef mln::morpho::tree::dn_site_piter<self_> dn_site_piter;
123
	typedef up_site_piter site_piter;
124
125
126
127

	// Iterate on nodes only.
	typedef mln::morpho::tree::up_node_piter<self_> up_node_piter;
	typedef mln::morpho::tree::dn_node_piter<self_> dn_node_piter;
128
	typedef up_node_piter node_piter;
129

130
131
132
	// Iterate on leaves only.
	typedef mln::morpho::tree::up_leaf_piter<self_> up_leaf_piter;
	typedef mln::morpho::tree::dn_leaf_piter<self_> dn_leaf_piter;
133
	typedef up_leaf_piter leaf_piter;
134

135
	typedef mln::morpho::tree::depth1st_piter<self_> depth1st_piter;
136

Thierry Geraud's avatar
Thierry Geraud committed
137

138
	/// Constructor.
139
	template <typename N>
140
	data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh);
141
142
143
144
145



	/// \{ Parent-related materials.

146
147
	const mln_psite(I)& parent(const mln_psite(I)& p) const;
	const parent_t& parent_image() const;
148

149
150
	/// \}

151
152
	/// \{ Child-related materials.

153
154
	const p_array<mln_psite(I)>& children(const mln_psite(I)& p) const;
	const mln_ch_value(I, nodes_t)& children_image() const;
155

156
	/// \}
157

158
	/// \{ Nodes materials.
159

160
	const p_array<mln_psite(I)>& nodes() const;
161

162
	/// \}
163

164
	/// \{ Leaves materials.
165

166
	const p_array<mln_psite(I)>& leaves() const;
167

168
	/// \}
Guillaume Lazzara's avatar
Guillaume Lazzara committed
169

170
	/// \{ Sites materials.
171
172

	const S& domain() const;
173

174
175
	/// \}

176
177
178
179
180
181
182
183
184
185
186
187
188
189
190


	/// \{ Tests.

	bool is_valid() const;
	bool is_root(const mln_psite(I)& p) const;
	bool is_a_node(const mln_psite(I)& p) const;
	bool is_a_non_root_node(const mln_psite(I)& p) const;
	bool is_a_leaf(const mln_psite(I)& p) const;

	/// \}




191
	unsigned nroots() const;
192
193


194
	const I& f() const;
195
196


197
	mln_rvalue(I) f(const mln_psite(I)& p) const;
198

199

200
201
202
203
204
205
      protected:
	const function& f_;
	const sites_t& s_;
	mln_ch_value(I, mln_psite(I)) parent_;	// Parent image.
	mln_ch_value(I, nodes_t) children_;	// Children image.
	nodes_t nodes_;
206
	leaves_t leaves_;
207
208
	unsigned nroots_;
      };
Edwin Carlinet's avatar
Edwin Carlinet committed
209

210

211
212
      /* Iterators */

213
214
215
      template <typename T>
      struct up_site_piter
	: public mln::internal::piter_identity_< typename T::sites_t::bkd_piter,	// Adaptee.
216
						 up_site_piter<T> >			// Exact.
217
218
219
220
221
222
223
      {
      private:
	typedef typename T::sites_t::bkd_piter Pi_;
	typedef mln::internal::piter_identity_< Pi_, up_site_piter<T> > super_;

      public:
	up_site_piter(const T& t)
224
	{
225
	  this->change_target(t.domain());
226
227
	}

228
229
230
231
232
	up_site_piter(const Pi_& pi)
	  : super_(pi)
	{
	}
      };
233

234
235
236
237
238
239
240
241
      template <typename T>
      struct dn_site_piter
	: public mln::internal::piter_identity_< typename T::sites_t::fwd_piter,	// Adaptee.
						 dn_site_piter<T> >			// Exact.
      {
      private:
	typedef typename T::sites_t::fwd_piter Pi_;
	typedef mln::internal::piter_identity_< Pi_, dn_site_piter<T> > super_;
242

243
244
245
246
247
      public:
	dn_site_piter(const T& t)
	{
	  this->change_target(t.domain());
	}
248

249
250
	dn_site_piter(const Pi_& pi)
	  : super_(pi)
251
252
	{
	}
253
      };
Edwin Carlinet's avatar
Edwin Carlinet committed
254

255
256
257
258
259
260
      template <typename T>
      struct up_node_piter
	: public mln::internal::piter_identity_< typename T::nodes_t::fwd_piter,	// Adaptee.
						 up_node_piter<T> >			// Exact.
      {
      private:
261
	typedef typename T::nodes_t::fwd_piter Pi_;
262
	typedef mln::internal::piter_identity_< Pi_, up_node_piter<T> > super_;
263

264
265
      public:
	up_node_piter(const T& t)
266
	{
267
	  this->change_target(t.nodes());
268
269
	}

270
271
	up_node_piter(const Pi_& pi)
	  : super_(pi)
272
273
	{
	}
274
      };
275

276
277
278
279
280
281
      template <typename T>
      struct dn_node_piter
	: public mln::internal::piter_identity_< typename T::nodes_t::bkd_piter,	// Adaptee.
						 dn_node_piter<T> >			// Exact.
      {
      private:
282
	typedef typename T::nodes_t::bkd_piter Pi_;
283
284
285
286
	typedef mln::internal::piter_identity_< Pi_, dn_node_piter<T> > super_;

      public:
	dn_node_piter(const T& t)
287
	{
288
	  this->change_target(t.nodes());
289
290
	}

291
292
293
294
	dn_node_piter(const Pi_& pi)
	  : super_(pi)
	{
	}
295
296
      };

297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
      template <typename T>
      struct up_leaf_piter
	: public mln::internal::piter_identity_< typename T::leaves_t::fwd_piter,	// Adaptee.
						 up_leaf_piter<T> >			// Exact.
      {
      private:
	typedef typename T::leaves_t::fwd_piter Pi_;
	typedef mln::internal::piter_identity_< Pi_, up_leaf_piter<T> > super_;

      public:
	up_leaf_piter(const T& t)
	{
	  this->change_target(t.leaves());
	}

	up_leaf_piter(const Pi_& pi)
	  : super_(pi)
	{
	}
      };

      template <typename T>
      struct dn_leaf_piter
	: public mln::internal::piter_identity_< typename T::leaves_t::bkd_piter,	// Adaptee.
						 dn_leaf_piter<T> >			// Exact.
      {
      private:
	typedef typename T::leaves_t::bkd_piter Pi_;
	typedef mln::internal::piter_identity_< Pi_, dn_leaf_piter<T> > super_;

      public:
	dn_leaf_piter(const T& t)
	{
	  this->change_target(t.leaves());
	}

	dn_leaf_piter(const Pi_& pi)
	  : super_(pi)
	{
	}
      };

339
      template <typename T>
340
341
      class depth1st_piter
	: public mln::internal::site_set_iterator_base< T, depth1st_piter<T> >
342
      {
343
	typedef depth1st_piter<T> self_;
344
345
346
347
348
	typedef mln::internal::site_set_iterator_base<T, self_> super_;

      public:

	/// Constructor with no argument.
349
	depth1st_piter();
350
351

	/// Constructor.
352
	depth1st_piter(const T& t);
353

354

355
	depth1st_piter(const T& t,
356
357
		       const mln_psite(T::function)& p);

358
359
360
361
362
363
364
365
366
367
368
369
	/// 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_();

370
371
372
	/// Skip current point children. Next call to next() goes to the brother point.
	void skip_children();

373
374
375
376
	unsigned get_depth() {
	  return stack_.size() - 1;
	}

377
378
379
      protected:
	using super_::p_;
	using super_::s_;
380
381
	std::deque<mln_psite(T::function)> stack_; // FIXME: implement p_stack.
	const mln_psite(T::function)* root_;
382
383
  };

384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399



# ifndef MLN_INCLUDE_ONLY

      template <typename I, typename S>
      template <typename N>
      inline
      data<I,S>::data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh)
	: f_(exact(f)),
	  s_(exact(s))
      {
	const N& nbh_ = exact(nbh);

	// Compute parent image.
	parent_ = morpho::tree::compute_parent(f_, nbh_, s_);
400
	initialize(children_, f);
401

402
403
404
405
	// Store tree nodes.
	nroots_ = 0;
	mln_bkd_piter(S) p(s_);
	for_all(p)
406
	{
407
	  if (f_(parent_(p)) != f_(p))
408
409
	    {
	      nodes_.insert(p);
410
	      children_(parent_(p)).insert(p);
411
412
413
414
415
416
417
418
419
	      if (is_a_leaf(p))
		leaves_.insert(p);
	    }
	  else if (parent_(p) == p) //it's a root.
	    {
	      nodes_.insert(p);
	      if (is_a_leaf(p)) // One pixel image...
		leaves_.insert(p);
	      ++nroots_;
420
	    }
Edwin Carlinet's avatar
Edwin Carlinet committed
421
	}
422
	mln_assertion(leaves_.nsites() > 0);
423
424
425
426
427
428
429
430
431
432
433
      }

      template <typename I, typename S>
      inline
      const mln_psite(I)&
      data<I,S>::parent(const mln_psite(I)& p) const
      {
	mln_precondition(is_valid());
	mln_precondition(parent_.domain().has(p));
	return parent_(p);
      }
Edwin Carlinet's avatar
Edwin Carlinet committed
434

435
436
437
438
439
440
441
442
      template <typename I, typename S>
      inline
      const mln_ch_value(I, mln_psite(I))&
      data<I,S>::parent_image() const
      {
	mln_precondition(is_valid());
	return parent_;
      }
Edwin Carlinet's avatar
Edwin Carlinet committed
443

444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
      template <typename I, typename S>
      inline
      bool
      data<I,S>::is_valid() const
      {
	return parent_.is_valid(); // FIXME: and... (?)
      }

      template <typename I, typename S>
      inline
      bool
      data<I,S>::is_root(const mln_psite(I)& p) const
      {
	mln_precondition(is_valid());
	mln_precondition(parent_.domain().has(p));
	return parent_(p) == p;
      }


      template <typename I, typename S>
      inline
      bool
      data<I,S>::is_a_node(const mln_psite(I)& p) const
      {
	mln_precondition(is_valid());
	mln_precondition(parent_.domain().has(p));
	return parent_(p) == p || f_(parent_(p)) != f_(p);
471
472
      }

473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
      template <typename I, typename S>
      inline
      bool
      data<I,S>::is_a_non_root_node(const mln_psite(I)& p) const
      {
	mln_precondition(is_valid());
	mln_precondition(parent_.domain().has(p));
	return f_(parent_(p)) != f_(p);
      }


      template <typename I, typename S>
      inline
      bool
      data<I,S>::is_a_leaf(const mln_psite(I)& p) const
      {
	mln_precondition(is_valid());
	mln_precondition(children_.domain().has(p));
	return children_(p).nsites() == 0;
      }

      template <typename I, typename S>
      inline
      const p_array<mln_psite(I)>&
      data<I,S>::nodes() const
      {
	mln_precondition(is_valid());
	return nodes_;
      }

503
504
505
506
507
508
509
510
511
      template <typename I, typename S>
      inline
      const p_array<mln_psite(I)>&
      data<I,S>::leaves() const
      {
	mln_precondition(is_valid());
	return leaves_;
      }

512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
      template <typename I, typename S>
      inline
      const S&
      data<I,S>::domain() const
      {
	return s_;
      }

      template <typename I, typename S>
      inline
      unsigned
      data<I,S>::nroots() const
      {
	return nroots_;
      }

      template <typename I, typename S>
      inline
      const I&
      data<I,S>::f() const
      {
	return f_;
      }

      template <typename I, typename S>
      inline
      mln_rvalue(I)
      data<I,S>::f(const mln_psite(I)& p) const
      {
	return f_(p);
      }

544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
      template <typename I, typename S>
      inline
      const p_array<mln_psite(I)>&
      data<I,S>::children(const mln_psite(I)& p) const
      {
	return children_(p);
      }

      template <typename I, typename S>
      inline
      const mln_ch_value(I, p_array<mln_psite(I)>)&
      data<I,S>::children_image() const
      {
	return children_;
      }

560
561
562
563
564
565
566


      // Iterators.


      template <typename T>
      inline
567
      depth1st_piter<T>::depth1st_piter()
568
	: root_ (0)
569
570
571
572
573
      {
      }

      template <typename T>
      inline
574
      depth1st_piter<T>::depth1st_piter(const T& t)
575
576
577
578
579
580
581
	: root_ (0)
      {
	this->change_target(t);
      }

      template <typename T>
      inline
582
      depth1st_piter<T>::depth1st_piter(const T& t,
583
584
					const mln_psite(T::function)& p)
	: root_ (&p)
585
      {
586
	mln_assertion(t.is_a_node(p));
587
588
589
590
591
592
	this->change_target(t);
      }

      template <typename T>
      inline
      bool
593
      depth1st_piter<T>::is_valid_() const
594
595
596
597
598
599
600
      {
	return !stack_.empty();
      }

      template <typename T>
      inline
      void
601
      depth1st_piter<T>::invalidate_()
602
603
604
605
606
607
608
      {
	stack_.clear();
      }

      template <typename T>
      inline
      void
609
      depth1st_piter<T>::start_()
610
611
      {
	this->invalidate();
612
613
614
615
616
	stack_.push_back(mln_psite(T::function)()); // needed for last element.

	if (root_)
	  stack_.push_back(*root_);
	else
617
	  {
618
	    mln_dn_node_piter(T) n(*s_);
619
	    unsigned roots = 0;
620
621
622
623
624
625
	    for (n.start(); n.is_valid() && roots < s_->nroots(); n.next())
	      if (s_->is_root(n))
		{
		  stack_.push_back(n);
		  roots++;
		}
626
627
628
629
630
631
632
633
	  }

	this->next();
      }

      template <typename T>
      inline
      void
634
      depth1st_piter<T>::next_()
635
636
637
      {
	p_ = stack_.back();
	stack_.pop_back();
638
639
	if (!exact(this)->is_valid())
	  return;
640
641
642
643
644
	mln_fwd_piter(T::nodes_t) child(s_->children(p_));
	for_all(child)
	  stack_.push_back(child);
      }

645
646
647
      template <typename T>
      inline
      void
648
      depth1st_piter<T>::skip_children()
649
650
651
652
653
      {
	while (stack_.size() != 1 && s_->parent(stack_.back()) == p_)
	  stack_.pop_back();
      }

654

655
656
657
658
659
660
661
662
663
664
# endif // ! MLN_INCLUDE_ONLY

    } // end of namespace mln::morpho::tree

  } // end of namespace mln::morpho

} // end of namespace mln


#endif // ! MLN_MORPHO_TREE_DATA_HH