root/06/libkombilo/search.cpp

Revision 253, 178.0 KB (checked in by ug, 3 years ago)

Fixed bug in search with wildcards.

Line 
1// File: search.cpp
2// part of libkombilo, http://www.u-go.net/kombilo/
3
4// Copyright (c) 2006-7 Ulrich Goertz <u@g0ertz.de>
5
6// Permission is hereby granted, free of charge, to any person obtaining a copy of
7// this software and associated documentation files (the "Software"), to deal in
8// the Software without restriction, including without limitation the rights to
9// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10// of the Software, and to permit persons to whom the Software is furnished to do
11// so, subject to the following conditions:
12//
13// The above copyright notice and this permission notice shall be included in all
14// copies or substantial portions of the Software.
15//
16// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22// SOFTWARE.
23
24#include "sgfparser.h"
25#include "abstractboard.h"
26#include "search.h"
27#include <stdio.h>
28#include <string>
29#include <cstring>
30
31using std::min;
32using std::max;
33using std::string;
34using std::vector;
35using std::map;
36using std::pair;
37using std::make_pair;
38using std::stack;
39
40#if defined(_MSC_VER)
41#include <algorithm>
42#else
43using std::sort;
44#endif
45
46SnapshotVector::SnapshotVector() : vector<unsigned char>() {
47  current = begin();
48}
49
50SnapshotVector::SnapshotVector(char* c, int size) : vector<unsigned char>() {
51  for(int i=0; i<size; i++) push_back(c[i]);
52  current = begin();
53}
54
55void SnapshotVector::pb_int(int d) {
56  for(int i = 0; i < 4; i++) {
57    push_back((unsigned char)(d % 256));
58    d = d >> 8;
59  }
60}
61
62void SnapshotVector::pb_charp(char* c, int size) {
63  pb_int(size);
64  for(int i=0; i<size; i++) push_back(c[i]);
65}
66
67void SnapshotVector::pb_intp(int* p, int size) {
68  pb_int(size);
69  for(int i=0; i<size; i++) pb_int(p[i]);
70}
71
72void SnapshotVector::pb_string(string s) {
73  pb_int(s.size()+1);
74  for(unsigned int i=0; i<s.size(); i++) push_back(s[i]);
75  push_back(0);
76}
77
78void SnapshotVector::pb_char(char c) {
79  push_back(c);
80}
81
82int SnapshotVector::retrieve_int() {
83  int result = 0;
84  for(int i=0; i<4; i++) {
85    result += *current << (i*8);
86    current++;
87  }
88  return result;
89}
90
91int* SnapshotVector::retrieve_intp() {
92  int sz = retrieve_int();
93  int* result = new int[sz];
94  for(int i=0; i<sz; i++)
95    result[i] = retrieve_int();
96  return result;
97}
98
99char SnapshotVector::retrieve_char() {
100  char c = *current;
101  current++;
102  return c;
103}
104
105char* SnapshotVector::retrieve_charp() {
106  int sz = retrieve_int();
107  char* result = new char[sz];
108  for(int i=0; i<sz; i++) {
109    result[i] = *current;
110    current++;
111  }
112  return result;
113}
114
115string SnapshotVector::retrieve_string() {
116  char* cp = retrieve_charp();
117  string s(cp);
118  delete [] cp;
119  return s;
120}
121
122char* SnapshotVector::to_charp() {
123  char* result = new char[size()];
124  int counter = 0;
125  for(SnapshotVector::iterator it = begin(); it != end(); it++) result[counter++] = *it;
126  return result;
127}
128
129
130PatternError::PatternError() {}
131
132Continuation::Continuation() {
133  B  = 0;
134  W  = 0;
135  tB = 0;
136  tW = 0;
137  wB = 0;
138  lB = 0;
139  wW = 0;
140  lW = 0;
141}
142
143void Continuation::from_snv(SnapshotVector& snv) {
144  B = snv.retrieve_int();
145  W = snv.retrieve_int();
146  tB = snv.retrieve_int();
147  tW = snv.retrieve_int();
148  wB = snv.retrieve_int();
149  lB = snv.retrieve_int();
150  wW = snv.retrieve_int();
151  lW = snv.retrieve_int();
152}
153
154void Continuation::to_snv(SnapshotVector& snv) {
155  snv.pb_int(B);
156  snv.pb_int(W);
157  snv.pb_int(tB);
158  snv.pb_int(tW);
159  snv.pb_int(wB);
160  snv.pb_int(lB);
161  snv.pb_int(wW);
162  snv.pb_int(lW);
163}
164
165Symmetries::Symmetries(char sX, char sY) {
166  sizeX = sX;
167  sizeY = sY;
168  dataX = new char[sizeX*sizeY];
169  dataY = new char[sizeX*sizeY];
170  dataCS = new char[sizeX*sizeY];
171  for(int i=0; i<sizeX*sizeY; i++) {
172    dataX[i] = -1;
173    dataY[i] = -1;
174    dataCS[i] = -1;
175  }
176}
177
178Symmetries::~Symmetries() {
179  delete [] dataX;
180  delete [] dataY;
181  delete [] dataCS;
182}
183
184Symmetries::Symmetries(const Symmetries& s) {
185  sizeX = s.sizeX;
186  sizeY = s.sizeY;
187  dataX = new char[sizeX*sizeY];
188  dataY = new char[sizeX*sizeY];
189  dataCS = new char[sizeX*sizeY];
190  for(int i=0; i<sizeX*sizeY; i++) {
191    dataX[i] = s.dataX[i];
192    dataY[i] = s.dataY[i];
193    dataCS[i] = s.dataCS[i];
194  }
195}
196
197Symmetries& Symmetries::operator=(const Symmetries& s) {
198  if (&s != this) {
199    sizeX = s.sizeX;
200    sizeY = s.sizeY;
201    delete [] dataX;
202    delete [] dataY;
203    delete [] dataCS;
204    dataX = new char[sizeX*sizeY];
205    dataY = new char[sizeX*sizeY];
206    dataCS = new char[sizeX*sizeY];
207    for(int i=0; i<sizeX*sizeY; i++) {
208      dataX[i] = s.dataX[i];
209      dataY[i] = s.dataY[i];
210      dataCS[i] = s.dataCS[i];
211    }
212  }
213  return *this;
214}
215
216void Symmetries::set(char i, char j, char k, char l, char cs) throw(PatternError) {
217  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) {
218    dataX[i + j*sizeX] = k;
219    dataY[i + j*sizeX] = l;
220    dataCS[i + j*sizeX] = cs;
221  }
222  else throw PatternError();
223}
224
225char Symmetries::getX(char i, char j) throw(PatternError) {
226  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataX[i + j*sizeX];
227  else throw PatternError();
228  return -1;
229}
230
231char Symmetries::getY(char i, char j) throw(PatternError) {
232  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataY[i + j*sizeX];
233  else throw PatternError();
234  return -1;
235}
236
237char Symmetries::getCS(char i, char j) throw(PatternError) {
238  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) return dataCS[i + j*sizeX];
239  else throw PatternError();
240  return -1;
241}
242
243char Symmetries::has_key(char i, char j) throw(PatternError) {
244  if (0 <= i && i < sizeX && 0 <= j && j < sizeY) {
245    if (dataX[i + j*sizeX] == -1) return 0;
246    else return 1;
247  }
248  else throw PatternError();
249  return 0;
250}
251
252
253// ----------- class Pattern -----------------------------------------------
254
255int Pattern::operator==(const Pattern& p) {
256  if (boardsize != p.boardsize) return 0;
257  if (sizeX != p.sizeX || sizeY != p.sizeY) return 0;
258  if (left != p.left || right != p.right || top != p.top || bottom != p.bottom) return 0; 
259  for(int i=0; i < sizeX*sizeY; i++)
260    if (initialPos[i] != p.initialPos[i]) return 0;
261  if (contList != p.contList) return 0;
262  return 1;
263}
264
265
266char Pattern::BW2XO(char c) {
267  if (c == 'B') return 'X';
268  if (c == 'W') return 'O';
269  return c;
270}
271
272char Pattern::getInitial(int i, int j) {
273  return initialPos[i + sizeX*j];
274}
275 
276char Pattern::getFinal(int i, int j) {
277  return finalPos[i + sizeX*j];
278}
279 
280
281Pattern::Pattern() {
282  initialPos = 0;
283  finalPos = 0;
284  flip = 0;
285  colorSwitch = 0;
286  sizeX = 0;
287  sizeY = 0;
288  boardsize = 0;
289  contLabels = 0;
290}
291
292
293Pattern::Pattern(int type, int BOARDSIZE, int sX, int sY, char* iPos, char* CONTLABELS) {
294  flip = 0;
295  colorSwitch = 0;
296  sizeX = sX;
297  sizeY = sY;
298  boardsize = BOARDSIZE;
299  if (CONTLABELS) {
300    contLabels = new char[sizeX * sizeY];
301    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
302  } else contLabels = 0;
303
304  if (type == CORNER_NW_PATTERN || type == FULLBOARD_PATTERN) {
305    left = right = top = bottom = 0;
306  } else if (type == CORNER_NE_PATTERN) {
307    top = bottom = 0;
308    left = right = boardsize - sizeX;
309  } else if (type == CORNER_SE_PATTERN) {
310    top = bottom = boardsize - sizeY;
311    left = right = boardsize - sizeX;
312  } else if (type == CORNER_SW_PATTERN) {
313    top = bottom = boardsize - sizeY;
314    left = right = 0;
315  } else if (type == SIDE_N_PATTERN) {
316    top = bottom = 0;
317    left = 1;
318    right = boardsize -1 - sizeX;
319  } else if (type == SIDE_E_PATTERN) {
320    left = right = boardsize - sizeX;
321    top = 1;
322    bottom = boardsize -1 - sizeY;
323  } else if (type == SIDE_W_PATTERN) {
324    left = right = 0;
325    top = 1;
326    bottom = boardsize -1 - sizeY;
327  } else if (type == SIDE_S_PATTERN) {
328    top = bottom = boardsize - sizeY;
329    left = 1;
330    right = boardsize -1 - sizeX;
331  } else if (type == CENTER_PATTERN) {
332    left = top = 1;
333    right = boardsize -1 - sizeX;
334    bottom = boardsize -1 - sizeY;
335  }
336
337  initialPos = new char[sizeX * sizeY];
338  finalPos = new char[sizeX*sizeY];
339  for(int i=0; i<sizeX*sizeY; i++) {
340    initialPos[i] = iPos[i];
341    finalPos[i] = iPos[i];
342  }
343}
344
345Pattern::Pattern(int type, int BOARDSIZE, int sX, int sY,
346                 char* iPos, vector<MoveNC> CONTLIST, char* CONTLABELS) {
347  flip = 0;
348  colorSwitch = 0;
349  sizeX = sX;
350  sizeY = sY;
351  boardsize = BOARDSIZE;
352  if (CONTLABELS) {
353    contLabels = new char[sizeX * sizeY];
354    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
355  } else contLabels = 0;
356
357  if (type == CORNER_NW_PATTERN || type == FULLBOARD_PATTERN) {
358    left = right = top = bottom = 0;
359  } else if (type == CORNER_NE_PATTERN) {
360    top = bottom = 0;
361    left = right = boardsize - sizeX;
362  } else if (type == CORNER_SE_PATTERN) {
363    top = bottom = boardsize - sizeY;
364    left = right = boardsize - sizeX;
365  } else if (type == CORNER_SW_PATTERN) {
366    top = bottom = boardsize - sizeY;
367    left = right = 0;
368  } else if (type == SIDE_N_PATTERN) {
369    top = bottom = 0;
370    left = 1;
371    right = boardsize -1 - sizeX;
372  } else if (type == SIDE_E_PATTERN) {
373    left = right = boardsize - sizeX;
374    top = 1;
375    bottom = boardsize -1 - sizeY;
376  } else if (type == SIDE_W_PATTERN) {
377    left = right = 0;
378    top = 1;
379    bottom = boardsize -1 - sizeY;
380  } else if (type == SIDE_S_PATTERN) {
381    top = bottom = boardsize - sizeY;
382    left = 1;
383    right = boardsize -1 - sizeX;
384  } else if (type == CENTER_PATTERN) {
385    left = top = 1;
386    right = boardsize -1 - sizeX;
387    bottom = boardsize -1 - sizeY;
388  }
389
390  initialPos = new char[sizeX * sizeY];
391  finalPos = new char[sizeX*sizeY];
392  for(int i=0; i<sizeX*sizeY; i++) {
393    initialPos[i] = iPos[i];
394    finalPos[i] = iPos[i];
395  }
396
397  contList = CONTLIST;
398}
399
400Pattern::Pattern(int le, int ri, int to, int bo, int BOARDSIZE, int sX, int sY,
401                 char* iPos, const vector<MoveNC>& CONTLIST, char* CONTLABELS) throw(PatternError) {
402  // check whether anchor rectangle is valid
403  if (le < 0 || ri+sX > BOARDSIZE || to < 0 || bo+sY > BOARDSIZE || ri < le || bo < to) throw PatternError();
404
405  flip = 0;
406  colorSwitch = 0;
407
408  left = le;
409  right = ri;
410  top = to;
411  bottom = bo;
412  boardsize = BOARDSIZE;
413
414  sizeX = sX;
415  sizeY = sY;
416  if (CONTLABELS) {
417    contLabels = new char[sizeX * sizeY];
418    for(int i=0; i<sizeX*sizeY; i++) contLabels[i] = CONTLABELS[i];
419  } else contLabels = 0;
420
421  initialPos = new char[sizeX * sizeY];
422  finalPos = new char[sizeX*sizeY];
423  for(int i=0; i<sizeX*sizeY; i++) {
424    initialPos[i] = iPos[i];
425    finalPos[i] = iPos[i];
426  }
427
428  contList = CONTLIST;
429}
430
431Pattern::Pattern(SnapshotVector& snv) {
432  flip = snv.retrieve_int();
433  colorSwitch = snv.retrieve_int();
434  left = snv.retrieve_int();
435  right = snv.retrieve_int();
436  top = snv.retrieve_int();
437  bottom = snv.retrieve_int();
438  boardsize = snv.retrieve_int();
439  sizeX = snv.retrieve_int();
440  sizeY = snv.retrieve_int();
441  if (snv.retrieve_char()) { // contLabels?
442    contLabels = snv.retrieve_charp();
443  } else contLabels = 0;
444  initialPos = snv.retrieve_charp();
445  finalPos = snv.retrieve_charp();
446
447  int size = snv.retrieve_int();
448  for(int i=0; i<size; i++)
449    contList.push_back(MoveNC(snv.retrieve_char(), snv.retrieve_char(), snv.retrieve_char())); // x, y, color
450}
451
452void Pattern::to_snv(SnapshotVector& snv) {
453  snv.pb_int(flip);
454  snv.pb_int(colorSwitch);
455  snv.pb_int(left);
456  snv.pb_int(right);
457  snv.pb_int(top);
458  snv.pb_int(bottom);
459  snv.pb_int(boardsize);
460  snv.pb_int(sizeX);
461  snv.pb_int(sizeY);
462  if (contLabels) {
463    snv.pb_char(1);
464    snv.pb_charp(contLabels, sizeX*sizeY);
465  } else snv.pb_char(0);
466  snv.pb_charp(initialPos, sizeX*sizeY);
467  snv.pb_charp(finalPos, sizeX*sizeY);
468  snv.pb_int(contList.size());
469  for(vector<MoveNC>::iterator it = contList.begin(); it != contList.end(); it++) {
470    snv.pb_char(it->x);
471    snv.pb_char(it->y);
472    snv.pb_char(it->color);
473  }
474}
475
476Pattern::~Pattern() {
477  if (initialPos) delete [] initialPos;
478  if (finalPos) delete [] finalPos;
479  if (contLabels) delete [] contLabels;
480}
481
482Pattern::Pattern(const Pattern& p) {
483  left = p.left;
484  right = p.right;
485  top = p.top;
486  bottom = p.bottom;
487  boardsize = p.boardsize;
488  sizeX = p.sizeX;
489  sizeY = p.sizeY;
490  flip = p.flip;
491  colorSwitch = p.colorSwitch;
492
493  initialPos = new char[sizeX*sizeY];
494  finalPos = new char[sizeX*sizeY];
495  if (p.contLabels) contLabels = new char[sizeX*sizeY];
496  else contLabels = 0;
497  for(int i=0; i<sizeX*sizeY; i++) {
498    initialPos[i] = p.initialPos[i];
499    finalPos[i] = p.finalPos[i];
500    if (p.contLabels) contLabels[i] = p.contLabels[i];
501  }
502  contList = p.contList;
503}
504
505Pattern& Pattern::operator=(const Pattern& p) {
506  if (&p != this) {
507    left = p.left;
508    right = p.right;
509    top = p.top;
510    bottom = p.bottom;
511    boardsize = p.boardsize;
512    sizeX = p.sizeX;
513    sizeY = p.sizeY;
514    flip = p.flip;
515    colorSwitch = p.colorSwitch;
516
517    if (initialPos) delete [] initialPos;
518    if (finalPos) delete [] finalPos;
519    if (contLabels) delete [] contLabels;
520
521    initialPos = new char[sizeX*sizeY];
522    finalPos = new char[sizeX*sizeY];
523    if (p.contLabels) contLabels = new char[sizeX*sizeY];
524    else contLabels = 0;
525    for(int i=0; i<sizeX*sizeY; i++) {
526      initialPos[i] = p.initialPos[i];
527      finalPos[i] = p.finalPos[i];
528      if (p.contLabels) contLabels[i] = p.contLabels[i];
529    }
530    contList = p.contList;
531  }
532  return *this;
533}
534
535
536Pattern& Pattern::copy(const Pattern& p) {
537  if (&p != this) {
538    left = p.left;
539    right = p.right;
540    top = p.top;
541    bottom = p.bottom;
542    boardsize = p.boardsize;
543    sizeX = p.sizeX;
544    sizeY = p.sizeY;
545    flip = p.flip;
546    colorSwitch = p.colorSwitch;
547
548    if (initialPos) delete [] initialPos;
549    if (finalPos) delete [] finalPos;
550
551    initialPos = new char[sizeX*sizeY];
552    finalPos = new char[sizeX*sizeY];
553    if (p.contLabels) contLabels = new char[sizeX*sizeY];
554    else contLabels = 0;
555    for(int i=0; i<sizeX*sizeY; i++) {
556      initialPos[i] = p.initialPos[i];
557      finalPos[i] = p.finalPos[i];
558      if (p.contLabels) contLabels[i] = p.contLabels[i];
559    }
560    contList = p.contList;
561  }
562  return *this;
563}
564
565string Pattern::printPattern() {
566  string result;
567  char buf[100];
568  sprintf(buf, "boardsize: %d, area: %d, %d, %d, %d\nsize: %d, %d\n", boardsize, left, right, top, bottom, sizeX, sizeY);
569  result += buf;
570  for(int i=0; i<sizeY; i++) {
571    for(int j=0; j<sizeX; j++) {
572      if (initialPos[i*sizeX + j] == 'X' || initialPos[i*sizeX + j] == 'O' || initialPos[i*sizeX + j] == 'x' || initialPos[i*sizeX + j] == 'x' || initialPos[i*sizeX+j] == '*') result += initialPos[i*sizeX+j];
573      else result += '.';
574    }
575    result += "\n";
576  }
577  result += "\n";
578  return result;
579}
580
581
582int Pattern::flipsX(int i, int x, int y, int XX, int YY) {
583  if (i==0) return x;
584  if (i==1) return XX-x;
585  if (i==2) return x;
586  if (i==3) return XX-x;
587  if (i==4) return y;
588  if (i==5) return YY-y;
589  if (i==6) return y;
590  if (i==7) return YY-y;
591  return -1;
592}
593
594int Pattern::flipsY(int i, int x, int y, int XX, int YY) {
595  if (i==0) return y;
596  if (i==1) return y;
597  if (i==2) return YY-y;
598  if (i==3) return YY-y;
599  if (i==4) return x;
600  if (i==5) return x;
601  if (i==6) return XX-x;
602  if (i==7) return XX-x;
603  return -1;
604}
605
606
607int Pattern::PatternInvFlip(int i) {
608  if (i == 5) return 6;
609  if (i == 6) return 5;
610  return i;
611}
612
613const int composition_table[] = {
614  0, 1, 2, 3, 4, 5, 6, 7,
615  1, 0, 3, 2, 5, 4, 7, 6,
616  2, 3, 0, 1, 6, 7, 4, 5,
617  3, 2, 1, 0, 7, 6, 5, 4,
618  4, 6, 5, 7, 0, 2, 1, 3,
619  5, 7, 4, 6, 1, 3, 0, 2,
620  6, 4, 7, 5, 2, 0, 3, 1,
621  7, 5, 6, 4, 3, 1, 2, 0 };
622
623int Pattern::compose_flips(int i, int j) {
624  return composition_table[j+8*i];
625}
626
627PatternList::PatternList(Pattern& p, int fColor, int nMove) throw(PatternError) {
628  pattern.copy(p);
629  fixedColor = fColor;
630  nextMove = nMove;
631  special = -1;
632  flipTable = new int[16];
633  for(int i=0; i<16; i++) flipTable[i] = -1; // (patternList() relies on this)
634
635  patternList();
636  continuations = new Continuation[pattern.sizeX * pattern.sizeY];
637}
638
639PatternList::~PatternList() {
640  delete [] continuations;
641  delete [] flipTable;
642}
643
644char PatternList::invertColor(char co) {
645  if (co == 'X') return 'O';
646  if (co == 'x') return 'o';
647
648  if (co == 'O') return 'X';
649  if (co == 'o') return 'x';
650
651  return co;
652}
653
654void PatternList::patternList() {
655  vector<Pattern> lCS;
656  vector<pair<int,int> > sy;
657  int boardsize = pattern.boardsize;
658
659  for(int f = 0; f < 8; f++) {
660    int newSizeX = max(Pattern::flipsX(f,0,0,pattern.sizeX,pattern.sizeY),
661                       Pattern::flipsX(f,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));
662    int newSizeY = max(Pattern::flipsY(f,0,0,pattern.sizeX,pattern.sizeY),
663                       Pattern::flipsY(f,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));
664
665    int newLeft = min(Pattern::flipsX(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
666                      Pattern::flipsX(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
667                                      boardsize-1,boardsize-1));
668    int newRight = max(Pattern::flipsX(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
669                       Pattern::flipsX(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
670                                       boardsize-1,boardsize-1)) - (newSizeX-1);
671    int newTop = min(Pattern::flipsY(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
672                     Pattern::flipsY(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
673                                     boardsize-1,boardsize-1));
674    int newBottom = max(Pattern::flipsY(f,pattern.left,pattern.top,boardsize-1,boardsize-1),
675                        Pattern::flipsY(f,pattern.right+pattern.sizeX-1,pattern.bottom+pattern.sizeY-1,
676                        boardsize-1,boardsize-1)) - (newSizeY - 1);
677
678    // printf("%d, %d, %d, %d, %d, %d, %d\n", f, newSizeX, newSizeY, newLeft, newRight, newTop, newBottom);
679    char* newInitialPos = new char[pattern.sizeX*pattern.sizeY];
680    int i=0;
681    for(i=0; i<pattern.sizeX; i++) {
682      for(int j=0; j<pattern.sizeY; j++) {
683        newInitialPos[Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1) + \
684                      newSizeX*Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1)] = pattern.getInitial(i, j);
685      }
686    }
687
688    vector<MoveNC> newContList;
689    for(i=0; (unsigned int)i<pattern.contList.size(); i++) {
690      newContList.push_back(MoveNC(Pattern::flipsX(f, pattern.contList[i].x, pattern.contList[i].y, 
691                                                      pattern.sizeX-1,pattern.sizeY-1),
692                                  Pattern::flipsY(f, pattern.contList[i].x, pattern.contList[i].y,
693                                                      pattern.sizeX-1,pattern.sizeY-1),
694                                  pattern.contList[i].color));
695    }
696
697    Pattern pNew(newLeft, newRight, newTop, newBottom, pattern.boardsize, newSizeX, newSizeY,
698                 newInitialPos, newContList);
699
700    pNew.flip = f;
701    // printf("new size %d %d\n", pNew.sizeX, pNew.sizeY);
702
703    delete [] newInitialPos;
704
705    vector<Pattern>::iterator it;
706    bool foundNewPattern = true;
707    for(it = data.begin(); it != data.end(); it++) {
708      if (pNew == *it) {
709        foundNewPattern = false;
710        flipTable[f] = flipTable[it->flip];
711        break;
712      }
713    }
714    if (foundNewPattern) {
715      flipTable[f] = data.size();
716      data.push_back(pNew);
717    }
718
719    if (pNew == pattern) sy.push_back(pair<int,int>(f,0));
720
721    if (nextMove || !fixedColor) {
722      char* newInitialPos = new char[pattern.sizeX*pattern.sizeY];
723      for(int i=0; i<pattern.sizeX; i++) {
724        for(int j=0; j<pattern.sizeY; j++) {
725          newInitialPos[Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1) + newSizeX*Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1)] =
726            invertColor(pattern.getInitial(i, j));
727        }
728      }
729      vector<MoveNC> newContList;
730      {
731        for(unsigned int i=0; i<pattern.contList.size(); i++) {
732          newContList.push_back(MoveNC(Pattern::flipsX(f, pattern.contList[i].x, pattern.contList[i].y, 
733                  pattern.sizeX-1,pattern.sizeY-1),
734                Pattern::flipsY(f, pattern.contList[i].x, pattern.contList[i].y,
735                  pattern.sizeX-1,pattern.sizeY-1),
736                invertColor(pattern.contList[i].color)));
737        }
738      }
739
740
741      // printf("new size %d %d", newSizeX, newSizeY);
742      Pattern pNew1(newLeft, newRight, newTop, newBottom, pattern.boardsize, newSizeX, newSizeY,
743                    newInitialPos, newContList);
744      pNew1.flip = f;
745      pNew1.colorSwitch = 1;
746
747      delete [] newInitialPos;
748
749      if (!fixedColor) {
750        bool foundNewPattern = true;
751        int lCS_ctr = 0;
752        for(vector<Pattern>::iterator it = lCS.begin(); it != lCS.end(); it++) {
753          if (pNew1 == *it) {
754            foundNewPattern = false;
755            flipTable[f+8] = lCS_ctr;
756            break;
757          }
758          lCS_ctr++;
759        }
760        if (foundNewPattern) {
761          lCS.push_back(pNew1);
762        }
763      }
764
765      if (pNew1 == pattern) {
766        if (!fixedColor) sy.push_back(pair<int,int>(f,1));
767        if (nextMove) special = Pattern::PatternInvFlip(f);
768      }
769    }
770  }
771
772  int lCS_ctr = 0;
773  for(vector<Pattern>::iterator it = lCS.begin(); it != lCS.end(); it++) {
774    bool contained_in_l = false;
775    for(vector<Pattern>::iterator it_l = data.begin(); it_l != data.end(); it_l++)
776      if (*it == *it_l) {
777        contained_in_l = true;
778        flipTable[8+it->flip] = flipTable[it_l->flip];
779        break;
780      }
781    if (!contained_in_l) {
782      flipTable[8+it->flip] = data.size();
783      data.push_back(*it);
784    }
785    for(int ii=it->flip+1; ii<8; ii++) 
786      if (flipTable[8+ii] == lCS_ctr) flipTable[8+ii] = flipTable[8+it->flip];
787    lCS_ctr++;
788  }
789
790  Symmetries symm(pattern.sizeX, pattern.sizeY);
791  for(int i=0; i<symm.sizeX; i++)
792    for(int j=0; j<symm.sizeY; j++)
793      symm.set(i,j, i,j,0);
794
795  for(vector<pair<int,int> >::iterator it_s=sy.begin(); it_s!=sy.end(); it_s++) {
796    int s = it_s->first;
797    int newSizeX = max(Pattern::flipsX(s,0,0,pattern.sizeX,pattern.sizeY),
798                       Pattern::flipsX(s,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));
799    int newSizeY = max(Pattern::flipsY(s,0,0,pattern.sizeX,pattern.sizeY),
800                       Pattern::flipsY(s,pattern.sizeX,pattern.sizeY,pattern.sizeX,pattern.sizeY));
801    int c = it_s->second;
802    Symmetries symm1(newSizeX, newSizeY);
803
804    for(int i=0; i < pattern.sizeX; i++) {
805      for(int j=0; j < pattern.sizeY; j++) {
806        int fX = Pattern::flipsX(s, i, j, pattern.sizeX-1, pattern.sizeY-1);
807        int fY = Pattern::flipsY(s, i, j, pattern.sizeX-1, pattern.sizeY-1);
808        if ((i != fX || j != fY) && !symm1.has_key(fX, fY))
809          symm1.set(i,j, fX, fY, c);
810      }
811    }
812
813    {
814      int cs;
815      for(int i=0; i<symm.sizeX; i++)
816        for(int j=0; j<symm.sizeY; j++)
817          if (symm1.has_key(symm.getX(i,j), symm.getY(i,j))) {
818            if ((symm1.getCS(symm.getX(i,j),symm.getY(i,j)) || symm.getCS(i,j)) && 
819                !(symm1.getCS(symm.getX(i,j),symm.getY(i,j)) && symm.getCS(i,j)))
820              cs = 1;
821            else cs = 0;
822            symm.set(i,j,symm1.getX(symm.getX(i,j),symm.getY(i,j)), 
823                symm1.getY(symm.getX(i,j),symm.getY(i,j)), cs);
824          }
825    }
826  }
827
828  symmetries.push_back(symm);
829  {
830    vector<Pattern>::iterator it = data.begin();
831    it++;
832    for(; it != data.end(); it++) {
833      // printf("ne %d, %d\n", it->sizeX, it->sizeY);
834      int f = it->flip;
835      Symmetries s(it->sizeX, it->sizeY);
836      for(int i=0; i<pattern.sizeX; i++) {
837        for(int j=0; j<pattern.sizeY; j++) {
838          if (!it->colorSwitch) {
839            s.set(Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1), 
840                Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1), 
841                symm.getX(i,j), symm.getY(i,j), symm.getCS(i,j));
842          } else {
843            s.set(Pattern::flipsX(f,i,j,pattern.sizeX-1,pattern.sizeY-1), 
844                Pattern::flipsY(f,i,j,pattern.sizeX-1,pattern.sizeY-1), 
845                symm.getX(i,j), symm.getY(i,j), 1-symm.getCS(i,j));
846          }
847        }
848      }
849      symmetries.push_back(s);
850    }
851  }
852}
853
854
855Pattern PatternList::get(int i) {
856  return data[i];
857}
858
859
860int PatternList::size() {
861  return data.size();
862}
863
864
865char* PatternList::updateContinuations(int index, int x, int y, char co, bool tenuki, char winner) {
866  char xx;
867  char yy;
868  char cSymm;
869  char cc;
870  xx = symmetries[index].getX(x,y);
871  yy = symmetries[index].getY(x,y);
872  cSymm = symmetries[index].getCS(x,y);
873  if (co == 'X' || co == 'B') {
874    if (cSymm) cc = 'W'; else cc = 'B';
875  } else {
876    if (cSymm) cc = 'B'; else cc = 'W';
877  }
878
879  if ((nextMove == 1 && cc == 'W') || (nextMove == 2 && cc == 'B')) {
880    if (special != -1) {
881      char xx1 = xx;
882      // printf("s1 xx %d, yy %d sp %d\n", xx, yy, special);
883      xx = Pattern::flipsX(special, xx, yy, pattern.sizeX-1, pattern.sizeY-1);
884      yy = Pattern::flipsY(special, xx1, yy, pattern.sizeX-1, pattern.sizeY-1);
885      // printf("s2 xx %d, yy %d\n", xx, yy);
886      if (cc == 'B') cc = 'W';
887      else cc = 'B';
888      cSymm = 1-cSymm;
889    } else {
890      return 0;
891    }
892  }
893
894  if (cc == 'B') {
895    continuations[xx + pattern.sizeX*yy].B++;
896    if (tenuki) continuations[xx + pattern.sizeX*yy].tB++;
897    if ((winner == 'B' && !cSymm) || (winner == 'W' && cSymm)) continuations[xx + pattern.sizeX*yy].wB++;
898    else if ((winner == 'W' && !cSymm) || (winner == 'B' && cSymm)) continuations[xx + pattern.sizeX*yy].lB++;
899  } else {
900    // printf("xx %d, yy %d\n", xx, yy);
901    continuations[xx + pattern.sizeX*yy].W++;
902    if (tenuki) continuations[xx + pattern.sizeX*yy].tW++;
903    if ((winner == 'B' && !cSymm) || (winner == 'W' && cSymm)) continuations[xx + pattern.sizeX*yy].wW++;
904    else if ((winner == 'W' && !cSymm) || (winner ='B' && cSymm)) continuations[xx + pattern.sizeX*yy].lW++;
905  }
906  char* result = new char[3];
907  result[0] = xx;
908  result[1] = yy;
909  result[2] = cSymm;
910  return result;
911}
912
913
914char* PatternList::sortContinuations() {
915  char* labels = new char[pattern.sizeX*pattern.sizeY+1];
916  labels[pattern.sizeX * pattern.sizeY] = 0; // so we can just printf the labels as a string
917  for(int i=0; i<pattern.sizeX*pattern.sizeY; i++) {
918    if (continuations[i].B || continuations[i].W) labels[i] = '?'; // need to assign label
919    else labels[i] = '.';
920  }
921  string labelList = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
922  unsigned int labelIndex = 0;
923
924  // assign labels which are in the contLabels array passed to the original pattern
925  // (these will usually be labels "already present in the SGF file")
926 
927  if (pattern.contLabels) {
928    for(int i=0; i<pattern.sizeX*pattern.sizeY; i++) {
929      if (pattern.contLabels[i] != '.') {
930        labels[i] = pattern.contLabels[i];
931        unsigned int j = labelList.find(pattern.contLabels[i]);
932        if (j != string::npos) labelList.erase(j,1);
933      }
934    }
935  }
936
937  // now give labels to the remaining points, starting with the one with
938  // most hits
939 
940  int max_hits = 0;
941  int max_hits_index = 0;
942  while (max_hits != -1 && labelIndex < labelList.size()) {
943    for(int i=0; i<pattern.sizeX*pattern.sizeY; i++) {
944      if (labels[i] == '?' && continuations[i].B + continuations[i].W > max_hits) {
945        max_hits = continuations[i].B + continuations[i].W;
946        max_hits_index = i;
947      }
948    }
949    if (max_hits != 0) { // found another point needing a label
950      labels[max_hits_index] = labelList[labelIndex++];
951      max_hits = 0;
952    } else max_hits = -1; // done
953  }
954  return labels;
955}
956
957DBError::DBError() {
958}
959
960int dbinsert1blob(sqlite3* db, char* sql, int id, char* blob, int size) {
961  sqlite3_stmt *ppStmt=0;
962  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
963  if (rc != SQLITE_OK || ppStmt==0) return rc;
964  rc = sqlite3_bind_int(ppStmt, 1, id);
965  if (rc != SQLITE_OK) return rc;
966  rc = sqlite3_bind_blob(ppStmt, 2, blob, size, SQLITE_TRANSIENT);
967  if (rc != SQLITE_OK) return rc;
968  rc = sqlite3_step(ppStmt);
969  if (rc != SQLITE_DONE) return rc;
970  rc = sqlite3_finalize(ppStmt);
971  if (rc != SQLITE_OK) return rc;
972  return 0; // Success
973}
974
975int dbinsert2blobs(sqlite3* db, char* sql, int id, char* blob1, int size1, char* blob2, int size2) {
976  sqlite3_stmt *ppStmt=0;
977  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
978  if (rc != SQLITE_OK || ppStmt==0) return rc;
979  rc = sqlite3_bind_int(ppStmt, 1, id);
980  if (rc != SQLITE_OK) return rc;
981  rc = sqlite3_bind_blob(ppStmt, 2, blob1, size1, SQLITE_TRANSIENT);
982  if (rc != SQLITE_OK) return rc;
983  rc = sqlite3_bind_blob(ppStmt, 3, blob2, size2, SQLITE_TRANSIENT);
984  if (rc != SQLITE_OK) return rc;
985  rc = sqlite3_step(ppStmt);
986  if (rc != SQLITE_DONE) return rc;
987  rc = sqlite3_finalize(ppStmt);
988  if (rc != SQLITE_OK) return rc;
989  return 0; // Success
990}
991   
992Algorithm::Algorithm(int bsize) {
993  boardsize = bsize;
994  db = 0;
995}
996
997Algorithm::~Algorithm() {}
998
999void Algorithm::initialize_process(sqlite3* DB) {}
1000void Algorithm::newgame_process(int game_id) {}
1001void Algorithm::AB_process(int x, int y) {}
1002void Algorithm::AW_process(int x, int y) {}
1003void Algorithm::AE_process(int x, int y, char removed) {}
1004void Algorithm::endOfNode_process() {}
1005void Algorithm::move_process(Move m) {}
1006void Algorithm::pass_process() {}
1007void Algorithm::branchpoint_process() {}
1008void Algorithm::endOfVariation_process() {}
1009void Algorithm::endgame_process(bool commit) {}
1010void Algorithm::finalize_process() {}
1011int Algorithm::readDB(sqlite3* DB) { return 0; }
1012int Algorithm::search(PatternList& patternList, GameList& gl, SearchOptions& options) { 
1013  return -1; 
1014}
1015
1016Algo_signature::Algo_signature(int bsize) : Algorithm(bsize) {
1017  main_variation = true;
1018}
1019
1020Algo_signature::~Algo_signature() {
1021}
1022
1023void Algo_signature::initialize_process(sqlite3* DB) throw(DBError) {
1024  db = DB;
1025  char sql[100];
1026  sprintf(sql, "create table if not exists algo_signature_%d ( id integer primary key, signature varchar(12) );", boardsize);
1027  int rc = sqlite3_exec(db, sql, 0, 0, 0);
1028  if (rc != SQLITE_OK) throw DBError();
1029  sprintf(sql, "create index if not exists sig_idx on algo_signature_%d(signature);", boardsize);
1030  rc = sqlite3_exec(db, sql, 0, 0, 0);
1031  if (rc != SQLITE_OK) throw DBError();
1032}
1033
1034void Algo_signature::newgame_process(int game_id) {
1035  main_variation = true;
1036  counter = 0;
1037  gid = game_id;
1038  signature = new char[12];
1039  for(int i=0; i<12; i++) signature[i] = '?';
1040}
1041
1042void Algo_signature::AB_process(int x, int y) {
1043}
1044
1045void Algo_signature::AW_process(int x, int y) {
1046}
1047
1048void Algo_signature::AE_process(int x, int y, char removed) {
1049}
1050
1051void Algo_signature::endOfNode_process() {
1052}
1053
1054void Algo_signature::move_process(Move m) {
1055  if (!main_variation) return;
1056  counter++;
1057
1058  if (counter==20) {
1059    signature[0] = m.x + 97;
1060    signature[1] = m.y + 97;
1061  }
1062  if (counter==40) {
1063    signature[2] = m.x + 97;
1064    signature[3] = m.y + 97;
1065  }
1066  if (counter==60) {
1067    signature[4] = m.x + 97;
1068    signature[5] = m.y + 97;
1069  }
1070  if (counter==31) {
1071    signature[6] = m.x + 97;
1072    signature[7] = m.y + 97;
1073  }
1074  if (counter==51) {
1075    signature[8] = m.x + 97;
1076    signature[9] = m.y + 97;
1077  }
1078  if (counter==71) {
1079    signature[10] = m.x + 97;
1080    signature[11] = m.y + 97;
1081  }
1082}
1083
1084void Algo_signature::pass_process() {
1085  if (main_variation) move_process(Move(19,19,'p'));
1086}
1087
1088void Algo_signature::branchpoint_process() {
1089
1090}
1091
1092void Algo_signature::endOfVariation_process() {
1093  main_variation = false;
1094}
1095
1096char* symmetrize(char* signature, int boardsize) {
1097  // symmetrize signature
1098  char* min_signature = new char[12];
1099  for(int i=0; i<12; i++) min_signature[i] = signature[i];
1100  for (int f=0; f<8; f++) { // for all flips
1101    // compute flipped signature
1102    char* next = new char[12];
1103    for(int i=0; i<6; i++) {
1104      if ('a' <= signature[2*i] && signature[2*i] <= 's')
1105        next[2*i] = Pattern::flipsX(f, signature[2*i]-'a', signature[2*i+1]-'a', boardsize-1, boardsize-1)+'a';
1106      else next[2*i] = signature[2*i];
1107      if ('a' <= signature[2*i+1] && signature[2*i+1] <= 's')
1108        next[2*i+1] = Pattern::flipsY(f, signature[2*i]-'a', signature[2*i+1]-'a', boardsize-1, boardsize-1)+'a';
1109      else next[2*i+1] = signature[2*i+1];
1110    }
1111    // if next < min_signature, then swap
1112    for(int j=0; j<12; j++) {
1113      if (next[j] > min_signature[j]) break;
1114      if (next[j] < min_signature[j]) {
1115        char* help = next;
1116        next = min_signature;
1117        min_signature = help;
1118        break;
1119      }
1120    }
1121    delete [] next;
1122  }
1123  return min_signature;
1124}
1125
1126void Algo_signature::endgame_process(bool commit) throw(DBError) {
1127  if (commit) {
1128    char* min_signature = symmetrize(signature, boardsize);
1129    char sql[100];
1130    sprintf(sql, "insert into algo_signature_%d (id, signature) values (?,?);", boardsize);
1131    if (dbinsert1blob(db, sql, gid, min_signature, 12)) throw DBError();
1132    // for(int i=0; i<12; i++) printf("%c", min_signature[i]); printf("\n");
1133    delete [] min_signature;
1134  }
1135  delete [] signature;
1136}
1137
1138void Algo_signature::finalize_process() {
1139}
1140
1141char* Algo_signature::get_current_signature() {
1142  return symmetrize(signature, boardsize);
1143}
1144
1145vector<int> Algo_signature::search_signature(char* sig) {
1146  // to be used during processing! (because we need the db)
1147  char sql[100];
1148  sprintf(sql, "select id from algo_signature_%d where signature=? order by id", boardsize);
1149  sqlite3_stmt *ppStmt=0;
1150  vector<int> result;
1151  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
1152  if (rc != SQLITE_OK || ppStmt==0) throw DBError();
1153  rc = sqlite3_bind_blob(ppStmt, 1, sig, 12, SQLITE_TRANSIENT);
1154  if (rc != SQLITE_OK || ppStmt==0) throw DBError();
1155  do {
1156    rc = sqlite3_step(ppStmt);
1157    if (rc != SQLITE_DONE && rc != SQLITE_ROW) throw DBError();
1158    if (rc == SQLITE_ROW) {
1159      result.push_back(sqlite3_column_int(ppStmt, 0));
1160    }
1161  } while (rc == SQLITE_ROW);
1162  rc = sqlite3_finalize(ppStmt);
1163  if (rc != SQLITE_OK) throw DBError();
1164  return result;
1165}
1166
1167Algo_finalpos::Algo_finalpos(int bsize) : Algorithm(bsize) {
1168  fp = 0;
1169  fpIndex = -1;
1170  data = 0;
1171}
1172
1173Algo_finalpos::~Algo_finalpos() {
1174  if (data) {
1175    for(map<int, char* >::iterator it = data->begin(); it != data->end(); it++) delete [] it->second;
1176    delete data;
1177  }
1178}
1179
1180void Algo_finalpos::initialize_process(sqlite3* DB) throw(DBError) {
1181  // printf("init Algo_finalpos\n");
1182  db = DB;
1183  char sql[100];
1184  sprintf(sql, "create table if not exists algo_finalpos_%d ( id integer primary key, data blob );", boardsize);
1185  int rc = sqlite3_exec(db, sql, 0, 0, 0);
1186  if (rc != SQLITE_OK) {
1187    throw DBError();
1188  }
1189  // printf("init Algo_finalpos\n");
1190}
1191
1192void Algo_finalpos::newgame_process(int game_id) {
1193  gid = game_id;
1194  fp = new char[100];
1195  for(int i=0; i<100; i++) fp[i] = 255;
1196}
1197
1198void Algo_finalpos::AB_process(int x, int y) {
1199  fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))));
1200}
1201
1202void Algo_finalpos::AW_process(int x, int y) {
1203  fp[y/2 + 10*(x/2)] &= ~(1 << (2*(x%2 + 2*(y%2))+1));
1204}
1205
1206void Algo_finalpos::AE_process(int x, int y, char removed) {
1207}
1208
1209void Algo_finalpos::endOfNode_process() {
1210}
1211
1212void Algo_finalpos::move_process(Move m) {
1213  if (m.color == 'B')
1214    fp[m.y/2 + 10*(m.x/2)] &= ~(1 << (2*(m.x%2 + 2*(m.y%2))));
1215  else if (m.color == 'W')
1216    fp[m.y/2 + 10*(m.x/2)] &= ~(1 << (2*(m.x%2 + 2*(m.y%2))+1));
1217}
1218
1219void Algo_finalpos::pass_process() {
1220}
1221
1222void Algo_finalpos::branchpoint_process() {
1223}
1224
1225void Algo_finalpos::endOfVariation_process() {
1226}
1227
1228void Algo_finalpos::endgame_process(bool commit) throw(DBError) {
1229  if (commit) {
1230    char sql[100];
1231    sprintf(sql, "insert into algo_finalpos_%d (id, data) values (?,?);", boardsize);
1232    if (dbinsert1blob(db, sql, gid, fp, 100)) throw DBError();
1233  }
1234  delete [] fp;
1235}
1236
1237void Algo_finalpos::finalize_process() {
1238}
1239
1240int Algo_finalpos::readDB(sqlite3* DB) { 
1241  db = DB;
1242  if (data) {
1243    for(map<int, char* >::iterator it = data->begin(); it != data->end(); it++) delete [] it->second;
1244    delete data;
1245  }
1246  data = new map<int, char* >;
1247  int rc = sqlite3_exec(db, "begin transaction;", 0, 0, 0);
1248  if (rc) throw DBError();
1249  sqlite3_stmt *ppStmt=0;
1250  char sql[100];
1251  sprintf(sql, "select id, data from algo_finalpos_%d order by id", boardsize);
1252  rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
1253  if (rc != SQLITE_OK || ppStmt==0) return rc; // FIXME: catch certain errors, (and/or throw DBError?)
1254  while (sqlite3_step(ppStmt) == SQLITE_ROW) {
1255    // printf("step0\n");
1256    int index = sqlite3_column_int(ppStmt, 0);
1257    char* d = (char*)sqlite3_column_blob(ppStmt, 1);
1258    // printf("step1\n");
1259    char* d1 = new char[100];
1260    // printf("step2\n");
1261    for(int i=0; i<100; i++) d1[i] = d[i];
1262    // printf("step3\n");
1263    // printf("insert %d %p\n", index, d1);
1264    data->insert(make_pair(index, d1));
1265  }
1266  // printf("done\n");
1267  rc = sqlite3_finalize(ppStmt);
1268  if (rc != SQLITE_OK) return rc;
1269  rc = sqlite3_exec(db, "commit;", 0, 0, 0);
1270  if (rc != SQLITE_OK) throw DBError();
1271  return 0;
1272}
1273
1274int Algo_finalpos::search(PatternList& patternList, GameList& gl, SearchOptions& options) { // progress bar?!
1275
1276  // Put the pattern into bitmap format, which is the format the final
1277  // positions are stored in in the database. This makes the comparisons
1278  // faster.
1279
1280  int plS = patternList.size();
1281  char_p** allbits = new char_p*[plS];
1282  int** allbitlengths = new int*[plS];
1283  for(int N=0; N<plS; N++) {
1284    Pattern* pattern = &patternList.data[N];
1285    allbits[N] = new char_p[4];
1286    allbitlengths[N] = new int[4];
1287
1288    for(int i=0; i<2; i++) {
1289      for(int j=0; j<2; j++) {
1290        int xBlocks = (pattern->sizeY+i+1)/2;
1291        int yBlocks = (pattern->sizeX+j+1)/2;
1292        char* nextBlock = new char[400];
1293        int nextBlockIndex = 0;
1294        nextBlock[nextBlockIndex++] = yBlocks;
1295
1296        for(int k1=0; k1 < yBlocks; k1++) {
1297          char nlist[400];
1298          int nlistIndex = 0;
1299
1300          for(int k2=0; k2 < xBlocks; k2++) {
1301            int n = 0;
1302            for(int x=0; x<2; x++) {
1303              for(int y=0; y<2; y++) {
1304                int indexX = k1 * 2 + y - j;
1305                int indexY = k2 * 2 + x - i;
1306                if (0 <= indexX && indexX < pattern->sizeX && 0 <= indexY && indexY < pattern->sizeY) {
1307                  if (pattern->getFinal(indexX,indexY)=='X')
1308                    n |= 1 << (2*(2*x+y));
1309                  else if (pattern->getFinal(indexX,indexY)=='O')
1310                    n |= 1 << (2*(2*x+y)+1);
1311                }
1312              }
1313            }
1314            nlist[nlistIndex++] = n;
1315          }             
1316
1317          int start = 0;
1318          int end = nlistIndex;
1319
1320          while (start < end && !nlist[start]) start++;
1321          while (end > start && !nlist[end-1]) end--;
1322
1323          nextBlock[nextBlockIndex++] = start;
1324          nextBlock[nextBlockIndex++] = end-start;
1325          for(int current=start; current < end; current++) 
1326            nextBlock[nextBlockIndex++] = nlist[current];
1327        }
1328        char* nB = new char[nextBlockIndex];
1329        for(int ii=0; ii<nextBlockIndex; ii++) nB[ii] = nextBlock[ii];
1330        allbitlengths[N][2*i + j] = nextBlockIndex;
1331        allbits[N][2*i + j] = nB;
1332        delete [] nextBlock;
1333      }
1334    }
1335  }
1336
1337  int index = gl.start();
1338  // int counter = 0; // to keep track of progress bar
1339  // printf("%d patterns\n", plS);
1340  char start;
1341  char length;
1342  char x;
1343  char y;
1344  while (index != -1) {   
1345    // if (!(counter++ % 1000)) printf("counter: %d, index: %d\n", counter, index);
1346    // if (progBar && !(counter % 100))
1347    //   progBar.redraw((progEnd-progStart)*counter/len(gl.current) + progStart);
1348
1349    map<int, char* >::iterator it = data->find(index);
1350    if (it == data->end()) {
1351      // printf("skip\n");
1352      index = gl.next();
1353      continue;
1354    }
1355    char* finalpos = it->second;
1356    // printf("index %d, %p\n", index, finalpos);
1357    vector<Candidate* > *matchList = new vector<Candidate* >;;
1358
1359    for(int N=0; N<plS; N++) {
1360      Pattern* pattern = &patternList.data[N];
1361      for(int a0=pattern->left; a0 <= pattern->right; a0++) {
1362        for(int a1 = pattern->top; a1 <= pattern->bottom; a1++) {
1363          int matches = 1;
1364
1365          int pIndex = 2*(a1%2) + (a0%2);
1366          char* pbits = allbits[N][pIndex];
1367          int pbIndex = 0;
1368          int fpIndex = a1/2 + (a0/2)*10;
1369
1370          for(x=0; x < pbits[0]; x++) {
1371            start = pbits[++pbIndex];
1372            length = pbits[++pbIndex];
1373            fpIndex += start;
1374            for(y=0; y<length; y++) {
1375              pbIndex++;
1376              if (pbits[pbIndex] & finalpos[fpIndex]) {
1377                matches = 0;
1378                break;
1379              }
1380              fpIndex++;
1381            }
1382            if (!matches) break;
1383            fpIndex += 10 - start - length;
1384          }               
1385          if (matches) matchList->push_back(new Candidate(a0,a1,N));
1386        }
1387      }
1388    }
1389
1390    if (matchList->size()) gl.makeCurrentCandidate(matchList);
1391    else delete matchList;
1392
1393    index = gl.next();
1394  }
1395  {
1396    for(int N=0; N<plS; N++) {
1397      delete [] allbitlengths[N];
1398      for(int i=0; i<4; i++)
1399        if (allbits[N][i]) delete [] allbits[N][i];
1400      delete [] allbits[N];
1401    }
1402  }
1403  delete [] allbitlengths;
1404  delete [] allbits;
1405  return 0;
1406}
1407
1408bool Algo_finalpos::equal(unsigned int i1, unsigned int i2) { 
1409  // not to be used during processing
1410  // i1, i2 correspond to game id's
1411  sqlite3_stmt *ppStmt=0;
1412  char sql[100];
1413  sprintf(sql, "select data from algo_finalpos_%d where id = %d or id = %d", boardsize, i1, i2);
1414  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
1415  if (rc != SQLITE_OK || ppStmt==0) return false; // FIXME: catch certain errors, (and/or throw DBError?)
1416  if (sqlite3_step(ppStmt) == SQLITE_ROW) {
1417    char* dd1 = (char*)sqlite3_column_blob(ppStmt, 0);
1418    char* d1 = new char[100];
1419    for(int i=0; i<100; i++) d1[i] = dd1[i]; // FIXME: is this necessary?
1420    if (sqlite3_step(ppStmt) == SQLITE_ROW) {
1421      char* d2 = (char*)sqlite3_column_blob(ppStmt, 0);
1422      for(int i=0; i<100; i++) 
1423        if (d1[i] != d2[i]) {
1424          delete [] d1;
1425          sqlite3_finalize(ppStmt);
1426          return false;
1427        }
1428      delete [] d1;
1429      sqlite3_finalize(ppStmt);
1430      return true;
1431    }
1432    delete [] d1;
1433  }
1434  sqlite3_finalize(ppStmt);
1435  return false;
1436}
1437
1438bool Algo_finalpos::equals_current(unsigned int id1) { 
1439  // to be used only during processing
1440  // id1 here corresponds to a game id
1441  bool result = true;
1442  sqlite3_stmt *ppStmt=0;
1443  char sql[100];
1444  sprintf(sql, "select data from algo_finalpos_%d where id = %d", boardsize, id1);
1445  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
1446  if (rc != SQLITE_OK || ppStmt==0) return false; // FIXME: catch certain errors, (and/or throw DBError?)
1447  if (sqlite3_step(ppStmt) == SQLITE_ROW) {
1448    char* d = (char*)sqlite3_column_blob(ppStmt, 0);
1449    for(int i=0; i<100; i++) 
1450      if (d[i] != fp[i]) {
1451        result = false;
1452        break;
1453      }
1454  } else result = false;
1455  sqlite3_finalize(ppStmt);
1456  return result;
1457}
1458
1459
1460Algo_movelist::Algo_movelist(int bsize) : Algorithm(bsize) {
1461  data1 = 0;
1462  data2 = 0;
1463  data1l = 0;
1464}
1465
1466Algo_movelist::~Algo_movelist() {
1467  if (data1) {
1468    for(map<int, char* >::iterator it = data1->begin(); it != data1->end(); it++) {
1469      delete [] it->second;
1470    }
1471    delete data1;
1472  }
1473  if (data2) {
1474    for(map<int, char* >::iterator it = data2->begin(); it != data2->end(); it++) {
1475      delete [] it->second;
1476    }
1477    delete data2;
1478  }
1479  if (data1l) delete data1l;
1480}
1481
1482void Algo_movelist::initialize_process(sqlite3* DB) throw(DBError) {
1483  // printf("init Algo_movelist\n");
1484  db = DB;
1485  char sql[100];
1486  sprintf(sql, "create table if not exists algo_movelist_%d ( id integer primary key, movelist blob, fpC blob );", boardsize);
1487  int rc = sqlite3_exec(db, sql, 0, 0, 0);
1488  if (rc != SQLITE_OK) throw DBError();
1489  // printf("init Algo_movelist\n");
1490}
1491
1492void Algo_movelist::newgame_process(int game_id) {
1493  gid = game_id;
1494  movelist = vector<char>();
1495
1496  fpC = new char[50];
1497  for(int i=0; i<50; i++) fpC[i] = 0;
1498}
1499
1500void Algo_movelist::AB_process(int x, int y) {
1501  movelist.push_back((char)x);
1502  movelist.push_back((char)(y | BLACK));
1503}
1504       
1505
1506void Algo_movelist::AW_process(int x, int y) {
1507  movelist.push_back((char)x);
1508  movelist.push_back((char)(y | WHITE));
1509}
1510
1511
1512void Algo_movelist::AE_process(int x, int y, char removed) {
1513  movelist.push_back((char)x);
1514  if (removed == 'B') movelist.push_back((char)(y | REMOVE | BLACK));
1515  else if (removed == 'W') movelist.push_back((char)(y | REMOVE | WHITE));
1516}
1517
1518void Algo_movelist::endOfNode_process() {
1519  if (movelist.size()>1) {
1520    if (movelist[movelist.size()-2] & (ENDOFNODE | BRANCHPOINT | ENDOFVARIATION)) {
1521      movelist.push_back(ENDOFNODE);
1522      movelist.push_back(0);
1523    } else {
1524      movelist[movelist.size()-2] |= ENDOFNODE;
1525    }
1526  } else {
1527    movelist.push_back(ENDOFNODE);
1528    movelist.push_back(0);
1529  }
1530}
1531
1532void Algo_movelist::move_process(Move m) {
1533  if (!movelist.size()) {
1534    movelist.push_back(ENDOFNODE);
1535    movelist.push_back(0);
1536  }
1537  movelist.push_back(m.x);
1538  if (m.color=='B') movelist.push_back(m.y | BLACK);
1539  else movelist.push_back(m.y | WHITE);
1540
1541  if (m.captures) {
1542    vector<p_cc>::iterator it;
1543    for(it = m.captures->begin(); it != m.captures->end(); it++) {
1544      int xx = it->first;
1545      int yy = it->second;
1546
1547      movelist.push_back(xx);
1548      if (m.color=='B') movelist.push_back(yy | REMOVE | WHITE);
1549      else movelist.push_back(yy | REMOVE | BLACK);
1550      fpC[yy/4 + 5*(xx/2)] |= 1 << (xx%2 + 2*(yy%4));
1551    }
1552  }
1553}
1554
1555void Algo_movelist::pass_process() {
1556  movelist.push_back(19);
1557  movelist.push_back(19);
1558}
1559
1560void Algo_movelist::branchpoint_process() {
1561  movelist.push_back(BRANCHPOINT);
1562  movelist.push_back(0);
1563}
1564
1565void Algo_movelist::endOfVariation_process() {
1566  movelist.push_back(ENDOFVARIATION);
1567  movelist.push_back(0);
1568}
1569
1570void Algo_movelist::endgame_process(bool commit) throw(DBError) {
1571  if (commit) {
1572    char* ml = new char[movelist.size()];
1573    int mlIndex = 0;
1574    for(vector<char>::iterator it = movelist.begin(); it != movelist.end(); it++) {
1575      ml[mlIndex++] = *it;
1576    }
1577    char sql[100];
1578    sprintf(sql, "insert into algo_movelist_%d (id, movelist, fpC) values (?, ?, ?);", boardsize);
1579    if (dbinsert2blobs(db, sql, gid, ml, mlIndex, fpC, 50)) throw DBError();
1580    delete [] ml;
1581  }
1582  delete [] fpC;
1583}
1584
1585void Algo_movelist::finalize_process() {
1586}
1587
1588int Algo_movelist::readDB(sqlite3* DB) {
1589  if (data1) {
1590    for(map<int, char* >::iterator it = data1->begin(); it != data1->end(); it++) delete [] it->second;
1591    delete data1;
1592  }
1593  data1 = new map<int, char* >;
1594  if (data1l) delete data1l;
1595  data1l = new map<int, int >;
1596  if (data2) {
1597    for(map<int, char* >::iterator it = data2->begin(); it != data2->end(); it++) delete [] it->second;
1598    delete data2;
1599  }
1600  data2 = new map<int, char* >;
1601  db = DB;
1602
1603  int rc = sqlite3_exec(db, "begin transaction;", 0, 0, 0);
1604  if (rc) throw DBError();
1605
1606  sqlite3_stmt *ppStmt=0;
1607  char sql[100];
1608  sprintf(sql, "select movelist,fpC,id from algo_movelist_%d order by id", boardsize);
1609  rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
1610  if (rc != SQLITE_OK || ppStmt==0) return rc; // FIXME: catch certain errors, (and/or throw DBError?)
1611  while (sqlite3_step(ppStmt) == SQLITE_ROW) {
1612    int l = sqlite3_column_bytes(ppStmt,0);
1613    // printf("len movelist: %d\n", l);
1614    char* d = (char*)sqlite3_column_blob(ppStmt, 0);
1615    char* d1 = new char[l];
1616    for(int i=0; i<l; i++) {
1617      d1[i] = d[i];
1618      // printf("%c", (d[i] & 31)+97);
1619    }
1620    int index = sqlite3_column_int(ppStmt, 2);
1621    // printf("\n");
1622    data1->insert(make_pair(index, d1));
1623    data1l->insert(make_pair(index, l));
1624    d = (char*)sqlite3_column_blob(ppStmt, 1);
1625    d1 = new char[50];
1626    {
1627      for(int i=0; i<50; i++) d1[i] = d[i];
1628    }
1629    data2->insert(make_pair(index, d1));
1630  }
1631  rc = sqlite3_finalize(ppStmt);
1632  if (rc != SQLITE_OK) return rc;
1633
1634  rc = sqlite3_exec(db, "commit;", 0, 0, 0);
1635  if (rc != SQLITE_OK) throw DBError();
1636  // printf("data sizes %d, %d, %d\n", data1->size(), data1l->size(), data2->size());
1637  return 0;
1638}
1639
1640
1641MovelistCand::MovelistCand(Pattern* P, int ORIENTATION, char* DICTS, int NO, char X, char Y) {
1642  orientation = ORIENTATION;
1643  p = P;
1644  mx = X;
1645  my = Y;
1646  Xinterv = make_pair(mx, mx+p->sizeX);
1647  Yinterv = make_pair(my, my+p->sizeY);
1648
1649  dicts = DICTS;
1650  dictsNO = NO;
1651  contListIndex = 0;
1652  dictsFound = false;
1653  dictsFoundInitial = false;
1654  dictsDR = false;
1655  contList = p->contList; // FIXME
1656}
1657
1658MovelistCand::~MovelistCand() {
1659  delete [] dicts;
1660}
1661
1662char MovelistCand::dictsget(char x, char y) {
1663  return dicts[x-mx + p->sizeX*(y-my)];
1664}
1665
1666void MovelistCand::dictsset(char x, char y, char d) {
1667  dicts[x-mx + p->sizeX*(y-my)] = d;
1668}
1669
1670bool MovelistCand::in_relevant_region(char x, char y) {
1671  return (mx <= x && x < mx + p->sizeX && my <= y && y < my + p->sizeY);
1672}
1673
1674
1675VecMC::VecMC() : vector<MovelistCand* >() {
1676  candssize = 0;
1677}
1678
1679VecMC::~VecMC() {
1680  for(VecMC::iterator it = begin(); it != end(); it++) {
1681    if (*it) delete *it;
1682  }
1683}
1684
1685VecMC* VecMC::deepcopy(ExtendedMoveNumber& COUNTER, int CANDSSIZE) {
1686  VecMC* result = new VecMC;
1687  result->candssize = CANDSSIZE;
1688  result->counter = COUNTER;
1689  for(VecMC::iterator it = begin(); it != end(); it++) {
1690    MovelistCand* mlc = 0;
1691    if (*it) {
1692      char* DICTS = new char[(*it)->p->sizeX * (*it)->p->sizeY];
1693      for (int i=0; i < (*it)->p->sizeX * (*it)->p->sizeY; i++) DICTS[i] = (*it)->dicts[i];
1694      mlc = new MovelistCand((*it)->p, (*it)->orientation, DICTS, (*it)->dictsNO, (*it)->mx, (*it)->my);
1695      mlc->contListIndex = (*it)->contListIndex;
1696      mlc->dictsFound = (*it)->dictsFound;
1697      mlc->dictsF = (*it)->dictsF;
1698      mlc->dictsFoundInitial = (*it)->dictsFoundInitial;
1699      mlc->dictsFI = (*it)->dictsFI;
1700      mlc->dictsDR = (*it)->dictsDR;
1701      mlc->contList = mlc->p->contList; // FIXME
1702    }
1703    result->push_back(mlc);
1704  }
1705  return result;
1706}
1707
1708int Algo_movelist::search(PatternList& patternList, GameList& gl, SearchOptions& options) { 
1709  // FIXME progbar
1710
1711  // printf("Enter Algo_movelist::search\n");
1712  int numOfHits = 0;
1713  int self_numOfSwitched = 0;
1714  int Bwins = 0;
1715  int Wwins = 0;
1716
1717  int movelimit = options.moveLimit;
1718
1719  int index = gl.start();
1720  // int gameCounter = 0;
1721
1722  while (index != -1) {
1723
1724    // gameCounter++;
1725    // if (progBar && !(gameCounter % 10))
1726    //   progBar.redraw((progEnd-progStart)*gameCounter/len(db.current) + progStart);
1727   
1728    // printf("Process index %d\n", index);
1729
1730    vector<Hit* > * result = new vector<Hit* >;
1731    int numOfSwitched = 0;
1732    stack<VecMC* > branchpoints;
1733
1734    char* movel = (*data1)[index];
1735    int movelistIndex = 0;
1736    int endMovelist = (*data1l)[index];
1737    // printf("len movelist: %d\n", (*data1l)[index]);
1738    // int nodeCtr = 0;
1739    // for(int i=0; i<endMovelist/2; i++) {
1740      // printf(" - ");
1741      // if (movel[2*i] & BRANCHPOINT) printf("BP\n");
1742      // if (movel[2*i] & ENDOFVARIATION) printf("EV\n");
1743      // if (movel[2*i+1] & BLACK) printf("B");
1744      // if (movel[2*i+1] & WHITE) printf("W");
1745      // if (movel[2*i+1] & REMOVE) printf("C");
1746      // printf("%c", (movel[2*i] & 31)+97);
1747      // printf("%c", (movel[2*i+1] & 31)+97);
1748      // if (movel[2*i] & ENDOFNODE) printf("\n%d ", nodeCtr++);
1749    // }
1750    // printf("\n");
1751
1752    char* fpC = (*data2)[index];
1753
1754    vector<Candidate* > *currentMatchList = gl.getCurrentCandidateList();
1755    int candssize = currentMatchList->size();
1756    VecMC* cands = new VecMC;
1757    cands->reserve(currentMatchList->size());
1758
1759    for(int mCounter=0; mCounter<(int)currentMatchList->size(); mCounter++) {
1760      Candidate* m = (*currentMatchList)[mCounter];
1761      int dNO = 0;
1762      Pattern* p = &patternList.data[m->orientation];
1763      char* d = new char[p->sizeX * p->sizeY];
1764      for(int i=0; i<p->sizeX; i++) {
1765        for(int j=0; j<p->sizeY; j++) {
1766          char p_ij = p->getInitial(i,j);
1767          if (p_ij != '.') d[i+p->sizeX*j] = p_ij;
1768          else d[i+p->sizeX*j] = 0;
1769          if (p_ij == 'X' || p_ij == 'O') dNO++;
1770        }
1771      }
1772      cands->push_back(new MovelistCand(p, m->orientation, d, dNO, m->x, m->y));
1773    }
1774    // printf("candssize %d\n", cands->size());
1775
1776    ExtendedMoveNumber counter(0);
1777
1778    while (movelistIndex < endMovelist) {
1779      // printf("\nnextmove %d\n", counter.total_move_num());
1780      if (counter.total_move_num() == movelimit+1) {
1781        for(vector<MovelistCand* >::iterator it = cands->begin(); it != cands->end(); it++) {
1782          if (*it == 0) continue;
1783          if (!(*it)->dictsFound) {
1784            delete *it;
1785            *it = 0;
1786            candssize--;
1787          }
1788        }
1789      }
1790      if (options.searchInVariations && movel[movelistIndex] & BRANCHPOINT) {
1791        // printf("branchpoint\n");
1792        branchpoints.push(cands->deepcopy(counter, candssize));
1793        movelistIndex += 2;
1794        continue;
1795      } 
1796      if (options.searchInVariations && movel[movelistIndex] & ENDOFVARIATION) {
1797        // printf("endofvariation\n");
1798        if (!patternList.nextMove) { // deal with hits w/o continuation
1799          for(vector<MovelistCand* >::iterator it = cands->begin(); it != cands->end(); it++) {
1800            if (*it == 0) continue;
1801            if ((*it)->dictsFound) {
1802              if ((*it)->p->colorSwitch) {
1803                numOfSwitched++;
1804                char* rstr = new char[3];
1805                rstr[0] = NO_CONT;
1806                rstr[1] = 0;
1807                rstr[2] = 1;
1808                result->push_back(new Hit(new ExtendedMoveNumber((*it)->dictsF), rstr));
1809              } else {
1810                char* rstr = new char[3];
1811                rstr[0] = NO_CONT;
1812                rstr[1] = 0;
1813                rstr[2] = 0;
1814                result->push_back(new Hit(new ExtendedMoveNumber((*it)->dictsF), rstr));
1815              }
1816            }
1817          }
1818        }
1819
1820        delete cands;
1821        cands = branchpoints.top();
1822        counter = cands->counter;
1823        candssize = cands->candssize;
1824        counter.down();
1825        branchpoints.pop();
1826        movelistIndex += 2;
1827        continue;
1828      }
1829
1830      char x = movel[movelistIndex] & 31;
1831      char y = movel[movelistIndex+1] & 31;
1832
1833      char co = 'O';
1834      char invco = 'X';
1835      char lower_invco = 'x';
1836
1837      if (!(movel[movelistIndex+1] & REMOVE) && (movel[movelistIndex+1] & (BLACK | WHITE))) {
1838        // printf("mv\n");
1839        if (movel[movelistIndex+1] & BLACK) {
1840          co = 'X';
1841          invco = 'O';
1842          lower_invco = 'o';
1843        }
1844
1845        for(vector<MovelistCand* >::iterator it = cands->begin(); it != cands->end(); it++) {
1846          if (*it == 0) continue;
1847          if ((*it)->in_relevant_region(x,y)) {
1848            // printf("loop 1\n %c", (*it)->dictsget(x,y));
1849            if ((*it)->dictsFound) { // found, so now we have found the continuation
1850              // printf("found\n");
1851              char* label;
1852              label = patternList.updateContinuations(
1853                  (*it)->orientation, // pattern in question
1854                  x-(*it)->mx, y-(*it)->my, // pos of continuation
1855                  co, // color of continuation
1856                  (counter.total_move_num()-(*it)->dictsF.total_move_num())>2, // tenuki?
1857                  gl.getCurrentWinner()
1858                  );
1859              if (label) { // otherwise no hit because continuation has wrong color (i.e. nextMove set)
1860                numOfSwitched += label[2];
1861                result->push_back(new Hit(new ExtendedMoveNumber((*it)->dictsF), label));
1862              }
1863
1864              delete *it;
1865              *it = 0;
1866              candssize--;
1867              continue;
1868            } else if ((*it)->dictsFoundInitial) { // foundInitial, so now look for contList
1869              if (MoveNC(x, y, co) == ((*it)->contList)[(*it)->contListIndex]) {
1870                (*it)->contListIndex++;
1871                if ((*it)->contListIndex == (int)(*it)->contList.size()) {
1872                  (*it)->dictsF = counter;
1873                  (*it)->dictsFound = true;
1874                }
1875              } else {
1876                if ((*it)->dictsDR) { // don't restore
1877                  delete *it;
1878                  *it = 0;
1879                  candssize--;
1880                  continue;
1881                } else {
1882                  (*it)->contListIndex = 0;
1883                  (*it)->dictsFoundInitial = false;
1884                }
1885              }
1886            }
1887
1888            if (!(*it)->dictsget(x,y)) { // this move occupies a spot which should be empty
1889              if (!(fpC[y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {
1890                if (!(*it)->contListIndex) {
1891                  delete *it;
1892                  *it = 0;
1893                  candssize--;
1894                  continue;
1895                } else (*it)->dictsDR = true;
1896              } else {
1897                (*it)->dictsset(x,y,'.');
1898                (*it)->dictsNO++; // printf("++ A\n");
1899              }
1900            } else if ((*it)->dictsget(x,y) == lower_invco) {
1901              // this move occupies a wildcard spot of the wrong color
1902              if (!(fpC[y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {
1903                if (!(*it)->contListIndex) {
1904                  delete *it;
1905                  *it = 0;
1906                  candssize--;
1907                  continue;
1908                } else (*it)->dictsDR = true;
1909              } else (*it)->dictsNO++; // printf("++ B\n");
1910            } else if ((*it)->dictsget(x,y) == co) {
1911              // this move gives us the stone we are looking for
1912              (*it)->dictsset(x,y,0);
1913              (*it)->dictsNO--; // printf("-- A\n");
1914            }
1915          }
1916        }
1917      }
1918      else if (movel[movelistIndex+1] & REMOVE) {
1919        if (movel[movelistIndex+1] & BLACK) {
1920          co = 'X';
1921          invco = 'O';
1922          lower_invco = 'o';
1923        } else if (movel[movelistIndex+1] & WHITE) {
1924          co = 'O';
1925          invco = 'X';
1926          lower_invco = 'x';
1927        }
1928
1929        for(vector<MovelistCand* >::iterator it = cands->begin(); it != cands->end(); it++) {
1930          // printf("loop 2\n");
1931          if (*it == 0) continue;
1932          if (!(*it)->dictsFound) { // not found yet
1933            if ((*it)->in_relevant_region(x,y)) {
1934              if ((*it)->dictsFoundInitial) { // foundInitial
1935                int ii = (*it)->contListIndex;
1936                while (ii < (int)(*it)->contList.size() && (*it)->contList[ii].color == '-' &&
1937                    (x != (*it)->contList[ii].x || y != (*it)->contList[ii].y))
1938                  ii++;
1939                if (ii < (int)(*it)->contList.size() && (*it)->contList[ii].color == '-') {
1940                  MoveNC help = (*it)->contList[ii];
1941                  (*it)->contList[ii] = (*it)->contList[(*it)->contListIndex];
1942                  (*it)->contList[(*it)->contListIndex] = help;
1943
1944                  (*it)->contListIndex++;
1945                } else {
1946                  if ((*it)->dictsDR) {
1947                    delete *it;
1948                    *it = 0;
1949                    candssize--;
1950                    continue;
1951                  } else {
1952                    (*it)->contListIndex = 0;
1953                    (*it)->dictsFoundInitial = false; 
1954                  }
1955                }
1956              }
1957              if (!(*it)->dictsget(x,y)) { 
1958                // the stone at this position was what we needed,
1959                // since it was captured, we are once again looking for it:
1960                (*it)->dictsset(x,y,co);
1961                (*it)->dictsNO++; // printf("++ C\n");
1962              }
1963              else if ((*it)->dictsget(x,y) == lower_invco) { 
1964                (*it)->dictsNO--; // printf("-- B\n");
1965              }
1966              else if ((*it)->dictsget(x,y) == '.') {
1967                // we are looking for an empty spot here, so this capture is helpful:
1968                (*it)->dictsset(x,y,0);
1969                (*it)->dictsNO--; // printf("-- C\n");
1970              }
1971            }
1972          }
1973        }
1974      }
1975
1976      if (movel[movelistIndex] & ENDOFNODE) {
1977        vector<MovelistCand* >::iterator candsend = cands->end();
1978        for(vector<MovelistCand* >::iterator it = cands->begin(); it != candsend; it++) {
1979          if (*it == 0) continue;
1980          if (!(*it)->dictsNO && !(*it)->dictsFound) {
1981            if (!(*it)->contList.size()) {
1982              (*it)->dictsF = counter;
1983              (*it)->dictsFound = true;
1984            } else if (!(*it)->dictsFoundInitial) {
1985              (*it)->dictsFI = counter;
1986              (*it)->dictsFoundInitial = true;
1987            } else if (!(*it)->dictsDR) { // found initial position again during processing of contList
1988              char* d = new char[(*it)->p->sizeX*(*it)->p->sizeY];
1989              for (int ct=0; ct < (*it)->p->sizeX*(*it)->p->sizeY; ct++) d[ct] = (*it)->dicts[ct];
1990              MovelistCand* mlc = new MovelistCand((*it)->p, (*it)->orientation, d, 0, (*it)->mx, (*it)->my);
1991              mlc->dictsFI = counter;
1992              cands->push_back(mlc);
1993              candssize++;
1994            }
1995          }
1996        }
1997        counter.next();
1998      }
1999
2000      if (candssize==0 && branchpoints.size()==0) break;
2001      movelistIndex += 2;
2002    }
2003
2004    // printf("assemble results\n");
2005
2006    if (!patternList.nextMove) { // look at matches w/o continuation
2007      for(vector<MovelistCand* >::iterator it = cands->begin(); it != cands->end(); it++) {
2008        if (*it == 0) continue;
2009        if ((*it)->dictsFound) {
2010          if ((*it)->p->colorSwitch) {
2011            numOfSwitched++;
2012            char* rstr = new char[3];
2013            rstr[0] = NO_CONT;
2014            rstr[1] = 0;
2015            rstr[2] = 1;
2016            result->push_back(new Hit(new ExtendedMoveNumber((*it)->dictsF), rstr)); // FIXME what w/ variations?
2017          } else {
2018            char* rstr = new char[3];
2019            rstr[0] = NO_CONT;
2020            rstr[1] = 0;
2021            rstr[2] = 0;
2022            result->push_back(new Hit(new ExtendedMoveNumber((*it)->dictsF), rstr));
2023          }
2024        }
2025      }
2026    }
2027
2028    if (result->size()) {
2029      numOfHits += result->size();
2030      self_numOfSwitched += numOfSwitched;
2031
2032      if (gl.getCurrentWinner() == 'B') {
2033        Bwins += result->size() - numOfSwitched;
2034        Wwins += numOfSwitched;
2035      } else if (gl.getCurrentWinner() == 'W') {
2036        Bwins += numOfSwitched;
2037        Wwins += result->size() - numOfSwitched;
2038      }
2039      gl.makeCurrentHit(result);
2040    } else delete result;
2041    index = gl.next();
2042    delete cands;
2043  }
2044  gl.num_hits = numOfHits;
2045  gl.num_switched = self_numOfSwitched;
2046  gl.Bwins = Bwins;
2047  gl.Wwins = Wwins;
2048  return 0;
2049}
2050
2051#if (defined(__BORLANDC__) || defined(_MSC_VER))
2052const hashtype Algo_hash::hashCodes[] = {
2053  1448047776469843i64 ,  23745670021858756i64 ,  2503503679898819i64 , 
2054  20893061577159209i64 ,  10807838381971450i64 ,  2362252468869198i64 , 
2055  24259008893265414i64 ,  12770534669822463i64 ,  6243872632612083i64 , 
2056  9878602848666731i64 ,  15403460661141300i64 ,  23328125617276831i64 , 
2057  24399618481479321i64 ,  6553504962910284i64 ,  1670313139184804i64 , 
2058  12980312942597170i64 ,  20479559860862969i64 ,  9622188310955879i64 , 
2059  240315181816498i64 ,  15806748501866401i64 ,  11025185739521454i64 , 
2060  9892014082139049i64 ,  24468178939325513i64 ,  18336761931886570i64 , 
2061  17607110247268341i64 ,  1659968630984898i64 ,  15644176636883129i64 , 
2062  21288430710467667i64 ,  21718647773405600i64 ,  8449573198599383i64 , 
2063  12949198458251018i64 ,  13260609204816340i64 ,  15942818511406502i64 , 
2064  19422389391992560i64 ,  2306873372585698i64 ,  13245768415868578i64 , 
2065  3527685889767840i64 ,  16821792770065498i64 ,  14659578113224043i64 , 
2066  8882299950073676i64 ,  7855747638699870i64 ,  11443553816792995i64 , 
2067  10278034782711378i64 ,  9888977721917330i64 ,  8622555585025384i64 ,
2068  20622776792089008i64 ,  6447699412562541i64 ,  21593237574254863i64 ,
2069  4100056509197325i64 ,  8358405560798101i64 ,  24120904895822569i64 ,
2070  21004758159739407i64 ,  4380824971205155i64 ,  23810250238005035i64 ,
2071  11573868012372637i64 ,  21740007761325076i64 ,  20569500166060069i64 ,
2072  23367084743140030i64 ,  832128940274250i64 ,  3863567854976796i64 ,
2073  8401188629788306i64 ,  20293444021869434i64 ,  12476938100997420i64 ,
2074  5997141871489394i64 ,  777596196611050i64 ,  8407423122275781i64 ,
2075  23742268390341663i64 ,  6606677504119583i64 ,  17099083579458611i64 ,
2076  128040681345920i64 ,  7441253945309846i64 ,  17672412151152227i64 ,
2077  14657002484427869i64 ,  3764334613856311i64 ,  7399928989161192i64 ,
2078  24730167942169592i64 ,  13814924480574978i64 ,  5810810907567287i64 ,
2079  7008927747711241i64 ,  3714629224790215i64 ,  9946435535599731i64 ,
2080  20057491299504334i64 ,  15866852457019228i64 ,  123155262761331i64 ,
2081  1315783062254243i64 ,  24497766846727950i64 ,  12902532251391440i64 ,
2082  16788431106050494i64 ,  15993209359043506i64 ,  6163570598235227i64 ,
2083  23479274902645580i64 ,  12086295521073246i64 ,  14074331278381816i64 ,
2084  1049820141442769i64 ,  5160957003350972i64 ,  24302799572195320i64 ,
2085  23881606652035662i64 ,  23969818184919245i64 ,  19374430422494128i64 ,
2086  9346353622623467i64 ,  13646698673919768i64 ,  20787456987251805i64 ,
2087  19834903548127921i64 ,  8194151691638546i64 ,  7687885124853709i64 ,
2088  4843137186034754i64 ,  23141719256229263i64 ,  5528755394284040i64 ,
2089  22362536622784133i64 ,  7624654257445620i64 ,  8792845080211956i64 ,
2090  24991012676161170i64 ,  5382030845010972i64 ,  1942150054817210i64 ,
2091  1024267612932772i64 ,  14257279792025309i64 ,  11127353401828247i64 ,
2092  4123063511789286i64 ,  363215666444395i64 ,  15523634951795520i64 ,
2093  21114031740764324i64 ,  12549698630972549i64 ,  7906682572409157i64 ,
2094  9682658163949194i64 ,  14445831019902887i64 ,  19796086007848283i64 ,
2095  25041651202294181i64 ,  434144873391024i64 ,  24468825775827696i64 ,
2096  16436890395501393i64 ,  16373785289815135i64 ,  16626551488832360i64 ,
2097  7748715007439309i64 ,  22731617567631698i64 ,  14232800365889972i64 ,
2098  10951727445457549i64 ,  8041373240290953i64 ,  24930514145406896i64 ,
2099  9591184974667554i64 ,  24880672410562956i64 ,  23221721160805093i64 ,
2100  20593543181655919i64 ,  23599230930155014i64 ,  15520097083998302i64 ,
2101  14424914931817466i64 ,  7073972177203460i64 ,  16674214483955582i64 ,
2102  4557916889838393i64 ,  14520120252661131i64 ,  2948253205366287i64 ,
2103  18549806070390636i64 ,  10409566723123418i64 ,  18398906015238963i64 ,
2104  21169009649313417i64 ,  18391044531337716i64 ,  2911838512392375i64 ,
2105  13771057876708721i64 ,  11955633853535396i64 ,  18911960208175147i64 ,
2106  1483143365895487i64 ,  5864164841327281i64 ,  16798674080914657i64 ,
2107  21169543712647072i64 ,  2554895121282201i64 ,  12465286616181485i64 ,
2108  5756888636558955i64 ,  2597276631190750i64 ,  2560624395830604i64 ,
2109  20296901708171088i64 ,  14642976680682096i64 ,  12194169777111940i64 ,
2110  938262584370639i64 ,  7206443811292574i64 ,  501111636607822i64 ,
2111  5705951146039127i64 ,  19098237626875269i64 ,  5726006303511723i64 ,
2112  5717532750720198i64 ,  4848344546021481i64 ,  7407311808156422i64 ,
2113  2061821731974308i64 ,  8556380079387133i64 ,  13575103943220600i64 ,
2114  10594365938844562i64 ,  19966653780019989i64 ,  24412404083453688i64 ,
2115  8019373982039936i64 ,  7753495706295280i64 ,  838015840877266i64 ,
2116  5235642127051968i64 ,  10225916255867901i64 ,  14975561937408701i64 ,
2117  4914762527221109i64 ,  16273933213731410i64 ,  25240707945233645i64 ,
2118  6477894775523777i64 ,  16128190602024745i64 ,  12452291569329611i64 ,
2119  51030855211419i64 ,  1848783942303739i64 ,  2537297571305471i64 ,
2120  24811709277564335i64 ,  23354767332363093i64 ,  11338712562024830i64 ,
2121  10845782284945582i64 ,  20710115514013598i64 ,  19611282767915684i64 ,
2122  11160258605900113i64 ,  17875966449141620i64 ,  8400967803093668i64 ,
2123  6871997953834029i64 ,  13914235659320051i64 ,  8949576634650339i64 ,
2124  2143755776666584i64 ,  13309009078638265i64 ,  17871461210902733i64 ,
2125  11987276750060947i64 ,  19212042799964345i64 ,  9684310155516547i64 ,
2126  1307858104678668i64 ,  8369225045337652i64 ,  11470364009363081i64 ,
2127  10726698770860164i64 ,  22857364846703600i64 ,  25284735055035435i64 ,
2128  19224377054148393i64 ,  16403807100295998i64 ,  4653376186522389i64 ,
2129  15242640882406966i64 ,  15315275662931969i64 ,  11642086728644568i64 ,
2130  12158439227609947i64 ,  5366950703441186i64 ,  21989897136444615i64 ,
2131  21241101455718813i64 ,  1591417368086590i64 ,  14579493634035095i64 ,
2132  23329624772309429i64 ,  4022767503269837i64 ,  12858990365780377i64 ,
2133  1546772101519453i64 ,  23839228242060485i64 ,  3152020333001361i64 ,
2134  7700997223270546i64 ,  7886359803633970i64 ,  18794372628879385i64 ,
2135  22159114735365084i64 ,  7999390508114986i64 ,  17413096555746886i64 ,
2136  9385231705999634i64 ,  15875377080359488i64 ,  4319895571584052i64 ,
2137  15831501864738265i64 ,  23927036136254152i64 ,  9023165779396619i64 ,
2138  6131245054225200i64 ,  20314359892927215i64 ,  1896686091879468i64 ,
2139  14130616725563771i64 ,  22653904323575475i64 ,  9831497463521490i64 ,
2140  13110057076369419i64 ,  5902087517632052i64 ,  23714067728868348i64 ,
2141  10422641883492326i64 ,  10327276345146850i64 ,  795518417987648i64 ,
2142  25452954487907785i64 ,  3500196309207718i64 ,  14513995844064906i64 ,
2143  7844549909962914i64 ,  9407804562184273i64 ,  15229768031797498i64 ,
2144  14111656085687927i64 ,  16834184600349678i64 ,  7291182384885469i64 ,
2145  17771577974633552i64 ,  21586473553657942i64 ,  18166326806718423i64 ,
2146  10928317030329388i64 ,  13135712137024532i64 ,  12947681282864548i64 ,
2147  21220312239923983i64 ,  9606249244876101i64 ,  4653965165819933i64 ,
2148  5039148287631156i64 ,  3987726544496362i64 ,  11235885894214833i64 ,
2149  3549024987193191i64 ,  6369560450327424i64 ,  5296536600431238i64 ,
2150  10833371878822587i64 ,  5746338282416722i64 ,  20335144029844343i64 ,
2151  14857534135172842i64 ,  13933887642921338i64 ,  3610489245941154i64 ,
2152  7780064458218242i64 ,  18217608762631328i64 ,  4861734558486078i64 ,
2153  19138089389909524i64 ,  162404484845663i64 ,  6326150309736266i64 ,
2154  5691634479075905i64 ,  14377989390160001i64 ,  7788436404648140i64 ,
2155  20312143630017606i64 ,  6781467023516504i64 ,  7265384191721189i64 ,
2156  13990392558924592i64 ,  4811546322556989i64 ,  3891404257596968i64 ,
2157  19222546653408634i64 ,  9733466771346453i64 ,  20011679489309705i64 ,
2158  11556921572925005i64 ,  13429005557512149i64 ,  16680841455593148i64 ,
2159  394589115298971i64 ,  22224576785554448i64 ,  18262625753524808i64 ,
2160  20893780129453860i64 ,  25064972830160559i64 ,  241970110039610i64 ,
2161  7452533933839720i64 ,  10726026396546933i64 ,  17312051917081899i64 ,
2162  17281553837379637i64 ,  24008819488103387i64 ,  5193878516496164i64 ,
2163  21529615734706496i64 ,  22844915602846365i64 ,  17118246686087168i64 ,
2164  6560869056902581i64 ,  10553021967047717i64 ,  3729950813036887i64 ,
2165  14459986099519295i64 ,  15808907290234758i64 ,  6234512969275540i64 ,
2166  18690008075805909i64 ,  492531108753402i64 ,  7721002928884704i64 ,
2167  4886156035126456i64 ,  21716374046066558i64 ,  11035311630511661i64 ,
2168  16837692753538891i64 ,  20172053977953882i64 ,  15488511700491202i64 ,
2169  17477921115358343i64 ,  24726937211646877i64 ,  22480504880004621i64 ,
2170  18521326635500559i64 ,  8076560603417178i64 ,  22382516625473209i64 ,
2171  21696842111535623i64 ,  12559160944089288i64 ,  1661142873895453i64 ,
2172  18379772814447567i64 ,  10295321430586466i64 ,  12378145201769592i64 , 
2173  11815752235866582i64 };
2174#else
2175const hashtype Algo_hash::hashCodes[] = {
2176  1448047776469843LL ,  23745670021858756LL ,  2503503679898819LL , 
2177  20893061577159209LL ,  10807838381971450LL ,  2362252468869198LL , 
2178  24259008893265414LL ,  12770534669822463LL ,  6243872632612083LL , 
2179  9878602848666731LL ,  15403460661141300LL ,  23328125617276831LL , 
2180  24399618481479321LL ,  6553504962910284LL ,  1670313139184804LL , 
2181  12980312942597170LL ,  20479559860862969LL ,  9622188310955879LL , 
2182  240315181816498LL ,  15806748501866401LL ,  11025185739521454LL , 
2183  9892014082139049LL ,  24468178939325513LL ,  18336761931886570LL , 
2184  17607110247268341LL ,  1659968630984898LL ,  15644176636883129LL , 
2185  21288430710467667LL ,  21718647773405600LL ,  8449573198599383LL , 
2186  12949198458251018LL ,  13260609204816340LL ,  15942818511406502LL , 
2187  19422389391992560LL ,  2306873372585698LL ,  13245768415868578LL , 
2188  3527685889767840LL ,  16821792770065498LL ,  14659578113224043LL , 
2189  8882299950073676LL ,  7855747638699870LL ,  11443553816792995LL , 
2190  10278034782711378LL ,  9888977721917330LL ,  8622555585025384LL ,
2191  20622776792089008LL ,  6447699412562541LL ,  21593237574254863LL ,
2192  4100056509197325LL ,  8358405560798101LL ,  24120904895822569LL ,
2193  21004758159739407LL ,  4380824971205155LL ,  23810250238005035LL ,
2194  11573868012372637LL ,  21740007761325076LL ,  20569500166060069LL ,
2195  23367084743140030LL ,  832128940274250LL ,  3863567854976796LL ,
2196  8401188629788306LL ,  20293444021869434LL ,  12476938100997420LL ,
2197  5997141871489394LL ,  777596196611050LL ,  8407423122275781LL ,
2198  23742268390341663LL ,  6606677504119583LL ,  17099083579458611LL ,
2199  128040681345920LL ,  7441253945309846LL ,  17672412151152227LL ,
2200  14657002484427869LL ,  3764334613856311LL ,  7399928989161192LL ,
2201  24730167942169592LL ,  13814924480574978LL ,  5810810907567287LL ,
2202  7008927747711241LL ,  3714629224790215LL ,  9946435535599731LL ,
2203  20057491299504334LL ,  15866852457019228LL ,  123155262761331LL ,
2204  1315783062254243LL ,  24497766846727950LL ,  12902532251391440LL ,
2205  16788431106050494LL ,  15993209359043506LL ,  6163570598235227LL ,
2206  23479274902645580LL ,  12086295521073246LL ,  14074331278381816LL ,
2207  1049820141442769LL ,  5160957003350972LL ,  24302799572195320LL ,
2208  23881606652035662LL ,  23969818184919245LL ,  19374430422494128LL ,
2209  9346353622623467LL ,  13646698673919768LL ,  20787456987251805LL ,
2210  19834903548127921LL ,  8194151691638546LL ,  7687885124853709LL ,
2211  4843137186034754LL ,  23141719256229263LL ,  5528755394284040LL ,
2212  22362536622784133LL ,  7624654257445620LL ,  8792845080211956LL ,
2213  24991012676161170LL ,  5382030845010972LL ,  1942150054817210LL ,
2214  1024267612932772LL ,  14257279792025309LL ,  11127353401828247LL ,
2215  4123063511789286LL ,  363215666444395LL ,  15523634951795520LL ,
2216  21114031740764324LL ,  12549698630972549LL ,  7906682572409157LL ,
2217  9682658163949194LL ,  14445831019902887LL ,  19796086007848283LL ,
2218  25041651202294181LL ,  434144873391024LL ,  24468825775827696LL ,
2219  16436890395501393LL ,  16373785289815135LL ,  16626551488832360LL ,
2220  7748715007439309LL ,  22731617567631698LL ,  14232800365889972LL ,
2221  10951727445457549LL ,  8041373240290953LL ,  24930514145406896LL ,
2222  9591184974667554LL ,  24880672410562956LL ,  23221721160805093LL ,
2223  20593543181655919LL ,  23599230930155014LL ,  15520097083998302LL ,
2224  14424914931817466LL ,  7073972177203460LL ,  16674214483955582LL ,
2225  4557916889838393LL ,  14520120252661131LL ,  2948253205366287LL ,
2226  18549806070390636LL ,  10409566723123418LL ,  18398906015238963LL ,
2227  21169009649313417LL ,  18391044531337716LL ,  2911838512392375LL ,
2228  13771057876708721LL ,  11955633853535396LL ,  18911960208175147LL ,
2229  1483143365895487LL ,  5864164841327281LL ,  16798674080914657LL ,
2230  21169543712647072LL ,  2554895121282201LL ,  12465286616181485LL ,
2231  5756888636558955LL ,  2597276631190750LL ,  2560624395830604LL ,
2232  20296901708171088LL ,  14642976680682096LL ,  12194169777111940LL ,
2233  938262584370639LL ,  7206443811292574LL ,  501111636607822LL ,
2234  5705951146039127LL ,  19098237626875269LL ,  5726006303511723LL ,
2235  5717532750720198LL ,  4848344546021481LL ,  7407311808156422LL ,
2236  2061821731974308LL ,  8556380079387133LL ,  13575103943220600LL ,
2237  10594365938844562LL ,  19966653780019989LL ,  24412404083453688LL ,
2238  8019373982039936LL ,  7753495706295280LL ,  838015840877266LL ,
2239  5235642127051968LL ,  10225916255867901LL ,  14975561937408701LL ,
2240  4914762527221109LL ,  16273933213731410LL ,  25240707945233645LL ,
2241  6477894775523777LL ,  16128190602024745LL ,  12452291569329611LL ,
2242  51030855211419LL ,  1848783942303739LL ,  2537297571305471LL ,
2243  24811709277564335LL ,  23354767332363093LL ,  11338712562024830LL ,
2244  10845782284945582LL ,  20710115514013598LL ,  19611282767915684LL ,
2245  11160258605900113LL ,  17875966449141620LL ,  8400967803093668LL ,
2246  6871997953834029LL ,  13914235659320051LL ,  8949576634650339LL ,
2247  2143755776666584LL ,  13309009078638265LL ,  17871461210902733LL ,
2248  11987276750060947LL ,  19212042799964345LL ,  9684310155516547LL ,
2249  1307858104678668LL ,  8369225045337652LL ,  11470364009363081LL ,
2250  10726698770860164LL ,  22857364846703600LL ,  25284735055035435LL ,
2251  19224377054148393LL ,  16403807100295998LL ,  4653376186522389LL ,
2252  15242640882406966LL ,  15315275662931969LL ,  11642086728644568LL ,
2253  12158439227609947LL ,  5366950703441186LL ,  21989897136444615LL ,
2254  21241101455718813LL ,  1591417368086590LL ,  14579493634035095LL ,
2255  23329624772309429LL ,  4022767503269837LL ,  12858990365780377LL ,
2256  1546772101519453LL ,  23839228242060485LL ,  3152020333001361LL ,
2257  7700997223270546LL ,  7886359803633970LL ,  18794372628879385LL ,
2258  22159114735365084LL ,  7999390508114986LL ,  17413096555746886LL ,
2259  9385231705999634LL ,  15875377080359488LL ,  4319895571584052LL ,
2260  15831501864738265LL ,  23927036136254152LL ,  9023165779396619LL ,
2261  6131245054225200LL ,  20314359892927215LL ,  1896686091879468LL ,
2262  14130616725563771LL ,  22653904323575475LL ,  9831497463521490LL ,
2263  13110057076369419LL ,  5902087517632052LL ,  23714067728868348LL ,
2264  10422641883492326LL ,  10327276345146850LL ,  795518417987648LL ,
2265  25452954487907785LL ,  3500196309207718LL ,  14513995844064906LL ,
2266  7844549909962914LL ,  9407804562184273LL ,  15229768031797498LL ,
2267  14111656085687927LL ,  16834184600349678LL ,  7291182384885469LL ,
2268  17771577974633552LL ,  21586473553657942LL ,  18166326806718423LL ,
2269  10928317030329388LL ,  13135712137024532LL ,  12947681282864548LL ,
2270  21220312239923983LL ,  9606249244876101LL ,  4653965165819933LL ,
2271  5039148287631156LL ,  3987726544496362LL ,  11235885894214833LL ,
2272  3549024987193191LL ,  6369560450327424LL ,  5296536600431238LL ,
2273  10833371878822587LL ,  5746338282416722LL ,  20335144029844343LL ,
2274  14857534135172842LL ,  13933887642921338LL ,  3610489245941154LL ,
2275  7780064458218242LL ,  18217608762631328LL ,  4861734558486078LL ,
2276  19138089389909524LL ,  162404484845663LL ,  6326150309736266LL ,
2277  5691634479075905LL ,  14377989390160001LL ,  7788436404648140LL ,
2278  20312143630017606LL ,  6781467023516504LL ,  7265384191721189LL ,
2279  13990392558924592LL ,  4811546322556989LL ,  3891404257596968LL ,
2280  19222546653408634LL ,  9733466771346453LL ,  20011679489309705LL ,
2281  11556921572925005LL ,  13429005557512149LL ,  16680841455593148LL ,
2282  394589115298971LL ,  22224576785554448LL ,  18262625753524808LL ,
2283  20893780129453860LL ,  25064972830160559LL ,  241970110039610LL ,
2284  7452533933839720LL ,  10726026396546933LL ,  17312051917081899LL ,
2285  17281553837379637LL ,  24008819488103387LL ,  5193878516496164LL ,
2286  21529615734706496LL ,  22844915602846365LL ,  17118246686087168LL ,
2287  6560869056902581LL ,  10553021967047717LL ,  3729950813036887LL ,
2288  14459986099519295LL ,  15808907290234758LL ,  6234512969275540LL ,
2289  18690008075805909LL ,  492531108753402LL ,  7721002928884704LL ,
2290  4886156035126456LL ,  21716374046066558LL ,  11035311630511661LL ,
2291  16837692753538891LL ,  20172053977953882LL ,  15488511700491202LL ,
2292  17477921115358343LL ,  24726937211646877LL ,  22480504880004621LL ,
2293  18521326635500559LL ,  8076560603417178LL ,  22382516625473209LL ,
2294  21696842111535623LL ,  12559160944089288LL ,  1661142873895453LL ,
2295  18379772814447567LL ,  10295321430586466LL ,  12378145201769592LL , 
2296  11815752235866582LL };
2297#endif
2298
2299HashFEntry::HashFEntry(hashtype HASHCODE, char* BUF, int LENGTH) {
2300  hashCode = HASHCODE;
2301  buf = BUF;
2302  length = LENGTH;
2303}
2304
2305HashFEntry::HashFEntry(const HashFEntry& hfe) {
2306  hashCode = hfe.hashCode;
2307  length = hfe.length;
2308  buf = new char[length];
2309  for(int i=0; i<length; i++) buf[i] = hfe.buf[i];
2310}
2311
2312HashFEntry::~HashFEntry() {
2313  if (buf) {
2314    delete [] buf;
2315    buf = 0;
2316  }
2317}
2318
2319HashhitF::HashhitF(int GAMEID, char ORIENTATION, char* blob) {
2320  gameid = GAMEID;
2321  orientation = ORIENTATION;
2322  cont = new MoveNC(blob[0], blob[1], blob[2]);
2323  emn = new ExtendedMoveNumber;
2324  emn->length = blob[3] * 256 + blob[4];
2325  emn->data = new int[emn->length];
2326  for(int i=0; i<emn->length; i++) {
2327    emn->data[i] = blob[5+2*i]*256 + blob[6+2*i];
2328  }
2329}
2330
2331HashhitF::HashhitF() {
2332  cont = 0;
2333  emn = 0;
2334}
2335
2336HashhitF::~HashhitF() {
2337  if (cont) delete cont;
2338  if (emn) delete emn;
2339}
2340
2341bool cmp_HashhitF(const HashhitF* a, const HashhitF* b) {
2342  return a->gameid < b->gameid;
2343}
2344
2345HashhitCS::HashhitCS(int GAMEID, int POSITION, bool CS) {
2346  gameid = GAMEID;
2347  position = POSITION;
2348  cs = CS;
2349}
2350
2351bool cmp_HashhitCS(const HashhitCS* a, const HashhitCS* b) {
2352  return a->gameid < b->gameid;
2353}
2354
2355
2356typedef vector<HashhitF* >* vpsip;
2357
2358
2359HashVarInfo::HashVarInfo(hashtype CHC, vector<pair<hashtype, ExtendedMoveNumber>* > * LFC,
2360                         ExtendedMoveNumber* MOVENUMBER, int NUMSTONES) {
2361  chc = CHC;
2362  numStones = NUMSTONES;
2363  moveNumber = new ExtendedMoveNumber(*MOVENUMBER);
2364  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
2365  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = LFC->begin(); it != LFC->end(); it++) {
2366    lfc->push_back(new pair<hashtype, ExtendedMoveNumber>((*it)->first, (*it)->second));
2367  }
2368}
2369
2370
2371Algo_hash_full::Algo_hash_full(int bsize, int MAXNUMSTONES) : Algorithm(bsize) {
2372  branchpoints = 0;
2373  maxNumStones = MAXNUMSTONES;
2374}
2375
2376Algo_hash_full::~Algo_hash_full() {
2377}
2378
2379int Algo_hash_full::insert_hash(hashtype hashCode, ExtendedMoveNumber& mn, Move* continuation) {
2380  // printf("insert %lld\n", hashCode);
2381  char* buf = new char[30 + mn.length*2];
2382  if (continuation) {
2383    buf[0] = continuation->x;
2384    buf[1] = continuation->y;
2385    buf[2] = continuation->color;
2386  } else {
2387    buf[0] = NO_CONT;
2388    buf[1] = 0;
2389    buf[2] = 0;
2390  }
2391  buf[3] = mn.length/256;
2392  buf[4] = mn.length%256;
2393  for (int i=0; i<mn.length; i++) {
2394    buf[5+2*i] = mn.data[i]/265;
2395    buf[6+2*i] = mn.data[i]%256;
2396  }
2397  hash_vector.push_back(HashFEntry(hashCode, buf, 5+2*mn.length));
2398  return 0;
2399}
2400
2401int Algo_hash_full::insert_all_hashes() {
2402  char sql[100];
2403  sprintf(sql, "insert into algo_hash_full_%d (hash, gameid, hit) values (?,?,?);", boardsize);
2404  sqlite3_stmt *ppStmt=0;
2405  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
2406  if (rc != SQLITE_OK || ppStmt==0) return rc;
2407  for(vector<HashFEntry>::iterator it = hash_vector.begin(); it != hash_vector.end(); it++) {
2408    rc = sqlite3_bind_int64(ppStmt, 1, it->hashCode);
2409    if (rc != SQLITE_OK) return rc;
2410    rc = sqlite3_bind_int(ppStmt, 2, gid);
2411    if (rc != SQLITE_OK) return rc;
2412    rc = sqlite3_bind_blob(ppStmt, 3, it->buf, it->length, SQLITE_TRANSIENT); 
2413    if (rc != SQLITE_OK) return rc;
2414    rc = sqlite3_step(ppStmt);
2415    if (rc != SQLITE_DONE) return rc;
2416    rc = sqlite3_reset(ppStmt);
2417    if (rc != SQLITE_OK) return rc;
2418  }
2419  rc = sqlite3_finalize(ppStmt);
2420  if (rc != SQLITE_OK) return rc;
2421  hash_vector.clear();
2422  return 0; // success
2423}
2424
2425void Algo_hash_full::initialize_process(sqlite3* DB) throw(DBError) {
2426  // printf("enter algo_hash_full::initialize_processing\n");
2427  db = DB;
2428  char sql[200];
2429  sprintf(sql, "create table if not exists algo_hash_full_%d ( id integer primary key, hash integer, gameid integer, hit text );", boardsize);
2430  int rc = sqlite3_exec(db, sql, 0, 0, 0);
2431  if (rc != SQLITE_OK) throw DBError();
2432  sprintf(sql, "create index if not exists hash_idx on algo_hash_full_%d(hash);", boardsize);
2433  rc = sqlite3_exec(db, sql, 0, 0, 0);
2434  if (rc != SQLITE_OK) throw DBError();
2435  // printf("leave algo_hash_full::initialize_processing\n");
2436}
2437
2438void Algo_hash_full::newgame_process(int game_id) {
2439  numStones = 0;
2440  gid = game_id;
2441  moveNumber = new ExtendedMoveNumber(0);
2442  currentHashCode = 0; // start with empty board
2443  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
2444  branchpoints = new stack<HashVarInfo>;
2445}
2446
2447void Algo_hash_full::AB_process(int x, int y) {
2448  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
2449    Move* continuation = new Move(x,y,'B');
2450    if (insert_hash((*it)->first, (*it)->second, continuation) != 0) throw DBError();
2451    delete continuation;
2452    delete *it;
2453  }
2454  delete lfc;
2455  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
2456  currentHashCode += Algo_hash::hashCodes[x + boardsize*y];
2457  numStones++;
2458}
2459
2460void Algo_hash_full::AW_process(int x, int y) {
2461  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
2462    Move* continuation = new Move(x,y,'W');
2463    if (insert_hash((*it)->first, (*it)->second, continuation) != 0) throw DBError();
2464    delete continuation;
2465    delete *it;
2466  }
2467  delete lfc;
2468  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
2469  currentHashCode -= Algo_hash::hashCodes[x + boardsize*y];
2470  numStones++;
2471}                 
2472
2473void Algo_hash_full::AE_process(int x, int y, char removed) {
2474  if (removed == 'B') currentHashCode -= Algo_hash::hashCodes[x + boardsize*y];
2475  else currentHashCode += Algo_hash::hashCodes[x + boardsize*y];
2476  numStones--;
2477}
2478
2479void Algo_hash_full::endOfNode_process() {
2480  if (numStones <= maxNumStones) lfc->push_back(new pair<hashtype, ExtendedMoveNumber>(currentHashCode, *moveNumber));
2481  moveNumber->next();
2482}
2483
2484void Algo_hash_full::pass_process() {
2485  // (we do not count pass as continuation)
2486}
2487
2488void Algo_hash_full::move_process(Move m) throw(DBError) {
2489  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
2490    Move* continuation = new Move(m);
2491    int rc = insert_hash((*it)->first, (*it)->second, continuation);
2492    if (rc != 0) throw DBError();
2493    delete continuation;
2494    delete *it;
2495  }
2496  delete lfc;
2497  lfc = new vector<pair<hashtype, ExtendedMoveNumber>* >;
2498  int epsilon = (m.color == 'B' || m.color == 'X' ? 1 : -1);
2499  currentHashCode += epsilon * Algo_hash::hashCodes[m.x + boardsize*m.y];
2500  numStones++;
2501
2502  if (m.captures) {
2503    vector<p_cc>::iterator it;
2504    for(it = m.captures->begin(); it != m.captures->end(); it++) {
2505      int xx = it->first;
2506      int yy = it->second;
2507
2508      currentHashCode += epsilon * Algo_hash::hashCodes[xx + boardsize*yy];
2509      numStones--;
2510    }
2511  }
2512}
2513
2514void Algo_hash_full::branchpoint_process() {
2515  branchpoints->push(HashVarInfo(currentHashCode, lfc, moveNumber, numStones));
2516  // printf("push %lld\n", currentHashCode);
2517}
2518
2519void Algo_hash_full::endOfVariation_process() throw(DBError) {
2520  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
2521    int rc = insert_hash((*it)->first, (*it)->second, 0);
2522    if (rc != 0) throw DBError();
2523    delete *it;
2524  }
2525  delete lfc;
2526  delete moveNumber;
2527  currentHashCode = branchpoints->top().chc;
2528  lfc = branchpoints->top().lfc;
2529  moveNumber = branchpoints->top().moveNumber;
2530  numStones = branchpoints->top().numStones;
2531  // printf("pop %lld\n", currentHashCode);
2532  branchpoints->pop();
2533}
2534
2535void Algo_hash_full::endgame_process(bool commit) throw(DBError) {
2536  for(vector<pair<hashtype, ExtendedMoveNumber>* >::iterator it = lfc->begin(); it != lfc->end(); it++) {
2537    Move* continuation = 0;
2538    int rc = insert_hash((*it)->first, (*it)->second, continuation);
2539    if (rc != 0) throw DBError();
2540    delete *it;
2541  }
2542  if (commit) {
2543    int rc = insert_all_hashes();
2544    if (rc) printf("ouch %d\n",rc);
2545  } else hash_vector.clear();
2546  delete lfc;
2547  delete moveNumber;
2548  delete branchpoints;
2549}
2550 
2551void Algo_hash_full::finalize_process() {
2552}
2553
2554
2555hashtype Algo_hash_full::compute_hashkey(Pattern& pattern) {
2556  if (pattern.sizeX != boardsize || pattern.sizeY != boardsize)
2557    return NOT_HASHABLE;
2558  hashtype hashkey = 0;
2559  int ns = 0;         
2560  for(int i=0; i<boardsize; i++) {
2561    for(int j=0; j<boardsize; j++) {
2562      char p = pattern.finalPos[i + boardsize*j];
2563      if (p == 'x' || p ==  'o' || p == '*') return NOT_HASHABLE;
2564      else if (p == 'X') {
2565        hashkey += Algo_hash::hashCodes[i + boardsize*j];
2566        ns++;
2567      } else if (p == 'O') {
2568        hashkey -= Algo_hash::hashCodes[i + boardsize*j];
2569        ns++;
2570      }
2571    }
2572  }
2573  if (ns > maxNumStones) return NOT_HASHABLE;
2574  return hashkey;
2575}
2576
2577int insert_result_hf(void *results, int argc, char **argv, char **azColName) throw (DBError) {
2578  vpsip res = ((pair<vpsip, int>*)results)->first;
2579  int orientation = ((pair<vpsip, int>*)results)->second;
2580  if (argc==2 && argv[0]) {
2581    res->push_back(new HashhitF(atoi(argv[0]), orientation, argv[1]));
2582  } else throw DBError();
2583  return 0;
2584}
2585
2586
2587int Algo_hash_full::search(PatternList& patternList, GameList& gl, SearchOptions& options, sqlite3* db) {
2588  // printf("enter algo_hash_full::search\n");
2589  int numOfHits = 0;
2590  int self_numOfSwitched = 0;
2591  int Bwins = 0;
2592  int Wwins = 0;
2593
2594  int hash_result = -1; // -1 = failure; 0 = ok, but have to check w/ Algo_movelist, 1 = ok, produced final result
2595  int plS = patternList.size();
2596  vpsip results = new vector<HashhitF* >;
2597  for(int N=0; N<plS; N++) {
2598    hashtype hashCode = compute_hashkey(patternList.data[N]);
2599    if (hashCode == NOT_HASHABLE) return -1; // failure
2600
2601    char sql[100];
2602#if (defined(__BORLANDC__) || defined(_MSC_VER))
2603    sprintf(sql, "select gameid,hit from algo_hash_full_%d where hash = %I64d", boardsize, hashCode);
2604#else
2605    sprintf(sql, "select gameid,hit from algo_hash_full_%d where hash = %lld", boardsize, hashCode);
2606#endif
2607    // printf("hc %lld, %s\n", hashCode, sql);
2608    pair<vpsip, int> rN(results, N);
2609    sqlite3_exec(db, sql, insert_result_hf, &rN, 0);
2610  }
2611  if (options.trustHashFull && patternList.pattern.contList.size()==0) hash_result = 1;
2612  else hash_result = 0;
2613  if (gl.start_sorted() == 0) {
2614    sort(results->begin(), results->end(), cmp_HashhitF);
2615    // printf("res-size %d\n", results->size());
2616    vector<HashhitF* >::iterator resultIT = results->begin();
2617    while (resultIT != results->end()) {
2618      int index = (*resultIT)->gameid;
2619
2620      if (hash_result) {
2621        gl.setCurrentFromIndex(index);
2622        int numOfSwitched = 0;
2623        vector<Hit* >* hits = new vector<Hit* >;
2624        while ((*resultIT)->gameid == index) {
2625          if ((*resultIT)->emn->total_move_num() > options.moveLimit) {
2626            resultIT++;
2627            continue;
2628          }
2629          char *label;
2630          if ((*resultIT)->cont->x != NO_CONT) { // continuation
2631            label = patternList.updateContinuations((*resultIT)->orientation, 
2632                                                    (*resultIT)->cont->x, (*resultIT)->cont->y, (*resultIT)->cont->color,
2633                                                    false, // tenuki impossible with full board pattern
2634                                                    gl.getCurrentWinner());
2635            if (label) {
2636              hits->push_back(new Hit((*resultIT)->emn, label));
2637              (*resultIT)->emn = 0;
2638              numOfSwitched += label[2];
2639            }
2640          } else {
2641            label = new char[3];
2642            label[0] = NO_CONT;
2643            label[1] = 0;
2644            label[2] = patternList.data[(*resultIT)->orientation].colorSwitch;
2645            numOfSwitched += label[2];
2646            hits->push_back(new Hit((*resultIT)->emn, label));
2647            (*resultIT)->emn = 0;
2648          }
2649          resultIT++;
2650          if (resultIT == results->end()) break;
2651        }
2652        if (hits->size()) {
2653          numOfHits += hits->size();
2654          self_numOfSwitched += numOfSwitched;
2655          if (gl.getCurrentWinner() == 'B') {
2656            Bwins += hits->size() - numOfSwitched;
2657            Wwins += numOfSwitched;
2658          } else if (gl.getCurrentWinner() == 'W') {
2659            Bwins += numOfSwitched;
2660            Wwins += hits->size() - numOfSwitched;
2661          }
2662          gl.makeCurrentHit(hits);
2663        } else delete hits;
2664      } else { // produce Candidate list, check using another algorithm
2665        vector<Candidate* >* candidates = new vector<Candidate* >;
2666        while ((*resultIT)->gameid == index) {
2667          if ((*resultIT)->emn->total_move_num() > options.moveLimit) continue;
2668          candidates->push_back(new Candidate(0,0,(*resultIT)->orientation));
2669          resultIT++;
2670          if (resultIT == results->end()) break;
2671        }
2672        gl.makeIndexCandidate(index, candidates);
2673      }
2674    }
2675    for(vector<HashhitF* >::iterator it = results->begin(); it != results->end(); it++) delete *it;
2676    delete results;
2677    gl.end_sorted();
2678  }
2679  gl.num_hits = numOfHits;
2680  gl.num_switched = self_numOfSwitched;
2681  gl.Bwins = Bwins;
2682  gl.Wwins = Wwins;
2683  return hash_result;
2684}
2685
2686// -----------------------------------------------------------------------------------
2687
2688Algo_hash::Algo_hash(int bsize, const string& DBNAMEEXT, int MAXNUMSTONES) : Algorithm(bsize) {
2689  dbnameext = DBNAMEEXT;
2690  hi = 0;
2691  maxNumStones = MAXNUMSTONES;
2692}
2693
2694Algo_hash::~Algo_hash() {
2695  if (hi) delete hi;
2696}
2697
2698int Algo_hash::insert_hash(hashtype hashCode, int pos) {
2699  hash_vector.push_back(make_pair(hashCode, pos));
2700  return 0;
2701}
2702
2703int Algo_hash::insert_all_hashes() {
2704  // printf("insert all hashes %d\n", hash_vector.size());
2705  char sql[200];
2706  sprintf(sql, "insert into algo_hash_%d_%s (hash, gameid, position) values (?,?,?);", boardsize, dbnameext.c_str());
2707  sqlite3_stmt *ppStmt=0;
2708  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
2709  if (rc != SQLITE_OK || ppStmt==0) return rc;
2710  rc = sqlite3_bind_int(ppStmt, 2, gid);
2711  if (rc != SQLITE_OK) return rc;
2712  for(vector<pair<hashtype, int> >::iterator it = hash_vector.begin(); it != hash_vector.end(); it++) {
2713    // printf("insert %d %d\n", it->first, it->second);
2714    rc = sqlite3_bind_int64(ppStmt, 1, it->first);
2715    if (rc != SQLITE_OK) return rc;
2716    rc = sqlite3_bind_int(ppStmt, 3, it->second);
2717    if (rc != SQLITE_OK) return rc;
2718    rc = sqlite3_step(ppStmt);
2719    if (rc != SQLITE_DONE) return rc;
2720    rc = sqlite3_reset(ppStmt);
2721    if (rc != SQLITE_OK) return rc;
2722  }
2723  rc = sqlite3_finalize(ppStmt);
2724  if (rc != SQLITE_OK) return rc;
2725  return 0; // success
2726}
2727
2728void Algo_hash::initialize_process(sqlite3* DB) throw(DBError) {
2729  // printf("enter algo_hash::initialize_processing\n");
2730  db = DB;
2731  char buf[200];
2732  sprintf(buf, "create table if not exists algo_hash_%d_%s ( hash integer, gameid integer, position integer );", boardsize, dbnameext.c_str());
2733  int rc = sqlite3_exec(db, buf, 0, 0, 0);
2734  if (rc != SQLITE_OK) throw DBError();
2735  sprintf(buf, "create index if not exists hash_idx_%d_%s on algo_hash_%d_%s(hash);", boardsize, dbnameext.c_str(), boardsize, dbnameext.c_str());
2736  rc = sqlite3_exec(db, buf, 0, 0, 0);
2737  if (rc != SQLITE_OK) throw DBError();
2738  // printf("leave algo_hash::initialize_processing\n");
2739}
2740       
2741void Algo_hash::newgame_process(int game_id) {
2742  gid = game_id;
2743  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2744    it->initialize();
2745}
2746
2747void Algo_hash::AB_process(int x, int y) {
2748  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2749    it->addB(x,y);
2750}
2751
2752void Algo_hash::AW_process(int x, int y) {
2753  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2754    it->addW(x,y);
2755}                 
2756
2757void Algo_hash::AE_process(int x, int y, char removed) {
2758  if (removed == 'B') {
2759    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) it->removeB(x,y);
2760  } else { 
2761    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) it->removeW(x,y);
2762  }
2763}
2764
2765void Algo_hash::endOfNode_process() {
2766  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++) {
2767    if (it->numStones <= maxNumStones && it->changed) {
2768      it->changed = false;
2769      pair<hashtype,int> phi = it->cHC();
2770      insert_hash(phi.first, phi.second);
2771      // printf("insert hash CORNER %d %d\n", phi.first, phi.second);
2772    }
2773  }
2774}
2775
2776void Algo_hash::pass_process() {
2777  // (we do not count pass as continuation)
2778}
2779
2780void Algo_hash::move_process(Move m) throw(DBError) {
2781  if (m.color == 'B') {
2782    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2783      it->addB(m.x, m.y);
2784    if (m.captures) {
2785      for(vector<p_cc>::iterator cap_it = m.captures->begin(); cap_it != m.captures->end(); cap_it++) {
2786        for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2787          it->removeW(cap_it->first, cap_it->second);
2788      }
2789    }
2790  } else {
2791    for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2792      it->addW(m.x, m.y);
2793    if (m.captures) {
2794      for(vector<p_cc>::iterator cap_it = m.captures->begin(); cap_it != m.captures->end(); cap_it++) {
2795        for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2796          it->removeB(cap_it->first, cap_it->second);
2797      }
2798    }
2799  }
2800}
2801
2802void Algo_hash::branchpoint_process() {
2803  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2804    it->bppush();
2805}
2806
2807void Algo_hash::endOfVariation_process() {
2808  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2809    it->bppop();
2810}
2811
2812void Algo_hash::endgame_process(bool commit) {
2813  for(vector<HashInstance>::iterator it = hi->begin(); it != hi->end(); it++)
2814    it->finalize();
2815  if (commit) {
2816    int rc = insert_all_hashes();
2817    if (rc) printf("ouch %d\n",rc);
2818    hash_vector.clear();
2819  } else hash_vector.clear();
2820}
2821 
2822void Algo_hash::finalize_process() {
2823}
2824
2825
2826pair<hashtype,int> Algo_hash::compute_hashkey(PatternList& pl, int CS) {
2827  return make_pair(NOT_HASHABLE,0);
2828}
2829
2830int insert_result(void *rN, int argc, char **argv, char **azColName) throw (DBError) {
2831  vector<HashhitCS* >* results = ((pair<vector<HashhitCS* >*, hashtype>*)rN)->first;
2832  hashtype hashCode = ((pair<vector<HashhitCS* >*, hashtype>*)rN)->second;
2833
2834  if (argc==3 && argv[0] && argv[1] && argv[2]) {
2835    // printf("found %s, %lld", argv[2], atoi(argv[2]));
2836#if (defined(__BORLANDC__) || defined(_MSC_VER))
2837    ((vector<HashhitCS* >*)results)->push_back(new HashhitCS(atoi(argv[0]), atoi(argv[1]), _atoi64(argv[2])!=hashCode));
2838#else
2839    ((vector<HashhitCS* >*)results)->push_back(new HashhitCS(atoi(argv[0]), atoi(argv[1]), atoll(argv[2])!=hashCode));
2840#endif
2841  } else throw DBError();
2842  return 0;
2843}
2844
2845
2846int Algo_hash::search(PatternList& patternList, GameList& gl, SearchOptions& options, sqlite3* db) {
2847  // return value: -1 = failure; 0 = ok, but have to check w/ Algo_movelist
2848
2849  vector<HashhitCS* >* results = new vector<HashhitCS* >;
2850
2851  pair<hashtype, int> hco = compute_hashkey(patternList, 0);
2852  hashtype hashCode = hco.first;
2853  // printf("HC %lld\n", hashCode);
2854  hashtype hashCode2 = hashCode;
2855  if (hashCode == NOT_HASHABLE) {
2856    delete results;
2857    return -1; // failure
2858  }
2859  int fl = patternList.data[hco.second].flip;
2860  int fl2 = fl;
2861  char buf[100];
2862#if (defined(__BORLANDC__) || defined(_MSC_VER))
2863  sprintf(buf, "select gameid,position,hash from algo_hash_%d_%s where hash = %I64d", 
2864      boardsize, dbnameext.c_str(), hashCode);
2865#else
2866  sprintf(buf, "select gameid,position,hash from algo_hash_%d_%s where hash = %lld", 
2867      boardsize, dbnameext.c_str(), hashCode);
2868#endif
2869  string sql = buf;
2870
2871  bool cs = patternList.data[patternList.size()-1].colorSwitch;
2872  if (cs) {
2873    pair<hashtype, int> hco = compute_hashkey(patternList, 1);
2874    hashCode2 = hco.first;
2875    // printf("HC2 %lld\n", hashCode2);
2876    if (hashCode == NOT_HASHABLE) {
2877      delete results;
2878      return -1; // failure
2879    }
2880    fl2 = patternList.data[hco.second].flip;
2881
2882    if (hashCode != hashCode2) {
2883#if (defined(__BORLANDC__) || defined(_MSC_VER))
2884      sprintf(buf, " or hash = %I64d", hashCode2);
2885#else
2886      sprintf(buf, " or hash = %lld", hashCode2);
2887#endif
2888      sql += buf;
2889    }
2890  }
2891  sql += " order by gameid";
2892
2893  if (gl.start_sorted() == 0) {
2894    // query database
2895
2896    // printf("%s\n", sql);
2897    pair<vector<HashhitCS* >*, hashtype> rN(results, hashCode);
2898    sqlite3_exec(db, sql.c_str(), insert_result, &rN, 0);
2899    // printf("results->size() %d\n", results->size());
2900
2901    // communicate results of query to database
2902   
2903    vector<HashhitCS* >::iterator resultIT = results->begin();
2904    while (resultIT != results->end()) {
2905      // printf("gid %d\n", (*resultIT)->gameid);
2906      int index = (*resultIT)->gameid;
2907
2908      vector<Candidate* >* candidates = new vector<Candidate* >;
2909      while ((*resultIT)->gameid == index) {
2910        // int pos = (*resultIT)->position % (1<<16);
2911        int ori = (*resultIT)->position / (1<<16);
2912        // printf("%d %d\n", pos, ori);
2913        if (cs && hashCode == hashCode2) { // this is a somewhat pathological case ...
2914          int ind = patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)];
2915          candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
2916          ind = patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)];
2917          candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
2918        } else {
2919          if ((*resultIT)->cs) {
2920            // FIXME works only for corner patterns right now!
2921            int ind = patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)];
2922            // printf("cand cs %d %d %d\n", patternList.flipTable[8+Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl2)], patternList.data[ind].left, patternList.data[ind].top);
2923            candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
2924          } else {
2925            int ind = patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)];
2926            // printf("cand %d %d %d\n", patternList.flipTable[Pattern::compose_flips(Pattern::PatternInvFlip(ori),fl)], patternList.data[ind].left, patternList.data[ind].top);
2927            candidates->push_back(new Candidate(patternList.data[ind].left, patternList.data[ind].top, ind));
2928          }
2929        }
2930        resultIT++;
2931        if (resultIT == results->end()) break;
2932      }
2933      gl.makeIndexCandidate(index, candidates);
2934    }
2935    for(vector<HashhitCS* >::iterator it = results->begin(); it != results->end(); it++) delete *it;
2936    delete results;
2937    gl.end_sorted();
2938  } else return -1;
2939  return 0;
2940}
2941
2942Algo_hash_corner::Algo_hash_corner(int bsize, int SIZE, int MAXNUMSTONES) : Algo_hash(bsize, "CORNER", MAXNUMSTONES) {
2943  size = SIZE;
2944  char buf[5];
2945  sprintf(buf, "%d", size);
2946  dbnameext += buf;
2947  hi = new vector<HashInstance>;
2948  hi->push_back(HashInstance(0,0,size,size,boardsize));
2949  hi->push_back(HashInstance(0,bsize-size,size,size,boardsize));
2950  hi->push_back(HashInstance(bsize-size,0,size,size,boardsize));
2951  hi->push_back(HashInstance(bsize-size, bsize-size, size, size,boardsize));
2952}
2953
2954pair<hashtype,int> Algo_hash_corner::compute_hashkey(PatternList& pl, int CS) {
2955  if (pl.data[0].sizeX < size || pl.data[0].sizeY < size || pl.data[0].left != pl.data[0].right || pl.data[0].top != pl.data[0].bottom || (pl.data[0].left != 0 && pl.data[0].left != boardsize-size) || (pl.data[0].top != 0 && pl.data[0].top != boardsize-size)) return make_pair(NOT_HASHABLE,0);
2956  hashtype hk = NOT_HASHABLE;
2957  int f = 0;
2958  vector<hashtype> hCodes;
2959  for(int pCtr=0; pCtr<pl.size(); pCtr++) {
2960    if (CS == pl.data[pCtr].colorSwitch) {
2961      hashtype hashkey = 0;
2962      int ns = 0;
2963
2964      Pattern *pattern = & pl.data[pCtr];
2965      int offsetX = 0;
2966      int offsetY = 0;
2967      if (pattern->left > 0) offsetX = boardsize-size-pattern->left; // pattern located on east side of board
2968      if (pattern->top > 0) offsetY = boardsize-size-pattern->top;   // ... south ...
2969      for(int i=0; i<size; i++) {
2970        for(int j=0; j<size; j++) {
2971          char p = pattern->finalPos[i+offsetX + pattern->sizeX*(j+offsetY)];
2972          if (p == 'x' || p ==  'o' || p == '*') return make_pair(NOT_HASHABLE,0);
2973          else if (p == 'X') {
2974            hashkey += hashCodes[i+offsetX+pattern->left + boardsize*(j+offsetY+pattern->top)];
2975            ns++;
2976          } else if (p == 'O') {
2977            hashkey -= hashCodes[i+offsetX+pattern->left + boardsize*(j+offsetY+pattern->top)];
2978            ns++;
2979          }
2980        }
2981      }
2982      if (ns < 3 || ns > maxNumStones) return make_pair(NOT_HASHABLE,0);
2983
2984      // make sure all hash keys are unique
2985      for(vector<hashtype>::iterator it = hCodes.begin(); it != hCodes.end(); it++)
2986        if (*it == hashkey) return make_pair(NOT_HASHABLE, 0);
2987      hCodes.push_back(hashkey);
2988
2989      if (hk==NOT_HASHABLE || hashkey<hk) {
2990        hk = hashkey;
2991        f = pCtr;
2992      }
2993    }
2994  }
2995  return make_pair(hk, f);
2996}
2997
2998// Algo_hash_side::Algo_hash_side(int bsize, int SIZEX, int SIZEY) : Algo_hash(bsize, "SIDE") {
2999//   sizeX = SIZEX;
3000//   sizeY = SIZEY;
3001//   char buf[10];
3002//   sprintf(buf, "%d_%d", sizeX, sizeY);
3003//   dbnameext += buf;
3004//
3005//   hi = new vector<HashInstance>;
3006//   for(int i=1; i<bsize-1-sizeX; i++)
3007//     hi->push_back(HashInstance(i,0,sizeX, sizeY,boardsize));
3008//   for(int i=1; i<bsize-1-sizeX; i++)
3009//     hi->push_back(HashInstance(i,bsize-sizeY,sizeX, sizeY,boardsize));
3010//   for(int i=1; i<bsize-1-sizeX; i++)
3011//     hi->push_back(HashInstance(0, i, sizeY, sizeX,boardsize));
3012//   for(int i=1; i<bsize-1-sizeX; i++)
3013//     hi->push_back(HashInstance(bsize-sizeY, i, sizeY, sizeX,boardsize));
3014// }
3015
3016HashInstance::HashInstance(char X, char Y, char SIZEX, char SIZEY, int BOARDSIZE) {
3017  boardsize = BOARDSIZE;
3018  xx = X;
3019  yy = Y;
3020  pos = xx + boardsize*yy;
3021  sizeX = SIZEX; 
3022  sizeY = SIZEY;
3023  branchpoints = 0;
3024  currentHashCode = 0;
3025  numStones = 0;
3026  changed = true;
3027}
3028
3029HashInstance::~HashInstance() {
3030  finalize();
3031}
3032
3033void HashInstance::finalize() {
3034  if (branchpoints) {
3035    while (branchpoints->size()) {
3036      delete [] branchpoints->top().first;
3037      branchpoints->pop();
3038    }
3039    delete branchpoints;
3040    branchpoints = 0;
3041  }
3042  if (currentHashCode) {
3043    delete [] currentHashCode;
3044    currentHashCode = 0;
3045  }
3046}
3047
3048bool HashInstance::inRelevantRegion(char X, char Y) {
3049  if (xx <= X && X < xx+sizeX && yy <= Y && Y < yy+sizeY) return true;
3050  return false;
3051}
3052
3053void HashInstance::initialize() {
3054  currentHashCode = new hashtype[8]; 
3055  for(int i=0; i<8; i++) currentHashCode[i] = 0; // start with empty board
3056  numStones = 0;
3057  branchpoints = new stack<pair<hashtype*,int> >;
3058  changed = true; // do record empty pattern ...
3059}
3060
3061void HashInstance::addB(char x, char y) {
3062  if (inRelevantRegion(x,y)) {
3063    changed = true;
3064    for(int i=0; i<8; i++) {
3065      currentHashCode[i] += Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
3066    }
3067    numStones++;
3068  }
3069}
3070
3071void HashInstance::addW(char x, char y) {
3072  if (inRelevantRegion(x,y)) {
3073    changed = true;
3074    for(int i=0; i<8; i++) {
3075      currentHashCode[i] -= Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
3076    }
3077    numStones++;
3078  }
3079}
3080
3081void HashInstance::removeB(char x, char y) {
3082  if (inRelevantRegion(x,y)) {
3083    changed = true;
3084    for(int i=0; i<8; i++) {
3085      currentHashCode[i] -= Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
3086    }
3087    numStones++;
3088  }
3089}
3090
3091void HashInstance::removeW(char x, char y) {
3092  if (inRelevantRegion(x,y)) {
3093    changed = true;
3094    for(int i=0; i<8; i++) {
3095      currentHashCode[i] += Algo_hash::hashCodes[Pattern::flipsX(i,x,y,boardsize-1, boardsize-1) + boardsize*Pattern::flipsY(i,x,y,boardsize-1, boardsize-1)];
3096    }
3097    numStones++;
3098  }
3099}
3100
3101pair<hashtype,int> HashInstance::cHC() {
3102  int flip = 0;
3103  hashtype minCHC = currentHashCode[0];
3104  for(int i=1; i<8; i++) { 
3105    if (currentHashCode[i] < minCHC) {
3106      minCHC = currentHashCode[i];
3107      flip = i;
3108    }
3109  }
3110  return make_pair(minCHC, flip*(1<<16)  + pos);
3111}
3112
3113void HashInstance::bppush() {
3114  hashtype* chc = new hashtype[8];
3115  for(int i=0; i<8; i++) chc[i] = currentHashCode[i];
3116  branchpoints->push(make_pair(chc, numStones));
3117}
3118
3119void HashInstance::bppop() {
3120  delete [] currentHashCode;
3121  currentHashCode = branchpoints->top().first;
3122  numStones = branchpoints->top().second;
3123  branchpoints->pop();
3124}
3125
3126
3127// UIntervals::UIntervals(intervs = []) {
3128//   data = intervs;
3129// }
3130//
3131//
3132// void UIntervals::first() {
3133//   if (data->size()) return data[0].first;
3134//   else return -1; // FIXME ?!
3135// }
3136//
3137// void UIntervals::append(int interv_start, int interv_end) {
3138//   data.push_back(pair<int,int>(interv_start, interv_end));
3139// }
3140//
3141//
3142// void UIntervals::inters(UIntervals& uinterv) {
3143//   int current2low = 0;
3144//   int current2high = 0;
3145//
3146//   vector<pair<int,int>> newUInt();
3147//
3148//   for(int current1=0; current1 < data.size(); current1++) {
3149//     while (current2low < uinterv.data.size && !(uinterv.data[current2low].second > data[current1].first))
3150//       current2low++;
3151//     current2high = current2low;
3152//     while (current2high < uinterv.data.size() && uinterv.data[current2high].first < data[current1].second)
3153//       current2high++;
3154//     current2high--;
3155//
3156//     if (current2low == uinterv.data.size()) break;
3157//     if (current2high < current2low) continue;
3158//
3159//     newUInt.append(max(self.data[current1][0], uinterv.data[current2low][0]),
3160//       min(self.data[current1][1], uinterv.data[current2low][1]));
3161//
3162//     for(int c=current2low+1; c < current2high; c++)
3163//       newUInt.append(uinterv.data[c].first, uninterv.data[c].second);
3164//
3165//     if (current2high > current2low)
3166//       newUInt.append(uinterv.data[current2high].first, min(uinterv.data[current2high].second, data[current1].second));
3167//
3168//     current2low = current2high;
3169//   }
3170//   data = newUInt;
3171// }
3172//
3173// void UIntervals::isEmpty() {
3174//   int isEmpty = 1;
3175//   for(int i=0; i<data.size(); i++)
3176//     if (data[i].first < data[i].second) isEmpty = 0;
3177//   return isEmpty;
3178// }
3179//
3180//
3181//
3182// Algo_intervals::Algo_intervals(int bsize) {
3183//   boardsize = bsize;
3184// }                       
3185//
3186//
3187// void Algo_intervals::initialize_process(int l) {
3188//
3189//   movesArr = vector<long>();
3190//   moveIntsArr = vector<long>();
3191// }
3192//
3193// void Algo_intervals::newgame_process() {
3194//   counter = 0;
3195//   moves = [];
3196//   for(int i=0; i<boardsize*boardsize; i++) moves.append([]);
3197//   ignore = 0;
3198// }
3199//
3200// void Algo_intervals::AB_process(int x, int y) {
3201//   if (ignore) return;
3202//   moves[boardsize*x+y]->push_back(counter | FLAG_BLACK);
3203// }
3204//
3205//
3206// void Algo_intervals::AW_process(int x, int y) {
3207//   if (ignore) return;
3208//   moves[boardsize*x+y]->push_back(counter | FLAG_WHITE);
3209// }
3210//
3211// void Algo_intervals::AE_process(int x, int y, char removed) {
3212//   if (ignore) return;
3213//   self.moves[self.boardsize*x+y]->push_back(counter | FLAG_REMOVE);
3214// }
3215//
3216// void Algo_intervals::endOfNode_process() {
3217//   if (ignore) return;
3218//   counter++;
3219// }
3220//
3221// void Algo_intervals::B_process(int x, int y, cap) {
3222//   if (ignore) return;
3223//   moves[self.boardsize*x+y]->push_back(counter | FLAG_BLACK);
3224//   for(c in cap)
3225//     moves[self.boardsize*c[0] + c[1]]->push_back(counter | FLAG_REMOVE);
3226// }
3227//
3228// void Algo_intervals::W_process(int x, int y, cap) {
3229//   if (ignore) return;
3230//   moves[self.boardsize*x+y]->push_back(counter | FLAG_WHITE);
3231//   for(c in cap)
3232//     moves[self.boardsize*c[0] + c[1]]->push_back(counter | FLAG_REMOVE);
3233// }
3234//
3235// void Algo_intervals::branchpoint_process() {
3236// }
3237//
3238//
3239// void Algo_intervals::endOfVariation_process() {
3240//   ignore = 1;
3241// }
3242//
3243//
3244// void Algo_intervals::endgame_process() {
3245//   for(int x=0; x < boardsize; x++) {
3246//     for(int y=0; y < boardsize; y++) {
3247//       if (!moves[self.boardsize*x+y]->size())
3248//  movesArr.push_back(0);
3249//       else if (moves[self.boardsize*x+y]->size() == 1) {
3250//  long d = (*moves[self.boardsize*x+y])[0];
3251//  self.movesArr.append(d);
3252//       }
3253//       else {
3254//  vector<int>* mvs = moves[self.boardsize*x+y];
3255//  long d = moveIntsArr.size() | FLAG_POINTER;
3256//
3257//  vector<long> Blist;
3258//  vector<long> Wlist;
3259//  vector<long> Elist;
3260//
3261//  Elist.push_back(0);
3262//
3263//  int moveIndex = 0;
3264//  while (moveIndex < mvs.size()) {
3265//    if (mvs[moveIndex] & FLAG_BLACK) {
3266//      d = d | FLAG_BLACK;
3267//      Blist.push_back(mvs[moveIndex] & ~FLAG_BLACK);
3268//      Elist.push_back(mvs[moveIndex] & ~FLAG_BLACK);
3269//      if (moveIndex + 1 < mvs->size()) {
3270//        Blist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE));
3271//        Elist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE));
3272//      }
3273//      else Blist.push_back(MAXNOMOVES);
3274//    }
3275//    if (mvs[moveIndex] & FLAG_WHITE) {
3276//      d = d | FLAG_WHITE;
3277//      Wlist.push_back(mvs[moveIndex] & ~FLAG_WHITE);
3278//      Elist.push_back(mvs[moveIndex] & ~FLAG_WHITE);
3279//      if (moveIndex + 1 < mvs->size()) {
3280//        Wlist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE));
3281//        Elist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE));
3282//      }
3283//      else Wlist.append(MAXNOMOVES);
3284//    }
3285//    moveIndex += 2;
3286//  }
3287//         
3288//  if ((!Blist.size() || Blist[Blist.size()-1] != MAXNOMOVES) &&
3289//      (!Wlist.size() || Wlist[Wlist.size()-1] != MAXNOMOVES))
3290//    Elist.push_back(MAXNOMOVES);
3291//
3292//  moveIntsArr.push_back(Blist.size());
3293//  moveIntsArr.push_back(Wlist.size());
3294//  moveIntsArr.push_back(Elist.size());
3295//  moveIntsArr.extend(Blist);
3296//  moveIntsArr.extend(Wlist);
3297//  moveIntsArr.extend(Elist);
3298//
3299//  movesArr.push_back(d);
3300//       }
3301//     }
3302//   }
3303// }
3304//
3305// void Algo_intervals::finalize_process(datap) {
3306//   // FIXME
3307//  extract datap0, datap1 from datap
3308// 
3309//  String fn = datap0 + "/movesarr" + datap1 + ".db"; // FIXME: linux specific!?
3310//  ofstream file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc
3311//   file.write(movesArr, movesArrSize);
3312//   file.close();
3313// 
3314//  fn = datap0 + "/moveints" + datap1 + ".db"; // FIXME: linux specific!?
3315//  file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc
3316//   file.write(moveIntsArr, moveIntsArrSize);
3317//   file.close();
3318//         
3319// }       
3320//
3321//
3322// int Algo_intervals::retrieve_db(datap) {
3323//  String fn = ... "/movesarr" ...; // FIXME
3324//  ifstream file (fn, ios::in|ios::binary|ios::ate);
3325//  if (file.is_open()) {
3326//    ifstream::pos_type size = file.tellg();
3327//    delete [] movesArr;
3328//    movesArr = new char[size]; // FIXME: not a char array?
3329//    file.seekg (0, ios::beg);
3330//    file.read (memblock, size);
3331//    file.close();
3332//  }
3333//   else {
3334//    return 0;
3335//  }
3336//  String fn = ... "/moveints" ...; // FIXME
3337//  ifstream file (fn, ios::in|ios::binary|ios::ate);
3338//  if (file.is_open()) {
3339//    ifstream::pos_type size = file.tellg();
3340//    delete [] moveIntsArr;
3341//    moveIntsArr = new char[size]; // FIXME: not a char array?
3342//    file.seekg (0, ios::beg);
3343//    file.read (memblock, size);
3344//    file.close();
3345//  }
3346//   else {
3347//    return 0;
3348//  }
3349//   return 0;
3350// }
3351//
3352// void Algo_intervals::getUInterv(mves, vector<long> mves1, int gameno, int x, int y, char color) {
3353//
3354//   UIntervals UInterv();
3355//   int typeInterv = 0;
3356//   long d = mves[gameno*boardsize*boardsize + boardsize*x + y];
3357//
3358//   if (d & FLAG_POINTER) {
3359//         
3360//     if (color == 'X' && !(d & FLAG_BLACK)) return 0, UIntervals();
3361//     if (color == 'O' && !(d & FLAG_WHITE)) return 0, UIntervals();
3362//     
3363//    long p = d & MAXNOMOVES;
3364//    long lenB = moves1[p];
3365//    long lenW = moves1[p+1];
3366//    long lenE = moves1[p+2];
3367//    long start;
3368//    long length;
3369//
3370//    if (color == 'X') {
3371//      start = p + 3;
3372//      length = lenB;
3373//    }
3374//    else if (color == 'O') {
3375//      start = p + 3 + lenB;
3376//      length = lenW;
3377//    }
3378//    else if (color == '.') {
3379//      start = p + 3 + lenB + lenW;
3380//      length = lenE;
3381//    }
3382//
3383//    l = [];
3384//    for(int i=0; i<length/2; i++)
3385//      l.append((moves1[start+2*i], moves1[start+2*i+1]));
3386//
3387//    if (l[-1][1] == MAXNOMOVES) typeInterv = length-1;
3388//    else typeInterv = length;
3389//    return typeInterv, UIntervals(l);
3390//   }
3391//   else {
3392//     if (color == 'X' && (d & FLAG_BLACK))
3393//       return 1, UIntervals([( d & MAXNOMOVES , MAXNOMOVES)]);
3394//     else if (color == 'O' && (d & FLAG_WHITE))
3395//       return 1, UIntervals([( d & MAXNOMOVES , MAXNOMOVES)]);
3396//     else if (color == '.') {
3397//       if (!d) return -1, UIntervals([(0, MAXNOMOVES)]);
3398//       else return 1, UIntervals([(0, d & MAXNOMOVES)]);
3399//     }
3400//   }
3401//   return 0, UIntervals();
3402// }
3403// 
3404//
3405// void Algo_intervals::search(patternList, options, db,
3406//          continuations, contLabelsIndex, contLabels,
3407//          progBar, progStart, progEnd) {
3408//   int ctr = 0;
3409//   int numOfHits = 0;
3410//   int overallSwitched = 0;
3411//   int Bwins = 0;
3412//   int Wwins = 0;
3413//   int index = db.start();
3414//
3415//   if (!self.retrieve_db(db.datapath)) {
3416//     printf("Error!\n"); // FIXME
3417//     return;
3418//   }
3419//   
3420//   int movelimit = MAXNOMOVES;
3421//   if (options.has_key('movelimit')) movelimit = options['movelimit'];
3422//   
3423//   //  moves, moves1 = self.movesArr, self.moveIntsArr;
3424//
3425//   while (index != -1) {
3426//     ctr++;
3427//
3428//     matchList = db.getCurrentMatchlist();
3429//     result = [];
3430//     int numOfSwitched = 0;
3431//             
3432//     if (progBar && !(ctr % 10))
3433//       progBar.redraw((progEnd-progStart)*ctr/len(db.current) + progStart);
3434//             
3435//     for(m in matchList) {
3436//       Pattern p = patternList.get(m[0]);
3437//       a0, a1 = m[1];
3438//                 
3439//       UIntervals currentUInterv([(0, self.movelimit)]);
3440//
3441//       toDo = {};
3442//       cont = [(MAXNOMOVES, -1,-1)];
3443//       int i = 0;
3444//       int j = 0;
3445//
3446//       while (i < p.sizeX && !currentUInterv.isEmpty()) {
3447// 
3448//  if (p.data[i][j] == '*') {
3449//    Bint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1];
3450//    if (Bint.data) cont.extend([(x,i,j) for x in [z[0] for z in Bint.data]]);
3451//    Wint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1];
3452//    if (Wint.data) cont.extend([(x,i,j) for x in [z[0] for z in Wint.data]]);
3453//  }
3454//  else if p.data[i][j] == 'x': printf("oops\n"); // FIXME
3455//  else if p.data[i][j] == 'o': printf("oops\n"); // FIXME
3456//                         
3457//  else {
3458//    typeInt, nextInt = self.getUInterv(moves, moves1, index, i+a0, j+a1, p.data[i][j]);
3459//                         
3460//    if (typeInt == -1) ;
3461//    else if (typeInt == 0) currentUInterv = UIntervals();
3462//    else if (typeInt == 1) {
3463//      if (p.data[i][j] == '.' && cont[0][0] > nextInt.data[0][1]) {
3464//        Bi = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1];
3465//        Wi = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1];
3466//        counter = nextInt.data[0][1];
3467//        cont[0] = (nextInt.data[0][1], i, j);
3468//      }
3469//      currentUInterv.inters(nextInt);
3470//    }
3471//    else {
3472//      if (toDo.has_key(typeInt)) toDo[typeInt].append((i,j,nextInt));
3473//      else toDo[typeInt] = [(i, j, nextInt)];
3474//    }
3475//  }     
3476//  j++;
3477//  if (j == p.sizeY) {
3478//    j = 0;
3479//    i++;
3480//  }
3481//       }
3482//
3483//       toDoList = [];
3484//       for(ii in toDo.keys()) toDoList.extend(toDo[ii]);
3485//
3486//       while (toDoList && !currentUInterv.isEmpty()) {
3487//  i, j, nextInt = toDoList[0];
3488//  del toDoList[0];
3489//
3490//  currentUInterv.inters(nextInt);
3491//  if (currentUInterv.isEmpty()) break;
3492//                     
3493//  if (p.data[i][j] == 'X') Bint = nextInt;
3494//  else Bint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1];
3495//  if (Bint.data) cont.extend([(x,i,j) for x in [z[0] for z in Bint.data]]);
3496//  if (p.data[i][j] == 'O') Wint = nextInt;
3497//  else Wint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1];
3498//  if (Wint.data) cont.extend([(x,i,j) for x in [z[0] for z in Wint.data]]);
3499//       }
3500//       
3501//       if (!currentUInterv.isEmpty()) {
3502//
3503//  cont.sort();
3504//  for(counter, x, y in cont)
3505//    if (counter > currentUInterv.first()) break;
3506//
3507//  if (counter == MAXNOMOVES || counter <= currentUInterv.first()) {
3508//    hit = 1;
3509//    label = '';
3510//    switched = p.colorSwitch;
3511//  }
3512//  else {
3513//    Xint = (m[1][0], m[1][0] + patternList.get(m[0]).sizeX);
3514//    Yint = (m[1][1], m[1][1] + patternList.get(m[0]).sizeY);
3515//
3516//    Bint = self.getUInterv(moves, moves1, index, x+a0, y+a1, 'X')[1];
3517//    Wint = self.getUInterv(moves, moves1, index, x+a0, y+a1, 'O')[1];
3518//    if (counter in [z[0] for z in Bint.data]) co = 'W';   // !!! FIXME (cf. Algo_movelist.search)
3519//    else if (counter in [z[0] for z in Wint.data]) co = 'B'; // !!!
3520//    else raise Exception; // FIXME
3521//                         
3522//    hit, label, contLabelsIndex, switched =
3523//      patternList.updateContinuations(m[0], x+a0, y+a1, co, Xint, Yint,
3524//              currentUInterv.first(), counter-1,
3525//              continuations, contLabels, contLabelsIndex,
3526//              gl.getCurrentWinner());
3527//  }
3528// 
3529//  if (hit) {
3530//    numOfSwitched += switched;
3531//    if (switched) result.append(str(currentUInterv.first())+label+'-');
3532//    else result.append(str(currentUInterv.first())+label);
3533//  }
3534//       }
3535//     }
3536//
3537//     if (result) {
3538//       result.sort();
3539//       db.makeCurrentHit(join(result, ', '));
3540//       numOfHits = numOfHits + len(result);
3541//       overallSwitched += numOfSwitched;
3542//             
3543//       if (gl.getCurrentWinner() == 'B') {
3544//  Bwins = Bwins + len(result) - numOfSwitched;
3545//  Wwins = Wwins + numOfSwitched;
3546//       }
3547//       else if (gl.getCurrentWinner() == 'W') {
3548//  Bwins = Bwins + numOfSwitched;
3549//  Wwins = Wwins + len(result) - numOfSwitched;
3550//       }
3551//     }
3552//     else db.discardCurrent();
3553//       
3554//     index = db.next();
3555//   }
3556//   return numOfHits, Bwins, Wwins, overallSwitched;
3557// }
3558
3559
3560
3561
3562// ----------------------------------------------------------------------------------------------
3563
3564// GameList and related stuff
3565
3566Candidate::Candidate(char X, char Y, char ORIENTATION) {
3567  x = X;
3568  y = Y;
3569  orientation = ORIENTATION;
3570}
3571
3572Hit::Hit(ExtendedMoveNumber* POS, char* LABEL) { // LABEL is a char[3]
3573  pos = POS; // note that we do not copy these!
3574  label = LABEL;
3575}
3576
3577Hit::~Hit() {
3578  delete pos;
3579  delete [] label;
3580}
3581
3582Hit::Hit(SnapshotVector& snv) {
3583  int length = snv.retrieve_int();
3584  int* data = snv.retrieve_intp();
3585  pos = new ExtendedMoveNumber(length, data);
3586  delete [] data;
3587  label = snv.retrieve_charp();
3588}
3589
3590void Hit::to_snv(SnapshotVector& snv) {
3591  snv.pb_int(pos->length);
3592  snv.pb_intp(pos->data, pos->length);
3593  snv.pb_charp(label, 3);
3594}
3595
3596bool Hit::cmp_pts(Hit* a, Hit* b) {
3597  if (a->pos->length != b->pos->length) return a->pos->length < b->pos->length;
3598  for(int i=0; i < a->pos->length; i++)
3599    if (a->pos->data[i] != b->pos->data[i]) return a->pos->data[i] < b->pos->data[i];
3600  return false;
3601}
3602
3603SearchOptions::SearchOptions() {
3604  fixedColor = 0;
3605  moveLimit = 10000;
3606  nextMove = 0;
3607  trustHashFull = false;
3608  searchInVariations = true;
3609  algos = (1<<30) - 1; // use all available algorithms
3610}
3611
3612SearchOptions::SearchOptions(int FIXEDCOLOR, int NEXTMOVE, int MOVELIMIT) {
3613  fixedColor = FIXEDCOLOR;
3614  moveLimit = MOVELIMIT;
3615  nextMove = NEXTMOVE;
3616  trustHashFull = false;
3617  searchInVariations = true;
3618  algos = (1<<30) - 1; // use all available algorithms
3619}
3620
3621SearchOptions::SearchOptions(SnapshotVector& snv) {
3622  fixedColor = snv.retrieve_int();
3623  moveLimit = snv.retrieve_int();
3624  nextMove = snv.retrieve_int();
3625  trustHashFull = snv.retrieve_int();
3626  searchInVariations= snv.retrieve_int();
3627  algos = snv.retrieve_int();
3628}
3629
3630void SearchOptions::to_snv(SnapshotVector& snv) {
3631  snv.pb_int(fixedColor);
3632  snv.pb_int(moveLimit);
3633  snv.pb_int(nextMove);
3634  snv.pb_int(trustHashFull);
3635  snv.pb_int(searchInVariations);
3636  snv.pb_int(algos);
3637}
3638
3639ProcessOptions::ProcessOptions() {
3640  processVariations = true;
3641  sgfInDB = true;
3642  rootNodeTags = "BR,CA,DT,EV,HA,KM,PB,PC,PW,RE,RO,RU,SZ,US,WR";
3643  algos = ALGO_FINALPOS | ALGO_MOVELIST | ALGO_HASH_FULL | ALGO_HASH_CORNER;
3644  algo_hash_full_maxNumStones = 50;
3645  algo_hash_corner_maxNumStones = 20;
3646}
3647
3648ProcessOptions::ProcessOptions(string s) {
3649  int p = 0;
3650  if (s[p++] == 't') processVariations = true;
3651  else processVariations = false;
3652
3653  if (s[p++] == 't') sgfInDB = true;
3654  else sgfInDB = false;
3655
3656  p++;
3657  int pn = s.find('|', p) + 1;
3658  algos = atoi(s.substr(p, pn-p-1).c_str());
3659 
3660  p = pn;
3661  pn = s.find('|', p) + 1;
3662  algo_hash_full_maxNumStones = atoi(s.substr(p, pn-p-1).c_str());
3663 
3664  p = pn;
3665  pn = s.find('|', p) + 1;
3666  algo_hash_corner_maxNumStones = atoi(s.substr(p, pn-p-1).c_str());
3667 
3668  rootNodeTags = s.substr(pn);
3669}
3670
3671string ProcessOptions::asString() {
3672  string result;
3673  if (processVariations) result += "t";
3674  else result += "f";
3675  if (sgfInDB) result += "t";
3676  else result += "f";
3677  char buf[200];
3678  sprintf(buf, "|%d|%d|%d|%s", algos, algo_hash_full_maxNumStones, algo_hash_corner_maxNumStones, rootNodeTags.c_str());
3679  result += buf;
3680  return result;
3681}
3682
3683void ProcessOptions::validate() {
3684  string::iterator it = rootNodeTags.begin();
3685  while (it != rootNodeTags.end()) {
3686    if (*it == ' ') it = rootNodeTags.erase(it);
3687    else it++;
3688  }
3689  if (rootNodeTags.find("PB") == string::npos) rootNodeTags += ",PB";
3690  if (rootNodeTags.find("PW") == string::npos) rootNodeTags += ",PW";
3691  if (rootNodeTags.find("RE") == string::npos) rootNodeTags += ",RE";
3692  if (rootNodeTags.find("DT") == string::npos) rootNodeTags += ",DT";
3693
3694  algos |= ALGO_FINALPOS | ALGO_MOVELIST; // these are mandatory at the moment
3695}
3696
3697vector<string>* ProcessOptions::SGFTagsAsStrings() {
3698  vector<string>* SGFtags = new vector<string>;
3699  int ctr = 0;
3700  unsigned int p = 0;
3701  unsigned int pn = rootNodeTags.find(',', p);
3702  while (pn != string::npos) {
3703    SGFtags->push_back(rootNodeTags.substr(p,pn-p));
3704    ctr++;
3705    p = pn+1;
3706    pn = rootNodeTags.find(',', p);
3707  }
3708  SGFtags->push_back(rootNodeTags.substr(p));
3709  return SGFtags;
3710}
3711
3712GameListEntry::GameListEntry(int ID, char WINNER, string GAMEINFOSTR) {
3713  // printf("GLE %d %c %s\n", ID, WINNER, GAMEINFOSTR);
3714  id = ID;
3715  if (WINNER == 'B' || WINNER == 'b') winner = 'B';
3716  else if (WINNER == 'W' || WINNER == 'w') winner = 'W';
3717  else if (WINNER == 'J' || WINNER == 'j') winner = 'J';
3718  else winner = '-';
3719  gameInfoStr = GAMEINFOSTR;
3720  hits = 0;
3721  candidates = 0;
3722}
3723
3724GameListEntry::~GameListEntry() {
3725  if (hits) {
3726    for(vector<Hit* >::iterator it = hits->begin(); it != hits->end(); it++) delete *it;
3727    delete hits;
3728    hits = 0;
3729  }
3730  if (candidates) {
3731    for(vector<Candidate* >::iterator it = candidates->begin(); it != candidates->end(); it++) delete *it;
3732    delete candidates;
3733    candidates = 0;
3734  }
3735}
3736
3737void GameListEntry::hits_from_snv(SnapshotVector& snv) {
3738  int h_size = snv.retrieve_int();
3739  hits = new vector<Hit* >;
3740  for(int j=0; j<h_size; j++) {
3741    hits->push_back(new Hit(snv));
3742  }
3743}
3744
3745int insertEntry(void *gl, int argc, char **argv, char **azColName) {
3746  char winner = '-';
3747  if (argv[1] && (argv[1][0] == 'B' || argv[1][0] == 'W' || argv[1][0] == 'J')) winner = argv[1][0];
3748  string gameInfoStr = ((GameList*)gl)->format2;
3749  for(int i=0; i<((GameList*)gl)->numColumns; i++) {
3750    char strpip1[20];
3751    sprintf(strpip1, "[[%d[[F", i);
3752    unsigned int p = gameInfoStr.find(strpip1);
3753    if (p != string::npos) {
3754      if (argv[i]) {
3755        string fn = argv[i];
3756        if (fn.substr(fn.size()-4) == ".sgf" || fn.substr(fn.size()-4) == ".mgt") 
3757          gameInfoStr.replace(p, strlen(strpip1), fn.substr(0,fn.size()-4));
3758        else gameInfoStr.replace(p, strlen(strpip1), fn);
3759      } else gameInfoStr.erase(gameInfoStr.find(strpip1), strlen(strpip1));
3760      continue;
3761    }
3762
3763    sprintf(strpip1, "[[%d", i);
3764    p = gameInfoStr.find(strpip1);
3765    if (p != string::npos) {
3766      if (argv[i]) gameInfoStr.replace(p, strlen(strpip1), argv[i]);
3767      else gameInfoStr.erase(gameInfoStr.find(strpip1), strlen(strpip1));
3768    }
3769  }
3770  unsigned int p = gameInfoStr.find("[[W");
3771  if (p != string::npos) gameInfoStr.replace(p, 3, 1, winner);
3772
3773  // printf("id %s\n", argv[0]);
3774  ((GameList*)gl)->all->push_back(new GameListEntry(atoi(argv[0]), winner, gameInfoStr));
3775  return 0;
3776}
3777
3778int dbinfo_callback(void *s, int argc, char **argv, char **asColName) {
3779  char** cpp = (char**)s;
3780  if (argc && argv[0]) {
3781    // printf("dbi_cb %s\n", argv[0]);
3782    *cpp = new char[strlen(argv[0])+1];
3783    strcpy(*cpp, argv[0]);
3784  }
3785  return 0;
3786}
3787
3788GameList::GameList(char* DBNAME, string ORDERBY, string FORMAT, ProcessOptions* p_options, int cache) throw(DBError) {
3789  duplicates = 0;
3790  labels = 0;
3791  continuations = 0;
3792  mrs_pattern = 0;
3793  searchOptions = 0;
3794  dbname = new char[strlen(DBNAME)+2];
3795  strcpy(dbname, DBNAME);
3796  db = algo_db1 = algo_db2 = 0;
3797
3798  dbname[strlen(DBNAME)] = '1';
3799  dbname[strlen(DBNAME)+1] = 0;
3800  int rc = sqlite3_open(dbname, &algo_db1); 
3801  if (rc) {
3802    sqlite3_close(algo_db1);
3803    algo_db1 = 0;
3804    throw DBError();
3805  }
3806  rc = sqlite3_busy_timeout(algo_db1, 200);
3807  if (rc) throw DBError();
3808  rc = sqlite3_exec(algo_db1, "pragma synchronous = off;", 0, 0, 0);
3809  if (rc) throw DBError();
3810  char cache_str[100];
3811  sprintf(cache_str, "pragma cache_size = %d", cache*1000);
3812  rc = sqlite3_exec(algo_db1, cache_str, 0, 0, 0);
3813  if (rc) throw DBError();
3814  dbname[strlen(DBNAME)] = '2';
3815  dbname[strlen(DBNAME)+1] = 0;
3816  rc = sqlite3_open(dbname, &algo_db2); 
3817  if (rc) {
3818    sqlite3_close(algo_db2);
3819    algo_db2 = 0;
3820    throw DBError();
3821  }
3822  rc = sqlite3_busy_timeout(algo_db2, 200);
3823  if (rc) throw DBError();
3824  rc = sqlite3_exec(algo_db2, "pragma synchronous = off;", 0, 0, 0);
3825  if (rc) throw DBError();
3826  sprintf(cache_str, "pragma cache_size = %d", cache*7000);
3827  rc = sqlite3_exec(algo_db2, cache_str, 0, 0, 0);
3828  if (rc) throw DBError();
3829
3830  // try to retrieve basic options from database
3831  dbname[strlen(DBNAME)] = 0;
3832  rc = sqlite3_open(dbname, &db); 
3833  if (rc) {
3834    sqlite3_close(db);
3835    db = 0;
3836    throw DBError();
3837  }
3838  rc = sqlite3_busy_timeout(db, 200);
3839  if (rc) throw DBError();
3840  rc = sqlite3_exec(db, "pragma synchronous = off;", 0, 0, 0);
3841  if (rc) throw DBError();
3842  sprintf(cache_str, "pragma cache_size = %d", cache*1000);
3843  rc = sqlite3_exec(db, cache_str, 0, 0, 0);
3844  if (rc) throw DBError();
3845
3846  rc = sqlite3_exec(db, "create table if not exists db_info ( info text );", 0, 0, 0);
3847  if (rc != SQLITE_OK) throw DBError();
3848  char* dbinfo = 0;
3849  rc = sqlite3_exec(db, "select * from db_info where rowid = 1;", dbinfo_callback, &dbinfo, 0);
3850  if (rc != SQLITE_OK) throw DBError();
3851
3852  if (dbinfo) {
3853    // printf("dbinfo: %s\n", dbinfo);
3854    p_op = new ProcessOptions(dbinfo);
3855    delete [] dbinfo;
3856    char* bsizes = 0;
3857    rc = sqlite3_exec(db, "select * from db_info where rowid = 2;", dbinfo_callback, &bsizes, 0);
3858    if (rc != SQLITE_OK) throw DBError();
3859    if (bsizes) {
3860      // printf("board sizes %s\n", bsizes); // should be a comma-sep. list of integers *ending w/ a comma*
3861      string bsizes_str(bsizes);
3862      delete [] bsizes;
3863      unsigned int p = 0;
3864      unsigned int pn = bsizes_str.find(",",p);
3865      while (pn > p && pn != string::npos) {
3866        boardsizes.push_back(atoi(bsizes_str.substr(p, pn-p).c_str()));
3867        p = pn+1;
3868        pn = bsizes_str.find(",",p);
3869      }
3870    }
3871  } else { // if this does not work: create database and read p_options (or use defaults)
3872    // printf("retrieving dbinfo failed\n");
3873    if (p_options == 0) p_op = new ProcessOptions(); // use default values
3874    else {
3875      // printf("use p_options\n");
3876      p_op = new ProcessOptions(*p_options);
3877      p_op->validate(); // make sure the most important information is contained in rootNodeTags list
3878    }
3879    string sql = "insert into db_info (rowid,info) values (1,'";
3880    sql += p_op->asString();
3881    sql += "');";
3882    rc = sqlite3_exec(db, sql.c_str(), 0, 0, 0);
3883    if (rc != SQLITE_OK) throw DBError();
3884    rc = sqlite3_exec(db, "insert into db_info (rowid, info) values (2, ',');", 0, 0, 0);
3885    if (rc != SQLITE_OK) throw DBError();
3886  }
3887
3888  // set up snapshot db
3889  rc = sqlite3_exec(db, "create table if not exists snapshots ( data text );", 0, 0, 0);
3890  if (rc != SQLITE_OK) throw DBError();
3891
3892  // printf("set up Algorithm instances\n");
3893  for(vector<int>::iterator it = boardsizes.begin(); it != boardsizes.end(); it++)
3894    addAlgos(*it);
3895  all = 0;
3896  currentList = oldList = 0;
3897  readDBs = 0;
3898  resetFormat(ORDERBY, FORMAT);
3899}
3900
3901void GameList::resetFormat(string ORDERBY, string FORMAT) {
3902  // printf("enter resetFormat\n");
3903  if (FORMAT == "") { // use default format string
3904    numColumns = 5;
3905    format1 = "id,re,pw,pb,dt";
3906    format2 = "[[2 - [[3 ([[W), [[4, ";
3907  } else {
3908    char buf[10];
3909    numColumns = 2;
3910    format1 = "id,re";
3911    format2 = FORMAT;
3912    unsigned int p = 0;
3913    unsigned int q = 0;
3914    while (p != string::npos) {
3915      p = format2.find("[[",p);
3916      q = format2.find("]]",p);
3917      if (p+2 < format2.size() && q != string::npos) {
3918        string col = format2.substr(p+2, q-p-2);
3919        // check availability
3920        if (col == "id" || col == "filename" || col == "pos" || col == "duplicate" || col == "date" || p_op->rootNodeTags.find(col) != string::npos) {
3921          sprintf(buf, "[[%d", numColumns++); 
3922          format2.replace(p,q+2-p, buf);
3923          format1 += ",";
3924          format1 += col;
3925        } else if (col == "winner") format2.replace(p,q+2-p, "[[W");
3926        else if (col == "filename.") {
3927          sprintf(buf, "[[%d[[F", numColumns++); 
3928          format2.replace(p, q+2-p, buf);
3929          format1 += ",filename";
3930        }
3931        p++;
3932      } else break;
3933    }
3934  }
3935  if (ORDERBY == "" || ORDERBY == "id" || ORDERBY == "ID" || ORDERBY == "Id" || ORDERBY == "iD") orderby = "id";
3936  else orderby = ORDERBY + ",id";
3937  // printf("finished parsing\n");
3938
3939  readDB();
3940}
3941
3942
3943void GameList::addAlgos(int bs) {
3944  int ctr = algo_ps.size()/20;
3945  // printf("add algos %d %d %d\n", bs, ctr, p_op->algos);
3946  for(int i=0; i<20; i++) {
3947    algo_ps.push_back(0);
3948    algo_dbs.push_back(0);
3949  }
3950
3951  algo_ps[20*ctr] = new Algo_signature(bs);
3952  algo_dbs[20*ctr] = db;
3953  if (p_op->algos & ALGO_FINALPOS) {
3954    algo_ps[algo_finalpos+20*ctr] = new Algo_finalpos(bs);
3955    algo_dbs[algo_finalpos+20*ctr] = algo_db1;
3956  }
3957  if (p_op->algos & ALGO_MOVELIST) {
3958    algo_ps[algo_movelist+20*ctr] = new Algo_movelist(bs);
3959    algo_dbs[algo_movelist+20*ctr] = algo_db1;
3960  }
3961  if (p_op->algos & ALGO_HASH_FULL) {
3962    algo_ps[algo_hash_full+20*ctr] = new Algo_hash_full(bs, p_op->algo_hash_corner_maxNumStones);
3963    algo_dbs[algo_hash_full+20*ctr] = algo_db2;
3964  }
3965  if (p_op->algos & ALGO_HASH_CORNER) {
3966    algo_ps[algo_hash_corner+20*ctr] = new Algo_hash_corner(bs, 7, p_op->algo_hash_corner_maxNumStones);
3967    algo_dbs[algo_hash_corner+20*ctr] = algo_db2;
3968  }
3969  // for(int a=20*ctr; a<20*(ctr+1); a++) printf("aa %d %p\n", a, algo_ps[a]);
3970  // if (algos & ALGO_HASH_SIDE)
3971  //   algo_ps[algo_hash_side] = new Algo_hash_side(boardsize, 6, 4, p_op->algo_hash_side_maxNumStones);
3972}
3973
3974void GameList::readDB() throw(DBError) {
3975  // printf("read dbs\n");
3976  if (oldList) delete oldList;
3977  if (currentList) delete currentList;
3978  if (all) {
3979    for(vector<GameListEntry* >::iterator it = all->begin(); it != all->end(); it++)
3980      delete *it;
3981    delete all;
3982  }
3983  current = -1;
3984  all = new vector<GameListEntry* >;
3985  currentList = 0;
3986  oldList = 0;
3987
3988  int rc;
3989  rc = sqlite3_exec(db, "begin transaction;", 0, 0, 0);
3990  if (rc) throw DBError();
3991
3992  string sql = "select ";
3993  sql += format1;
3994  sql += " from games order by ";
3995  sql += orderby;
3996  // printf("sql: %s\n", sql.c_str());
3997  rc = sqlite3_exec(db, sql.c_str(), insertEntry, this, 0);
3998  if (rc != SQLITE_OK && rc != SQLITE_ERROR) {
3999    throw DBError(); 
4000  }
4001  // printf("read.\n");
4002  // SQLITE_ERROR may occur since table might not yet exist
4003
4004  readPlayersList();
4005  rc = sqlite3_exec(db, "commit;", 0, 0, 0);
4006  if (rc != SQLITE_OK) throw DBError();
4007
4008  if (rc == SQLITE_OK && !readDBs) {
4009    for(unsigned int a=0; a < 20*boardsizes.size(); a++) {
4010      if (algo_ps[a]) algo_ps[a]->readDB(algo_dbs[a]);
4011    }
4012    readDBs = 1;
4013  }
4014  // printf("read.\n");
4015
4016  reset();
4017  // printf("leave readDB\n");
4018}
4019
4020GameList::~GameList() {
4021  // printf("enter ~GameList\n");
4022  if (mrs_pattern) delete mrs_pattern;
4023  if (searchOptions) delete searchOptions;
4024  if (p_op) delete p_op;
4025  if (labels) delete [] labels;
4026  if (continuations) delete [] continuations; // FIXME CHECK whether the Continuation destructor is invoked!
4027  if (duplicates) delete duplicates;
4028  delete [] dbname;
4029  if (all) {
4030    for(vector<GameListEntry* >::iterator it = all->begin(); it != all->end(); it++)
4031      delete *it;
4032    delete all;
4033  }
4034  if (currentList) delete currentList;
4035  if (oldList) delete oldList;
4036  for(unsigned int i=0; i<20*boardsizes.size(); i++) 
4037    if (algo_ps[i]) delete algo_ps[i];
4038  if (db) sqlite3_close(db);
4039  db = 0;
4040  if (algo_db1) sqlite3_close(algo_db1);
4041  algo_db1 = 0;
4042  if (algo_db2) sqlite3_close(algo_db2);
4043  algo_db2 = 0;
4044  // printf("leave ~GameList\n");
4045}
4046
4047
4048int GameList::start() {
4049  current = 0;
4050  if (oldList) delete oldList;
4051  oldList = currentList;
4052  currentList = new vector<pair<int,int> >;
4053  if (oldList && oldList->size()) return (*oldList)[0].first;
4054  else {
4055    if (oldList) delete oldList;
4056    oldList = 0;
4057    return -1;
4058  }
4059}
4060
4061int GameList::next() {
4062  current++;
4063  if (current < (int)oldList->size()) return (*oldList)[current].first;
4064  else {
4065    if (oldList) delete oldList;
4066    oldList = 0;
4067    return -1;
4068  }
4069}
4070
4071bool sndcomp(const pair<int,int>& a, const pair<int,int>& b) {
4072  return a.second < b.second;
4073}
4074
4075int GameList::start_sorted() {
4076  current = 0;
4077  if (oldList) delete oldList;
4078  oldList = currentList;
4079  currentList = new vector<pair<int,int> >;
4080  if (!oldList || !oldList->size()) {
4081    if (oldList) delete oldList;
4082    oldList = 0;
4083    return -1;
4084  }
4085  sort(oldList->begin(), oldList->end());
4086  return 0;
4087}
4088
4089int GameList::end_sorted() {
4090  // printf("end sorted\n");
4091  sort(currentList->begin(), currentList->end(), sndcomp);
4092  delete oldList;
4093  oldList = 0;
4094  return 0;
4095}
4096
4097char GameList::getCurrentWinner() {
4098  return (*all)[(*oldList)[current].second]->winner;
4099}
4100
4101vector<Candidate* > * GameList::getCurrentCandidateList() {
4102  return (*all)[(*oldList)[current].second]->candidates;
4103}
4104
4105void GameList::makeCurrentCandidate(vector<Candidate* > * candidates) {
4106  GameListEntry* gle = (*all)[(*oldList)[current].second];
4107  if (gle->candidates) delete gle->candidates;
4108  gle->candidates = candidates;
4109  currentList->push_back((*oldList)[current]);
4110}
4111
4112void GameList::makeCurrentHit(vector<Hit* > * hits) {
4113  GameListEntry* gle = (*all)[(*oldList)[current].second];
4114  if (gle->hits) delete gle->hits;
4115  gle->hits = hits;
4116  sort(gle->hits->begin(), gle->hits->end(), Hit::cmp_pts);
4117  currentList->push_back((*oldList)[current]);
4118}
4119
4120void GameList::setCurrentFromIndex(int index) {
4121  int start = current;
4122  int end = oldList->size();
4123  int m = start;
4124  while (start < end) {
4125    m = (end+start)/2;
4126    if (index == (*oldList)[m].first) {
4127      break;
4128    } else {
4129      if (index < (*oldList)[m].first) end = m;
4130      else start = m+1;
4131    }
4132  }
4133  current = m;
4134}
4135
4136void GameList::makeIndexHit(int index, vector<Hit* > * hits) {
4137  int m = get_current_index(index, &current);
4138  if (m != -1) {
4139    currentList->push_back((*oldList)[m]);
4140    if (hits) {
4141      if ((*all)[(*oldList)[m].second]->hits) delete (*all)[(*oldList)[m].second]->hits;
4142      (*all)[(*oldList)[m].second]->hits = hits;
4143    }
4144  }
4145}
4146
4147void GameList::makeIndexCandidate(int index, vector<Candidate* > * candidates) {
4148  int m = get_current_index(index, &current);
4149  if (m != -1) {
4150    currentList->push_back((*oldList)[m]);
4151    if (candidates) {
4152      if ((*all)[(*oldList)[m].second]->candidates) delete (*all)[(*oldList)[m].second]->candidates;
4153      (*all)[(*oldList)[m].second]->candidates = candidates;
4154    }
4155  }
4156}
4157
4158
4159void GameList::reset() {
4160  if (oldList) delete oldList;
4161  oldList = 0;
4162  if (currentList) delete currentList;
4163  currentList = new vector<pair<int,int> >;
4164  int counter = 0;
4165  for(vector<GameListEntry* >::iterator it = all->begin(); it != all->end(); it++) {
4166    if ((*it)->hits) {
4167      for(vector<Hit* >::iterator ith = (*it)->hits->begin(); ith != (*it)->hits->end(); ith++)
4168        delete *ith;
4169      delete (*it)->hits;
4170      (*it)->hits = 0;
4171    }
4172    if ((*it)->candidates) {
4173      for(vector<Candidate* >::iterator itc = (*it)->candidates->begin(); itc != (*it)->candidates->end(); itc++)
4174        delete *itc;
4175      delete (*it)->candidates;
4176      (*it)->candidates = 0;
4177    }
4178    currentList->push_back(make_pair((*it)->id, counter++));
4179  }
4180  num_hits = 0;
4181  num_switched = 0;
4182  Bwins = 0;
4183  Wwins = 0;
4184}
4185
4186void GameList::tagsearch(int tag) throw(DBError) {
4187  char sql[200];
4188
4189  if (!tag) return;
4190  if (tag > 0) {
4191    sprintf(sql, "select games.id from games join game_tags on games.id = game_tags.game_id where game_tags.tag_id = %d order by games.id", tag);
4192  } else {
4193    sprintf(sql, "select games.id from games except select games.id from games join game_tags on games.id = game_tags.game_id where game_tags.tag_id = %d order by games.id;", -tag);
4194  }
4195  gisearch(sql, 1);
4196}
4197
4198void GameList::setTag(int tag, int start, int end) throw(DBError) {
4199  if (end==0) end = currentList->size();
4200  if (start>end || end > (int)currentList->size()) return;
4201  int rc = sqlite3_exec(db, "begin transaction", 0, 0, 0);
4202  if (rc != SQLITE_OK) throw DBError();
4203  for(int i = start; i < end; i++) {
4204    if (getTags(i, tag).size()) continue;
4205    char sql[200];
4206    sprintf(sql, "insert into game_tags (game_id, tag_id) values (%d, %d)", (*all)[(*currentList)[i].second]->id, tag);
4207    rc = sqlite3_exec(db, sql, 0, 0, 0);
4208    if (rc != SQLITE_OK) throw DBError();
4209  }
4210  rc = sqlite3_exec(db, "commit", 0, 0, 0);
4211  if (rc != SQLITE_OK) throw DBError();
4212}
4213
4214void GameList::deleteTag(int tag, int i) throw(DBError) {
4215  char sql[200];
4216  if (i == -1) sprintf(sql, "delete from game_tags where tag_id=%d", tag);
4217  else sprintf(sql, "delete from game_tags where game_id=%d and tag_id=%d", (*all)[(*currentList)[i].second]->id, tag);
4218  int rc = sqlite3_exec(db, sql, 0, 0, 0);
4219  if (rc != SQLITE_OK) throw DBError();
4220}
4221
4222int gettags_callback(void *res, int argc, char **argv, char **azColName) {
4223  if (!argc) return 1;
4224  ((vector<int>*)res)->push_back(atoi(argv[0]));
4225  return 0;
4226}
4227
4228vector<int> GameList::getTags(int i, int tag) throw(DBError) {
4229  vector<int> result;
4230  char sql[200];
4231  if (tag==0) sprintf(sql, "select tag_id from game_tags where game_id=%d", (*all)[(*currentList)[i].second]->id);
4232  else sprintf(sql, "select tag_id from game_tags where game_id=%d and tag_id=%d", (*all)[(*currentList)[i].second]->id, tag);
4233  int rc = sqlite3_exec(db, sql, gettags_callback, &result, 0);
4234  if (rc != SQLITE_OK) throw DBError();
4235  return result;
4236}
4237
4238void GameList::insert_duplicate(int i1, int i2, vector<vector<int> >* dupl) {
4239  int ii1 = get_current_index_CL(i1);
4240  int ii2 = get_current_index_CL(i2);
4241  // printf("insert_duplicate %d, %d\n", ii1, ii2);
4242  if (ii1 == -1 || ii2 == -1) return;
4243  bool inserted = false;
4244  for(vector<vector<int> >::iterator it = dupl->begin(); it != dupl->end(); it++) {
4245    vector<int>::iterator i = it->begin();
4246    while(i != it->end() && *i != ii1 && *i != ii2) i++;
4247    if (i == it->end()) continue;
4248    int insert = ii1;
4249    if (*i == ii1) insert = ii2;
4250    while (i != it->end() && *i != insert) i++;
4251    if (i == it->end()) it->push_back(insert);
4252    sort(it->begin(), it->end());
4253    inserted = true;
4254    break;
4255  }
4256  if (!inserted) {
4257    vector<int> new_list;
4258    if (ii1 < ii2) {
4259      new_list.push_back(ii1);
4260      new_list.push_back(ii2);
4261    } else {
4262      new_list.push_back(ii2);
4263      new_list.push_back(ii1);
4264    }
4265    dupl->push_back(new_list);
4266  }
4267}
4268
4269int GameList::find_duplicates(int bs, bool strict) throw(DBError) {
4270  if (!currentList->size()) return 0; // this also deals with the case of an empty db
4271  int bs_index = 0;
4272  if (duplicates) delete duplicates;
4273  duplicates = new vector<vector<int> >;
4274  if (strict) {
4275    vector<int>::iterator it = boardsizes.begin();
4276    while (it != boardsizes.end() && *it != bs) {
4277      bs_index++;
4278      it++;
4279    }
4280    if (it == boardsizes.end()) {
4281      return 0;
4282    }
4283  }
4284  sort(currentList->begin(), currentList->end());
4285  sqlite3_stmt *ppStmt=0;
4286  char sql[200];
4287  sprintf(sql, "select as1.id,as2.id from algo_signature_%d as1 join algo_signature_%d as2 on as1.signature = as2.signature where as1.id < as2.id;", bs, bs);
4288  int rc = sqlite3_prepare(db, sql, -1, &ppStmt, 0);
4289  if (rc != SQLITE_OK || ppStmt==0) throw DBError();
4290  do {
4291    rc = sqlite3_step(ppStmt);
4292    if (rc != SQLITE_DONE && rc != SQLITE_ROW) throw DBError();
4293    if (rc == SQLITE_ROW) {
4294      if (!strict || ((Algo_finalpos*)algo_ps[20*bs_index+algo_finalpos])->equal(sqlite3_column_int(ppStmt, 0), sqlite3_column_int(ppStmt, 1)))
4295        insert_duplicate(sqlite3_column_int(ppStmt, 0), sqlite3_column_int(ppStmt, 1), duplicates);
4296    }
4297  } while (rc == SQLITE_ROW);
4298  rc = sqlite3_finalize(ppStmt);
4299  if (rc != SQLITE_OK) throw DBError();
4300  sort(currentList->begin(), currentList->end(), sndcomp);
4301  return duplicates->size();
4302}
4303
4304vector<int> GameList::retrieve_duplicates_VI(unsigned int i) {
4305  if (i>=duplicates->size()) return vector<int>();
4306  return (*duplicates)[i];
4307}
4308
4309int* GameList::retrieve_duplicates_PI(unsigned int i) {
4310  if (i>=duplicates->size()) return 0;
4311  int* result = new int[(*duplicates)[i].size()+1];
4312  int j = 0;
4313  for(vector<int>::iterator it = (*duplicates)[i].begin(); it != (*duplicates)[i].end(); it++)
4314    result[j++] = *it;
4315  result[(*duplicates)[i].size()] = -1;
4316  return result;
4317}
4318
4319
4320int GameList::get_current_index(int id, int* start) {
4321  // use this in between start_sorted() and end_sorted() only!
4322  int end = oldList->size();
4323  int m = *start;
4324  while (*start < end) {
4325    m = (end+*start)/2;
4326    if (id == (*oldList)[m].first) {
4327      *start = m;
4328      return m;
4329    } else {
4330      if (id < (*oldList)[m].first) end = m;
4331      else *start = m+1;
4332    }
4333  }
4334  return -1; 
4335}
4336
4337int GameList::get_current_index_CL(int id, int start) {
4338  // use this in between start_sorted() and end_sorted() only!
4339  int end = currentList->size();
4340  int m = start;
4341  while (start < end) {
4342    m = (end+start)/2;
4343    if (id == (*currentList)[m].first) return m;
4344    else {
4345      if (id < (*currentList)[m].first) end = m;
4346      else start = m+1;
4347    }
4348  }
4349  return -1; 
4350}
4351
4352void GameList::sigsearch(char* sig, int boardsize) throw(DBError) {
4353  if (start_sorted() == 0) { 
4354    char* symmetrized_sig = 0;
4355    if (boardsize) symmetrized_sig = symmetrize(sig, boardsize);
4356    // char ssig[13];
4357    // for(int i=0; i<12; i++) ssig[i] = symmetrized_sig[i];
4358    // ssig[12] = 0;
4359    // printf("ssig: %s\n", ssig);
4360    string query = "select id from algo_signature_19 where signature like ? order by id";
4361    // int rc = sqlite3_exec(db, query.c_str(), sigs_callback, this, 0);
4362    sqlite3_stmt *ppStmt=0;
4363    int rc = sqlite3_prepare(db, query.c_str(), -1, &ppStmt, 0);
4364    if (rc != SQLITE_OK || ppStmt==0) throw DBError();
4365    if (boardsize) rc = sqlite3_bind_blob(ppStmt, 1, symmetrized_sig, 12, SQLITE_TRANSIENT);
4366    else rc = sqlite3_bind_blob(ppStmt, 1, sig, 12, SQLITE_TRANSIENT);
4367    if (rc != SQLITE_OK || ppStmt==0) throw DBError();
4368    do {
4369      rc = sqlite3_step(ppStmt);
4370      if (rc != SQLITE_DONE && rc != SQLITE_ROW) throw DBError();
4371      if (rc == SQLITE_ROW) {
4372        makeIndexHit(sqlite3_column_int(ppStmt, 0), 0);
4373      }
4374    } while (rc == SQLITE_ROW);
4375    rc = sqlite3_finalize(ppStmt);
4376    if (symmetrized_sig) delete [] symmetrized_sig;
4377    if (rc != SQLITE_OK) throw DBError();
4378
4379    end_sorted();
4380  }
4381}
4382
4383int gis_callback(void *gl, int argc, char **argv, char **azColName) {
4384  if (!argc) return 1;
4385  ((GameList*)gl)->makeIndexHit(atoi(argv[0]), 0);
4386  return 0;
4387}
4388
4389void GameList::gisearch(char* sql, int complete) throw(DBError) {
4390  if (start_sorted() == 0) { 
4391    string query;
4392    if (!complete) query = "select id from games where ";
4393    query += sql;
4394    if (!complete) query += " order by id";
4395    // printf("%s\n", query.c_str());
4396    int rc = sqlite3_exec(db, query.c_str(), gis_callback, this, 0);
4397    if( rc!=SQLITE_OK ) throw DBError();
4398
4399    end_sorted();
4400  }
4401}
4402
4403int GameList::numHits() {
4404  return num_hits;
4405}
4406
4407int GameList::size() {
4408  return currentList->size();
4409}
4410
4411string GameList::resultsStr(GameListEntry* gle) {
4412  string result;
4413  if (!gle->hits) return result;
4414  char buf[20];
4415  result.reserve(gle->hits->size()*8);
4416  for(vector<Hit* >::iterator it = gle->hits->begin(); it != gle->hits->end(); it++) {
4417    sprintf(buf, "%d", (*it)->pos->data[0]);
4418    result += buf;
4419    for(int i=1; i<(*it)->pos->length; i++) {
4420      sprintf(buf, "-%d", (*it)->pos->data[i]);
4421      result += buf;
4422    }
4423    if ((*it)->label[0] != NO_CONT) result += lookupLabel((*it)->label[0], (*it)->label[1]); // coordinates of Hit
4424    if ((*it)->label[2]) result += "-, ";
4425    else result += ", ";
4426  }
4427  return result;
4428}
4429
4430char GameList::lookupLabel(char x, char y) {
4431  if (!labels || !mrs_pattern || x < 0 || x >= mrs_pattern->sizeX || y < 0 || y >= mrs_pattern->sizeY) return '?';
4432  return labels[x+y*mrs_pattern->sizeX];
4433}
4434
4435Continuation GameList::lookupContinuation(char x, char y) {
4436  if (!continuations || !mrs_pattern || x < 0 || x >= mrs_pattern->sizeX || y < 0 || y >= mrs_pattern->sizeY) return Continuation();
4437  return continuations[x+y*mrs_pattern->sizeX];
4438}
4439
4440vector<string> GameList::currentEntriesAsStrings(int start, int end) {
4441  if (end==0) end = currentList->size();
4442  vector<string> result;
4443  if (start>end || end > (int)currentList->size()) return result;
4444  for(int i=start; i<end; i++) {
4445    result.push_back((*all)[(*currentList)[i].second]->gameInfoStr + resultsStr((*all)[(*currentList)[i].second]));
4446  }
4447  return result;
4448}
4449
4450string GameList::currentEntryAsString(int i) {
4451  if (i < 0 || i >= (int)currentList->size()) {
4452    return "";
4453  } else return (*all)[(*currentList)[i].second]->gameInfoStr + resultsStr((*all)[(*currentList)[i].second]);
4454}
4455
4456int getpropcallback(void *s, int argc, char **argv, char **azColName) {
4457  char** prop = (char**)s;
4458  if (argc && argv[0]) {
4459    *prop = new char[strlen(argv[0])+1];
4460    strcpy(*prop, argv[0]);
4461  }
4462  return 0;
4463}
4464
4465string GameList::getSignature(int i) throw(DBError) {
4466  if (i < 0 || i >= (int)currentList->size()) {
4467    // printf("index out of range\n");
4468    return "";
4469  }
4470  int index = (*all)[(*currentList)[i].second]->id;
4471  char* prop = 0;
4472  char sql[200];
4473  sprintf(sql, "select signature from algo_signature_19 where id = %d;", index);
4474  // printf("%s\n", sql);
4475  int rc = sqlite3_exec(db, sql, getpropcallback, &prop, 0);
4476  if (rc != SQLITE_OK) throw DBError();
4477
4478  if (!prop) return "";
4479  string prop_str(prop);
4480  delete [] prop;
4481  return prop_str;
4482}
4483
4484string GameList::getSGF(int i) throw(DBError) {
4485  if (!p_op->sgfInDB) return "";
4486  return getCurrentProperty(i, "sgf");
4487}
4488
4489string GameList::getCurrentProperty(int i, string tag) throw(DBError) {
4490  if (i < 0 || i >= (int)currentList->size()) {
4491    // printf("index out of range\n");
4492    return "";
4493  }
4494  int index = (*all)[(*currentList)[i].second]->id;
4495  char* prop = 0;
4496  char sql[200];
4497  sprintf(sql, "select %s from games where id = %d;", tag.c_str(), index);
4498  // printf("%s\n", sql);
4499  int rc = sqlite3_exec(db, sql, getpropcallback, &prop, 0);
4500  if (rc != SQLITE_OK) throw DBError();
4501
4502  if (!prop) return "";
4503  string prop_str(prop);
4504  delete [] prop;
4505  return prop_str;
4506}
4507
4508void GameList::search(Pattern& pattern, SearchOptions* so) throw(DBError) {
4509  if (mrs_pattern) delete mrs_pattern;
4510  mrs_pattern = new Pattern(pattern);
4511  if (searchOptions) delete searchOptions;
4512  if (so) searchOptions = new SearchOptions(*so);
4513  else searchOptions = new SearchOptions();
4514  PatternList pl(pattern, searchOptions->fixedColor, searchOptions->nextMove);
4515
4516  vector<int>::iterator it = boardsizes.begin();
4517  int bs_index = 0;
4518  while (it != boardsizes.end() && *it != pattern.boardsize) {
4519    bs_index++;
4520    it++;
4521  }
4522  if (it == boardsizes.end()) {
4523    delete searchOptions;
4524    searchOptions = 0;
4525    if (oldList) delete oldList;
4526    oldList = 0;
4527    if (currentList) delete currentList;
4528    currentList = new vector<pair<int,int> >;
4529    return;
4530  }
4531
4532  if (boardsizes.size() != 1) {
4533    char buf[20];
4534    sprintf(buf, "sz = %d", pattern.boardsize);
4535    gisearch(buf);
4536  }
4537  if (!readDBs) {
4538    for(unsigned int a=0; a < 20*boardsizes.size(); a++) if (algo_ps[a]) algo_ps[a]->readDB(algo_dbs[a]);
4539    readDBs = 1;
4540  }
4541
4542  int hash_result = -1;
4543  // FULL BOARD PATTERN?
4544  if ((searchOptions->algos & ALGO_HASH_FULL) && pattern.sizeX == pattern.boardsize && pattern.sizeY == pattern.boardsize && algo_ps[algo_hash_full+20*bs_index]) {
4545    hash_result = ((Algo_hash_full*)algo_ps[algo_hash_full+20*bs_index])->search(pl, *this, *searchOptions, algo_dbs[algo_hash_full+20*bs_index]);
4546    if (hash_result == 1) {
4547    } else if (hash_result == 0) {
4548      if (searchOptions->algos & ALGO_MOVELIST && algo_ps[algo_movelist+20*bs_index])
4549        algo_ps[algo_movelist+20*bs_index]->search(pl, *this, *searchOptions);
4550    }
4551  }
4552  if (hash_result == -1) { // not a full board pattern (or not hashable)
4553
4554    // CORNER PATTERN?
4555    if ((searchOptions->algos & ALGO_HASH_CORNER) && pattern.sizeX >= 7 && pattern.sizeY >= 7 && algo_ps[algo_hash_corner+20*bs_index]) {
4556      hash_result = ((Algo_hash_corner*)algo_ps[algo_hash_corner+20*bs_index])->search(pl, *this, *searchOptions, algo_dbs[algo_hash_corner+20*bs_index]);
4557      if (hash_result == 0) {
4558        if (searchOptions->algos & ALGO_MOVELIST && algo_ps[algo_movelist+20*bs_index])
4559          algo_ps[algo_movelist+20*bs_index]->search(pl, *this, *searchOptions);
4560      }
4561    }
4562
4563    if (hash_result == -1) {
4564      if (searchOptions->algos & ALGO_FINALPOS && algo_ps[algo_finalpos+20*bs_index])
4565        algo_ps[algo_finalpos+20*bs_index]->search(pl, *this, *searchOptions);
4566      if (searchOptions->algos & ALGO_MOVELIST && algo_ps[algo_movelist+20*bs_index])
4567        algo_ps[algo_movelist+20*bs_index]->search(pl, *this, *searchOptions);
4568    }
4569  }
4570  if (labels) delete [] labels;
4571  labels = pl.sortContinuations();
4572  if (continuations) delete [] continuations;
4573  continuations = pl.continuations;
4574  pl.continuations = new Continuation[pattern.sizeX*pattern.sizeY];
4575
4576  // FIXME: delete all candidate lists!
4577}
4578
4579
4580int GameList::plSize() {
4581  return pl.size();
4582}
4583
4584string GameList::plEntry(int i) {
4585  if (i < 0 || i >= (int)pl.size()) return "";
4586  else return pl[i];
4587}
4588
4589int rpl_callback(void *pl, int argc, char **argv, char **azColName) {
4590  if (!argc) return 1;
4591  ((vector<string>*)pl)->push_back(string(argv[0]));
4592  return 0;
4593}
4594
4595void GameList::readPlayersList() throw(DBError) {
4596  if (pl.size()) pl = vector<string>();
4597  sqlite3_exec(db, "select p from (select pw p from games union select pb p from games) order by lower(p)", rpl_callback, &pl, 0);
4598  // we ignore possible errors, since the table might not yet exist
4599}
4600
4601void GameList::createGamesDB() throw(DBError) {
4602  SGFtags = p_op->SGFTagsAsStrings();
4603
4604  string sql1 =          "create table if not exists GAMES ( ";
4605  sql1 +=                  "id integer primary key, ";
4606  sql1 +=                  "path text, ";
4607  sql1 +=                  "filename text, ";
4608  sql1 +=                  "pos integer default 0, ";
4609  sql1 +=                  "duplicate integer, ";
4610  sql1 +=                  "dbtree text, ";
4611  sql1 +=                  "date date";
4612
4613  sql_ins_rnp =            "insert into games (path, filename, pos, dbtree, date";
4614  string question_marks =  "?,?,?,?,?";
4615
4616  if (p_op->sgfInDB) {
4617    sql1 +=                ", sgf text";
4618    sql_ins_rnp +=         ", sgf";
4619    question_marks += ",?";
4620  }
4621
4622  SGFtagsSize = SGFtags->size();
4623  int ctr = 0;
4624  posDT = posSZ = posWR = posBR = posHA = -1;
4625  for(vector<string>::iterator it = SGFtags->begin(); it != SGFtags->end(); it++) {
4626    sql1 += ", " + *it + " text";
4627    sql_ins_rnp += ", " + *it;
4628    question_marks += ",?";
4629    if (*it == "DT") posDT = ctr;
4630
4631    if (*it == "SZ") posSZ = ctr;
4632    if (*it == "WR") posWR = ctr;
4633    if (*it == "BR") posBR = ctr;
4634    if (*it == "HA") posHA = ctr;
4635    ctr++;
4636  }
4637  if (posDT == -1) throw DBError();
4638  if (posSZ == -1) {
4639    posSZ = SGFtags->size();
4640    SGFtags->push_back("SZ");
4641  }
4642  if (posWR == -1) {
4643    posWR = SGFtags->size();
4644    SGFtags->push_back("WR");
4645  }
4646  if (posBR == -1) {
4647    posBR = SGFtags->size();
4648    SGFtags->push_back("BR");
4649  }
4650  if (posHA == -1) {
4651    posHA = SGFtags->size();
4652    SGFtags->push_back("HA");
4653  }
4654
4655  sql1 +=                  ");";
4656  sql_ins_rnp +=           ") values (" + question_marks + ");";
4657
4658  int rc = sqlite3_exec(db, sql1.c_str(), 0, 0, 0);
4659  if(rc != SQLITE_OK) throw DBError();
4660
4661  sql1 = "create table if not exists TAGS ( id integer primary key, name text, visible integer default 1 );";
4662  rc = sqlite3_exec(db, sql1.c_str(), 0, 0, 0);
4663  if (rc != SQLITE_OK) throw DBError();
4664  char sql[100];
4665  sprintf(sql, "insert into TAGS (id, name) values (%d, '%d');", HANDI_TAG, HANDI_TAG);
4666  rc = sqlite3_exec(db, sql, 0, 0, 0);
4667  // if (rc != SQLITE_OK) throw DBError();
4668  sprintf(sql, "insert into TAGS (id, name) values (%d, '%d');", PROFESSIONAL_TAG, PROFESSIONAL_TAG);
4669  rc = sqlite3_exec(db, sql, 0, 0, 0);
4670  // if (rc != SQLITE_OK) throw DBError();
4671  sql1 = "create table if not exists GAME_TAGS ( id integer primary key, game_id integer, tag_id integer );";
4672  rc = sqlite3_exec(db, sql1.c_str(), 0, 0, 0);
4673  if (rc != SQLITE_OK) throw DBError();
4674}
4675
4676void GameList::start_processing(int PROCESSVARIATIONS) throw(DBError) {
4677  // printf("enter start_processing %p\n", p_op);
4678
4679  delete_all_snapshots();
4680
4681  if (PROCESSVARIATIONS != -1) processVariations = PROCESSVARIATIONS;
4682  else processVariations = p_op->processVariations;
4683  readDBs = 0;
4684  // printf("dt %d sz %d\n", posDT, posSZ);
4685
4686  int rc;
4687
4688  createGamesDB();
4689
4690  char* sql = "begin transaction;";
4691  rc = sqlite3_exec(db, sql, 0, 0, 0);
4692  if (rc) { throw DBError(); }
4693  rc = sqlite3_exec(algo_db1, sql, 0, 0, 0);
4694  if (rc) { throw DBError(); }
4695  rc = sqlite3_exec(algo_db2, sql, 0, 0, 0);
4696  if (rc) { throw DBError(); }
4697  current = 0;
4698  for(unsigned int a=0; a < 20*boardsizes.size(); a++) {
4699    if (algo_ps[a]) algo_ps[a]->initialize_process(algo_dbs[a]);
4700  }
4701}
4702
4703void GameList::finalize_processing() throw(DBError) {
4704  for(unsigned int a=0; a<20*boardsizes.size(); a++) 
4705    if (algo_ps[a]) algo_ps[a]->finalize_process();
4706  int rc = sqlite3_exec(db, "commit;", 0, 0, 0);
4707  if (rc != SQLITE_OK) {
4708    sqlite3_close(db);
4709    db = 0;
4710    throw DBError();
4711  }
4712  rc = sqlite3_exec(algo_db1, "commit;", 0, 0, 0);
4713  if (rc != SQLITE_OK) {
4714    sqlite3_close(algo_db1);
4715    algo_db1 = 0;
4716    throw DBError();
4717  }
4718  rc = sqlite3_exec(algo_db2, "commit;", 0, 0, 0);
4719  if (rc != SQLITE_OK) {
4720    sqlite3_close(algo_db2);
4721    algo_db2 = 0;
4722    throw DBError();
4723  }
4724  string sql = "update db_info set info = '";
4725  for(vector<int>::iterator it = boardsizes.begin(); it != boardsizes.end(); it++) {
4726    char buf[20];
4727    sprintf(buf, "%d,", *it);
4728    sql += buf;
4729  } 
4730  sql += "' WHERE rowid = 2;";
4731  rc = sqlite3_exec(db, sql.c_str(), 0, 0, 0);
4732  if (rc != SQLITE_OK) throw DBError();
4733  // sqlite3_close(db);
4734  // db = 0;
4735  readDBs = 0;
4736  readDB();
4737  delete SGFtags;
4738}
4739
4740int GameList::process(const char* sgf, const char* path, const char* fn,
4741                      const char* DBTREE, int flags) throw(SGFError,DBError) {
4742  process_results_vector.clear();
4743  const char* dbtree = "";
4744  if (DBTREE) dbtree = DBTREE;
4745
4746  Cursor* c = 0;
4747  try {
4748    c = new Cursor(sgf, 1); // parse sgf sloppily
4749  } catch (SGFError) {
4750    return 0;
4751  }
4752
4753  Node* root = c->root->next;
4754
4755  int pos = 0;
4756  while (root) {
4757    current++;
4758    int return_val = 0;
4759    // if (!(current%1000)) {
4760    //  char* sql = "end transaction;";
4761    //  int rc = sqlite3_exec(db, sql, 0, 0, 0);
4762    //  if (rc) {
4763    //    sqlite3_close(db);
4764    //    db = 0;
4765    //    throw DBError();
4766    //  }
4767    //  sql = "begin transaction;";
4768    //  rc = sqlite3_exec(db, sql, 0, 0, 0);
4769    //  if (rc) {
4770    //    sqlite3_close(db);
4771    //    db = 0;
4772    //    throw DBError();
4773    //  }
4774    // }
4775    vector<string>* rootNodeProperties = parseRootNode(root, SGFtags);
4776    // for(vector<string>::iterator rnp = rootNodeProperties->begin(); rnp != rootNodeProperties->end(); rnp++)
4777    // printf("rnp %s\n", rnp->c_str());
4778
4779    // check board size
4780    string sz = (*rootNodeProperties)[posSZ];
4781    // printf("sz %s\n", sz.c_str());
4782    if (sz=="") sz = "19";
4783    int bs = atoi(sz.c_str());
4784    if (bs < 1) {
4785      return_val |= UNACCEPTABLE_BOARDSIZE;
4786      process_results_vector.push_back(return_val);
4787      delete rootNodeProperties;
4788      root = root->down;
4789      pos++;
4790      continue;
4791    }
4792    int algo_offset = -1;
4793    int bs_ctr = 0;
4794    for(vector<int>::iterator it = boardsizes.begin();  it != boardsizes.end(); it++) {
4795      if (*it == bs) {
4796        algo_offset = bs_ctr;
4797        break;
4798      }
4799      bs_ctr++;
4800    } 
4801    if (algo_offset == -1) { // not found
4802      boardsizes.push_back(bs);
4803      addAlgos(bs);
4804      algo_offset = algo_ps.size()/20 - 1;
4805      // printf("algo_offset %d %d \n", algo_offset, algo_ps.size());
4806      for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) {
4807        // printf("a %d\n", a);
4808        // printf("%p\n", algo_ps[a]);
4809        if (algo_ps[a]) algo_ps[a]->initialize_process(algo_dbs[a]);
4810      }
4811    }
4812
4813    // parse DT tag
4814    string dt = (*rootNodeProperties)[posDT];
4815    // printf("dt %s\n", dt.c_str());
4816    string date;
4817
4818    bool year_found = false;
4819    int p = 0;
4820    while (!year_found && p < (int)dt.size()) {
4821      p = dt.find_first_of("0123456789", p);
4822      if (p == (int)string::npos || p+4 > (int)dt.size() ) break;
4823      else {
4824        year_found = (('0' <= dt[p] && dt[p] <= '9') && ('0' <= dt[p+1] && dt[p+1] <= '9') && ('0' <= dt[p+2] && dt[p+2] <= '9') && ('0' <= dt[p+3] && dt[p+3] <= '9'));
4825        if (year_found && (int)dt.find_first_of("0123456789", p+4) != p+4) { // success: found 4 digits in a row
4826          date += dt.substr(p,4);
4827          date += '-';
4828          dt.erase(p,4);
4829        } else {
4830          while ('0' <= dt[p] && dt[p] <= '9') p++;
4831          year_found = false;
4832          continue;
4833        }
4834      }
4835    }
4836    if (!year_found) date = "0000-00-00";
4837    else {
4838      bool month_found = false;
4839      p = 0;
4840      while (!month_found && p < (int)dt.size()) {
4841        p = dt.find_first_of("0123456789", p);
4842        if (p == (int)string::npos || p+2 > (int)dt.size() ) break;
4843        else {
4844          month_found = ('0' <= dt[p] && dt[p] <= '9' && '0' <= dt[p+1] && dt[p+1] <= '9');
4845          if (month_found && (int)dt.find_first_of("0123456789", p+2) != p+2) {
4846            date += dt.substr(p,2);
4847            date += '-';
4848            dt.erase(p,2);
4849          } else {
4850            while ('0' <= dt[p] && dt[p] <= '9') p++;
4851            month_found = false;
4852            continue;
4853          }
4854        }
4855      }
4856      if (!month_found) date += "00-00";
4857      else {
4858        bool day_found = false;
4859        p = 0;
4860        while (!day_found && p < (int)dt.size()) {
4861          p = dt.find_first_of("0123456789", p);
4862          if (p == (int)string::npos || p+2 > (int)dt.size() ) break;
4863          else {
4864            day_found = ('0' <= dt[p] && dt[p] <= '9' && '0' <= dt[p+1] && dt[p+1] <= '9');
4865            if (day_found && (int)dt.find_first_of("0123456789", p+2) != p+2) {
4866              date += dt.substr(p,2);
4867            } else {
4868              while ('0' <= dt[p] && dt[p] <= '9') p++;
4869              day_found = false;
4870              continue;
4871            }
4872          }
4873        }
4874        if (!day_found) date += "00";
4875      }
4876    }
4877
4878    // printf("sql %s\n", sql_ins_rnp.c_str());
4879    sqlite3_stmt *ppStmt=0;
4880    int rc = sqlite3_prepare(db, sql_ins_rnp.c_str(), -1, &ppStmt, 0);
4881    if (rc != SQLITE_OK || ppStmt==0) {
4882      throw DBError(); // FIXME: catch busy error, (and/or throw DBError?)
4883    }
4884
4885    int stmt_ctr = 1;
4886    rc = sqlite3_bind_text(ppStmt, stmt_ctr++, path, -1, SQLITE_TRANSIENT);
4887    if (rc != SQLITE_OK) throw DBError();
4888    rc = sqlite3_bind_text(ppStmt, stmt_ctr++, fn, -1, SQLITE_TRANSIENT); 
4889    if (rc != SQLITE_OK) throw DBError();
4890    rc = sqlite3_bind_int(ppStmt, stmt_ctr++, pos);
4891    if (rc != SQLITE_OK) throw DBError();
4892    rc = sqlite3_bind_text(ppStmt, stmt_ctr++, dbtree, -1, SQLITE_TRANSIENT);
4893    if (rc != SQLITE_OK) throw DBError();
4894    rc = sqlite3_bind_text(ppStmt, stmt_ctr++, date.c_str(), -1, SQLITE_TRANSIENT); 
4895    if (rc != SQLITE_OK) throw DBError();
4896
4897    if (p_op->sgfInDB) {
4898      if (c->root->numChildren == 1) rc = sqlite3_bind_text(ppStmt, stmt_ctr++, sgf, -1, SQLITE_TRANSIENT); 
4899      else {
4900        string s= "(";
4901        s += c->outputVar(root);
4902        s+= ")";
4903        rc = sqlite3_bind_text(ppStmt, stmt_ctr++, s.c_str(), -1, SQLITE_TRANSIENT); 
4904      }
4905      if (rc != SQLITE_OK) throw DBError();
4906    }
4907
4908    for(int i=0; i < SGFtagsSize; i++) {
4909      rc = sqlite3_bind_text(ppStmt, stmt_ctr++, (*rootNodeProperties)[i].c_str(), -1, SQLITE_TRANSIENT); 
4910      if (rc != SQLITE_OK) throw DBError();
4911    }
4912
4913    rc = sqlite3_step(ppStmt);
4914    if (rc != SQLITE_DONE)  throw DBError();
4915    rc = sqlite3_finalize(ppStmt);
4916    if (rc != SQLITE_OK)  throw DBError();
4917    int game_id = sqlite3_last_insert_rowid(db);
4918
4919
4920    // printf("play through the game\n");
4921    bool commit = true;
4922
4923    Node* currentN = root;
4924    for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
4925      if (algo_ps[a]) algo_ps[a]->newgame_process(game_id);
4926
4927    abstractBoard b = abstractBoard(bs);
4928    int whichVar = 0;
4929    stack<VarInfo> branchpoints;
4930
4931    while (currentN) {
4932      // printf("nn\n");
4933      bool caughtSGFError = false;
4934      char* propValue = 0;
4935
4936      try {
4937
4938        // parse current node, watch out for B, W, AB, AW, AE properties
4939        const char* s = currentN->SGFstring.c_str();
4940        int lSGFstring = strlen(s);
4941        int i = 0;
4942        while (i < lSGFstring && s[i] != ';' && (s[i]==' ' || s[i]=='\n' || s[i]=='\r' || s[i]=='\t')) 
4943          i++;
4944
4945        if (i>=lSGFstring || s[i] != ';') throw SGFError();
4946        i++;
4947
4948        while (i < lSGFstring) { // while parsing
4949
4950          while (i < lSGFstring && (s[i]==' ' || s[i]=='\n' || s[i]=='\r' || s[i]=='\t')) 
4951            i++;
4952          if (i >= lSGFstring) break;
4953
4954          char ID[30];
4955          int IDindex = 0;
4956
4957          while (i < lSGFstring && s[i] != '[' && IDindex < 30) {
4958            if (65 <= s[i] && s[i] <= 90)
4959              ID[IDindex++] = s[i];
4960            else if (!(97 <= s[i] && s[i] <= 122) && !(s[i]==' ' || s[i]=='\n' || s[i]=='\r' || s[i]=='\t')) {
4961              throw SGFError();
4962            }
4963            i++;
4964          }
4965
4966          i++;
4967
4968          if (i >= lSGFstring || IDindex >= 30 || !IDindex) {
4969            throw SGFError();
4970          }
4971          ID[IDindex] = 0; // found next property ID
4972          bool IDrelevant= (!strcmp(ID,"B") || !strcmp(ID,"W") || !strcmp(ID,"AB") || !strcmp(ID,"AW") || !strcmp(ID,"AE"));
4973          propValue = new char[100000];
4974          int propValueIndex = 0;
4975          int oldPropValueIndex = 0;
4976
4977          while (i < lSGFstring) { // while looking for property values of the current property
4978            while (s[i] != ']' && i < lSGFstring) {
4979              if (s[i] == '\\') i++;
4980              if (!IDrelevant || s[i] == '\t' || s[i] == ' ' || s[i] == '\r' || s[i] == '\n') {
4981                i++;
4982                continue;
4983              }
4984              if (97 <= s[i] && s[i] <= 96+bs) { // valid board coordinate?
4985                propValue[propValueIndex++] = s[i];
4986                if (propValueIndex > 99990) throw SGFError();
4987              } else if (s[i] == 't') { ; // allow passes, but do not record them (we handle them a little sloppily here)
4988              } else if (s[i] == ':') {
4989                if (propValueIndex - oldPropValueIndex != 2)
4990                  throw SGFError();
4991                char rect1 = 'a';
4992                char rect2 = 'a';
4993                i++;
4994                while (i<lSGFstring && (s[i] == '\t' || s[i] == ' ' || s[i] == '\r' || s[i] == '\n')) i++;
4995                if (i >= lSGFstring) throw SGFError();
4996                if (97 <= s[i] && s[i] <= 96+bs) // valid board coordinate?
4997                  rect1 = s[i];
4998                else throw SGFError();
4999                i++;
5000                while (i<lSGFstring && (s[i] == '\t' || s[i] == ' ' || s[i] == '\r' || s[i] == '\n')) i++;
5001                if (i >= lSGFstring) throw SGFError();
5002                if (97 <= s[i] && s[i] <= 96+bs) // valid board coordinate?
5003                  rect2 = s[i];
5004                else throw SGFError();
5005                i++;
5006                while (i<lSGFstring && (s[i] == '\t' || s[i] == ' ' || s[i] == '\r' || s[i] == '\n')) i++;
5007                if (i >= lSGFstring) throw SGFError();
5008                if (s[i] == ']') {
5009                  char st1 = propValue[propValueIndex-2];
5010                  char st2 = propValue[propValueIndex-1];
5011                  propValueIndex -= 2; // do not want to have the first entry twice!
5012                  for(char x1 = st1; x1 <= rect1; x1++) {
5013                    for(char x2 = st2; x2 <= rect2; x2++) {
5014                      propValue[propValueIndex++] = x1;
5015                      propValue[propValueIndex++] = x2;
5016                      if (propValueIndex > 99990) throw SGFError();
5017                    }
5018                  }
5019                  oldPropValueIndex = propValueIndex;
5020                  break;
5021                } else throw SGFError();
5022              } else {
5023                throw SGFError();
5024              }
5025              i++;
5026            }
5027            if (i >= lSGFstring) throw SGFError();
5028
5029            if (propValueIndex - oldPropValueIndex != 0 && propValueIndex - oldPropValueIndex != 2) {
5030              throw SGFError();
5031            }
5032            oldPropValueIndex = propValueIndex;
5033
5034            i++;
5035            while (i < lSGFstring && (s[i]==' ' || s[i]=='\n' || s[i]=='\r' || s[i]=='\t')) i++;
5036
5037            if (i >= lSGFstring || s[i] != '[') break; // end of node, or found next property
5038            else i++; // s[i] == '[', so another property value follows.
5039          }
5040          int p_len = propValueIndex/2;
5041
5042          if (!propValueIndex) { // in particular, this happens if !IDrelevant
5043            if (!strcmp(ID, "B") || !strcmp(ID, "W")) {
5044              for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5045                if (algo_ps[a]) algo_ps[a]->pass_process();
5046            }
5047            delete [] propValue;
5048            propValue = 0;
5049            continue;
5050          }
5051
5052          if (!strcmp(ID, "B") || !strcmp(ID, "W")) {
5053            char x = propValue[0]-97; // 97 == ord('a'), (0,0) <= (x,y) <= (bs-1, bs-1)
5054            char y = propValue[1]-97;
5055
5056            if (!b.play(x, y, ID)) throw SGFError();
5057            Move m = b.undostack.top();
5058
5059            for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5060              if (algo_ps[a]) algo_ps[a]->move_process(m);
5061          } else
5062            if (!strcmp(ID, "AB")) {
5063              for(int pp=0; pp < p_len; pp++) {
5064                char x = propValue[2*pp]-97;
5065                char y = propValue[2*pp+1]-97;
5066                if (!b.play(x, y, "B")) throw SGFError();
5067                for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5068                  if (algo_ps[a]) algo_ps[a]->AB_process(x, y);
5069              }
5070            } else
5071              if (!strcmp(ID, "AW")) {
5072                for(int pp=0; pp < p_len; pp++) {
5073                  char x = propValue[2*pp]-97;
5074                  char y = propValue[2*pp+1]-97;
5075                  if (!b.play(x, y, "W")) throw SGFError();
5076                  for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5077                    if (algo_ps[a]) algo_ps[a]->AW_process(x, y);
5078                }
5079              } else {
5080                if (!strcmp(ID, "AE")) {
5081                  for(int pp=0; pp < p_len; pp++) {
5082                    char x = propValue[2*pp]-97;
5083                    char y = propValue[2*pp+1]-97;
5084                    char removed = b.getStatus(x,y);
5085                    if (removed==' ') throw SGFError();
5086                    b.remove(x, y);
5087                    for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5088                      if (algo_ps[a]) algo_ps[a]->AE_process(x, y, removed);
5089                  }
5090                }
5091              }
5092              delete [] propValue;
5093              propValue = 0;
5094        } 
5095      } catch (SGFError) {
5096        if (propValue) {
5097          delete [] propValue;
5098          propValue = 0;
5099        }
5100        return_val |= SGF_ERROR;
5101        caughtSGFError = true;
5102        if (flags & OMIT_GAMES_WITH_SGF_ERRORS) {
5103          commit = false;
5104          // (FIXME should exit from the loop here)
5105        }
5106      }
5107
5108      {
5109        for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5110          if (algo_ps[a]) algo_ps[a]->endOfNode_process();
5111      }
5112
5113      if (processVariations && currentN->numChildren > 1) { // several variations start from this node;
5114        for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5115          if (algo_ps[a]) algo_ps[a]->branchpoint_process();
5116        branchpoints.push(VarInfo(currentN, new abstractBoard(b), 0));
5117      }
5118
5119      if (caughtSGFError) currentN = 0; // stop here with this branch
5120      else currentN = currentN->next;
5121
5122      if (!currentN && branchpoints.size()) {
5123        currentN = branchpoints.top().n;
5124        b = abstractBoard(*branchpoints.top().b);
5125        whichVar = branchpoints.top().i;
5126        branchpoints.pop();
5127        for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5128          if (algo_ps[a]) algo_ps[a]->endOfVariation_process();
5129        if (whichVar+2 < currentN->numChildren) {
5130          for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) 
5131            if (algo_ps[a]) algo_ps[a]->branchpoint_process();
5132          branchpoints.push(VarInfo(currentN, new abstractBoard(b), whichVar+1));
5133        }
5134        currentN = currentN->next;
5135        for(int vi=0; vi < whichVar+1; vi++) currentN = currentN->down;
5136      } 
5137    } // while
5138    {
5139      // check for duplicates (if desired)
5140      bool is_duplicate = false;
5141      if (flags & (CHECK_FOR_DUPLICATES|CHECK_FOR_DUPLICATES_STRICT)) {
5142        char* sig = ((Algo_signature*)algo_ps[20*algo_offset])->get_current_signature();
5143        vector<int> all_duplicates = ((Algo_signature*)algo_ps[20*algo_offset])->search_signature(sig);
5144        if (all_duplicates.size()) {
5145          // printf("dupl %d\n", all_duplicates.size());
5146          is_duplicate = true;
5147          if ((flags & CHECK_FOR_DUPLICATES_STRICT) && (p_op->algos & ALGO_FINALPOS)) {
5148            vector<int>::iterator d_it = all_duplicates.begin();
5149            while (d_it != all_duplicates.end() && !((Algo_finalpos*)algo_ps[20*algo_offset + algo_finalpos])->equals_current(*d_it))
5150              d_it++;
5151            if (d_it == all_duplicates.end()) is_duplicate = false;
5152          }
5153          if (is_duplicate) {
5154            return_val |= IS_DUPLICATE;
5155            if (flags & OMIT_DUPLICATES) commit = false;
5156          }
5157        }
5158        delete [] sig;
5159      }
5160
5161      if (commit) {
5162        // evaluate tags
5163        if ((*rootNodeProperties)[posHA] != "") { // handicap game
5164          char sql[100];
5165          sprintf(sql, "insert into GAME_TAGS (game_id, tag_id) values (%d, %d);", game_id, HANDI_TAG);
5166          rc = sqlite3_exec(db, sql, 0, 0, 0);
5167          if (rc != SQLITE_OK)  throw DBError();
5168        }
5169        if ((*rootNodeProperties)[posWR].find('p') != string::npos ||
5170            (*rootNodeProperties)[posBR].find('p') != string::npos) { 
5171          // at least one of the players is professional
5172          char sql[100];
5173          sprintf(sql, "insert into GAME_TAGS (game_id, tag_id) values (%d, %d);", game_id, PROFESSIONAL_TAG);
5174          rc = sqlite3_exec(db, sql, 0, 0, 0);
5175          if (rc != SQLITE_OK)  throw DBError();
5176        }
5177      } else {
5178        return_val |= NOT_INSERTED_INTO_DB;
5179        char sql[200];
5180        sprintf(sql, "delete from GAMES where id=%d", game_id);
5181        rc = sqlite3_exec(db, sql, 0, 0, 0);
5182        if (rc) printf("ouch %d\n", rc);
5183      }
5184      for(int a=20*algo_offset; a < 20*(algo_offset+1); a++) {
5185        // printf("endgame %d\n", a);
5186        if (algo_ps[a]) algo_ps[a]->endgame_process(commit);
5187      }
5188    }
5189    delete rootNodeProperties;
5190    process_results_vector.push_back(return_val);
5191    root = root->down;
5192    pos++;
5193  }
5194  delete c;
5195  return process_results_vector.size();
5196}
5197
5198int GameList::process_results(unsigned int i) {
5199  if (i<0 || i>=process_results_vector.size()) return INDEX_OUT_OF_RANGE;
5200  return process_results_vector[i];
5201}
5202
5203
5204int GameList::snapshot() throw(DBError) {
5205  // return a handle to a snapshot stored in the main GameList db
5206  // the snapshot contains copies of
5207  // - orderby, format1, format2
5208  // - currentList
5209  // - all hits in the GameListEntry's of currentList
5210  // - pattern, labels, continuations, num_hits, num_switched, Bwins, Wwins
5211
5212  SnapshotVector snapshot;
5213  snapshot.pb_string(orderby);
5214  snapshot.pb_string(format1);
5215  snapshot.pb_string(format2);
5216
5217  snapshot.pb_int(currentList->size());
5218  for(vector<pair<int,int> >::iterator it = currentList->begin(); it != currentList->end(); it++) {
5219    snapshot.pb_int(it->first);
5220    snapshot.pb_int(it->second);
5221    vector<Hit* >* hits = (*all)[it->second]->hits;
5222    snapshot.pb_int(hits->size());
5223    for (vector<Hit* >::iterator it_h = hits->begin(); it_h != hits->end(); it_h++) {
5224      (*it_h)->to_snv(snapshot);
5225    }
5226  }
5227
5228  if (mrs_pattern) {
5229    snapshot.pb_char(1);
5230    mrs_pattern->to_snv(snapshot);
5231  } else snapshot.pb_char(0);
5232  if (searchOptions) {
5233    snapshot.pb_char(1);
5234    searchOptions->to_snv(snapshot);
5235  } else snapshot.pb_char(0);
5236  if (mrs_pattern && labels && continuations) {
5237    snapshot.pb_char(1);
5238    snapshot.pb_charp(labels, mrs_pattern->sizeX * mrs_pattern->sizeY);
5239    for(int i=0; i<mrs_pattern->sizeX * mrs_pattern->sizeY; i++) continuations[i].to_snv(snapshot);
5240  } else snapshot.pb_char(0);
5241  snapshot.pb_int(num_hits);
5242  snapshot.pb_int(num_switched);
5243  snapshot.pb_int(Bwins);
5244  snapshot.pb_int(Wwins);
5245
5246  // insert snapshot into database
5247  sqlite3_stmt *ppStmt=0;
5248  int rc = sqlite3_prepare(db, "insert into snapshots (data) values (?)", -1, &ppStmt, 0);
5249  if (rc != SQLITE_OK || ppStmt==0) throw DBError();
5250  char* snchp = snapshot.to_charp();
5251  rc = sqlite3_bind_blob(ppStmt, 1, snchp, snapshot.size(), SQLITE_TRANSIENT);
5252  delete [] snchp;
5253  if (rc != SQLITE_OK) throw DBError();
5254  rc = sqlite3_step(ppStmt);
5255  if (rc != SQLITE_DONE) throw DBError();
5256  rc = sqlite3_finalize(ppStmt);
5257  if (rc != SQLITE_OK) throw DBError();
5258  return sqlite3_last_insert_rowid(db);
5259}
5260
5261void GameList::restore(int handle, bool del) throw(DBError) {
5262  // restore the state of the GameList associated with handle
5263
5264  // retrieve info associated with handle from db
5265
5266  char* sn = 0;
5267  int sn_size = 0;
5268  sqlite3_stmt *ppStmt=0;
5269  int rc = sqlite3_prepare(db, "select data from snapshots where rowid = ?", -1, &ppStmt, 0);
5270  if (rc != SQLITE_OK || ppStmt==0) {
5271    throw DBError();
5272  }
5273  rc = sqlite3_bind_int(ppStmt, 1, handle);
5274  if (rc != SQLITE_OK) throw DBError();
5275  rc = sqlite3_step(ppStmt);
5276  if (rc == SQLITE_ROW) {
5277    sn = (char*)sqlite3_column_blob(ppStmt, 0);
5278    sn_size = sqlite3_column_bytes(ppStmt, 0);
5279  } else throw DBError();
5280
5281  SnapshotVector snapshot(sn, sn_size);
5282
5283  // parse info
5284
5285  string ob = snapshot.retrieve_string();
5286  string f1 = snapshot.retrieve_string();
5287  string f2 = snapshot.retrieve_string();
5288  if (ob != orderby || f1 != format1 || f2 != format2) resetFormat();
5289
5290  if (oldList) delete oldList;
5291  oldList = 0;
5292  if (currentList) delete currentList;
5293  currentList = new vector<pair<int,int> >;
5294  for(vector<GameListEntry* >::iterator it = all->begin(); it != all->end(); it++) {
5295    if ((*it)->hits) {
5296      for(vector<Hit* >::iterator ith = (*it)->hits->begin(); ith != (*it)->hits->end(); ith++)
5297        delete *ith;
5298      delete (*it)->hits;
5299      (*it)->hits = 0;
5300    }
5301    if ((*it)->candidates) {
5302      for(vector<Candidate* >::iterator itc = (*it)->candidates->begin(); itc != (*it)->candidates->end(); itc++)
5303        delete *itc;
5304      delete (*it)->candidates;
5305      (*it)->candidates = 0;
5306    }
5307  }
5308
5309  int cl_size = snapshot.retrieve_int();
5310  for(int i=0; i<cl_size; i++) {
5311    int i1 = snapshot.retrieve_int();
5312    int i2 = snapshot.retrieve_int();
5313
5314    currentList->push_back(make_pair(i1, i2));
5315    // if ((*currentList)[currentList->size()-1].second >= all->size()) printf("ouch %d\n", (*currentList)[currentList->size()-1].second);
5316    (*all)[(*currentList)[currentList->size()-1].second]->hits_from_snv(snapshot);
5317  }
5318
5319  if (mrs_pattern) delete mrs_pattern;
5320  if (snapshot.retrieve_char()) mrs_pattern = new Pattern(snapshot);
5321  else mrs_pattern = 0;
5322
5323  if (searchOptions) delete searchOptions;
5324  if (snapshot.retrieve_char()) searchOptions = new SearchOptions(snapshot);
5325  else searchOptions = 0;
5326
5327  if (labels) delete [] labels;
5328  if (continuations) delete [] continuations; // FIXME check (cf. ~GameList)
5329  if (snapshot.retrieve_char()) {
5330    labels = snapshot.retrieve_charp();
5331    continuations = new Continuation[mrs_pattern->sizeX * mrs_pattern->sizeY];
5332    for(int i=0; i<mrs_pattern->sizeX * mrs_pattern->sizeY; i++) 
5333      continuations[i].from_snv(snapshot);
5334  } else {
5335    labels = 0;
5336    continuations = 0;
5337  }
5338  num_hits = snapshot.retrieve_int();
5339  num_switched = snapshot.retrieve_int();
5340  Bwins = snapshot.retrieve_int();
5341  Wwins = snapshot.retrieve_int();
5342
5343  rc = sqlite3_finalize(ppStmt);
5344  if (rc != SQLITE_OK) throw DBError();
5345  if (del) { // delete snapshot from db
5346    char sql[100];
5347    sprintf(sql, "delete from snapshots where rowid = %d", handle);
5348    rc = sqlite3_exec(db, sql, 0, 0, 0);
5349    if (rc != SQLITE_OK) throw DBError();
5350  }
5351}
5352
5353void GameList::delete_snapshot(int handle) throw(DBError) {
5354  char sql[100];
5355  sprintf(sql, "delete from snapshots where rowid = %d", handle);
5356  int rc = sqlite3_exec(db, sql, 0, 0, 0);
5357  if (rc != SQLITE_OK) throw DBError();
5358}
5359
5360void GameList::delete_all_snapshots() throw(DBError) {
5361  int rc = sqlite3_exec(db, "delete from snapshots", 0, 0, 0);
5362  if (rc != SQLITE_OK) throw DBError();
5363}
5364
5365VarInfo::VarInfo(Node* N, abstractBoard* B, int I) {
5366  n = N;
5367  b = B;
5368  i = I;
5369}
5370
5371VarInfo::VarInfo(const VarInfo& v) {
5372  n = v.n;
5373  b = new abstractBoard(*v.b);
5374  i = v.i;
5375}
5376
5377VarInfo::~VarInfo() {
5378  delete b;
5379}
5380
Note: See TracBrowser for help on using the browser.