UnorderedSetByBlock.h

 
#pragma once
 
#ifndef UNORDEREDSETBYBLOCK_HPP
#define UNORDEREDSETBYBLOCK_HPP
 
#include <unordered_map>
#include <boost/iterator/iterator_facade.hpp>
#include <climits>
#include "DGtal/base/Common.h"
#include "DGtal/base/Bits.h"
#include "DGtal/kernel/CUnsignedNumber.h"
#include "DGtal/kernel/CBoundedNumber.h"
#include "DGtal/kernel/PointVector.h"
#include "DGtal/kernel/PointHashFunctions.h"
 
namespace DGtal
{
 
  template < typename TElement, typename TWord = uint32_t >
  struct Splitter {
    typedef Splitter< TElement,TWord >   Self;
    typedef TElement                     Element;
    typedef TWord                        Word;
    typedef typename Element::Coordinate Coordinate;
 
    BOOST_CONCEPT_ASSERT(( concepts::CBoundedNumber< Word > ));
    BOOST_CONCEPT_ASSERT(( concepts::CUnsignedNumber< Word > ));
 
    static
    std::pair< Element, Coordinate >
    split( Element e )
    {
      auto block_coords =
        ( e[ 0 ] & static_cast<Coordinate>( sizeof( Word ) * CHAR_BIT - 1 ) );
      e[ 0 ] -= block_coords;
      return { e, block_coords };
    }
 
    static
    Element
    join( Element e, Coordinate x )
    {
      e[ 0 ] |= x;
      return e;
    }
 
    static
    Element
    join( const std::pair< Element, Coordinate >& p )
    {
      Element ge = p.first;
      ge[ 0 ] |= p.second;
      return ge;
    }
  };
 
 
  template < typename Key,
             typename TSplitter = Splitter< Key >,
             class Hash = std::hash<Key>,
             class KeyEqual = std::equal_to<Key>,
             class UnorderedMapAllocator = std::allocator<
               std::pair<const Key, typename TSplitter::Word >
               >
             >
  struct UnorderedSetByBlock {
    typedef UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual > Self;
    typedef TSplitter               Splitter;
    typedef typename Splitter::Word Word;
    typedef typename Splitter::Coordinate Coordinate;
    typedef std::unordered_map< Key, Word, Hash, KeyEqual,
                                UnorderedMapAllocator > Container;
 
    // Standard types
    typedef Key key_type;
    typedef Key value_type;
    typedef typename Container::size_type size_type;
    typedef typename Container::difference_type difference_type;
    typedef Hash     hasher;
    typedef KeyEqual key_equal;
    typedef typename Container::allocator_type allocator_type;
    typedef Key& reference;
    typedef const Key& const_reference;
    typedef Key* pointer;
    typedef const Key* const_pointer;
 
  public:
    // ---------------------- iterators --------------------------------
 
    struct const_iterator
      : public boost::iterator_facade< const_iterator, Key const,
                                       boost::forward_traversal_tag,
                                       Key const >
    {
      friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
      const_iterator() : collection( nullptr ), it(),
                         bit( static_cast<Coordinate>(0) ),
                         current( static_cast<Word>(0) ) {}
 
      const_iterator( const Self& aSet, typename Container::const_iterator anIt )
        : collection( &aSet ), it( anIt )
      {
        if ( it != collection->my_elements.cend() )
          {
            current  = it->second;
            bit      = static_cast<Coordinate>( Bits::leastSignificantBit( current ) );
          }
        else
          {
            current = static_cast<Word>(0);
            bit     = static_cast<Coordinate>(0);
          }
      }
 
      const_iterator( const Self& aSet, typename Container::const_iterator anIt,
                      Coordinate aBit )
        : collection( &aSet ), it( anIt ), bit( aBit )
      {
        if ( it != collection->my_elements.cend() )
          {
            current  = it->second;
            current &= ~( ( static_cast<Word>(1) << bit ) - static_cast<Word>(1) );
          }
        else
          current = static_cast<Word>(0);
      }
 
      const_iterator( const Self& aSet, const Key& key )
        : collection( &aSet )
      {
        auto se  = collection->my_splitter.split( key );
        it       = collection->my_elements.find( se.first );
        if ( it != collection->my_elements.cend() )
          {
            bit     = se.second;
            current = it->second & ~( (static_cast<Word>(1) << bit )
                                      - static_cast<Word>(1) );
          }
        else
          {
            bit     = static_cast<Coordinate>(0);
            current = static_cast<Word>(0);
          }
      }
 
    private:
      friend class boost::iterator_core_access;
      void increment()
      {
        ASSERT( current != static_cast<Word>(0)
                && "Invalid increment on const_iterator" );
        current &= ~( static_cast<Word>(1) << bit );
        if ( current == static_cast<Word>(0) )
          {
            ++it;
            if ( it != collection->my_elements.cend() )
              {
                current = it->second;
                bit     = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
              }
            else
              {
                current = static_cast<Word>(0);
                bit     = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
              }
          }
        else
          bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
      }
 
      bool equal( const const_iterator & other ) const
      {
        ASSERT( collection == other.collection );
        return it == other.it && bit == other.bit;
      }
 
      const Key dereference() const
      {
        return collection->my_splitter.join( it->first, bit );
      }
 
      const Self*                  collection;
      typename Container::const_iterator it;
      Coordinate                   bit;
      Word                         current;
 
    };
 
