root/05/release-0.5j/matchC.cc

// File: matchC.cc

//   Copyright (C) 2001-4 Ulrich Goertz (u@g0ertz.de)

//   This is part of Kombilo, a go database program.

//   This program is free software; you can redistribute it and/or modify
//   it under the terms of the GNU General Public License as published by
//   the Free Software Foundation; either version 2 of the License, or
//   (at your option) any later version.

//   This program is distributed in the hope that it will be useful,
//   but WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//   GNU General Public License for more details.

//   You should have received a copy of the GNU General Public License
//   along with this program (see doc/license.txt); if not, write to the Free Software
//   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//   The GNU GPL is also currently available at
//   http://www.gnu.org/copyleft/gpl.html

#include <Python.h>

void invert(char *s) {
  int c,i,j;
  for (i=0,j=strlen(s)-1;i<j;i++,j--) {
    c=s[i];
    s[i]=s[j];
    s[j]=c;
  }
}

char* itoa(int n) {             // convert a non-negative integer to a char*
  char *s = new char[15];
  int i;
  
  i=0;
  do { s[i++] = n%10+'0';
  } while ((n/=10)>0);
  
  s[i]='\0';
  invert(s);
  return s;
}


bool greater(long* a, unsigned long i, unsigned long j) {
  if (a[2*i]>a[2*j] || (a[2*i]==a[2*j] && a[2*i+1]>a[2*j+1])) return true;
  return false;
}

void swap(long* a, unsigned long i, unsigned long j) {
  long help1, help2;

  help1 = a[2*i];
  help2 = a[2*i+1];
  a[2*i] = a[2*j];
  a[2*i+1] = a[2*j+1];
  a[2*j] = help1;
  a[2*j+1] = help2;
}


void sortCArray(long* a, long l, long r) {

  long left, right, li11;

  long stack[250];
  stack[0] = l;
  stack[1] = r;
  unsigned char stackIndex = 1;

  long help1, help2;

  while (stackIndex) {
    if (r > l) {
      if (r-l == 1) {
        if (greater(a, l, r)) swap(a, l, r);
        
        stackIndex--;
        l = stack[2*stackIndex];
        r = stack[2*stackIndex+1];

      } else {

        if (greater(a, (r+l)/2, l)) {
          if (greater(a, l, r)) li11 = l;
          else { 
            if (greater(a, r, (r+l)/2)) li11 = (r+l)/2;
            else li11 = r;
          } 
        } else {
          if (greater(a, (r+l)/2, r)) li11 = (r+l)/2;
          else {
            if (greater(a, r, l)) li11 = l;
            else li11 = r;
          }
        }

        swap(a, li11, r);
        help1 = a[2*r];
        help2 = a[2*r+1];
        
        left = l;
        right = r-1;
        
        while (1) { 
          while (a[2*left] < help1 || (a[2*left]==help1 && a[2*left+1]<help2)) left++;
          while (a[2*right] > help1 || (a[2*right]==help1 && a[2*right+1]>help2)) right--;
          
          if (right <= left) break;
          
          swap(a, left, right);
          
          left++;
          right--;
        }

        swap(a, left, r);

        if (left-l > r-left) {
            stack[2*stackIndex] = l;
            stack[2*stackIndex+1] = left-1;
            stackIndex++;
          l = left+1;
        } else {
            stack[2*stackIndex] = left+1;
            stack[2*stackIndex+1] = r;
            stackIndex++;
          r = left-1;
        } 
      }
    } else {
      stackIndex--;
      l = stack[2*stackIndex];
      r = stack[2*stackIndex+1];
    }
  }
}

static const int COLORSWITCH = 1024;

static char flipX(char flipNO, char x, char y) {
  if (flipNO==0) return x;
  if (flipNO==1) return 18-x;
  if (flipNO==2) return x;
  if (flipNO==3) return 18-x;
  if (flipNO==4) return y;
  if (flipNO==5) return 18-y;
  if (flipNO==6) return y;
  if (flipNO==7) return 18-y;
  return 0;
}

