// aps.h - Assembly Puzzle Solver utility layer
// This layer provides management and transforms for puzzles and solutions.
// A puzzle is represented as a set of locations and a set of shapes.
// A position is a subset of puzzle locations.
// A Map is used to perform various mathematical mappings.
// A shape has a set of positions, related by maps.
// A shape has a number of copies required for a solution.
// A solution is comprised of all the required numbers of copies of shapes.
// A part is a particular copy of a shape in a particular position.
// A solution consists of parts.
// A solution has no location occupied by two parts.
// A solution may have locations not occupied by any parts.
// A shape may have positions that do not occur in any solutions.

#ifndef APS_H_
#define APS_H_

#include <string>
#include <algorithm>
#include "print.h"

// typedef SitId - id of a site (filled during search)
typedef int SitId;

// typedef LocId - id of a location (within the puzzle body)
typedef int LocId;

// typedef ShapeId - id of a shape, a distinct shape used to assemble puzzle
typedef int ShapeId;

// typedef PartId - id of a part, one of several shapes in a puzzle solution
typedef int PartId;

// typedef PosId - id of a position, a set of locations occupied by a part
typedef int PosId;

// typedef MapId - id of a map, used to map (reposition) a position or map
typedef int MapId;

// class Db - simple database index of keys for records
template<class RECORD, class KEY> class Db;

// class Pos - a position, a set of locations occupied by a part or shape
class Pos;

// Map - used to map (reposition) a position or another map
class Map;

// class Poss - an ordered set of Pos's
class Poss;

// class Maps - an ordered set of Map's
class Maps;

// class Shape - a puzzle piece with a distinct set of positions it may occupy
class Shape;

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

// class Part - a puzzle piece, a shape, that occupies a particular position
class Part;

// class Parts - an ordered set of Part's
class Parts;

// class PartIds - an ordered set of PartId's
class PartIds;

// class PartIdss - an ordered set of PartIds's
class PartIdss;

// class MapPart - indirectly represented Part, whose Pos is remapped by a Map
class MapPart;

// class MapParts - an ordered set of MapPart's
class MapParts;

// sort - return sorted copy of src
template<class T>
T sort(const T &src);

template<class T>
T set_difference(const T &set, const T &subset);

// next_permutation - make next permutation in lexicographical order of data
// between first and last (excluding last),
// return iterator to last first datum changed.
// on last permutation (data in reverse order), return last
template<class IT>
IT next_permutation(IT first, IT last);

// class Db - simple database index of keys for records
template<class RECORD, class KEY>
class Db {

private:

// nextkey - key to be assigned to next new record
KEY nextkey;

// dbmap - STL map container, but with RECORD as the container key and
// KEY as the container data
map<RECORD,KEY> dbmap;

public:

// Db - initialize database index with anextkey
Db(KEY anextkey = 0);

// getnextkey - return nextkey
KEY getnextkey(void) const;

// return key of record; if record is new, return and increment nextkey
KEY set(const RECORD &record);

// return "is this record new?" ("first time this record presented?")
bool isnew(const RECORD &record);

// operator<< - free format print of nextkey and map
template<class FRECORD, class FKEY>
friend std::ostream &operator<<(std::ostream &, const Db<FRECORD,FKEY> &);

}; // end of class Db

// class Pos - a position, a set of locations occupied by a part or shape
class Pos : public vector<LocId> {

public:

// Pos - initialize with n locations
Pos(int n = 0);

// Pos - initialize with data between first and last, excluding last
template<class InputIterator>
Pos(InputIterator first, InputIterator last);

// Pos - initialize with LocIds v
Pos(const vector<LocId> &v);

// add - add sorted rhs locations to this Pos's sorted locations
Pos &add(const Pos &rhs);

// includes - return "does this Pos include all locations of rhs Pos?
bool includes(const Pos &rhs);

}; // end of class Pos