    struct iterator
      : public boost::iterator_facade< iterator, Key const,
                                       boost::forward_traversal_tag,
                                       Key const >
    {
      friend struct UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual >;
      iterator() : collection( nullptr ), it(),
                   bit( static_cast<Coordinate>(0) ),
                   current( static_cast<Word>(0) ) {}
 
      iterator( Self& aSet, typename Container::iterator anIt )
        : collection( &aSet ), it( anIt )
      {
        if ( it != collection->my_elements.end() )
          {
            current  = it->second;
            bit      = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
          }
        else
          {
            current = static_cast<Word>(0);
            bit     = static_cast<Coordinate>(0);
          }
      }
 
      iterator( Self& aSet, typename Container::iterator anIt, Coordinate aBit )
        : collection( &aSet ), it( anIt ), bit( aBit )
      {
        if ( it != collection->my_elements.end() )
          {
            current  = it->second;
            current &= ~( ( static_cast<Word>(1) << bit )
                          - static_cast<Word>(1) );
          }
        else
          current = static_cast<Word>(0);
      }
 
      iterator( Self& aSet, const Key& key )
        : collection( &aSet )
      {
        auto se  = collection->my_splitter.split( key );
        it       = collection->my_elements.find( se.first );
        if ( it != collection->my_elements.end() )
          {
            bit     = se.second;
            current = it->second & ~( (static_cast<Word>(1) << bit )
                                      - static_cast<Word>(1) );
          }
        else
          {
            bit     = static_cast<Coordinate>(0);
            current = static_cast<Word>(0);
          }
      }
 
      iterator( const const_iterator& other )
        : collection( other.collection ), it( other.it ),
          bit( other.bit ), current( other.current )
      {}
 
      iterator( const_iterator&& other )
        : collection( std::move( other.collection ) ),
          it( std::move( other.it ) ),
          bit( std::move( other.bit ) ),
          current( std::move( other.current ) )
      {}
 
      operator const_iterator() const
      {
        return const_iterator( *collection, it, bit );
      }
 
    private:
      friend class boost::iterator_core_access;
      void increment()
      {
        ASSERT( current != static_cast<Word>(0)
                && "Invalid increment on iterator" );
        current &= ~( static_cast<Word>(1) << bit );
        if ( current == static_cast<Word>(0) )
          {
            ++it;
            if ( it != collection->my_elements.end() )
              {
                current = it->second;
                bit     = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
              }
            else
              {
                current = static_cast<Word>(0);
                bit     = static_cast<Coordinate>(0); // NB: LSB(0) is undefined
              }
          }
        else
          bit = static_cast<Coordinate>(Bits::leastSignificantBit( current ));
      }
 
      bool equal( const iterator & other ) const
      {
        ASSERT( collection == other.collection );
        return it == other.it && bit == other.bit;
      }
 
      // The equality comparator with const_iterator must also be
      // provided to respect the standard that says that iterator and
      // const_iterator should always be comparable.
      bool equal( const const_iterator & other ) const
      {
        ASSERT( collection == other.collection );
        return it == other.it && bit == other.bit;
      }
 
      const Key dereference() const
      {
        return collection->my_splitter.join( it->first, bit );
      }
 
      Self*                        collection;
      typename Container::iterator it;
      Coordinate                   bit;
      Word                         current;
 
    };
 
