Program Listing for File PositionIndex.h

↰ Return to documentation for file (ADS/dictionary/PositionIndex.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File PositionIndex.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_PositionIndex
 #define __ADS_PositionIndex
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/dictionary/FastHash.h"
#include "ADS/dictionary/FlatHashTable.h"

#include <algorithm>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <memory>
#include <ranges>
#include <span>
#include <stdexcept>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS PositionIndex ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class H = FastHash< const T * > >
class PositionIndex {

/*--------------------------------------------------------------------------*/
 public:

 using Position = std::uint32_t;

 static constexpr Position NONE = std::numeric_limits< Position >::max();

 explicit PositionIndex( std::size_t n = 0 , H h = H() )
  : f_table( n , std::move( h ) ) {}

/*--------------------------------------------------------------------------*/

 [[nodiscard]] Position find( const T * p ) const;

 [[nodiscard]] bool contains( const T * p ) const;

 bool insert( const T * p , Position i );

 bool erase( const T * p );

 template< std::ranges::random_access_range R >
 void assign( const R & v );

 void renumber( std::span< const Position > E );

 [[nodiscard]] std::size_t size( void ) const { return( f_table.size() ); }

 [[nodiscard]] bool empty( void ) const { return( f_table.empty() ); }

 [[nodiscard]] std::size_t capacity( void ) const {
  return( f_table.capacity() );
  }

 void reserve( std::size_t n ) { f_table.reserve( n ); }

 void clear( void ) { f_table.clear(); }

 template< class F >
 void forEach( F && f ) const { f_table.forEach( f ); }

 void swap( PositionIndex & o ) noexcept {
  f_table.swap( o.f_table );
  f_words.swap( o.f_words );
  f_drop.swap( o.f_drop );
  }

/*--------------------------------------------------------------------------*/
 private:

 struct Word {
  std::uint64_t bits;
  Position rank;
  };

 FlatHashTable< const T * , Position , H > f_table;
 std::vector< Word > f_words;
 std::vector< const T * > f_drop;

 };  // end( class PositionIndex )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/dictionary/impl/PositionIndex.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* PositionIndex.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File PositionIndex.h ------------------------*/
/*--------------------------------------------------------------------------*/