// Map - used to map (reposition) a position or another map
class Map : public vector<LocId> {

private:

// operator* - return rhs remapped by this Map
template<class T>
T operator*(const T &rhs) const;

// issymmetric - return "does rhs map onto itself by this Map?"
template<class T>
bool issymmetric(const T &rhs) const;

public:

// initialize identity map with n elements
Map(int n = 0);

// Map - initialize with data between first and last, excluding last
template<class InputIterator>
Map(InputIterator first, InputIterator last);

// make this its inverse map with n elements
Map &inverse(int n);

// operator* - return rhs remapped by this Map
Pos operator*(const Pos &rhs) const;

// operator* - return rhs remapped by this Map
Map operator*(const Map &rhs) const;

// issymmetric - return "does rhs map onto itself by this Map?"
bool issymmetric(const Pos &rhs) const;

// rev - reverse in place elements of this Map and return it,
// beginning at start and extending for len elements
// rev(start) is through the end of the map; rev() is the entire map
Map &rev(int start = 0, int len = -1);

// rot - rotate in place elements of this Map and return it
// rotate "right" number of elements from old map to new
// beginning at start and extending for len elements
// rot(right, start) is through end of the map; rot(right) is entire map
// rot() is one element to the right for entire map
Map &rot(int right = 1, int start = 0, int len = -1);

// nestlist - return Maps of 0 to n iterations of this Map
// 0th map is identity, 1st map is this Map
// ith map is i-1st map remapped by this Map
Maps nestlist(int n) const;

}; // end of class Map

// class Poss - an ordered set of Pos's
class Poss : public vector<Pos> {

public:

// Poss - initialize with n Pos's
Poss(int n = 0);

// Poss - initialize with a single pos
Poss(const Pos &pos);

// append - append poss to these Poss and return them
Poss &append(const Poss &poss);

}; // end of class Poss

// class Maps - an ordered set of Map's
class Maps : public vector<Map> {

private:

// operator* - return each rhs element mapped by each of these Maps
template<class T>
T operator*(const T &rhs) const;

// symmetric - return these Maps that are symmetric for all rhs elements
template<class T>
Maps symmetric(const T &rhs) const;

public:

// Maps - initialize with n Map's
Maps(int n = 0);

// Maps - initialize with a single map
Maps(const Map &map);

// append - append maps to these Maps and return them
Maps &append(const Maps &maps);

// operator* - return each rhs element mapped by each of these Maps
Poss operator*(const Poss &rhs) const;

// operator* - return each rhs element mapped by each of these Maps
Maps operator*(const Maps &rhs) const;

// symmetric - return these Maps that are symmetric for all rhs elements
Maps symmetric(const Poss &rhs) const;

// return the closure of these Maps
// the closure is the set of all maps formed by composition of these Maps
Maps close(void) const;

}; // end of class Maps

// class Shape - a puzzle piece with a distinct set of positions it may occupy
class Shape {

public:

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

// poss - set of positions that this shape may occupy in puzzle
Poss poss;

// Shape - initialize with an parts and aposs positions
Shape(int an = 0, const Poss &aposs = Poss());

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

}; // end of class Shape

// class 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 Part - a puzzle piece, a shape, that occupies a particular position
class Part {

public:

// shapeid - identifier of part's shape in an ordered set of shapes
ShapeId shapeid;

// pos - position of part in puzzle
Pos pos;

// Part - initialize with shape identifier ashapeid and apos position
Part(ShapeId ashapeid = 0, const Pos &apos = Pos());

// operator< - is this less than rhs, comparing shapeid then pos, for ordering
bool operator<(const Part &rhs) const;

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

}; // end of class Part

// class Parts - an ordered set of Part's
class Parts : public vector<Part> {

public:

// Parts - initialize with n Part's
Parts(int n = 0);

// Parts - initialize with a single Part
Parts(const Part &part);

// select - return these Parts with shapeid
Parts select(ShapeId shapeid) const;

// select - return these Parts indexed by partids
Parts select(const PartIds &partids) const;

// decode - return a string representation of these Parts.
// codes is a list of characters to represent each of these Parts, in order.
// src is a list of default characters to represent each location, in order.
// the returned string is a list of characters to represent each location,
// in order. if the location is occupied by a part, a character representing
// that part from codes is returned, otherwise a default character representing
// that location from src is returned.
std::string decode(const std::string &codes,
		const std::string &src) const;

}; // end of class Parts

// class PartIds - an ordered set of PartId's
class PartIds : public vector<PartId> {

public:

// initialize with n PartId's
PartIds(int n = 0);

}; // end of class PartIds

// class PartIdss - an ordered set of PartIds's
class PartIdss : public vector<PartIds> {

}; // end of class PartIdss

// class MapPart - indirectly represented Part, whose Pos is remapped by a Map
class MapPart {

public:

// id of map in some Maps
MapId mapid;

// id of part in some Parts
PartId partid;

// MapPart - initialize with amapid and apartid
MapPart(MapId amapid = 0, PartId apartid = 0);

// operator<< - free format print of mapid and partid
friend std::ostream &operator<<(std::ostream &, const MapPart &);

}; // end of class MapPart

// class MapParts - an ordered set of MapPart's
class MapParts : public vector<MapPart> {

}; // end of class MapParts

#endif // end APS_H_