DGtal  0.9.2
CubicalComplex.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file CubicalComplex.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
21  *
22  * @date 2015/08/28
23  *
24  * Implementation of inline methods defined in CubicalComplex.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 #include <queue>
33 #include "DGtal/base/SetFunctions.h"
34 //////////////////////////////////////////////////////////////////////////////
35 
36 ///////////////////////////////////////////////////////////////////////////////
37 // IMPLEMENTATION of inline methods.
38 ///////////////////////////////////////////////////////////////////////////////
39 
40 ///////////////////////////////////////////////////////////////////////////////
41 // ----------------------- Standard services ------------------------------
42 
43 //-----------------------------------------------------------------------------
44 template <typename TKSpace, typename TCellContainer>
45 inline
46 DGtal::CubicalComplex<TKSpace, TCellContainer>::
47 ~CubicalComplex()
48 {
49 }
50 
51 //-----------------------------------------------------------------------------
52 template <typename TKSpace, typename TCellContainer>
53 inline
54 DGtal::CubicalComplex<TKSpace, TCellContainer>::
55 CubicalComplex()
56  : myKSpace( 0 ), myCells( dimension+1 )
57 {
58 }
59 
60 //-----------------------------------------------------------------------------
61 template <typename TKSpace, typename TCellContainer>
62 inline
63 DGtal::CubicalComplex<TKSpace, TCellContainer>::
64 CubicalComplex( ConstAlias<KSpace> aK )
65  : myKSpace( &aK ), myCells( dimension+1 )
66 {
67 }
68 
69 //-----------------------------------------------------------------------------
70 template <typename TKSpace, typename TCellContainer>
71 inline
72 DGtal::CubicalComplex<TKSpace, TCellContainer>::
73 CubicalComplex( const CubicalComplex& other )
74  : myKSpace( other.myKSpace ), myCells( other.myCells )
75 {
76 }
77 
78 //-----------------------------------------------------------------------------
79 template <typename TKSpace, typename TCellContainer>
80 template <typename TDigitalSet>
81 inline
82 void DGtal::CubicalComplex<TKSpace, TCellContainer>::
83 construct( const TDigitalSet & set )
84 {
85  assert ( TDigitalSet::Domain::dimension == dimension );
86  for ( typename TDigitalSet::ConstIterator it = set.begin(); it != set.end(); ++it )
87  {
88  typedef typename TKSpace::Cells CellsCollection;
89  typename TKSpace::Cell cell = myKSpace->uSpel ( *it );
90  insertCell ( cell );
91  CellsCollection n = myKSpace->uFaces ( cell );
92  for ( typename CellsCollection::ConstIterator itt = n.begin() ; itt < n.end(); ++itt )
93  insertCell ( *itt );
94  }
95 }
96 
97 //-----------------------------------------------------------------------------
98 template <typename TKSpace, typename TCellContainer>
99 inline
100 const typename DGtal::CubicalComplex<TKSpace, TCellContainer>::KSpace &
101 DGtal::CubicalComplex<TKSpace, TCellContainer>::
102 space() const
103 {
104  return *myKSpace;
105 }
106 
107 //-----------------------------------------------------------------------------
108 template <typename TKSpace, typename TCellContainer>
109 inline
110 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
111 DGtal::CubicalComplex<TKSpace, TCellContainer>::
112 begin() const
113 {
114  return ConstIterator( *this, 0 );
115 }
116 
117 //-----------------------------------------------------------------------------
118 template <typename TKSpace, typename TCellContainer>
119 inline
120 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
121 DGtal::CubicalComplex<TKSpace, TCellContainer>::
122 end() const
123 {
124  return ConstIterator( *this, dimension+1 );
125 }
126 
127 //-----------------------------------------------------------------------------
128 template <typename TKSpace, typename TCellContainer>
129 inline
130 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
131 DGtal::CubicalComplex<TKSpace, TCellContainer>::
132 begin()
133 {
134  return Iterator( *this, 0 );
135 }
136 
137 //-----------------------------------------------------------------------------
138 template <typename TKSpace, typename TCellContainer>
139 inline
140 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
141 DGtal::CubicalComplex<TKSpace, TCellContainer>::
142 end()
143 {
144  return Iterator( *this, dimension+1 );
145 }
146 
147 //-----------------------------------------------------------------------------
148 template <typename TKSpace, typename TCellContainer>
149 inline
150 DGtal::CubicalComplex<TKSpace, TCellContainer>&
151 DGtal::CubicalComplex<TKSpace, TCellContainer>::
152 operator=( const CubicalComplex& other )
153 {
154  if ( this != &other )
155  {
156  myKSpace = other.myKSpace;
157  myCells = other.myCells;
158  }
159  return *this;
160 }
161 
162 //-----------------------------------------------------------------------------
163 template <typename TKSpace, typename TCellContainer>
164 inline
165 void
166 DGtal::CubicalComplex<TKSpace, TCellContainer>::
167 clear()
168 {
169  for ( Dimension d = 0; d <= dimension; ++d )
170  clear( d );
171 }
172 
173 //-----------------------------------------------------------------------------
174 template <typename TKSpace, typename TCellContainer>
175 inline
176 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
177 DGtal::CubicalComplex<TKSpace, TCellContainer>::
178 count( const Cell& aCell ) const
179 {
180  return belongs( aCell ) ? 1 : 0;
181 }
182 
183 //-----------------------------------------------------------------------------
184 template <typename TKSpace, typename TCellContainer>
185 inline
186 void
187 DGtal::CubicalComplex<TKSpace, TCellContainer>::
188 clear( Dimension d )
189 {
190  myCells[ d ].clear();
191 }
192 //-----------------------------------------------------------------------------
193 template <typename TKSpace, typename TCellContainer>
194 inline
195 void
196 DGtal::CubicalComplex<TKSpace, TCellContainer>::
197 fillData( Data data )
198 {
199  for ( Dimension d = 0; d <= dimension; ++d )
200  clearData( d, data );
201 }
202 //-----------------------------------------------------------------------------
203 template <typename TKSpace, typename TCellContainer>
204 inline
205 void
206 DGtal::CubicalComplex<TKSpace, TCellContainer>::
207 fillData( Dimension d, Data data )
208 {
209  ASSERT( d <= dimension );
210  for ( CellMapIterator it = begin( d ), itE = end( d ); it != itE; ++it )
211  {
212  it->second = data;
213  }
214 }
215 
216 //-----------------------------------------------------------------------------
217 template <typename TKSpace, typename TCellContainer>
218 inline
219 DGtal::Dimension
220 DGtal::CubicalComplex<TKSpace, TCellContainer>::
221 dim() const
222 {
223  Dimension d = myCells.size()-1;
224  for ( typename std::vector<CellMap>::const_reverse_iterator it = myCells.rbegin(), itE = myCells.rend();
225  it != itE; ++it, --d )
226  if ( ! it->empty() ) return d;
227  return 0;
228 }
229 //-----------------------------------------------------------------------------
230 template <typename TKSpace, typename TCellContainer>
231 inline
232 DGtal::Dimension
233 DGtal::CubicalComplex<TKSpace, TCellContainer>::
234 dim( const Cell& c ) const
235 {
236  return myKSpace->uDim( c );
237 }
238 
239 //-----------------------------------------------------------------------------
240 template <typename TKSpace, typename TCellContainer>
241 inline
242 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
243 DGtal::CubicalComplex<TKSpace, TCellContainer>::
244 nbCells( Dimension d ) const
245 {
246  return myCells[ d ].size();
247 }
248 
249 //-----------------------------------------------------------------------------
250 template <typename TKSpace, typename TCellContainer>
251 inline
252 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
253 DGtal::CubicalComplex<TKSpace, TCellContainer>::
254 size() const
255 {
256  Size n = 0;
257  for ( Dimension d = 0; d <= dimension; ++d )
258  n += myCells[ d ].size();
259  return n;
260 }
261 //-----------------------------------------------------------------------------
262 template <typename TKSpace, typename TCellContainer>
263 inline
264 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
265 DGtal::CubicalComplex<TKSpace, TCellContainer>::
266 max_size() const
267 {
268  ASSERT( isValid() );
269  Point p = space().uKCoords( space().upperCell() )
270  - space().uKCoords( space().lowerCell() );
271  Size n = (Size) p.norm( Point::L_1 );
272  return n;
273 }
274 
275 //-----------------------------------------------------------------------------
276 template <typename TKSpace, typename TCellContainer>
277 inline
278 bool
279 DGtal::CubicalComplex<TKSpace, TCellContainer>::
280 empty() const
281 {
282  for ( Dimension d = 0; d <= dimension; ++d )
283  if ( ! myCells[ d ].empty() ) return false;
284  return true;
285 }
286 
287 //-----------------------------------------------------------------------------
288 template <typename TKSpace, typename TCellContainer>
289 inline
290 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Integer
291 DGtal::CubicalComplex<TKSpace, TCellContainer>::
292 euler() const
293 {
294  Integer n = 0;
295  bool pos = true;
296  for ( typename std::vector<CellMap>::const_iterator it = myCells.begin(), itE = myCells.end();
297  it != itE; ++it )
298  {
299  n += pos ? (Integer) it->size() : -(Integer) it->size();
300  pos = ! pos;
301  }
302  return n;
303 }
304 
305 //-----------------------------------------------------------------------------
306 template <typename TKSpace, typename TCellContainer>
307 inline
308 std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator,
309  typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator >
310 DGtal::CubicalComplex<TKSpace, TCellContainer>::
311 equal_range( const Cell& aCell )
312 {
313  Dimension d = myKSpace->uDim( aCell );
314  std::pair< CellMapIterator, CellMapIterator > pIt
315  = myCells[ d ].equal_range( aCell );
316  return std::make_pair( Iterator( *this, d, pIt->first ),
317  Iterator( *this, d, pIt->second ) );
318 }
319 
320 //-----------------------------------------------------------------------------
321 template <typename TKSpace, typename TCellContainer>
322 inline
323 std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator,
324  typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator >
325 DGtal::CubicalComplex<TKSpace, TCellContainer>::
326 equal_range( const Cell& aCell ) const
327 {
328  Dimension d = myKSpace->uDim( aCell );
329  std::pair< CellMapConstIterator, CellMapConstIterator > pIt
330  = myCells[ d ].equal_range( aCell );
331  return std::make_pair( ConstIterator( *this, d, pIt->first ),
332  ConstIterator( *this, d, pIt->second ) );
333 }
334 
335 //-----------------------------------------------------------------------------
336 template <typename TKSpace, typename TCellContainer>
337 inline
338 void
339 DGtal::CubicalComplex<TKSpace, TCellContainer>::
340 erase( Iterator it )
341 {
342  eraseCell( it.myIt );
343 }
344 
345 //-----------------------------------------------------------------------------
346 template <typename TKSpace, typename TCellContainer>
347 inline
348 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
349 DGtal::CubicalComplex<TKSpace, TCellContainer>::
350 erase( const Cell& aCell )
351 {
352  return eraseCell( aCell );
353 }
354 
355 //-----------------------------------------------------------------------------
356 template <typename TKSpace, typename TCellContainer>
357 inline
358 void
359 DGtal::CubicalComplex<TKSpace, TCellContainer>::
360 erase( Iterator first, Iterator last )
361 {
362  while ( first != last )
363  {
364  Iterator tmp = first++;
365  erase( tmp );
366  }
367 }
368 
369 //-----------------------------------------------------------------------------
370 template <typename TKSpace, typename TCellContainer>
371 inline
372 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
373 DGtal::CubicalComplex<TKSpace, TCellContainer>::
374 find( const Cell& aCell )
375 {
376  Dimension d = myKSpace->uDim( aCell );
377  CellMapIterator cmIt = findCell( d, aCell );
378  if ( cmIt == end( d ) ) return Iterator( *this, d+1 );
379  else return Iterator( *this, d, cmIt );
380 }
381 
382 //-----------------------------------------------------------------------------
383 template <typename TKSpace, typename TCellContainer>
384 inline
385 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
386 DGtal::CubicalComplex<TKSpace, TCellContainer>::
387 find( const Cell& aCell ) const
388 {
389  Dimension d = myKSpace->uDim( aCell );
390  CellMapConstIterator cmIt = findCell( d, aCell );
391  if ( cmIt == end( d ) ) return ConstIterator( *this, d+1 );
392  else return ConstIterator( *this, d, cmIt );
393 }
394 
395 //-----------------------------------------------------------------------------
396 template <typename TKSpace, typename TCellContainer>
397 inline
398 std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator,
399  bool >
400 DGtal::CubicalComplex<TKSpace, TCellContainer>::
401 insert( const Cell& aCell )
402 {
403  Dimension d = myKSpace->uDim( aCell );
404  std::pair< CellMapIterator,bool > pIt
405  = myCells[ d ].insert( std::make_pair( aCell, Data() ) );
406  return ( pIt.first == myCells[ d ].end() )
407  ? std::make_pair( Iterator( *this, dimension+1 ), false )
408  : std::make_pair( Iterator( *this, d, pIt.first ), pIt.second );
409 }
410 
411 //-----------------------------------------------------------------------------
412 template <typename TKSpace, typename TCellContainer>
413 inline
414 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
415 DGtal::CubicalComplex<TKSpace, TCellContainer>::
416 insert( Iterator position, const Cell& aCell )
417 {
418  Dimension d = myKSpace->uDim( aCell );
419  if ( position.dimension() == d )
420  return Iterator( *this, d,
421  myCells[ d ].insert( position.myIt,
422  std::make_pair( aCell, Data() ) ) );
423  else
424  return Iterator( *this, d,
425  myCells[ d ].insert( std::make_pair( aCell, Data() ) ).first );
426 }
427 //-----------------------------------------------------------------------------
428 template <typename TKSpace, typename TCellContainer>
429 template <class InputIterator>
430 inline
431 void
432 DGtal::CubicalComplex<TKSpace, TCellContainer>::
433 insert( InputIterator first, InputIterator last )
434 {
435  for ( ; first != last; ++first )
436  insert( *first );
437 }
438 
439 //-----------------------------------------------------------------------------
440 template <typename TKSpace, typename TCellContainer>
441 inline
442 void
443 DGtal::CubicalComplex<TKSpace, TCellContainer>::
444 swap( CubicalComplex& other )
445 {
446  if ( other != *this )
447  { // Swap space with special care of invalid complexes.
448  if ( myKSpace == 0 ) myKSpace = other.myKSpace;
449  else if ( other.myKSpace == 0 ) other.myKSpace = myKSpace;
450  else std::swap( myKSpace, other.myKSpace );
451  myCells.swap( other.myCells );
452  }
453 }
454 
455 
456 //-----------------------------------------------------------------------------
457 template <typename TKSpace, typename TCellContainer>
458 inline
459 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Data&
460 DGtal::CubicalComplex<TKSpace, TCellContainer>::
461 operator[]( const Cell& aCell )
462 {
463  Dimension d = space().uDim( aCell );
464  return myCells[ d ][ aCell ];
465 }
466 
467 //-----------------------------------------------------------------------------
468 template <typename TKSpace, typename TCellContainer>
469 inline
470 bool
471 DGtal::CubicalComplex<TKSpace, TCellContainer>::
472 operator()( const Cell& aCell ) const
473 {
474  Dimension d = space().uDim( aCell );
475  return findCell( d, aCell ) != end( d );
476 }
477 
478 //-----------------------------------------------------------------------------
479 template <typename TKSpace, typename TCellContainer>
480 inline
481 void
482 DGtal::CubicalComplex<TKSpace, TCellContainer>::
483 insertCell( const Cell& aCell, const Data& data )
484 {
485  insertCell( myKSpace->uDim( aCell ), aCell, data );
486 }
487 //-----------------------------------------------------------------------------
488 template <typename TKSpace, typename TCellContainer>
489 inline
490 void
491 DGtal::CubicalComplex<TKSpace, TCellContainer>::
492 insertCell( Dimension d, const Cell& aCell, const Data& data )
493 {
494  myCells[ d ][ aCell ] = data;
495 }
496 
497 //-----------------------------------------------------------------------------
498 template <typename TKSpace, typename TCellContainer>
499 template <typename CellConstIterator>
500 inline
501 void
502 DGtal::CubicalComplex<TKSpace, TCellContainer>::
503 insertCells( CellConstIterator it, CellConstIterator itE, const Data& data )
504 {
505  for ( ; it != itE; ++it )
506  insertCell( *it, data );
507 }
508 
509 //-----------------------------------------------------------------------------
510 template <typename TKSpace, typename TCellContainer>
511 template <typename CellConstIterator>
512 inline
513 void
514 DGtal::CubicalComplex<TKSpace, TCellContainer>::
515 insertCells( Dimension d, CellConstIterator it, CellConstIterator itE, const Data& data )
516 {
517  for ( ; it != itE; ++it )
518  insertCell( d, *it, data );
519 }
520 
521 //-----------------------------------------------------------------------------
522 template <typename TKSpace, typename TCellContainer>
523 inline
524 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
525 DGtal::CubicalComplex<TKSpace, TCellContainer>::
526 eraseCell( const Cell& aCell )
527 {
528  return eraseCell( myKSpace->uDim( aCell ), aCell );
529 }
530 
531 //-----------------------------------------------------------------------------
532 template <typename TKSpace, typename TCellContainer>
533 inline
534 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
535 DGtal::CubicalComplex<TKSpace, TCellContainer>::
536 eraseCell( Dimension d, const Cell& aCell )
537 {
538  return (Size) myCells[ d ].erase( aCell );
539 }
540 
541 //-----------------------------------------------------------------------------
542 template <typename TKSpace, typename TCellContainer>
543 inline
544 void
545 DGtal::CubicalComplex<TKSpace, TCellContainer>::
546 eraseCell( CellMapIterator it )
547 {
548  Dimension d = myKSpace->uDim( it->first );
549  myCells[ d ].erase( it );
550 }
551 
552 //-----------------------------------------------------------------------------
553 template <typename TKSpace, typename TCellContainer>
554 inline
555 void
556 DGtal::CubicalComplex<TKSpace, TCellContainer>::
557 eraseCells( CellMapIterator it, CellMapIterator itE )
558 {
559  for ( ; it != itE; ++it )
560  eraseCell( it );
561 }
562 
563 //-----------------------------------------------------------------------------
564 template <typename TKSpace, typename TCellContainer>
565 template <typename CellConstIterator>
566 inline
567 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
568 DGtal::CubicalComplex<TKSpace, TCellContainer>::
569 eraseCells( CellConstIterator it, CellConstIterator itE )
570 {
571  Size nb = 0;
572  for ( ; it != itE; ++it )
573  nb += eraseCell( *it );
574 }
575 
576 //-----------------------------------------------------------------------------
577 template <typename TKSpace, typename TCellContainer>
578 template <typename CellConstIterator>
579 inline
580 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
581 DGtal::CubicalComplex<TKSpace, TCellContainer>::
582 eraseCells( Dimension d, CellConstIterator it, CellConstIterator itE )
583 {
584  Size nb = 0;
585  for ( ; it != itE; ++it )
586  nb += eraseCell( d, *it );
587 }
588 
589 //-----------------------------------------------------------------------------
590 template <typename TKSpace, typename TCellContainer>
591 inline
592 bool
593 DGtal::CubicalComplex<TKSpace, TCellContainer>::
594 belongs( const Cell& aCell ) const
595 {
596  return belongs( myKSpace->uDim( aCell ), aCell );
597 }
598 //-----------------------------------------------------------------------------
599 template <typename TKSpace, typename TCellContainer>
600 inline
601 bool
602 DGtal::CubicalComplex<TKSpace, TCellContainer>::
603 belongs( Dimension d, const Cell& aCell ) const
604 {
605  ASSERT( d <= dimension );
606  CellMapConstIterator it = myCells[ d ].find( aCell );
607  return it != myCells[ d ].end();
608 }
609 //-----------------------------------------------------------------------------
610 template <typename TKSpace, typename TCellContainer>
611 template <typename CellOutputIterator>
612 inline
613 void
614 DGtal::CubicalComplex<TKSpace, TCellContainer>::
615 faces( CellOutputIterator& outIt, const Cell& aCell, bool hintClosed ) const
616 {
617  Cells all_proper_faces = myKSpace->uFaces( aCell );
618  if ( hintClosed )
619  std::copy( all_proper_faces.begin(), all_proper_faces.end(), outIt );
620  else
621  for ( typename Cells::ConstIterator it = all_proper_faces.begin(),
622  itE = all_proper_faces.end(); it != itE; ++it )
623  if ( belongs( *it ) )
624  *outIt++ = *it;
625 }
626 //-----------------------------------------------------------------------------
627 template <typename TKSpace, typename TCellContainer>
628 template <typename CellOutputIterator>
629 inline
630 void
631 DGtal::CubicalComplex<TKSpace, TCellContainer>::
632 coFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintOpen ) const
633 {
634  Cells all_proper_co_faces = myKSpace->uCoFaces( aCell );
635  if ( hintOpen )
636  std::copy( all_proper_co_faces.begin(), all_proper_co_faces.end(), outIt );
637  else
638  for ( typename Cells::ConstIterator it = all_proper_co_faces.begin(),
639  itE = all_proper_co_faces.end(); it != itE; ++it )
640  if ( belongs( *it ) )
641  *outIt++ = *it;
642 }
643 //-----------------------------------------------------------------------------
644 template <typename TKSpace, typename TCellContainer>
645 template <typename CellOutputIterator>
646 inline
647 void
648 DGtal::CubicalComplex<TKSpace, TCellContainer>::
649 directFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintClosed ) const
650 {
651  Cells all_direct_faces = myKSpace->uLowerIncident( aCell );
652  if ( hintClosed )
653  std::copy( all_direct_faces.begin(), all_direct_faces.end(), outIt );
654  else
655  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
656  itE = all_direct_faces.end(); it != itE; ++it )
657  if ( belongs( *it ) )
658  *outIt++ = *it;
659 }
660 //-----------------------------------------------------------------------------
661 template <typename TKSpace, typename TCellContainer>
662 template <typename CellMapIteratorOutputIterator>
663 inline
664 void
665 DGtal::CubicalComplex<TKSpace, TCellContainer>::
666 directFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell )
667 {
668  Cells all_direct_faces = myKSpace->uLowerIncident( aCell );
669  Dimension k = dim( aCell );
670  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
671  itE = all_direct_faces.end(); it != itE; ++it )
672  {
673  CellMapIterator map_it = findCell( *it );
674  if ( map_it != end( k-1 ) )
675  *outIt++ = map_it;
676  }
677 }
678 //-----------------------------------------------------------------------------
679 template <typename TKSpace, typename TCellContainer>
680 template <typename CellOutputIterator>
681 inline
682 void
683 DGtal::CubicalComplex<TKSpace, TCellContainer>::
684 directCoFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintOpen ) const
685 {
686  Cells all_direct_co_faces = myKSpace->uUpperIncident( aCell );
687  if ( hintOpen )
688  std::copy( all_direct_co_faces.begin(), all_direct_co_faces.end(), outIt );
689  else
690  for ( typename Cells::ConstIterator it = all_direct_co_faces.begin(),
691  itE = all_direct_co_faces.end(); it != itE; ++it )
692  if ( belongs( *it ) )
693  *outIt++ = *it;
694 }
695 //-----------------------------------------------------------------------------
696 template <typename TKSpace, typename TCellContainer>
697 template <typename CellMapIteratorOutputIterator>
698 inline
699 void
700 DGtal::CubicalComplex<TKSpace, TCellContainer>::
701 directCoFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell )
702 {
703  Cells all_direct_faces = myKSpace->uUpperIncident( aCell );
704  Dimension k = dim( aCell );
705  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
706  itE = all_direct_faces.end(); it != itE; ++it )
707  {
708  CellMapIterator map_it = findCell( *it );
709  if ( map_it != end( k+1 ) )
710  *outIt++ = map_it;
711  }
712 }
713 
714 //-----------------------------------------------------------------------------
715 template <typename TKSpace, typename TCellContainer>
716 inline
717 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
718 DGtal::CubicalComplex<TKSpace, TCellContainer>::
719 begin( Dimension d ) const
720 {
721  return myCells[ d ].begin();
722 }
723 
724 //-----------------------------------------------------------------------------
725 template <typename TKSpace, typename TCellContainer>
726 inline
727 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
728 DGtal::CubicalComplex<TKSpace, TCellContainer>::
729 end( Dimension d ) const
730 {
731  return myCells[ d ].end();
732 }
733 
734 //-----------------------------------------------------------------------------
735 template <typename TKSpace, typename TCellContainer>
736 inline
737 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
738 DGtal::CubicalComplex<TKSpace, TCellContainer>::
739 begin( Dimension d )
740 {
741  return myCells[ d ].begin();
742 }
743 
744 //-----------------------------------------------------------------------------
745 template <typename TKSpace, typename TCellContainer>
746 inline
747 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
748 DGtal::CubicalComplex<TKSpace, TCellContainer>::
749 end( Dimension d )
750 {
751  return myCells[ d ].end();
752 }
753 
754 //-----------------------------------------------------------------------------
755 template <typename TKSpace, typename TCellContainer>
756 inline
757 void
758 DGtal::CubicalComplex<TKSpace, TCellContainer>::
759 close()
760 {
761  close( dim() );
762 }
763 
764 //-----------------------------------------------------------------------------
765 template <typename TKSpace, typename TCellContainer>
766 inline
767 void
768 DGtal::CubicalComplex<TKSpace, TCellContainer>::
769 close( Dimension k )
770 {
771  if ( k <= 0 ) return;
772  Dimension l = k - 1;
773  for ( CellMapConstIterator it = begin( k ), itE = end( k );
774  it != itE; ++it )
775  {
776  Cells direct_faces = myKSpace->uLowerIncident( it->first );
777  for ( typename Cells::const_iterator cells_it = direct_faces.begin(),
778  cells_it_end = direct_faces.end(); cells_it != cells_it_end; ++cells_it )
779  insertCell( l, *cells_it );
780  }
781  close( l );
782 }
783 
784 //-----------------------------------------------------------------------------
785 template <typename TKSpace, typename TCellContainer>
786 inline
787 void
788 DGtal::CubicalComplex<TKSpace, TCellContainer>::
789 open()
790 {
791  open( dim() );
792 }
793 
794 //-----------------------------------------------------------------------------
795 template <typename TKSpace, typename TCellContainer>
796 inline
797 void
798 DGtal::CubicalComplex<TKSpace, TCellContainer>::
799 open( Dimension k )
800 {
801  if ( k < dimension )
802  {
803  Dimension l = k + 1;
804  for ( CellMapIterator it = begin( k ), itE = end( k ); it != itE; )
805  {
806  Cells direct_cofaces = myKSpace->uUpperIncident( it->first );
807  bool is_open = true;
808  for ( typename Cells::const_iterator cells_it = direct_cofaces.begin(),
809  cells_it_end = direct_cofaces.end(); cells_it != cells_it_end; ++cells_it )
810  if ( ! belongs( l, *cells_it ) )
811  {
812  is_open = false;
813  break;
814  }
815  CellMapIterator itMem = it;
816  ++it;
817  if ( ! is_open ) myCells[ k ].erase( itMem );
818  }
819  }
820  if ( k > 0 ) open( k - 1 );
821 }
822 
823 //-----------------------------------------------------------------------------
824 template <typename TKSpace, typename TCellContainer>
825 inline
826 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
827 DGtal::CubicalComplex<TKSpace, TCellContainer>::
828 findCell( const Cell& aCell ) const
829 {
830  return findCell( dim( aCell ), aCell );
831 }
832 
833 //-----------------------------------------------------------------------------
834 template <typename TKSpace, typename TCellContainer>
835 inline
836 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
837 DGtal::CubicalComplex<TKSpace, TCellContainer>::
838 findCell( Dimension d, const Cell& aCell ) const
839 {
840  return myCells[ d ].findCell( aCell );
841 }
842 
843 //-----------------------------------------------------------------------------
844 template <typename TKSpace, typename TCellContainer>
845 inline
846 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
847 DGtal::CubicalComplex<TKSpace, TCellContainer>::
848 findCell( const Cell& aCell )
849 {
850  return findCell( dim( aCell ), aCell );
851 }
852 
853 //-----------------------------------------------------------------------------
854 template <typename TKSpace, typename TCellContainer>
855 inline
856 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
857 DGtal::CubicalComplex<TKSpace, TCellContainer>::
858 findCell( Dimension d, const Cell& aCell )
859 {
860  return myCells[ d ].find( aCell );
861 }
862 
863 
864 
865 //-----------------------------------------------------------------------------
866 template <typename TKSpace, typename TCellContainer>
867 inline
868 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
869 DGtal::CubicalComplex<TKSpace, TCellContainer>::
870 cellBoundary( const Cell& aCell, bool hintClosed ) const
871 {
872  if ( hintClosed ) return myKSpace->uFaces( aCell );
873  Cells proper_faces = myKSpace->uFaces( aCell );
874  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
875  typename Cells::iterator first = proper_faces.begin();
876  typename Cells::iterator last = proper_faces.end();
877  typename Cells::iterator result = first;
878  for ( ; first != last; ++first )
879  {
880  if ( belongs( *first ) )
881  {
882  *result = std::move( *first );
883  ++result;
884  }
885  }
886  proper_faces.resize( result - proper_faces.begin() );
887  return proper_faces;
888 }
889 //-----------------------------------------------------------------------------
890 template <typename TKSpace, typename TCellContainer>
891 inline
892 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
893 DGtal::CubicalComplex<TKSpace, TCellContainer>::
894 cellCoBoundary( const Cell& aCell, bool hintOpen ) const
895 {
896  if ( hintOpen ) return myKSpace->uCoFaces( aCell );
897  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
898  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
899  typename Cells::iterator first = proper_cofaces.begin();
900  typename Cells::iterator last = proper_cofaces.end();
901  typename Cells::iterator result = first;
902  for ( ; first != last; ++first )
903  {
904  if ( belongs( *first ) )
905  {
906  *result = std::move( *first );
907  ++result;
908  }
909  }
910  proper_cofaces.resize( result - proper_cofaces.begin() );
911  return proper_cofaces;
912 }
913 
914 //-----------------------------------------------------------------------------
915 template <typename TKSpace, typename TCellContainer>
916 inline
917 bool
918 DGtal::CubicalComplex<TKSpace, TCellContainer>::
919 isCellInterior( const Cell& aCell ) const
920 {
921  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
922  typename Cells::iterator first = proper_cofaces.begin();
923  typename Cells::iterator last = proper_cofaces.end();
924  for ( ; first != last; ++first )
925  {
926  if ( ! belongs( *first ) ) return false;
927  }
928  return true;
929 }
930 
931 //-----------------------------------------------------------------------------
932 template <typename TKSpace, typename TCellContainer>
933 inline
934 bool
935 DGtal::CubicalComplex<TKSpace, TCellContainer>::
936 isCellBoundary( const Cell& aCell ) const
937 {
938  return ! isCellInterior( aCell );
939 }
940 
941 //-----------------------------------------------------------------------------
942 template <typename TKSpace, typename TCellContainer>
943 inline
944 DGtal::CubicalComplex<TKSpace, TCellContainer>
945 DGtal::CubicalComplex<TKSpace, TCellContainer>::
946 interior() const
947 {
948  CubicalComplex I( space() );
949  for ( Dimension d = 0; d <= dimension; ++d )
950  {
951  for ( CellMapConstIterator it = begin( d ), itE = end( d ); it != itE; ++it )
952  {
953  if ( isCellInterior( it->first ) )
954  I.insertCell( d, it->first, it->second );
955  }
956  }
957  return I;
958 }
959 
960 //-----------------------------------------------------------------------------
961 template <typename TKSpace, typename TCellContainer>
962 inline
963 DGtal::CubicalComplex<TKSpace, TCellContainer>
964 DGtal::CubicalComplex<TKSpace, TCellContainer>::
965 boundary( bool hintClosed ) const
966 {
967  CubicalComplex B( *this );
968  if ( ! hintClosed ) B.close();
969  for ( Dimension d = 0; d <= dimension; ++d )
970  {
971  CellMapIterator itNext;
972  for ( CellMapIterator it = B.begin( d ), itE = B.end( d ); it != itE; )
973  {
974  itNext = it; ++itNext;
975  if ( B.isCellInterior( it->first ) )
976  B.eraseCell( it );
977  it = itNext;
978  }
979  }
980  return B;
981 }
982 
983 //-----------------------------------------------------------------------------
984 template <typename TKSpace, typename TCellContainer>
985 inline
986 void
987 DGtal::CubicalComplex<TKSpace, TCellContainer>::
988 getInteriorAndBoundary( CubicalComplex& intcc, CubicalComplex& bdcc,
989  bool hintClosed ) const
990 {
991  intcc = *this;
992  bdcc = CubicalComplex( this->space() );
993  if ( ! hintClosed ) intcc.close();
994  for ( Dimension d = 0; d <= dimension; ++d )
995  {
996  CellMapIterator itNext;
997  for ( CellMapIterator it = intcc.begin( d ), itE = intcc.end( d ); it != itE; )
998  {
999  itNext = it; ++itNext;
1000  if ( ! intcc.isCellInterior( it->first ) )
1001  {
1002  intcc.eraseCell( it );
1003  bdcc.insertCell( d, it->first, it->second );
1004  }
1005  it = itNext;
1006  }
1007  }
1008 }
1009 
1010 //-----------------------------------------------------------------------------
1011 template <typename TKSpace, typename TCellContainer>
1012 inline
1013 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1014 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1015 closure( const CubicalComplex& S, bool hintClosed ) const
1016 {
1017  CubicalComplex cl_S = S;
1018  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1019  {
1020  Cells cell_faces = cellBoundary( *it, hintClosed );
1021  cl_S.insert( cell_faces.begin(), cell_faces.end() );
1022  }
1023  return cl_S;
1024 }
1025 //-----------------------------------------------------------------------------
1026 template <typename TKSpace, typename TCellContainer>
1027 inline
1028 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1029 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1030 star( const CubicalComplex& S, bool hintOpen ) const
1031 {
1032  CubicalComplex star_S = S;
1033  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1034  {
1035  Cells cell_cofaces = cellCoBoundary( *it, hintOpen );
1036  star_S.insert( cell_cofaces.begin(), cell_cofaces.end() );
1037  }
1038  return star_S;
1039 }
1040 //-----------------------------------------------------------------------------
1041 template <typename TKSpace, typename TCellContainer>
1042 inline
1043 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1044 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1045 link( const CubicalComplex& S, bool hintClosed, bool hintOpen ) const
1046 {
1047  using namespace ::DGtal::functions;
1048  CubicalComplex cl_star_S = closure( star ( S, hintOpen ), hintClosed );
1049  CubicalComplex star_cl_S = star ( closure( S, hintClosed ), hintOpen );
1050 
1051  // Calls a specializable difference of sets operation.
1052  return cl_star_S - star_cl_S;
1053 }
1054 
1055 //-----------------------------------------------------------------------------
1056 template <typename TKSpace, typename TCellContainer>
1057 inline
1058 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellType
1059 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1060 computeCellType( const Cell& c, CellMapIterator& it_cell_up, Dimension n )
1061 {
1062  // Check if it is a maximal cell
1063  Dimension k = dim( c );
1064  if ( k == n ) return Maximal;
1065 
1066  std::vector< CellMapIterator > Q_up;
1067  std::back_insert_iterator< std::vector< CellMapIterator > > back_it( Q_up );
1068  this->directCoFacesIterators( back_it, c );
1069 
1070  // Filtering unwanted up-incident cells.
1071  uint32_t nb = 0;
1072  for ( typename std::vector< CellMapIterator >::const_iterator it = Q_up.begin(), itE = Q_up.end();
1073  it != itE; ++it )
1074  {
1075  uint32_t& data = (*it)->second.data;
1076  if ( ! ( data & COLLAPSIBLE ) ) return Any;
1077  if ( ! ( data & REMOVED ) )
1078  {
1079  ++nb;
1080  if ( nb > 1 ) return Any;
1081  it_cell_up = *it;
1082  }
1083  }
1084  return ( nb != 0 ) ? Free : Maximal ;
1085 }
1086 
1087 
1088 
1089 ///////////////////////////////////////////////////////////////////////////////
1090 // Interface - public :
1091 
1092 /**
1093  * Writes/Displays the object on an output stream.
1094  * @param out the output stream where the object is written.
1095  */
1096 template <typename TKSpace, typename TCellContainer>
1097 inline
1098 void
1099 DGtal::CubicalComplex<TKSpace, TCellContainer>::selfDisplay ( std::ostream & out ) const
1100 {
1101  out << "[CubicalComplex dim=" << dim() << " chi=" << euler();
1102  for ( Dimension i = 0; i < myCells.size(); ++i )
1103  out << " #" << i << "=" << myCells[ i ].size();
1104  out << "]";
1105 }
1106 
1107 /**
1108  * Checks the validity/consistency of the object.
1109  * @return 'true' if the object is valid, 'false' otherwise.
1110  */
1111 template <typename TKSpace, typename TCellContainer>
1112 inline
1113 bool
1114 DGtal::CubicalComplex<TKSpace, TCellContainer>::isValid() const
1115 {
1116  return true;
1117 }
1118 
1119 //-----------------------------------------------------------------------------
1120 template <typename TKSpace, typename TCellContainer>
1121 inline
1122 std::string
1123 DGtal::CubicalComplex<TKSpace, TCellContainer>::className() const
1124 {
1125  return "CubicalComplex";
1126 }
1127 
1128 
1129 
1130 ///////////////////////////////////////////////////////////////////////////////
1131 // Implementation of inline functions //
1132 
1133 template <typename TKSpace, typename TCellContainer>
1134 inline
1135 std::ostream&
1136 DGtal::operator<< ( std::ostream & out,
1137  const CubicalComplex<TKSpace, TCellContainer> & object )
1138 {
1139  object.selfDisplay( out );
1140  return out;
1141 }
1142 
1143 // //
1144 ///////////////////////////////////////////////////////////////////////////////
1145 
1146