DGtal 1.3.0
Loading...
Searching...
No Matches
LabelledMap.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 LabelledMap.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 2012/07/05
23 *
24 * Implementation of inline methods defined in LabelledMap.h
25 *
26 * This file is part of the DGtal library.
27 */
28
29
30//////////////////////////////////////////////////////////////////////////////
31#include <cstdlib>
32//////////////////////////////////////////////////////////////////////////////
33
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
37
38///////////////////////////////////////////////////////////////////////////////
39// ----------------------- Standard services ------------------------------
40
41///////////////////////////////////////////////////////////////////////////////
42// class LabelledMap::BlockIterator
43//-----------------------------------------------------------------------------
44template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
45DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
46~BlockIterator()
47{}
48//-----------------------------------------------------------------------------
49template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
50DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
51BlockIterator()
52 : myIdx( 0 ), myDatas( 0 )
53{}
54//-----------------------------------------------------------------------------
55template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
56DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
57BlockIterator( const Self & other)
58 : myIdx( other.myIdx ), myNbDatas( other.myNbDatas ),
59 myDatas( other.myDatas ), myNext( other.myNext )
60{}
61//-----------------------------------------------------------------------------
62template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
63DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
64BlockIterator( __FirstBlock & block, unsigned int idx, unsigned int size )
65{
66 ASSERT( idx <= size );
67 if ( size <= N+1 )
68 {
69 if ( idx <= N )
70 {
71 myIdx = idx;
72 myNbDatas = N + 1;
73 myDatas = block.datas;
74 myNext = 0;
75 }
76 else
77 { // end iterator.
78 myIdx = 0;
79 myNbDatas = 0;
80 myDatas = 0;
81 myNext = 0;
82 }
83 }
84 else
85 {
86 ASSERT( block.data.nextBlock != 0 );
87 myNext = block.data.nextBlock;
88 if ( idx < N )
89 {
90 myIdx = idx;
91 myNbDatas = N;
92 myDatas = block.datas;
93 }
94 else
95 {
96 idx -= N;
97 while ( idx >= M )
98 {
99 idx -= M;
100 myNext = ( myNext != 0 ) ? myNext->next : 0;
101 }
102 if ( myNext == 0 )
103 {
104 myIdx = 0;
105 myNbDatas = 0;
106 myDatas = 0;
107 }
108 else
109 {
110 myIdx = idx;
111 myNbDatas = M;
112 myDatas = myNext->datas;
113 }
114 }
115 }
116}
117//-----------------------------------------------------------------------------
118template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
119inline
120typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
121DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
122operator=( const Self & other )
123{
124 if ( this != &other )
125 {
126 myIdx = other.myIdx;
127 myNbDatas = other.myNbDatas;
128 myDatas = other.myDatas;
129 myNext = other.myNext;
130 }
131 return *this;
132}
133//-----------------------------------------------------------------------------
134template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
135inline
136typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Reference
137DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
138operator*() const
139{
140 ASSERT( myDatas != 0 );
141 return myDatas[ myIdx ];
142}
143//-----------------------------------------------------------------------------
144template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
145inline
146typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Pointer
147DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
148operator->() const
149{
150 ASSERT( myDatas != 0 );
151 return myDatas + myIdx;
152}
153//-----------------------------------------------------------------------------
154template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
155inline
156typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
157DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
158operator++()
159{
160 return this->operator+=( 1 );
161}
162//-----------------------------------------------------------------------------
163template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
164inline
165typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self
166DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
167operator++( int )
168{
169 Self tmp( *this );
170 this->operator++();
171 return tmp;
172}
173//-----------------------------------------------------------------------------
174template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
175inline
176bool
177DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
178operator==( const Self & other ) const
179{
180 return ( myDatas == other.myDatas ) && ( myIdx == other.myIdx );
181}
182//-----------------------------------------------------------------------------
183template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
184inline
185bool
186DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
187operator!=( const Self & other ) const
188{
189 return ( myDatas != other.myDatas ) || ( myIdx != other.myIdx );
190}
191//-----------------------------------------------------------------------------
192template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
193inline
194typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
195DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
196operator+=( DifferenceType n )
197{
198 myIdx += n;
199 while ( myIdx >= myNbDatas )
200 {
201 if ( myNext == 0 )
202 {
203 myDatas = 0;
204 myIdx = 0;
205 break;
206 }
207 myIdx -= myNbDatas;
208 myDatas = myNext->datas;
209 myNbDatas = M;
210 myNext = myNext->next;
211 }
212 return *this;
213}
214//-----------------------------------------------------------------------------
215template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
216inline
217typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Reference
218DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
219operator[]( DifferenceType n ) const
220{
221 Self tmp( *this );
222 tmp += n;
223 return *tmp;
224}
225
226///////////////////////////////////////////////////////////////////////////////
227// class LabelledMap::BlockConstIterator
228//-----------------------------------------------------------------------------
229template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
230DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
231~BlockConstIterator()
232{}
233//-----------------------------------------------------------------------------
234template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
235DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
236BlockConstIterator()
237 : myIdx( 0 ), myDatas( 0 )
238{}
239//-----------------------------------------------------------------------------
240template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
241DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
242BlockConstIterator( const Self & other)
243 : myIdx( other.myIdx ), myNbDatas( other.myNbDatas ),
244 myDatas( other.myDatas ), myNext( other.myNext )
245{}
246//-----------------------------------------------------------------------------
247template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
248DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
249BlockConstIterator( const __FirstBlock & block, unsigned int idx, unsigned int size )
250{
251 ASSERT( idx <= size );
252 if ( size <= N+1 )
253 {
254 if ( idx <= N )
255 {
256 myIdx = idx;
257 myNbDatas = N + 1;
258 myDatas = block.datas;
259 myNext = 0;
260 }
261 else
262 { // end iterator.
263 myIdx = 0;
264 myNbDatas = 0;
265 myDatas = 0;
266 myNext = 0;
267 }
268 }
269 else
270 {
271 ASSERT( block.data.nextBlock != 0 );
272 myNext = block.data.nextBlock;
273 if ( idx < N )
274 {
275 myIdx = idx;
276 myNbDatas = N;
277 myDatas = block.datas;
278 }
279 else
280 {
281 idx -= N;
282 while ( idx >= M )
283 {
284 idx -= M;
285 myNext = ( myNext != 0 ) ? myNext->next : 0;
286 }
287 if ( myNext == 0 )
288 {
289 myIdx = 0;
290 myNbDatas = 0;
291 myDatas = 0;
292 }
293 else
294 {
295 myIdx = idx;
296 myNbDatas = M;
297 myDatas = myNext->datas;
298 }
299 }
300 }
301}
302//-----------------------------------------------------------------------------
303template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
304inline
305typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
306DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
307operator=( const Self & other )
308{
309 if ( this != &other )
310 {
311 myIdx = other.myIdx;
312 myNbDatas = other.myNbDatas;
313 myDatas = other.myDatas;
314 myNext = other.myNext;
315 }
316 return *this;
317}
318//-----------------------------------------------------------------------------
319template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
320inline
321typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Reference
322DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
323operator*() const
324{
325 ASSERT( myDatas != 0 );
326 return myDatas[ myIdx ];
327}
328//-----------------------------------------------------------------------------
329template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
330inline
331typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Pointer
332DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
333operator->() const
334{
335 ASSERT( myDatas != 0 );
336 return myDatas + myIdx;
337}
338//-----------------------------------------------------------------------------
339template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
340inline
341typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
342DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
343operator++()
344{
345 return this->operator+=( 1 );
346}
347//-----------------------------------------------------------------------------
348template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
349inline
350typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self
351DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
352operator++( int )
353{
354 Self tmp( *this );
355 this->operator++();
356 return tmp;
357}
358//-----------------------------------------------------------------------------
359template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
360inline
361bool
362DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
363operator==( const Self & other ) const
364{
365 return ( myDatas == other.myDatas ) && ( myIdx == other.myIdx );
366}
367//-----------------------------------------------------------------------------
368template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
369inline
370bool
371DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
372operator!=( const Self & other ) const
373{
374 return ( myDatas != other.myDatas ) || ( myIdx != other.myIdx );
375}
376//-----------------------------------------------------------------------------
377template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
378inline
379typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
380DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
381operator+=( DifferenceType n )
382{
383 myIdx += n;
384 while ( myIdx >= myNbDatas )
385 {
386 if ( myNext == 0 )
387 {
388 myDatas = 0;
389 myIdx = 0;
390 break;
391 }
392 myIdx -= myNbDatas;
393 myDatas = myNext->datas;
394 myNbDatas = M;
395 myNext = myNext->next;
396 }
397 return *this;
398}
399//-----------------------------------------------------------------------------
400template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
401inline
402typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Reference
403DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
404operator[]( DifferenceType n ) const
405{
406 Self tmp( *this );
407 tmp += n;
408 return *tmp;
409}
410
411///////////////////////////////////////////////////////////////////////////////
412// class LabelledMap::ConstIterator
413//-----------------------------------------------------------------------------
414template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
415inline
416DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
417ConstIterator( LabelsConstIterator lIt, BlockConstIterator bIt )
418 : myLabelsIt( lIt ), myBlockIt( bIt )
419{}
420//-----------------------------------------------------------------------------
421template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
422inline
423DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
424~ConstIterator()
425{}
426//-----------------------------------------------------------------------------
427template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
428inline
429DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
430ConstIterator()
431{}
432//-----------------------------------------------------------------------------
433template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
434inline
435DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
436ConstIterator( const ConstIterator & other )
437 : myLabelsIt( other.myLabelsIt ), myBlockIt( other.myBlockIt )
438{}
439//-----------------------------------------------------------------------------
440template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
441inline
442typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self &
443DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
444operator= ( const Self & other )
445{
446 if ( this != &other )
447 {
448 myLabelsIt = other.myLabelsIt;
449 myBlockIt = other.myBlockIt;
450 }
451 return *this;
452}
453//-----------------------------------------------------------------------------
454template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
455inline
456typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Reference
457DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
458operator*() const
459{
460 return std::make_pair( *myLabelsIt, *myBlockIt );
461}
462//-----------------------------------------------------------------------------
463template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
464inline
465typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Pointer
466DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
467operator->() const
468{
469 // Warning: not thread-safe.
470 static Value __static_tmp;
471 __static_tmp = this->operator*();
472 return &__static_tmp;
473}
474//-----------------------------------------------------------------------------
475template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
476inline
477typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self&
478DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
479operator++()
480{
481 ++myLabelsIt;
482 ++myBlockIt;
483 return *this;
484}
485//-----------------------------------------------------------------------------
486template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
487inline
488typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self
489DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
490operator++( int )
491{
492 Self tmp( *this );
493 this->operator++();
494 return tmp;
495}
496//-----------------------------------------------------------------------------
497template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
498inline
499bool
500DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
501operator==( const Self & other ) const
502{
503 return myLabelsIt == other.myLabelsIt;
504}
505//-----------------------------------------------------------------------------
506template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
507inline
508bool
509DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
510operator!=( const Self & other ) const
511{
512 return myLabelsIt != other.myLabelsIt;
513}
514//-----------------------------------------------------------------------------
515template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
516inline
517typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data&
518DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
519_data() const
520{
521 return const_cast<Data&>( *myBlockIt );
522}
523//-----------------------------------------------------------------------------
524template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
525inline
526const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data&
527DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
528_const_data() const
529{
530 return *myBlockIt;
531}
532
533///////////////////////////////////////////////////////////////////////////////
534// class LabelledMap
535//-----------------------------------------------------------------------------
536template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
537inline
538DGtal::LabelledMap<TData, L, TWord, N, M>::
539LabelledMap()
540{ // default constructor of myLabels and myFirstBlock is automatically called.
541}
542//-----------------------------------------------------------------------------
543template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
544inline
545DGtal::LabelledMap<TData, L, TWord, N, M>::
546~LabelledMap()
547{
548 blockClear( size() );
549}
550//-----------------------------------------------------------------------------
551template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
552inline
553DGtal::LabelledMap<TData, L, TWord, N, M>::
554LabelledMap( const LabelledMap & other )
555 : myLabels( other.myLabels ),
556 myFirstBlock( other.myFirstBlock )
557{
558 const auto theSize = other.size();
559 if ( theSize > N + 1 )
560 {
561 unsigned int s = N;
562 const __AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
563 __AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
564 while ( s < theSize )
565 {
566 *currentPointer = new __AnyBlock( *nextBlock );
567 s += M;
568 currentPointer = & ( (*currentPointer)->next );
569 nextBlock = nextBlock->next;
570 }
571 }
572}
573//-----------------------------------------------------------------------------
574template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
575template <typename InputIterator>
576inline
577DGtal::LabelledMap<TData, L, TWord, N, M>::
578LabelledMap( InputIterator first, InputIterator last )
579{ // default constructor of myLabels and myFirstBlock is automatically called.
580 BOOST_CONCEPT_ASSERT(( boost::InputIterator< InputIterator > ));
581 for ( ; first != last; ++first )
582 {
583 this->operator[]( first->first ) = first->second;
584 }
585}
586//-----------------------------------------------------------------------------
587template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
588inline
589DGtal::LabelledMap<TData, L, TWord, N, M> &
590DGtal::LabelledMap<TData, L, TWord, N, M>::
591operator=( const LabelledMap & other )
592{
593 if ( this != &other )
594 {
595 blockClear( size() );
596 myLabels = other.myLabels;
597 myFirstBlock = other.myFirstBlock;
598
599 auto theSize = other.size();
600 if ( theSize > N + 1 )
601 {
602 unsigned int s = N;
603 const __AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
604 __AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
605 while ( s < theSize )
606 {
607 *currentPointer = new __AnyBlock( *nextBlock );
608 s += M;
609 currentPointer = & ( (*currentPointer)->next );
610 nextBlock = nextBlock->next;
611 }
612 }
613 }
614 return *this;
615}
616//-----------------------------------------------------------------------------
617template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
618inline
619void
620DGtal::LabelledMap<TData, L, TWord, N, M>::
621clear()
622{
623 blockClear( size() );
624 myLabels.reset();
625}
626//-----------------------------------------------------------------------------
627template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
628inline
629void
630DGtal::LabelledMap<TData, L, TWord, N, M>::
631blockClear( size_t theSize )
632{
633 if ( theSize != N+1 )
634 {
635 __AnyBlock* nextBlock = myFirstBlock.data.nextBlock;
636 while ( nextBlock != 0 )
637 {
638 __AnyBlock* ptr = nextBlock;
639 nextBlock = nextBlock->next;
640 delete ptr;
641 }
642 }
643 myFirstBlock.data.nextBlock = 0;
644}
645//-----------------------------------------------------------------------------
646template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
647inline
648const typename DGtal::LabelledMap<TData, L, TWord, N, M>::LabelsType &
649DGtal::LabelledMap<TData, L, TWord, N, M>::
650labels() const
651{
652 return myLabels;
653}
654//-----------------------------------------------------------------------------
655template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
656inline
657typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
658DGtal::LabelledMap<TData, L, TWord, N, M>::
659size() const
660{
661 return myLabels.count();
662}
663//-----------------------------------------------------------------------------
664template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
665inline
666bool
667DGtal::LabelledMap<TData, L, TWord, N, M>::
668empty() const
669{
670 return size() == 0;
671}
672//-----------------------------------------------------------------------------
673template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
674inline
675typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
676DGtal::LabelledMap<TData, L, TWord, N, M>::
677max_size() const
678{
679 return L; //SizeType( -1 ) / (2*sizeof( Data ));
680}
681//-----------------------------------------------------------------------------
682template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
683inline
684typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
685DGtal::LabelledMap<TData, L, TWord, N, M>::
686capacity() const
687{
688 return ( size() <= (N+1) )
689 ? N+1
690 : ( 1 + ( size() - 1 - N ) / M ) * M + N;
691}
692//-----------------------------------------------------------------------------
693template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
694inline
695typename DGtal::LabelledMap<TData, L, TWord, N, M>::KeyCompare
696DGtal::LabelledMap<TData, L, TWord, N, M>::
697key_comp() const
698{
699 return KeyCompare();
700}
701//-----------------------------------------------------------------------------
702template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
703inline
704typename DGtal::LabelledMap<TData, L, TWord, N, M>::ValueCompare
705DGtal::LabelledMap<TData, L, TWord, N, M>::
706value_comp() const
707{
708 return ValueCompare();
709}
710//-----------------------------------------------------------------------------
711template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
712inline
713void
714DGtal::LabelledMap<TData, L, TWord, N, M>::
715swap( Self & other )
716{
717 std::swap( myLabels, other.myLabels );
718 std::swap( myFirstBlock, other.myFirstBlock );
719}
720//-----------------------------------------------------------------------------
721template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
722inline
723typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
724DGtal::LabelledMap<TData, L, TWord, N, M>::
725count( const Key & key ) const
726{
727 return myLabels.test( key ) ? 1 : 0;
728}
729//-----------------------------------------------------------------------------
730template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
731inline
732const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
733DGtal::LabelledMap<TData, L, TWord, N, M>::
734blockAt( size_t idx ) const
735{
736 ASSERT( idx < size() );
737 if ( idx < N )
738 return myFirstBlock.datas[ idx ];
739 else if ( ( idx == N ) && ( size() == N+1 ) )
740 return myFirstBlock.data.lastData;
741 const __AnyBlock* ptr = myFirstBlock.data.nextBlock;
742 idx -= N;
743 while ( idx >= M )
744 {
745 idx -= M;
746 ptr = ptr->next;
747 }
748 ASSERT( ptr != 0 );
749 return ptr->datas[ idx ];
750}
751//-----------------------------------------------------------------------------
752template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
753inline
754typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
755DGtal::LabelledMap<TData, L, TWord, N, M>::
756blockAt( size_t idx )
757{
758 ASSERT( idx < size() );
759 if ( idx < N )
760 return myFirstBlock.datas[ idx ];
761 else if ( ( idx == N ) && ( size() == N+1 ) )
762 return myFirstBlock.data.lastData;
763 __AnyBlock* ptr = myFirstBlock.data.nextBlock;
764 idx -= N;
765 while ( idx >= M )
766 {
767 idx -= M;
768 ptr = ptr->next;
769 }
770 ASSERT( ptr != 0 );
771 return ptr->datas[ idx ];
772}
773//-----------------------------------------------------------------------------
774template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
775inline
776const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
777DGtal::LabelledMap<TData, L, TWord, N, M>::
778operator[]( const Key & key ) const
779{
780 ASSERT( key < L );
781 bool exists = myLabels.test( key );
782 if ( ! exists )
783 {
784 unsigned int block_size = size();
785 myLabels.set( key ); // must be done before so that 'index' works.
786 return blockInsert( myLabels.index( key ), block_size, Data() );
787 }
788 else
789 {
790 return blockAt( myLabels.index( key ) );
791 }
792}
793//-----------------------------------------------------------------------------
794template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
795inline
796typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
797DGtal::LabelledMap<TData, L, TWord, N, M>::
798operator[]( const Key & key )
799{
800 ASSERT( key < L );
801 bool exists = myLabels.test( key );
802 if ( ! exists )
803 {
804 auto block_size = size();
805 myLabels.set( key ); // must be done before so that 'index' works.
806 return blockInsert( myLabels.index( key ), block_size, Data() );
807 }
808 else
809 {
810 return blockAt( myLabels.index( key ) );
811 }
812}
813//-----------------------------------------------------------------------------
814template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
815inline
816const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
817DGtal::LabelledMap<TData, L, TWord, N, M>::
818fastAt( const Key & key ) const
819{
820 ASSERT( key < L );
821 ASSERT( myLabels.test( key ) );
822 return blockAt( myLabels.index( key ) );
823}
824//-----------------------------------------------------------------------------
825template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
826inline
827typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
828DGtal::LabelledMap<TData, L, TWord, N, M>::
829fastAt( const Key & key )
830{
831 ASSERT( key < L );
832 ASSERT( myLabels.test( key ) );
833 return blockAt( myLabels.index( key ) );
834}
835//-----------------------------------------------------------------------------
836template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
837inline
838void
839DGtal::LabelledMap<TData, L, TWord, N, M>::
840erase( Iterator position )
841{
842 Key key = (*position).first;
843 ASSERT( myLabels.test( key ) );
844 blockErase( myLabels.index( key ) );
845 myLabels.reset( key );
846}
847//-----------------------------------------------------------------------------
848template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
849inline
850typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
851DGtal::LabelledMap<TData, L, TWord, N, M>::
852erase( Key key )
853{
854 if ( myLabels.test( key ) )
855 {
856 blockErase( myLabels.index( key ) );
857 myLabels.reset( key );
858 return 1;
859 }
860 return 0;
861}
862//-----------------------------------------------------------------------------
863template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
864inline
865void
866DGtal::LabelledMap<TData, L, TWord, N, M>::
867erase( Iterator first, Iterator last )
868{
869 for ( ; first != last; ++first )
870 erase( first );
871}
872
873//-----------------------------------------------------------------------------
874template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
875inline
876std::pair<typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator, bool>
877DGtal::LabelledMap<TData, L, TWord, N, M>::
878insert( const Value & val )
879{
880 ASSERT( val.first < L );
881 bool exists = myLabels.test( val.first );
882 if ( ! exists )
883 {
884 unsigned int block_size = static_cast<unsigned int>( size() );
885 myLabels.set( val.first ); // must be done before so that 'index' works.
886 blockInsert( myLabels.index( val.first ), block_size, val.second );
887 }
888 Iterator position = begin();
889 while ( (*position).first != val.first )
890 {
891 // std::cerr << "[" << (*position).first << "]" << std::endl;
892 ++position;
893 }
894 return std::make_pair( position, exists );
895}
896//-----------------------------------------------------------------------------
897template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
898inline
899typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
900DGtal::LabelledMap<TData, L, TWord, N, M>::
901insert ( Iterator position, const Value & val )
902{
903 ASSERT( val.first < L );
904 if ( ! myLabels.test( val.first ) )
905 {
906 unsigned int block_size = size();
907 myLabels.set( val.first ); // must be done before so that 'index' works.
908 blockInsert( myLabels.index( val.first ), block_size, val.second );
909 }
910 position = begin();
911 while ( (*position).first != val.first )
912 {
913 //std::cerr << "[" << (*position).first << "]" << std::endl;
914 ++position;
915 }
916 return position;
917}
918//-----------------------------------------------------------------------------
919template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
920template <typename InputIterator>
921inline
922void
923DGtal::LabelledMap<TData, L, TWord, N, M>::
924insert( InputIterator first, InputIterator last )
925{
926 BOOST_CONCEPT_ASSERT(( boost::InputIterator< InputIterator > ));
927 for ( ; first != last; ++first )
928 {
929 Key k = first->first;
930 if ( ! myLabels.test( k ) )
931 {
932 auto block_size = size();
933 myLabels.set( k ); // must be done before so that 'index' works.
934 blockInsert( myLabels.index( k ), block_size, first->second );
935 }
936 }
937}
938//-----------------------------------------------------------------------------
939template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
940inline
941std::pair< typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator,
942 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator >
943DGtal::LabelledMap<TData, L, TWord, N, M>::
944equal_range( const Key & x )
945{
946 Iterator it = begin(), it_end = end();
947 for ( ; it != it_end; ++it )
948 {
949 if ( (*it).first == x )
950 {
951 // JOL: g++ does not compile correctly:
952 // return std::make_pair( it, ++it );
953 it_end = it; ++it_end;
954 return std::make_pair( it, it_end );
955 }
956 else if ( (*it).first > x ) return std::make_pair( it, it );
957 }
958 return std::make_pair( it_end, it_end );
959}
960//-----------------------------------------------------------------------------
961template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
962inline
963std::pair< typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator,
964 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator >
965DGtal::LabelledMap<TData, L, TWord, N, M>::
966equal_range( const Key & x ) const
967{
968 ConstIterator it = begin(), it_end = end();
969 for ( ; it != it_end; ++it )
970 {
971 if ( (*it).first == x ) return std::make_pair( it, ++it );
972 else if ( (*it).first > x ) return std::make_pair( it, it );
973 }
974 return std::make_pair( it_end, it_end );
975}
976//-----------------------------------------------------------------------------
977template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
978inline
979typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
980DGtal::LabelledMap<TData, L, TWord, N, M>::
981find( const Key & x )
982{
983 Iterator it = begin(), it_end = end();
984 for ( ; it != it_end; ++it )
985 {
986 if ( (*it).first == x ) return it;
987 else if ( (*it).first > x ) return it_end;
988 }
989 return it_end;
990}
991//-----------------------------------------------------------------------------
992template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
993inline
994typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
995DGtal::LabelledMap<TData, L, TWord, N, M>::
996find( const Key & x ) const
997{
998 ConstIterator it = begin(), it_end = end();
999 for ( ; it != it_end; ++it )
1000 {
1001 if ( (*it).first == x ) return it;
1002 else if ( (*it).first > x ) return it_end;
1003 }
1004 return it_end;
1005}
1006//-----------------------------------------------------------------------------
1007template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1008inline
1009typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1010DGtal::LabelledMap<TData, L, TWord, N, M>::
1011lower_bound( const Key & x )
1012{
1013 Iterator it = begin(), it_end = end();
1014 for ( ; it != it_end; ++it )
1015 {
1016 if ( (*it).first >= x ) return it;
1017 }
1018 return it_end;
1019}
1020//-----------------------------------------------------------------------------
1021template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1022inline
1023typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1024DGtal::LabelledMap<TData, L, TWord, N, M>::
1025lower_bound( const Key & x ) const
1026{
1027 ConstIterator it = begin(), it_end = end();
1028 for ( ; it != it_end; ++it )
1029 {
1030 if ( (*it).first >= x ) return it;
1031 }
1032 return it_end;
1033}
1034//-----------------------------------------------------------------------------
1035template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1036inline
1037typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1038DGtal::LabelledMap<TData, L, TWord, N, M>::
1039upper_bound( const Key & x )
1040{
1041 Iterator it = begin(), it_end = end();
1042 for ( ; it != it_end; ++it )
1043 {
1044 if ( (*it).first > x ) return it;
1045 }
1046 return it_end;
1047}
1048//-----------------------------------------------------------------------------
1049template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1050inline
1051typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1052DGtal::LabelledMap<TData, L, TWord, N, M>::
1053upper_bound( const Key & x ) const
1054{
1055 ConstIterator it = begin(), it_end = end();
1056 for ( ; it != it_end; ++it )
1057 {
1058 if ( (*it).first > x ) return it;
1059 }
1060 return it_end;
1061}
1062
1063//-----------------------------------------------------------------------------
1064template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1065inline
1066typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
1067DGtal::LabelledMap<TData, L, TWord, N, M>::
1068blockInsert( size_t idx, size_t block_size, const Data & data )
1069{
1070 ASSERT( idx <= block_size ); // end is ok.
1071 return myFirstBlock.insert( idx, block_size, data );
1072}
1073//-----------------------------------------------------------------------------
1074template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1075inline
1076void
1077DGtal::LabelledMap<TData, L, TWord, N, M>::
1078blockErase( size_t idx )
1079{
1080 ASSERT( idx < size() ); // end is not ok.
1081 myFirstBlock.erase( idx, size() );
1082}
1083//-----------------------------------------------------------------------------
1084template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1085inline
1086typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1087DGtal::LabelledMap<TData, L, TWord, N, M>::
1088begin()
1089{
1090 const Self* ptr = (const Self *) this;
1091 return Iterator( myLabels.begin(), ptr->blockBegin() );
1092}
1093//-----------------------------------------------------------------------------
1094template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1095inline
1096typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1097DGtal::LabelledMap<TData, L, TWord, N, M>::
1098end()
1099{
1100 const Self* ptr = (const Self *) this;
1101 return Iterator( myLabels.end(), ptr->blockEnd() );
1102}
1103//-----------------------------------------------------------------------------
1104template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1105inline
1106typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1107DGtal::LabelledMap<TData, L, TWord, N, M>::
1108begin() const
1109{
1110 return ConstIterator( myLabels.begin(), blockBegin() );
1111}
1112//-----------------------------------------------------------------------------
1113template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1114inline
1115typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1116DGtal::LabelledMap<TData, L, TWord, N, M>::
1117end() const
1118{
1119 return ConstIterator( myLabels.end(), blockEnd() );
1120}
1121//-----------------------------------------------------------------------------
1122template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1123inline
1124typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator
1125DGtal::LabelledMap<TData, L, TWord, N, M>::
1126blockBegin()
1127{
1128 return BlockIterator( myFirstBlock, 0, size() );
1129}
1130//-----------------------------------------------------------------------------
1131template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1132inline
1133typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator
1134DGtal::LabelledMap<TData, L, TWord, N, M>::
1135blockEnd()
1136{
1137 SizeType s = size();
1138 return BlockIterator( myFirstBlock, s, s );
1139}
1140//-----------------------------------------------------------------------------
1141template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1142inline
1143typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator
1144DGtal::LabelledMap<TData, L, TWord, N, M>::
1145blockBegin() const
1146{
1147 return BlockConstIterator( myFirstBlock, 0, size() );
1148}
1149//-----------------------------------------------------------------------------
1150template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1151inline
1152typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator
1153DGtal::LabelledMap<TData, L, TWord, N, M>::
1154blockEnd() const
1155{
1156 SizeType s = size();
1157 return BlockConstIterator( myFirstBlock, s, s );
1158}
1159
1160///////////////////////////////////////////////////////////////////////////////
1161// Interface - public :
1162
1163/**
1164 * Writes/Displays the object on an output stream.
1165 * @param out the output stream where the object is written.
1166 */
1167template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1168inline
1169void
1170DGtal::LabelledMap<TData, L, TWord, N, M>::
1171selfDisplay( std::ostream & out ) const
1172{
1173 if ( size() == 0 ) out << "()";
1174 else
1175 {
1176 ConstIterator it = begin();
1177 ConstIterator it_end = end();
1178 out << "( ";
1179 out << "(" << (*it).first << "," << (*it).second << ")";
1180 ++it;
1181 for ( ; it != it_end; ++it )
1182 {
1183 out << ",(" << (*it).first << "," << (*it).second << ")";
1184 }
1185 out << " )";
1186 }
1187 // {
1188 // BlockConstIterator it = blockBegin();
1189 // BlockConstIterator it_end = blockEnd();
1190 // BlockConstIterator it_last = it;
1191 // out << "(";
1192 // out << *it;
1193 // ++it;
1194 // for ( ; it != it_end; ++it )
1195 // {
1196 // out << ( ( it_last.myDatas == it.myDatas ) ? ',' : ';' );
1197 // out << *it;
1198 // it_last = it;
1199 // }
1200 // out << ")";
1201 // }
1202}
1203
1204/**
1205 * Checks the validity/consistency of the object.
1206 * @return 'true' if the object is valid, 'false' otherwise.
1207 */
1208template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1209inline
1210bool
1211DGtal::LabelledMap<TData, L, TWord, N, M>::isValid() const
1212{
1213 return true;
1214}
1215
1216
1217
1218///////////////////////////////////////////////////////////////////////////////
1219// Implementation of inline functions //
1220
1221template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1222inline
1223std::ostream&
1224DGtal::operator<< ( std::ostream & out,
1225 const LabelledMap<TData, L, TWord, N, M> & object )
1226{
1227 object.selfDisplay( out );
1228 return out;
1229}
1230
1231template <typename TData>
1232std::pair< unsigned int, unsigned int >
1233DGtal::detail::argminLabelledMapMemoryUsageForGeometricDistribution
1234( unsigned int L, double prob_no_data, double prob_one_data )
1235{
1236 unsigned int sL = 2 * ( ( ( L - 1 ) / 16 ) + 1 ); // word of 16bits
1237 // std::cerr << "L=" << L << " sL=" << sL << std::endl;
1238 LabelledMapMemFunctor F( prob_one_data, prob_no_data, sL, sizeof( TData ),
1239 sizeof( TData* ), 2 );
1240 double m = -1.0;
1241 unsigned int Nopt = 0;
1242 unsigned int Mopt = 0;
1243 for ( unsigned int N = 1; N < L; ++N )
1244 for ( unsigned int M = 2; M < (L-N); ++M )
1245 {
1246 // std::cerr << "Fmem(" << N << "," << M << ")="
1247 // << F.fctNM( N, M ) << std::endl;
1248 if ( ( m < 0.0 ) || ( F.fctNM( N, M ) < m ) )
1249 {
1250 Nopt = N; Mopt = M;
1251 m = F.fctNM( Nopt, Mopt );
1252 }
1253 }
1254 return std::make_pair( Nopt, Mopt );
1255}
1256
1257// //
1258///////////////////////////////////////////////////////////////////////////////
1259
1260
Generated on Sun Nov 27 2022 15:15:35 for DGtal by doxygen 1.9.5