DGtal 1.3.0
Loading...
Searching...
No Matches
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//-----------------------------------------------------------------------------
44template <typename TValue, unsigned int N, unsigned int M>
45DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
46~Iterator()
47{}
48//-----------------------------------------------------------------------------
49template <typename TValue, unsigned int N, unsigned int M>
50DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
51Iterator()
52 : myIdx( 0 ), myValues( 0 )
53{}
54//-----------------------------------------------------------------------------
55template <typename TValue, unsigned int N, unsigned int M>
56DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
57Iterator( const Self & other)
58 : myIdx( other.myIdx ), myNbValues( other.myNbValues ),
59 myValues( other.myValues ), myNext( other.myNext )
60{}
61//-----------------------------------------------------------------------------
62template <typename TValue, unsigned int N, unsigned int M>
63DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
64Iterator( 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//-----------------------------------------------------------------------------
118template <typename TValue, unsigned int N, unsigned int M>
119inline
120typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
121DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
122operator=( 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//-----------------------------------------------------------------------------
134template <typename TValue, unsigned int N, unsigned int M>
135inline
136typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Reference
137DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
138operator*() const
139{
140 ASSERT( myValues != 0 );
141 return myValues[ myIdx ];
142}
143//-----------------------------------------------------------------------------
144template <typename TValue, unsigned int N, unsigned int M>
145inline
146typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Pointer
147DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
148operator->() const
149{
150 ASSERT( myValues != 0 );
151 return myValues + myIdx;
152}
153//-----------------------------------------------------------------------------
154template <typename TValue, unsigned int N, unsigned int M>
155inline
156typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
157DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
158operator++()
159{
160 return this->operator+=( 1 );
161}
162//-----------------------------------------------------------------------------
163template <typename TValue, unsigned int N, unsigned int M>
164inline
165typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self
166DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
167operator++( int )
168{
169 Self tmp( *this );
170 this->operator++();
171 return tmp;
172}
173//-----------------------------------------------------------------------------
174template <typename TValue, unsigned int N, unsigned int M>
175inline
176bool
177DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
178operator==( const Self & other ) const
179{
180 return ( myValues == other.myValues ) && ( myIdx == other.myIdx );
181}
182//-----------------------------------------------------------------------------
183template <typename TValue, unsigned int N, unsigned int M>
184inline
185bool
186DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
187operator!=( const Self & other ) const
188{
189 return ( myValues != other.myValues ) || ( myIdx != other.myIdx );
190}
191//-----------------------------------------------------------------------------
192template <typename TValue, unsigned int N, unsigned int M>
193inline
194typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Self &
195DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
196operator+=( 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//-----------------------------------------------------------------------------
215template <typename TValue, unsigned int N, unsigned int M>
216inline
217typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::Reference
218DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator::
219operator[]( DifferenceType n ) const
220{
221 Self tmp( *this );
222 tmp += n;
223 return *tmp;
224}
225
226///////////////////////////////////////////////////////////////////////////////
227// class IndexedListWithBlocks::ConstIterator
228//-----------------------------------------------------------------------------
229template <typename TValue, unsigned int N, unsigned int M>
230DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
231~ConstIterator()
232{}
233//-----------------------------------------------------------------------------
234template <typename TValue, unsigned int N, unsigned int M>
235DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
236ConstIterator()
237 : myIdx( 0 ), myValues( 0 )
238{}
239//-----------------------------------------------------------------------------
240template <typename TValue, unsigned int N, unsigned int M>
241DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
242ConstIterator( const Self & other)
243 : myIdx( other.myIdx ), myNbValues( other.myNbValues ),
244 myValues( other.myValues ), myNext( other.myNext )
245{}
246//-----------------------------------------------------------------------------
247template <typename TValue, unsigned int N, unsigned int M>
248DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
249ConstIterator( 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//-----------------------------------------------------------------------------
303template <typename TValue, unsigned int N, unsigned int M>
304inline
305typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
306DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
307operator=( 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//-----------------------------------------------------------------------------
319template <typename TValue, unsigned int N, unsigned int M>
320inline
321typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Reference
322DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
323operator*() const
324{
325 ASSERT( myValues != 0 );
326 return myValues[ myIdx ];
327}
328//-----------------------------------------------------------------------------
329template <typename TValue, unsigned int N, unsigned int M>
330inline
331typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Pointer
332DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
333operator->() const
334{
335 ASSERT( myValues != 0 );
336 return myValues + myIdx;
337}
338//-----------------------------------------------------------------------------
339template <typename TValue, unsigned int N, unsigned int M>
340inline
341typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
342DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
343operator++()
344{
345 return this->operator+=( 1 );
346}
347//-----------------------------------------------------------------------------
348template <typename TValue, unsigned int N, unsigned int M>
349inline
350typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self
351DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
352operator++( int )
353{
354 Self tmp( *this );
355 this->operator++();
356 return tmp;
357}
358//-----------------------------------------------------------------------------
359template <typename TValue, unsigned int N, unsigned int M>
360inline
361bool
362DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
363operator==( const Self & other ) const
364{
365 return ( myValues == other.myValues ) && ( myIdx == other.myIdx );
366}
367//-----------------------------------------------------------------------------
368template <typename TValue, unsigned int N, unsigned int M>
369inline
370bool
371DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
372operator!=( const Self & other ) const
373{
374 return ( myValues != other.myValues ) || ( myIdx != other.myIdx );
375}
376//-----------------------------------------------------------------------------
377template <typename TValue, unsigned int N, unsigned int M>
378inline
379typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Self &
380DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
381operator+=( 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//-----------------------------------------------------------------------------
400template <typename TValue, unsigned int N, unsigned int M>
401inline
402typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::Reference
403DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator::
404operator[]( DifferenceType n ) const
405{
406 Self tmp( *this );
407 tmp += n;
408 return *tmp;
409}
410
411
412//-----------------------------------------------------------------------------
413template <typename TValue, unsigned int N, unsigned int M>
414inline
415DGtal::IndexedListWithBlocks<TValue, N, M>::
416IndexedListWithBlocks()
417{ // default constructor of myFirstBlock is automatically called.
418}
419//-----------------------------------------------------------------------------
420template <typename TValue, unsigned int N, unsigned int M>
421inline
422DGtal::IndexedListWithBlocks<TValue, N, M>::
423~IndexedListWithBlocks()
424{
425 clear();
426}
427//-----------------------------------------------------------------------------
428template <typename TValue, unsigned int N, unsigned int M>
429inline
430DGtal::IndexedListWithBlocks<TValue, N, M>::
431IndexedListWithBlocks( 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//-----------------------------------------------------------------------------
445template <typename TValue, unsigned int N, unsigned int M>
446inline
447DGtal::IndexedListWithBlocks<TValue, N, M> &
448DGtal::IndexedListWithBlocks<TValue, N, M>::
449operator=( 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//-----------------------------------------------------------------------------
469template <typename TValue, unsigned int N, unsigned int M>
470inline
471void
472DGtal::IndexedListWithBlocks<TValue, N, M>::
473clear()
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//-----------------------------------------------------------------------------
486template <typename TValue, unsigned int N, unsigned int M>
487inline
488typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
489DGtal::IndexedListWithBlocks<TValue, N, M>::
490size() const
491{
492 return myFirstBlock.size;
493}
494//-----------------------------------------------------------------------------
495template <typename TValue, unsigned int N, unsigned int M>
496inline
497bool
498DGtal::IndexedListWithBlocks<TValue, N, M>::
499empty() const
500{
501 return size() == 0;
502}
503//-----------------------------------------------------------------------------
504template <typename TValue, unsigned int N, unsigned int M>
505inline
506typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
507DGtal::IndexedListWithBlocks<TValue, N, M>::
508max_size() const
509{
510 return SizeType( -1 ) / (2*sizeof( Value ));
511}
512//-----------------------------------------------------------------------------
513template <typename TValue, unsigned int N, unsigned int M>
514inline
515typename DGtal::IndexedListWithBlocks<TValue, N, M>::SizeType
516DGtal::IndexedListWithBlocks<TValue, N, M>::
517capacity() const
518{
519 return ( size() <= (N+1) )
520 ? N+1
521 : ( 1 + ( size() - 1 - N ) / M ) * M + N;
522}
523//-----------------------------------------------------------------------------
524template <typename TValue, unsigned int N, unsigned int M>
525inline
526const typename DGtal::IndexedListWithBlocks<TValue, N, M>::Value &
527DGtal::IndexedListWithBlocks<TValue, N, M>::
528operator[]( 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//-----------------------------------------------------------------------------
546template <typename TValue, unsigned int N, unsigned int M>
547inline
548typename DGtal::IndexedListWithBlocks<TValue, N, M>::Value &
549DGtal::IndexedListWithBlocks<TValue, N, M>::
550operator[]( 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//-----------------------------------------------------------------------------
568template <typename TValue, unsigned int N, unsigned int M>
569inline
570void
571DGtal::IndexedListWithBlocks<TValue, N, M>::
572insert( unsigned int idx, const Value & value )
573{
574 ASSERT( idx <= size() ); // end is ok.
575 myFirstBlock.insert( idx, value );
576}
577//-----------------------------------------------------------------------------
578template <typename TValue, unsigned int N, unsigned int M>
579inline
580void
581DGtal::IndexedListWithBlocks<TValue, N, M>::
582erase( unsigned int idx )
583{
584 ASSERT( idx < size() ); // end is not ok.
585 myFirstBlock.erase( idx );
586}
587
588
589//-----------------------------------------------------------------------------
590template <typename TValue, unsigned int N, unsigned int M>
591inline
592typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator
593DGtal::IndexedListWithBlocks<TValue, N, M>::
594begin()
595{
596 return Iterator( myFirstBlock, 0 );
597}
598//-----------------------------------------------------------------------------
599template <typename TValue, unsigned int N, unsigned int M>
600inline
601typename DGtal::IndexedListWithBlocks<TValue, N, M>::Iterator
602DGtal::IndexedListWithBlocks<TValue, N, M>::
603end()
604{
605 return Iterator( myFirstBlock, size() );
606}
607//-----------------------------------------------------------------------------
608template <typename TValue, unsigned int N, unsigned int M>
609inline
610typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator
611DGtal::IndexedListWithBlocks<TValue, N, M>::
612begin() const
613{
614 return ConstIterator( myFirstBlock, 0 );
615}
616//-----------------------------------------------------------------------------
617template <typename TValue, unsigned int N, unsigned int M>
618inline
619typename DGtal::IndexedListWithBlocks<TValue, N, M>::ConstIterator
620DGtal::IndexedListWithBlocks<TValue, N, M>::
621end() 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 */
633template <typename TValue, unsigned int N, unsigned int M>
634inline
635void
636DGtal::IndexedListWithBlocks<TValue, N, M>::
637selfDisplay( 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 */
662template <typename TValue, unsigned int N, unsigned int M>
663inline
664bool
665DGtal::IndexedListWithBlocks<TValue, N, M>::isValid() const
666{
667 return true;
668}
669
670
671
672///////////////////////////////////////////////////////////////////////////////
673// Implementation of inline functions //
674
675template <typename TValue, unsigned int N, unsigned int M>
676inline
677std::ostream&
678DGtal::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
Generated on Sun Nov 27 2022 15:15:35 for DGtal by doxygen 1.9.5