    // ------------------------- standard services ----------------------------------
  public:
 
    UnorderedSetByBlock( size_type bucket_count = 23,
                         const Splitter & splitter = Splitter(),
                         const Hash& hash = Hash(),
                         const key_equal& equal = key_equal(),
                         const UnorderedMapAllocator& alloc = UnorderedMapAllocator())
      : my_splitter( splitter ),
        my_elements( bucket_count, hash, equal, alloc ),
        my_size( 0 ) {}
 
    ~UnorderedSetByBlock() = default;
 
    UnorderedSetByBlock( const Self& other )
      : my_splitter( other.my_splitter ),
        my_elements( other.my_elements ),
        my_size( other.my_size )
    {}
 
    UnorderedSetByBlock( Self&& other )
      : my_splitter( std::move( other.my_splitter ) ),
        my_elements( std::move( other.my_elements ) ),
        my_size( std::move( other.my_size ) )
    {}
 
    Self& operator=( const Self& other )
    {
      if ( this != &other )
        {
          my_splitter = other.my_splitter;
          my_elements = other.my_elements;
          my_size     = other.my_size;
        }
      return *this;
    }
    Self& operator=( Self&& other )
    {
      my_splitter = std::move( other.my_splitter );
      my_elements = std::move( other.my_elements );
      my_size     = std::move( other.my_size );
      return *this;
    }
 
 
    // ---------------------- iterator services -----------------------------
  public:
 
    iterator begin()
    {
      return iterator( *this, my_elements.begin() );
    }
    iterator end()
    {
      return iterator( *this, my_elements.end() );
    }
 
    const_iterator begin() const
    {
      return const_iterator( *this, my_elements.cbegin() );
    }
    const_iterator end() const
    {
      return const_iterator( *this, my_elements.cend() );
    }
 
    const_iterator cbegin() const
    {
      return const_iterator( *this, my_elements.cbegin() );
    }
    const_iterator cend() const
    {
      return const_iterator( *this, my_elements.cend() );
    }
 
 
    // ---------------------- capacity services -----------------------------
  public:
 
    bool empty() const noexcept { return my_elements.empty(); }
    size_type size() const noexcept { return my_size; }
    size_type max_size() const noexcept { return my_elements.max_size(); }
 
    size_type blocks() const noexcept { return my_elements.size(); }
 
    size_type memory_usage() const noexcept
    {
      size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
        + 2 * sizeof( size_type );
      mem += blocks() * ( sizeof( void* )       /* next */
                          + sizeof( Key )       /* key */
                          + sizeof( Word )      /* value */
                          + sizeof( size_type ) /* hash  */
                          + sizeof( void* )     /* dyn. alloc. */ );
      return mem;
    }
 
    size_type memory_usage_unordered_set() const noexcept
    {
      size_type mem = (my_elements.bucket_count()+1) * sizeof( void* )
        + 2 * sizeof( size_type );
      mem += size() * ( sizeof( void* )       /* next */
                        + sizeof( Key )       /* key */
                        + sizeof( size_type ) /* hash  */
                        + sizeof( void* )     /* dyn. alloc. */ );
      return mem;
    }
 
 
    // ---------------------- modifier services -----------------------------
  public:
 
    void clear() noexcept
    {
      my_elements.clear();
      my_size = 0;
    }
 
    void swap( Self& other ) noexcept
    {
      std::swap( my_splitter, other.my_splitter );
      std::swap( my_elements, other.my_elements );
      std::swap( my_size, other.my_size );
    }
 
    std::pair<iterator,bool> insert( const value_type& value )
    {
      const auto se = my_splitter.split( value );
      auto it = my_elements.find( se.first );
      if ( it == my_elements.end() )
        {
          auto   p = my_elements.insert
            ( std::make_pair( se.first,
                              static_cast<Word>(1) << se.second ) );
          my_size += 1;
          return std::make_pair( iterator( *this, p.first, se.second ), true );
        }
      else
        {
          bool exist = it->second & ( static_cast<Word>(1) << se.second );
          if ( ! exist )
            {
              it->second |= static_cast<Word>(1) << se.second;
              my_size    += 1;
            }
          return std::make_pair( iterator( *this, it, se.second ), ! exist );
        }
    }
 
