[Eliot-dev] eliot/game board_search.cpp [multibyte]

[eliot-dev]

CVSROOT:        /sources/eliot
Module name:    eliot
Branch:         multibyte
Changes by:     Olivier Teulière <address@hidden>      06/01/14 21:02:14

Modified files:
        game           : board_search.cpp 

Log message:
        Optimization over the original algorithm: ignore the current anchor
        if none of the letters in the rack matches the cross set.
        
        This optimization saves more than 6% of the total regression time
        (measured on the total time needed for 100 successive runs of the
        regression)

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/board_search.cpp.diff?only_with_tag=multibyte&tr1=1.9.2.1&tr2=1.9.2.2&r1=text&r2=text

Patches:
Index: eliot/game/board_search.cpp
diff -u eliot/game/board_search.cpp:1.9.2.1 eliot/game/board_search.cpp:1.9.2.2
--- eliot/game/board_search.cpp:1.9.2.1 Tue Jan  3 20:42:13 2006
+++ eliot/game/board_search.cpp Sat Jan 14 21:02:13 2006
@@ -219,6 +219,12 @@
 {
     int row, col, lastanchor;
     Round partialword;
+
+    list<Tile> rackTiles;
+    iRack.getTiles(rackTiles);
+    list<Tile>::const_iterator it;
+    bool match;
+
     for (row = 1; row <= BOARD_DIM; row++)
     {
         partialword.init();
@@ -233,20 +239,35 @@
                  !iTilesMx[row - 1][col].isEmpty() ||
                  !iTilesMx[row + 1][col].isEmpty()))
             {
-                if (!iTilesMx[row][col - 1].isEmpty())
+                // Optimization compared to the original Appel & Jacobson
+                // algorithm: skip Leftpart if none of the tiles of the rack
+                // matches the cross mask for the current anchor
+                match = false;
+                for (it = rackTiles.begin();
+                     !match && it != rackTiles.end(); it++)
                 {
-                    partialword.accessCoord().setCol(lastanchor + 1);
-                    ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
-                                iJokerMx, iRack, partialword, iResults,
-                                Dic_root(iDic), row, lastanchor + 1, col);
+                    if (iCrossMx[row][col].check(*it))
+                    {
+                        match = true;
+                    }
                 }
-                else
+                if (match)
                 {
-                    partialword.accessCoord().setCol(col);
-                    LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
-                             iJokerMx, iRack, partialword, iResults,
-                             Dic_root(iDic), row, col, col -
-                             lastanchor - 1);
+                    if (!iTilesMx[row][col - 1].isEmpty())
+                    {
+                        partialword.accessCoord().setCol(lastanchor + 1);
+                        ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, 
iPointsMx,
+                                    iJokerMx, iRack, partialword, iResults,
+                                    Dic_root(iDic), row, lastanchor + 1, col);
+                    }
+                    else
+                    {
+                        partialword.accessCoord().setCol(col);
+                        LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
+                                 iJokerMx, iRack, partialword, iResults,
+                                 Dic_root(iDic), row, col, col -
+                                 lastanchor - 1);
+                    }
                 }
                 lastanchor = col;
             }