DGtal  0.9.4.1
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 = static_cast<Dimension>((int)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 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
717 DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d)
718 {
719  return myCells[d];
720 }
721 
722 template <typename TKSpace, typename TCellContainer>
723 const typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
724 DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d) const
725 {
726  return myCells[d];
727 }
728 //-----------------------------------------------------------------------------
729 template <typename TKSpace, typename TCellContainer>
730 inline
731 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
732 DGtal::CubicalComplex<TKSpace, TCellContainer>::
733 begin( Dimension d ) const
734 {
735  return myCells[ d ].begin();
736 }
737 
738 //-----------------------------------------------------------------------------
739 template <typename TKSpace, typename TCellContainer>
740 inline
741 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
742 DGtal::CubicalComplex<TKSpace, TCellContainer>::
743 end( Dimension d ) const
744 {
745  return myCells[ d ].end();
746 }
747 
748 //-----------------------------------------------------------------------------
749 template <typename TKSpace, typename TCellContainer>
750 inline
751 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
752 DGtal::CubicalComplex<TKSpace, TCellContainer>::
753 begin( Dimension d )
754 {
755  return myCells[ d ].begin();
756 }
757 
758 //-----------------------------------------------------------------------------
759 template <typename TKSpace, typename TCellContainer>
760 inline
761 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
762 DGtal::CubicalComplex<TKSpace, TCellContainer>::
763 end( Dimension d )
764 {
765  return myCells[ d ].end();
766 }
767 
768 //-----------------------------------------------------------------------------
769 template <typename TKSpace, typename TCellContainer>
770 inline
771 void
772 DGtal::CubicalComplex<TKSpace, TCellContainer>::
773 close()
774 {
775  close( dim() );
776 }
777 
778 //-----------------------------------------------------------------------------
779 template <typename TKSpace, typename TCellContainer>
780 inline
781 void
782 DGtal::CubicalComplex<TKSpace, TCellContainer>::
783 close( Dimension k )
784 {
785  if ( k <= 0 ) return;
786  Dimension l = k - 1;
787  for ( CellMapConstIterator it = begin( k ), itE = end( k );
788  it != itE; ++it )
789  {
790  Cells direct_faces = myKSpace->uLowerIncident( it->first );
791  for ( typename Cells::const_iterator cells_it = direct_faces.begin(),
792  cells_it_end = direct_faces.end(); cells_it != cells_it_end; ++cells_it )
793  insertCell( l, *cells_it );
794  }
795  close( l );
796 }
797 
798 //-----------------------------------------------------------------------------
799 template <typename TKSpace, typename TCellContainer>
800 inline
801 void
802 DGtal::CubicalComplex<TKSpace, TCellContainer>::
803 open()
804 {
805  open( dim() );
806 }
807 
808 //-----------------------------------------------------------------------------
809 template <typename TKSpace, typename TCellContainer>
810 inline
811 void
812 DGtal::CubicalComplex<TKSpace, TCellContainer>::
813 open( Dimension k )
814 {
815  if ( k < dimension )
816  {
817  Dimension l = k + 1;
818  for ( CellMapIterator it = begin( k ), itE = end( k ); it != itE; )
819  {
820  Cells direct_cofaces = myKSpace->uUpperIncident( it->first );
821  bool is_open = true;
822  for ( typename Cells::const_iterator cells_it = direct_cofaces.begin(),
823  cells_it_end = direct_cofaces.end(); cells_it != cells_it_end; ++cells_it )
824  if ( ! belongs( l, *cells_it ) )
825  {
826  is_open = false;
827  break;
828  }
829  CellMapIterator itMem = it;
830  ++it;
831  if ( ! is_open ) myCells[ k ].erase( itMem );
832  }
833  }
834  if ( k > 0 ) open( k - 1 );
835 }
836 
837 //-----------------------------------------------------------------------------
838 template <typename TKSpace, typename TCellContainer>
839 inline
840 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
841 DGtal::CubicalComplex<TKSpace, TCellContainer>::
842 findCell( const Cell& aCell ) const
843 {
844  return findCell( dim( aCell ), aCell );
845 }
846 
847 //-----------------------------------------------------------------------------
848 template <typename TKSpace, typename TCellContainer>
849 inline
850 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
851 DGtal::CubicalComplex<TKSpace, TCellContainer>::
852 findCell( Dimension d, const Cell& aCell ) const
853 {
854  return myCells[ d ].find( aCell );
855 }
856 
857 //-----------------------------------------------------------------------------
858 template <typename TKSpace, typename TCellContainer>
859 inline
860 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
861 DGtal::CubicalComplex<TKSpace, TCellContainer>::
862 findCell( const Cell& aCell )
863 {
864  return findCell( dim( aCell ), aCell );
865 }
866 
867 //-----------------------------------------------------------------------------
868 template <typename TKSpace, typename TCellContainer>
869 inline
870 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
871 DGtal::CubicalComplex<TKSpace, TCellContainer>::
872 findCell( Dimension d, const Cell& aCell )
873 {
874  return myCells[ d ].find( aCell );
875 }
876 
877 
878 
879 //-----------------------------------------------------------------------------
880 template <typename TKSpace, typename TCellContainer>
881 inline
882 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
883 DGtal::CubicalComplex<TKSpace, TCellContainer>::
884 cellBoundary( const Cell& aCell, bool hintClosed ) const
885 {
886  if ( hintClosed ) return myKSpace->uFaces( aCell );
887  Cells proper_faces = myKSpace->uFaces( aCell );
888  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
889  typename Cells::iterator first = proper_faces.begin();
890  typename Cells::iterator last = proper_faces.end();
891  typename Cells::iterator result = first;
892  for ( ; first != last; ++first )
893  {
894  if ( belongs( *first ) )
895  {
896  *result = std::move( *first );
897  ++result;
898  }
899  }
900  proper_faces.resize( result - proper_faces.begin() );
901  return proper_faces;
902 }
903 //-----------------------------------------------------------------------------
904 template <typename TKSpace, typename TCellContainer>
905 inline
906 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
907 DGtal::CubicalComplex<TKSpace, TCellContainer>::
908 cellCoBoundary( const Cell& aCell, bool hintOpen ) const
909 {
910  if ( hintOpen ) return myKSpace->uCoFaces( aCell );
911  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
912  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
913  typename Cells::iterator first = proper_cofaces.begin();
914  typename Cells::iterator last = proper_cofaces.end();
915  typename Cells::iterator result = first;
916  for ( ; first != last; ++first )
917  {
918  if ( belongs( *first ) )
919  {
920  *result = std::move( *first );
921  ++result;
922  }
923  }
924  proper_cofaces.resize( result - proper_cofaces.begin() );
925  return proper_cofaces;
926 }
927 
928 //-----------------------------------------------------------------------------
929 template <typename TKSpace, typename TCellContainer>
930 inline
931 bool
932 DGtal::CubicalComplex<TKSpace, TCellContainer>::
933 isCellInterior( const Cell& aCell ) const
934 {
935  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
936  typename Cells::iterator first = proper_cofaces.begin();
937  typename Cells::iterator last = proper_cofaces.end();
938  for ( ; first != last; ++first )
939  {
940  if ( ! belongs( *first ) ) return false;
941  }
942  return true;
943 }
944 
945 //-----------------------------------------------------------------------------
946 template <typename TKSpace, typename TCellContainer>
947 inline
948 bool
949 DGtal::CubicalComplex<TKSpace, TCellContainer>::
950 isCellBoundary( const Cell& aCell ) const
951 {
952  return ! isCellInterior( aCell );
953 }
954 
955 //-----------------------------------------------------------------------------
956 template <typename TKSpace, typename TCellContainer>
957 inline
958 DGtal::CubicalComplex<TKSpace, TCellContainer>
959 DGtal::CubicalComplex<TKSpace, TCellContainer>::
960 interior() const
961 {
962  CubicalComplex I( space() );
963  for ( Dimension d = 0; d <= dimension; ++d )
964  {
965  for ( CellMapConstIterator it = begin( d ), itE = end( d ); it != itE; ++it )
966  {
967  if ( isCellInterior( it->first ) )
968  I.insertCell( d, it->first, it->second );
969  }
970  }
971  return I;
972 }
973 
974 //-----------------------------------------------------------------------------
975 template <typename TKSpace, typename TCellContainer>
976 inline
977 DGtal::CubicalComplex<TKSpace, TCellContainer>
978 DGtal::CubicalComplex<TKSpace, TCellContainer>::
979 boundary( bool hintClosed ) const
980 {
981  CubicalComplex B( *this );
982  if ( ! hintClosed ) B.close();
983  for ( Dimension d = 0; d <= dimension; ++d )
984  {
985  CellMapIterator itNext;
986  for ( CellMapIterator it = B.begin( d ), itE = B.end( d ); it != itE; )
987  {
988  itNext = it; ++itNext;
989  if ( B.isCellInterior( it->first ) )
990  B.eraseCell( it );
991  it = itNext;
992  }
993  }
994  return B;
995 }
996 
997 //-----------------------------------------------------------------------------
998 template <typename TKSpace, typename TCellContainer>
999 inline
1000 void
1001 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1002 getInteriorAndBoundary( CubicalComplex& intcc, CubicalComplex& bdcc,
1003  bool hintClosed ) const
1004 {
1005  intcc = *this;
1006  bdcc = CubicalComplex( this->space() );
1007  if ( ! hintClosed ) intcc.close();
1008  for ( Dimension d = 0; d <= dimension; ++d )
1009  {
1010  CellMapIterator itNext;
1011  for ( CellMapIterator it = intcc.begin( d ), itE = intcc.end( d ); it != itE; )
1012  {
1013  itNext = it; ++itNext;
1014  if ( ! intcc.isCellInterior( it->first ) )
1015  {
1016  intcc.eraseCell( it );
1017  bdcc.insertCell( d, it->first, it->second );
1018  }
1019  it = itNext;
1020  }
1021  }
1022 }
1023 
1024 //-----------------------------------------------------------------------------
1025 template <typename TKSpace, typename TCellContainer>
1026 inline
1027 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1028 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1029 closure( const CubicalComplex& S, bool hintClosed ) const
1030 {
1031  CubicalComplex cl_S = S;
1032  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1033  {
1034  Cells cell_faces = cellBoundary( *it, hintClosed );
1035  cl_S.insert( cell_faces.begin(), cell_faces.end() );
1036  }
1037  return cl_S;
1038 }
1039 //-----------------------------------------------------------------------------
1040 template <typename TKSpace, typename TCellContainer>
1041 inline
1042 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1043 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1044 star( const CubicalComplex& S, bool hintOpen ) const
1045 {
1046  CubicalComplex star_S = S;
1047  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1048  {
1049  Cells cell_cofaces = cellCoBoundary( *it, hintOpen );
1050  star_S.insert( cell_cofaces.begin(), cell_cofaces.end() );
1051  }
1052  return star_S;
1053 }
1054 //-----------------------------------------------------------------------------
1055 template <typename TKSpace, typename TCellContainer>
1056 inline
1057 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1058 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1059 link( const CubicalComplex& S, bool hintClosed, bool hintOpen ) const
1060 {
1061  using namespace ::DGtal::functions;
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