26 #ifndef UNORDEREDSETBYBLOCK_HPP
27 #define UNORDEREDSETBYBLOCK_HPP
29 #include <unordered_map>
30 #include <boost/iterator/iterator_facade.hpp>
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"
66 template <
typename TElement,
typename TWord = u
int32_t >
84 std::pair< Element, Coordinate >
88 ( e[ 0 ] &
static_cast<Coordinate>(
sizeof(
Word ) * CHAR_BIT - 1 ) );
89 e[ 0 ] -= block_coords;
90 return { e, block_coords };
115 join(
const std::pair< Element, Coordinate >& p )
155 template <
typename 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 >
169 typedef std::unordered_map< Key,
Word, Hash, KeyEqual,
201 :
public boost::iterator_facade< const_iterator, Key const,
202 boost::forward_traversal_tag,
258 -
static_cast<Word>(1) );
272 &&
"Invalid increment on const_iterator" );
306 typename Container::const_iterator
it;
316 :
public boost::iterator_facade< iterator, Key const,
317 boost::forward_traversal_tag,
355 -
static_cast<Word>(1) );
375 -
static_cast<Word>(1) );
395 it( std::move( other.
it ) ),
396 bit( std::move( other.
bit ) ),
412 &&
"Invalid increment on iterator" );
455 typename Container::iterator
it;
476 const Hash& hash = Hash(),
478 const UnorderedMapAllocator& alloc = UnorderedMapAllocator())
507 if (
this != &other )
522 my_size = std::move( other.my_size );
590 mem +=
blocks() * (
sizeof(
void* )
605 mem +=
size() * (
sizeof(
void* )
640 std::swap(
my_size, other.my_size );
663 ( std::make_pair( se.first,
664 static_cast<Word>(1) << se.second ) );
666 return std::make_pair(
iterator( *
this, p.first, se.second ),
true );
670 bool exist = it->second & (
static_cast<Word>(1) << se.second );
673 it->second |=
static_cast<Word>(1) << se.second;
676 return std::make_pair(
iterator( *
this, it, se.second ), ! exist );
693 template<
typename... _Args>
694 std::pair<iterator, bool>
697 const auto se =
my_splitter.split( Key( std::forward<_Args>(__args)... ) );
703 static_cast<Word>(1) << se.second ) );
705 return std::make_pair(
iterator( *
this, p.first, se.second ),
true );
709 bool exist = it->second & (
static_cast<Word>(1) << se.second );
712 it->second |=
static_cast<Word>(1) << se.second;
715 return std::make_pair(
iterator( *
this, it, se.second ), ! exist );
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) );
737 Word & w =
const_cast< Word&
>( pos.it->second );
738 if ( ( w &= ~(
static_cast<Word>(1) << pos.bit ) )
739 ==
static_cast<Word>(0) )
762 ASSERT(
this == first.collection );
763 ASSERT(
this == last.collection );
764 if ( first ==
cend() )
return end();
771 while ( first != last )
773 mask |=
static_cast<Word>(1) << first.bit;
783 while ( first.it == itB )
785 mask |=
static_cast<Word>(1) << first.bit;
791 ==
static_cast<Word>(0) )
794 for ( itB = first.it; itB != itE; ++itB )
802 mask =
static_cast<Word>(0);
803 while ( first != last )
805 mask |=
static_cast<Word>(1) << first.bit;
811 ==
static_cast<Word>(0) )
827 auto it =
find( key );
853 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
854 if ( exist )
return iterator( *
this, it, se.second );
868 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
882 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
883 return exist ? 1 : 0;
894 std::pair<iterator,iterator>
898 if ( first !=
end() )
901 return std::make_pair( first, ++last );
903 else return std::make_pair( first, first );
914 std::pair<const_iterator,const_iterator>
918 if ( first !=
end() )
921 return std::make_pair( first, ++last );
923 else return std::make_pair( first, first );
952 const auto itEndMap_other = other.
my_elements.cend();
954 for ( ; itMap_other != itEndMap_other; ++itMap_other )
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;
973 <<
" #other=" << other.
size() << std::endl;
975 const auto itEndMap_other = other.
my_elements.cend();
977 for ( ; itMap_other != itEndMap_other; ++itMap_other )
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;
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;
1002 auto it_other = other.
cbegin();
1003 auto itEnd_other = other.
cend();
1004 while ( it_other != itEnd_other )
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;
1027 <<
" #other=" << other.
size() << std::endl;
1028 auto it_other = other.
cbegin();
1029 auto itEnd_other = other.
cend();
1030 while ( it_other != itEnd_other )
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;
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;
1094 template <
typename Key,
1098 class UnorderedMapAllocator >
DGtal is the top-level namespace which contains all DGtal functions and types.
void swap(UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s1, UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator > &s2) noexcept
static unsigned int nbSetBits(T val)
static unsigned int leastSignificantBit(DGtal::uint8_t n)
static Element join(Element e, Coordinate x)
BOOST_CONCEPT_ASSERT((concepts::CBoundedNumber< Word >))
Element::Coordinate Coordinate
Splitter< TElement, TWord > Self
static std::pair< Element, Coordinate > split(Element e)
BOOST_CONCEPT_ASSERT((concepts::CUnsignedNumber< Word >))
static Element join(const std::pair< Element, Coordinate > &p)
Read iterator on set elements. Model of ForwardIterator.
bool equal(const const_iterator &other) const
const_iterator()
Default constructor.
const_iterator(const Self &aSet, typename Container::const_iterator anIt)
const_iterator(const Self &aSet, const Key &key)
const Key dereference() const
Container::const_iterator it
the hidden iterator that traverses the block map.
const Self * collection
the collection that this iterator is traversing.
friend class boost::iterator_core_access
Coordinate bit
the current position in the block.
const_iterator(const Self &aSet, typename Container::const_iterator anIt, Coordinate aBit)
Word current
the current value of the block, where visited bits have been erased.
Read-write iterator on set elements. Model of ForwardIterator.
Self * collection
the collection that this iterator is traversing.
Coordinate bit
the current position in the block.
iterator(const const_iterator &other)
bool equal(const const_iterator &other) const
Container::iterator it
the hidden iterator that traverses the block map.
iterator(Self &aSet, typename Container::iterator anIt)
const Key dereference() const
iterator(Self &aSet, const Key &key)
bool equal(const iterator &other) const
friend class boost::iterator_core_access
iterator()
Default constructor.
Word current
the current value of the block, where visited bits have been erased.
iterator(Self &aSet, typename Container::iterator anIt, Coordinate aBit)
iterator(const_iterator &&other)
~UnorderedSetByBlock()=default
Default destructor.
iterator find(const Key &key)
Self & operator=(const Self &other)
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Self & operator=(Self &&other)
bool internal_trace_includes_by_iterator(const Self &other) const
void swap(Self &other) noexcept
Splitter::Coordinate Coordinate
UnorderedSetByBlock(const Self &other)
std::unordered_map< Key, Word, Hash, KeyEqual, UnorderedMapAllocator > Container
The underlying container, an unordered_map.
Key & reference
Reference to value_type/Key.
size_type blocks() const noexcept
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the set.
size_type erase(const key_type &key)
iterator erase(const_iterator pos) noexcept
size_type max_size() const noexcept
std::pair< iterator, iterator > equal_range(const Key &key)
const_iterator cbegin() const
Key * pointer
Pointer to value_type/Key.
bool internal_includes_by_iterator(const Self &other) const
void reserve(size_type block_count)
Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
std::pair< iterator, bool > insert(const value_type &value)
Attempts to insert an element into the set.
const_iterator cend() const
const_iterator begin() const
UnorderedSetByBlock(Self &&other)
Splitter my_splitter
The splitter object.
size_type size() const noexcept
bool empty() const noexcept
bool internal_includes_by_map_iterator(const Self &other) const
bool includes(const Self &other) const
size_type my_size
the number of elements
const Key * const_pointer
Const Pointer to value_type/Key.
iterator erase(const_iterator first, const_iterator last) noexcept
const_iterator find(const Key &key) const
const_iterator end() const
size_type count(const Key &key) const
const Key & const_reference
Const reference to value_type/Key.
Container::allocator_type allocator_type
Allocator.
Container my_elements
the unordered_set containing the elements
UnorderedSetByBlock(size_type bucket_count=23, const Splitter &splitter=Splitter(), const Hash &hash=Hash(), const key_equal &equal=key_equal(), const UnorderedMapAllocator &alloc=UnorderedMapAllocator())
Container::size_type size_type
Unsigned integer type (usually std::size_t)
UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual > Self
size_type memory_usage_unordered_set() const noexcept
KeyEqual key_equal
KeyEqual.
void clear() noexcept
Clears the container.
size_type memory_usage() const noexcept
bool internal_trace_includes_by_map_iterator(const Self &other) const
Aim: The concept CBoundedNumber specifies what are the bounded numbers. Models of this concept should...
Aim: Concept checking for Unsigned numbers. Models of this concept should be listed in NumberTraits c...