    template<typename... _Args>
    std::pair<iterator, bool>
    emplace(_Args&&... __args)
    {
      const auto se = my_splitter.split( Key( std::forward<_Args>(__args)... ) );
      auto it = my_elements.find( se.first );
      if ( it == my_elements.end() )
        {
          auto   p =
            my_elements.insert( std::make_pair( se.first,
                                                static_cast<Word>(1) << se.second ) );
          my_size += 1;
          return std::make_pair( iterator( *this, p.first, se.second ), true );
        }
      else
        {
          bool exist = it->second & ( static_cast<Word>(1) << se.second );
          if ( ! exist )
            {
              it->second |= static_cast<Word>(1) << se.second;
              my_size    += 1;
            }
          return std::make_pair( iterator( *this, it, se.second ), ! exist );
        }
    }
 
    iterator erase( const_iterator pos ) noexcept
    {
      ASSERT( this == pos.collection );
      ASSERT( pos  != cend() );
      ASSERT( ( pos.it->second & ( static_cast<Word>(1) << pos.bit ) )
              != static_cast<Word>(0) );
      my_size -= 1;
      Word & w = const_cast< Word& >( pos.it->second );
      if ( ( w &= ~( static_cast<Word>(1) << pos.bit ) )
           == static_cast<Word>(0) )
        return iterator( *this, my_elements.erase( pos.it ) );
      else
        return iterator( *this, my_elements.erase( pos.it, pos.it ), pos.bit );
    }
 
    iterator erase( const_iterator first, const_iterator last ) noexcept
    {
      ASSERT( this == first.collection );
      ASSERT( this == last.collection );
      if ( first == cend() ) return end();
      auto itB = first.it;
      auto itE = last.it;
      Word mask = static_cast<Word>(0);
      // Take care of range over one block only
      if ( itB == itE )
        {
          while ( first != last )
            {
              mask    |= static_cast<Word>(1) << first.bit;
              my_size -= 1;
              ++first;
            }
          my_elements[ itB->first ] &= ~mask;
          return iterator( *this,
                           my_elements.find( itE->first ),
                           last.bit ); // must be valid
        }
      // Take care of first element.
      while ( first.it == itB )
        {
          mask    |= static_cast<Word>(1) << first.bit;
          my_size -= 1;
          ++first;
        }
      // Erase first block if empty
      if ( ( my_elements[ itB->first ] &= ~mask )
           == static_cast<Word>(0) )
        my_elements.erase( itB );
      // Count erased elements in main range.
      for ( itB = first.it; itB != itE; ++itB )
        my_size -= Bits::nbSetBits( itB->second );
      // Erase elements in main range
      my_elements.erase( first.it, itE );
      // Take care of last element.
      if ( itE == my_elements.cend() ) return end();
      itB   = itE;
      first = const_iterator( *this, itB );
      mask  = static_cast<Word>(0);
      while ( first != last )
        {
          mask    |= static_cast<Word>(1) << first.bit;
          my_size -= 1;
          ++first;
        }
      // Erase last block if empty
      if ( ( my_elements[ itB->first ] &= ~mask )
           == static_cast<Word>(0) )
        my_elements.erase( itB );
      return iterator( *this,
                       my_elements.find( itE->first ),
                       last.bit ); // must be valid or end.
    }
 
    size_type erase( const key_type& key )
    {
      auto it = find( key );
      if ( it != end() )
        {
          erase( it );
          return 1;
        }
      else return 0;
    }
 
 
    // ---------------------- lookup services -----------------------------
  public:
 
