assembler_1_c Class Reference

This class is an assembler class. More...

#include <assembler_1.h>

Inheritance diagram for assembler_1_c:

Inheritance graph
[legend]
Collaboration diagram for assembler_1_c:

Collaboration graph
[legend]

List of all members.

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_cgetAssembly (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_cbgetCallback (void)
unsigned int getPiecenumber (void)
void checkForTransformedAssemblies (unsigned int pivot, mirrorInfo_c *mir)

Protected Attributes

const problem_cpuzzle
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_cbasm_bc
std::vector< piecePositionpiecePositions
bool avoidTransformedAssemblies
unsigned int avoidTransformedPivot
mirrorInfo_cavoidTransformedMirror
bool complete
 set to true, when complete analysis is requested
bool debug
int debug_loops
unsigned long iterations


Detailed Description

This class is an assembler class.

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.


Constructor & Destructor Documentation

assembler_1_c::assembler_1_c ( void   ) 

References next_row_stack, and task_stack.

assembler_1_c::~assembler_1_c ( void   ) 

assembler_1_c::assembler_1_c ( const assembler_1_c  )  [private]


Member Function Documentation

int assembler_1_c::AddPieceNode ( unsigned int  piece,
unsigned int  rot,
unsigned int  x,
unsigned int  y,
unsigned int  z 
) [protected]

References colCount, down, left, piecePositions, right, up, and weight.

Referenced by prepare().

void assembler_1_c::AddRangeNode ( unsigned int  col,
unsigned int  piecenode,
unsigned int  weight 
) [protected]

References colCount, down, left, right, up, and weight.

Referenced by prepare().

void assembler_1_c::AddVoxelNode ( unsigned int  col,
unsigned int  piecenode 
) [protected]

References bt_assert, colCount, down, left, right, up, and weight.

Referenced by prepare().

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]

bool assembler_1_c::canPlace ( const voxel_c piece,
int  x,
int  y,
int  z 
) const [private]

void assembler_1_c::checkForTransformedAssemblies ( unsigned int  pivot,
mirrorInfo_c mir 
) [protected]

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]

References colCount, max, min, and weight.

Referenced by iterative().

bool assembler_1_c::column_condition_fulfilled ( int  col  )  [private]

References max, min, and weight.

Referenced by iterative().

void assembler_1_c::cover_column_only ( int  col  )  [private]

References left, and right.

Referenced by iterative(), and setPosition().

void assembler_1_c::cover_column_rows ( int  col  )  [private]

References colCount, down, right, up, and weight.

Referenced by iterative(), and setPosition().

assembler_1_c::errState assembler_1_c::createMatrix ( const problem_c ,
bool  ,
bool  ,
bool   
) [virtual]

void assembler_1_c::debug_step ( unsigned long  num = 1  )  [virtual]

Reimplemented from assembler_c.

References abbort, asm_bc, debug, debug_loops, and iterative().

int assembler_1_c::find_best_unclosed_column ( void   )  [private]

References betterParams(), colCount, max, min, right, and weight.

Referenced by iterative().

void assembler_1_c::GenerateFirstRow ( unsigned int  res_filled  )  [protected]

References colCount, down, headerNodes, left, max, min, right, up, and weight.

Referenced by prepare().

assembly_c * assembler_1_c::getAssembly ( void   )  [virtual]

assembler_cb* assembler_1_c::getCallback ( void   )  [inline, protected]

References asm_bc.

Referenced by solution().

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]

References bt_assert, and piecePositions.

Referenced by getAssembly(), and getPiecePlacement().

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]

unsigned int assembler_1_c::getPiecePlacementCount ( unsigned int  piece  )  const [virtual]

Reimplemented from assembler_c.

References problem_c::getShapeMax(), and puzzle.

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]

bool assembler_1_c::open_column_conditions_fulfillable ( void   )  [private]

References colCount, max, min, right, and weight.

Referenced by iterative(), and reduce().

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]

References down, left, and right.

Referenced by clumpify().

void assembler_1_c::remove_row ( register unsigned int  r  )  [private]

References colCount, down, right, up, and weight.

Referenced by reduce().

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]

References left, and right.

Referenced by iterative().

void assembler_1_c::uncover_column_rows ( int  col  )  [private]

References colCount, down, left, up, and weight.

Referenced by iterative().

void assembler_1_c::unhiderow ( int  r  )  [private]

References colCount, down, left, up, and weight.

Referenced by reduce(), and unhiderows().

void assembler_1_c::unhiderows ( void   )  [private]

References hidden_rows, and unhiderow().

Referenced by iterative().


Member Data Documentation

bool assembler_1_c::abbort [private]

Referenced by assemble(), debug_step(), iterative(), and stop().

Referenced by assemble(), debug_step(), and getCallback().

unsigned int assembler_1_c::avoidTransformedPivot [private]

std::vector<unsigned int> assembler_1_c::colCount [private]

std::vector<unsigned int> assembler_1_c::column_stack [private]

Referenced by iterative(), save(), and setPosition().

bool assembler_1_c::complete [private]

set to true, when complete analysis is requested

Referenced by createMatrix(), and solution().

bool assembler_1_c::debug [private]

Referenced by assemble(), debug_step(), and iterative().

Referenced by debug_step(), and iterative().

std::vector<unsigned int> assembler_1_c::down [private]

Referenced by createMatrix(), and getErrorsParam().

Referenced by assemble(), and createMatrix().

std::vector<unsigned int> assembler_1_c::finished_a [private]

std::vector<unsigned int> assembler_1_c::finished_b [private]

unsigned int assembler_1_c::headerNodes [private]

Referenced by GenerateFirstRow(), iterative(), and reduce().

std::vector<unsigned int> assembler_1_c::hidden_rows [private]

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]

unsigned int assembler_1_c::piecenumber [private]

Referenced by createMatrix(), and getPiecenumber().

const problem_c* assembler_1_c::puzzle [protected]

unsigned int assembler_1_c::reducePiece [protected]

Referenced by getReducePiece(), prepare(), and reduce().

std::vector<unsigned int> assembler_1_c::right [private]

std::vector<unsigned int> assembler_1_c::rows [private]

bool assembler_1_c::running [private]

Referenced by assemble(), and stopped().

std::vector<unsigned int> assembler_1_c::task_stack [private]

std::vector<unsigned int> assembler_1_c::up [private]

std::vector<unsigned int> assembler_1_c::weight [private]


The documentation for this class was generated from the following files:

Generated on Sun Oct 10 10:02:42 2010 for BurrTools by  doxygen 1.5.8