// puzzle.h and namespace puzzle - Higher-level abstraction of assembly puzzle
// solver in which maps are used to avoid reporting redundancies. In most cases,
// puzzle solutions are considered redundant if they are related by trivial
// transformations, such as rotating the solved puzzle. Here the position of
// parts in solutions are also managed and redundancies eliminated.
// The user will instantiate the Puzzle class here and provide shapes, maps
// and a search::Server to carry out the search. The results are solutions,
// which are lists of lists for part ids, and parts, which are indexed by part
// ids. Alternatively, the part ids index map parts, which indicate a map and
// mapped part. None of the solutions are related by any output maps and
// none of the mapped parts are related by any input maps. Also, input maps are
// applied to positions of the shapes. For convenience, the closure of the input
// and output maps are used.
// The strategy here is to generate and store redundant solutions by applying
// the output maps to each new solution as soon as it is produced by the search
// algorithm. When that algorithm finds a redundant solution it is already on
// the list and ignored. The position of parts and their output mappings are
// also stored, by the PosMapper class, so that a solution is a list of position
// identifiers, rather positions, which are lists of locations. The position
// of parts and their input mappings is managed by the PartMapper class, in
// order to provide mapped parts.

#ifndef PUZZLE_H_
#define PUZZLE_H_

#include "search.h"
#include "aps.h"

namespace puzzle {

// typedef PosIdId - id of a PosId
typedef int PosIdId;

// typedef PosIdsId - id of a PosIds
typedef int PosIdsId;

// typedef MapPosId - id of a MapPos
typedef int MapPosId;

// typedef PosMapId - id of a PosMap
typedef int PosMapId;

// class Posdb - a database of Pos's
class Posdb;

// class PosIds - an ordered set of PosId's
class PosIds;

// class PosIdDb - a database of PosId's
class PosIdDb;

// class PosIdsDb - a database of PosIds's
class PosIdsDb;

// class PosMap - part with mapped positions identified
class PosMap;

// class PosMaps - an ordered set of PosMap's
class PosMaps;

// class PosMapIds - an ordered set of PosMapId's
class PosMapIds;

// Hed - ids of PosMap's related by head location; an ordered set of PosMapId's
class Hed;

// Heds - an ordered set of Hed's, one for each starting location
class Heds;

// class Shape - distinct puzzle piece; number of copies and Heds
class Shape;

// Shapes - an ordered set of Shape's
class Shapes;

// class PosMapper - manage position mappings; identify new solutions
class PosMapper;

// PartMapper - manage part mappings; identify new parts
class PartMapper;

// class Puzzle - puzzle with mapping redundancies suppressed, and search client
class Puzzle;

} // end of namespace puzzle

