Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include "liberty.h" | |
25 | #include "dfa.h" | |
26 | ||
27 | #include <memory.h> | |
28 | ||
29 | /* Array for use by TRANSFORM() macro. */ | |
30 | int transformation[MAX_OFFSET][8]; | |
31 | ||
32 | /* Matrix array for use by TRANSFORM2() macro. */ | |
33 | const int transformation2[8][2][2] = { | |
34 | { { 1, 0}, | |
35 | { 0, 1}}, /* a - identity transformation matrix */ | |
36 | ||
37 | { { 0, 1}, | |
38 | {-1, 0}}, /* g - rotate 90 clockwise */ | |
39 | ||
40 | { {-1, 0}, | |
41 | { 0, -1}}, /* d - rotate 180 */ | |
42 | ||
43 | { { 0, -1}, | |
44 | { 1, 0}}, /* f - rotate 90 counter-clockwise */ | |
45 | ||
46 | { { 0, -1}, | |
47 | {-1, 0}}, /* h - rotate 90 clockwise and flip on x axis */ | |
48 | ||
49 | { {-1, 0}, | |
50 | { 0, 1}}, /* b - flip on x axis */ | |
51 | ||
52 | { { 0, 1}, | |
53 | { 1, 0}}, /* e - rotate 90 counter-clockwise and flip on x axis */ | |
54 | ||
55 | { { 1, 0}, | |
56 | { 0, -1}} /* c - flip on y axis */ | |
57 | }; | |
58 | ||
59 | ||
60 | /* Initialize transformation[][] array. */ | |
61 | void | |
62 | transformation_init(void) | |
63 | { | |
64 | int k; | |
65 | int dx; | |
66 | int dy; | |
67 | ||
68 | for (k = 0; k < 8; k++) { | |
69 | for (dy = -MAX_BOARD+1; dy <= MAX_BOARD-1; dy++) { | |
70 | for (dx = -MAX_BOARD+1; dx <= MAX_BOARD-1; dx++) { | |
71 | int tx; | |
72 | int ty; | |
73 | ||
74 | TRANSFORM2(dx, dy, &tx, &ty, k); | |
75 | transformation[OFFSET(dx, dy)][k] = DELTA(tx, ty); | |
76 | } | |
77 | } | |
78 | } | |
79 | } | |
80 | /* Spiral orders for DFA matching and building. */ | |
81 | int spiral[DFA_MAX_ORDER][8]; | |
82 | ||
83 | /* The spiral order is the way we scan the board, we begin on the | |
84 | * anchor and we progressively scan all its neigbouring intersections, | |
85 | * collecting all the known patterns we meet on our way: | |
86 | * | |
87 | * 4 4 4 | |
88 | * 1 1 13 13 513 513 ... and so on until we reach a | |
89 | * 2 2 2 2 827 stopping state in the DFA. | |
90 | * 6 | |
91 | * | |
92 | * Build the spiral order for each transformation: instead of changing | |
93 | * the board or changing the patterns, we only change the order. For | |
94 | * e.g. the same DFA can perform the pattern matching | |
95 | * | |
96 | * That way for identity: | |
97 | * | |
98 | * 40 04 | |
99 | * 5139 and this way for mirror symetry: 9315 | |
100 | * 827 728 | |
101 | * 6 6 | |
102 | * | |
103 | * Anther possibility is to generate one string by pattern and by | |
104 | * transformation in `mkpat' to avoid any runtime transformation but | |
105 | * it drastically increases the size of DFAs. | |
106 | */ | |
107 | void | |
108 | build_spiral_order(void) | |
109 | { | |
110 | int i; | |
111 | int j; | |
112 | int k; | |
113 | char mark[2 * DFA_MAX_BOARD + 1][2 * DFA_MAX_BOARD + 1]; | |
114 | int queue_i[DFA_MAX_ORDER]; | |
115 | int queue_j[DFA_MAX_ORDER]; | |
116 | int queue_start = 0; | |
117 | int queue_end = 1; | |
118 | ||
119 | static const int delta_i[4] = { 1, 0, -1, 0}; | |
120 | static const int delta_j[4] = { 0, 1, 0, -1}; | |
121 | ||
122 | /* Initialization. */ | |
123 | memset(mark, 1, sizeof(mark)); | |
124 | for (i = 1; i < 2 * DFA_MAX_BOARD; i++) { | |
125 | for (j = 1; j < 2 * DFA_MAX_BOARD; j++) | |
126 | mark[i][j] = 0; | |
127 | } | |
128 | ||
129 | queue_i[0] = DFA_MAX_BOARD; | |
130 | queue_j[0] = DFA_MAX_BOARD; | |
131 | mark[DFA_MAX_BOARD][DFA_MAX_BOARD] = 1; | |
132 | ||
133 | do { | |
134 | int transformation; | |
135 | ||
136 | /* Transform queued coordinates and store DFA offsets in spiral[][]. */ | |
137 | for (transformation = 0; transformation < 8; transformation++) { | |
138 | TRANSFORM2(queue_i[queue_start] - DFA_MAX_BOARD, | |
139 | queue_j[queue_start] - DFA_MAX_BOARD, | |
140 | &i, &j, transformation); | |
141 | spiral[queue_start][transformation] = DFA_BASE * i + j; | |
142 | } | |
143 | ||
144 | for (k = 0; k < 4; k++) { | |
145 | i = queue_i[queue_start] + delta_i[k]; | |
146 | j = queue_j[queue_start] + delta_j[k]; | |
147 | ||
148 | if (!mark[i][j]) { | |
149 | queue_i[queue_end] = i; | |
150 | queue_j[queue_end++] = j; | |
151 | mark[i][j] = 1; | |
152 | } | |
153 | } | |
154 | } while (++queue_start < queue_end); | |
155 | ||
156 | if (0) { | |
157 | int transformation; | |
158 | for (transformation = 0; transformation < 8; transformation++) { | |
159 | fprintf(stderr, "Transformation %d:\n", transformation); | |
160 | for (k = 0; k < 16; k++) { | |
161 | fprintf(stderr, "\t%d(%c); %d\n", k, 'A' + k, | |
162 | spiral[k][transformation]); | |
163 | } | |
164 | } | |
165 | } | |
166 | } | |
167 | ||
168 | ||
169 | /* | |
170 | * Local Variables: | |
171 | * tab-width: 8 | |
172 | * c-basic-offset: 2 | |
173 | * End: | |
174 | */ |