DGtal  1.5.beta
IndexedListWithBlocks.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 IndexedListWithBlocks.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 IndexedListWithBlocks.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 IndexedListWithBlocks::Iterator
43 //-----------------------------------------------------------------------------
44 template <typename TValue, unsigned int N, unsigned int M>
45 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
46 ~Iterator()
47 {}
48 //-----------------------------------------------------------------------------
49 template <typename TValue, unsigned int N, unsigned int M>
50 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
51 Iterator()
52  : myIdx( 0 ), myValues( 0 )
53 {}
54 //-----------------------------------------------------------------------------
55 template <typename TValue, unsigned int N, unsigned int M>
56 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
57 Iterator( const Self & other)
58  : myIdx( other.myIdx ), myNbValues( other.myNbValues ),
59  myValues( other.myValues ), myNext( other.myNext )
60 {}
61 //-----------------------------------------------------------------------------
62 template <typename TValue, unsigned int N, unsigned int M>
63 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
64 Iterator( FirstBlock & block, unsigned int idx )
65 {
66  ASSERT( idx <= block.size );
67  if ( block.size <= N+1 )
68  {
69  if ( idx <= N )
70  {
71  myIdx = idx;
72  myNbValues = N + 1;
73  myValues = block.values;
74  myNext = 0;
75  }
76  else
77  { // end iterator.
78  myIdx = 0;
79  myNbValues = 0;
80  myValues = 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  myNbValues = N;
92  myValues = block.values;
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  myNbValues = 0;
106  myValues = 0;
107  }
108  else
109  {
110  myIdx = idx;
111  myNbValues = M;
112  myValues = myNext->values;
113  }
114  }
115  }
116 }
117 //-----------------------------------------------------------------------------
118 template <typename TValue, unsigned int N, unsigned int M>
119 inline
120 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
121 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
122 operator=( const Self & other )
123 {
124  if ( this != &other )
125  {
126  myIdx = other.myIdx;
127  myNbValues = other.myNbValues;
128  myValues = other.myValues;
129  myNext = other.myNext;
130  }
131  return *this;
132 }
133 //-----------------------------------------------------------------------------
134 template <typename TValue, unsigned int N, unsigned int M>
135 inline
136 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Reference
137 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
138 operator*() const
139 {
140  ASSERT( myValues != 0 );
141  return myValues[ myIdx ];
142 }
143 //-----------------------------------------------------------------------------
144 template <typename TValue, unsigned int N, unsigned int M>
145 inline
146 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Pointer
147 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
148 operator->() const
149 {
150  ASSERT( myValues != 0 );
151  return myValues + myIdx;
152 }
153 //-----------------------------------------------------------------------------
154 template <typename TValue, unsigned int N, unsigned int M>
155 inline
156 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
157 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
158 operator++()
159 {
160  return this->operator+=( 1 );
161 }
162 //-----------------------------------------------------------------------------
163 template <typename TValue, unsigned int N, unsigned int M>
164 inline
165 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self
166 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
167 operator++( int )
168 {
169  Self tmp( *this );
170  this->operator++();
171  return tmp;
172 }
173 //-----------------------------------------------------------------------------
174 template <typename TValue, unsigned int N, unsigned int M>
175 inline
176 bool
177 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
178 operator==( const Self & other ) const
179 {
180  return ( myValues == other.myValues ) && ( myIdx == other.myIdx );
181 }
182 //-----------------------------------------------------------------------------
183 template <typename TValue, unsigned int N, unsigned int M>
184 inline
185 bool
186 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
187 operator!=( const Self & other ) const
188 {
189  return ( myValues != other.myValues ) || ( myIdx != other.myIdx );
190 }
191 //-----------------------------------------------------------------------------
192 template <typename TValue, unsigned int N, unsigned int M>
193 inline
194 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
195 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
196 operator+=( DifferenceType n )
197 {
198  myIdx += n;
199  while ( myIdx >= myNbValues )
200  {
201  if ( myNext == 0 )
202  {
203  myValues = 0;
204  myIdx = 0;
205  break;
206  }
207  myIdx -= myNbValues;
208  myValues = myNext->values;
209  myNbValues = M;
210  myNext = myNext->next;
211  }
212  return *this;
213 }
214 //-----------------------------------------------------------------------------
215 template <typename TValue, unsigned int N, unsigned int M>
216 inline
217 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Reference
218 DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
219 operator[]( DifferenceType n ) const
220 {
221  Self tmp( *this );
222  tmp += n;
223  return *tmp;
224 }
225 
226 ///////////////////////////////////////////////////////////////////////////////
227 // class IndexedListWithBlocks::ConstIterator
228 //-----------------------------------------------------------------------------
229 template <typename TValue, unsigned int N, unsigned int M>
230 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
231 ~ConstIterator()
232 {}
233 //-----------------------------------------------------------------------------
234 template <typename TValue, unsigned int N, unsigned int M>
235 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
236 ConstIterator()
237  : myIdx( 0 ), myValues( 0 )
238 {}
239 //-----------------------------------------------------------------------------
240 template <typename TValue, unsigned int N, unsigned int M>
241 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
242 ConstIterator( const Self & other)
243  : myIdx( other.myIdx ), myNbValues( other.myNbValues ),
244  myValues( other.myValues ), myNext( other.myNext )
245 {}
246 //-----------------------------------------------------------------------------
247 template <typename TValue, unsigned int N, unsigned int M>
248 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
249 ConstIterator( const FirstBlock & block, unsigned int idx )
250 {
251  ASSERT( idx <= block.size );
252  if ( block.size <= N+1 )
253  {
254  if ( idx <= N )
255  {
256  myIdx = idx;
257  myNbValues = N + 1;
258  myValues = block.values;
259  myNext = 0;
260  }
261  else
262  { // end iterator.
263  myIdx = 0;
264  myNbValues = 0;
265  myValues = 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  myNbValues = N;
277  myValues = block.values;
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  myNbValues = 0;
291  myValues = 0;
292  }
293  else
294  {
295  myIdx = idx;
296  myNbValues = M;
297  myValues = myNext->values;
298  }
299  }
300  }
301 }
302 //-----------------------------------------------------------------------------
303 template <typename TValue, unsigned int N, unsigned int M>
304 inline
305 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
306 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
307 operator=( const Self & other )
308 {
309  if ( this != &other )
310  {
311  myIdx = other.myIdx;
312  myNbValues = other.myNbValues;
313  myValues = other.myValues;
314  myNext = other.myNext;
315  }
316  return *this;
317 }
318 //-----------------------------------------------------------------------------
319 template <typename TValue, unsigned int N, unsigned int M>
320 inline
321 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Reference
322 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
323 operator*() const
324 {
325  ASSERT( myValues != 0 );
326  return myValues[ myIdx ];
327 }
328 //-----------------------------------------------------------------------------
329 template <typename TValue, unsigned int N, unsigned int M>
330 inline
331 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Pointer
332 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
333 operator->() const
334 {
335  ASSERT( myValues != 0 );
336  return myValues + myIdx;
337 }
338 //-----------------------------------------------------------------------------
339 template <typename TValue, unsigned int N, unsigned int M>
340 inline
341 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
342 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
343 operator++()
344 {
345  return this->operator+=( 1 );
346 }
347 //-----------------------------------------------------------------------------
348 template <typename TValue, unsigned int N, unsigned int M>
349 inline
350 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self
351 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
352 operator++( int )
353 {
354  Self tmp( *this );
355  this->operator++();
356  return tmp;
357 }
358 //-----------------------------------------------------------------------------
359 template <typename TValue, unsigned int N, unsigned int M>
360 inline
361 bool
362 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
363 operator==( const Self & other ) const
364 {
365  return ( myValues == other.myValues ) && ( myIdx == other.myIdx );
366 }
367 //-----------------------------------------------------------------------------
368 template <typename TValue, unsigned int N, unsigned int M>
369 inline
370 bool
371 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
372 operator!=( const Self & other ) const
373 {
374  return ( myValues != other.myValues ) || ( myIdx != other.myIdx );
375 }
376 //-----------------------------------------------------------------------------
377 template <typename TValue, unsigned int N, unsigned int M>
378 inline
379 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
380 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
381 operator+=( DifferenceType n )
382 {
383  myIdx += n;
384  while ( myIdx >= myNbValues )
385  {
386  if ( myNext == 0 )
387  {
388  myValues = 0;
389  myIdx = 0;
390  break;
391  }
392  myIdx -= myNbValues;
393  myValues = myNext->values;
394  myNbValues = M;
395  myNext = myNext->next;
396  }
397  return *this;
398 }
399 //-----------------------------------------------------------------------------
400 template <typename TValue, unsigned int N, unsigned int M>
401 inline
402 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Reference
403 DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
404 operator[]( DifferenceType n ) const
405 {
406  Self tmp( *this );
407  tmp += n;
408  return *tmp;
409 }
410 
411 
412 //-----------------------------------------------------------------------------
413 template <typename TValue, unsigned int N, unsigned int M>
414 inline
415 DGtal::IndexedListWithBlocks<TValue, N, M>::
416 IndexedListWithBlocks()
417 { // default constructor of myFirstBlock is automatically called.
418 }
419 //-----------------------------------------------------------------------------
420 template <typename TValue, unsigned int N, unsigned int M>
421 inline
422 DGtal::IndexedListWithBlocks<TValue, N, M>::
423 ~IndexedListWithBlocks()
424 {
425  clear();
426 }
427 //-----------------------------------------------------------------------------
428 template <typename TValue, unsigned int N, unsigned int M>
429 inline
430 DGtal::IndexedListWithBlocks<TValue, N, M>::
431 IndexedListWithBlocks( const IndexedListWithBlocks & other )
432  : myFirstBlock( other.myFirstBlock )
433 {
434  unsigned int s = N + 1; // there is one more stored value in the last block.
435  const AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
436  AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
437  while ( s < myFirstBlock.size )
438  {
439  *currentPointer = new AnyBlock( *nextBlock );
440  s += M;
441  currentPointer = & ( currentPointer->data.nextBlock );
442  }
443 }
444 //-----------------------------------------------------------------------------
445 template <typename TValue, unsigned int N, unsigned int M>
446 inline
447 DGtal::IndexedListWithBlocks<TValue, N, M> &
448 DGtal::IndexedListWithBlocks<TValue, N, M>::
449 operator=( const IndexedListWithBlocks & other )
450 {
451  if ( this != &other )
452  {
453  clear();
454  myFirstBlock = other.myFirstBlock;
455  // there is one more stored value in the last block.
456  unsigned int s = N + 1;
457  const AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
458  AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
459  while ( s < myFirstBlock.size )
460  {
461  *currentPointer = new AnyBlock( *nextBlock );
462  s += M;
463  currentPointer = & ( (*currentPointer)->next );
464  }
465  }
466  return *this;
467 }
468 //-----------------------------------------------------------------------------
469 template <typename TValue, unsigned int N, unsigned int M>
470 inline
471 void
472 DGtal::IndexedListWithBlocks<TValue, N, M>::
473 clear()
474 {
475  AnyBlock* nextBlock = myFirstBlock.data.nextBlock;
476  while ( nextBlock != 0 )
477  {
478  AnyBlock* ptr = nextBlock;
479  nextBlock = nextBlock->next;
480  delete ptr;
481  }
482  myFirstBlock.size = 0;
483  myFirstBlock.data.nextBlock = 0;
484 }
485 //-----------------------------------------------------------------------------
486 template <typename TValue, unsigned int N, unsigned int M>
487 inline
488 typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
489 DGtal::IndexedListWithBlocks<TValue, N, M>::
490 size() const
491 {
492  return myFirstBlock.size;
493 }
494 //-----------------------------------------------------------------------------
495 template <typename TValue, unsigned int N, unsigned int M>
496 inline
497 bool
498 DGtal::IndexedListWithBlocks<TValue, N, M>::
499 empty() const
500 {
501  return size() == 0;
502 }
503 //-----------------------------------------------------------------------------
504 template <typename TValue, unsigned int N, unsigned int M>
505 inline
506 typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
507 DGtal::IndexedListWithBlocks<TValue, N, M>::
508 max_size() const
509 {
510  return SizeType( -1 ) / (2*sizeof( Value ));
511 }
512 //-----------------------------------------------------------------------------
513 template <typename TValue, unsigned int N, unsigned int M>
514 inline
515 typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
516 DGtal::IndexedListWithBlocks<TValue, N, M>::
517 capacity() const
518 {
519  return ( size() <= (N+1) )
520  ? N+1
521  : ( 1 + ( size() - 1 - N ) / M ) * M + N;
522 }
523 //-----------------------------------------------------------------------------
524 template <typename TValue, unsigned int N, unsigned int M>
525 inline
526 const typename DGtal::IndexedListWithBlocks<TValue, N, M>::Value &
527 DGtal::IndexedListWithBlocks<TValue, N, M>::
528 operator[]( unsigned int idx ) const
529 {
530  ASSERT( idx < size() );
531  if ( idx < N )
532  return myFirstBlock.values[ idx ];
533  else if ( ( idx == N ) && ( size() == N+1 ) )
534  return myFirstBlock.data.lastValue;
535  const AnyBlock* ptr = myFirstBlock.data.nextBlock;
536  idx -= N;
537  while ( idx >= M )
538  {
539  idx -= M;
540  ptr = ptr->next;
541  }
542  ASSERT( ptr != 0 );
543  return ptr->values[ idx ];
544 }
545 //-----------------------------------------------------------------------------
546 template <typename TValue, unsigned int N, unsigned int M>
547 inline
548 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Value &
549 DGtal::IndexedListWithBlocks<TValue, N, M>::
550 operator[]( unsigned int idx )
551 {
552  ASSERT( idx < size() );
553  if ( idx < N )
554  return myFirstBlock.values[ idx ];
555  else if ( ( idx == N ) && ( size() == N+1 ) )
556  return myFirstBlock.data.lastValue;
557  AnyBlock* ptr = myFirstBlock.data.nextBlock;
558  idx -= N;
559  while ( idx >= M )
560  {
561  idx -= M;
562  ptr = ptr->next;
563  }
564  ASSERT( ptr != 0 );
565  return ptr->values[ idx ];
566 }
567 //-----------------------------------------------------------------------------
568 template <typename TValue, unsigned int N, unsigned int M>
569 inline
570 void
571 DGtal::IndexedListWithBlocks<TValue, N, M>::
572 insert( unsigned int idx, const Value & value )
573 {
574  ASSERT( idx <= size() ); // end is ok.
575  myFirstBlock.insert( idx, value );
576 }
577 //-----------------------------------------------------------------------------
578 template <typename TValue, unsigned int N, unsigned int M>
579 inline
580 void
581 DGtal::IndexedListWithBlocks<TValue, N, M>::
582 erase( unsigned int idx )
583 {
584  ASSERT( idx < size() ); // end is not ok.
585  myFirstBlock.erase( idx );
586 }
587 
588 
589 //-----------------------------------------------------------------------------
590 template <typename TValue, unsigned int N, unsigned int M>
591 inline
592 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator
593 DGtal::IndexedListWithBlocks<TValue, N, M>::
594 begin()
595 {
596  return Iterator( myFirstBlock, 0 );
597 }
598 //-----------------------------------------------------------------------------
599 template <typename TValue, unsigned int N, unsigned int M>
600 inline
601 typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator
602 DGtal::IndexedListWithBlocks<TValue, N, M>::
603 end()
604 {
605  return Iterator( myFirstBlock, size() );
606 }
607 //-----------------------------------------------------------------------------
608 template <typename TValue, unsigned int N, unsigned int M>
609 inline
610 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator
611 DGtal::IndexedListWithBlocks<TValue, N, M>::
612 begin() const
613 {
614  return ConstIterator( myFirstBlock, 0 );
615 }
616 //-----------------------------------------------------------------------------
617 template <typename TValue, unsigned int N, unsigned int M>
618 inline
619 typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator
620 DGtal::IndexedListWithBlocks<TValue, N, M>::
621 end() const
622 {
623  return ConstIterator( myFirstBlock, size() );
624 }
625 
626 ///////////////////////////////////////////////////////////////////////////////
627 // Interface - public :
628 
629 /**
630  * Writes/Displays the object on an output stream.
631  * @param out the output stream where the object is written.
632  */
633 template <typename TValue, unsigned int N, unsigned int M>
634 inline
635 void
636 DGtal::IndexedListWithBlocks<TValue, N, M>::
637 selfDisplay( std::ostream & out ) const
638 {
639  if ( size() == 0 ) out << "()";
640  else
641  {
642  ConstIterator it = begin();
643  ConstIterator it_end = end();
644  ConstIterator it_last = it;
645  out << "(";
646  out << *it;
647  ++it;
648  for ( ; it != it_end; ++it )
649  {
650  out << ( ( it_last.myValues == it.myValues ) ? ',' : ';' );
651  out << *it;
652  it_last = it;
653  }
654  out << ")";
655  }
656 }
657 
658 /**
659  * Checks the validity/consistency of the object.
660  * @return 'true' if the object is valid, 'false' otherwise.
661  */
662 template <typename TValue, unsigned int N, unsigned int M>
663 inline
664 bool
665 DGtal::IndexedListWithBlocks<TValue, N, M>::isValid() const
666 {
667  return true;
668 }
669 
670 
671 
672 ///////////////////////////////////////////////////////////////////////////////
673 // Implementation of inline functions //
674 
675 template <typename TValue, unsigned int N, unsigned int M>
676 inline
677 std::ostream&
678 DGtal::operator<< ( std::ostream & out,
679  const IndexedListWithBlocks<TValue, N, M> & object )
680 {
681  object.selfDisplay( out );
682  return out;
683 }
684 
685 // //
686 ///////////////////////////////////////////////////////////////////////////////
687 
688