DGtal  1.5.beta
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 //-----------------------------------------------------------------------------
44 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
45 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
46 ~BlockIterator()
47 {}
48 //-----------------------------------------------------------------------------
49 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
50 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
51 BlockIterator()
52  : myIdx( 0 ), myDatas( 0 )
53 {}
54 //-----------------------------------------------------------------------------
55 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
56 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
57 BlockIterator( const Self & other)
58  : myIdx( other.myIdx ), myNbDatas( other.myNbDatas ),
59  myDatas( other.myDatas ), myNext( other.myNext )
60 {}
61 //-----------------------------------------------------------------------------
62 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
63 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
64 BlockIterator( __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 //-----------------------------------------------------------------------------
118 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
119 inline
120 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
121 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
122 operator=( 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 //-----------------------------------------------------------------------------
134 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
135 inline
136 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Reference
137 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
138 operator*() const
139 {
140  ASSERT( myDatas != 0 );
141  return myDatas[ myIdx ];
142 }
143 //-----------------------------------------------------------------------------
144 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
145 inline
146 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Pointer
147 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
148 operator->() const
149 {
150  ASSERT( myDatas != 0 );
151  return myDatas + myIdx;
152 }
153 //-----------------------------------------------------------------------------
154 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
155 inline
156 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
157 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
158 operator++()
159 {
160  return this->operator+=( 1 );
161 }
162 //-----------------------------------------------------------------------------
163 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
164 inline
165 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self
166 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
167 operator++( int )
168 {
169  Self tmp( *this );
170  this->operator++();
171  return tmp;
172 }
173 //-----------------------------------------------------------------------------
174 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
175 inline
176 bool
177 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
178 operator==( const Self & other ) const
179 {
180  return ( myDatas == other.myDatas ) && ( myIdx == other.myIdx );
181 }
182 //-----------------------------------------------------------------------------
183 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
184 inline
185 bool
186 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
187 operator!=( const Self & other ) const
188 {
189  return ( myDatas != other.myDatas ) || ( myIdx != other.myIdx );
190 }
191 //-----------------------------------------------------------------------------
192 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
193 inline
194 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Self &
195 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
196 operator+=( 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 //-----------------------------------------------------------------------------
215 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
216 inline
217 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::Reference
218 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator::
219 operator[]( DifferenceType n ) const
220 {
221  Self tmp( *this );
222  tmp += n;
223  return *tmp;
224 }
225 
226 ///////////////////////////////////////////////////////////////////////////////
227 // class LabelledMap::BlockConstIterator
228 //-----------------------------------------------------------------------------
229 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
230 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
231 ~BlockConstIterator()
232 {}
233 //-----------------------------------------------------------------------------
234 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
235 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
236 BlockConstIterator()
237  : myIdx( 0 ), myDatas( 0 )
238 {}
239 //-----------------------------------------------------------------------------
240 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
241 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
242 BlockConstIterator( const Self & other)
243  : myIdx( other.myIdx ), myNbDatas( other.myNbDatas ),
244  myDatas( other.myDatas ), myNext( other.myNext )
245 {}
246 //-----------------------------------------------------------------------------
247 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
248 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
249 BlockConstIterator( 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 //-----------------------------------------------------------------------------
303 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
304 inline
305 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
306 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
307 operator=( 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 //-----------------------------------------------------------------------------
319 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
320 inline
321 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Reference
322 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
323 operator*() const
324 {
325  ASSERT( myDatas != 0 );
326  return myDatas[ myIdx ];
327 }
328 //-----------------------------------------------------------------------------
329 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
330 inline
331 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Pointer
332 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
333 operator->() const
334 {
335  ASSERT( myDatas != 0 );
336  return myDatas + myIdx;
337 }
338 //-----------------------------------------------------------------------------
339 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
340 inline
341 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
342 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
343 operator++()
344 {
345  return this->operator+=( 1 );
346 }
347 //-----------------------------------------------------------------------------
348 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
349 inline
350 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self
351 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
352 operator++( int )
353 {
354  Self tmp( *this );
355  this->operator++();
356  return tmp;
357 }
358 //-----------------------------------------------------------------------------
359 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
360 inline
361 bool
362 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
363 operator==( const Self & other ) const
364 {
365  return ( myDatas == other.myDatas ) && ( myIdx == other.myIdx );
366 }
367 //-----------------------------------------------------------------------------
368 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
369 inline
370 bool
371 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
372 operator!=( const Self & other ) const
373 {
374  return ( myDatas != other.myDatas ) || ( myIdx != other.myIdx );
375 }
376 //-----------------------------------------------------------------------------
377 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
378 inline
379 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Self &
380 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
381 operator+=( 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 //-----------------------------------------------------------------------------
400 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
401 inline
402 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::Reference
403 DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator::
404 operator[]( DifferenceType n ) const
405 {
406  Self tmp( *this );
407  tmp += n;
408  return *tmp;
409 }
410 
411 ///////////////////////////////////////////////////////////////////////////////
412 // class LabelledMap::ConstIterator
413 //-----------------------------------------------------------------------------
414 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
415 inline
416 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
417 ConstIterator( LabelsConstIterator lIt, BlockConstIterator bIt )
418  : myLabelsIt( lIt ), myBlockIt( bIt )
419 {}
420 //-----------------------------------------------------------------------------
421 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
422 inline
423 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
424 ~ConstIterator()
425 {}
426 //-----------------------------------------------------------------------------
427 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
428 inline
429 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
430 ConstIterator()
431 {}
432 //-----------------------------------------------------------------------------
433 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
434 inline
435 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
436 ConstIterator( const ConstIterator & other )
437  : myLabelsIt( other.myLabelsIt ), myBlockIt( other.myBlockIt )
438 {}
439 //-----------------------------------------------------------------------------
440 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
441 inline
442 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self &
443 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
444 operator= ( const Self & other )
445 {
446  if ( this != &other )
447  {
448  myLabelsIt = other.myLabelsIt;
449  myBlockIt = other.myBlockIt;
450  }
451  return *this;
452 }
453 //-----------------------------------------------------------------------------
454 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
455 inline
456 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Reference
457 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
458 operator*() const
459 {
460  return std::make_pair( *myLabelsIt, *myBlockIt );
461 }
462 //-----------------------------------------------------------------------------
463 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
464 inline
465 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Pointer
466 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
467 operator->() const
468 {
469  // Warning: not thread-safe.
470  static Value __static_tmp;
471  __static_tmp = this->operator*();
472  return &__static_tmp;
473 }
474 //-----------------------------------------------------------------------------
475 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
476 inline
477 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self&
478 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
479 operator++()
480 {
481  ++myLabelsIt;
482  ++myBlockIt;
483  return *this;
484 }
485 //-----------------------------------------------------------------------------
486 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
487 inline
488 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::Self
489 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
490 operator++( int )
491 {
492  Self tmp( *this );
493  this->operator++();
494  return tmp;
495 }
496 //-----------------------------------------------------------------------------
497 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
498 inline
499 bool
500 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
501 operator==( const Self & other ) const
502 {
503  return myLabelsIt == other.myLabelsIt;
504 }
505 //-----------------------------------------------------------------------------
506 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
507 inline
508 bool
509 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
510 operator!=( const Self & other ) const
511 {
512  return myLabelsIt != other.myLabelsIt;
513 }
514 //-----------------------------------------------------------------------------
515 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
516 inline
517 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data&
518 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
519 _data() const
520 {
521  return const_cast<Data&>( *myBlockIt );
522 }
523 //-----------------------------------------------------------------------------
524 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
525 inline
526 const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data&
527 DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator::
528 _const_data() const
529 {
530  return *myBlockIt;
531 }
532 
533 ///////////////////////////////////////////////////////////////////////////////
534 // class LabelledMap
535 //-----------------------------------------------------------------------------
536 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
537 inline
538 DGtal::LabelledMap<TData, L, TWord, N, M>::
539 LabelledMap()
540 { // default constructor of myLabels and myFirstBlock is automatically called.
541 }
542 //-----------------------------------------------------------------------------
543 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
544 inline
545 DGtal::LabelledMap<TData, L, TWord, N, M>::
546 ~LabelledMap()
547 {
548  blockClear( size() );
549 }
550 //-----------------------------------------------------------------------------
551 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
552 inline
553 DGtal::LabelledMap<TData, L, TWord, N, M>::
554 LabelledMap( 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 //-----------------------------------------------------------------------------
574 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
575 template <typename InputIterator>
576 inline
577 DGtal::LabelledMap<TData, L, TWord, N, M>::
578 LabelledMap( 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 //-----------------------------------------------------------------------------
587 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
588 inline
589 DGtal::LabelledMap<TData, L, TWord, N, M> &
590 DGtal::LabelledMap<TData, L, TWord, N, M>::
591 operator=( 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 //-----------------------------------------------------------------------------
617 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
618 inline
619 void
620 DGtal::LabelledMap<TData, L, TWord, N, M>::
621 clear()
622 {
623  blockClear( size() );
624  myLabels.reset();
625 }
626 //-----------------------------------------------------------------------------
627 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
628 inline
629 void
630 DGtal::LabelledMap<TData, L, TWord, N, M>::
631 blockClear( 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 //-----------------------------------------------------------------------------
646 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
647 inline
648 const typename DGtal::LabelledMap<TData, L, TWord, N, M>::LabelsType &
649 DGtal::LabelledMap<TData, L, TWord, N, M>::
650 labels() const
651 {
652  return myLabels;
653 }
654 //-----------------------------------------------------------------------------
655 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
656 inline
657 typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
658 DGtal::LabelledMap<TData, L, TWord, N, M>::
659 size() const
660 {
661  return myLabels.count();
662 }
663 //-----------------------------------------------------------------------------
664 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
665 inline
666 bool
667 DGtal::LabelledMap<TData, L, TWord, N, M>::
668 empty() const
669 {
670  return size() == 0;
671 }
672 //-----------------------------------------------------------------------------
673 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
674 inline
675 typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
676 DGtal::LabelledMap<TData, L, TWord, N, M>::
677 max_size() const
678 {
679  return L; //SizeType( -1 ) / (2*sizeof( Data ));
680 }
681 //-----------------------------------------------------------------------------
682 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
683 inline
684 typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
685 DGtal::LabelledMap<TData, L, TWord, N, M>::
686 capacity() const
687 {
688  return ( size() <= (N+1) )
689  ? N+1
690  : ( 1 + ( size() - 1 - N ) / M ) * M + N;
691 }
692 //-----------------------------------------------------------------------------
693 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
694 inline
695 typename DGtal::LabelledMap<TData, L, TWord, N, M>::KeyCompare
696 DGtal::LabelledMap<TData, L, TWord, N, M>::
697 key_comp() const
698 {
699  return KeyCompare();
700 }
701 //-----------------------------------------------------------------------------
702 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
703 inline
704 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ValueCompare
705 DGtal::LabelledMap<TData, L, TWord, N, M>::
706 value_comp() const
707 {
708  return ValueCompare();
709 }
710 //-----------------------------------------------------------------------------
711 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
712 inline
713 void
714 DGtal::LabelledMap<TData, L, TWord, N, M>::
715 swap( Self & other )
716 {
717  std::swap( myLabels, other.myLabels );
718  std::swap( myFirstBlock, other.myFirstBlock );
719 }
720 //-----------------------------------------------------------------------------
721 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
722 inline
723 typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
724 DGtal::LabelledMap<TData, L, TWord, N, M>::
725 count( const Key & key ) const
726 {
727  return myLabels.test( key ) ? 1 : 0;
728 }
729 //-----------------------------------------------------------------------------
730 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
731 inline
732 const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
733 DGtal::LabelledMap<TData, L, TWord, N, M>::
734 blockAt( 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 //-----------------------------------------------------------------------------
752 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
753 inline
754 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
755 DGtal::LabelledMap<TData, L, TWord, N, M>::
756 blockAt( 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 //-----------------------------------------------------------------------------
774 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
775 inline
776 const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
777 DGtal::LabelledMap<TData, L, TWord, N, M>::
778 operator[]( 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 //-----------------------------------------------------------------------------
794 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
795 inline
796 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
797 DGtal::LabelledMap<TData, L, TWord, N, M>::
798 operator[]( 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 //-----------------------------------------------------------------------------
814 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
815 inline
816 const typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
817 DGtal::LabelledMap<TData, L, TWord, N, M>::
818 fastAt( const Key & key ) const
819 {
820  ASSERT( key < L );
821  ASSERT( myLabels.test( key ) );
822  return blockAt( myLabels.index( key ) );
823 }
824 //-----------------------------------------------------------------------------
825 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
826 inline
827 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
828 DGtal::LabelledMap<TData, L, TWord, N, M>::
829 fastAt( const Key & key )
830 {
831  ASSERT( key < L );
832  ASSERT( myLabels.test( key ) );
833  return blockAt( myLabels.index( key ) );
834 }
835 //-----------------------------------------------------------------------------
836 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
837 inline
838 void
839 DGtal::LabelledMap<TData, L, TWord, N, M>::
840 erase( Iterator position )
841 {
842  Key key = (*position).first;
843  ASSERT( myLabels.test( key ) );
844  blockErase( myLabels.index( key ) );
845  myLabels.reset( key );
846 }
847 //-----------------------------------------------------------------------------
848 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
849 inline
850 typename DGtal::LabelledMap<TData, L, TWord, N, M>::SizeType
851 DGtal::LabelledMap<TData, L, TWord, N, M>::
852 erase( 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 //-----------------------------------------------------------------------------
863 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
864 inline
865 void
866 DGtal::LabelledMap<TData, L, TWord, N, M>::
867 erase( Iterator first, Iterator last )
868 {
869  for ( ; first != last; ++first )
870  erase( first );
871 }
872 
873 //-----------------------------------------------------------------------------
874 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
875 inline
876 std::pair<typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator, bool>
877 DGtal::LabelledMap<TData, L, TWord, N, M>::
878 insert( 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 //-----------------------------------------------------------------------------
897 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
898 inline
899 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
900 DGtal::LabelledMap<TData, L, TWord, N, M>::
901 insert ( 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 //-----------------------------------------------------------------------------
919 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
920 template <typename InputIterator>
921 inline
922 void
923 DGtal::LabelledMap<TData, L, TWord, N, M>::
924 insert( 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 //-----------------------------------------------------------------------------
939 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
940 inline
941 std::pair< typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator,
942  typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator >
943 DGtal::LabelledMap<TData, L, TWord, N, M>::
944 equal_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 //-----------------------------------------------------------------------------
961 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
962 inline
963 std::pair< typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator,
964  typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator >
965 DGtal::LabelledMap<TData, L, TWord, N, M>::
966 equal_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 //-----------------------------------------------------------------------------
977 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
978 inline
979 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
980 DGtal::LabelledMap<TData, L, TWord, N, M>::
981 find( 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 //-----------------------------------------------------------------------------
992 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
993 inline
994 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
995 DGtal::LabelledMap<TData, L, TWord, N, M>::
996 find( 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 //-----------------------------------------------------------------------------
1007 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1008 inline
1009 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1010 DGtal::LabelledMap<TData, L, TWord, N, M>::
1011 lower_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 //-----------------------------------------------------------------------------
1021 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1022 inline
1023 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1024 DGtal::LabelledMap<TData, L, TWord, N, M>::
1025 lower_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 //-----------------------------------------------------------------------------
1035 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1036 inline
1037 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1038 DGtal::LabelledMap<TData, L, TWord, N, M>::
1039 upper_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 //-----------------------------------------------------------------------------
1049 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1050 inline
1051 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1052 DGtal::LabelledMap<TData, L, TWord, N, M>::
1053 upper_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 //-----------------------------------------------------------------------------
1064 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1065 inline
1066 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Data &
1067 DGtal::LabelledMap<TData, L, TWord, N, M>::
1068 blockInsert( 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 //-----------------------------------------------------------------------------
1074 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1075 inline
1076 void
1077 DGtal::LabelledMap<TData, L, TWord, N, M>::
1078 blockErase( size_t idx )
1079 {
1080  ASSERT( idx < size() ); // end is not ok.
1081  myFirstBlock.erase( idx, size() );
1082 }
1083 //-----------------------------------------------------------------------------
1084 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1085 inline
1086 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1087 DGtal::LabelledMap<TData, L, TWord, N, M>::
1088 begin()
1089 {
1090  const Self* ptr = (const Self *) this;
1091  return Iterator( myLabels.begin(), ptr->blockBegin() );
1092 }
1093 //-----------------------------------------------------------------------------
1094 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1095 inline
1096 typename DGtal::LabelledMap<TData, L, TWord, N, M>::Iterator
1097 DGtal::LabelledMap<TData, L, TWord, N, M>::
1098 end()
1099 {
1100  const Self* ptr = (const Self *) this;
1101  return Iterator( myLabels.end(), ptr->blockEnd() );
1102 }
1103 //-----------------------------------------------------------------------------
1104 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1105 inline
1106 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1107 DGtal::LabelledMap<TData, L, TWord, N, M>::
1108 begin() const
1109 {
1110  return ConstIterator( myLabels.begin(), blockBegin() );
1111 }
1112 //-----------------------------------------------------------------------------
1113 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1114 inline
1115 typename DGtal::LabelledMap<TData, L, TWord, N, M>::ConstIterator
1116 DGtal::LabelledMap<TData, L, TWord, N, M>::
1117 end() const
1118 {
1119  return ConstIterator( myLabels.end(), blockEnd() );
1120 }
1121 //-----------------------------------------------------------------------------
1122 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1123 inline
1124 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator
1125 DGtal::LabelledMap<TData, L, TWord, N, M>::
1126 blockBegin()
1127 {
1128  return BlockIterator( myFirstBlock, 0, size() );
1129 }
1130 //-----------------------------------------------------------------------------
1131 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1132 inline
1133 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockIterator
1134 DGtal::LabelledMap<TData, L, TWord, N, M>::
1135 blockEnd()
1136 {
1137  SizeType s = size();
1138  return BlockIterator( myFirstBlock, s, s );
1139 }
1140 //-----------------------------------------------------------------------------
1141 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1142 inline
1143 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator
1144 DGtal::LabelledMap<TData, L, TWord, N, M>::
1145 blockBegin() const
1146 {
1147  return BlockConstIterator( myFirstBlock, 0, size() );
1148 }
1149 //-----------------------------------------------------------------------------
1150 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1151 inline
1152 typename DGtal::LabelledMap<TData, L, TWord, N, M>::BlockConstIterator
1153 DGtal::LabelledMap<TData, L, TWord, N, M>::
1154 blockEnd() 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  */
1167 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1168 inline
1169 void
1170 DGtal::LabelledMap<TData, L, TWord, N, M>::
1171 selfDisplay( 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  */
1208 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1209 inline
1210 bool
1211 DGtal::LabelledMap<TData, L, TWord, N, M>::isValid() const
1212 {
1213  return true;
1214 }
1215 
1216 
1217 
1218 ///////////////////////////////////////////////////////////////////////////////
1219 // Implementation of inline functions //
1220 
1221 template <typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
1222 inline
1223 std::ostream&
1224 DGtal::operator<< ( std::ostream & out,
1225  const LabelledMap<TData, L, TWord, N, M> & object )
1226 {
1227  object.selfDisplay( out );
1228  return out;
1229 }
1230 
1231 template <typename TData>
1232 std::pair< unsigned int, unsigned int >
1233 DGtal::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