Program Listing for File DancingLinks.h

↰ Return to documentation for file (ADS/backtrack/DancingLinks.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File DancingLinks.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

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

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS ExactCover -----------------------------*/
/*--------------------------------------------------------------------------*/

class ExactCover {

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

 ExactCover( int primary , int secondary = 0 );

 int addOption( const std::vector< int > & items );

 template< class F >
 long solve( F && visit );

 [[nodiscard]] long updates( void ) const { return( f_updates ); }

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

 void cover( int i );
 void uncover( int i );
 void hide( int p );
 void unhide( int p );

 [[nodiscard]] bool exact( const std::vector< int > & options ) const;

 int f_primary , f_items;
 std::vector< int > f_L , f_R;
 std::vector< int > f_U , f_D , f_top;
 std::vector< int > f_len;
 std::vector< int > f_option;
 std::vector< std::vector< int > > f_options;
 long f_updates = 0;

 };  // end( class ExactCover )

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

}  // end( namespace ADS )

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

#include "ADS/backtrack/impl/DancingLinks.tpp"

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

#endif  /* DancingLinks.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File DancingLinks.h -------------------------*/
/*--------------------------------------------------------------------------*/