    iterator find( const Key& key )
    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.end() ) return end();
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      if ( exist ) return iterator( *this, it, se.second );
      else         return end();
    }
 
    const_iterator find( const Key& key ) const
    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.cend() ) return cend();
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      if ( exist ) return const_iterator( *this, it, se.second );
      else         return cend();
    }
 
    size_type count( const Key& key ) const
    {
      const auto se = my_splitter.split( key );
      const auto it = my_elements.find( se.first );
      if ( it == my_elements.cend() ) return 0;
      const bool exist = it->second & ( static_cast<Word>(1) << se.second );
      return exist ? 1 : 0;
    }
 
    std::pair<iterator,iterator>
    equal_range( const Key & key )
    {
      iterator first = find( key );
      if ( first != end() )
        {
          iterator last = first;
          return std::make_pair( first, ++last );
        }
      else return std::make_pair( first, first );
    }
 
    std::pair<const_iterator,const_iterator>
    equal_range( const Key & key ) const
    {
      const_iterator first = find( key );
      if ( first != end() )
        {
          const_iterator last = first;
          return std::make_pair( first, ++last );
        }
      else return std::make_pair( first, first );
    }
 
 
    // ---------------------- set services -------------------------
  public:
 
    bool includes( const Self& other ) const
    {
      return internal_includes_by_map_iterator( other );
    }
 
  protected:
    bool internal_includes_by_map_iterator( const Self& other ) const
    {
      auto       itMap_other    = other.my_elements.cbegin();
      const auto itEndMap_other = other.my_elements.cend();
      const auto itEndMap_this  = my_elements.cend();
      for ( ; itMap_other != itEndMap_other; ++itMap_other )
        {
          const auto itMap_this = my_elements.find( itMap_other->first );
          if ( itMap_this == itEndMap_this ) return false;
          const Word w_this  = itMap_this->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
        }
      return true;
    }
 
    bool internal_trace_includes_by_map_iterator( const Self& other ) const
    {
      trace.info() << "[trace_includes_v1] #this=" << size()
                   << " #other=" << other.size() << std::endl;
      auto       itMap_other    = other.my_elements.cbegin();
      const auto itEndMap_other = other.my_elements.cend();
      const auto itEndMap_this  = my_elements.cend();
      for ( ; itMap_other != itEndMap_other; ++itMap_other )
        {
          trace.info() << "other: cell=" << itMap_other->first
                << " value=" << std::hex << itMap_other->second << std::endl;
          const auto itMap_this = my_elements.find( itMap_other->first );
          if ( itMap_this != itEndMap_this )
            trace.info() << "this : cell=" << itMap_this->first
                  << " value=" << std::hex << itMap_this->second << std::endl;
          else
            trace.info() << "this : end cell" << std::endl;
          if ( itMap_this == itEndMap_this ) return false;
          const Word w_this  = itMap_this->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
        }
      return true;
    }
 
    bool internal_includes_by_iterator( const Self& other ) const
    {
      auto it_other  = other.cbegin();
      auto itEnd_other = other.cend();
      while ( it_other != itEnd_other )
        {
          const auto it_this = find( *it_other );
          if ( it_this == cend() ) return false;
          auto   itMap_other = it_other.it;
          const Word w_this  = it_this.it->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
          it_other = const_iterator( other, ++itMap_other );
        }
      return true;
    }
 
    bool internal_trace_includes_by_iterator( const Self& other ) const
    {
      trace.info() << "[trace_includes_v2] #this=" << size()
                   << " #other=" << other.size() << std::endl;
      auto it_other  = other.cbegin();
      auto itEnd_other = other.cend();
      while ( it_other != itEnd_other )
        {
          trace.info() << "other: cell=" << it_other.it->first
                << " value=" << std::hex << it_other.it->second << std::endl;
          const auto it_this = find( *it_other );
          if ( it_this != cend() )
            trace.info() << "this : cell=" << it_this.it->first
                  << " value=" << std::hex << it_this.it->second << std::endl;
          else
            trace.info() << "this : end cell" << std::endl;
          if ( it_this == cend() ) return false;
          auto   itMap_other = it_other.it;
          const Word w_this  = it_this.it->second;
          const Word w_other = itMap_other->second;
          if ( ( w_this & w_other ) != w_other ) return false;
          it_other = const_iterator( other, ++itMap_other );
        }
      return true;
    }
 
 
    // ---------------------- hash policy services -----------------------------
  public:
 
    void reserve( size_type block_count )
    {
      my_elements.reserve( block_count );
    }
 
 
  private:
    // -------------------------- data ---------------------------------
    Splitter  my_splitter;
    Container my_elements;
    size_type my_size;
  };
 
 
  template < typename Key,
             typename TSplitter,
             class Hash,
             class KeyEqual,
             class UnorderedMapAllocator >
  void swap
  ( UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >& s1,
    UnorderedSetByBlock< Key, TSplitter, Hash, KeyEqual, UnorderedMapAllocator >& s2 )
    noexcept
  {
    s1.swap( s2 );
  }
 
} // namespace DGtal
 
#endif // #ifndef UNORDEREDSETBYBLOCK_HPP