DGtal  1.4.beta
LabelledMap.h
1 
17 #pragma once
18 
31 #if defined(LabelledMap_RECURSES)
32 #error Recursive header files inclusion detected in LabelledMap.h
33 #else // defined(LabelledMap_RECURSES)
35 #define LabelledMap_RECURSES
36 
37 #if !defined LabelledMap_h
39 #define LabelledMap_h
40 
42 // Inclusions
43 #include <cstring>
44 #include <cmath>
45 #include <iostream>
46 #include "DGtal/base/Common.h"
47 #include "DGtal/base/Labels.h"
48 //#include "DGtal/base/FakeKeyValuePair.h"
50 
51 namespace DGtal
52 {
53 
55  // template class LabelledMap
117  template <typename TData, unsigned int L, typename TWord,
118  unsigned int N, unsigned int M>
120  {
124  public:
125  // ----------------------- Public types ------------------------------
127  typedef TData Data;
128  typedef TWord Word;
130  typedef typename LabelsType::Label Label;
131  typedef Label Key;
132  typedef std::pair<const Key, Data> Value;
133  //typedef FakeKeyValuePair<Key, Data> Value;
134 
136  typedef std::ptrdiff_t DifferenceType;
137  typedef std::size_t SizeType;
138  typedef Value& Reference;
139  typedef Value* Pointer;
140  typedef const Value& ConstReference;
141  typedef const Value* ConstPointer;
142 
143  //class Iterator; ///< Forward declaration
144  class ConstIterator;
145  class KeyCompare;
146  class ValueCompare;
147  // ----------------------- Standard types ------------------------------
148  typedef Key key_type;
149  typedef Value value_type;
150  typedef Data data_type;
151  typedef Data mapped_type;
154  typedef Pointer pointer;
162 
163  struct __FirstBlock;
164  struct __AnyBlock;
165 
166  union BlockPointer {
169  };
170 
173  Data lastData; // used when at the end of the list
174  __AnyBlock* nextBlock; // used otherwise
175  };
176 
179  struct __FirstBlock {
180  inline
182  { data.nextBlock = 0; }
183 
184  inline
185  Data & insert( size_t idx, size_t size, const Data & v )
186  {
187  ASSERT( idx <= size );
188  if ( size < N )
189  {
190  std::copy_backward( datas + idx, datas + size, datas + size + 1 );
191  return ( datas[ idx ] = v );
192  }
193  else if ( size == N )
194  {
195  if ( idx < N )
196  {
197  data.lastData = datas[ N - 1 ];
198  std::copy_backward( datas + idx, datas + N - 1, datas + N );
199  return ( datas[ idx ] = v );
200  }
201  else // idx == N
202  {
203  return ( data.lastData = v );
204  }
205  }
206  else if ( size == (N+1) )
207  {
208  // This cannot be tested.
209  // ASSERT( data.nextBlock == 0 );
210  __AnyBlock* next = new __AnyBlock;
211  if ( idx < N )
212  {
213  next->datas[ 0 ] = datas[ N - 1 ];
214  next->datas[ 1 ] = data.lastData;
215  std::copy_backward( datas + idx, datas + N - 1, datas + N );
216  data.nextBlock = next;
217  return ( datas[ idx ] = v );
218  }
219  else if ( idx == N )
220  {
221  next->datas[ 1 ] = data.lastData;
222  data.nextBlock = next;
223  return ( next->datas[ 0 ] = v );
224  }
225  else //if ( idx > N )
226  {
227  next->datas[ 0 ] = data.lastData;
228  data.nextBlock = next;
229  return ( next->datas[ 1 ] = v );
230  }
231  }
232  else // size > N + 1
233  {
234  if ( idx < N )
235  {
236  Data v1 = datas[ N - 1 ];
237  std::copy_backward( datas + idx, datas + N - 1, datas + N );
238  data.nextBlock->insert( 0, size - N, v1 );
239  return ( datas[ idx ] = v );
240  }
241  else
242  return data.nextBlock->insert( idx - N, size - N, v );
243  }
244  }
245 
246  inline
247  void erase( size_t idx, size_t size )
248  {
249  // std::cerr << "__FirstBlock::erase(" << idx << ")"
250  // << " this=" << this
251  // << " next=" << data.nextBlock
252  // << std::endl;
253  ASSERT( idx < size );
254  if ( size <= ( N + 1 ) )
255  {
256  // works also in the case we use 'data' to store a N+1-th data.
257  std::copy( datas + idx + 1, datas + size, datas + idx );
258  data.nextBlock = 0;
259  }
260  else if ( size == N + 2 )
261  {
262  if ( idx < N )
263  {
264  std::copy( datas + idx + 1, datas + N, datas + idx );
265  datas[ N - 1 ] = data.nextBlock->datas[ 0 ];
266  Data tmp = data.nextBlock->datas[ 1 ];
267  delete data.nextBlock;
268  data.lastData = tmp;
269  }
270  else if ( idx == N )
271  {
272  Data tmp = data.nextBlock->datas[ 1 ];
273  delete data.nextBlock;
274  data.lastData = tmp;
275  }
276  else // idx == N + 1
277  {
278  Data tmp = data.nextBlock->datas[ 0 ];
279  delete data.nextBlock;
280  data.lastData = tmp;
281  }
282  }
283  else // size > N + 2
284  {
285  if ( idx < N )
286  {
287  std::copy( datas + idx + 1, datas + N, datas + idx );
288  datas[ N - 1 ] = data.nextBlock->datas[ 0 ];
289  data.nextBlock = data.nextBlock->erase( 0, size - N );
290  }
291  else
292  data.nextBlock = data.nextBlock->erase( idx - N, size - N );
293  }
294  }
295 
296  Data datas[ N ];
298  };
299 
302  struct __AnyBlock {
303  inline __AnyBlock() : next( 0 ) {}
304 
305  inline
306  Data & insert( size_t idx, size_t size, const Data & v )
307  {
308  ASSERT( idx <= size );
309  if ( idx >= M )
310  {
311  if ( next == 0 )
312  {
313  ASSERT( size == M );
314  ASSERT( idx == M );
315  next = new __AnyBlock;
316  return ( next->datas[ 0 ] = v );
317  }
318  else
319  {
320  ASSERT( size > M );
321  return next->insert( idx - M, size - M, v );
322  }
323  }
324  else
325  { // idx < M
326  if ( size <= ( M - 1) ) // ( size < ( M - 1) )
327  {
328  ASSERT( next == 0 );
329  std::copy_backward( datas + idx, datas + size,
330  datas + size + 1 );
331  return ( datas[ idx ] = v );
332  }
333  else
334  {
335  Data v1 = datas[ M - 1 ];
336  std::copy_backward( datas + idx, datas + M - 1, datas + M );
337  // if ( size >= M )
338  // {
339  if ( next == 0 )
340  {
341  ASSERT( size == M );
342  next = new __AnyBlock;
343  next->datas[ 0 ] = v1;
344  }
345  else
346  {
347  ASSERT( size > M );
348  next->insert( 0, size - M, v1 );
349  }
350  // }
351  return ( datas[ idx ] = v );
352  }
353  }
354  }
355 
356  inline
357  __AnyBlock* erase( size_t idx, size_t size )
358  {
359  // std::cerr << "__AnyBlock::erase(" << idx << "," << size << ")"
360  // << " this=" << this
361  // << " next=" << next
362  // << std::endl;
363  if ( size == 1 )
364  {
365  ASSERT( idx == 0 );
366  delete this;
367  return 0;
368  }
369  if ( idx < M )
370  {
371  std::copy( datas + idx + 1, datas + M, datas + idx );
372  if ( next != 0 )
373  {
374  ASSERT( size > M );
375  datas[ M - 1 ] = next->datas[ 0 ];
376  next = next->erase( 0, size - M );
377  }
378  }
379  else
380  next = next->erase( idx - M, size - M );
381  return this;
382  }
383 
384 
385  Data datas[ M ];
387  };
388 
395  public:
397  typedef TData Value;
398  typedef Value* Pointer;
399  typedef Value& Reference;
400  typedef std::ptrdiff_t DifferenceType;
401 
402  // ----------------------- std types ----------------------------------
403  typedef Value value_type;
404  typedef std::size_t size_type;
406  typedef Pointer pointer;
408  //typedef const Reference const_reference;
409  typedef std::forward_iterator_tag iterator_category;
410 
411 
412  protected:
413  unsigned int myIdx;
414  unsigned int myNbDatas;
417 
418  friend class LabelledMap;
419 
420  protected:
424  BlockIterator( __FirstBlock & block, unsigned int idx, unsigned int size );
425 
426  public:
431 
436 
441  BlockIterator( const BlockIterator & other );
442 
448  Self & operator= ( const Self & other );
449 
455 
461 
467 
472  Self operator++( int );
473 
480 
487 
493  bool operator==( const Self & other ) const;
494 
500  bool operator!=( const Self & other ) const;
501 
502 
503  };
504 
505 
512  public:
514  typedef TData Value;
515  typedef const Value* Pointer;
516  typedef const Value& Reference;
517  typedef std::ptrdiff_t DifferenceType;
518 
519  // ----------------------- std types ----------------------------------
520  typedef Value value_type;
521  typedef std::size_t size_type;
523  typedef Pointer pointer;
525  // typedef Reference const_reference;
526  typedef std::forward_iterator_tag iterator_category;
527 
528 
529  protected:
530  unsigned int myIdx;
531  unsigned int myNbDatas;
532  const Data* myDatas;
534 
535  friend class LabelledMap;
536 
537  protected:
542  BlockConstIterator( const __FirstBlock & block, unsigned int idx, unsigned int size );
543 
544  public:
549 
554 
560 
566  Self & operator= ( const Self & other );
567 
573 
579 
585 
590  Self operator++( int );
591 
598 
605 
611  bool operator==( const Self & other ) const;
612 
618  bool operator!=( const Self & other ) const;
619 
620 
621  };
622 
623  // ----------------------- Iterator services ------------------------------
624  public:
625 
630  public:
631  friend class LabelledMap;
633  // The following line is removed so that gcc-4.2 and gcc-4.6 compiles.
634  //typedef typename LabelledMap<TData, L, TWord, N, M>::Value Value;
635  typedef const Value* Pointer;
637  typedef Value Reference;
638  typedef std::ptrdiff_t DifferenceType;
639 
640  // ----------------------- std types ----------------------------------
641  typedef Value value_type;
642  typedef std::size_t size_type;
644  typedef Pointer pointer;
646  // typedef Reference const_reference;
647  typedef std::forward_iterator_tag iterator_category;
648 
649  private:
654 
655  protected:
660 
661  public:
666 
671 
676  ConstIterator( const ConstIterator & other );
677 
683  Self & operator= ( const Self & other );
684 
690 
697 
703 
708  Self operator++( int );
709 
715  bool operator==( const Self & other ) const;
716 
722  bool operator!=( const Self & other ) const;
723 
724 
725  Data & _data() const;
726  const Data & _const_data() const;
727  };
728 
732  class KeyCompare {
733  public:
734  inline KeyCompare() {}
735  inline bool operator()( Key k1, Key k2 ) const
736  {
737  return k1 < k2;
738  }
739  };
741  class ValueCompare {
742  public:
743  inline ValueCompare() {}
744  inline bool operator()( const Value & v1, const Value & v2 ) const
745  {
746  return v1.first < v2.first;
747  }
748  };
749 
750 
751  // ----------------------- Standard services ------------------------------
752  public:
753 
758 
763  LabelledMap ( const LabelledMap & other );
764 
774  template <typename InputIterator>
775  LabelledMap( InputIterator first, InputIterator last );
776 
782  LabelledMap & operator= ( const LabelledMap & other );
783 
788 
789  // ----------------------- Container services -----------------------------
790  public:
791 
795  const LabelsType & labels() const;
796 
800  SizeType size() const;
801 
805  bool empty() const;
806 
811 
816 
821 
826 
840  void swap( Self & other );
841 
845  void clear();
846 
853  SizeType count( const Key & key ) const;
854 
862  Data & operator[]( const Key & key );
863 
871  const Data & operator[]( const Key & key ) const;
872 
879  Data & fastAt( const Key & key );
880 
887  const Data & fastAt( const Key & key ) const;
888 
905  std::pair<Iterator, bool> insert( const Value & val );
906 
920  Iterator insert( Iterator position, const Value & val );
921 
933  template <typename InputIterator>
934  void insert( InputIterator first, InputIterator last );
935 
941  void erase( Iterator position );
942 
950 
960  void erase( Iterator first, Iterator last );
961 
964 
967 
970 
973 
995  std::pair<Iterator, Iterator> equal_range( const Key & x );
996 
1018  std::pair<ConstIterator, ConstIterator> equal_range( const Key & x ) const;
1019 
1037  Iterator find ( const Key & x );
1038 
1056  ConstIterator find ( const Key & x ) const;
1057 
1080  Iterator lower_bound( const Key & x );
1081 
1103  ConstIterator lower_bound ( const Key & x ) const;
1104 
1125  Iterator upper_bound ( const Key & x );
1126 
1147  ConstIterator upper_bound ( const Key & x ) const;
1148 
1149 
1154  void blockClear( size_t size );
1155 
1163  Data & blockAt( size_t idx );
1164 
1172  const Data & blockAt( size_t idx ) const;
1173 
1184  Data & blockInsert( size_t idx, size_t block_size, const Data & data );
1185 
1193  void blockErase( size_t idx );
1194 
1195 
1198 
1201 
1204 
1207 
1208  // ----------------------- Interface --------------------------------------
1209  public:
1210 
1215  void selfDisplay ( std::ostream & out ) const;
1216 
1221  bool isValid() const;
1222 
1223  // ------------------------- Protected Datas ------------------------------
1224  private:
1225  // ------------------------- Private Datas --------------------------------
1226  private:
1227 
1230 
1235 
1236  // ------------------------- Hidden services ------------------------------
1237  protected:
1238 
1239  // ------------------------- Internals ------------------------------------
1240  private:
1241 
1242  }; // end of class LabelledMap
1243 
1244 
1256  template <typename TData, unsigned int L, typename TWord,
1257  unsigned int N, unsigned int M>
1258  std::ostream&
1259  operator<< ( std::ostream & out,
1260  const LabelledMap<TData, L, TWord, N, M> & object );
1261 
1262  namespace detail {
1263 
1269  {
1270  double _p; double _q;
1271  unsigned int _sL;
1272  unsigned int _sV;
1273  unsigned int _sP;
1274  unsigned int _sA;
1275  LabelledMapMemFunctor( double p, double q,
1276  unsigned int sL, unsigned int sV,
1277  unsigned int sP, unsigned int sA )
1278  : _p( p ), _q( q ), _sL( sL ), _sV( sV ), _sP( sP ), _sA( sA )
1279  {}
1280 
1281  inline
1282  double fctNM( unsigned int N, unsigned int M ) const
1283  {
1284  double alpha0 = _sL + _sV * ( N+1 );
1285  double beta0 = _sV * M + _sA + _sP;
1286  return alpha0
1287  + beta0 * _q * pow(1.0 - _p, (double)N+1)
1288  * ( 1.0 + pow(1.0 - _p, (double)M-1 )
1289  / ( 1.0 - pow(1.0 - _p, (double)M ) ) );
1290  }
1291  inline
1292  double fctNMpq( unsigned int N, unsigned int M, double p, double q ) const
1293  {
1294  double alpha0 = _sL + _sV * ( N+1 );
1295  double beta0 = _sV * M + _sA + _sP;
1296  return alpha0
1297  + beta0 * q * pow(1.0 - p, (double)N+1)
1298  * ( 1.0 + pow(1.0 - p, (double)M-1 )
1299  / ( 1.0 - pow(1.0 - p, (double)M ) ) );
1300  }
1301 
1302  };
1303 
1323  template <typename TData>
1324  std::pair< unsigned int, unsigned int >
1326  ( unsigned int L, double prob_no_data, double prob_one_data );
1327  }
1328 
1329 } // namespace DGtal
1330 
1331 
1333 // Includes inline functions.
1334 #include "DGtal/base/LabelledMap.ih"
1335 
1336 // //
1338 
1339 #endif // !defined LabelledMap_h
1340 
1341 #undef LabelledMap_RECURSES
1342 #endif // else defined(LabelledMap_RECURSES)
BlockConstIterator(const __FirstBlock &block, unsigned int idx, unsigned int size)
const __AnyBlock * myNext
pointer to next block or 0 if last block.
Definition: LabelledMap.h:533
unsigned int myNbDatas
number of valid datas in array myDatas
Definition: LabelledMap.h:531
Self & operator+=(DifferenceType n)
unsigned int myIdx
current index in myDatas of the iterator
Definition: LabelledMap.h:530
const Data * myDatas
array of myNbDatas datas.
Definition: LabelledMap.h:532
Self & operator=(const Self &other)
BlockConstIterator(const BlockConstIterator &other)
bool operator!=(const Self &other) const
Reference operator[](DifferenceType n) const
bool operator==(const Self &other) const
std::forward_iterator_tag iterator_category
Definition: LabelledMap.h:526
std::ptrdiff_t DifferenceType
only positive offsets allowed.
Definition: LabelledMap.h:517
std::forward_iterator_tag iterator_category
Definition: LabelledMap.h:409
BlockIterator(__FirstBlock &block, unsigned int idx, unsigned int size)
Reference operator[](DifferenceType n) const
unsigned int myNbDatas
number of valid datas in array myDatas
Definition: LabelledMap.h:414
bool operator!=(const Self &other) const
Self & operator+=(DifferenceType n)
bool operator==(const Self &other) const
unsigned int myIdx
current index in myDatas of the iterator
Definition: LabelledMap.h:413
std::ptrdiff_t DifferenceType
only positive offsets allowed.
Definition: LabelledMap.h:400
Data * myDatas
array of myNbDatas datas.
Definition: LabelledMap.h:415
__AnyBlock * myNext
pointer to next block or 0 if last block.
Definition: LabelledMap.h:416
BlockIterator(const BlockIterator &other)
Self & operator=(const Self &other)
BlockConstIterator myBlockIt
ConstIterator to visit datas.
Definition: LabelledMap.h:653
const Data & _const_data() const
LabelsConstIterator myLabelsIt
ConstIterator to visit keys.
Definition: LabelledMap.h:651
Value Reference
Note the trick here. The reference is a rvalue. Works only for const iterator.
Definition: LabelledMap.h:637
ConstIterator(const ConstIterator &other)
bool operator==(const Self &other) const
Self & operator=(const Self &other)
bool operator!=(const Self &other) const
ConstIterator(LabelsConstIterator lIt, BlockConstIterator bIt)
std::forward_iterator_tag iterator_category
Definition: LabelledMap.h:647
Key comparator class. Always natural ordering.
Definition: LabelledMap.h:732
bool operator()(Key k1, Key k2) const
Definition: LabelledMap.h:735
Value comparator class. Always natural ordering between keys.
Definition: LabelledMap.h:741
bool operator()(const Value &v1, const Value &v2) const
Definition: LabelledMap.h:744
Aim: Represents a map label -> data, where the label is an integer between 0 and a constant L-1....
Definition: LabelledMap.h:120
std::pair< ConstIterator, ConstIterator > equal_range(const Key &x) const
ConstIterator find(const Key &x) const
DifferenceType difference_type
Definition: LabelledMap.h:152
Data & operator[](const Key &key)
BOOST_STATIC_ASSERT(M >=2)
BlockConstIterator blockEnd() const
std::pair< Iterator, bool > insert(const Value &val)
ConstIterator upper_bound(const Key &x) const
LabelledMap< TData, L, TWord, N, M > Self
Definition: LabelledMap.h:126
SizeType count(const Key &key) const
Data & blockAt(size_t idx)
LabelledMap(InputIterator first, InputIterator last)
bool empty() const
const Data & operator[](const Key &key) const
ValueCompare value_compare
Definition: LabelledMap.h:161
const Value & ConstReference
Definition: LabelledMap.h:140
ConstIterator iterator
Definition: LabelledMap.h:158
std::pair< Iterator, Iterator > equal_range(const Key &x)
ValueCompare value_comp() const
void blockErase(size_t idx)
BlockIterator blockEnd()
KeyCompare key_compare
Definition: LabelledMap.h:160
void insert(InputIterator first, InputIterator last)
LabelsType::ConstIterator LabelsConstIterator
Definition: LabelledMap.h:135
Key key_type
Forward declaration.
Definition: LabelledMap.h:146
std::size_t SizeType
Definition: LabelledMap.h:137
ConstIterator begin() const
BOOST_STATIC_ASSERT(N >=0)
BlockConstIterator blockBegin() const
Reference reference
Definition: LabelledMap.h:153
ConstPointer const_pointer
Definition: LabelledMap.h:156
__FirstBlock myFirstBlock
Definition: LabelledMap.h:1234
Iterator find(const Key &x)
LabelledMap(const LabelledMap &other)
ConstReference const_reference
Definition: LabelledMap.h:155
KeyCompare key_comp() const
LabelsType myLabels
Stores the labels for this sequence of datas.
Definition: LabelledMap.h:1229
const Data & fastAt(const Key &key) const
Iterator lower_bound(const Key &x)
const Data & blockAt(size_t idx) const
ConstIterator lower_bound(const Key &x) const
ConstIterator const_iterator
Definition: LabelledMap.h:159
void swap(Self &other)
bool isValid() const
Iterator insert(Iterator position, const Value &val)
void selfDisplay(std::ostream &out) const
Data & blockInsert(size_t idx, size_t block_size, const Data &data)
SizeType size() const
void blockClear(size_t size)
BlockIterator blockBegin()
std::ptrdiff_t DifferenceType
Definition: LabelledMap.h:136
ConstIterator Iterator
non-mutable class via iterators.
Definition: LabelledMap.h:730
SizeType max_size() const
const LabelsType & labels() const
BOOST_STATIC_ASSERT(L >=1)
LabelsType::Label Label
Definition: LabelledMap.h:130
void erase(Iterator first, Iterator last)
ConstIterator end() const
std::pair< const Key, Data > Value
Definition: LabelledMap.h:132
const Value * ConstPointer
Definition: LabelledMap.h:141
SizeType erase(Key key)
SizeType capacity() const
Labels< L, Word > LabelsType
Definition: LabelledMap.h:129
Iterator upper_bound(const Key &x)
LabelledMap & operator=(const LabelledMap &other)
Data & fastAt(const Key &key)
void erase(Iterator position)
unsigned int Label
Definition: Labels.h:80
ConstEnumerator ConstIterator
Definition: Labels.h:197
std::pair< unsigned int, unsigned int > argminLabelledMapMemoryUsageForGeometricDistribution(unsigned int L, double prob_no_data, double prob_one_data)
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(size_t idx, size_t size)
Definition: LabelledMap.h:357
Data & insert(size_t idx, size_t size, const Data &v)
Definition: LabelledMap.h:306
Data & insert(size_t idx, size_t size, const Data &v)
Definition: LabelledMap.h:185
void erase(size_t idx, size_t size)
Definition: LabelledMap.h:247
double fctNM(unsigned int N, unsigned int M) const
Definition: LabelledMap.h:1282
LabelledMapMemFunctor(double p, double q, unsigned int sL, unsigned int sV, unsigned int sP, unsigned int sA)
Definition: LabelledMap.h:1275
double fctNMpq(unsigned int N, unsigned int M, double p, double q) const
Definition: LabelledMap.h:1292
Used in first block to finish it or to point to the next block.
Definition: LabelledMap.h:172