DGtal  1.3.beta
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 InputIterator>
694  void insert( InputIterator first, InputIterator last )
695  {
696  for ( ; first != last; ++first ) insert( *first );
697  }
698 
712  template<typename... _Args>
713  std::pair<iterator, bool>
714  emplace(_Args&&... __args)
715  {
716  const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
717  auto it = my_elements.find( se.first );
718  if ( it == my_elements.end() )
719  {
720  auto p =
721  my_elements.insert( std::make_pair( se.first,
722  static_cast<Word>(1) << se.second ) );
723  my_size += 1;
724  return std::make_pair( iterator( *this, p.first, se.second ), true );
725  }
726  else
727  {
728  bool exist = it->second & ( static_cast<Word>(1) << se.second );
729  if ( ! exist )
730  {
731  it->second |= static_cast<Word>(1) << se.second;
732  my_size += 1;
733  }
734  return std::make_pair( iterator( *this, it, se.second ), ! exist );
735  }
736  }
737 
749  iterator erase( const_iterator pos ) noexcept
750  {
751  ASSERT( this == pos.collection );
752  ASSERT( pos != cend() );
753  ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
754  != static_cast<Word>(0) );
755  my_size -= 1;
756  Word & w = const_cast< Word& >( pos.it->second );
757  if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
758  == static_cast<Word>(0) )
759  return iterator( *this, my_elements.erase( pos.it ) );
760  else
761  return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
762  }
763 
779  iterator erase( const_iterator first, const_iterator last ) noexcept
780  {
781  ASSERT( this == first.collection );
782  ASSERT( this == last.collection );
783  if ( first == cend() ) return end();
784  auto itB = first.it;
785  auto itE = last.it;
786  Word mask = static_cast<Word>(0);
787  // Take care of range over one block only
788  if ( itB == itE )
789  {
790  while ( first != last )
791  {
792  mask |= static_cast<Word>(1) << first.bit;
793  my_size -= 1;
794  ++first;
795  }
796  my_elements[ itB->first ] &= ~mask;
797  return iterator( *this,
798  my_elements.find( itE->first ),
799  last.bit ); // must be valid
800  }
801  // Take care of first element.
802  while ( first.it == itB )
803  {
804  mask |= static_cast<Word>(1) << first.bit;
805  my_size -= 1;
806  ++first;
807  }
808  // Erase first block if empty
809  if ( ( my_elements[ itB->first ] &= ~mask )
810  == static_cast<Word>(0) )
811  my_elements.erase( itB );
812  // Count erased elements in main range.
813  for ( itB = first.it; itB != itE; ++itB )
814  my_size -= Bits::nbSetBits( itB->second );
815  // Erase elements in main range
816  my_elements.erase( first.it, itE );
817  // Take care of last element.
818  if ( itE == my_elements.cend() ) return end();
819  itB = itE;
820  first = const_iterator( *this, itB );
821  mask = static_cast<Word>(0);
822  while ( first != last )
823  {
824  mask |= static_cast<Word>(1) << first.bit;
825  my_size -= 1;
826  ++first;
827  }
828  // Erase last block if empty
829  if ( ( my_elements[ itB->first ] &= ~mask )
830  == static_cast<Word>(0) )
831  my_elements.erase( itB );
832  return iterator( *this,
833  my_elements.find( itE->first ),
834  last.bit ); // must be valid or end.
835  }
836 
844  size_type erase( const key_type& key )
845  {
846  auto it = find( key );
847  if ( it != end() )
848  {
849  erase( it );
850  return 1;
851  }
852  else return 0;
853  }
854 
856 
857  // ---------------------- lookup services -----------------------------
860  public:
861 
867  iterator find( const Key& key )
868  {
869  const auto se = my_splitter.split( key );
870  const auto it = my_elements.find( se.first );
871  if ( it == my_elements.end() ) return end();
872  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
873  if ( exist ) return iterator( *this, it, se.second );
874  else return end();
875  }
876 
882  const_iterator find( const Key& key ) const
883  {
884  const auto se = my_splitter.split( key );
885  const auto it = my_elements.find( se.first );
886  if ( it == my_elements.cend() ) return cend();
887  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
888  if ( exist ) return const_iterator( *this, it, se.second );
889  else return cend();
890  }
891 
896  size_type count( const Key& key ) const
897  {
898  const auto se = my_splitter.split( key );
899  const auto it = my_elements.find( se.first );
900  if ( it == my_elements.cend() ) return 0;
901  const bool exist = it->second & ( static_cast<Word>(1) << se.second );
902  return exist ? 1 : 0;
903  }
904 
913  std::pair<iterator,iterator>
914  equal_range( const Key & key )
915  {
916  iterator first = find( key );
917  if ( first != end() )
918  {
919  iterator last = first;
920  return std::make_pair( first, ++last );
921  }
922  else return std::make_pair( first, first );
923  }
924 
933  std::pair<const_iterator,const_iterator>
934  equal_range( const Key & key ) const
935  {
936  const_iterator first = find( key );
937  if ( first != end() )
938  {
939  const_iterator last = first;
940  return std::make_pair( first, ++last );
941  }
942  else return std::make_pair( first, first );
943  }
944 
946 
947  // ---------------------- set services -------------------------
950  public:
951 
958  bool includes( const Self& other ) const
959  {
960  return internal_includes_by_map_iterator( other );
961  }
962 
963  protected:
968  bool internal_includes_by_map_iterator( const Self& other ) const
969  {
970  auto itMap_other = other.my_elements.cbegin();
971  const auto itEndMap_other = other.my_elements.cend();
972  const auto itEndMap_this = my_elements.cend();
973  for ( ; itMap_other != itEndMap_other; ++itMap_other )
974  {
975  const auto itMap_this = my_elements.find( itMap_other->first );
976  if ( itMap_this == itEndMap_this ) return false;
977  const Word w_this = itMap_this->second;
978  const Word w_other = itMap_other->second;
979  if ( ( w_this & w_other ) != w_other ) return false;
980  }
981  return true;
982  }
983 
990  {
991  trace.info() << "[trace_includes_v1] #this=" << size()
992  << " #other=" << other.size() << std::endl;
993  auto itMap_other = other.my_elements.cbegin();
994  const auto itEndMap_other = other.my_elements.cend();
995  const auto itEndMap_this = my_elements.cend();
996  for ( ; itMap_other != itEndMap_other; ++itMap_other )
997  {
998  trace.info() << "other: cell=" << itMap_other->first
999  << " value=" << std::hex << itMap_other->second << std::endl;
1000  const auto itMap_this = my_elements.find( itMap_other->first );
1001  if ( itMap_this != itEndMap_this )
1002  trace.info() << "this : cell=" << itMap_this->first
1003  << " value=" << std::hex << itMap_this->second << std::endl;
1004  else
1005  trace.info() << "this : end cell" << std::endl;
1006  if ( itMap_this == itEndMap_this ) return false;
1007  const Word w_this = itMap_this->second;
1008  const Word w_other = itMap_other->second;
1009  if ( ( w_this & w_other ) != w_other ) return false;
1010  }
1011  return true;
1012  }
1013 
1019  bool internal_includes_by_iterator( const Self& other ) const
1020  {
1021  auto it_other = other.cbegin();
1022  auto itEnd_other = other.cend();
1023  while ( it_other != itEnd_other )
1024  {
1025  const auto it_this = find( *it_other );
1026  if ( it_this == cend() ) return false;
1027  auto itMap_other = it_other.it;
1028  const Word w_this = it_this.it->second;
1029  const Word w_other = itMap_other->second;
1030  if ( ( w_this & w_other ) != w_other ) return false;
1031  it_other = const_iterator( other, ++itMap_other );
1032  }
1033  return true;
1034  }
1035 
1043  bool internal_trace_includes_by_iterator( const Self& other ) const
1044  {
1045  trace.info() << "[trace_includes_v2] #this=" << size()
1046  << " #other=" << other.size() << std::endl;
1047  auto it_other = other.cbegin();
1048  auto itEnd_other = other.cend();
1049  while ( it_other != itEnd_other )
1050  {
1051  trace.info() << "other: cell=" << it_other.it->first
1052  << " value=" << std::hex << it_other.it->second << std::endl;
1053  const auto it_this = find( *it_other );
1054  if ( it_this != cend() )
1055  trace.info() << "this : cell=" << it_this.it->first
1056  << " value=" << std::hex << it_this.it->second << std::endl;
1057  else
1058  trace.info() << "this : end cell" << std::endl;
1059  if ( it_this == cend() ) return false;
1060  auto itMap_other = it_other.it;
1061  const Word w_this = it_this.it->second;
1062  const Word w_other = itMap_other->second;
1063  if ( ( w_this & w_other ) != w_other ) return false;
1064  it_other = const_iterator( other, ++itMap_other );
1065  }
1066  return true;
1067  }
1068 
1070 
1071  // ---------------------- hash policy services -----------------------------
1074  public:
1075 
1087  void reserve( size_type block_count )
1088  {
1089  my_elements.reserve( block_count );
1090  }
1091 
1093 
1094  private:
1095  // -------------------------- data ---------------------------------
1102  };
1103 
1104 
1113  template < typename Key,
1114  typename TSplitter,
1115  class Hash,
1116  class KeyEqual,
1117  class UnorderedMapAllocator >
1118  void swap
1121  noexcept
1122  {
1123  s1.swap( s2 );
1124  }
1125 
1126 } // namespace DGtal
1127 
1128 #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:94
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::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:882
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:844
DGtal::UnorderedSetByBlock::internal_trace_includes_by_iterator
bool internal_trace_includes_by_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:1043
DGtal::UnorderedSetByBlock::find
iterator find(const Key &key)
Definition: UnorderedSetByBlock.h:867
DGtal::swap
void swap(UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s1, UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s2) noexcept
Definition: UnorderedSetByBlock.h:1119
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:154
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:1099
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:96
DGtal::UnorderedSetByBlock::iterator::collection
Self * collection
the collection that this iterator is traversing.
Definition: UnorderedSetByBlock.h:453
DGtal::UnorderedSetByBlock::const_reference
const typedef Key & const_reference
Const reference to value_type/Key.
Definition: UnorderedSetByBlock.h:190
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:958
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:914
DGtal::UnorderedSetByBlock::reserve
void reserve(size_type block_count)
Definition: UnorderedSetByBlock.h:1087
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::const_pointer
const typedef Key * const_pointer
Const Pointer to value_type/Key.
Definition: UnorderedSetByBlock.h:194
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:1019
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.
DGtal::UnorderedSetByBlock::const_iterator
Read iterator on set elements. Model of ForwardIterator.
Definition: UnorderedSetByBlock.h:200
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:1097
DGtal::UnorderedSetByBlock::internal_trace_includes_by_map_iterator
bool internal_trace_includes_by_map_iterator(const Self &other) const
Definition: UnorderedSetByBlock.h:989
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:779
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:934
DGtal::UnorderedSetByBlock::insert
void insert(InputIterator first, InputIterator last)
Inserts a range of element into the set.
Definition: UnorderedSetByBlock.h:694
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:749
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:1101
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:896
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::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:315
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:714
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:968
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_iterator::const_iterator
const_iterator(const Self &aSet, typename Container::const_iterator anIt)
Definition: UnorderedSetByBlock.h:214