Changeset 174 for 06/devel

Show
Ignore:
Timestamp:
08/16/06 22:26:22 (2 years ago)
Author:
ug
Message:

Worked some more on pattern.cc ... not done yet, though.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • 06/devel/aglPY.py

    r168 r174  
    2222 
    2323from searchPY import * 
    24 from patternPY import * 
     24try: 
     25    from pattern import * 
     26except ImportError: 
     27    print "Using patternPY" 
     28    from patternPY import * 
    2529from algosPY import Hit 
    2630 
    …… 
    548552 
    549553        print nextMoveVar 
     554        print "Build pattern list ..." 
    550555        patternList = PatternList(pattern, fixedColorVar, nextMoveVar, self.boardsize) 
     556        print "done" # FIXME 
    551557 
    552558        if contLabels is None: 

  • 06/devel/algos.cc

    r172 r174  
    11// File: algos.cc 
    22 
    3 //   Copyright (C) 2001-4 Ulrich Goertz (u@g0ertz.de) 
     3//   Copyright (C) 2001-6 Ulrich Goertz (u@g0ertz.de) 
    44 
    55//   This is part of Kombilo, a go database program. 
    …… 
    2929// --------------------------------------------------------------------------------------- 
    3030 
     31 
     32string retrieve_datap0(PyObject* datapath) { 
     33} 
     34 
     35string retrieve_datap1(PyObject* datapath) { 
     36} 
    3137 
    3238Algorithm::Algorithm(int bsize) { 
    …… 
    94100 
    95101void Algo_finalpos::finalize_process(PyObject* datap) { 
    96   // FIXME 
    97         extract datap0, datap1 from datap 
    98         String fn = datap0 + "/finalpos" + datap1 + ".db"; // FIXME: linux specific!? 
     102        String fn = retrieve_datap0(datap) + "/finalpos" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    99103        ofstream file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc 
    100104  file.write(finalpos, finalposSize); 
    …… 
    103107 
    104108 
    105 int Algo_finalpos::duplicateCheck(sli, datapath=None) { 
     109int Algo_finalpos::duplicateCheck(sli, datapath=None) { // FIXME None 
    106110  if (!strcmp(datapath, "")) { 
    107111    for(int i=0; i<100; i++) 
    108112      if (finalpos[sli*100+i] != fp[i]) 
    109         return 0; 
     113                               return 0; 
    110114    return 1; 
    111115  } 
    …… 
    136140 
    137141int Algo_finalpos::retrieve_db(datap) { 
    138         String fn = ... "/finalpos" ...; 
     142        String fn = retrieve_datap0(datap) + "/finalpos" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    139143        ifstream file (fn, ios::in|ios::binary|ios::ate); 
    140144        if (file.is_open()) { 
    …… 
    329333 
    330334void Algo_movelist::finalize_process(datap) { 
    331   // FIXME 
    332         extract datap0, datap1 from datap 
    333                  
    334         String fn = datap0 + "/posTable" + datap1 + ".db"; // FIXME: linux specific!? 
     335        String fn = retrieve_datap0(datap) + "/posTable" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    335336        ofstream file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc 
    336337  file.write(posTable, posTableSize); // FIXME: posTable is vector, posTableSize does not exist 
    …… 
    350351void Algo_movelist::retrieve_db(datap) { 
    351352 
    352         String fn = ... "/finalposC" ...; // FIXME 
     353        String fn = retrieve_datap0(datap) + "/finalposC" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    353354        ifstream file (fn, ios::in|ios::binary|ios::ate); 
    354355        if (file.is_open()) { 
    …… 
    364365          return 0; 
    365366        } 
    366         String fn = ... "/lists" ...; // FIXME 
     367        fn = retrieve_datap0(datap) + "/lists" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    367368        ifstream file (fn, ios::in|ios::binary|ios::ate); 
    368369        if (file.is_open()) { 
    …… 
    378379        return 0; 
    379380        } 
    380         String fn = ... "/posTable" ...; // FIXME 
     381        fn = retrieve_datap0(datap) + "/posTable" + retrieve_datap1(datap) + ".db"; // FIXME: linux specific!? 
    381382        ifstream file (fn, ios::in|ios::binary|ios::ate); 
    382383        if (file.is_open()) { 
    …… 
    690691     
    691692 
    692 Algo_hash::Algo_hash(int bsize, plist, char* fname) : ALgorithm(bsize) { 
    693   poslist = [[0,0] + p for p in plist]; 
    694   filename = new char[strlen(fname)+1]; 
    695   strcpy(filename, fname); 
    696 } 
    697  
    698 Algo_hash::~Algo_hash() { 
    699   delete [] filename; 
    700 } 
    701  
    702 void Algo_hash::initialize_process(l) { 
    703   hash_global = hashTable(l, self.filename); 
    704   gameCtr = 0; 
    705 } 
    706          
    707 void Algo_hash::newgame_process() { 
    708  
    709   for (p in self.poslist) { 
    710     p[0] = 0; 
    711     p[1] = 0; 
    712   } 
    713  
    714   hash_global.newCtr(gameCtr); 
    715   branchpoints = []; 
    716 } 
    717  
    718 void Algo_hash::AB_process(int x, int y) { 
    719   for (p in self.poslist) { 
    720     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
    721       p[0]++; 
    722       p[1] += hashTable.hash_value[(x,y)]; 
    723     } 
    724   } 
    725 } 
    726  
    727 void Algo_hash::AW_process(int x, int y) { 
    728   for (p in self.poslist) { 
    729     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
    730       p[0]++; 
    731       p[1] -= hashTable.hash_value[(x,y)]; 
    732     } 
    733   } 
    734 }                  
    735  
    736 void Algo_hash::AE_process(int x, int y, char removed) { 
    737   int epsilon; 
    738   if (removed == 'B') epsilon = -1; 
    739   else epsilon = 1; 
    740    
    741   for (p in self.poslist) { 
    742     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
    743       p[0]--; 
    744       p[1] += epsilon * hashTable.hash_value[(x,y)]; 
    745     } 
    746   } 
    747 } 
    748  
    749 void Algo_hash::endOfNode_process() { 
    750   for(p in self.poslist) 
    751     if (p[0] <= p[6]) self.hash_global.append(p[1]); 
    752 } 
    753  
    754 void Algo_hash::B_process(int x, int y, cap) { 
    755   self.move_process(x, y, cap, 1); 
    756 } 
    757  
    758 void Algo_hash::W_process(int x, int y, cap) { 
    759   self.move_process(x, y, cap, -1); 
    760 } 
    761  
    762 void Algo_hash::move_process(int x, int y, cap, epsilon) { 
    763   for (p in self.poslist) 
    764     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
    765       p[0]++; 
    766       p[1] += epsilon * hashTable.hash_value[(x,y)]; 
    767     } 
    768    
    769   for (c in cap) { 
    770     for(p in self.poslist)  
    771       if (p[2] <= c[0] && c[0] <= p[4] && p[3] <= c[1] && c[1] <= p[5]) { 
    772       p[0] -= 1; 
    773       p[1] += epsilon * hashTable.hash_value[c]; 
    774       } 
    775   } 
    776 } 
    777  
    778 void Algo_hash::branchpoint_process() { 
    779   branchpoints.append(deepcopy(self.poslist)); 
    780 } 
    781  
    782 void Algo_hash::endOfVariation_process() { 
    783   poslist = self.branchpoints.pop(); 
    784 } 
    785  
    786 void Algo_hash::endgame_process() { 
    787   gameCtr++; 
    788 } 
    789   
    790 void Algo_hash::finalize_process(PyObject* datap) { 
    791   hash_global.newCtr(gameCtr); 
    792   hash_global.sortedOutput(datap); 
    793 } 
    794  
    795  
    796 long Algo_hash::compute_hashkey(Pattern pattern, type) { 
    797  
    798   int numOfStones = 0; 
    799  
    800   a0,b0,a1,b1, maxNumOfStones = type; 
    801   long hashkey = 0; 
    802              
    803   for(int i=a0, i<a1+1; i++) { 
    804     for(int j=b0; j<b1+1; j++) { 
    805       if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] in ['x', 'o', '*']) 
    806       return NOT_HASHABLE; 
    807       else if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] == 'X') { 
    808       hashkey += hashTable.hash_value[(i,j)]; 
    809       numOfStones += 1; 
    810       } 
    811       else if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] == 'O') { 
    812       hashkey -= hashTable.hash_value[(i,j)]; 
    813       numOfStones += 1; 
    814       } 
    815     } 
    816     if numOfStones > maxNumOfStones: return NOT_HASHABLE; 
    817   } 
    818   return hashkey; 
    819 } 
    820  
    821 int Algo_hash::retrieve_db(PyObject* datap) { 
    822       String fn = ... filename ...; // FIXME 
    823       ifstream file (fn, ios::in|ios::binary|ios::ate); 
    824       if (file.is_open()) { 
    825               ifstream::pos_type size = file.tellg(); 
    826               delete [] hash; 
    827               hash = new char[size]; // FIXME: not a char array? 
    828               file.seekg (0, ios::beg); 
    829               file.read (memblock, size); 
    830               file.close(); 
    831       } 
    832   else { 
    833               cout << "Unable to open file"; 
    834         return 0; 
    835       } 
    836       String fn = ... filename + "T" ...; // FIXME 
    837       ifstream file (fn, ios::in|ios::binary|ios::ate); 
    838       if (file.is_open()) { 
    839               ifstream::pos_type size = file.tellg(); 
    840               delete [] hashT; 
    841               hashT = new char[size]; 
    842               file.seekg (0, ios::beg); 
    843               file.read (memblock, size); 
    844               file.close(); 
    845       } 
    846   else { 
    847               cout << "Unable to open file"; 
    848         return 0; 
    849       } 
    850   return 0; 
    851 } 
    852  
    853 void Algo_hash::search(patternList, options, db, progBar, progStart, progEnd) { 
    854   for(int i=0; i<patternList.size(); i++) { 
    855     Pattern pattern = patternList.get(i); 
    856     pattern_hashkeys = {}; 
    857              
    858     for(int a0=pattern.left; a0<=pattern.right; a0++) { 
    859       for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
    860       pattern_hashkeys[(a0,a1)] = []; 
    861       for(p in self.poslist) { 
    862         if (a0 <= p[2] && a0+pattern.sizeX >= p[4] a1 <= p[3] && a1+pattern.sizeY >= p[5]) { 
    863           hk = self.compute_hashkey(pattern, p[2:]); 
    864  
    865           if (hk != NOT_HASHABLE) pattern.hashkeys[(a0,a1)].append([hk]); 
    866         } 
    867       } 
    868       if (!pattern.hashkeys[(a0,a1)]) return; 
    869       } 
    870     } 
    871   } 
    872          
    873   if (!self.retrieve_db(db.datapath)) { 
    874     printf("error\n"); // FIXME 
    875     return; 
    876   } 
    877          
    878   for(int N=0; N<patternList.size(); N++) { 
    879     Pattern pattern = patternList.get(N); 
    880              
    881     for(int a0=pattern.left; a0<=pattern.right; a0++) { 
    882       for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
    883              
    884       for(int hk=0; hk<len(pattern.hashkeys[(a0,a1)]); hk++) { 
    885  
    886         int hashkey = pattern.hashkeys[(a0,a1)][hk][0]; 
    887         int start = 0; 
    888         int end = len(self.hashT)/2; 
    889                    
    890         int hash_start; 
    891         int hash_end; 
    892  
    893         while (start < end) { 
    894           int help = self.hashT[2*((start+end)/2)]; 
    895           if (help == hashkey) { 
    896             hash_start = self.hashT[2*((start+end)/2)+1]; 
    897             if (2*((start+end)/2)+3 >= len(self.hashT)) hash_end = len(hash); 
    898             else hash_end = self.hashT[2*((start+end)/2)+3]; 
    899  
    900             pattern.hashkeys[(a0,a1)][hk].extend([hash_start, hash_start, hash_end]); 
    901             break; 
    902           } 
    903           else if (help > hashkey) end = (start+end)/2; 
    904           else if (help < hashkey) start = (start+end)/2 + 1; 
    905         } 
    906       } 
    907       } 
    908     } 
    909   } 
    910  
    911   int index = db.start(); 
    912   int gameCounter = 0; 
    913          
    914   while (index != -1) { 
    915     gameCounter++; 
    916     if (progBar && !(gameCounter % 50)) 
    917       progBar.redraw((progEnd-progStart)*gameCounter/len(db.current) + progStart); 
    918  
    919     matchList = []; 
    920     for(int N=0; N<patternList.size(); N++) { 
    921       Pattern pattern = patternList.get(N); 
    922       for(int a0=pattern.left; a0<=pattern.right; a0++) { 
    923       for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
    924         int matchPossible = 1; 
    925         for(int hk=0; hk<len(pattern.hashkeys[(a0,a1)]); hk++) { 
    926           l = pattern.hashkeys[(a0,a1)][hk]; 
    927           if (len(l) == 1) { 
    928             matchPossible = 0; 
    929             break; 
    930           } 
    931                              
    932           while (l[2]+1 < l[3] && index > 256*hash[l[2]] + hash[l[2]+1]) 
    933             l[2] += 2; 
    934                      
    935           if (index < 256*hash[l[2]] + hash[l[2]+1]) { 
    936             matchPossible = 0; 
    937             break; 
    938           } 
    939         } 
    940  
    941         if (matchPossible) { 
    942           l[2] += 2; 
    943           matchList.append((N, (a0, a1))); 
    944         } 
    945       } 
    946       } 
    947     } 
    948      
    949     if (matchList) db.makeCurrentCandidate(matchList); 
    950     else db.discardCurrent(); 
    951              
    952     index = db.next(); 
    953   } 
    954   return 1; 
    955 } 
    956  
    957 // class Algo_hash_full_corners(Algo_hash): 
    958  
    959 //     def __init__(boardsize): 
    960 //         Algo_hash.__init__(boardsize, 
    961 //                            [[0,0,18,18, 30], [0,0,6,6, 25], [0,12,6,18, 25], [12,0,18,6, 25], [12,12,18,18, 25]], 
    962 //                            'hash') 
    963  
    964  
    965 // class Algo_hash_sides(Algo_hash): 
    966  
    967 //     def __init__(boardsize): 
    968 //         poslist = [] 
    969 //         Algo_hash.__init__(poslist, 'hashC') 
    970  
    971  
    972  
    973 // class Algo_hash_center(Algo_hash): 
    974  
    975 //     def __init__(boardsize): 
    976 //         poslist = [] 
    977 //         Algo_hash.__init__(poslist, 'hashS') 
    978  
    979  
    980  
    981  
    982 UIntervals::UIntervals(intervs = []) { 
    983   data = intervs; 
    984 } 
    985  
    986  
    987 void UIntervals::first() { 
    988   if (data->size()) return data[0].first; 
    989   else return -1; // FIXME ?! 
    990 } 
    991  
    992 void UIntervals::append(int interv_start, int interv_end) { 
    993   data.push_back(pair<int,int>(interv_start, interv_end)); 
    994 } 
    995  
    996  
    997 void UIntervals::inters(UIntervals& uinterv) { 
    998   int current2low = 0; 
    999   int current2high = 0; 
    1000  
    1001   vector<pair<int,int>> newUInt(); 
    1002  
    1003   for(int current1=0; current1 < data.size(); current1++) { 
    1004     while (current2low < uinterv.data.size && !(uinterv.data[current2low].second > data[current1].first)) 
    1005       current2low++; 
    1006     current2high = current2low; 
    1007     while (current2high < uinterv.data.size() && uinterv.data[current2high].first < data[current1].second) 
    1008       current2high++; 
    1009     current2high--; 
    1010  
    1011     if (current2low == uinterv.data.size()) break; 
    1012     if (current2high < current2low) continue; 
    1013  
    1014     newUInt.append(max(self.data[current1][0], uinterv.data[current2low][0]), 
    1015                  min(self.data[current1][1], uinterv.data[current2low][1])); 
    1016  
    1017     for(int c=current2low+1; c < current2high; c++) 
    1018       newUInt.append(uinterv.data[c].first, uninterv.data[c].second); 
    1019  
    1020     if (current2high > current2low) 
    1021       newUInt.append(uinterv.data[current2high].first, min(uinterv.data[current2high].second, data[current1].second)); 
    1022  
    1023     current2low = current2high; 
    1024   } 
    1025   data = newUInt; 
    1026 } 
    1027  
    1028 void UIntervals::isEmpty() { 
    1029   int isEmpty = 1; 
    1030   for(int i=0; i<data.size(); i++)  
    1031     if (data[i].first < data[i].second) isEmpty = 0; 
    1032   return isEmpty; 
    1033 } 
    1034  
    1035  
    1036  
    1037 Algo_intervals::Algo_intervals(int bsize) { 
    1038   boardsize = bsize; 
    1039 }                         
    1040  
    1041  
    1042 void Algo_intervals::initialize_process(int l) { 
    1043  
    1044   movesArr = vector<long>(); 
    1045   moveIntsArr = vector<long>(); 
    1046 } 
    1047  
    1048 void Algo_intervals::newgame_process() { 
    1049   counter = 0; 
    1050   moves = []; 
    1051   for(int i=0; i<boardsize*boardsize; i++) moves.append([]); 
    1052   ignore = 0; 
    1053 } 
    1054  
    1055 void Algo_intervals::AB_process(int x, int y) { 
    1056   if (ignore) return; 
    1057   moves[boardsize*x+y]->push_back(counter | FLAG_BLACK); 
    1058 } 
    1059  
    1060  
    1061 void Algo_intervals::AW_process(int x, int y) { 
    1062   if (ignore) return; 
    1063   moves[boardsize*x+y]->push_back(counter | FLAG_WHITE); 
    1064 } 
    1065  
    1066 void Algo_intervals::AE_process(int x, int y, char removed) { 
    1067   if (ignore) return; 
    1068   self.moves[self.boardsize*x+y]->push_back(counter | FLAG_REMOVE); 
    1069 } 
    1070  
    1071 void Algo_intervals::endOfNode_process() { 
    1072   if (ignore) return; 
    1073   counter++; 
    1074 } 
    1075  
    1076 void Algo_intervals::B_process(int x, int y, cap) { 
    1077   if (ignore) return; 
    1078   moves[self.boardsize*x+y]->push_back(counter | FLAG_BLACK); 
    1079   for(c in cap) 
    1080     moves[self.boardsize*c[0] + c[1]]->push_back(counter | FLAG_REMOVE); 
    1081 } 
    1082  
    1083 void Algo_intervals::W_process(int x, int y, cap) { 
    1084   if (ignore) return; 
    1085   moves[self.boardsize*x+y]->push_back(counter | FLAG_WHITE); 
    1086   for(c in cap) 
    1087     moves[self.boardsize*c[0] + c[1]]->push_back(counter | FLAG_REMOVE); 
    1088 } 
    1089  
    1090 void Algo_intervals::branchpoint_process() { 
    1091 } 
    1092  
    1093  
    1094 void Algo_intervals::endOfVariation_process() { 
    1095   ignore = 1; 
    1096 } 
    1097  
    1098  
    1099 void Algo_intervals::endgame_process() { 
    1100   for(int x=0; x < boardsize; x++) { 
    1101     for(int y=0; y < boardsize; y++) { 
    1102       if (!moves[self.boardsize*x+y]->size()) 
    1103       movesArr.push_back(0); 
    1104       else if (moves[self.boardsize*x+y]->size() == 1) { 
    1105       long d = (*moves[self.boardsize*x+y])[0]; 
    1106       self.movesArr.append(d); 
    1107       } 
    1108       else { 
    1109       vector<int>* mvs = moves[self.boardsize*x+y]; 
    1110       long d = moveIntsArr.size() | FLAG_POINTER; 
    1111  
    1112       vector<long> Blist; 
    1113       vector<long> Wlist; 
    1114       vector<long> Elist; 
    1115  
    1116       Elist.push_back(0); 
    1117  
    1118       int moveIndex = 0; 
    1119       while (moveIndex < mvs.size()) { 
    1120         if (mvs[moveIndex] & FLAG_BLACK) { 
    1121           d = d | FLAG_BLACK; 
    1122           Blist.push_back(mvs[moveIndex] & ~FLAG_BLACK); 
    1123           Elist.push_back(mvs[moveIndex] & ~FLAG_BLACK); 
    1124           if (moveIndex + 1 < mvs->size()) { 
    1125             Blist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE)); 
    1126             Elist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE)); 
    1127           } 
    1128           else Blist.push_back(MAXNOMOVES); 
    1129         } 
    1130         if (mvs[moveIndex] & FLAG_WHITE) { 
    1131           d = d | FLAG_WHITE; 
    1132           Wlist.push_back(mvs[moveIndex] & ~FLAG_WHITE); 
    1133           Elist.push_back(mvs[moveIndex] & ~FLAG_WHITE); 
    1134           if (moveIndex + 1 < mvs->size()) { 
    1135             Wlist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE)); 
    1136             Elist.push_back(mvs[moveIndex+1] & ~(FLAG_BLACK|FLAG_WHITE|FLAG_REMOVE)); 
    1137           } 
    1138           else Wlist.append(MAXNOMOVES); 
    1139         } 
    1140         moveIndex += 2; 
    1141       } 
    1142           
    1143       if ((!Blist.size() || Blist[Blist.size()-1] != MAXNOMOVES) && 
    1144           (!Wlist.size() || Wlist[Wlist.size()-1] != MAXNOMOVES)) 
    1145         Elist.push_back(MAXNOMOVES); 
    1146  
    1147       moveIntsArr.push_back(Blist.size()); 
    1148       moveIntsArr.push_back(Wlist.size()); 
    1149       moveIntsArr.push_back(Elist.size()); 
    1150       moveIntsArr.extend(Blist); 
    1151       moveIntsArr.extend(Wlist); 
    1152       moveIntsArr.extend(Elist); 
    1153  
    1154       movesArr.push_back(d); 
    1155       } 
    1156     } 
    1157   } 
    1158 } 
    1159  
    1160 void Algo_intervals::finalize_process(datap) { 
    1161   // FIXME 
    1162       extract datap0, datap1 from datap 
    1163        
    1164       String fn = datap0 + "/movesarr" + datap1 + ".db"; // FIXME: linux specific!? 
    1165       ofstream file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc 
    1166   file.write(movesArr, movesArrSize); 
    1167   file.close(); 
    1168        
    1169       fn = datap0 + "/moveints" + datap1 + ".db"; // FIXME: linux specific!? 
    1170       file(fn, ios::out|ios::trunc|ios::binary) // FIXME: careful with ios::trunc 
    1171   file.write(moveIntsArr, moveIntsArrSize); 
    1172   file.close(); 
    1173          
    1174 }         
    1175  
    1176  
    1177 int Algo_intervals::retrieve_db(datap) { 
    1178       String fn = ... "/movesarr" ...; // FIXME 
    1179       ifstream file (fn, ios::in|ios::binary|ios::ate); 
    1180       if (file.is_open()) { 
    1181               ifstream::pos_type size = file.tellg(); 
    1182               delete [] movesArr; 
    1183               movesArr = new char[size]; // FIXME: not a char array? 
    1184               file.seekg (0, ios::beg); 
    1185               file.read (memblock, size); 
    1186               file.close(); 
    1187       } 
    1188   else { 
    1189               cout << "Unable to open file"; 
    1190         return 0; 
    1191       } 
    1192       String fn = ... "/moveints" ...; // FIXME 
    1193       ifstream file (fn, ios::in|ios::binary|ios::ate); 
    1194       if (file.is_open()) { 
    1195               ifstream::pos_type size = file.tellg(); 
    1196               delete [] moveIntsArr; 
    1197               moveIntsArr = new char[size]; // FIXME: not a char array? 
    1198               file.seekg (0, ios::beg); 
    1199               file.read (memblock, size); 
    1200               file.close(); 
    1201       } 
    1202   else { 
    1203               cout << "Unable to open file"; 
    1204         return 0; 
    1205       } 
    1206   return 0; 
    1207 } 
    1208  
    1209 void Algo_intervals::getUInterv(mves, vector<long> mves1, int gameno, int x, int y, char color) { 
    1210  
    1211   UIntervals UInterv(); 
    1212   int typeInterv = 0; 
    1213   long d = mves[gameno*boardsize*boardsize + boardsize*x + y]; 
    1214  
    1215   if (d & FLAG_POINTER) { 
    1216          
    1217     if (color == 'X' && !(d & FLAG_BLACK)) return 0, UIntervals(); 
    1218     if (color == 'O' && !(d & FLAG_WHITE)) return 0, UIntervals(); 
    1219      
    1220    long p = d & MAXNOMOVES; 
    1221    long lenB = moves1[p]; 
    1222    long lenW = moves1[p+1]; 
    1223    long lenE = moves1[p+2]; 
    1224    long start; 
    1225    long length; 
    1226  
    1227    if (color == 'X') { 
    1228      start = p + 3; 
    1229      length = lenB; 
    1230    } 
    1231    else if (color == 'O') { 
    1232      start = p + 3 + lenB; 
    1233      length = lenW; 
    1234    } 
    1235    else if (color == '.') { 
    1236      start = p + 3 + lenB + lenW; 
    1237      length = lenE; 
    1238    } 
    1239  
    1240    l = []; 
    1241    for(int i=0; i<length/2; i++)  
    1242      l.append((moves1[start+2*i], moves1[start+2*i+1])); 
    1243  
    1244    if (l[-1][1] == MAXNOMOVES) typeInterv = length-1; 
    1245    else typeInterv = length; 
    1246    return typeInterv, UIntervals(l); 
    1247   } 
    1248   else { 
    1249     if (color == 'X' && (d & FLAG_BLACK)) 
    1250       return 1, UIntervals([( d & MAXNOMOVES , MAXNOMOVES)]); 
    1251     else if (color == 'O' && (d & FLAG_WHITE)) 
    1252       return 1, UIntervals([( d & MAXNOMOVES , MAXNOMOVES)]); 
    1253     else if (color == '.') { 
    1254       if (!d) return -1, UIntervals([(0, MAXNOMOVES)]); 
    1255       else return 1, UIntervals([(0, d & MAXNOMOVES)]); 
    1256     } 
    1257   } 
    1258   return 0, UIntervals(); 
    1259 } 
    1260   
    1261  
    1262 void Algo_intervals::search(patternList, options, db, 
    1263                           continuations, contLabelsIndex, contLabels, 
    1264                           progBar, progStart, progEnd) { 
    1265   int ctr = 0; 
    1266   int numOfHits = 0; 
    1267   int overallSwitched = 0; 
    1268   int Bwins = 0; 
    1269   int Wwins = 0; 
    1270   int index = db.start(); 
    1271  
    1272   if (!self.retrieve_db(db.datapath)) { 
    1273     printf("Error!\n"); // FIXME 
    1274     return; 
    1275   } 
    1276    
    1277   int movelimit = MAXNOMOVES; 
    1278   if (options.has_key('movelimit')) movelimit = options['movelimit']; 
    1279   int showColorSwap = 1; 
    1280   if (options.has_key('showcolorswap')) showColorSwap = options['showcolorswap']; 
    1281    
    1282   //  moves, moves1 = self.movesArr, self.moveIntsArr; 
    1283  
    1284   while (index != -1) { 
    1285     ctr++; 
    1286  
    1287     matchList = db.getCurrentMatchlist(); 
    1288     result = []; 
    1289     int numOfSwitched = 0; 
    1290              
    1291     if (progBar && !(ctr % 10)) 
    1292       progBar.redraw((progEnd-progStart)*ctr/len(db.current) + progStart); 
    1293              
    1294     for(m in matchList) { 
    1295       Pattern p = patternList.get(m[0]); 
    1296       a0, a1 = m[1]; 
    1297                  
    1298       UIntervals currentUInterv([(0, self.movelimit)]); 
    1299  
    1300       toDo = {}; 
    1301       cont = [(MAXNOMOVES, -1,-1)]; 
    1302       int i = 0; 
    1303       int j = 0; 
    1304  
    1305       while (i < p.sizeX && !currentUInterv.isEmpty()) { 
    1306        
    1307       if (p.data[i][j] == '*') { 
    1308         Bint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1]; 
    1309         if (Bint.data) cont.extend([(x,i,j) for x in [z[0] for z in Bint.data]]); 
    1310         Wint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1]; 
    1311         if (Wint.data) cont.extend([(x,i,j) for x in [z[0] for z in Wint.data]]); 
    1312       } 
    1313       else if p.data[i][j] == 'x': printf("oops\n"); // FIXME 
    1314       else if p.data[i][j] == 'o': printf("oops\n"); // FIXME 
    1315                          
    1316       else { 
    1317         typeInt, nextInt = self.getUInterv(moves, moves1, index, i+a0, j+a1, p.data[i][j]); 
    1318                          
    1319         if (typeInt == -1) ; 
    1320         else if (typeInt == 0) currentUInterv = UIntervals(); 
    1321         else if (typeInt == 1) { 
    1322           if (p.data[i][j] == '.' && cont[0][0] > nextInt.data[0][1]) { 
    1323             Bi = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1]; 
    1324             Wi = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1]; 
    1325             counter = nextInt.data[0][1]; 
    1326             cont[0] = (nextInt.data[0][1], i, j); 
    1327           } 
    1328           currentUInterv.inters(nextInt); 
    1329         } 
    1330         else { 
    1331           if (toDo.has_key(typeInt)) toDo[typeInt].append((i,j,nextInt)); 
    1332           else toDo[typeInt] = [(i, j, nextInt)]; 
    1333         } 
    1334       }       
    1335       j++; 
    1336       if (j == p.sizeY) { 
    1337         j = 0; 
    1338         i++; 
    1339       } 
    1340       } 
    1341  
    1342       toDoList = []; 
    1343       for(ii in toDo.keys()) toDoList.extend(toDo[ii]); 
    1344  
    1345       while (toDoList && !currentUInterv.isEmpty()) { 
    1346       i, j, nextInt = toDoList[0]; 
    1347       del toDoList[0]; 
    1348  
    1349       currentUInterv.inters(nextInt); 
    1350       if (currentUInterv.isEmpty()) break; 
    1351                      
    1352       if (p.data[i][j] == 'X') Bint = nextInt; 
    1353       else Bint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'X')[1]; 
    1354       if (Bint.data) cont.extend([(x,i,j) for x in [z[0] for z in Bint.data]]); 
    1355       if (p.data[i][j] == 'O') Wint = nextInt; 
    1356       else Wint = self.getUInterv(moves, moves1, index, i+a0, j+a1, 'O')[1]; 
    1357       if (Wint.data) cont.extend([(x,i,j) for x in [z[0] for z in Wint.data]]); 
    1358       } 
    1359        
    1360       if (!currentUInterv.isEmpty()) { 
    1361  
    1362       cont.sort(); 
    1363       for(counter, x, y in cont) 
    1364         if (counter > currentUInterv.first()) break; 
    1365  
    1366       if (counter == MAXNOMOVES || counter <= currentUInterv.first()) { 
    1367         hit = 1; 
    1368         label = ''; 
    1369         switched = p.colorSwitch; 
    1370       } 
    1371       else { 
    1372         Xint = (m[1][0], m[1][0] + patternList.get(m[0]).sizeX); 
    1373         Yint = (m[1][1], m[1][1] + patternList.get(m[0]).sizeY); 
    1374  
    1375         Bint = self.getUInterv(moves, moves1, index, x+a0, y+a1, 'X')[1]; 
    1376         Wint = self.getUInterv(moves, moves1, index, x+a0, y+a1, 'O')[1]; 
    1377         if (counter in [z[0] for z in Bint.data]) co = 'W';   // !!! FIXME (cf. Algo_movelist.search) 
    1378         else if (counter in [z[0] for z in Wint.data]) co = 'B'; // !!! 
    1379         else raise Exception; // FIXME 
    1380                          
    1381         hit, label, contLabelsIndex, switched =\ 
    1382           patternList.updateContinuations(m[0], x+a0, y+a1, co, Xint, Yint, 
    1383                                           currentUInterv.first(), counter-1, 
    1384                                           continuations, contLabels, contLabelsIndex, 
    1385                                           db.getCurrentWinner()); 
    1386       } 
    1387        
    1388       if (hit) { 
    1389         numOfSwitched += switched; 
    1390         if (showColorSwap && switched) result.append(str(currentUInterv.first())+label+'-'); 
    1391         else result.append(str(currentUInterv.first())+label); 
    1392       } 
    1393       } 
    1394     } 
    1395  
    1396     if (result) { 
    1397       result.sort(); 
    1398       db.makeCurrentHit(join(result, ', ')); 
    1399       numOfHits = numOfHits + len(result); 
    1400       overallSwitched += numOfSwitched; 
    1401              
    1402       if (db.getCurrentWinner() == 'B') { 
    1403       Bwins = Bwins + len(result) - numOfSwitched; 
    1404       Wwins = Wwins + numOfSwitched; 
    1405       } 
    1406       else if (db.getCurrentWinner() == 'W') { 
    1407       Bwins = Bwins + numOfSwitched; 
    1408       Wwins = Wwins + len(result) - numOfSwitched; 
    1409       } 
    1410     } 
    1411     else db.discardCurrent(); 
    1412        
    1413     index = db.next(); 
    1414   } 
    1415   return numOfHits, Bwins, Wwins, overallSwitched; 
    1416 } 
    1417  
    1418  
     693// Algo_hash::Algo_hash(int bsize, plist, char* fname) : ALgorithm(bsize) { 
     694//   poslist = [[0,0] + p for p in plist]; 
     695//   filename = new char[strlen(fname)+1]; 
     696//   strcpy(filename, fname); 
     697// } 
     698//  
     699// Algo_hash::~Algo_hash() { 
     700//   delete [] filename; 
     701// } 
     702//  
     703// void Algo_hash::initialize_process(l) { 
     704//   hash_global = hashTable(l, self.filename); 
     705//   gameCtr = 0; 
     706// } 
     707//          
     708// void Algo_hash::newgame_process() { 
     709//  
     710//   for (p in self.poslist) { 
     711//     p[0] = 0; 
     712//     p[1] = 0; 
     713//   } 
     714//  
     715//   hash_global.newCtr(gameCtr); 
     716//   branchpoints = []; 
     717// } 
     718//  
     719// void Algo_hash::AB_process(int x, int y) { 
     720//   for (p in self.poslist) { 
     721//     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
     722//       p[0]++; 
     723//       p[1] += hashTable.hash_value[(x,y)]; 
     724//     } 
     725//   } 
     726// } 
     727//  
     728// void Algo_hash::AW_process(int x, int y) { 
     729//   for (p in self.poslist) { 
     730//     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
     731//       p[0]++; 
     732//       p[1] -= hashTable.hash_value[(x,y)]; 
     733//     } 
     734//   } 
     735// }                  
     736//  
     737// void Algo_hash::AE_process(int x, int y, char removed) { 
     738//   int epsilon; 
     739//   if (removed == 'B') epsilon = -1; 
     740//   else epsilon = 1; 
     741//    
     742//   for (p in self.poslist) { 
     743//     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
     744//       p[0]--; 
     745//       p[1] += epsilon * hashTable.hash_value[(x,y)]; 
     746//     } 
     747//   } 
     748// } 
     749//  
     750// void Algo_hash::endOfNode_process() { 
     751//   for(p in self.poslist) 
     752//     if (p[0] <= p[6]) self.hash_global.append(p[1]); 
     753// } 
     754//  
     755// void Algo_hash::B_process(int x, int y, cap) { 
     756//   self.move_process(x, y, cap, 1); 
     757// } 
     758//  
     759// void Algo_hash::W_process(int x, int y, cap) { 
     760//   self.move_process(x, y, cap, -1); 
     761// } 
     762//  
     763// void Algo_hash::move_process(int x, int y, cap, epsilon) { 
     764//   for (p in self.poslist) 
     765//     if (p[2] <= x && x <= p[4] && p[3] <= y && y <= p[5]) { 
     766//       p[0]++; 
     767//       p[1] += epsilon * hashTable.hash_value[(x,y)]; 
     768//     } 
     769//    
     770//   for (c in cap) { 
     771//     for(p in self.poslist)  
     772//       if (p[2] <= c[0] && c[0] <= p[4] && p[3] <= c[1] && c[1] <= p[5]) { 
     773//    p[0] -= 1; 
     774//    p[1] += epsilon * hashTable.hash_value[c]; 
     775//       } 
     776//   } 
     777// } 
     778//  
     779// void Algo_hash::branchpoint_process() { 
     780//   branchpoints.append(deepcopy(self.poslist)); 
     781// } 
     782//  
     783// void Algo_hash::endOfVariation_process() { 
     784//   poslist = self.branchpoints.pop(); 
     785// } 
     786//  
     787// void Algo_hash::endgame_process() { 
     788//   gameCtr++; 
     789// } 
     790//  
     791// void Algo_hash::finalize_process(PyObject* datap) { 
     792//   hash_global.newCtr(gameCtr); 
     793//   hash_global.sortedOutput(datap); 
     794// } 
     795//  
     796//  
     797// long Algo_hash::compute_hashkey(Pattern pattern, type) { 
     798//  
     799//   int numOfStones = 0; 
     800//  
     801//   a0,b0,a1,b1, maxNumOfStones = type; 
     802//   long hashkey = 0; 
     803//              
     804//   for(int i=a0, i<a1+1; i++) { 
     805//     for(int j=b0; j<b1+1; j++) { 
     806//       if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] in ['x', 'o', '*']) 
     807//    return NOT_HASHABLE; 
     808//       else if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] == 'X') { 
     809//    hashkey += hashTable.hash_value[(i,j)]; 
     810//    numOfStones += 1; 
     811//       } 
     812//       else if (pattern.data[i-pattern.anchors[0][0]][j-pattern.anchors[0][1]] == 'O') { 
     813//    hashkey -= hashTable.hash_value[(i,j)]; 
     814//    numOfStones += 1; 
     815//       } 
     816//     } 
     817//     if numOfStones > maxNumOfStones: return NOT_HASHABLE; 
     818//   } 
     819//   return hashkey; 
     820// } 
     821//  
     822// int Algo_hash::retrieve_db(PyObject* datap) { 
     823//    String fn = ... filename ...; // FIXME 
     824//    ifstream file (fn, ios::in|ios::binary|ios::ate); 
     825//    if (file.is_open()) { 
     826//            ifstream::pos_type size = file.tellg(); 
     827//            delete [] hash; 
     828//            hash = new char[size]; // FIXME: not a char array? 
     829//            file.seekg (0, ios::beg); 
     830//            file.read (memblock, size); 
     831//            file.close(); 
     832//    } 
     833//   else { 
     834//            cout << "Unable to open file"; 
     835//      return 0; 
     836//    } 
     837//    String fn = ... filename + "T" ...; // FIXME 
     838//    ifstream file (fn, ios::in|ios::binary|ios::ate); 
     839//    if (file.is_open()) { 
     840//            ifstream::pos_type size = file.tellg(); 
     841//            delete [] hashT; 
     842//            hashT = new char[size]; 
     843//            file.seekg (0, ios::beg); 
     844//            file.read (memblock, size); 
     845//            file.close(); 
     846//    } 
     847//   else { 
     848//            cout << "Unable to open file"; 
     849//      return 0; 
     850//    } 
     851//   return 0; 
     852// } 
     853//  
     854// void Algo_hash::search(patternList, options, db, progBar, progStart, progEnd) { 
     855//   for(int i=0; i<patternList.size(); i++) { 
     856//     Pattern pattern = patternList.get(i); 
     857//     pattern_hashkeys = {}; 
     858//              
     859//     for(int a0=pattern.left; a0<=pattern.right; a0++) { 
     860//       for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
     861//    pattern_hashkeys[(a0,a1)] = []; 
     862//    for(p in self.poslist) { 
     863//      if (a0 <= p[2] && a0+pattern.sizeX >= p[4] a1 <= p[3] && a1+pattern.sizeY >= p[5]) { 
     864//        hk = self.compute_hashkey(pattern, p[2:]); 
     865//  
     866//        if (hk != NOT_HASHABLE) pattern.hashkeys[(a0,a1)].append([hk]); 
     867//      } 
     868//    } 
     869//    if (!pattern.hashkeys[(a0,a1)]) return; 
     870//       } 
     871//     } 
     872//   } 
     873//          
     874//   if (!self.retrieve_db(db.datapath)) { 
     875//     printf("error\n"); // FIXME 
     876//     return; 
     877//   } 
     878//          
     879//   for(int N=0; N<patternList.size(); N++) { 
     880//     Pattern pattern = patternList.get(N); 
     881//              
     882//     for(int a0=pattern.left; a0<=pattern.right; a0++) { 
     883//       for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
     884//              
     885//    for(int hk=0; hk<len(pattern.hashkeys[(a0,a1)]); hk++) { 
     886//  
     887//      int hashkey = pattern.hashkeys[(a0,a1)][hk][0]; 
     888//      int start = 0; 
     889//      int end = len(self.hashT)/2; 
     890//                    
     891//      int hash_start; 
     892//      int hash_end; 
     893//  
     894//      while (start < end) { 
     895//        int help = self.hashT[2*((start+end)/2)]; 
     896//        if (help == hashkey) { 
     897//          hash_start = self.hashT[2*((start+end)/2)+1]; 
     898//          if (2*((start+end)/2)+3 >= len(self.hashT)) hash_end = len(hash); 
     899//          else hash_end = self.hashT[2*((start+end)/2)+3]; 
     900//  
     901//          pattern.hashkeys[(a0,a1)][hk].extend([hash_start, hash_start, hash_end]); 
     902//          break; 
     903//        } 
     904//        else if (help > hashkey) end = (start+end)/2; 
     905//        else if (help < hashkey) start = (start+end)/2 + 1; 
     906//      } 
     907//    } 
     908//       } 
     909//     } 
     910//   } 
     911//  
     912//   int index = db.start(); 
     913//   int gameCounter = 0; 
     914//          
     915//   while (index != -1) { 
     916//     gameCounter++; 
     917//     if (progBar && !(gameCounter % 50)) 
     918//       progBar.redraw((progEnd-progStart)*gameCounter/len(db.current) + progStart); 
     919//  
     920//     matchList = []; 
     921//     for(int N=0; N<patternList.size(); N++) { 
     922//       Pattern pattern = patternList.get(N); 
     923//       for(int a0=pattern.left; a0<=pattern.right; a0++) { 
     924//    for(int a1=pattern.top; a1<=pattern.bottom; a1++) { 
     925//      int matchPossible = 1; 
     926//      for(int hk=0; hk<len(pattern.hashkeys[(a0,a1)]); hk++) { 
     927//        l = pattern.hashkeys[(a0,a1)][hk]; 
     928//        if (len(l) == 1) { 
     929//          matchPossible = 0; 
     930//          break; 
     931//        } 
     932//           &