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) );
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 InputIterator>
694 void insert( InputIterator first, InputIterator last )
696 for ( ; first != last; ++first )
insert( *first );
712 template<
typename... _Args>
713 std::pair<iterator, bool>
716 const auto se =
my_splitter.split( Key( std::forward<_Args>(__args)... ) );
722 static_cast<Word>(1) << se.second ) );
724 return std::make_pair(
iterator( *
this, p.first, se.second ),
true );
728 bool exist = it->second & (
static_cast<Word>(1) << se.second );
731 it->second |=
static_cast<Word>(1) << se.second;
734 return std::make_pair(
iterator( *
this, it, se.second ), ! exist );
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) );
756 Word & w =
const_cast< Word&
>( pos.it->second );
757 if ( ( w &= ~(
static_cast<Word>(1) << pos.bit ) )
758 ==
static_cast<Word>(0) )
781 ASSERT(
this == first.collection );
782 ASSERT(
this == last.collection );
783 if ( first ==
cend() )
return end();
790 while ( first != last )
792 mask |=
static_cast<Word>(1) << first.bit;
802 while ( first.it == itB )
804 mask |=
static_cast<Word>(1) << first.bit;
810 ==
static_cast<Word>(0) )
813 for ( itB = first.it; itB != itE; ++itB )
821 mask =
static_cast<Word>(0);
822 while ( first != last )
824 mask |=
static_cast<Word>(1) << first.bit;
830 ==
static_cast<Word>(0) )
846 auto it =
find( key );
872 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
873 if ( exist )
return iterator( *
this, it, se.second );
887 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
901 const bool exist = it->second & (
static_cast<Word>(1) << se.second );
902 return exist ? 1 : 0;
913 std::pair<iterator,iterator>
917 if ( first !=
end() )
920 return std::make_pair( first, ++last );
922 else return std::make_pair( first, first );
933 std::pair<const_iterator,const_iterator>
937 if ( first !=
end() )
940 return std::make_pair( first, ++last );
942 else return std::make_pair( first, first );
971 const auto itEndMap_other = other.
my_elements.cend();
973 for ( ; itMap_other != itEndMap_other; ++itMap_other )
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;
992 <<
" #other=" << other.
size() << std::endl;
994 const auto itEndMap_other = other.
my_elements.cend();
996 for ( ; itMap_other != itEndMap_other; ++itMap_other )
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;
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;
1021 auto it_other = other.
cbegin();
1022 auto itEnd_other = other.
cend();
1023 while ( it_other != itEnd_other )
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;
1046 <<
" #other=" << other.
size() << std::endl;
1047 auto it_other = other.
cbegin();
1048 auto itEnd_other = other.
cend();
1049 while ( it_other != itEnd_other )
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;
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;
1113 template <
typename Key,
1117 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)
void insert(InputIterator first, InputIterator last)
Inserts a range of element into the set.
~UnorderedSetByBlock()=default
Default destructor.
iterator find(const Key &key)
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
std::pair< iterator, bool > insert(const value_type &value)
Attempts to insert an element into the set.
bool internal_trace_includes_by_iterator(const Self &other) const
void swap(Self &other) noexcept
Splitter::Coordinate Coordinate
Self & operator=(Self &&other)
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
size_type erase(const key_type &key)
iterator erase(const_iterator pos) noexcept
size_type max_size() const noexcept
const_iterator cbegin() const
Key * pointer
Pointer to value_type/Key.
bool internal_includes_by_iterator(const Self &other) const
std::pair< iterator, iterator > equal_range(const Key &key)
void reserve(size_type block_count)
Container::difference_type difference_type
Signed integer type (usually std::ptrdiff_t)
const_iterator cend() const
const_iterator begin() const
Self & operator=(const Self &other)
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
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the set.
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...