head 1.12; access; symbols; locks poly:1.12; strict; comment @ * @; 1.12 date 2006.04.13.05.22.57; author poly; state Exp; branches; next 1.11; 1.11 date 2006.04.11.03.19.24; author poly; state Exp; branches; next 1.10; 1.10 date 2006.04.09.21.06.27; author poly; state Exp; branches; next 1.9; 1.9 date 2006.04.08.17.28.22; author poly; state Exp; branches; next 1.8; 1.8 date 2006.04.06.04.43.51; author poly; state Exp; branches; next 1.7; 1.7 date 2006.04.06.03.48.43; author poly; state Exp; branches; next 1.6; 1.6 date 2006.04.05.03.55.11; author poly; state Exp; branches; next 1.5; 1.5 date 2006.04.03.03.11.31; author poly; state Exp; branches; next 1.4; 1.4 date 2006.04.01.08.38.44; author poly; state Exp; branches; next 1.3; 1.3 date 2006.03.31.07.19.13; author poly; state Exp; branches; next 1.2; 1.2 date 2006.03.31.05.06.03; author poly; state Exp; branches; next 1.1; 1.1 date 2006.03.30.07.23.42; author poly; state Exp; branches; next ; desc @in @ 1.12 log @in . @ text @/* * fittings.h * omino_fitting_2006 * * Created by david van brink on 3/29/06. * Copyright 2006 __MyCompanyName__. All rights reserved. * */ #ifndef FITTINGS_H #define FITTINGS_H /* Definitions: Cell -- a square, either in a polyomino or in a field to be tiled with polyominoes Field -- an area to be filled with polyominoes, made of cells Points -- a list of coordinates describing a group of tiles. Sometimes the order matters, such as the coordinate list for a perimeter (used for hole-detection). Offset -- we expand polyominoes so that, for a particular width of field, each cell's position is identified by an arithmetic offset. This lets us deal with single values rather than coordinate pairs. */ // X and Y coordiantes are RIGHT and UP, just like math, ok? /* fillOrder -- there are 8 possible fill orders 0: right,up 1: left ,up 2: right,down 3: left ,down 4: up ,right 5: down ,right 6: up ,left 7: down ,left */ // Size we use in the field typedef long OFCell; #define kCellWall 0x80000000 #define kCellOmino 0x000000ff #define kCellAnnotation 0xff00 // misc printing value here #define kCellID 0x00ff0000 // unique cross of orientation&cell-index, for row-identification /* A "Sequence element" describes which cell to attempt to fill next, OR some other action to take. If it's another cell to fill, it is encoded like so: ACTION: attempt-to-fiil high byte: 00..07 for fill-directon low-3-bytes: xxxxxx offset to fill next ACTION: check-for-halfstrip-repeat high byte: 80 -- check a row for repeat high byte: c0 -- check a column for repeat middle-high byte: xx row or column number we have just finished middle-low byte: ignored low byte: yy -- row or column number to check up to, from current */ typedef int OFSequenceElement; #define SEQUENCE_IMPERATIVE_ROWCOMPLETE 0x80000000 #define SEQUENCE_IMPERATIVE_COLUMNCOMPLETE 0xc0000000 #define SEQUENCE_IMPERATIVE_SUCCESS 0xf0000000 #define PACK_SEQUENCE_OFFSET_DIR(_offset,_dir) ((_offset) | ((_dir) << 24)) #define PACK_SEQUENCE_IMPERATIVE(_rowcol_imper,_thisone,_scanfrom) ((_rowcol_imper) | ((_thisone) << 16) | (_scanfrom)) #define UNPACK_SEQUENCE_OFFSET(_seqval) ((_seqval) & 0x00ffFFFF) #define UNPACK_SEQUENCE_DIR(_seqval) (((_seqval) >> 24) & 0x00ff) #define UNPACK_SEQUENCE_IMPERATIVE(_seqval) ((_seqval) & 0xf0000000) #define UNPACK_SEQUENCE_IMPERATIVE_VALUE(_seqval) (((_seqval) >> 16) & 0x000000ff) #define UNPACK_SEQUENCE_IMPERATIVE_FROM(_seqval) ((_seqval) & 0x000000ff) // Lesser Structures typedef struct { int x,y; } OFCellPoint; // A collection of points -- allocated in on block typedef struct { int cellCount; OFCellPoint cells[0]; } OFPoints; // A field -- accessed by offsets, one block typedef struct { int width; // not counting boundary, &c int height; // not counting boundary, &c int rowCells; // cells per row, counting boundary int cell00; // lower left cell offset int cellCount; // COUNTING ALL cells, including boundary int *rowChecksums; // hash values for completed rows, for halfstrip testing int *columnChecksums; // hash values for completed columns, for halfstrip testing OFCell cells[0]; } OFField; // The placement of a single Omino typedef struct { int orientation; // the digit 0-7 int fieldCell; // offset into field where placed int cellNumber; // sequence number of where placed int dir; // which fill-direction was used } OFDigit; // A single orientation of an omino, // unrolled for quick-rendering/placement. typedef struct { int cellCount; // number of squares in the omino int cellOffsets[0]; // offsets into the tile for the current field size } OFOffsets; // A collection of orientations -- must be freed specially typedef struct { char *name; int fillOrder; // 0 means right,down int fieldRow; // number of cells per field row (usually width+2) int orientationCount; // usually 8 OFOffsets *orientations[8]; // room for 8 pointers OFOffsets *perimeters[8]; // 8 pointers to PERIMETERs, paired to the orientations } OFOmino; // The state of a search-in-progress typedef struct { long long startTime; long long dur; // totol microseconds used long long placementsTried; long long placementsPlaced; int perimeterCheck; // how many cells of perimeter to check, for holes, >1 OFField *field; OFOmino *omino; int fillCount; // how many needed to fill int curCount; // how many placed now OFDigit digit[0]; } OFSearch; // This kind of search enumerates the orders and directions // of cells to fill. typedef struct { long long startTime; long long dur; // totol microseconds used long long placementsTried; long long placementsPlaced; int deepestCount; int halfstripHalting; // 1 for yes, normal. long long halfstripRejections; int perimeterCheck; // how many cells of perimeter to check, for holes, >1 int cellCount; // cells to actually populate OFSequenceElement *offsetSequence; // offsets into field for each, in order // int *directionSequence; OFField *field; // bitmap to populate OFOmino *omino[8]; // the different fill orders int fillCount; // how many needed to fill int curCount; // how many placed now OFDigit digit[0]; } OFSequenceSearch; OFPoints *copyPoints(OFPoints *original); OFOmino *newOFOmino(char *ominoDescription, int fieldRow,int fillOrder); OFField *newOFField(int width,int height); void freeOFField(OFField **field); OFSearch *newSearch(OFField *field,OFOmino *omino); OFSequenceSearch *newSequenceSearch(char *ominoDescription,int width,int height); void freeSequenceSearchAt(OFSequenceSearch **search); // lesser routines, exposed for testing OFPoints *pointsFromDescription(char *ominoDescription); void positionFirstPoint(OFPoints *cells); OFPoints *getPerimeterPoints(OFPoints *cells); void rotatePoints90(OFPoints *cells); void reflectPointsY(OFPoints *cells); OFOffsets *offsetsFromPoints(OFPoints *cells,int fieldRow); void rotatePoints(OFPoints *points,int direction); void computeRowChecksum(OFField *field,int row); void computeColumnChecksum(OFField *field,int column); #endif FITTINGS_H // end of file@ 1.11 log @in @ text @a56 1 d74 4 d79 1 d82 3 a84 1 a164 19 // The state of a search-in-progress typedef struct { long long startTime; long long dur; // totol microseconds used long long placementsTried; long long placementsPlaced; int perimeterCheck; // how many cells of perimeter to check, for holes, >1 OFField *field; // bitmap to populate OFField *spiralField; // order to fill from OFOmino *omino[8]; // the different fill orders int fillCount; // how many needed to fill int curCount; // how many placed now OFDigit digit[0]; } OFSpiralSearch; d174 3 d186 2 a187 2 unsigned int fillCount; // how many needed to fill unsigned int curCount; // how many placed now a201 1 OFSpiralSearch *newSpiralSearch(char *ominoDescription, int width, int height); a214 3 OFField *makeSpiralField(OFField *field); OFField *makeRightLeftField(OFField *field); OFField *makeRightField(OFField *field); @ 1.10 log @in @ text @a31 15 /* orientations -- there are 8 possible orientations. Using standard coordinates -- x right, y up: 0 -- Original 1 -- Y-reflected 2 -- +90 (CCW) 3 -- +90 (CCW) and then Y-reflected 4 -- +180 (CCW) 5 -- +180 (CCW) and then Y-reflected 6 -- +270 (CCW) 7 -- +270 (CCW) and then Y-reflected */ d48 3 a50 1 typedef short OFCell; d52 1 a52 2 #define kCellWall 0x8000 #define kCellOmino 0x00ff d54 2 a55 1 #define kCellAnnotation 0x7f00 // misc printing value here d68 1 a68 1 high byte: 81 -- check a column for repeat d73 5 a77 1 typedef int OFOffsetSequenceElement; d104 2 d191 2 a192 2 int *offsetSequence; // offsets into field for each, in order int *directionSequence; d196 2 a197 2 int fillCount; // how many needed to fill int curCount; // how many placed now d206 2 a207 1 OFField *newField(int width,int height); d211 1 d214 1 d229 7 @ 1.9 log @in @ text @d71 19 @ 1.8 log @in @ text @d102 2 d166 24 d199 1 @ 1.7 log @in @ text @d63 1 a63 1 typedef char OFCell; d65 4 a68 2 #define kCellWall 0x80 #define kCellOmino 0x7f d185 2 @ 1.6 log @in @ text @d140 25 d170 2 d182 2 @ 1.5 log @in @ text @d13 17 d34 11 a44 9 orientations -- there are 8 possible orientations 0: original 1: rotated +90 (CCW) 2: rotated +180 (CCW) 3: rotated +270 (CCW) 4: original,reflected in Y axis 5: rotated +90 (CCW) and then reflected in Y axis 6: rotated +180 (CCW) and then reflected in Y axis 7: rotated +270 (CCW) and then reflected in Y axis d76 1 d81 1 a81 1 } OFOminoCells; d84 1 a84 1 // Field used for filling d108 1 a108 1 } OFOrientedOmino; d110 1 a110 1 // A collection of orientations d117 2 a118 2 OFOrientedOmino *orientations[8]; // room for 8 pointers OFOrientedOmino *perimeters[8]; // 8 pointers to PERIMETERs, paired to the orientations d148 6 a153 6 OFOminoCells *cellsFromDescription(char *ominoDescription); void positionFirstCell(OFOminoCells *cells,int fillOrder); OFOminoCells *discoverPerimeter(OFOminoCells *cells); void rotateCells90(OFOminoCells *cells); void reflectCellsY(OFOminoCells *cells); OFOrientedOmino *cellsToOffsets(OFOminoCells *cells,int fieldRow); @ 1.4 log @in @ text @d46 18 d93 1 d98 1 d106 5 a110 1 long long endTime; d126 10 @ 1.3 log @in @ text @d85 3 @ 1.2 log @checkpoint @ text @d90 1 a90 1 } OFInProgress; d96 3 @ 1.1 log @Initial revision @ text @d10 3 d49 6 a54 3 int width; // not counting boundary, &c int height; // not counting boundary, &c OFCell *field; d57 9 a65 1 // A single orientation of an omino d82 9 a90 2 OFOmino *newOFOmino(char *ominoDescription, int fieldRow,int fillOrder); d93 2 d96 1 @