1 /* BurrTools 2 * 3 * BurrTools is the legal property of its developers, whose 4 * names are listed in the COPYRIGHT file, which is included 5 * within the source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 20 */ 21 #ifndef __MOVEMENTCACHE_H__ 22 #define __MOVEMENTCACHE_H__ 23 24 class voxel_c; 25 class problem_c; 26 class gridType_c; 27 28 /** 29 * Calculates and stores the information required for movement analysis 30 * 31 * The movement cache calculates the following value: 32 * - How far can one piece be moved relative to another piece, used by normal movement analysis 33 * 34 * Because calculating this information is expensive all the values 35 * gained are stored in a table for later retrieval. That is why it 36 * is called cache 37 * 38 * Internally this class holds a hash table for the stored values and 39 * calls abstract functions for the calculation of the values, when they 40 * are not inside the table. 41 * 42 * So only the derived classes do actually calculate something. 43 */ 44 class movementCache_c { 45 46 private: 47 48 /** 49 * values are saved within a hash table, this is the entry for the table for the movement data 50 */ 51 typedef struct moEntry { 52 53 int dx; ///< relative x position of the 2nd piece 54 int dy; ///< relative y position of the 2nd piece 55 int dz; ///< relative z position of the 2nd piece 56 57 unsigned int s1; ///< id of the first involved shape 58 unsigned int s2; ///< id of the second involved shape 59 60 /* the transformations of the 2 involved pieces 61 * normally we would need only one transformation, that for piece 2 62 * but the calculations involved to transform the 2 pieces so that 63 * piece one has a fixed transformation are too expensive 64 */ 65 unsigned short t1; ///< orientation of the first shape 66 unsigned short t2; ///< orientation of the second shape 67 68 /** the possible movement in positive directions */ 69 unsigned int * move; 70 71 /** next in the linked list of the hash table */ 72 struct moEntry * next; 73 74 } moEntry; 75 76 /** the hash table */ 77 moEntry ** moHash; 78 79 unsigned int moTableSize; ///< size of the hash table 80 unsigned int moEntries; ///< number of entries in the table 81 82 /** 83 * Saves the shapes in all orientations. 84 * The voxel spaces are calculated on demand. The entry at the zero-th position are 85 * pointers into the puzzle, so we must not free them 86 */ 87 const voxel_c *** shapes; 88 89 /** the mapping of piece numbers to shape ids */ 90 unsigned int * pieces; 91 92 /** number of shapes */ 93 unsigned int num_shapes; 94 95 /** number of possible transformations for each shape */ 96 unsigned int num_transformations; 97 98 void moRehash(void); ///< this function resizes the hash table to roughly twice the size 99 100 /** when the entry is not inside the table, this function calculates the values for the movement info */ 101 virtual unsigned int* moCalcValues(const voxel_c * sh1, const voxel_c * sh2, int dx, int dy, int dz) = 0; 102 103 /// the gridtype used. We need this to make copies and transformations of the shapes 104 const gridType_c * gt; 105 106 /// get the transformed shape from the shapes array, calculating missing ones 107 const voxel_c * getTransformedShape(unsigned int s, unsigned char t); 108 109 public: 110 111 /** create the cache. The cache is then fixed to the puzzle and the problem, it can 112 * and should be reused to analyse all assemblies found but can not be used for another puzzle 113 */ 114 movementCache_c(const problem_c * puz); 115 116 virtual ~movementCache_c(void); 117 118 /** 119 * return the values, that are: 120 * how far can the 2nd piece be moved in positive x, y and z direction, when 121 * the 2nd piece is offset by dx, dy and dz relative to the first, 122 * the 2 pieces are the pieces p1 and p2 from the puzzle and problem defined in the constructor 123 * and the 2 pieces are transformed by t1 and t2 124 */ 125 void getMoValue(int dx, int dy, int dz, unsigned char t1, unsigned char t2, unsigned int p1, unsigned int p2, unsigned int * movements); 126 127 /** 128 * return the number of different directions of movement that are possible within 129 * the space grid that that movement cache is for 130 */ 131 virtual unsigned int numDirections(void) = 0; 132 133 /** return the movement vector of the given direction */ 134 virtual void getDirection(unsigned int dir, int * x, int * y, int * z) = 0; 135 136 private: 137 138 // no copying and assigning 139 movementCache_c(const movementCache_c&); 140 void operator=(const movementCache_c&); 141 }; 142 143 #endif 144