Program Listing for File MultiwayMerge.h

↰ Return to documentation for file (ADS/priority/MultiwayMerge.h)

/*--------------------------------------------------------------------------*/
/*------------------------- File MultiwayMerge.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/sort/Sorted.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iterator>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

namespace detail {

template< class T , class C >
inline constexpr bool kNaturalOrder =
 std::is_arithmetic_v< T > &&
 ( std::is_same_v< C , std::less<> > || std::is_same_v< C , std::less< T > >
   || std::is_same_v< C , std::greater<> > ||
   std::is_same_v< C , std::greater< T > > );

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS FlatLoserTree ---------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class C = std::less<> >
class FlatLoserTree {

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

 explicit FlatLoserTree( std::size_t k , C less = C() );

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

 void start( std::size_t s , const T & x );

 void build( void );

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

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

 [[nodiscard]] const T & top( void ) const;

 void replaceTop( const T & x );

 void exhaustTop( void );

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

 static constexpr bool kNatural = detail::kNaturalOrder< T , C >;

 static constexpr bool kInteger = kNatural && std::is_integral_v< T > &&
                                  ! std::is_same_v< T , bool > &&
                                  ( sizeof( T ) <= 8 );

 static constexpr bool kUp = std::is_same_v< C , std::less<> > ||
                             std::is_same_v< C , std::less< T > >;

 static constexpr bool kByValue = std::is_trivially_copyable_v< T > &&
                                  ( sizeof( T ) <= 16 ) &&
                                  std::is_default_constructible_v< T >;

 using Key = std::conditional_t< kByValue , T , const T * >;

 static constexpr std::uint32_t kSup = std::uint32_t( 1 ) << 31;

 struct Node {
  Key key;
  std::uint32_t src;
  };

 static const T & keyOf( const Node & a );

 static T supKey( void );

 [[nodiscard]] bool beats( const Node & a , const Node & b ) const;

 void replay( Node cur );

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

 std::size_t f_k;
 std::size_t f_K;
 std::vector< Node > f_node;
 std::vector< Node > f_leaf;
 C f_less;

 };  // end( class FlatLoserTree )

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

template< class I , class O , class C = std::less<> >
O multiwayMerge( const std::vector< std::pair< I , I > > & R , O out ,
                 C less = C() );

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

}  // end( namespace ADS )

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

#include "ADS/priority/impl/MultiwayMerge.tpp"

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

#endif  /* MultiwayMerge.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File MultiwayMerge.h ------------------------*/
/*--------------------------------------------------------------------------*/