namespace puzzle {

// class Posdb - a database of Pos's
class Posdb : public Db<Pos,PosId> {

}; // end of class Posdb

// class PosIds - an ordered set of PosId's
class PosIds : public vector<PosId> {

public:

// PosIds - initialize with n PosId's
PosIds(int n = 0);

}; // end of class PosIds

// class PosIdDb - a database of PosId's
class PosIdDb : public Db<PosId,PosIdId> {

}; // end of class PosIdDb

// class PosIdsDb - a database of PosIds's
class PosIdsDb : public Db<PosIds,PosIdsId> {

}; // end of class PosIdsDb

// class PosMap - Part with mapped positions identified
class PosMap {

public:

// part - unmapped part with this position
Part part;

// posids - ids of positions after mapping
PosIds posids;

// PosMap - initialize with apart; posids initially empty
PosMap(Part apart = Part());

// operator<< - free format print of part and posids
friend std::ostream &operator<<(std::ostream &, const PosMap &);

}; // end of class PosMap

// class PosMaps - an ordered set of PosMap's
class PosMaps : public vector<PosMap> {

}; // end of class PosMaps

// class PosMapIds - an ordered set of PosMapId's
class PosMapIds : public vector<PosMapId>
{

public:

// PosMapIds - initialize with n PosMapId's
PosMapIds(int n = 0);

}; // end of class PosMapIds

// Hed - ids of PosMap's related by head location; an ordered set of PosMapId's
class Hed : public PosMapIds {

public:

// Hed - initialize with n PosMapId's
Hed(int n = 0);

}; // end of class Hed

// Heds - an ordered set of Hed's, one for each starting location
class Heds : public vector<Hed> {

public:

// Heds - initialize with n Hed's
Heds(int n = 0);

}; // end of class Heds

// class Shape - distinct puzzle piece; number of copies and Heds
class Shape {

public:

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

// heds - Part and mapping information, grouped by starting location
Heds heds;

// Shape - initialize with n parts of this shape
Shape(int n = 0);

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

}; // end of class Shape

// Shapes - an ordered set of Shape's
class Shapes : public vector<Shape> {

public:

// Shapes - initialize with n Shape's
Shapes(int n = 0);

}; // end of class Shapes

// class PosMapper - manage position mappings; identify new solutions
class PosMapper {

private:

// outputmaps - closed set of maps which identify solutions that are not new
Maps outputmaps;

// posdb - database of added positions and their mappings
Posdb posdb;

// posidsdb - database of added solutions and their mappings
PosIdsDb posidsdb;

// posmaps - ordered set of all PosMap's
PosMaps posmaps;

// makeposids - fill posids for pos mapped by outputmaps
void makeposids(PosIds &posids, const Pos &pos);

public:

// setoutputmaps - set outputmaps to closure of maps
void setoutputmaps(const Maps &maps);

// add - return PosMapId of new PosMap for part
PosMapId add(const Part &part);

// getpart - return Part in PosMap for posmapid
Part &getpart(PosMapId posmapid);

// getposid - return the ith PosId in PosMap for posmapid
PosId getposid(PosMapId posmapid, int i = 0);

// isnew - return "are posmapids a new solution? not a mapping of old?"
bool isnew(const PosMapIds &posmapids);

}; // end of class PosMapper

// PartMapper - manage part mappings; identify new parts
class PartMapper {

// inputmaps - closed set of maps which identify parts that are not new
Maps inputmaps;

// mappingposdb - database of added positions (and their mappings)
Posdb mappingposdb;

// mappingparts - ordered set of added positions (and their mappings)
MapParts mappingparts;

// mapparts - ordered set of added parts (map ids and mappedpart ids)
MapParts mapparts;

// mappedparts - ordered set of new parts (not mappings of old)
Parts mappedparts;

// savemappedpart - save a new mapped part; save its smallest mapped position
void savemappedpart(const Part &part);

// savemappingpart - save MapPart of poss[i] if new
void savemappingpart(const Poss &poss, int i);

public:

// setoutputmaps - set inputmaps to closure of maps
void setinputmaps(const Maps &maps);

// map - return poss mapped by inputmaps
Poss map(const Poss &poss) const;

// add - add part to mapparts and, if new, to mappedparts
void add(const Part &part);

// getmapparts - return mapparts, ordered set of added parts
MapParts &getmapparts(void);

// getmappedparts - retyurn mappedparts, order set of new parts
Parts &getmappedparts(void);

}; // end of class PartMapper

// class Puzzle - puzzle with mapping redundancies suppressed, and search client
class Puzzle : public search::Client {

private:

// nsit - number of (filled) sites in puzzle
SitId nsit;

// nloc - number of (filled and unfilled) locations in puzzle
LocId nloc;

// pos - occupiable (filled) locations in puzzle
Pos pos;

// sitemap - given location, map to site
Map sitemap;

// shapes - shapes data; intermediate form between ::Shapes and search::Shapes
Shapes shapes;

// ishapes - shape index for getshapeparts()
Shapes::const_iterator ishapes;

// ishape - index of heds for gethedposs()
Heds::const_iterator ishape;

// ihed - position index for getposlocs()
Hed::const_iterator ihed;

// ipos - location index for getloc()
Pos::const_iterator ipos;

// posmapids - PosMapId's of solution
PosMapIds posmapids;

// iposmapids - index of PosMapId's for setsolpart()
PosMapIds::iterator iposmapids;

// posmapper - manager of position mappings to identify new solutions
PosMapper posmapper;

// partmapper - manager of part mappings to identify new parts in solutions
PartMapper partmapper;

// solutions - ordered set of solutions; which are ordered sets of part ids
PartIdss solutions;

// posiddb - database of positions, parts
PosIdDb posiddb;

// parts - ordered set of parts, identified by solutions
Parts parts;

// loadshape - load from src to internal dst, with shapeid, return nparts
int loadshape(Shape &dst, const ::Shape &src, ShapeId shapeid);

// initsitemap - make map of locations to sites
void initsitemap(const Pos &pos);

// savesol - save solution in posmapids, if new
void savesol(void);

public:

// Puzzle - initialize with anloc locations
Puzzle(LocId anloc);

// setpos - initialize nsit, pos, sitemap, partmapper, posmapper
void setpos(const Pos &apos);

// setmaps - set input and output maps with closure of maps
void setmaps(const Maps &maps);

// setinputmaps - set inputmaps with closure of maps, cull redundant parts
void setinputmaps(const Maps &maps);

// setoutputmaps - set outputmaps with closure of maps, cull redundant solutions
void setoutputmaps(const Maps &maps);

// setshapes - set the puzzle's shapes to external inputshapes
// map positions of inputshapes with inputmaps
void setshapes(const ::Shapes &inputshapes);

// search - run the search on server
void search(search::ServerBase &server);

// getsolutions - return solutions, suppressing redundant mappings of outputmaps
PartIdss &getsolutions(void);

// getparts - return parts referenced in PartIdss of getsolutions()
Parts &getparts(void);

// getmapparts - return mapparts; parts in terms of inputmaps and mappedparts
MapParts &getmapparts(void);

// getmappedparts - return mappedparts; inputmaps redundancies suppressed
Parts &getmappedparts(void);

public: // search::Client interface

virtual SitId getnsit(void);
virtual int getwholeshapes(void);
virtual int getshapeparts(void);
virtual int gethedposs(void);
virtual int getpossits(void);
virtual SitId getsit(void);

virtual void setsol(void);
virtual void setsolparts(int nparts);
virtual void setsolpart(ShapeId shapeid, SitId hedid, SitId sitid);

}; // end of class Puzzle

} // end of namespace puzzle

#endif // end of PUZZLE_H_