DGtal  1.1.0
UnorderedSetByBlock.h
1 
17 #pragma once
18 
26 #ifndef UNORDEREDSETBYBLOCK_HPP
27 #define UNORDEREDSETBYBLOCK_HPP
28 
29 #include <unordered_map>
30 #include <boost/iterator/iterator_facade.hpp>
31 #include <climits>
32 #include "DGtal/base/Common.h"
33 #include "DGtal/base/Bits.h"
34 #include "DGtal/kernel/CUnsignedNumber.h"
35 #include "DGtal/kernel/CBoundedNumber.h"
36 #include "DGtal/kernel/PointVector.h"
37 #include "DGtal/kernel/PointHashFunctions.h"
38 
39 namespace DGtal
40 {
41 
66  template < typename TElement, typename TWord = uint32_t >
67  struct Splitter {
69  typedef TElement Element;
70  typedef TWord Word;
71  typedef typename Element::Coordinate Coordinate;
72 
75 
83  static
84  std::pair< Element, Coordinate >
86  {
87  auto block_coords =
88  ( e[ 0 ] & static_cast<Coordinate>( sizeof( Word ) * CHAR_BIT - 1 ) );
89  e[ 0 ] -= block_coords;
90  return { e, block_coords };
91  }
92 
99  static
100  Element
102  {
103  e[ 0 ] |= x;
104  return e;
105  }
106 
113  static
114  Element
115  join( const std::pair< Element, Coordinate >& p )
116  {
117  Element ge = p.first;
118  ge[ 0 ] |= p.second;
119  return ge;
120  }
121  };
122 
123 
155  template < typename Key,
156  typename TSplitter = Splitter< Key >,
157  class Hash = std::hash<Key>,
158  class KeyEqual = std::equal_to<Key>,
159  class UnorderedMapAllocator = std::allocator<
160  std::pair<const Key, typename TSplitter::Word >
161  >
162  >
165  typedef TSplitter Splitter;
166  typedef typename Splitter::Word Word;
169  typedef std::unordered_map< Key, Word, Hash, KeyEqual,
170  UnorderedMapAllocator > Container;
171 
172  // Standard types
174  typedef Key key_type;
176  typedef Key value_type;
178  typedef typename Container::size_type size_type;
180  typedef typename Container::difference_type difference_type;
182  typedef Hash hasher;
184  typedef KeyEqual key_equal;
186  typedef typename Container::allocator_type allocator_type;
188  typedef Key& reference;
190  typedef const Key& const_reference;
192  typedef Key* pointer;
194  typedef const Key* const_pointer;
195 
196  public:
197  // ---------------------- iterators --------------------------------
198 
201  : public boost::iterator_facade< const_iterator, Key const,
202  boost::forward_traversal_tag,
203  Key const >
204  {
205  friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
207  const_iterator() : collection( nullptr ), it(),
208  bit( static_cast<Coordinate>(0) ),
209  current( static_cast<Word>(0) ) {}
210 
214  const_iterator( const Self& aSet, typename Container::const_iterator anIt )
215  : collection( &aSet ), it( anIt )
216  {
217  if ( it != collection->my_elements.cend() )
218  {
219  current = it->second;
220  bit = static_cast<Coordinate>( Bits::leastSignificantBit( current ) );
221  }
222  else
223  {
224  current = static_cast<Word>(0);
225  bit = static_cast<Coordinate>(0);
226  }
227  }
228 
233  const_iterator( const Self& aSet, typename Container::const_iterator anIt,
234  Coordinate aBit )
235  : collection( &aSet ), it( anIt ), bit( aBit )
236  {
237  if ( it != collection->my_elements.cend() )
238  {
239  current = it->second;
240  current &= ~( ( static_cast<Word>(1) << bit ) - static_cast<Word>(1) );
241  }
242  else
243  current = static_cast<Word>(0);
244  }
245 
249  const_iterator( const Self& aSet, const Key& key )
250  : collection( &aSet )
251  {
252  auto se = collection->my_splitter.split( key );
253  it = collection->my_elements.find( se.first );
254  if ( it != collection->my_elements.cend() )
255  {
256  bit = se.second;
257  current = it->second & ~( (static_cast<Word>(1) << bit )
258  - static_cast<Word>(1) );
259  }
260  else
261  {
262  bit = static_cast<Coordinate>(0);
263  current = static_cast<Word>(0);
264  }
265  }
266 
267  private:
269  void increment()
270  {
271  ASSERT( current != static_cast<Word>(0)
272  && "Invalid increment on const_iterator" );
273  current &= ~( static_cast<Word>(1) << bit );
274  if ( current == static_cast<Word>(0) )
275  {
276  ++it;
277  if ( it != collection->my_elements.cend() )
278  {
279  current = it->second;
280  bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
281  }
282  else
283  {
284  current = static_cast<Word>(0);
285  bit = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
286  }
287  }
288  else
289  bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
290  }
291 
292  bool equal( const const_iterator & other ) const
293  {
294  ASSERT( collection == other.collection );
295  return it == other.it && bit == other.bit;
296  }
297 
298  const Key dereference() const
299  {
300  return collection->my_splitter.join( it->first, bit );
301  }
302 
304  const Self* collection;
306  typename Container::const_iterator it;
311 
312  };
313 
315  struct iterator
316  : public boost::iterator_facade< iterator, Key const,
317  boost::forward_traversal_tag,
318  Key const >
319  {
320  friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
322  iterator() : collection( nullptr ), it(),
323  bit( static_cast<Coordinate>(0) ),
324  current( static_cast<Word>(0) ) {}
325 
329  iterator( Self& aSet, typename Container::iterator anIt )
330  : collection( &aSet ), it( anIt )
331  {
332  if ( it != collection->my_elements.end() )
333  {
334  current = it->second;
335  bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
336  }
337  else
338  {
339  current = static_cast<Word>(0);
340  bit = static_cast<Coordinate>(0);
341  }
342  }
343 
348  iterator( Self& aSet, typename Container::iterator anIt, Coordinate aBit )
349  : collection( &aSet ), it( anIt ), bit( aBit )
350  {
351  if ( it != collection->my_elements.end() )
352  {
353  current = it->second;
354  current &= ~( ( static_cast<Word>(1) << bit )
355  - static_cast<Word>(1) );
356  }
357  else
358  current = static_cast<Word>(0);
359  }
360 
366  iterator( Self& aSet, const Key& key )
367  : collection( &aSet )
368  {
369  auto se = collection->my_splitter.split( key );
370  it = collection->my_elements.find( se.first );
371  if ( it != collection->my_elements.end() )
372  {
373  bit = se.second;
374  current = it->second & ~( (static_cast<Word>(1) << bit )
375  - static_cast<Word>(1) );
376  }
377  else
378  {
379  bit = static_cast<Coordinate>(0);
380  current = static_cast<Word>(0);
381  }
382  }
383 
386  iterator( const const_iterator& other )
387  : collection( other.collection ), it( other.it ),
388  bit( other.bit ), current( other.current )
389  {}
390 
394  : collection( std::move( other.collection ) ),
395  it( std::move( other.it ) ),
396  bit( std::move( other.bit ) ),
397  current( std::move( other.current ) )
398  {}
399 
402  operator const_iterator() const
403  {
404  return const_iterator( *collection, it, bit );
405  }
406 
407  private:
409  void increment()
410  {
411  ASSERT( current != static_cast<Word>(0)
412  && "Invalid increment on iterator" );
413  current &= ~( static_cast<Word>(1) << bit );
414  if ( current == static_cast<Word>(0) )
415  {
416  ++it;
417  if ( it != collection->my_elements.end() )
418  {
419  current = it->second;
420  bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
421  }
422  else
423  {
424  current = static_cast<Word>(0);
425  bit = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
426  }
427  }
428  else
429  bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
430  }
431 
432  bool equal( const iterator & other ) const
433  {
434  ASSERT( collection == other.collection );
435  return it == other.it && bit == other.bit;
436  }
437 
438  // The equality comparator with const_iterator must also be
439  // provided to respect the standard that says that iterator and
440  // const_iterator should always be comparable.
441  bool equal( const const_iterator & other ) const
442  {
443  ASSERT( collection == other.collection );
444  return it == other.it && bit == other.bit;
445  }
446 
447  const Key dereference() const
448  {
449  return collection->my_splitter.join( it->first, bit );
450  }
451 
455  typename Container::iterator it;
460 
461  };
462 
463  // ------------------------- standard services ----------------------------------
466  public:
467 
474  UnorderedSetByBlock( size_type bucket_count = 23,
475  const Splitter & splitter = Splitter(),
476  const Hash& hash = Hash(),
477  const key_equal& equal = key_equal(),
478  const UnorderedMapAllocator& alloc = UnorderedMapAllocator())
479  : my_splitter( splitter ),
480  my_elements( bucket_count, hash, equal, alloc ),
481  my_size( 0 ) {}
482 
484  ~UnorderedSetByBlock() = default;
485 
488  UnorderedSetByBlock( const Self& other )
489  : my_splitter( other.my_splitter ),
490  my_elements( other.my_elements ),
491  my_size( other.my_size )
492  {}
493 
497  : my_splitter( std::move( other.my_splitter ) ),
498  my_elements( std::move( other.my_elements ) ),
499  my_size( std::move( other.my_size ) )
500  {}
501 
505  Self& operator=( const Self& other )
506  {
507  if ( this != &other )
508  {
509  my_splitter = other.my_splitter;
510  my_elements = other.my_elements;
511  my_size = other.my_size;
512  }
513  return *this;
514  }
518  Self& operator=( Self&& other )
519  {
520  my_splitter = std::move( other.my_splitter );
521  my_elements = std::move( other.my_elements );
522  my_size = std::move( other.my_size );
523  return *this;
524  }
525 
527 
528  // ---------------------- iterator services -----------------------------
531  public:
532 
534  iterator begin()
535  {
536  return iterator( *this, my_elements.begin() );
537  }
539  iterator end()
540  {
541  return iterator( *this, my_elements.end() );
542  }
543 
545  const_iterator begin() const
546  {
547  return const_iterator( *this, my_elements.cbegin() );
548  }
550  const_iterator end() const
551  {
552  return const_iterator( *this, my_elements.cend() );
553  }
554 
556  const_iterator cbegin() const
557  {
558  return const_iterator( *this, my_elements.cbegin() );
559  }
561  const_iterator cend() const
562  {
563  return const_iterator( *this, my_elements.cend() );
564  }
565 
567 
568  // ---------------------- capacity services -----------------------------
571  public:
572 
574  bool empty() const noexcept { return my_elements.empty(); }
576  size_type size() const noexcept { return my_size; }
578  size_type max_size() const noexcept { return my_elements.max_size(); }
579 
582  size_type blocks() const noexcept { return my_elements.size(); }
583 
586  size_type memory_usage() const noexcept
587  {
588  size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
589  + 2 * sizeof( size_type );
590  mem += blocks() * ( sizeof( void* ) /* next */
591  + sizeof( Key ) /* key */
592  + sizeof( Word ) /* value */
593  + sizeof( size_type ) /* hash */
594  + sizeof( void* ) /* dyn. alloc. */ );
595  return mem;
596  }
597 
602  {
603  size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
604  + 2 * sizeof( size_type );
605  mem += size() * ( sizeof( void* ) /* next */
606  + sizeof( Key ) /* key */
607  + sizeof( size_type ) /* hash */
608  + sizeof( void* ) /* dyn. alloc. */ );
609  return mem;
610  }
611 
613 
614  // ---------------------- modifier services -----------------------------
617  public:
618 
620  void clear() noexcept
621  {
622  my_elements.clear();
623  my_size = 0;
624  }
625 
636  void swap( Self& other ) noexcept
637  {
638  std::swap( my_splitter, other.my_splitter );
639  std::swap( my_elements, other.my_elements );
640  std::swap( my_size, other.my_size );
641  }
642 
656  std::pair<iterator,bool> insert( const value_type& value )
657  {
658  const auto se = my_splitter.split( value );
659  auto it = my_elements.find( se.first );
660  if ( it == my_elements.end() )
661  {
662  auto p = my_elements.insert
663  ( std::make_pair( se.first,
664  static_cast<Word>(1) << se.second ) );
665  my_size += 1;
666  return std::make_pair( iterator( *this, p.first, se.second ), true );
667  }
668  else
669  {
670  bool exist = it->second & ( static_cast<Word>(1) << se.second );
671  if ( ! exist )
672  {
673  it->second |= static_cast<Word>(1) << se.second;
674  my_size += 1;
675  }
676  return std::make_pair( iterator( *this, it, se.second ), ! exist );
677  }
678  }
679 
693  template<typename... _Args>
694  std::pair<iterator, bool>
695  emplace(_Args&&... __args)
696  {
697  const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
698  auto it = my_elements.find( se.first );
699  if ( it == my_elements.end() )
700  {
701  auto p =
702  my_elements.insert( std::make_pair( se.first,
703  static_cast<Word>(1) << se.second ) );
704  my_size += 1;
705  return std::make_pair( iterator( *this, p.first, se.second ), true );
706  }
707  else
708  {
709  bool exist = it->second & ( static_cast<Word>(1) << se.second );
710  if ( ! exist )
711  {
712  it->second |= static_cast<Word>(1) << se.second;
713  my_size += 1;
714  }
715  return std::make_pair( iterator( *this, it, se.second ), ! exist );
716  }
717  }
718 
730  iterator erase( const_iterator pos ) noexcept
731  {
732  ASSERT( this == pos.collection );
733  ASSERT( pos != cend() );
734  ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
735  != static_cast<Word>(0) );
736  my_size -= 1;
737  Word & w = const_cast< Word& >( pos.it->second );
738  if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
739  == static_cast<Word>(0) )
740  return iterator( *this, my_elements.erase( pos.it ) );
741  else
742  return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
743  }
744 
760  iterator erase( const_iterator first, const_iterator last ) noexcept
761  {
762  ASSERT( this == first.collection );
763  ASSERT( this == last.collection );
764  if ( first == cend() ) return end();
765  auto itB = first.it;
766  auto itE = last.it;
767  Word mask = static_cast<Word>(0);
768  // Take care of range over one block only
769  if ( itB == itE )
770  {
771  while ( first != last )
772  {
773  mask |= static_cast<Word>(1) << first.bit;
774  my_size -= 1;
775  ++first;
776  }
777  my_elements[ itB->first ] &= ~mask;
778  return iterator( *this,
779  my_elements.find( itE->first ),
780  last.bit ); // must be valid
781  }
782  // Take care of first element.
783  while ( first.it == itB )
784  {
785  mask |= static_cast<Word>(1) << first.bit;
786  my_size -= 1;
787  ++first;
788  }
789  // Erase first block if empty
790  if ( ( my_elements[ itB->first ] &= ~mask )
791  == static_cast<Word>(0) )
792  my_elements.erase( itB );
793  // Count erased elements in main range.
794  for ( itB = first.it; itB != itE; ++itB )
795  my_size -= Bits::nbSetBits( itB->second );
796  // Erase elements in main range
797  my_elements.erase( first.it, itE );
798  // Take care of last element.
799  if ( itE == my_elements.cend() ) return end();
800  itB = itE;
801  first = const_iterator( *this, itB );
802  mask = static_cast<Word>(0);
803  while ( first != last )
804  {
805  mask |= static_cast<Word>(1) << first.bit;
806  my_size -= 1;
807  ++first;
808  }
809  // Erase last block if empty
810  if ( ( my_elements[ itB->first ] &= ~mask )
811  == static_cast<Word>(0) )
812  my_elements.erase( itB );
813  return iterator( *this,
814  my_elements.find( itE->first ),
815  last.bit ); // must be valid or end.
816  }
817 
825  size_type erase( const key_type& key )
826  {
827  auto it = find( key );
828  if ( it != end() )
829  {
830  erase( it );
831  return 1;
832  }
833  else return 0;
834  }
835 
837 
838  // ---------------------- lookup services -----------------------------
841  public:
842 
848  iterator find( const Key& key )
849  {
850  const auto se = my_splitter.split( key );
851  const auto it = my_elements.find( se.first );
852  if ( it == my_elements.end() ) return end();
853  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
854  if ( exist ) return iterator( *this, it, se.second );
855  else return end();
856  }
857 
863  const_iterator find( const Key& key ) const
864  {
865  const auto se = my_splitter.split( key );
866  const auto it = my_elements.find( se.first );
867  if ( it == my_elements.cend() ) return cend();
868  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
869  if ( exist ) return const_iterator( *this, it, se.second );
870  else return cend();
871  }
872 
877  size_type count( const Key& key ) const
878  {
879  const auto se = my_splitter.split( key );
880  const auto it = my_elements.find( se.first );
881  if ( it == my_elements.cend() ) return 0;
882  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
883  return exist ? 1 : 0;
884  }
885 
894  std::pair<iterator,iterator>
895  equal_range( const Key & key )
896  {
897  iterator first = find( key );
898  if ( first != end() )
899  {
900  iterator last = first;
901  return std::make_pair( first, ++last );
902  }
903  else return std::make_pair( first, first );
904  }
905 
914  std::pair<const_iterator,const_iterator>
915  equal_range( const Key & key ) const
916  {
917  const_iterator first = find( key );
918  if ( first != end() )
919  {
920  const_iterator last = first;
921  return std::make_pair( first, ++last );
922  }
923  else return std::make_pair( first, first );
924  }
925 
927 
928  // ---------------------- set services -------------------------
931  public:
932 
939  bool includes( const Self& other ) const
940  {
941  return internal_includes_by_map_iterator( other );
942  }
943 
944  protected:
949  bool internal_includes_by_map_iterator( const Self& other ) const
950  {
951  auto itMap_other = other.my_elements.cbegin();
952  const auto itEndMap_other = other.my_elements.cend();
953  const auto itEndMap_this = my_elements.cend();
954  for ( ; itMap_other != itEndMap_other; ++itMap_other )
955  {
956  const auto itMap_this = my_elements.find( itMap_other->first );
957  if ( itMap_this == itEndMap_this ) return false;
958  const Word w_this = itMap_this->second;
959  const Word w_other = itMap_other->second;
960  if ( ( w_this & w_other ) != w_other ) return false;
961  }
962  return true;
963  }
964 
971  {
972  trace.info() << "[trace_includes_v1] #this=" << size()
973  << " #other=" << other.size() << std::endl;
974  auto itMap_other = other.my_elements.cbegin();
975  const auto itEndMap_other = other.my_elements.cend();
976  const auto itEndMap_this = my_elements.cend();
977  for ( ; itMap_other != itEndMap_other; ++itMap_other )
978  {
979  trace.info() << "other: cell=" << itMap_other->first
980  << " value=" << std::hex << itMap_other->second << std::endl;
981  const auto itMap_this = my_elements.find( itMap_other->first );
982  if ( itMap_this != itEndMap_this )
983  trace.info() << "this : cell=" << itMap_this->first
984  << " value=" << std::hex << itMap_this->second << std::endl;
985  else
986  trace.info() << "this : end cell" << std::endl;
987  if ( itMap_this == itEndMap_this ) return false;
988  const Word w_this = itMap_this->second;
989  const Word w_other = itMap_other->second;
990  if ( ( w_this & w_other ) != w_other ) return false;
991  }
992  return true;
993  }
994 
1000  bool internal_includes_by_iterator( const Self& other ) const
1001  {
1002  auto it_other = other.cbegin();
1003  auto itEnd_other = other.cend();
1004  while ( it_other != itEnd_other )
1005  {
1006  const auto it_this = find( *it_other );
1007  if ( it_this == cend() ) return false;
1008  auto itMap_other = it_other.it;
1009  const Word w_this = it_this.it->second;
1010  const Word w_other = itMap_other->second;
1011  if ( ( w_this & w_other ) != w_other ) return false;
1012  it_other = const_iterator( other, ++itMap_other );
1013  }
1014  return true;
1015  }
1016 
1024  bool internal_trace_includes_by_iterator( const Self& other ) const
1025  {
1026  trace.info() << "[trace_includes_v2] #this=" << size()
1027  << " #other=" << other.size() << std::endl;
1028  auto it_other = other.cbegin();
1029  auto itEnd_other = other.cend();
1030  while ( it_other != itEnd_other )
1031  {
1032  trace.info() << "other: cell=" << it_other.it->first
1033  << " value=" << std::hex << it_other.it->second << std::endl;
1034  const auto it_this = find( *it_other );
1035  if ( it_this != cend() )
1036  trace.info() << "this : cell=" << it_this.it->first
1037  << " value=" << std::hex << it_this.it->second << std::endl;
1038  else
1039  trace.info() << "this : end cell" << std::endl;
1040  if ( it_this == cend() ) return false;
1041  auto itMap_other = it_other.it;
1042  const Word w_this = it_this.it->second;
1043  const Word w_other = itMap_other->second;
1044  if ( ( w_this & w_other ) != w_other ) return false;
1045  it_other = const_iterator( other, ++itMap_other );
1046  }
1047  return true;
1048  }
1049 
1051 
1052  // ---------------------- hash policy services -----------------------------
1055  public:
1056 
1068  void reserve( size_type block_count )
1069  {
1070  my_elements.reserve( block_count );
1071  }
1072 
1074 
1075  private:
1076  // -------------------------- data ---------------------------------
1083  };
1084 
1085 
1094  template < typename Key,
1095  typename TSplitter,
1096  class Hash,
1097  class KeyEqual,
1098  class UnorderedMapAllocator >
1099  void swap
1102  noexcept
1103  {
1104  s1.swap( s2 );
1105  }
1106 
1107 } // namespace DGtal
1108 
1109 #endif // #ifndef UNORDEREDSETBYBLOCK_HPP
DGtal::UnorderedSetByBlock::~UnorderedSetByBlock
~UnorderedSetByBlock()=default
Default destructor.
DGtal::UnorderedSetByBlock::const_iterator::iterator_core_access
friend class boost::iterator_core_access
Definition: UnorderedSetByBlock.h:268
DGtal::concepts::CUnsignedNumber
Aim: Concept checking for Unsigned numbers. Models of this concept should be listed in NumberTraits c...
Definition: CUnsignedNumber.h:95
DGtal::UnorderedSetByBlock::end
const_iterator end() const
Definition: UnorderedSetByBlock.h:550
DGtal::UnorderedSetByBlock::Self
UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual > Self
Definition: UnorderedSetByBlock.h:164
DGtal::UnorderedSetByBlock::UnorderedSetByBlock
UnorderedSetByBlock(size_type bucket_count=23, const Splitter &splitter=Splitter(), const Hash &hash=Hash(), const key_equal &equal=key_equal(), const UnorderedMapAllocator &alloc=UnorderedMapAllocator())
Definition: UnorderedSetByBlock.h:474
DGtal::UnorderedSetByBlock::cbegin
const_iterator cbegin() const
Definition: UnorderedSetByBlock.h:556
DGtal::Splitter::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CUnsignedNumber< Word >))
DGtal::UnorderedSetByBlock::const_iterator::equal
bool equal(const const_iterator &other) const
Definition: UnorderedSetByBlock.h:292
DGtal::UnorderedSetByBlock::const_iterator::increment
void increment()
Definition: UnorderedSetByBlock.h:269
DGtal::UnorderedSetByBlock::iterator::iterator_core_access
friend class boost::iterator_core_access
Definition: UnorderedSetByBlock.h:408
DGtal::UnorderedSetByBlock::find
const_iterator find(const Key &key) const
Definition: UnorderedSetByBlock.h:863
DGtal::UnorderedSetByBlock::empty
bool empty() const noexcept
Definition: UnorderedSetByBlock.h:574
DGtal::UnorderedSetByBlock::UnorderedSetByBlock
UnorderedSetByBlock(Self &&other)
Definition: UnorderedSetByBlock.h:496
DGtal::Splitter::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CBoundedNumber< Word >))
DGtal::UnorderedSetByBlock::erase
size_type erase(const key_type &key)
Definition: UnorderedSetByBlock.h:825
DGtal::UnorderedSetByBlock::internal_trace_includes_by_iterator
bool internal_trace_includes_by_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:1024
DGtal::UnorderedSetByBlock::find
iterator find(const Key &key)
Definition: UnorderedSetByBlock.h:848
DGtal::swap
void swap(UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s1, UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s2) noexcept
Definition: UnorderedSetByBlock.h:1100
DGtal::Splitter::Word
TWord Word
Definition: UnorderedSetByBlock.h:70
DGtal::Bits::nbSetBits
static unsigned int nbSetBits(T val)
Definition: Bits.h:130
DGtal::trace
Trace trace
Definition: Common.h:150
DGtal::UnorderedSetByBlock::const_iterator::const_iterator
const_iterator(const Self &aSet, typename Container::const_iterator anIt, Coordinate aBit)
Definition: UnorderedSetByBlock.h:233
DGtal::UnorderedSetByBlock::my_elements
Container my_elements
the unordered_set containing the elements
Definition: UnorderedSetByBlock.h:1080
DGtal::UnorderedSetByBlock::blocks
size_type blocks() const noexcept
Definition: UnorderedSetByBlock.h:582
DGtal::UnorderedSetByBlock::iterator::equal
bool equal(const iterator &other) const
Definition: UnorderedSetByBlock.h:432
DGtal::Splitter
Definition: UnorderedSetByBlock.h:67
DGtal::concepts::CBoundedNumber
Aim: The concept CBoundedNumber specifies what are the bounded numbers. Models of this concept should...
Definition: CBoundedNumber.h:97
DGtal::UnorderedSetByBlock::iterator::collection
Self * collection
the collection that this iterator is traversing.
Definition: UnorderedSetByBlock.h:453
DGtal::UnorderedSetByBlock::const_iterator::bit
Coordinate bit
the current position in the block.
Definition: UnorderedSetByBlock.h:308
DGtal::Splitter::join
static Element join(const std::pair< Element, Coordinate > &p)
Definition: UnorderedSetByBlock.h:115
DGtal::UnorderedSetByBlock::includes
bool includes(const Self &other) const
Definition: UnorderedSetByBlock.h:939
DGtal::UnorderedSetByBlock::iterator::dereference
const Key dereference() const
Definition: UnorderedSetByBlock.h:447
DGtal::UnorderedSetByBlock::key_equal
KeyEqual key_equal
KeyEqual.
Definition: UnorderedSetByBlock.h:184
DGtal::UnorderedSetByBlock::max_size
size_type max_size() const noexcept
Definition: UnorderedSetByBlock.h:578
DGtal::UnorderedSetByBlock::iterator::bit
Coordinate bit
the current position in the block.
Definition: UnorderedSetByBlock.h:457
DGtal::UnorderedSetByBlock::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: UnorderedSetByBlock.h:895
DGtal::UnorderedSetByBlock::reserve
void reserve(size_type block_count)
Definition: UnorderedSetByBlock.h:1068
DGtal::UnorderedSetByBlock::const_iterator::const_iterator
const_iterator()
Default constructor.
Definition: UnorderedSetByBlock.h:207
DGtal::UnorderedSetByBlock::begin
iterator begin()
Definition: UnorderedSetByBlock.h:534
DGtal::UnorderedSetByBlock::UnorderedSetByBlock
UnorderedSetByBlock(const Self &other)
Definition: UnorderedSetByBlock.h:488
DGtal::Trace::info
std::ostream & info()
DGtal::UnorderedSetByBlock::difference_type
Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
Definition: UnorderedSetByBlock.h:180
DGtal::UnorderedSetByBlock::const_iterator::current
Word current
the current value of the block, where visited bits have been erased.
Definition: UnorderedSetByBlock.h:310
DGtal::UnorderedSetByBlock::hasher
Hash hasher
Hash.
Definition: UnorderedSetByBlock.h:182
DGtal::UnorderedSetByBlock::memory_usage_unordered_set
size_type memory_usage_unordered_set() const noexcept
Definition: UnorderedSetByBlock.h:601
DGtal::UnorderedSetByBlock::begin
const_iterator begin() const
Definition: UnorderedSetByBlock.h:545
DGtal::UnorderedSetByBlock::operator=
Self & operator=(Self &&other)
Definition: UnorderedSetByBlock.h:518
DGtal::UnorderedSetByBlock::internal_includes_by_iterator
bool internal_includes_by_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:1000
DGtal::Splitter::join
static Element join(Element e, Coordinate x)
Definition: UnorderedSetByBlock.h:101
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition: ClosedIntegerHalfPlane.h:49
DGtal::UnorderedSetByBlock::const_iterator
Read iterator on set elements. Model of ForwardIterator.
Definition: UnorderedSetByBlock.h:204
DGtal::UnorderedSetByBlock::pointer
Key * pointer
Pointer to value_type/Key.
Definition: UnorderedSetByBlock.h:192
DGtal::UnorderedSetByBlock::iterator::iterator
iterator(const_iterator &&other)
Definition: UnorderedSetByBlock.h:393
DGtal::UnorderedSetByBlock::cend
const_iterator cend() const
Definition: UnorderedSetByBlock.h:561
DGtal::Splitter::Coordinate
Element::Coordinate Coordinate
Definition: UnorderedSetByBlock.h:71
DGtal::UnorderedSetByBlock::my_splitter
Splitter my_splitter
The splitter object.
Definition: UnorderedSetByBlock.h:1078
DGtal::UnorderedSetByBlock::internal_trace_includes_by_map_iterator
bool internal_trace_includes_by_map_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:970
DGtal::UnorderedSetByBlock::iterator::increment
void increment()
Definition: UnorderedSetByBlock.h:409
DGtal::UnorderedSetByBlock::erase
iterator erase(const_iterator first, const_iterator last) noexcept
Definition: UnorderedSetByBlock.h:760
DGtal::UnorderedSetByBlock::value_type
Key value_type
Key.
Definition: UnorderedSetByBlock.h:176
DGtal::UnorderedSetByBlock::size
size_type size() const noexcept
Definition: UnorderedSetByBlock.h:576
DGtal::UnorderedSetByBlock::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: UnorderedSetByBlock.h:915
DGtal::UnorderedSetByBlock::end
iterator end()
Definition: UnorderedSetByBlock.h:539
DGtal::UnorderedSetByBlock::iterator::iterator
iterator(Self &aSet, typename Container::iterator anIt)
Definition: UnorderedSetByBlock.h:329
DGtal::UnorderedSetByBlock::erase
iterator erase(const_iterator pos) noexcept
Definition: UnorderedSetByBlock.h:730
DGtal::UnorderedSetByBlock::iterator::it
Container::iterator it
the hidden iterator that traverses the block map.
Definition: UnorderedSetByBlock.h:455
DGtal::UnorderedSetByBlock::my_size
size_type my_size
the number of elements
Definition: UnorderedSetByBlock.h:1082
DGtal::UnorderedSetByBlock::const_iterator::dereference
const Key dereference() const
Definition: UnorderedSetByBlock.h:298
DGtal::UnorderedSetByBlock::count
size_type count(const Key &key) const
Definition: UnorderedSetByBlock.h:877
DGtal::UnorderedSetByBlock::size_type
Container::size_type size_type
Unsigned integer type (usually std::size_t)
Definition: UnorderedSetByBlock.h:178
DGtal::UnorderedSetByBlock::allocator_type
Container::allocator_type allocator_type
Allocator.
Definition: UnorderedSetByBlock.h:186
DGtal::UnorderedSetByBlock::swap
void swap(Self &other) noexcept
Definition: UnorderedSetByBlock.h:636
DGtal::Bits::leastSignificantBit
static unsigned int leastSignificantBit(DGtal::uint8_t n)
Definition: Bits.h:297
DGtal::UnorderedSetByBlock::const_iterator::const_iterator
const_iterator(const Self &aSet, const Key &key)
Definition: UnorderedSetByBlock.h:249
DGtal::PointVector< dim, Integer >
DGtal::UnorderedSetByBlock::const_pointer
const Key * const_pointer
Const Pointer to value_type/Key.
Definition: UnorderedSetByBlock.h:194
DGtal::UnorderedSetByBlock::iterator::equal
bool equal(const const_iterator &other) const
Definition: UnorderedSetByBlock.h:441
DGtal::Splitter::split
static std::pair< Element, Coordinate > split(Element e)
Definition: UnorderedSetByBlock.h:85
DGtal::UnorderedSetByBlock::iterator
Read-write iterator on set elements. Model of ForwardIterator.
Definition: UnorderedSetByBlock.h:319
DGtal::Splitter::Element
TElement Element
Definition: UnorderedSetByBlock.h:69
DGtal::UnorderedSetByBlock::iterator::iterator
iterator(Self &aSet, typename Container::iterator anIt, Coordinate aBit)
Definition: UnorderedSetByBlock.h:348
DGtal::UnorderedSetByBlock::reference
Key & reference
Reference to value_type/Key.
Definition: UnorderedSetByBlock.h:188
DGtal::UnorderedSetByBlock::Container
std::unordered_map< Key, Word, Hash, KeyEqual, UnorderedMapAllocator > Container
The underlying container, an unordered_map.
Definition: UnorderedSetByBlock.h:170
DGtal::UnorderedSetByBlock::Splitter
TSplitter Splitter
Definition: UnorderedSetByBlock.h:165
DGtal::UnorderedSetByBlock::const_iterator::it
Container::const_iterator it
the hidden iterator that traverses the block map.
Definition: UnorderedSetByBlock.h:306
DGtal::UnorderedSetByBlock
Definition: UnorderedSetByBlock.h:163
DGtal::UnorderedSetByBlock::iterator::iterator
iterator(const const_iterator &other)
Definition: UnorderedSetByBlock.h:386
DGtal::UnorderedSetByBlock::clear
void clear() noexcept
Clears the container.
Definition: UnorderedSetByBlock.h:620
DGtal::UnorderedSetByBlock::operator=
Self & operator=(const Self &other)
Definition: UnorderedSetByBlock.h:505
DGtal::UnorderedSetByBlock::iterator::iterator
iterator()
Default constructor.
Definition: UnorderedSetByBlock.h:322
DGtal::UnorderedSetByBlock::iterator::current
Word current
the current value of the block, where visited bits have been erased.
Definition: UnorderedSetByBlock.h:459
DGtal::UnorderedSetByBlock::memory_usage
size_type memory_usage() const noexcept
Definition: UnorderedSetByBlock.h:586
DGtal::UnorderedSetByBlock::Coordinate
Splitter::Coordinate Coordinate
Definition: UnorderedSetByBlock.h:167
DGtal::UnorderedSetByBlock::insert
std::pair< iterator, bool > insert(const value_type &value)
Attempts to insert an element into the set.
Definition: UnorderedSetByBlock.h:656
DGtal::UnorderedSetByBlock::emplace
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the set.
Definition: UnorderedSetByBlock.h:695
DGtal::Splitter::Self
Splitter< TElement, TWord > Self
Definition: UnorderedSetByBlock.h:68
DGtal::UnorderedSetByBlock::key_type
Key key_type
Key.
Definition: UnorderedSetByBlock.h:174
DGtal::UnorderedSetByBlock::internal_includes_by_map_iterator
bool internal_includes_by_map_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:949
DGtal::UnorderedSetByBlock::Word
Splitter::Word Word
Definition: UnorderedSetByBlock.h:166
DGtal::UnorderedSetByBlock::iterator::iterator
iterator(Self &aSet, const Key &key)
Definition: UnorderedSetByBlock.h:366
DGtal::UnorderedSetByBlock::const_iterator::collection
const Self * collection
the collection that this iterator is traversing.
Definition: UnorderedSetByBlock.h:304
DGtal::UnorderedSetByBlock::const_reference
const Key & const_reference
Const reference to value_type/Key.
Definition: UnorderedSetByBlock.h:190
DGtal::UnorderedSetByBlock::const_iterator::const_iterator
const_iterator(const Self &aSet, typename Container::const_iterator anIt)
Definition: UnorderedSetByBlock.h:214