// search.h and namespace search - Low-level search algorithm for assembly
// puzzle solver. The puzzle is organized as a series of sites. The
// algorithm fits parts from the first empty site. So the positions of
// shapes are ordered by their starting (head) sites. The algorithm is
// is a recursive tree search. The Server class runs the algorithm, collecting
// puzzle data from the Client class and sending solutions to the Client.
// The Client here is a pure virtual class, to be implemented for particular
// puzzles. The Server class is a template, derived from the ServerBase class,
// so puzzle implementations can be independent on template specializations.
// The Server template allows for different Pos class implementations.
// Two are provided: PosVariable, which is general, and PosFixed, which is
// a template parameterized for the number of sites. PosVariable is flexible
// but PosFixed is faster, with the number of sites is fixed at compile time.

#ifndef SEARCH_H_
#define SEARCH_H_

#include "print.h"

namespace search {

// class Client - pure virtual class interface to search class Server
class Client;

// class Part - search part identified by shape, hed, pos numbers from client
class Part;

// class PosVariable - puzzle position bitmap for variable number of sites
class PosVariable;

// class PosFixed - puzzle position bitmap for fixed number of sites, nsit
template<SitId nsit> class PosFixed;

// class Hed - head site of shape; positions (POS's) starting at a site
template<class POS> class Hed;

// class Heds - ordered list of Hed<POS>'s; one Hed<POS> for each site
template<class POS> class Heds;

// class Shape - distinct puzzle piece; number of copies and Heds<POS>
template<class POS> class Shape;

// class Shapes - ordered list of Shape<POS>'s optimized for insert and delete
template<class POS> class Shapes;

// class ServerBase - pure virtual base class to search class template Server
class ServerBase;

// class Server - search server run with client; position implementation POS
template<class POS> class Server;

} // end of namespace search

