#include <assembler_1.h>
Classes | |
class | piecePosition |
Public Member Functions | |
assembler_1_c (void) | |
~assembler_1_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. | |
void | debug_step (unsigned long num=1) |
assembly_c * | getAssembly (void) |
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 |
unsigned long | getIterations (void) |
this function returns a number reflecting the complexity of the puzzle. | |
Static Public Member Functions | |
static bool | canHandle (const problem_c *p) |
Protected Member Functions | |
void | GenerateFirstRow (unsigned int res_filled) |
int | AddPieceNode (unsigned int piece, unsigned int rot, unsigned int x, unsigned int y, unsigned int z) |
void | AddRangeNode (unsigned int col, unsigned int piecenode, unsigned int weight) |
void | getPieceInformation (unsigned int node, unsigned int *piece, unsigned char *tran, int *x, int *y, int *z) const |
void | AddVoxelNode (unsigned int col, unsigned int piecenode) |
unsigned int | getRight (int pos) |
unsigned int | getColCount (int pos) |
assembler_cb * | getCallback (void) |
unsigned int | getPiecenumber (void) |
void | checkForTransformedAssemblies (unsigned int pivot, mirrorInfo_c *mir) |
Protected Attributes | |
const problem_c * | puzzle |
unsigned int | reducePiece |
Private Member Functions | |
void | solution (void) |
bool | open_column_conditions_fulfillable (void) |
int | find_best_unclosed_column (void) |
void | cover_column_only (int col) |
void | uncover_column_only (int col) |
void | cover_column_rows (int col) |
void | uncover_column_rows (int col) |
void | hiderow (int r) |
void | unhiderow (int r) |
void | hiderows (unsigned int r) |
void | unhiderows (void) |
bool | column_condition_fulfilled (int col) |
bool | column_condition_fulfillable (int col) |
void | iterative (void) |
void | remove_row (register unsigned int r) |
void | remove_column (register unsigned int c) |
unsigned int | clumpify (void) |
bool | canPlace (const voxel_c *piece, int x, int y, int z) const |
this function is called by the default implementation of prepare to check, if the piece fits at the given position | |
int | prepare (bool hasRange, unsigned int rangeMin, unsigned int rangeMax) |
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. | |
assembler_1_c (const assembler_1_c &) | |
void | operator= (const assembler_1_c &) |
Private Attributes | |
std::vector< unsigned int > | left |
std::vector< unsigned int > | right |
std::vector< unsigned int > | up |
std::vector< unsigned int > | down |
std::vector< unsigned int > | colCount |
std::vector< unsigned int > | weight |
std::vector< unsigned int > | min |
std::vector< unsigned int > | max |
std::vector< unsigned int > | holeColumns |
unsigned int | holes |
bool | abbort |
bool | running |
std::vector< unsigned int > | rows |
std::vector< unsigned int > | finished_a |
std::vector< unsigned int > | finished_b |
std::vector< unsigned int > | hidden_rows |
std::vector< unsigned int > | task_stack |
std::vector< unsigned int > | next_row_stack |
std::vector< unsigned int > | column_stack |
unsigned int | headerNodes |
errState | errorsState |
int | errorsParam |
unsigned int | piecenumber |
assembler_cb * | asm_bc |
std::vector< piecePosition > | piecePositions |
bool | avoidTransformedAssemblies |
unsigned int | avoidTransformedPivot |
mirrorInfo_c * | avoidTransformedMirror |
bool | complete |
set to true, when complete analysis is requested | |
bool | debug |
int | debug_loops |
unsigned long | iterations |
This assembler is written with ideas from Wei-Hwa Huang. It can handle ranges for the piece numbers and thus also multiple instances of one piece.
But for simple cases it is not really optimal.
It also has a problem with guessing how much of the analysis it done. This number is growing exponentially meaning in the beginning it is growing very slowly resulting in huge time-left numbers while at the end it is getting very fast and the time-left value dropping really fast.
assembler_1_c::assembler_1_c | ( | void | ) |
References next_row_stack, and task_stack.
assembler_1_c::~assembler_1_c | ( | void | ) |
References avoidTransformedMirror.
assembler_1_c::assembler_1_c | ( | const assembler_1_c & | ) | [private] |
int assembler_1_c::AddPieceNode | ( | unsigned int | piece, | |
unsigned int | rot, | |||
unsigned int | x, | |||
unsigned int | y, | |||
unsigned int | z | |||
) | [protected] |
void assembler_1_c::AddRangeNode | ( | unsigned int | col, | |
unsigned int | piecenode, | |||
unsigned int | weight | |||
) | [protected] |
void assembler_1_c::AddVoxelNode | ( | unsigned int | col, | |
unsigned int | piecenode | |||
) | [protected] |
void assembler_1_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 abbort, asm_bc, debug, assembler_c::ERR_NONE, errorsState, iterative(), next_row_stack, and running.
bool assembler_1_c::canHandle | ( | const problem_c * | p | ) | [static] |
Referenced by createMatrix(), and gridType_c::findAssembler().
bool assembler_1_c::canPlace | ( | const voxel_c * | piece, | |
int | x, | |||
int | y, | |||
int | z | |||
) | const [private] |
this function is called by the default implementation of prepare to check, if the piece fits at the given position
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_1_c::checkForTransformedAssemblies | ( | unsigned int | pivot, | |
mirrorInfo_c * | mir | |||
) | [protected] |
References avoidTransformedAssemblies, avoidTransformedMirror, and avoidTransformedPivot.
Referenced by prepare().
unsigned int assembler_1_c::clumpify | ( | void | ) | [private] |
References down, max, min, piecePositions, remove_column(), right, and weight.
Referenced by reduce().
bool assembler_1_c::column_condition_fulfillable | ( | int | col | ) | [private] |
bool assembler_1_c::column_condition_fulfilled | ( | int | col | ) | [private] |
void assembler_1_c::cover_column_only | ( | int | col | ) | [private] |
void assembler_1_c::cover_column_rows | ( | int | col | ) | [private] |
assembler_1_c::errState assembler_1_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(), 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::getMaxHoles(), problem_c::getResultShape(), problem_c::getShapeMax(), problem_c::getShapeMin(), problem_c::getShapeShape(), holes, max, problem_c::maxHolesDefined(), min, problem_c::partNumber(), problem_c::pieceNumber(), piecenumber, prepare(), puzzle, problem_c::resultValid(), voxel_c::VX_FILLED, and voxel_c::VX_VARIABLE.
void assembler_1_c::debug_step | ( | unsigned long | num = 1 |
) | [virtual] |
int assembler_1_c::find_best_unclosed_column | ( | void | ) | [private] |
void assembler_1_c::GenerateFirstRow | ( | unsigned int | res_filled | ) | [protected] |
assembly_c * assembler_1_c::getAssembly | ( | void | ) | [virtual] |
Implements assembler_c.
References assembly_c::addNonPlacement(), assembly_c::addPlacement(), problem_c::getGridType(), getPieceInformation(), problem_c::partNumber(), puzzle, rows, and assembly_c::sort().
Referenced by solution().
assembler_cb* assembler_1_c::getCallback | ( | void | ) | [inline, protected] |
unsigned int assembler_1_c::getColCount | ( | int | pos | ) | [inline, protected] |
References colCount.
int assembler_1_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_1_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 finished_a, finished_b, and next_row_stack.
unsigned long assembler_1_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_1_c::getPieceInformation | ( | unsigned int | node, | |
unsigned int * | piece, | |||
unsigned char * | tran, | |||
int * | x, | |||
int * | y, | |||
int * | z | |||
) | const [protected] |
unsigned int assembler_1_c::getPiecenumber | ( | void | ) | [inline, protected] |
References piecenumber.
unsigned int assembler_1_c::getPiecePlacement | ( | unsigned int | node, | |
int | delta, | |||
unsigned int | piece, | |||
unsigned char * | tran, | |||
int * | x, | |||
int * | y, | |||
int * | z | |||
) | const [virtual] |
Reimplemented from assembler_c.
References bt_assert, down, getPieceInformation(), problem_c::getShapeMax(), puzzle, and up.
unsigned int assembler_1_c::getPiecePlacementCount | ( | unsigned int | piece | ) | const [virtual] |
bool assembler_1_c::getPiecePlacementSupported | ( | void | ) | const [inline, virtual] |
Reimplemented from assembler_c.
virtual unsigned int assembler_1_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_1_c::getRight | ( | int | pos | ) | [inline, protected] |
References right.
void assembler_1_c::hiderow | ( | int | r | ) | [private] |
References colCount, down, right, up, and weight.
Referenced by hiderows(), iterative(), reduce(), and setPosition().
void assembler_1_c::hiderows | ( | unsigned int | r | ) | [private] |
References colCount, down, hidden_rows, hiderow(), max, right, and weight.
Referenced by iterative().
void assembler_1_c::iterative | ( | void | ) | [private] |
References abbort, bt_assert, column_condition_fulfillable(), column_condition_fulfilled(), column_stack, cover_column_only(), cover_column_rows(), debug, debug_loops, down, find_best_unclosed_column(), finished_a, finished_b, headerNodes, hidden_rows, hiderow(), hiderows(), holeColumns, holes, iterations, left, next_row_stack, open_column_conditions_fulfillable(), right, rows, solution(), task_stack, uncover_column_only(), uncover_column_rows(), unhiderows(), up, and weight.
Referenced by assemble(), and debug_step().
bool assembler_1_c::open_column_conditions_fulfillable | ( | void | ) | [private] |
void assembler_1_c::operator= | ( | const assembler_1_c & | ) | [private] |
int assembler_1_c::prepare | ( | bool | hasRange, | |
unsigned int | rangeMin, | |||
unsigned int | rangeMax | |||
) | [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(), AddRangeNode(), addToCache(), AddVoxelNode(), voxel_c::boundX1(), voxel_c::boundX2(), voxel_c::boundY1(), voxel_c::boundY2(), voxel_c::boundZ1(), voxel_c::boundZ2(), canPlace(), checkForTransformedAssemblies(), voxel_c::countState(), 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::getShapeMax(), problem_c::getShapeMin(), problem_c::getShapeShape(), voxel_c::getState(), gridType_c::getSymmetries(), gridType_c::getVoxel(), voxel_c::getXYZ(), holeColumns, max, min, problem_c::partNumber(), problem_c::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_1_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 clumpify(), colCount, down, headerNodes, hidden_rows, hiderow(), left, max, min, open_column_conditions_fulfillable(), piecePositions, reducePiece, remove_row(), right, unhiderow(), up, and weight.
void assembler_1_c::remove_column | ( | register unsigned int | c | ) | [private] |
void assembler_1_c::remove_row | ( | register unsigned int | r | ) | [private] |
void assembler_1_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, column_stack, xmlWriter_c::endTag(), finished_a, finished_b, hidden_rows, xmlWriter_c::newAttrib(), xmlWriter_c::newTag(), next_row_stack, rows, task_stack, and vectorToStream().
assembler_c::errState assembler_1_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 column_stack, cover_column_only(), cover_column_rows(), assembler_c::ERR_CAN_NOT_RESTORE_SYNTAX, assembler_c::ERR_NONE, finished_a, finished_b, hidden_rows, hiderow(), next_row_stack, right, rows, stringToVector(), task_stack, and weight.
void assembler_1_c::solution | ( | void | ) | [private] |
virtual void assembler_1_c::stop | ( | void | ) | [inline, virtual] |
stops the assembly process sometimes in the near future.
Reimplemented from assembler_c.
References abbort.
virtual bool assembler_1_c::stopped | ( | void | ) | const [inline, virtual] |
returns true, as soon as the process really has stopped
Reimplemented from assembler_c.
References running.
void assembler_1_c::uncover_column_only | ( | int | col | ) | [private] |
void assembler_1_c::uncover_column_rows | ( | int | col | ) | [private] |
void assembler_1_c::unhiderow | ( | int | r | ) | [private] |
void assembler_1_c::unhiderows | ( | void | ) | [private] |
bool assembler_1_c::abbort [private] |
Referenced by assemble(), debug_step(), iterative(), and stop().
assembler_cb* assembler_1_c::asm_bc [private] |
Referenced by assemble(), debug_step(), and getCallback().
bool assembler_1_c::avoidTransformedAssemblies [private] |
Referenced by checkForTransformedAssemblies(), createMatrix(), and solution().
Referenced by checkForTransformedAssemblies(), createMatrix(), solution(), and ~assembler_1_c().
unsigned int assembler_1_c::avoidTransformedPivot [private] |
Referenced by checkForTransformedAssemblies(), and solution().
std::vector<unsigned int> assembler_1_c::colCount [private] |
Referenced by AddPieceNode(), AddRangeNode(), AddVoxelNode(), column_condition_fulfillable(), cover_column_rows(), find_best_unclosed_column(), GenerateFirstRow(), getColCount(), hiderow(), hiderows(), open_column_conditions_fulfillable(), reduce(), remove_row(), uncover_column_rows(), and unhiderow().
std::vector<unsigned int> assembler_1_c::column_stack [private] |
Referenced by iterative(), save(), and setPosition().
bool assembler_1_c::complete [private] |
bool assembler_1_c::debug [private] |
Referenced by assemble(), debug_step(), and iterative().
int assembler_1_c::debug_loops [private] |
Referenced by debug_step(), and iterative().
std::vector<unsigned int> assembler_1_c::down [private] |
int assembler_1_c::errorsParam [private] |
Referenced by createMatrix(), and getErrorsParam().
errState assembler_1_c::errorsState [private] |
Referenced by assemble(), and createMatrix().
std::vector<unsigned int> assembler_1_c::finished_a [private] |
Referenced by getFinished(), iterative(), save(), and setPosition().
std::vector<unsigned int> assembler_1_c::finished_b [private] |
Referenced by getFinished(), iterative(), save(), and setPosition().
unsigned int assembler_1_c::headerNodes [private] |
Referenced by GenerateFirstRow(), iterative(), and reduce().
std::vector<unsigned int> assembler_1_c::hidden_rows [private] |
Referenced by hiderows(), iterative(), reduce(), save(), setPosition(), and unhiderows().
std::vector<unsigned int> assembler_1_c::holeColumns [private] |
Referenced by iterative(), and prepare().
unsigned int assembler_1_c::holes [private] |
Referenced by createMatrix(), and iterative().
unsigned long assembler_1_c::iterations [private] |
Referenced by getIterations(), and iterative().
std::vector<unsigned int> assembler_1_c::left [private] |
std::vector<unsigned int> assembler_1_c::max [private] |
std::vector<unsigned int> assembler_1_c::min [private] |
std::vector<unsigned int> assembler_1_c::next_row_stack [private] |
Referenced by assemble(), assembler_1_c(), getFinished(), iterative(), save(), and setPosition().
unsigned int assembler_1_c::piecenumber [private] |
Referenced by createMatrix(), and getPiecenumber().
std::vector<piecePosition> assembler_1_c::piecePositions [private] |
Referenced by AddPieceNode(), clumpify(), getPieceInformation(), and reduce().
const problem_c* assembler_1_c::puzzle [protected] |
Referenced by canPlace(), createMatrix(), getAssembly(), getPiecePlacement(), getPiecePlacementCount(), prepare(), and solution().
unsigned int assembler_1_c::reducePiece [protected] |
Referenced by getReducePiece(), prepare(), and reduce().
std::vector<unsigned int> assembler_1_c::right [private] |
Referenced by AddPieceNode(), AddRangeNode(), AddVoxelNode(), clumpify(), cover_column_only(), cover_column_rows(), find_best_unclosed_column(), GenerateFirstRow(), getRight(), hiderow(), hiderows(), iterative(), open_column_conditions_fulfillable(), reduce(), remove_column(), remove_row(), setPosition(), and uncover_column_only().
std::vector<unsigned int> assembler_1_c::rows [private] |
Referenced by getAssembly(), iterative(), save(), and setPosition().
bool assembler_1_c::running [private] |
Referenced by assemble(), and stopped().
std::vector<unsigned int> assembler_1_c::task_stack [private] |
Referenced by assembler_1_c(), iterative(), save(), and setPosition().
std::vector<unsigned int> assembler_1_c::up [private] |
std::vector<unsigned int> assembler_1_c::weight [private] |
Referenced by AddPieceNode(), AddRangeNode(), AddVoxelNode(), clumpify(), column_condition_fulfillable(), column_condition_fulfilled(), cover_column_rows(), find_best_unclosed_column(), GenerateFirstRow(), hiderow(), hiderows(), iterative(), open_column_conditions_fulfillable(), reduce(), remove_row(), setPosition(), uncover_column_rows(), and unhiderow().