// box.h and namespace box - high-level abstraction of assembly
// puzzle solver for hyperrectangular puzzles. Generally, the user only
// need specify one position per shape and the Box class will perform
// all legal rotations and translations. Nonetheless, Box uses locations
// rather than lists of coordinates.
// A rectangular grid is naturally an array. The class Ord here represents
// a puzzle location as an array element and class Space represents the
// whole puzzle as an array.
// Typically, puzzle solutions that can be produced by rotations and reflections
// are considered redundant whereas the position of parts within a puzzle are
// not unique if produced by translations or rotations.
// Strategically, reflections are easier to implement first, then
// rotations as pairs of reflections, as done in Space::maps(bool).
// To get rotations of parts where dimension lengths are uneven,
// in Space::getrotates(Pos), the dimensions are permuted and if the permutation
// represents a reflection, it is canceled out with a reflection (of the lowest
// order dimension with itself). A permutation is a reflection if it can be
// generated by an odd number of pair swaps. The number of pair swaps by the
// standard algorithm std::next_permutation is determined by the position of the
// first changed value relative to the end of the permutation.

#ifndef BOX_H_
#define BOX_H_

#include <string>
#include "puzzle.h"

namespace box {

// typedef Ord - an ordinate; value in some dimension
typedef int Ord;

// typedef OrdId - identifier of an ordinate, one of several dimensions
typedef int OrdId;

// Ords - an ordered set of Ord's; a set of coordinates
class Ords;

// Ordss - an ordered set of Ords's; a set of sets of coordinates
class Ordss;

// class Space - a box space; rectangular space in a number of dimensions
class Space;

// class Box - a puzzle in a box space
class Box;

} // end of namespace box

namespace box {

// Ords - an ordered set of Ord's; a set of coordinates
class Ords : public vector<Ord> {

public:

// Ords - initialize with n Ord's
Ords(OrdId n = 0);

// Ords - initialize with n Ords, all with Ord v, dimensions of a hyper-cube
Ords(OrdId n, Ord v);

// Ords - initialize with Ords v
Ords(const vector<Ord> &v);

// getmin - return minimum Ord
Ord getmin(void) const;

// getmax - return maximum Ord
Ord getmax(void) const;

}; // end of class Ords

// Ordss - an ordered set of Ords's; a set of sets of coordinates
class Ordss : public vector<Ords> {

public:

// Ordss - initialize with n Ords's
Ordss(int n = 0);

// return Ords by selecting the value of the ith OrdId of each Ords
Ords gettransposeords(OrdId i) const;

// getmin - return Ords by selecting the min value of each OrdId for all Ords
Ords getmin(void) const;

// getmax - return Ords by selecting the max value of each OrdId for all Ords
Ords getmax(void) const;

}; // end of class Ordss

// class Space - a box space; rectangular space in a number of dimensions
class Space {

private:

// lens - lengths of the dimensions
Ords lens;

// nloc - total number of locations; product of all lengths
LocId nloc;

// init - initialize with alens and compute space
void init(const Ords &alens);

// printheading - print to output heading for 4th dimension and higher of ords
void printheading(std::ostream &output, const Ords &ords) const;

public:

// Space - initialize with n dimensions of length len, a hyper-cube
Space(OrdId n, Ord len);

// Space - initialize with dimensions alens
Space(const Ords &alens = Ords());

// getn - return lengths of dimensions
Ords getlens(void) const;

// getnloc - return total number of locations
LocId getnloc(void) const;

// getloc - return location for coordinates ords
LocId getloc(const Ords &ords) const;

// getords - return coordinates of location loc
Ords getords(LocId loc) const;

// map - return identity map for locations in this space
Map map(void) const; // identity map

// map - return map of locations to reflect dimension i onto itself
Map map(OrdId i) const;

// map - return map of locations to reflected dimension i with dimension j
Map map(OrdId i, OrdId j) const; // map with dim i reflected to dim j

// maps - return reflection maps of location for all symmetries in this space
Maps maps(void) const;

// maps - if reflectflag, return reflection maps; otherwise only rotation maps
Maps maps(bool reflectflag) const;

// getordss - return a set of coordinates in this space for each location in pos
Ordss getordss(const Pos &pos) const;

// getpos - return pos of sets of coordinates in this space
Pos getpos(const Ordss &ordss) const;

// getrotates - return dimensional rotations of position pos in this space
Poss getrotates(const Pos &pos) const;

// getrotates - return dimensional rotations of positions poss in this space
Poss getrotates(const Poss &poss) const;

// gettranslates - return all translations of position pos in this space
Poss gettranslates(const Pos &pos) const;

// getranslates - return all translations of positions poss in this space
Poss gettranslates(const Poss &poss) const;

// gettransforms - return all transforms of positions poss in this space
Poss gettransforms(const Poss &poss, bool reflectflag) const;

// print - print to output, diagram of string tab, a table chars per location
void print(std::ostream &output, const std::string &tab) const;

}; // end of class Space

// class Box - a puzzle in a box space
class Box : public Space {

private:

// inputshapes - given shapes without any transformations
Shapes inputshapes;

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

// reflectinflag - can parts be reflected? (typically false)
bool reflectinflag;

// reflectoutflag - can solutions be reflected? (typically true)
bool reflectoutflag;

// puzzle - the puzzle representation
puzzle::Puzzle puzzle;

// transformshapes - return inputshapes with all transforms applied
Shapes transformshapes(bool reflectflag);

public:

// Box - initialize with n dimensions of length len, a hyper-cube
Box(OrdId n, Ord len);

// Box - initialize with dimensions alens
Box(const Ords &alens = Ords());

// setpos - initialize pos
void setpos(const Pos &apos);

// setreflect - set reflections for input (parts) and output (solutions)
void setreflect(bool areflectflag = true);

// setreflectin - set reflections for input (parts); typically false
void setreflectin(bool areflectinflag = true);

// setreflectout - set reflections for output (solutions); typically true
void setreflectout(bool areflectoutflag = true);

// setshapes - setup search for ainputshapes, to which transforms will be done
void setshapes(const Shapes &ainputshapes);

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

// getsolutions - return solutions, suppressing redundancies
PartIdss &getsolutions(void);

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

// printsols - print solutions on output, using codes, a table of chars per part
void printsols(std::ostream &output, const std::string &codes);

// printshapes - print parts on output, using codes, a table of chars per shape
void printshapes(std::ostream &output, const std::string &codes);

// print - print solutions and parts on output, using partcodes, a table of
// chars per part, and shapecodes, a table of chars per shape
void print(std::ostream &output,
		const std::string &partcodes,
		const std::string &shapecodes);

}; // end of class Box

} // end of namespace box

#endif // end of BOX_H_