Program Listing for File ListRanking.h

↰ Return to documentation for file (ADS/external/ListRanking.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File ListRanking.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

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

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

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

namespace ADS {

[[nodiscard]] inline bool isList( const std::vector< std::size_t > & succ );

[[nodiscard]] inline std::vector< std::size_t > listRank(
                                    const std::vector< std::size_t > & succ );

[[nodiscard]] inline std::vector< std::size_t > listRankPointerJumping(
                                    const std::vector< std::size_t > & succ ,
                                    std::size_t * rounds = nullptr );

template< class R >
std::vector< bool > randomIndependentSet(
                          const std::vector< std::size_t > & succ , R & g );

[[nodiscard]] inline std::vector< int > deterministicCoinTossing(
                                    const std::vector< std::size_t > & succ ,
                                    std::size_t * rounds = nullptr );

[[nodiscard]] inline std::vector< bool > independentSetOfColors(
                                    const std::vector< std::size_t > & succ ,
                                    const std::vector< int > & color );

template< class R >
std::vector< std::size_t > listRankIndependentSet(
                                    const std::vector< std::size_t > & succ ,
                                    R & g , bool deterministic = false ,
                                    std::size_t * levels = nullptr );

template< class T , class Op >
void parallelStep( const DiskFile< T > & A ,
                   const DiskFile< std::pair< std::size_t , std::size_t > > &
                                                                         ops ,
                   Op op , DiskFile< T > & out );

inline void externalPointerJumping( const DiskFile< std::size_t > & succ ,
                                    DiskFile< std::size_t > & rank ,
                                    std::size_t * rounds = nullptr );

template< class R >
void externalListRank( const DiskFile< std::size_t > & succ ,
                       DiskFile< std::size_t > & rank , R & g ,
                       std::size_t * levels = nullptr );

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

}  // end( namespace ADS )

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

#include "ADS/external/impl/ListRanking.tpp"

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

#endif  /* ListRanking.h included */

/*--------------------------------------------------------------------------*/
/*------------------------- End File ListRanking.h -------------------------*/
/*--------------------------------------------------------------------------*/