#include <assembler_0.h>
Classes | |
class | piecePosition |
Public Member Functions | |
assembler_0_c (void) | |
~assembler_0_c (void) | |
errState | createMatrix (const problem_c *puz, bool keepMirror, bool keepRotations, bool complete) |
the part of the initialisation that may take a while. | |
void | assemble (assembler_cb *callback) |
start the assembly process. | |
int | getErrorsParam (void) |
when createMatrix returns an error you can call this function to find out which piece is involved, or other additional information | |
virtual float | getFinished (void) const |
a function that returns the finished percentage in the range between 0 and 1. | |
virtual void | stop (void) |
stops the assembly process sometimes in the near future. | |
virtual bool | stopped (void) const |
returns true, as soon as the process really has stopped | |
virtual errState | setPosition (const char *string, const char *version) |
sets the position of the assembly process, so that it continues exactly where it stood, when getPosition was called | |
virtual void | save (xmlWriter_c &xml) const |
this function saves the current state of the assembler into an xml node to write it to an file. | |
virtual void | reduce (void) |
Try to optimize piece placement. | |
virtual unsigned int | getReducePiece (void) const |
Then running in an extra thread it is possible to find out which piece is worked on by reduce. | |
virtual unsigned long | getIterations (void) |
this function returns a number reflecting the complexity of the puzzle. | |
bool | getPiecePlacementSupported (void) const |
unsigned int | getPiecePlacement (unsigned int node, int delta, unsigned int piece, unsigned char *tran, int *x, int *y, int *z) const |
unsigned int | getPiecePlacementCount (unsigned int piece) const |
void | debug_step (unsigned long num=1) |
assembly_c * | getAssembly (void) |
Static Public Member Functions | |
static bool | canHandle (const problem_c *p) |
Protected Member Functions | |
void | GenerateFirstRow (void) |
int | AddPieceNode (unsigned int piece, unsigned int rot, unsigned int x, unsigned int y, unsigned int z) |
void | getPieceInformation (unsigned int node, unsigned char *tran, int *x, int *y, int *z, unsigned int *pc) const |
void | AddVoxelNode (unsigned int col, unsigned int piecenode) |
unsigned int | getRows (int pos) |
unsigned int | getRight (int pos) |
unsigned int | getColCount (int pos) |
unsigned int | getVarivoxelStart (void) |
unsigned int | getPos (void) |
assembler_cb * | getCallback (void) |
unsigned int | getPiecenumber (void) |
void | checkForTransformedAssemblies (unsigned int pivot, mirrorInfo_c *mir) |
Protected Attributes | |
const problem_c * | puzzle |
Private Member Functions | |
void | cover (unsigned int col) |
void | uncover (unsigned int col) |
void | cover_row (register unsigned int r) |
void | uncover_row (register unsigned int r) |
bool | try_cover_row (register unsigned int r, unsigned int *columns) |
void | remove_row (register unsigned int r) |
void | reinsert_row (register unsigned int r) |
void | remove_column (register unsigned int c) |
void | solution (void) |
void | iterativeMultiSearch (void) |
bool | canPlace (const voxel_c *piece, int x, int y, int z) const |
int | prepare (void) |
this function prepares the matrix of nodes for the recursive function I've done some additions to Knuths algorithm to implement variable voxels (empty spaces in the solution) and multiple instances of the same piece. | |
bool | checkmatrix (void) |
unsigned int | clumpify (void) |
assembler_0_c (const assembler_0_c &) | |
void | operator= (const assembler_0_c &) |
Private Attributes | |
std::vector< unsigned int > | left |
std::vector< unsigned int > | right |
std::vector< unsigned int > | upDown |
std::vector< unsigned int > | colCount |
bool | abbort |
bool | running |
unsigned int | pos |
unsigned int * | rows |
unsigned int * | columns |
errState | errorsState |
int | errorsParam |
unsigned long | iterations |
int | holes |
unsigned int | varivoxelStart |
unsigned int | varivoxelEnd |
unsigned int | piecenumber |
assembler_cb * | asm_bc |
unsigned int | reducePiece |
std::vector< piecePosition > | piecePositions |
bool | avoidTransformedAssemblies |
unsigned int | avoidTransformedPivot |
mirrorInfo_c * | avoidTransformedMirror |
bool | complete |
set to true, when complete rotation analysis is requested | |
bool | debug |
int | debug_loops |
It is mor or less identical to Don Knuths idea. Some changes have been done though to provide for holes. This class can not handle ranges or multi-pieces.
All involved pieces must be there exactly one time. But in that case it is a bit faster than assembler_1.
assembler_0_c::assembler_0_c | ( | void | ) |
assembler_0_c::~assembler_0_c | ( | void | ) |
References avoidTransformedMirror, columns, and rows.
assembler_0_c::assembler_0_c | ( | const assembler_0_c & | ) | [private] |
int assembler_0_c::AddPieceNode | ( | unsigned int | piece, | |
unsigned int | rot, | |||
unsigned int | x, | |||
unsigned int | y, | |||
unsigned int | z | |||
) | [protected] |
void assembler_0_c::AddVoxelNode | ( | unsigned int | col, | |
unsigned int | piecenode | |||
) | [protected] |
void assembler_0_c::assemble | ( | assembler_cb * | ) | [virtual] |
start the assembly process.
it is intended that the assembly process runs in a different thread from the controlling thread. When this is the case the controlling thread can call stop to make the assembly thread stop working. It will then return from this function but can be resumed any time
Reimplemented from assembler_c.
References asm_bc, debug, assembler_c::ERR_NONE, errorsState, and iterativeMultiSearch().
bool assembler_0_c::canHandle | ( | const problem_c * | p | ) | [static] |
References problem_c::getShapeMax(), problem_c::getShapeMin(), and problem_c::partNumber().
Referenced by createMatrix(), and gridType_c::findAssembler().
bool assembler_0_c::canPlace | ( | const voxel_c * | piece, | |
int | x, | |||
int | y, | |||
int | z | |||
) | const [private] |
References voxel_c::boundX1(), voxel_c::boundX2(), voxel_c::boundY1(), voxel_c::boundY2(), voxel_c::boundZ1(), voxel_c::boundZ2(), voxel_c::getColor(), problem_c::getResultShape(), voxel_c::getState(), voxel_c::onGrid(), problem_c::placementAllowed(), puzzle, voxel_c::VX_EMPTY, and voxel_c::VX_FILLED.
Referenced by prepare().
void assembler_0_c::checkForTransformedAssemblies | ( | unsigned int | pivot, | |
mirrorInfo_c * | mir | |||
) | [protected] |
References avoidTransformedAssemblies, avoidTransformedMirror, and avoidTransformedPivot.
Referenced by prepare().
bool assembler_0_c::checkmatrix | ( | void | ) | [private] |
unsigned int assembler_0_c::clumpify | ( | void | ) | [private] |
void assembler_0_c::cover | ( | unsigned int | col | ) | [private] |
References colCount, down, left, right, up, and upDown.
Referenced by cover_row(), iterativeMultiSearch(), reduce(), setPosition(), and try_cover_row().
void assembler_0_c::cover_row | ( | register unsigned int | r | ) | [private] |
assembler_0_c::errState assembler_0_c::createMatrix | ( | const problem_c * | , | |
bool | , | |||
bool | , | |||
bool | ||||
) | [virtual] |
the part of the initialisation that may take a while.
when keep mirror is true, the assembler must not throw away mirror solutions but it still removes solutions that are rotations.
Reimplemented from assembler_c.
References avoidTransformedAssemblies, avoidTransformedMirror, bt_assert, canHandle(), columns, complete, voxel_c::countState(), assembler_c::ERR_CAN_NOT_PLACE, assembler_c::ERR_NONE, assembler_c::ERR_PUZZLE_UNHANDABLE, assembler_c::ERR_TOO_FEW_UNITS, assembler_c::ERR_TOO_MANY_UNITS, errorsParam, errorsState, problem_c::getResultShape(), problem_c::getShapeShape(), holes, iterations, problem_c::partNumber(), problem_c::pieceNumber(), piecenumber, pos, prepare(), puzzle, problem_c::resultValid(), rows, varivoxelEnd, varivoxelStart, voxel_c::VX_FILLED, and voxel_c::VX_VARIABLE.
void assembler_0_c::debug_step | ( | unsigned long | num = 1 |
) | [virtual] |
void assembler_0_c::GenerateFirstRow | ( | void | ) | [protected] |
References colCount, left, right, upDown, varivoxelEnd, and varivoxelStart.
Referenced by prepare().
assembly_c * assembler_0_c::getAssembly | ( | void | ) | [virtual] |
Implements assembler_c.
References assembly_c::addNonPlacement(), assembly_c::addPlacement(), bt_assert, problem_c::getGridType(), getPieceInformation(), getPiecenumber(), getPos(), getRows(), piecenumber, pos, and puzzle.
Referenced by solution().
assembler_cb* assembler_0_c::getCallback | ( | void | ) | [inline, protected] |
unsigned int assembler_0_c::getColCount | ( | int | pos | ) | [inline, protected] |
References colCount.
int assembler_0_c::getErrorsParam | ( | void | ) | [inline, virtual] |
when createMatrix returns an error you can call this function to find out which piece is involved, or other additional information
Reimplemented from assembler_c.
References errorsParam.
float assembler_0_c::getFinished | ( | void | ) | const [virtual] |
a function that returns the finished percentage in the range between 0 and 1.
It must be possible to call this function while assemble is running
Reimplemented from assembler_c.
References colCount, columns, down, piecenumber, pos, rows, up, and upDown.
virtual unsigned long assembler_0_c::getIterations | ( | void | ) | [inline, virtual] |
this function returns a number reflecting the complexity of the puzzle.
This could be the number of placements tried, or some other value
Reimplemented from assembler_c.
References iterations.
void assembler_0_c::getPieceInformation | ( | unsigned int | node, | |
unsigned char * | tran, | |||
int * | x, | |||
int * | y, | |||
int * | z, | |||
unsigned int * | pc | |||
) | const [protected] |
unsigned int assembler_0_c::getPiecenumber | ( | void | ) | [inline, protected] |
unsigned int assembler_0_c::getPiecePlacement | ( | unsigned int | node, | |
int | delta, | |||
unsigned int | piece, | |||
unsigned char * | tran, | |||
int * | x, | |||
int * | y, | |||
int * | z | |||
) | const [virtual] |
unsigned int assembler_0_c::getPiecePlacementCount | ( | unsigned int | piece | ) | const [virtual] |
bool assembler_0_c::getPiecePlacementSupported | ( | void | ) | const [inline, virtual] |
Reimplemented from assembler_c.
unsigned int assembler_0_c::getPos | ( | void | ) | [inline, protected] |
virtual unsigned int assembler_0_c::getReducePiece | ( | void | ) | const [inline, virtual] |
Then running in an extra thread it is possible to find out which piece is worked on by reduce.
Because the reduce process can take a long time it is nice to give some feedback to the user. With this function the user can get a number to display with the information that the program is currently reducing. The intended interpretation is that the program is currently working on the piece with the returned number, but if you want you can also return something else
Reimplemented from assembler_c.
References reducePiece.
unsigned int assembler_0_c::getRight | ( | int | pos | ) | [inline, protected] |
References right.
unsigned int assembler_0_c::getRows | ( | int | pos | ) | [inline, protected] |
unsigned int assembler_0_c::getVarivoxelStart | ( | void | ) | [inline, protected] |
void assembler_0_c::iterativeMultiSearch | ( | void | ) | [private] |
References abbort, colCount, columns, cover(), cover_row(), debug, debug_loops, down, holes, iterations, piecenumber, pos, right, rows, running, solution(), uncover(), uncover_row(), and varivoxelEnd.
Referenced by assemble(), and debug_step().
void assembler_0_c::operator= | ( | const assembler_0_c & | ) | [private] |
int assembler_0_c::prepare | ( | void | ) | [private] |
this function prepares the matrix of nodes for the recursive function I've done some additions to Knuths algorithm to implement variable voxels (empty spaces in the solution) and multiple instances of the same piece.
Empty voxels in the result are done by removing columns from the matrix. This will prevent the algorithm from filling the corresponding voxels. But we need to have the constraints that these columns place on the solution. This is done by adding these columns to the matrix but behind the normal columns. These additional columns wont be searched by the alg. if it looks for the next task to achieve.
Multiple instances of the same piece is handles in a similar way. To prevent finding the same solution again and again with just the pieces swapping places we number the pieces and their possible placements and disallow that the position number of piece n is lower than the position number of piece n-1. This can be achieved by adding more constraint columns. There need to be one column for each
negative result show there is something wrong: the place -result has not possible position inside the result
References AddPieceNode(), mirrorInfo_c::addPieces(), addToCache(), AddVoxelNode(), voxel_c::boundX1(), voxel_c::boundX2(), voxel_c::boundY1(), voxel_c::boundY2(), voxel_c::boundZ1(), voxel_c::boundZ2(), canPlace(), checkForTransformedAssemblies(), columns, symmetries_c::countSymmetryIntersection(), GenerateFirstRow(), problem_c::getGridType(), voxel_c::getHx(), voxel_c::getHy(), voxel_c::getHz(), voxel_c::getIndex(), voxel_c::getMirrorTransform(), symmetries_c::getNumTransformations(), symmetries_c::getNumTransformationsMirror(), problem_c::getResultShape(), problem_c::getShape(), problem_c::getShapeShape(), voxel_c::getState(), gridType_c::getSymmetries(), getVarivoxelStart(), gridType_c::getVoxel(), voxel_c::getXYZ(), problem_c::partNumber(), problem_c::pieceNumber(), piecenumber, puzzle, reducePiece, voxel_c::selfSymmetries(), symmetries_c::symmetrieContainsTransformation(), symmetries_c::symmetriesLeft(), symmetries_c::symmetryContainsMirror(), voxel_c::transform(), unSymmetric, voxel_c::VX_FILLED, and voxel_c::VX_VARIABLE.
Referenced by createMatrix().
void assembler_0_c::reduce | ( | void | ) | [virtual] |
Try to optimize piece placement.
the function tries to remove possible piece placements by checking if, after the piece has been placed somewhere, that all the other pieces still can be placed and all holes can still be filled. if this is not the case then this placement can be removed
it is not necessary for an assembler to implement this function
Reimplemented from assembler_c.
References checkmatrix(), clumpify(), colCount, columns, cover(), down, piecenumber, piecePositions, reducePiece, remove_row(), right, try_cover_row(), uncover(), uncover_row(), and varivoxelEnd.
void assembler_0_c::reinsert_row | ( | register unsigned int | r | ) | [private] |
void assembler_0_c::remove_column | ( | register unsigned int | c | ) | [private] |
void assembler_0_c::remove_row | ( | register unsigned int | r | ) | [private] |
void assembler_0_c::save | ( | xmlWriter_c & | xml | ) | const [virtual] |
this function saves the current state of the assembler into an xml node to write it to an file.
this state must be such that the class can restore this state and continue from there by getting this and the puzzle given to the constructor
Reimplemented from assembler_c.
References xmlWriter_c::addContent(), ASSEMBLER_VERSION, columns, xmlWriter_c::endTag(), iterations, xmlWriter_c::newAttrib(), xmlWriter_c::newTag(), piecenumber, pos, and rows.
assembler_c::errState assembler_0_c::setPosition | ( | const char * | string, | |
const char * | version | |||
) | [virtual] |
sets the position of the assembly process, so that it continues exactly where it stood, when getPosition was called
the function should only be called when assembly is not running it should be called before calling assemble
Reimplemented from assembler_c.
References ASSEMBLER_VERSION, bt_assert, columns, cover(), cover_row(), assembler_c::ERR_CAN_NOT_RESTORE_SYNTAX, assembler_c::ERR_CAN_NOT_RESTORE_VERSION, assembler_c::ERR_NONE, getInt(), getLong(), iterations, left, piecenumber, pos, and rows.
void assembler_0_c::solution | ( | void | ) | [private] |
References assembler_cb::assembly(), avoidTransformedAssemblies, avoidTransformedMirror, avoidTransformedPivot, complete, getAssembly(), getCallback(), puzzle, and assembly_c::smallerRotationExists().
Referenced by iterativeMultiSearch().
virtual void assembler_0_c::stop | ( | void | ) | [inline, virtual] |
stops the assembly process sometimes in the near future.
Reimplemented from assembler_c.
References abbort.
virtual bool assembler_0_c::stopped | ( | void | ) | const [inline, virtual] |
returns true, as soon as the process really has stopped
Reimplemented from assembler_c.
References running.
bool assembler_0_c::try_cover_row | ( | register unsigned int | r, | |
unsigned int * | columns | |||
) | [private] |
void assembler_0_c::uncover | ( | unsigned int | col | ) | [private] |
References colCount, down, left, right, up, and upDown.
Referenced by iterativeMultiSearch(), reduce(), try_cover_row(), and uncover_row().
void assembler_0_c::uncover_row | ( | register unsigned int | r | ) | [private] |
bool assembler_0_c::abbort [private] |
Referenced by iterativeMultiSearch(), and stop().
assembler_cb* assembler_0_c::asm_bc [private] |
Referenced by assemble(), debug_step(), and getCallback().
bool assembler_0_c::avoidTransformedAssemblies [private] |
Referenced by checkForTransformedAssemblies(), createMatrix(), and solution().
Referenced by checkForTransformedAssemblies(), createMatrix(), solution(), and ~assembler_0_c().
unsigned int assembler_0_c::avoidTransformedPivot [private] |
Referenced by checkForTransformedAssemblies(), and solution().
std::vector<unsigned int> assembler_0_c::colCount [private] |
unsigned int* assembler_0_c::columns [private] |
Referenced by clumpify(), createMatrix(), getFinished(), iterativeMultiSearch(), prepare(), reduce(), save(), setPosition(), and ~assembler_0_c().
bool assembler_0_c::complete [private] |
set to true, when complete rotation analysis is requested
Referenced by createMatrix(), and solution().
bool assembler_0_c::debug [private] |
Referenced by assemble(), debug_step(), and iterativeMultiSearch().
int assembler_0_c::debug_loops [private] |
Referenced by debug_step(), and iterativeMultiSearch().
int assembler_0_c::errorsParam [private] |
Referenced by createMatrix(), and getErrorsParam().
errState assembler_0_c::errorsState [private] |
Referenced by assemble(), and createMatrix().
int assembler_0_c::holes [private] |
Referenced by checkmatrix(), createMatrix(), and iterativeMultiSearch().
unsigned long assembler_0_c::iterations [private] |
Referenced by createMatrix(), getIterations(), iterativeMultiSearch(), save(), and setPosition().
std::vector<unsigned int> assembler_0_c::left [private] |
Referenced by AddPieceNode(), AddVoxelNode(), cover(), GenerateFirstRow(), remove_column(), setPosition(), try_cover_row(), uncover(), and uncover_row().
unsigned int assembler_0_c::piecenumber [private] |
Referenced by createMatrix(), getAssembly(), getFinished(), getPiecenumber(), iterativeMultiSearch(), prepare(), reduce(), save(), and setPosition().
std::vector<piecePosition> assembler_0_c::piecePositions [private] |
Referenced by AddPieceNode(), clumpify(), getPieceInformation(), and reduce().
unsigned int assembler_0_c::pos [private] |
Referenced by createMatrix(), getAssembly(), getFinished(), getPos(), iterativeMultiSearch(), save(), and setPosition().
const problem_c* assembler_0_c::puzzle [protected] |
Referenced by canPlace(), createMatrix(), getAssembly(), prepare(), and solution().
unsigned int assembler_0_c::reducePiece [private] |
Referenced by getReducePiece(), prepare(), and reduce().
std::vector<unsigned int> assembler_0_c::right [private] |
unsigned int* assembler_0_c::rows [private] |
Referenced by createMatrix(), getFinished(), getRows(), iterativeMultiSearch(), save(), setPosition(), and ~assembler_0_c().
bool assembler_0_c::running [private] |
Referenced by iterativeMultiSearch(), and stopped().
std::vector<unsigned int> assembler_0_c::upDown [private] |
Referenced by AddPieceNode(), AddVoxelNode(), cover(), GenerateFirstRow(), getFinished(), and uncover().
unsigned int assembler_0_c::varivoxelEnd [private] |
Referenced by checkmatrix(), createMatrix(), GenerateFirstRow(), iterativeMultiSearch(), reduce(), and try_cover_row().
unsigned int assembler_0_c::varivoxelStart [private] |
Referenced by createMatrix(), GenerateFirstRow(), and getVarivoxelStart().