Program Listing for File Grid.h

↰ Return to documentation for file (ADS/graph/Grid.h)

/*--------------------------------------------------------------------------*/
/*------------------------------ File Grid.h -------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/graph/Visit.h"

#include <array>
#include <cstddef>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

using GridCell = std::pair< int , int >;

inline constexpr std::array< GridCell , 4 > FOUR_MOVES = {
 GridCell( -1 , 0 ) , GridCell( 0 , -1 ) , GridCell( 1 , 0 ) ,
 GridCell( 0 , 1 ) };

inline constexpr std::array< GridCell , 8 > EIGHT_MOVES = {
 GridCell( -1 , -1 ) , GridCell( -1 , 0 ) , GridCell( -1 , 1 ) ,
 GridCell( 0 , -1 ) , GridCell( 0 , 1 ) , GridCell( 1 , -1 ) ,
 GridCell( 1 , 0 ) , GridCell( 1 , 1 ) };

inline constexpr std::array< GridCell , 8 > KNIGHT_MOVES = {
 GridCell( -2 , -1 ) , GridCell( -2 , 1 ) , GridCell( -1 , -2 ) ,
 GridCell( -1 , 2 ) , GridCell( 1 , -2 ) , GridCell( 1 , 2 ) ,
 GridCell( 2 , -1 ) , GridCell( 2 , 1 ) };

using FourMoves = std::remove_cv_t< decltype( FOUR_MOVES ) >;

/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

inline bool insideGrid( int rows , int cols , GridCell x );

template< class Free , class Moves = FourMoves >
std::vector< std::vector< int > > gridDistances( int rows , int cols ,
                                    const std::vector< GridCell > & sources ,
                                    Free && free ,
                                    const Moves & moves = FOUR_MOVES );

template< class Free , class Moves = FourMoves >
int gridDistance( int rows , int cols , GridCell s , GridCell t ,
                  Free && free , const Moves & moves = FOUR_MOVES );

template< class T , class Moves = FourMoves >
std::size_t floodFill( std::vector< std::vector< T > > & M , int r , int c ,
                       const std::type_identity_t< T > & color ,
                       const Moves & moves = FOUR_MOVES );

inline int knightDistance( int n , GridCell s , GridCell t );

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

}  // end( namespace ADS )

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

#include "ADS/graph/impl/Grid.tpp"

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

#endif  /* Grid.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File Grid.h -----------------------------*/
/*--------------------------------------------------------------------------*/