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