Program Listing for File SortedIntersection.h

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

/*--------------------------------------------------------------------------*/
/*----------------------- File SortedIntersection.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/external/TwoLevelMemory.h"
#include "ADS/search/BinarySearch.h"
#include "ADS/sort/Sorted.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <utility>
#include <vector>

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

namespace ADS {

template< class T , class C = std::less<> >
std::vector< T > intersectMerge( const std::vector< T > & A ,
                                 const std::vector< T > & B , C less = C() );

template< class T , class C = std::less<> >
std::vector< T > intersectBinarySearch( const std::vector< T > & A ,
                                        const std::vector< T > & B ,
                                        C less = C() );

template< class T , class C = std::less<> >
std::vector< T > intersectMutualPartition( const std::vector< T > & A ,
                                           const std::vector< T > & B ,
                                           C less = C() );

template< class T , class C = std::less<> >
std::vector< T > intersectDoubling( const std::vector< T > & A ,
                                    const std::vector< T > & B ,
                                    C less = C() );

template< class T , class C = std::less<> >
std::vector< T > intersectTwoLevel( const std::vector< T > & A ,
                                    const std::vector< T > & B ,
                                    std::size_t L , C less = C() );

template< class T >
void twoLevelHeaders( const DiskFile< T > & A , std::size_t L ,
                      DiskFile< T > & H );

template< class T , class C = std::less<> >
void intersectMergeExternal( const DiskFile< T > & A ,
                             const DiskFile< T > & B , DiskFile< T > & out ,
                             C less = C() );

template< class T , class C = std::less<> >
void intersectTwoLevelExternal( const DiskFile< T > & A ,
                                const DiskFile< T > & H , std::size_t L ,
                                const DiskFile< T > & B ,
                                DiskFile< T > & out , C less = C() );

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS PermutedBuckets --------------------------*/
/*--------------------------------------------------------------------------*/

class PermutedBuckets {

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

 PermutedBuckets( const std::vector< std::uint64_t > & A , unsigned w ,
                  std::size_t L , std::uint64_t a , std::uint64_t c );

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

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

 [[nodiscard]] std::vector< std::uint64_t > intersect(
                                     const PermutedBuckets & other ,
                                     std::size_t * scanned = nullptr ) const;

 [[nodiscard]] std::vector< std::uint64_t > values( void ) const;

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

 [[nodiscard]] std::uint64_t mask( void ) const;

 [[nodiscard]] std::uint64_t permute( std::uint64_t x ) const;

 [[nodiscard]] std::uint64_t invert( std::uint64_t y ) const;

 unsigned f_w;
 unsigned f_ell;
 std::uint64_t f_a , f_c;
 std::uint64_t f_ainv;
 std::vector< std::uint64_t > f_img;
 std::vector< std::size_t > f_off;

 };  // end( class PermutedBuckets )

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

}  // end( namespace ADS )

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

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

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

#endif  /* SortedIntersection.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File SortedIntersection.h ---------------------*/
/*--------------------------------------------------------------------------*/