Program Listing for File FastExactCover.h

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

/*--------------------------------------------------------------------------*/
/*------------------------- File FastExactCover.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <algorithm>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS FastExactCover ---------------------------*/
/*--------------------------------------------------------------------------*/

class FastExactCover {

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

 FastExactCover( int primary , int secondary = 0 );

 int addOption( const std::vector< int > & items ,
                const std::vector< int > & colors = {} );

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

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

 [[nodiscard]] long nodes( void ) const { return( f_nodes ); }

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

 struct Node {
  int item;
  int loc;
  int color;
  int pad;
  };

 struct Item {
  int start , size , pos , pad;
  };

 void build( void );
 bool hide( int c , int color , bool check );

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

 int f_primary , f_items;
 std::vector< std::vector< int > > f_options , f_colors;

 std::vector< Node > f_node;
 std::vector< Item > f_item;
 std::vector< int > f_set , f_active , f_force;
 int f_nActive = 0 , f_oActive = 0;
 long f_updates = 0 , f_nodes = 0;

 };  // end( class FastExactCover )

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

}  // end( namespace ADS )

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

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

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

#endif  /* FastExactCover.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File FastExactCover.h -----------------------*/
/*--------------------------------------------------------------------------*/