DGtal 1.4.0
Loading...
Searching...
No Matches
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//-----------------------------------------------------------------------------
45template <typename TKSpace, typename TCellContainer>
46inline
47DGtal::CubicalComplex<TKSpace, TCellContainer>::
48~CubicalComplex()
49{
50}
51
52//-----------------------------------------------------------------------------
53template <typename TKSpace, typename TCellContainer>
54inline
55DGtal::CubicalComplex<TKSpace, TCellContainer>::
56CubicalComplex()
57 : myKSpace( 0 ), myCells( dimension+1 )
58{
59}
60
61//-----------------------------------------------------------------------------
62template <typename TKSpace, typename TCellContainer>
63inline
64DGtal::CubicalComplex<TKSpace, TCellContainer>::
65CubicalComplex( ConstAlias<KSpace> aK )
66 : myKSpace( &aK ), myCells( dimension+1 )
67{
68}
69
70//-----------------------------------------------------------------------------
71template <typename TKSpace, typename TCellContainer>
72inline
73DGtal::CubicalComplex<TKSpace, TCellContainer>::
74CubicalComplex( const CubicalComplex& other )
75 : myKSpace( other.myKSpace ), myCells( other.myCells )
76{
77}
78
79//-----------------------------------------------------------------------------
80template <typename TKSpace, typename TCellContainer>
81template <typename TDigitalSet>
82inline
83void DGtal::CubicalComplex<TKSpace, TCellContainer>::
84construct( 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//-----------------------------------------------------------------------------
99template <typename TKSpace, typename TCellContainer>
100inline
101const typename DGtal::CubicalComplex<TKSpace, TCellContainer>::KSpace &
102DGtal::CubicalComplex<TKSpace, TCellContainer>::
103space() const
104{
105 return *myKSpace;
106}
107
108//-----------------------------------------------------------------------------
109template <typename TKSpace, typename TCellContainer>
110inline
111typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
112DGtal::CubicalComplex<TKSpace, TCellContainer>::
113begin() const
114{
115 return ConstIterator( *this, 0 );
116}
117
118//-----------------------------------------------------------------------------
119template <typename TKSpace, typename TCellContainer>
120inline
121typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
122DGtal::CubicalComplex<TKSpace, TCellContainer>::
123end() const
124{
125 return ConstIterator( *this, dimension+1 );
126}
127
128//-----------------------------------------------------------------------------
129template <typename TKSpace, typename TCellContainer>
130inline
131typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
132DGtal::CubicalComplex<TKSpace, TCellContainer>::
133begin()
134{
135 return Iterator( *this, 0 );
136}
137
138//-----------------------------------------------------------------------------
139template <typename TKSpace, typename TCellContainer>
140inline
141typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
142DGtal::CubicalComplex<TKSpace, TCellContainer>::
143end()
144{
145 return Iterator( *this, dimension+1 );
146}
147
148//-----------------------------------------------------------------------------
149template <typename TKSpace, typename TCellContainer>
150inline
151DGtal::CubicalComplex<TKSpace, TCellContainer>&
152DGtal::CubicalComplex<TKSpace, TCellContainer>::
153operator=( const CubicalComplex& other )
154{
155 if ( this != &other )
156 {
157 myKSpace = other.myKSpace;
158 myCells = other.myCells;
159 }
160 return *this;
161}
162
163//-----------------------------------------------------------------------------
164template <typename TKSpace, typename TCellContainer>
165inline
166void
167DGtal::CubicalComplex<TKSpace, TCellContainer>::
168clear()
169{
170 for ( Dimension d = 0; d <= dimension; ++d )
171 clear( d );
172}
173
174//-----------------------------------------------------------------------------
175template <typename TKSpace, typename TCellContainer>
176inline
177typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
178DGtal::CubicalComplex<TKSpace, TCellContainer>::
179count( const Cell& aCell ) const
180{
181 return belongs( aCell ) ? 1 : 0;
182}
183
184//-----------------------------------------------------------------------------
185template <typename TKSpace, typename TCellContainer>
186inline
187void
188DGtal::CubicalComplex<TKSpace, TCellContainer>::
189clear( Dimension d )
190{
191 myCells[ d ].clear();
192}
193//-----------------------------------------------------------------------------
194template <typename TKSpace, typename TCellContainer>
195inline
196void
197DGtal::CubicalComplex<TKSpace, TCellContainer>::
198fillData( Data data )
199{
200 for ( Dimension d = 0; d <= dimension; ++d )
201 fillData( d, data );
202}
203//-----------------------------------------------------------------------------
204template <typename TKSpace, typename TCellContainer>
205inline
206void
207DGtal::CubicalComplex<TKSpace, TCellContainer>::
208fillData( 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//-----------------------------------------------------------------------------
218template <typename TKSpace, typename TCellContainer>
219inline
220DGtal::Dimension
221DGtal::CubicalComplex<TKSpace, TCellContainer>::
222dim() 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//-----------------------------------------------------------------------------
231template <typename TKSpace, typename TCellContainer>
232inline
233DGtal::Dimension
234DGtal::CubicalComplex<TKSpace, TCellContainer>::
235dim( const Cell& c ) const
236{
237 return myKSpace->uDim( c );
238}
239
240//-----------------------------------------------------------------------------
241template <typename TKSpace, typename TCellContainer>
242inline
243typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
244DGtal::CubicalComplex<TKSpace, TCellContainer>::
245nbCells( Dimension d ) const
246{
247 return static_cast<Size>(myCells[ d ].size());
248}
249
250//-----------------------------------------------------------------------------
251template <typename TKSpace, typename TCellContainer>
252inline
253typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
254DGtal::CubicalComplex<TKSpace, TCellContainer>::
255size() const
256{
257 Size n = 0;
258 for ( Dimension d = 0; d <= dimension; ++d )
259 n += myCells[ d ].size();
260 return n;
261}
262//-----------------------------------------------------------------------------
263template <typename TKSpace, typename TCellContainer>
264inline
265typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
266DGtal::CubicalComplex<TKSpace, TCellContainer>::
267max_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//-----------------------------------------------------------------------------
277template <typename TKSpace, typename TCellContainer>
278inline
279bool
280DGtal::CubicalComplex<TKSpace, TCellContainer>::
281empty() const
282{
283 for ( Dimension d = 0; d <= dimension; ++d )
284 if ( ! myCells[ d ].empty() ) return false;
285 return true;
286}
287
288//-----------------------------------------------------------------------------
289template <typename TKSpace, typename TCellContainer>
290inline
291typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Integer
292DGtal::CubicalComplex<TKSpace, TCellContainer>::
293euler() 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//-----------------------------------------------------------------------------
307template <typename TKSpace, typename TCellContainer>
308inline
309std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator,
310 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator >
311DGtal::CubicalComplex<TKSpace, TCellContainer>::
312equal_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//-----------------------------------------------------------------------------
322template <typename TKSpace, typename TCellContainer>
323inline
324std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator,
325 typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator >
326DGtal::CubicalComplex<TKSpace, TCellContainer>::
327equal_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//-----------------------------------------------------------------------------
337template <typename TKSpace, typename TCellContainer>
338inline
339void
340DGtal::CubicalComplex<TKSpace, TCellContainer>::
341erase( Iterator it )
342{
343 eraseCell( it.myIt );
344}
345
346//-----------------------------------------------------------------------------
347template <typename TKSpace, typename TCellContainer>
348inline
349typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
350DGtal::CubicalComplex<TKSpace, TCellContainer>::
351erase( const Cell& aCell )
352{
353 return eraseCell( aCell );
354}
355
356//-----------------------------------------------------------------------------
357template <typename TKSpace, typename TCellContainer>
358inline
359void
360DGtal::CubicalComplex<TKSpace, TCellContainer>::
361erase( Iterator first, Iterator last )
362{
363 while ( first != last )
364 {
365 Iterator tmp = first++;
366 erase( tmp );
367 }
368}
369
370//-----------------------------------------------------------------------------
371template <typename TKSpace, typename TCellContainer>
372inline
373typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
374DGtal::CubicalComplex<TKSpace, TCellContainer>::
375find( 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//-----------------------------------------------------------------------------
384template <typename TKSpace, typename TCellContainer>
385inline
386typename DGtal::CubicalComplex<TKSpace, TCellContainer>::ConstIterator
387DGtal::CubicalComplex<TKSpace, TCellContainer>::
388find( 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//-----------------------------------------------------------------------------
397template <typename TKSpace, typename TCellContainer>
398inline
399std::pair< typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator,
400 bool >
401DGtal::CubicalComplex<TKSpace, TCellContainer>::
402insert( 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//-----------------------------------------------------------------------------
413template <typename TKSpace, typename TCellContainer>
414inline
415typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Iterator
416DGtal::CubicalComplex<TKSpace, TCellContainer>::
417insert( 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//-----------------------------------------------------------------------------
429template <typename TKSpace, typename TCellContainer>
430template <class InputIterator>
431inline
432void
433DGtal::CubicalComplex<TKSpace, TCellContainer>::
434insert( InputIterator first, InputIterator last )
435{
436 for ( ; first != last; ++first )
437 insert( *first );
438}
439
440//-----------------------------------------------------------------------------
441template <typename TKSpace, typename TCellContainer>
442inline
443void
444DGtal::CubicalComplex<TKSpace, TCellContainer>::
445swap( 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//-----------------------------------------------------------------------------
458template <typename TKSpace, typename TCellContainer>
459inline
460typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Data&
461DGtal::CubicalComplex<TKSpace, TCellContainer>::
462operator[]( const Cell& aCell )
463{
464 Dimension d = space().uDim( aCell );
465 return myCells[ d ][ aCell ];
466}
467
468//-----------------------------------------------------------------------------
469template <typename TKSpace, typename TCellContainer>
470inline
471bool
472DGtal::CubicalComplex<TKSpace, TCellContainer>::
473operator()( const Cell& aCell ) const
474{
475 Dimension d = space().uDim( aCell );
476 return findCell( d, aCell ) != end( d );
477}
478
479//-----------------------------------------------------------------------------
480template <typename TKSpace, typename TCellContainer>
481inline
482void
483DGtal::CubicalComplex<TKSpace, TCellContainer>::
484insertCell( const Cell& aCell, const Data& data )
485{
486 insertCell( myKSpace->uDim( aCell ), aCell, data );
487}
488//-----------------------------------------------------------------------------
489template <typename TKSpace, typename TCellContainer>
490inline
491void
492DGtal::CubicalComplex<TKSpace, TCellContainer>::
493insertCell( Dimension d, const Cell& aCell, const Data& data )
494{
495 myCells[ d ][ aCell ] = data;
496}
497
498//-----------------------------------------------------------------------------
499template <typename TKSpace, typename TCellContainer>
500template <typename CellConstIterator>
501inline
502void
503DGtal::CubicalComplex<TKSpace, TCellContainer>::
504insertCells( CellConstIterator it, CellConstIterator itE, const Data& data )
505{
506 for ( ; it != itE; ++it )
507 insertCell( *it, data );
508}
509
510//-----------------------------------------------------------------------------
511template <typename TKSpace, typename TCellContainer>
512template <typename CellConstIterator>
513inline
514void
515DGtal::CubicalComplex<TKSpace, TCellContainer>::
516insertCells( Dimension d, CellConstIterator it, CellConstIterator itE, const Data& data )
517{
518 for ( ; it != itE; ++it )
519 insertCell( d, *it, data );
520}
521
522//-----------------------------------------------------------------------------
523template <typename TKSpace, typename TCellContainer>
524inline
525typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
526DGtal::CubicalComplex<TKSpace, TCellContainer>::
527eraseCell( const Cell& aCell )
528{
529 return eraseCell( myKSpace->uDim( aCell ), aCell );
530}
531
532//-----------------------------------------------------------------------------
533template <typename TKSpace, typename TCellContainer>
534inline
535typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
536DGtal::CubicalComplex<TKSpace, TCellContainer>::
537eraseCell( Dimension d, const Cell& aCell )
538{
539 return (Size) myCells[ d ].erase( aCell );
540}
541
542//-----------------------------------------------------------------------------
543template <typename TKSpace, typename TCellContainer>
544inline
545void
546DGtal::CubicalComplex<TKSpace, TCellContainer>::
547eraseCell( CellMapIterator it )
548{
549 Dimension d = myKSpace->uDim( it->first );
550 myCells[ d ].erase( it );
551}
552
553//-----------------------------------------------------------------------------
554template <typename TKSpace, typename TCellContainer>
555inline
556void
557DGtal::CubicalComplex<TKSpace, TCellContainer>::
558eraseCells( CellMapIterator it, CellMapIterator itE )
559{
560 for ( ; it != itE; ++it )
561 eraseCell( it );
562}
563
564//-----------------------------------------------------------------------------
565template <typename TKSpace, typename TCellContainer>
566template <typename CellConstIterator>
567inline
568typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
569DGtal::CubicalComplex<TKSpace, TCellContainer>::
570eraseCells( CellConstIterator it, CellConstIterator itE )
571{
572 Size nb = 0;
573 for ( ; it != itE; ++it )
574 nb += eraseCell( *it );
575}
576
577//-----------------------------------------------------------------------------
578template <typename TKSpace, typename TCellContainer>
579template <typename CellConstIterator>
580inline
581typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Size
582DGtal::CubicalComplex<TKSpace, TCellContainer>::
583eraseCells( Dimension d, CellConstIterator it, CellConstIterator itE )
584{
585 Size nb = 0;
586 for ( ; it != itE; ++it )
587 nb += eraseCell( d, *it );
588}
589
590//-----------------------------------------------------------------------------
591template <typename TKSpace, typename TCellContainer>
592inline
593bool
594DGtal::CubicalComplex<TKSpace, TCellContainer>::
595belongs( const Cell& aCell ) const
596{
597 return belongs( myKSpace->uDim( aCell ), aCell );
598}
599//-----------------------------------------------------------------------------
600template <typename TKSpace, typename TCellContainer>
601inline
602bool
603DGtal::CubicalComplex<TKSpace, TCellContainer>::
604belongs( 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//-----------------------------------------------------------------------------
611template <typename TKSpace, typename TCellContainer>
612inline
613bool
614DGtal::CubicalComplex<TKSpace, TCellContainer>::
615belongs( const PreCell& aCell ) const
616{
617 return belongs( TKSpace::PreCellularGridSpace::uDim( aCell ), aCell );
618}
619//-----------------------------------------------------------------------------
620template <typename TKSpace, typename TCellContainer>
621inline
622bool
623DGtal::CubicalComplex<TKSpace, TCellContainer>::
624belongs( Dimension d, const PreCell& aCell ) const
625{
626 if (!myKSpace->uIsValid(aCell)) return false;
627 return belongs(d, myKSpace->uCell(aCell) );
628}
629//-----------------------------------------------------------------------------
630template <typename TKSpace, typename TCellContainer>
631template <typename CellOutputIterator>
632inline
633void
634DGtal::CubicalComplex<TKSpace, TCellContainer>::
635faces( 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//-----------------------------------------------------------------------------
647template <typename TKSpace, typename TCellContainer>
648template <typename CellOutputIterator>
649inline
650void
651DGtal::CubicalComplex<TKSpace, TCellContainer>::
652coFaces( 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//-----------------------------------------------------------------------------
664template <typename TKSpace, typename TCellContainer>
665template <typename CellOutputIterator>
666inline
667void
668DGtal::CubicalComplex<TKSpace, TCellContainer>::
669directFaces( 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//-----------------------------------------------------------------------------
681template <typename TKSpace, typename TCellContainer>
682template <typename CellMapIteratorOutputIterator>
683inline
684void
685DGtal::CubicalComplex<TKSpace, TCellContainer>::
686directFacesIterators( 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//-----------------------------------------------------------------------------
699template <typename TKSpace, typename TCellContainer>
700template <typename CellOutputIterator>
701inline
702void
703DGtal::CubicalComplex<TKSpace, TCellContainer>::
704directCoFaces( 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//-----------------------------------------------------------------------------
716template <typename TKSpace, typename TCellContainer>
717template <typename CellMapIteratorOutputIterator>
718inline
719void
720DGtal::CubicalComplex<TKSpace, TCellContainer>::
721directCoFacesIterators( 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//-----------------------------------------------------------------------------
735template <typename TKSpace, typename TCellContainer>
736typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
737DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d)
738{
739 return myCells[d];
740}
741
742template <typename TKSpace, typename TCellContainer>
743const typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMap &
744DGtal::CubicalComplex<TKSpace, TCellContainer>::getCells(const Dimension d) const
745{
746 return myCells[d];
747}
748//-----------------------------------------------------------------------------
749template <typename TKSpace, typename TCellContainer>
750inline
751typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
752DGtal::CubicalComplex<TKSpace, TCellContainer>::
753begin( Dimension d ) const
754{
755 return myCells[ d ].begin();
756}
757
758//-----------------------------------------------------------------------------
759template <typename TKSpace, typename TCellContainer>
760inline
761typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
762DGtal::CubicalComplex<TKSpace, TCellContainer>::
763end( Dimension d ) const
764{
765 return myCells[ d ].end();
766}
767
768//-----------------------------------------------------------------------------
769template <typename TKSpace, typename TCellContainer>
770inline
771typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
772DGtal::CubicalComplex<TKSpace, TCellContainer>::
773begin( Dimension d )
774{
775 return myCells[ d ].begin();
776}
777
778//-----------------------------------------------------------------------------
779template <typename TKSpace, typename TCellContainer>
780inline
781typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
782DGtal::CubicalComplex<TKSpace, TCellContainer>::
783end( Dimension d )
784{
785 return myCells[ d ].end();
786}
787
788//-----------------------------------------------------------------------------
789template <typename TKSpace, typename TCellContainer>
790inline
791void
792DGtal::CubicalComplex<TKSpace, TCellContainer>::
793close()
794{
795 close( dim() );
796}
797
798//-----------------------------------------------------------------------------
799template <typename TKSpace, typename TCellContainer>
800inline
801void
802DGtal::CubicalComplex<TKSpace, TCellContainer>::
803close( 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//-----------------------------------------------------------------------------
819template <typename TKSpace, typename TCellContainer>
820inline
821void
822DGtal::CubicalComplex<TKSpace, TCellContainer>::
823open()
824{
825 open( dim() );
826}
827
828//-----------------------------------------------------------------------------
829template <typename TKSpace, typename TCellContainer>
830inline
831void
832DGtal::CubicalComplex<TKSpace, TCellContainer>::
833open( 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//-----------------------------------------------------------------------------
858template <typename TKSpace, typename TCellContainer>
859inline
860typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
861DGtal::CubicalComplex<TKSpace, TCellContainer>::
862findCell( const Cell& aCell ) const
863{
864 return findCell( dim( aCell ), aCell );
865}
866
867//-----------------------------------------------------------------------------
868template <typename TKSpace, typename TCellContainer>
869inline
870typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapConstIterator
871DGtal::CubicalComplex<TKSpace, TCellContainer>::
872findCell( Dimension d, const Cell& aCell ) const
873{
874 return myCells[ d ].find( aCell );
875}
876
877//-----------------------------------------------------------------------------
878template <typename TKSpace, typename TCellContainer>
879inline
880typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
881DGtal::CubicalComplex<TKSpace, TCellContainer>::
882findCell( const Cell& aCell )
883{
884 return findCell( dim( aCell ), aCell );
885}
886
887//-----------------------------------------------------------------------------
888template <typename TKSpace, typename TCellContainer>
889inline
890typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellMapIterator
891DGtal::CubicalComplex<TKSpace, TCellContainer>::
892findCell( Dimension d, const Cell& aCell )
893{
894 return myCells[ d ].find( aCell );
895}
896
897
898
899//-----------------------------------------------------------------------------
900template <typename TKSpace, typename TCellContainer>
901inline
902typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
903DGtal::CubicalComplex<TKSpace, TCellContainer>::
904cellBoundary( 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//-----------------------------------------------------------------------------
924template <typename TKSpace, typename TCellContainer>
925inline
926typename DGtal::CubicalComplex<TKSpace, TCellContainer>::Cells
927DGtal::CubicalComplex<TKSpace, TCellContainer>::
928cellCoBoundary( 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//-----------------------------------------------------------------------------
949template <typename TKSpace, typename TCellContainer>
950inline
951bool
952DGtal::CubicalComplex<TKSpace, TCellContainer>::
953isCellInterior( 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//-----------------------------------------------------------------------------
966template <typename TKSpace, typename TCellContainer>
967inline
968bool
969DGtal::CubicalComplex<TKSpace, TCellContainer>::
970isCellBoundary( const Cell& aCell ) const
971{
972 return ! isCellInterior( aCell );
973}
974
975//-----------------------------------------------------------------------------
976template <typename TKSpace, typename TCellContainer>
977inline
978DGtal::CubicalComplex<TKSpace, TCellContainer>
979DGtal::CubicalComplex<TKSpace, TCellContainer>::
980interior() 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//-----------------------------------------------------------------------------
995template <typename TKSpace, typename TCellContainer>
996inline
997DGtal::CubicalComplex<TKSpace, TCellContainer>
998DGtal::CubicalComplex<TKSpace, TCellContainer>::
999boundary( 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//-----------------------------------------------------------------------------
1018template <typename TKSpace, typename TCellContainer>
1019inline
1020void
1021DGtal::CubicalComplex<TKSpace, TCellContainer>::
1022getInteriorAndBoundary( 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//-----------------------------------------------------------------------------
1045template <typename TKSpace, typename TCellContainer>
1046inline
1047typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1048DGtal::CubicalComplex<TKSpace, TCellContainer>::
1049closure( 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//-----------------------------------------------------------------------------
1060template <typename TKSpace, typename TCellContainer>
1061inline
1062typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1063DGtal::CubicalComplex<TKSpace, TCellContainer>::
1064star( 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//-----------------------------------------------------------------------------
1075template <typename TKSpace, typename TCellContainer>
1076inline
1077typename DGtal::CubicalComplex<TKSpace, TCellContainer>
1078DGtal::CubicalComplex<TKSpace, TCellContainer>::
1079link( 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//-----------------------------------------------------------------------------
1089template <typename TKSpace, typename TCellContainer>
1090inline
1091typename DGtal::CubicalComplex<TKSpace, TCellContainer>::CellType
1092DGtal::CubicalComplex<TKSpace, TCellContainer>::
1093computeCellType( 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 */
1129template <typename TKSpace, typename TCellContainer>
1130inline
1131void
1132DGtal::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 */
1144template <typename TKSpace, typename TCellContainer>
1145inline
1146bool
1147DGtal::CubicalComplex<TKSpace, TCellContainer>::isValid() const
1148{
1149 return true;
1150}
1151
1152//-----------------------------------------------------------------------------
1153template <typename TKSpace, typename TCellContainer>
1154inline
1155std::string
1156DGtal::CubicalComplex<TKSpace, TCellContainer>::className() const
1157{
1158 return "CubicalComplex";
1159}
1160
1161
1162
1163///////////////////////////////////////////////////////////////////////////////
1164// Implementation of inline functions //
1165
1166template <typename TKSpace, typename TCellContainer>
1167inline
1168std::ostream&
1169DGtal::operator<< ( std::ostream & out,
1170 const CubicalComplex<TKSpace, TCellContainer> & object )
1171{
1172 object.selfDisplay( out );
1173 return out;
1174}
1175
1176// //
1177///////////////////////////////////////////////////////////////////////////////
1178
1179