DGtal 1.3.0
Loading...
Searching...
No Matches
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
51namespace 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;
162
163 struct __FirstBlock;
164 struct __AnyBlock;
165
169 };
170
173 Data lastData; // used when at the end of the list
174 __AnyBlock* nextBlock; // used otherwise
175 };
176
180 inline
182 { data.nextBlock = 0; }
183
184 inline
185 Data & insert( unsigned int idx, unsigned int 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( unsigned int idx, unsigned int 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
298 };
299
302 struct __AnyBlock {
303 inline __AnyBlock() : next( 0 ) {}
304
305 inline
306 Data & insert( unsigned int idx, unsigned int 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( unsigned int idx, unsigned int 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
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 ----------------------------------
404 typedef std::size_t size_type;
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
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 ----------------------------------
521 typedef std::size_t size_type;
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
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;
638 typedef std::ptrdiff_t DifferenceType;
639
640 // ----------------------- std types ----------------------------------
642 typedef std::size_t size_type;
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
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
733 public:
734 inline KeyCompare() {}
735 inline bool operator()( Key k1, Key k2 ) const
736 {
737 return k1 < k2;
738 }
739 };
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
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
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
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
BlockConstIterator(const BlockConstIterator &other)
Self & operator+=(DifferenceType n)
bool operator!=(const Self &other) const
Self & operator=(const Self &other)
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
Self & operator=(const Self &other)
BlockIterator(const BlockIterator &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
Data & blockAt(size_t idx)
ConstIterator find(const Key &x) const
DifferenceType difference_type
Definition: LabelledMap.h:152
BOOST_STATIC_ASSERT(M >=2)
BlockConstIterator blockEnd() const
ConstIterator upper_bound(const Key &x) const
LabelledMap< TData, L, TWord, N, M > Self
Definition: LabelledMap.h:126
SizeType count(const Key &key) const
LabelledMap(InputIterator first, InputIterator last)
bool empty() const
ValueCompare value_compare
Definition: LabelledMap.h:161
const Value & ConstReference
Definition: LabelledMap.h:140
const Data & operator[](const Key &key) const
ConstIterator iterator
Definition: LabelledMap.h:158
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:148
std::size_t SizeType
Definition: LabelledMap.h:137
ConstIterator begin() const
const LabelsType & labels() const
BOOST_STATIC_ASSERT(N >=0)
BlockConstIterator blockBegin() const
Reference reference
Definition: LabelledMap.h:153
ConstPointer const_pointer
Definition: LabelledMap.h:156
Data & blockInsert(size_t idx, size_t block_size, const Data &data)
__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
Iterator lower_bound(const Key &x)
std::pair< Iterator, Iterator > equal_range(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
LabelledMap & operator=(const LabelledMap &other)
const Data & fastAt(const Key &key) const
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
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
std::pair< Iterator, bool > insert(const Value &val)
Data & operator[](const Key &key)
const Value * ConstPointer
Definition: LabelledMap.h:141
SizeType erase(Key key)
SizeType capacity() const
Labels< L, Word > LabelsType
Definition: LabelledMap.h:129
std::pair< ConstIterator, ConstIterator > equal_range(const Key &x) const
Iterator upper_bound(const Key &x)
Data & fastAt(const Key &key)
void erase(Iterator position)
Aim: Stores a set of labels in {O..L-1} as a sequence of bits.
Definition: Labels.h:72
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 ClosedIntegerHalfPlane< TSpace > &object)
Data & insert(unsigned int idx, unsigned int size, const Data &v)
Definition: LabelledMap.h:306
__AnyBlock * erase(unsigned int idx, unsigned int size)
Definition: LabelledMap.h:357
void erase(unsigned int idx, unsigned int size)
Definition: LabelledMap.h:247
Data & insert(unsigned int idx, unsigned int size, const Data &v)
Definition: LabelledMap.h:185
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