Program Listing for File BoolSet.h

↰ Return to documentation for file (ADS/set/BoolSet.h)

/*--------------------------------------------------------------------------*/
/*----------------------------- File BoolSet.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/Iterators.h"

#include <algorithm>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <optional>
#include <memory>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

#if defined( __AVX2__ )
 #include <immintrin.h>
#endif

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

namespace ADS {

namespace detail {

template< class T >
struct UninitAllocator : std::allocator< T > {
 template< class U > struct rebind { using other = UninitAllocator< U >; };
 UninitAllocator( void ) = default;
 template< class U >
 UninitAllocator( const UninitAllocator< U > & ) noexcept {}
 template< class U >
 void construct( U * p ) noexcept( std::is_nothrow_default_constructible_v<
                                    U > ) {
  ::new( static_cast< void * >( p ) ) U;
  }
 template< class U , class... Args >
 void construct( U * p , Args &&... args ) {
  ::new( static_cast< void * >( p ) ) U( std::forward< Args >( args )... );
  }
 };

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS BoolSet ------------------------------*/
/*--------------------------------------------------------------------------*/

class BoolSet {

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

 using Item = long;

 explicit BoolSet( long N );

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] long dim( void ) const;

 [[nodiscard]] bool contains( long x ) const;

 void insert( long x );

 void remove( long x );

 [[nodiscard]] std::optional< long > min( void ) const;

 [[nodiscard]] std::optional< long > max( void ) const;

 template< class F >
 void forEach( F && f ) const;

/*------------------------- THE STANDARD INTERFACE -------------------------*/

 // a constant view of the items in increasing order, bidirectional; an
 // item is computed from its bit

 struct Places {
  static std::size_t size( const auto & o ) { return( o.f_N ); }
  static bool occupied( const auto & o , std::size_t i ) {
   return( ( o.f_W[ i / 64 ] >> ( i % 64 ) ) & 1 );
   }
  static auto read( const auto & , std::size_t i ) {
   return( long( i ) );
   }
  };

 using value_type = long;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;
 using reference = long;
 using const_reference = long;
 using const_iterator = SlotIterator< BoolSet , Places >;
 using iterator = const_iterator;

 [[nodiscard]] const_iterator begin( void ) const {
  return( const_iterator( this , 0 ) );
  }
 [[nodiscard]] const_iterator end( void ) const {
  return( const_iterator( this , Places::size( *this ) ) );
  }
 [[nodiscard]] const_iterator cbegin( void ) const { return( begin() ); }
 [[nodiscard]] const_iterator cend( void ) const { return( end() ); }

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

 [[nodiscard]] bool counted( void ) const;

 template< class Op >
 static void combine( BoolSet & C , const BoolSet & A , const BoolSet & B ,
                      Op op );

 friend BoolSet setUnion( const BoolSet & A , const BoolSet & B );
 friend BoolSet setIntersection( const BoolSet & A , const BoolSet & B );
 friend BoolSet setDifference( const BoolSet & A , const BoolSet & B );
 friend BoolSet setSymmetricDifference( const BoolSet & A ,
                                        const BoolSet & B );

 struct Raw {};
 BoolSet( long N , Raw );

 std::vector< std::uint64_t , detail::UninitAllocator< std::uint64_t > > f_W;
 std::size_t f_N = 0;
 std::size_t f_size = 0;

 };  // end( class BoolSet )

inline BoolSet setUnion( const BoolSet & A , const BoolSet & B );

inline BoolSet setIntersection( const BoolSet & A , const BoolSet & B );

inline BoolSet setDifference( const BoolSet & A , const BoolSet & B );

inline BoolSet setSymmetricDifference( const BoolSet & A ,
                                       const BoolSet & B );

}  // end( namespace ADS )

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

#include "ADS/set/impl/BoolSet.tpp"

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

#endif  /* BoolSet.h included */

/*--------------------------------------------------------------------------*/
/*--------------------------- End File BoolSet.h ---------------------------*/
/*--------------------------------------------------------------------------*/