DGtal  1.5.beta
IndexedListWithBlocks.h
1 
17 #pragma once
18 
31 #if defined(IndexedListWithBlocks_RECURSES)
32 #error Recursive header files inclusion detected in IndexedListWithBlocks.h
33 #else // defined(IndexedListWithBlocks_RECURSES)
35 #define IndexedListWithBlocks_RECURSES
36 
37 #if !defined IndexedListWithBlocks_h
39 #define IndexedListWithBlocks_h
40 
42 // Inclusions
43 #include <cstring>
44 #include <iostream>
45 #include "DGtal/base/Common.h"
47 
48 namespace DGtal
49 {
50 
52  // template class IndexedListWithBlocks
92  template <typename TValue, unsigned int N, unsigned int M>
94  {
97  public:
98  // ----------------------- Public types ------------------------------
99  typedef TValue Value;
100  typedef std::ptrdiff_t DifferenceType;
101  typedef std::size_t SizeType;
102  typedef Value& Reference;
103  typedef Value* Pointer;
104  typedef const Value& ConstReference;
105  typedef const Value* ConstPointer;
106 
107  class Iterator;
108  class ConstIterator;
109 
110  // ----------------------- Standard types ------------------------------
111  typedef Value value_type;
114  typedef Pointer pointer;
120 
121  struct FirstBlock;
122  struct AnyBlock;
123 
124  union BlockPointer {
127  };
128 
131  Value lastValue; // used when at the end of the list
132  AnyBlock* nextBlock; // used otherwise
133  };
134 
137  struct FirstBlock {
138  inline
139  FirstBlock() : size( 0 )
140  { data.nextBlock = 0; }
141 
142  inline
143  void insert( unsigned int idx, const Value & v )
144  {
145  if ( size <= N )
146  {
147  ASSERT( idx <= size );
148  // works also in the case we use 'data' to store a N+1-th value.
149  std::copy_backward( values + idx, values + size, values + size + 1 );
150  values[ idx ] = v;
151  }
152  else if ( size == (N+1) )
153  {
154  ASSERT( idx <= size );
155  // This cannot be tested.
156  // ASSERT( data.nextBlock == 0 );
157  AnyBlock* next = new AnyBlock;
158  if ( idx < N )
159  {
160  next->values[ 0 ] = values[ N - 1 ];
161  next->values[ 1 ] = data.lastValue;
162  std::copy_backward( values + idx, values + N - 1, values + N );
163  values[ idx ] = v;
164  }
165  else if ( idx == N )
166  {
167  next->values[ 0 ] = v;
168  next->values[ 1 ] = data.lastValue;
169  }
170  else if ( idx > N )
171  {
172  next->values[ 0 ] = data.lastValue;
173  next->values[ 1 ] = v;
174  }
175  data.nextBlock = next;
176  }
177  else // size > N + 1
178  {
179  if ( idx < N )
180  {
181  Value v1 = values[ N - 1 ];
182  std::copy_backward( values + idx, values + N - 1, values + N );
183  data.nextBlock->insert( 0, size - N, v1 );
184  values[ idx ] = v;
185  }
186  else
187  data.nextBlock->insert( idx - N, size - N, v );
188  }
189  ++size;
190  }
191 
192  inline
193  void erase( unsigned int idx )
194  {
195  // std::cerr << "FirstBlock::erase(" << idx << ")"
196  // << " this=" << this
197  // << " next=" << data.nextBlock
198  // << std::endl;
199  ASSERT( idx < size );
200  if ( size <= ( N + 1 ) )
201  {
202  // works also in the case we use 'data' to store a N+1-th value.
203  std::copy( values + idx + 1, values + size, values + idx );
204  data.nextBlock = 0;
205  }
206  else if ( size == N + 2 )
207  {
208  if ( idx < N )
209  {
210  std::copy( values + idx + 1, values + N, values + idx );
211  values[ N - 1 ] = data.nextBlock->values[ 0 ];
212  Value tmp = data.nextBlock->values[ 1 ];
213  delete data.nextBlock;
214  data.lastValue = tmp;
215  }
216  else if ( idx == N )
217  {
218  Value tmp = data.nextBlock->values[ 1 ];
219  delete data.nextBlock;
220  data.lastValue = tmp;
221  }
222  else // idx == N + 1
223  {
224  Value tmp = data.nextBlock->values[ 0 ];
225  delete data.nextBlock;
226  data.lastValue = tmp;
227  }
228  }
229  else // size > N + 2
230  {
231  if ( idx < N )
232  {
233  std::copy( values + idx + 1, values + N, values + idx );
234  values[ N - 1 ] = data.nextBlock->values[ 0 ];
235  data.nextBlock = data.nextBlock->erase( 0, size - N );
236  }
237  else
238  data.nextBlock = data.nextBlock->erase( idx - N, size - N );
239  }
240  --size;
241  }
242 
243  unsigned int size;
244  Value values[ N ];
246  };
247 
250  struct AnyBlock {
251  inline AnyBlock() : next( 0 ) {}
252 
253  inline
254  void insert( unsigned int idx, unsigned int size, const Value & v )
255  {
256  ASSERT( idx <= size );
257  if ( idx >= M )
258  {
259  if ( next == 0 )
260  {
261  ASSERT( idx == M );
262  next = new AnyBlock;
263  next->values[ 0 ] = v;
264  }
265  else
266  next->insert( idx - M, size - M, v );
267  }
268  else
269  { // idx < M
270  if ( size < ( M - 1) )
271  {
272  std::copy_backward( values + idx, values + size,
273  values + size + 1 );
274  values[ idx ] = v;
275  }
276  else
277  {
278  Value v1 = values[ M - 1 ];
279  std::copy_backward( values + idx, values + M - 1, values + M );
280  values[ idx ] = v;
281  if ( size >= M )
282  {
283  if ( next == 0 )
284  {
285  ASSERT( size == M );
286  next = new AnyBlock;
287  next->values[ 0 ] = v1;
288  }
289  else
290  next->insert( 0, size - M, v1 );
291  }
292  }
293  }
294  }
295 
296  inline
297  AnyBlock* erase( unsigned int idx, unsigned int size )
298  {
299  // std::cerr << "AnyBlock::erase(" << idx << "," << size << ")"
300  // << " this=" << this
301  // << " next=" << next
302  // << std::endl;
303  if ( size == 1 )
304  {
305  ASSERT( idx == 0 );
306  delete this;
307  return 0;
308  }
309  if ( idx < M )
310  {
311  std::copy( values + idx + 1, values + M, values + idx );
312  if ( next != 0 )
313  {
314  ASSERT( size > M );
315  values[ M - 1 ] = next->values[ 0 ];
316  next = next->erase( 0, size - M );
317  }
318  }
319  else
320  next = next->erase( idx - M, size - M );
321  return this;
322  }
323 
324 
325  Value values[ M ];
327  };
328 
334  class Iterator {
335  public:
336  typedef Iterator Self;
337  typedef TValue Value;
338  typedef Value* Pointer;
339  typedef Value& Reference;
340  typedef std::ptrdiff_t DifferenceType;
341 
342  // ----------------------- std types ----------------------------------
343  typedef Value value_type;
344  typedef std::size_t size_type;
346  typedef Pointer pointer;
348  //typedef const Reference const_reference;
349  typedef std::forward_iterator_tag iterator_category;
350 
351 
352  protected:
353  unsigned int myIdx;
354  unsigned int myNbValues;
357 
358  friend class IndexedListWithBlocks;
359 
360  protected:
364  Iterator( FirstBlock & block, unsigned int idx );
365 
366  public:
371 
376 
381  Iterator( const Iterator & other );
382 
388  Self & operator= ( const Self & other );
389 
395 
401 
407 
412  Self operator++( int );
413 
420 
427 
433  bool operator==( const Self & other ) const;
434 
440  bool operator!=( const Self & other ) const;
441 
442 
443  };
444 
445 
452  public:
454  typedef TValue Value;
455  typedef const Value* Pointer;
456  typedef const Value& Reference;
457  typedef std::ptrdiff_t DifferenceType;
458 
459  // ----------------------- std types ----------------------------------
460  typedef Value value_type;
461  typedef std::size_t size_type;
463  typedef Pointer pointer;
465  // typedef Reference const_reference;
466  typedef std::forward_iterator_tag iterator_category;
467 
468 
469  protected:
470  unsigned int myIdx;
471  unsigned int myNbValues;
472  const Value* myValues;
473  const AnyBlock* myNext;
474 
475  friend class IndexedListWithBlocks;
476 
477  protected:
482  ConstIterator( const FirstBlock & block, unsigned int idx );
483 
484  public:
489 
494 
499  ConstIterator( const ConstIterator & other );
500 
506  Self & operator= ( const Self & other );
507 
513 
519 
525 
530  Self operator++( int );
531 
538 
545 
551  bool operator==( const Self & other ) const;
552 
558  bool operator!=( const Self & other ) const;
559 
560 
561  };
562 
563 
564  // ----------------------- Standard services ------------------------------
565  public:
566 
571 
577 
584 
589 
590  // ----------------------- Container services -----------------------------
591  public:
592 
596  SizeType size() const;
597 
601  bool empty() const;
602 
607 
612 
617  void clear();
618 
626  Value & operator[]( unsigned int idx );
627 
635  const Value & operator[]( unsigned int idx ) const;
636 
646  void insert( unsigned int idx, const Value & value );
647 
655  void erase( unsigned int idx );
656 
661 
666 
671 
676 
677  // ----------------------- Interface --------------------------------------
678  public:
679 
684  void selfDisplay ( std::ostream & out ) const;
685 
690  bool isValid() const;
691 
692  // ------------------------- Protected Datas ------------------------------
693  private:
694  // ------------------------- Private Datas --------------------------------
695  private:
696 
701 
702  // ------------------------- Hidden services ------------------------------
703  protected:
704 
705  // ------------------------- Internals ------------------------------------
706  private:
707 
708  }; // end of class IndexedListWithBlocks
709 
710 
722  template <typename TValue, unsigned int N, unsigned int M>
723  std::ostream&
724  operator<< ( std::ostream & out,
725  const IndexedListWithBlocks<TValue, N, M> & object );
726 
727 } // namespace DGtal
728 
729 
731 // Includes inline functions.
732 #include "DGtal/base/IndexedListWithBlocks.ih"
733 
734 // //
736 
737 #endif // !defined IndexedListWithBlocks_h
738 
739 #undef IndexedListWithBlocks_RECURSES
740 #endif // else defined(IndexedListWithBlocks_RECURSES)
bool operator!=(const Self &other) const
ConstIterator(const ConstIterator &other)
ConstIterator(const FirstBlock &block, unsigned int idx)
std::ptrdiff_t DifferenceType
only positive offsets allowed.
const AnyBlock * myNext
pointer to next block or 0 if last block.
bool operator==(const Self &other) const
const Value * myValues
array of myNbValues values.
unsigned int myIdx
current index in myValues of the iterator
unsigned int myNbValues
number of valid values in array myValues
Reference operator[](DifferenceType n) const
unsigned int myIdx
current index in myValues of the iterator
Value * myValues
array of myNbValues values.
Self & operator=(const Self &other)
AnyBlock * myNext
pointer to next block or 0 if last block.
bool operator==(const Self &other) const
std::ptrdiff_t DifferenceType
only positive offsets allowed.
unsigned int myNbValues
number of valid values in array myValues
Self & operator+=(DifferenceType n)
Iterator(FirstBlock &block, unsigned int idx)
Reference operator[](DifferenceType n) const
bool operator!=(const Self &other) const
Aim: Represents a mixed list/array structure which is useful in some context. It is essentially a lis...
void insert(unsigned int idx, const Value &value)
Value & operator[](unsigned int idx)
IndexedListWithBlocks & operator=(const IndexedListWithBlocks &other)
void erase(unsigned int idx)
const Value & operator[](unsigned int idx) const
IndexedListWithBlocks(const IndexedListWithBlocks &other)
ConstIterator begin() const
ConstIterator end() const
void selfDisplay(std::ostream &out) const
DGtal is the top-level namespace which contains all DGtal functions and types.
std::ostream & operator<<(std::ostream &out, const ATu0v1< TKSpace, TLinearAlgebra > &object)
AnyBlock * erase(unsigned int idx, unsigned int size)
void insert(unsigned int idx, unsigned int size, const Value &v)
void insert(unsigned int idx, const Value &v)
Used in blocks to finish it or to point to the next block.