DGtal  1.5.beta
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  fillData( 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 inline
613 bool
614 DGtal::CubicalComplex<TKSpace, TCellContainer>::
615 belongs( const PreCell& aCell ) const
616 {
617  return belongs( TKSpace::PreCellularGridSpace::uDim( aCell ), aCell );
618 }
619 //-----------------------------------------------------------------------------
620 template <typename TKSpace, typename TCellContainer>
621 inline
622 bool
623 DGtal::CubicalComplex<TKSpace, TCellContainer>::
624 belongs( Dimension d, const PreCell& aCell ) const
625 {
626  if (!myKSpace->uIsValid(aCell)) return false;
627  return belongs(d, myKSpace->uCell(aCell) );
628 }
629 //-----------------------------------------------------------------------------
630 template <typename TKSpace, typename TCellContainer>
631 template <typename CellOutputIterator>
632 inline
633 void
634 DGtal::CubicalComplex<TKSpace, TCellContainer>::
635 faces( CellOutputIterator& outIt, const Cell& aCell, bool hintClosed ) const
636 {
637  Cells all_proper_faces = myKSpace->uFaces( aCell );
638  if ( hintClosed )
639  std::copy( all_proper_faces.begin(), all_proper_faces.end(), outIt );
640  else
641  for ( typename Cells::ConstIterator it = all_proper_faces.begin(),
642  itE = all_proper_faces.end(); it != itE; ++it )
643  if ( belongs( *it ) )
644  *outIt++ = *it;
645 }
646 //-----------------------------------------------------------------------------
647 template <typename TKSpace, typename TCellContainer>
648 template <typename CellOutputIterator>
649 inline
650 void
651 DGtal::CubicalComplex<TKSpace, TCellContainer>::
652 coFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintOpen ) const
653 {
654  Cells all_proper_co_faces = myKSpace->uCoFaces( aCell );
655  if ( hintOpen )
656  std::copy( all_proper_co_faces.begin(), all_proper_co_faces.end(), outIt );
657  else
658  for ( typename Cells::ConstIterator it = all_proper_co_faces.begin(),
659  itE = all_proper_co_faces.end(); it != itE; ++it )
660  if ( belongs( *it ) )
661  *outIt++ = *it;
662 }
663 //-----------------------------------------------------------------------------
664 template <typename TKSpace, typename TCellContainer>
665 template <typename CellOutputIterator>
666 inline
667 void
668 DGtal::CubicalComplex<TKSpace, TCellContainer>::
669 directFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintClosed ) const
670 {
671  Cells all_direct_faces = myKSpace->uLowerIncident( aCell );
672  if ( hintClosed )
673  std::copy( all_direct_faces.begin(), all_direct_faces.end(), outIt );
674  else
675  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
676  itE = all_direct_faces.end(); it != itE; ++it )
677  if ( belongs( *it ) )
678  *outIt++ = *it;
679 }
680 //-----------------------------------------------------------------------------
681 template <typename TKSpace, typename TCellContainer>
682 template <typename CellMapIteratorOutputIterator>
683 inline
684 void
685 DGtal::CubicalComplex<TKSpace, TCellContainer>::
686 directFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell )
687 {
688  Cells all_direct_faces = myKSpace->uLowerIncident( aCell );
689  Dimension k = dim( aCell );
690  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
691  itE = all_direct_faces.end(); it != itE; ++it )
692  {
693  CellMapIterator map_it = findCell( *it );
694  if ( map_it != end( k-1 ) )
695  *outIt++ = map_it;
696  }
697 }
698 //-----------------------------------------------------------------------------
699 template <typename TKSpace, typename TCellContainer>
700 template <typename CellOutputIterator>
701 inline
702 void
703 DGtal::CubicalComplex<TKSpace, TCellContainer>::
704 directCoFaces( CellOutputIterator& outIt, const Cell& aCell, bool hintOpen ) const
705 {
706  Cells all_direct_co_faces = myKSpace->uUpperIncident( aCell );
707  if ( hintOpen )
708  std::copy( all_direct_co_faces.begin(), all_direct_co_faces.end(), outIt );
709  else
710  for ( typename Cells::ConstIterator it = all_direct_co_faces.begin(),
711  itE = all_direct_co_faces.end(); it != itE; ++it )
712  if ( belongs( *it ) )
713  *outIt++ = *it;
714 }
715 //-----------------------------------------------------------------------------
716 template <typename TKSpace, typename TCellContainer>
717 template <typename CellMapIteratorOutputIterator>
718 inline
719 void
720 DGtal::CubicalComplex<TKSpace, TCellContainer>::
721 directCoFacesIterators( CellMapIteratorOutputIterator& outIt, const Cell& aCell )
722 {
723  Cells all_direct_faces = myKSpace->uUpperIncident( aCell );
724  Dimension k = dim( aCell );
725  for ( typename Cells::ConstIterator it = all_direct_faces.begin(),
726  itE = all_direct_faces.end(); it != itE; ++it )
727  {
728  CellMapIterator map_it = findCell( *it );
729  if ( map_it != end( k+1 ) )
730  *outIt++ = map_it;
731  }
732 }
733 
734 //-----------------------------------------------------------------------------
735 template <typename TKSpace, typename TCellContainer>
736 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
737 DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d)
738 {
739  return myCells[d];
740 }
741 
742 template <typename TKSpace, typename TCellContainer>
743 const typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
744 DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d) const
745 {
746  return myCells[d];
747 }
748 //-----------------------------------------------------------------------------
749 template <typename TKSpace, typename TCellContainer>
750 inline
751 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
752 DGtal::CubicalComplex<TKSpace, TCellContainer>::
753 begin( Dimension d ) const
754 {
755  return myCells[ d ].begin();
756 }
757 
758 //-----------------------------------------------------------------------------
759 template <typename TKSpace, typename TCellContainer>
760 inline
761 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
762 DGtal::CubicalComplex<TKSpace, TCellContainer>::
763 end( Dimension d ) const
764 {
765  return myCells[ d ].end();
766 }
767 
768 //-----------------------------------------------------------------------------
769 template <typename TKSpace, typename TCellContainer>
770 inline
771 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
772 DGtal::CubicalComplex<TKSpace, TCellContainer>::
773 begin( Dimension d )
774 {
775  return myCells[ d ].begin();
776 }
777 
778 //-----------------------------------------------------------------------------
779 template <typename TKSpace, typename TCellContainer>
780 inline
781 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
782 DGtal::CubicalComplex<TKSpace, TCellContainer>::
783 end( Dimension d )
784 {
785  return myCells[ d ].end();
786 }
787 
788 //-----------------------------------------------------------------------------
789 template <typename TKSpace, typename TCellContainer>
790 inline
791 void
792 DGtal::CubicalComplex<TKSpace, TCellContainer>::
793 close()
794 {
795  close( dim() );
796 }
797 
798 //-----------------------------------------------------------------------------
799 template <typename TKSpace, typename TCellContainer>
800 inline
801 void
802 DGtal::CubicalComplex<TKSpace, TCellContainer>::
803 close( Dimension k )
804 {
805  if ( k <= 0 ) return;
806  Dimension l = k - 1;
807  for ( CellMapConstIterator it = begin( k ), itE = end( k );
808  it != itE; ++it )
809  {
810  Cells direct_faces = myKSpace->uLowerIncident( it->first );
811  for ( typename Cells::const_iterator cells_it = direct_faces.begin(),
812  cells_it_end = direct_faces.end(); cells_it != cells_it_end; ++cells_it )
813  insertCell( l, *cells_it );
814  }
815  close( l );
816 }
817 
818 //-----------------------------------------------------------------------------
819 template <typename TKSpace, typename TCellContainer>
820 inline
821 void
822 DGtal::CubicalComplex<TKSpace, TCellContainer>::
823 open()
824 {
825  open( dim() );
826 }
827 
828 //-----------------------------------------------------------------------------
829 template <typename TKSpace, typename TCellContainer>
830 inline
831 void
832 DGtal::CubicalComplex<TKSpace, TCellContainer>::
833 open( Dimension k )
834 {
835  if ( k < dimension )
836  {
837  Dimension l = k + 1;
838  for ( CellMapIterator it = begin( k ), itE = end( k ); it != itE; )
839  {
840  Cells direct_cofaces = myKSpace->uUpperIncident( it->first );
841  bool is_open = true;
842  for ( typename Cells::const_iterator cells_it = direct_cofaces.begin(),
843  cells_it_end = direct_cofaces.end(); cells_it != cells_it_end; ++cells_it )
844  if ( ! belongs( l, *cells_it ) )
845  {
846  is_open = false;
847  break;
848  }
849  CellMapIterator itMem = it;
850  ++it;
851  if ( ! is_open ) myCells[ k ].erase( itMem );
852  }
853  }
854  if ( k > 0 ) open( k - 1 );
855 }
856 
857 //-----------------------------------------------------------------------------
858 template <typename TKSpace, typename TCellContainer>
859 inline
860 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
861 DGtal::CubicalComplex<TKSpace, TCellContainer>::
862 findCell( const Cell& aCell ) const
863 {
864  return findCell( dim( aCell ), aCell );
865 }
866 
867 //-----------------------------------------------------------------------------
868 template <typename TKSpace, typename TCellContainer>
869 inline
870 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
871 DGtal::CubicalComplex<TKSpace, TCellContainer>::
872 findCell( Dimension d, const Cell& aCell ) const
873 {
874  return myCells[ d ].find( aCell );
875 }
876 
877 //-----------------------------------------------------------------------------
878 template <typename TKSpace, typename TCellContainer>
879 inline
880 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
881 DGtal::CubicalComplex<TKSpace, TCellContainer>::
882 findCell( const Cell& aCell )
883 {
884  return findCell( dim( aCell ), aCell );
885 }
886 
887 //-----------------------------------------------------------------------------
888 template <typename TKSpace, typename TCellContainer>
889 inline
890 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
891 DGtal::CubicalComplex<TKSpace, TCellContainer>::
892 findCell( Dimension d, const Cell& aCell )
893 {
894  return myCells[ d ].find( aCell );
895 }
896 
897 
898 
899 //-----------------------------------------------------------------------------
900 template <typename TKSpace, typename TCellContainer>
901 inline
902 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
903 DGtal::CubicalComplex<TKSpace, TCellContainer>::
904 cellBoundary( const Cell& aCell, bool hintClosed ) const
905 {
906  if ( hintClosed ) return myKSpace->uFaces( aCell );
907  Cells proper_faces = myKSpace->uFaces( aCell );
908  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
909  typename Cells::iterator first = proper_faces.begin();
910  typename Cells::iterator last = proper_faces.end();
911  typename Cells::iterator result = first;
912  for ( ; first != last; ++first )
913  {
914  if ( belongs( *first ) )
915  {
916  *result = std::move( *first );
917  ++result;
918  }
919  }
920  proper_faces.resize( result - proper_faces.begin() );
921  return proper_faces;
922 }
923 //-----------------------------------------------------------------------------
924 template <typename TKSpace, typename TCellContainer>
925 inline
926 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
927 DGtal::CubicalComplex<TKSpace, TCellContainer>::
928 cellCoBoundary( const Cell& aCell, bool hintOpen ) const
929 {
930  if ( hintOpen ) return myKSpace->uCoFaces( aCell );
931  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
932  // NB: (JOL) do not use std::remove_if since predicate is passed by value.
933  typename Cells::iterator first = proper_cofaces.begin();
934  typename Cells::iterator last = proper_cofaces.end();
935  typename Cells::iterator result = first;
936  for ( ; first != last; ++first )
937  {
938  if ( belongs( *first ) )
939  {
940  *result = std::move( *first );
941  ++result;
942  }
943  }
944  proper_cofaces.resize( result - proper_cofaces.begin() );
945  return proper_cofaces;
946 }
947 
948 //-----------------------------------------------------------------------------
949 template <typename TKSpace, typename TCellContainer>
950 inline
951 bool
952 DGtal::CubicalComplex<TKSpace, TCellContainer>::
953 isCellInterior( const Cell& aCell ) const
954 {
955  Cells proper_cofaces = myKSpace->uCoFaces( aCell );
956  typename Cells::iterator first = proper_cofaces.begin();
957  typename Cells::iterator last = proper_cofaces.end();
958  for ( ; first != last; ++first )
959  {
960  if ( ! belongs( *first ) ) return false;
961  }
962  return true;
963 }
964 
965 //-----------------------------------------------------------------------------
966 template <typename TKSpace, typename TCellContainer>
967 inline
968 bool
969 DGtal::CubicalComplex<TKSpace, TCellContainer>::
970 isCellBoundary( const Cell& aCell ) const
971 {
972  return ! isCellInterior( aCell );
973 }
974 
975 //-----------------------------------------------------------------------------
976 template <typename TKSpace, typename TCellContainer>
977 inline
978 DGtal::CubicalComplex<TKSpace, TCellContainer>
979 DGtal::CubicalComplex<TKSpace, TCellContainer>::
980 interior() const
981 {
982  CubicalComplex I( space() );
983  for ( Dimension d = 0; d <= dimension; ++d )
984  {
985  for ( CellMapConstIterator it = begin( d ), itE = end( d ); it != itE; ++it )
986  {
987  if ( isCellInterior( it->first ) )
988  I.insertCell( d, it->first, it->second );
989  }
990  }
991  return I;
992 }
993 
994 //-----------------------------------------------------------------------------
995 template <typename TKSpace, typename TCellContainer>
996 inline
997 DGtal::CubicalComplex<TKSpace, TCellContainer>
998 DGtal::CubicalComplex<TKSpace, TCellContainer>::
999 boundary( bool hintClosed ) const
1000 {
1001  CubicalComplex B( *this );
1002  if ( ! hintClosed ) B.close();
1003  for ( Dimension d = 0; d <= dimension; ++d )
1004  {
1005  CellMapIterator itNext;
1006  for ( CellMapIterator it = B.begin( d ), itE = B.end( d ); it != itE; )
1007  {
1008  itNext = it; ++itNext;
1009  if ( B.isCellInterior( it->first ) )
1010  B.eraseCell( it );
1011  it = itNext;
1012  }
1013  }
1014  return B;
1015 }
1016 
1017 //-----------------------------------------------------------------------------
1018 template <typename TKSpace, typename TCellContainer>
1019 inline
1020 void
1021 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1022 getInteriorAndBoundary( CubicalComplex& intcc, CubicalComplex& bdcc,
1023  bool hintClosed ) const
1024 {
1025  intcc = *this;
1026  bdcc = CubicalComplex( this->space() );
1027  if ( ! hintClosed ) intcc.close();
1028  for ( Dimension d = 0; d <= dimension; ++d )
1029  {
1030  CellMapIterator itNext;
1031  for ( CellMapIterator it = intcc.begin( d ), itE = intcc.end( d ); it != itE; )
1032  {
1033  itNext = it; ++itNext;
1034  if ( ! intcc.isCellInterior( it->first ) )
1035  {
1036  intcc.eraseCell( it );
1037  bdcc.insertCell( d, it->first, it->second );
1038  }
1039  it = itNext;
1040  }
1041  }
1042 }
1043 
1044 //-----------------------------------------------------------------------------
1045 template <typename TKSpace, typename TCellContainer>
1046 inline
1047 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1048 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1049 closure( const CubicalComplex& S, bool hintClosed ) const
1050 {
1051  CubicalComplex cl_S = S;
1052  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1053  {
1054  Cells cell_faces = cellBoundary( *it, hintClosed );
1055  cl_S.insert( cell_faces.begin(), cell_faces.end() );
1056  }
1057  return cl_S;
1058 }
1059 //-----------------------------------------------------------------------------
1060 template <typename TKSpace, typename TCellContainer>
1061 inline
1062 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1063 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1064 star( const CubicalComplex& S, bool hintOpen ) const
1065 {
1066  CubicalComplex star_S = S;
1067  for ( ConstIterator it = S.begin(), itE = S.end(); it != itE; ++it )
1068  {
1069  Cells cell_cofaces = cellCoBoundary( *it, hintOpen );
1070  star_S.insert( cell_cofaces.begin(), cell_cofaces.end() );
1071  }
1072  return star_S;
1073 }
1074 //-----------------------------------------------------------------------------
1075 template <typename TKSpace, typename TCellContainer>
1076 inline
1077 typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1078 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1079 link( const CubicalComplex& S, bool hintClosed, bool hintOpen ) const
1080 {
1081  CubicalComplex cl_star_S = closure( star ( S, hintOpen ), hintClosed );
1082  CubicalComplex star_cl_S = star ( closure( S, hintClosed ), hintOpen );
1083 
1084  // Calls a specializable difference of sets operation.
1085  return cl_star_S - star_cl_S;
1086 }
1087 
1088 //-----------------------------------------------------------------------------
1089 template <typename TKSpace, typename TCellContainer>
1090 inline
1091 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellType
1092 DGtal::CubicalComplex<TKSpace, TCellContainer>::
1093 computeCellType( const Cell& c, CellMapIterator& it_cell_up, Dimension n )
1094 {
1095  // Check if it is a maximal cell
1096  Dimension k = dim( c );
1097  if ( k == n ) return Maximal;
1098 
1099  std::vector< CellMapIterator > Q_up;
1100  std::back_insert_iterator< std::vector< CellMapIterator > > back_it( Q_up );
1101  this->directCoFacesIterators( back_it, c );
1102 
1103  // Filtering unwanted up-incident cells.
1104  uint32_t nb = 0;
1105  for ( typename std::vector< CellMapIterator >::const_iterator it = Q_up.begin(), itE = Q_up.end();
1106  it != itE; ++it )
1107  {
1108  uint32_t& data = (*it)->second.data;
1109  if ( ! ( data & COLLAPSIBLE ) ) return Any;
1110  if ( ! ( data & REMOVED ) )
1111  {
1112  ++nb;
1113  if ( nb > 1 ) return Any;
1114  it_cell_up = *it;
1115  }
1116  }
1117  return ( nb != 0 ) ? Free : Maximal ;
1118 }
1119 
1120 
1121 
1122 ///////////////////////////////////////////////////////////////////////////////
1123 // Interface - public :
1124 
1125 /**
1126  * Writes/Displays the object on an output stream.
1127  * @param out the output stream where the object is written.
1128  */
1129 template <typename TKSpace, typename TCellContainer>
1130 inline
1131 void
1132 DGtal::CubicalComplex<TKSpace, TCellContainer>::selfDisplay ( std::ostream & out ) const
1133 {
1134  out << "[CubicalComplex dim=" << dim() << " chi=" << euler();
1135  for ( Dimension i = 0; i < myCells.size(); ++i )
1136  out << " #" << i << "=" << myCells[ i ].size();
1137  out << "]";
1138 }
1139 
1140 /**
1141  * Checks the validity/consistency of the object.
1142  * @return 'true' if the object is valid, 'false' otherwise.
1143  */
1144 template <typename TKSpace, typename TCellContainer>
1145 inline
1146 bool
1147 DGtal::CubicalComplex<TKSpace, TCellContainer>::isValid() const
1148 {
1149  return true;
1150 }
1151 
1152 //-----------------------------------------------------------------------------
1153 template <typename TKSpace, typename TCellContainer>
1154 inline
1155 std::string
1156 DGtal::CubicalComplex<TKSpace, TCellContainer>::className() const
1157 {
1158  return "CubicalComplex";
1159 }
1160 
1161 
1162 
1163 ///////////////////////////////////////////////////////////////////////////////
1164 // Implementation of inline functions //
1165 
1166 template <typename TKSpace, typename TCellContainer>
1167 inline
1168 std::ostream&
1169 DGtal::operator<< ( std::ostream & out,
1170  const CubicalComplex<TKSpace, TCellContainer> & object )
1171 {
1172  object.selfDisplay( out );
1173  return out;
1174 }
1175 
1176 // //
1177 ///////////////////////////////////////////////////////////////////////////////
1178 
1179