namespace search {

// class Client - pure virtual class interface to search class Server
class Client {

public:

// ~Client - destructor
virtual ~Client(void) {};

// return number of sites in puzzle
virtual SitId getnsit(void) = 0;

// return number of shapes in whole puzzle
virtual int getwholeshapes(void) = 0;

// return number of parts for new shape
virtual int getshapeparts(void) = 0;

// return numbers of positions in new head site of current shape
virtual int gethedposs(void) = 0;

// return number of sites in new position of current head site
virtual int getpossits(void) = 0;

// return new site in current position
virtual SitId getsit(void) = 0;

// indicates beginning of search, end of input, beginning of output
virtual void setsol(void) = 0;

// indicates number of parts in new solution
virtual void setsolparts(int nparts) = 0;

// indicates shape, head site, site ids of new part in current solution
virtual void setsolpart(ShapeId ashapeid, SitId ahedid, SitId asitid) = 0;

}; // end of class Client

// class Part - search part identified by shape, hed, pos numbers from client
class Part {

public:

// Part - initialize with shape, hed and site ids
Part(ShapeId ashapeid = 0, SitId ahedid = 0, SitId asitid = 0);

// shapeid - shape number given by sequence of getshapeparts() calls to client
ShapeId shapeid;

// hedid - hed number given by sequence of gethedposs() calls to client
SitId hedid;

// sitid - site number given by sequence of getpossits() calls to client
SitId sitid;

// operator<< - free format print of shapeid, hedid and posid
friend std::ostream &operator<<(std::ostream &, const Part &);

}; // end of class Part

// class PosVariable - puzzle position bitmap for variable number of sites
class PosVariable {

private:

// Val - bitmap data primitive type
typedef int Val;

// bitsbits - number of bits needed to encode number of bits in Val
static const int bitsbits = 5;

// bits - number of bits in Val
static const int bits = 1 << bitsbits;

// nsit - number of sites in puzzle bitmap
SitId nsit;

// val - storage for bitmap represented as ordered set of Val's
vector<Val> val;

public:

// resize - set number of sites, nsit, to ansit
void resize(SitId ansit);

// size - return number of sites, nsit
SitId size(void) const;

// firstzero - return first empty (zeroed) site in bitmap
SitId firstzero(void) const;

// isand - return "any sites set (non-zero) in both this and src bitmaps?"
bool isand(const PosVariable &src) const;

// setor - set sites in this bitmap if set in src1 or src2, and return this
PosVariable &setor(const PosVariable &src1, const PosVariable &src);

// clear - clear (zero) bitmap, and return this
PosVariable &clear(void);

// set - set (to non-zero) site sit of bitmap and return this
PosVariable &set(SitId sit);

// get - return "is site sit set in this bitmap?" (say that 10 times fast)
bool get(SitId sit) const;

// operator<< - free format print of bitmap; "0" or "1" for site 0 to nsit-1
friend std::ostream &operator<<(std::ostream &, const PosVariable &);

}; // end of class PosVariable

// class PosFixed - puzzle position bitmap for fixed number of sites, nsit
template<SitId nsit>
class PosFixed {

private:

// Val - bitmap data primitive type
typedef int Val;

// bitsbits - number of bits needed to encode number of bits in Val
static const int bitsbits = 5;

// bits - number of bits in Val
static const int bits = 1 << bitsbits;

// words - number of Val's needed to represent bitmap
static const int words = nsit + bits - 1 >> bitsbits;

// val - storage for bitmap represented as fixed array of words Val's
Val val[words];

public:

// resize - set number of sites, nsit, to ansit
void resize(SitId ansit = 0);

// size - return number of sites, nsit
SitId size(void) const;

// firstzero - return first empty (zeroed) site in bitmap
SitId firstzero(void) const;

// isand - return "any sites set (non-zero) in both this and src bitmaps?"
bool isand(const PosFixed &src) const;

// setor - set sites in this bitmap if set in src1 or src2, and return this
PosFixed &setor(const PosFixed &src1, const PosFixed &src);

// clear - clear (zero) bitmap, and return this
PosFixed &clear(void);

// set - set (to non-zero) site sit of bitmap and return this
PosFixed &set(SitId sit);

// get - return "is site sit set in this bitmap?" (6th sheik's 6th sheep sick)
bool get(SitId sit) const;

// operator<< - free format print of bitmap; "0" or "1" for site 0 to nsit-1
template<SitId fnsit>
friend std::ostream &operator<<(std::ostream &, const PosFixed<fnsit> &);

}; // end of class PosFixed

// class Hed - head site of shape; positions (POS's) starting at a site
template<class POS>
class Hed : public vector<POS> {

}; // end of class Hed

// class Heds - ordered list of Hed<POS>'s; one Hed<POS> for each site
template<class POS>
class Heds : public vector<Hed<POS> > {

}; // end of class Heds

// class Shape - distinct puzzle piece; number of copies and Heds<POS>
template<class POS>
class Shape {

public:

// n - number of available parts in puzzle with this shape
int n;

// shapeid - identifier of this shape in some Shapes
ShapeId shapeid;

// heds - set of positions this shape may occupy, ordered by head site
Heds<POS> heds;

// Shape - initialize with an and ashapeid
Shape(int an = 0, int ashapeid = 0);

// getshapeid - return shapeid
ShapeId getshapeid(void);

// pick - return number of parts of this shape available after picking one
int pick(void);

// place - return number of parts of this shape available before placing one
int place(void);

// operator<< - free format print of n, shapeid and heds
template<class FPOS>
friend std::ostream &operator<<(std::ostream &, const Shape<FPOS> &);

}; // end of class Shape

// class Shapes - ordered list of Shape<POS>'s optimized for insert and delete
template<class POS>
class Shapes : public list<Shape<POS> > {

}; // end of class Shapes

// class ServerBase - pure virtual base class to search class template Server
class ServerBase {

public:

// ~ServerBase - destructor
virtual ~ServerBase(void) {}

// run - run search for puzzle input from & solution output to Client *apclient
virtual void run(Client *apclient) = 0;

}; // end of class ServerBase

// class Server - search server run with client; position implementation POS
template<class POS>
class Server : public ServerBase {

private:

// pclient - pointer to server's client
Client *pclient;

// shapes - list of available shapes, yet to be fit in solution
Shapes<POS> shapes;

// empties - list of empty shapes, all copies fitted in solution
Shapes<POS> empties;

// solution - ordered set of Part's, holds current path in search tree
vector<Part> solution;

// loadshape - add shape with ipart, shapeid to shapes, get contents from client
Shape<POS> loadshape(int ipart, ShapeId shapeid);

// load - get shapes from client, return number of parts
int load(void);

// pick - pick one part with shape *iter on shapes list
// if no parts of this shape left AFTER picking, save in next the spot
// in shapes following *iter then move *iter to the empties list
void pick(typename Shapes<POS>::iterator &iter,
		typename Shapes<POS>::iterator &next);

// place - place one part with shape *iter on the shapes list
// if no parts of this shape in shapes BEFORE picking, move *iter
// from empties list to the shapes list in the spot preceding *next
void place(typename Shapes<POS>::iterator &iter,
		typename Shapes<POS>::iterator &next);

// run - run step of search, from i, the end of parts fitted into
// solution, and pos, the bitmap of parts fitted.
// if i is at the end of solution, then set solution to client,
// otherwise, search the currently available (unfitted) set of parts
// that start from the head site of the first empty (zero) site
// in pos. for part that fits, save the fitted part in solution and the
// bitmap and call this function recursively.
void run(vector<Part>::iterator i, const POS &pos);

// clear - clear internal lists, shapes, empties and solution
void clear(void);

public:

// run - run search for puzzle input from & solution output to Client *apclient
void run(Client *apclient);

// operator<< - free format print of shapes, empties and solution
template<class FPOS>
friend std::ostream &operator<<(std::ostream &, const Server<FPOS> &);

}; // end of class Server

} // end of namespace search

#endif // end SEARCH_H_