static char flipY(char flipNO, char x, char y) {
  if (flipNO==0) return y;
  if (flipNO==1) return y;
  if (flipNO==2) return 18-y;
  if (flipNO==3) return 18-y;
  if (flipNO==4) return x;
  if (flipNO==5) return x;
  if (flipNO==6) return 18-x;
  if (flipNO==7) return 18-x;
  return 0;
}

static PyObject* match(PyObject* self, PyObject* args) {
  int noPatterns;
  char *Patterns;
  char *PSize;
  char *PInvFlips;
  char *PColorSwitch;
  char *PAnchors;
  unsigned long *PBitsTable;
  unsigned char *PBits;
  unsigned char *fp;
  unsigned char *mainlist;
  unsigned long *posTable;

  unsigned long *hashIndices;
  unsigned char *hash;

  char* contLabels;

  int PCSlength, PAlength, PBTlength, PBlength, fplength, MLlength, PTlength, HLlength,
    hashIlength, hashlength, contLabelsLength, contLabelsIndex,
    showColorSwitch, nextMoveVar, fixedColorVar;
  int moveLimit;
  unsigned long* helplist;

  PyObject *progBarUpdate;
  PyObject *continuations;
  PyObject *symmetries;
  PyObject *dbData;
  float pB_start, pB_end;

  if (!PyArg_ParseTuple(args, "sss#s#s#s#s#is#s#s#s#s#s#Offs#iOOOiii", &Patterns, &PSize, 
                        &PInvFlips, &noPatterns, &PColorSwitch, &PCSlength,
                        &PAnchors, &PAlength, &PBitsTable, &PBTlength, &PBits, &PBlength, &moveLimit,
                        &helplist, &HLlength, &fp, &fplength, 
                        &mainlist, &MLlength, &posTable, &PTlength,
                        &hashIndices, &hashIlength, &hash, &hashlength,
                        &progBarUpdate, &pB_start, &pB_end,
                        &contLabels, &contLabelsLength, &contLabelsIndex,
                        &continuations, &symmetries, &dbData,
                        &showColorSwitch, &nextMoveVar, &fixedColorVar))
      return NULL; 

  HLlength /= sizeof(unsigned long);

  int foundgamesSize = 5000;
  int unsigned long *foundgames = PyMem_New(unsigned long, foundgamesSize);    // stored here: no. of found game
  int foundgamesIndex=0;

  PyObject *result = PyList_New(0);

  int Bwins = 0;
  int Wwins = 0;
  int noSwitched = 0;
  int noMatchesFinal = 0;

  int patternSize = PSize[0] * PSize[1];

  unsigned long* hashInd = new unsigned long[noPatterns];
  if (hashIlength) {
    for(int i=0; i<noPatterns; i++) hashInd[i] = hashIndices[2*i];     // set hashInd to hash_start's
  }

  for(int game=0; game < HLlength; game++) {

    if (game % 600 == 0) {      
      float percent = game * (pB_end - pB_start) / HLlength + pB_start;
      PyObject* arglist = Py_BuildValue("(f)", percent);
      PyEval_CallObject(progBarUpdate, arglist);
      Py_DECREF(arglist);
    }

    unsigned long index = helplist[game];

    char matchlist[13000];
    int matchlistIndex = 0;

    for(char N=0; N<noPatterns; N++) {            

      if (hashIlength) {
        while ((hashInd[N]+1<hashIndices[2*N+1]) && (index > 256*hash[hashInd[N]] + hash[hashInd[N]+1])) hashInd[N]+=2;
        if (index < 256*hash[hashInd[N]] + hash[hashInd[N]+1]) continue;
        if (index == 256*hash[hashInd[N]] + hash[hashInd[N]+1]) {
          hashInd[N] += 2;
          matchlist[matchlistIndex++] = N;
          matchlist[matchlistIndex++] = PAnchors[4*N];
          matchlist[matchlistIndex++] = PAnchors[4*N+1];
        }
      }
      else {
        
        char a00 = PAnchors[4*N];
        char a01 = PAnchors[4*N+1];
        char a10 = PAnchors[4*N+2];
        char a11 = PAnchors[4*N+3];
        
        for(char a0=a00; a0 <= a10; a0++) 
          for(char a1=a01; a1 <= a11; a1++) {
            
            int matches = 1;
            
            int pIndex = 2*(a1%2) + (a0%2);
            int patternBits = PBitsTable[N*4 + pIndex];
            
            int pbIndex = 0;
            int fpIndex = index*150 + a1/2 + (a0/2)*10;
            
            for(int x=0; x < PBits[patternBits]; x++) {
              
              int start = PBits[patternBits + ++pbIndex];
              int length = PBits[patternBits + ++pbIndex];
              fpIndex += start;
              
              for(int y=0; y<length; y++) {
                pbIndex++;
                
                if (PBits[patternBits+pbIndex] & fp[fpIndex]) {
                  matches = 0;
                  break;
                }
                
                fpIndex++;
              }
              if (!matches) break;
              fpIndex += 10 - start - length;
              
            }
            
            if (matches) { 
              matchlist[matchlistIndex++] = N;
              matchlist[matchlistIndex++] = a0;
              matchlist[matchlistIndex++] = a1;
            }
            
          }
      }
    }
    
    if (matchlistIndex) {    /* checkCandidate */

      int noMatches = matchlistIndex/3;
      int toBeFound = noMatches;        
      long noCurrentResults = 0;
      long *currentResults = new long[noMatches*2];
  
      char *dicts = new char[noMatches * patternSize];
      int *dictsNO = new int[noMatches];
          
      int *found = new int[noMatches];
          
      char *Xinterv = new char[2*noMatches];
      char *Yinterv = new char[2*noMatches];
          
      for(int m=0; m<noMatches; m++) {
              
        found[m] = -1;
        dictsNO[m] = 0;
              
        int sizeX = PSize[2*matchlist[3*m]];
        int sizeY = PSize[2*matchlist[3*m]+1];
        int Poffset = matchlist[3*m] * patternSize;
              
        for(int i=0; i < sizeX; i++) {
          for(int j=0; j < sizeY; j++) {
            if (Patterns[Poffset + sizeY*i + j] == '.')
              dicts[m*patternSize+i*sizeY+j] = ' ';
            else {
              dicts[m*patternSize+i*sizeY+j] = Patterns[Poffset + sizeY*i + j];
              if (Patterns[Poffset + sizeY*i + j] != '*') dictsNO[m]++;
            }                   
          }
        }
        
        Xinterv[2*m] = matchlist[3*m+1];
        Xinterv[2*m+1] = matchlist[3*m+1] + PSize[2*matchlist[3*m]];
        Yinterv[2*m] = matchlist[3*m+2];
        Yinterv[2*m+1] = matchlist[3*m+2] + PSize[2*matchlist[3*m]+1];
      }

      int movelistIndex = posTable[index]+2;
      
      int caplistIndex = movelistIndex;
      while (mainlist[caplistIndex] != 'z') caplistIndex++;
      int mlLength = caplistIndex;
      
      if (mainlist[caplistIndex+2] == 'z') caplistIndex +=2; // caplist empty
      else caplistIndex += 3;
      
      /* AB's */
      
      if (mainlist[movelistIndex] == 25 && mainlist[movelistIndex+1] == 3) {
        movelistIndex += 2;
        while (mainlist[movelistIndex] != 25) {
          char x = mainlist[movelistIndex++];
          char y = mainlist[movelistIndex++];
          
          for (int m=0; m<noMatches; m++) {
            if (found[m] != -2) {
              if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
                  Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {     /* stone played in */
                /* relevant region */
                if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]==' ') {
                  
                  if (!(fp[index*150 + 100 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {  
                    // this m can't become a match
                    found[m] = -2;
                    toBeFound--;
                    continue;
                  }
                  else {
                    dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = '.';
                    dictsNO[m]++;
                  }
                }
                else if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                              +y-matchlist[3*m+2]] == 'X') {
                  dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]=' ';
                  dictsNO[m]--;
                }
              }
            }
          }
        }
      }
      
      /* AW's */
      
      if (mainlist[movelistIndex] == 25 && mainlist[movelistIndex+1] == 4) {
        movelistIndex += 2;
        while (mainlist[movelistIndex] != 25) {
          char x = mainlist[movelistIndex];
          char y = mainlist[movelistIndex+1];
          movelistIndex += 2;
          
          int m;
          for (m=0; m<noMatches; m++) {
            if (found[m]!= -2) {
              if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
                  Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {     
                if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]==' ') {
                  if (!(fp[index*150 + 100 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {            
                    // this m can't become a match
                    found[m] = -2;
                    toBeFound--;
                    continue;
                  }
                  else {
                    dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = '.';
                    dictsNO[m]++;
                  }
                }
                else if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                              +y-matchlist[3*m+2]] == 'O') {
                  dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]]=' ';
                  dictsNO[m]--;
                }
              }
            }
          }
        }
      }
      
      for(int m=0; m<noMatches; m++)
        if (found[m]==-1 && !dictsNO[m]) found[m] = 0;        
      
      /* B's and W's */
      
      char co = 'B';
      
      if (mainlist[movelistIndex+1] == 1) co = 'B';
      if (mainlist[movelistIndex+1] == 2) co = 'W';
      
      int mLimit;
      
      if (moveLimit == 250) mLimit = 1500 + movelistIndex;         // practically no limit
      else mLimit = 2*moveLimit + movelistIndex;
      
      int counter = -1;
      char c;
      char cinv;
      
      while (movelistIndex < mlLength-2 && movelistIndex < mLimit) {
        
        movelistIndex += 2;
        counter++;
        
        if (co == 'B') {
          co = 'W';
          c = 'X';
          cinv = 'O';
        } else {
          co = 'B';
          c = 'O';
          cinv = 'X';
        }
        
        char x = mainlist[movelistIndex];
        char y = mainlist[movelistIndex+1];
        
        int clI = 0;
        int clIend = 0;
        
        if (mainlist[caplistIndex] != 'z' && counter == 256*mainlist[caplistIndex] + mainlist[caplistIndex+1]) {
          caplistIndex += 2;
          clI = caplistIndex;
          while (mainlist[caplistIndex] != 'z' && mainlist[caplistIndex] != 'y') caplistIndex++;
          clIend = caplistIndex-1;
          caplistIndex++;
        } 
        
        for(int m=0; m<noMatches; m++) {

          if (found[m] != -2) {

            if (Xinterv[2*m] <= x && x < Xinterv[2*m+1] &&
                Yinterv[2*m] <= y && y < Yinterv[2*m+1]) {
              
              if (found[m] > -1) {
                int colorSwitch = 0;
                
                int f = PInvFlips[matchlist[3*m]];
                char xx = flipX(f, x, y);
                char yy = flipY(f, x, y);
                
                char XX1 = flipX(f, Xinterv[2*m], Yinterv[2*m]);
                char YY1 = flipY(f, Xinterv[2*m], Yinterv[2*m]);
                
                char XX2 = flipX(f, Xinterv[2*m+1]-1, Yinterv[2*m+1]-1);
                char YY2 = flipY(f, Xinterv[2*m+1]-1, Yinterv[2*m+1]-1);
                
                char XX = XX1 < XX2 ? XX1 : XX2;
                char YY = YY1 < YY2 ? YY1 : YY2;
                
                xx -= XX;
                yy -= YY;

                char *cc, *wcc, *lcc, *tcc;
                if ((PColorSwitch[matchlist[3*m]] && co == 'B') ||
                    (!PColorSwitch[matchlist[3*m]] && co == 'W'))
                  cc = "B";
                else cc = "W";
                
                PyObject *key = Py_BuildValue("ii", xx, yy);
                PyObject *t = PyDict_GetItem(symmetries, key);
                Py_DECREF(key);

                PyObject *xxyy = PyTuple_GetItem(t, 0);
                Py_INCREF(xxyy);
                
                xx = PyInt_AsLong(PyTuple_GetItem(xxyy, 0));
                yy = PyInt_AsLong(PyTuple_GetItem(xxyy, 1));
                long cSymm = PyInt_AsLong(PyTuple_GetItem(t, 1));

                if ((strcmp(cc, "W")==0 && !cSymm) || (strcmp(cc, "B")==0 && cSymm)) {
                  cc = "W";
                  wcc = "wW";
                  lcc = "lW";
                  tcc = "tW";
                }
                else {
                  cc = "B";
                  wcc = "wB";
                  lcc = "lB";
                  tcc = "tB";
                }
                
                if (nextMoveVar) {
                  if ((nextMoveVar==2 && cc=="B") || (nextMoveVar==1 && cc=="W")) {
                    PyObject *key1 = PyInt_FromLong(-1);
                    PyObject *t1 = PyDict_GetItem(symmetries, key1);
                    Py_DECREF(key1);

                    long ssymm = PyInt_AsLong(t1);
                    if (ssymm != -1 && !fixedColorVar) {

                      if (cc == "B") {
                        cc = "W";
                        wcc = "wW";
                        lcc = "lW";
                        tcc = "tW";
                      }
                      else {
                        cc = "B";
                        wcc = "wB";
                        lcc = "lB";
                        tcc = "tB";
                      }            

                      
                      xx += XX;
                      yy += YY;
 
                      int xx_n = flipX(ssymm, xx, yy);
                      int yy_n = flipY(ssymm, xx, yy);
                      int XX1_n = flipX(ssymm, XX1, YY1);
                      int YY1_n = flipY(ssymm, XX1, YY1);
                      int XX2_n = flipX(ssymm, XX2, YY2);
                      int YY2_n = flipY(ssymm, XX2, YY2);

                      XX = XX1_n < XX2_n ? XX1_n : XX2_n;
                      YY = YY1_n < YY2_n ? YY1_n : YY2_n;

                      xx = xx_n - XX;
                      yy = yy_n - YY;

                      PyObject *key2 = Py_BuildValue("ii", xx, yy);
                      PyObject *t2 = PyDict_GetItem(symmetries, key);

                      PyObject *xxyy2 = PyTuple_GetItem(t2, 0);
                      long cSymm1 = PyInt_AsLong(PyTuple_GetItem(t2, 1));

                      if (!cSymm1) {
                        Py_DECREF(xxyy);
                        xxyy = xxyy2;
                        Py_DECREF(key2);
                        Py_INCREF(xxyy);
                      }
                      else {
                        Py_DECREF(xxyy);
                        xxyy = key2;
                      }

                      colorSwitch = 1-cSymm;
                      if (colorSwitch) noSwitched++;      
                    }
                    else {
                      found[m] = -2;
                      toBeFound--;
                      continue;
                    }
                  }
                  else {
                    colorSwitch = cSymm;
                    if (colorSwitch) noSwitched++;
                  }
                }
                else colorSwitch = cSymm;
                
                char text;
                PyObject* scxy;

                if ((scxy = PyDict_GetItem(continuations, xxyy))) {
                  PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, cc))+1);
                  PyDict_SetItemString(scxy, cc, temp);
                  Py_DECREF(temp);
                  text = PyString_AsString(PyDict_GetItemString(scxy, "N"))[0];
                }
                else {
                  if (contLabelsIndex >= contLabelsLength) text = '?';
                  else text = contLabels[contLabelsIndex++];
                  
                  if (strcmp(cc, "B")==0) {
                    scxy = PyDict_New();
                    PyObject* Py0 = PyInt_FromLong(0);
                    PyObject *Py1 = PyInt_FromLong(1);
                    PyDict_SetItemString(scxy, "B", Py1);
                    PyDict_SetItemString(scxy, "W", Py0);
                    PyDict_SetItemString(scxy, "tB", Py0);
                    PyDict_SetItemString(scxy, "tW", Py0);
                    PyDict_SetItemString(scxy, "wB", Py0);
                    PyDict_SetItemString(scxy, "lB", Py0);
                    PyDict_SetItemString(scxy, "wW", Py0);
                    PyDict_SetItemString(scxy, "lW", Py0);
                    PyDict_SetItemString(scxy, "N", PyString_FromStringAndSize(&text, 1));
                    Py_DECREF(Py0);
                    Py_DECREF(Py1);
                    PyDict_SetItem(continuations, xxyy, scxy);
                    Py_DECREF(scxy);
                  }
                  else {
                    scxy = PyDict_New();
                    PyObject *Py0 = PyInt_FromLong(0);
                    PyObject *Py1 = PyInt_FromLong(1);
                    PyDict_SetItemString(scxy, "B", Py0);
                    PyDict_SetItemString(scxy, "W", Py1);
                    PyDict_SetItemString(scxy, "tB", Py0);
                    PyDict_SetItemString(scxy, "tW", Py0);
                    PyDict_SetItemString(scxy, "wB", Py0);
                    PyDict_SetItemString(scxy, "lB", Py0);
                    PyDict_SetItemString(scxy, "wW", Py0);
                    PyDict_SetItemString(scxy, "lW", Py0);
                    PyDict_SetItemString(scxy, "N", PyString_FromStringAndSize(&text, 1));
                    Py_DECREF(Py0);
                    Py_DECREF(Py1);
                    PyDict_SetItem(continuations, xxyy, scxy);
                    Py_DECREF(scxy);
                  }
                }

                Py_DECREF(xxyy);

                PyObject *d1 = PyList_GetItem(dbData, index);

                if (!PyTuple_Check(d1)) return NULL;

                PyObject *d2 = PyTuple_GetItem(d1, 4);
                if (!PyString_Check(d2)) return NULL;

                char* winner = PyString_AsString(d2);

                if (winner[0] == 'B')
                  if (!(PColorSwitch[matchlist[3*m]] || colorSwitch)) {
                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, wcc))+1);
                    PyDict_SetItemString(scxy, wcc, temp);
                    Py_DECREF(temp);
                    Bwins++;
                  }
                  else {
                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, lcc))+1);
                    PyDict_SetItemString(scxy, lcc, temp);
                    Py_DECREF(temp);
                    Wwins++;
                  }
                if (winner[0] == 'W')
                  if (!(PColorSwitch[matchlist[3*m]] || colorSwitch)) {
                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, lcc))+1);
                    PyDict_SetItemString(scxy, lcc, temp);
                    Py_DECREF(temp);
                    Wwins++;
                  }
                  else {
                    PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, wcc))+1);
                    PyDict_SetItemString(scxy, wcc, temp);
                    Py_DECREF(temp);
                    Bwins++;
                  }

                if (!(found[m]==counter || found[m]==counter+1)) {
                  PyObject *temp = PyInt_FromLong(PyInt_AsLong(PyDict_GetItemString(scxy, tcc))+1);
                  PyDict_SetItemString(scxy, tcc, temp);
                  Py_DECREF(temp);
                }

                noSwitched += PColorSwitch[matchlist[3*m]];

                currentResults[2*noCurrentResults] = found[m];
                currentResults[2*noCurrentResults+1] = (PColorSwitch[matchlist[3*m]]|colorSwitch) * COLORSWITCH + text;
                noCurrentResults++;

                found[m] = -2;
                toBeFound--;
                
                continue;
              }
              
              if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                       +y-matchlist[3*m+2]] == ' ') {
                
                if (!(fp[index*150 + 100 + y/4 + 5*(x/2)] & (1 << (x%2 + 2*(y%4))))) {
                  found[m] = -2;
                  toBeFound--;
                  continue;
                }
                else {
                  dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = '.';
                  dictsNO[m]++;
                }
                
              }
              else if (dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                            +y-matchlist[3*m+2]] == c) {
                dicts[m*patternSize+(x-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]+y-matchlist[3*m+2]] = ' ';
                dictsNO[m]--;
              }
            }
            
            if (found[m] == -1) {

              if (clI) {                 /* captures */
                
                for(int i=clI; i<clIend; i+=2) {
                  char xx = mainlist[i]-1;
                  char yy = mainlist[i+1]-1;
                  
                  if (Xinterv[2*m] <= xx && xx < Xinterv[2*m+1] &&
                      Yinterv[2*m] <= yy && yy < Yinterv[2*m+1]) {
                    if (dicts[m*patternSize+(xx-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                             +yy-matchlist[3*m+2]] == ' ') {
                      dicts[m*patternSize+(xx-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                           +yy-matchlist[3*m+2]] = cinv;
                      dictsNO[m]++;
                    }
                    else if (dicts[m*patternSize+(xx-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                                  +yy-matchlist[3*m+2]] == '.') {
                      dicts[m*patternSize+(xx-matchlist[3*m+1])*PSize[2*matchlist[3*m]+1]
                           +yy-matchlist[3*m+2]] = ' ';
                      dictsNO[m]--;
                    }
                  }
                  
                }
              }
              if (!dictsNO[m]) found[m] = counter + 1;
            }

          }
        }
        
        if (!toBeFound) break;
      }
      

      if (!nextMoveVar) {
        for(int m=0; m<noMatches; m++) 
          if (found[m] > -1) {

            noSwitched += PColorSwitch[matchlist[3*m]];

            currentResults[2*noCurrentResults] = found[m];
            currentResults[2*noCurrentResults+1] = PColorSwitch[matchlist[3*m]] * COLORSWITCH;
            noCurrentResults++;

            char winner = PyString_AsString(PyTuple_GetItem(PyList_GetItem(dbData, index), 4))[0];

            if (winner == 'B')
              if (!PColorSwitch[matchlist[3*m]]) Bwins++;
              else Wwins++;
            if (winner == 'W')
              if (!PColorSwitch[matchlist[3*m]]) Wwins++;
              else Bwins++;       
          }
      }
      
      delete dicts;
      delete dictsNO;
      delete found;
      delete Xinterv;
      delete Yinterv;

      if (noCurrentResults) {

        if (foundgamesIndex > foundgamesSize - 2) {
          foundgamesSize += 2000;
          foundgames = PyMem_Resize(foundgames, unsigned long, foundgamesSize);
        }
      
        foundgames[foundgamesIndex++] = index;
        noMatchesFinal += noCurrentResults;

        sortCArray(currentResults, 0, noCurrentResults-1);

        char *resultStr = new char[7*noCurrentResults];
        int resultStrIndex = 0;

        for(int i=0; i<noCurrentResults; i++) {
          char *s = itoa(currentResults[2*i]);
          for(int j=0; j<strlen(s); j++) resultStr[resultStrIndex++] = s[j];
          delete s;
          if (currentResults[2*i+1] % 256) resultStr[resultStrIndex++] = currentResults[2*i+1] % 256;
          if (showColorSwitch && (currentResults[2*i+1]&COLORSWITCH)) resultStr[resultStrIndex++] = '-';
          resultStr[resultStrIndex++] = ',';
          resultStr[resultStrIndex++] = ' ';
        }       
        resultStrIndex -= 2;

        PyObject *temp = PyString_FromStringAndSize(resultStr, resultStrIndex);
        if (PyList_Append(result, temp)) return NULL;
        Py_DECREF(temp);

        delete resultStr;
  
      }
      delete currentResults;
    }
  }     
  
  PyObject *returnValue = Py_BuildValue("s#Oiiiii", foundgames, foundgamesIndex*sizeof(unsigned long), result, 
                                        noSwitched, contLabelsIndex, Wwins, Bwins, noMatchesFinal);

  Py_DECREF(result);
  delete hashInd;
  PyMem_Free(foundgames);

  return returnValue;
}


static PyObject* sortArray(PyObject* self, PyObject* args) {
  
  long* a;

  unsigned long adr;
  long l, r;          // it's important that these are signed!

  if (!PyArg_ParseTuple(args, "lii", &adr, &l, &r))
    return NULL;