[Eliot-dev] eliot/game board_search.cpp cross.cpp cross.h [cppdic]

[eliot-dev]

CVSROOT:        /cvsroot/eliot
Module name:    eliot
Branch:         cppdic
Changes by:     Olivier Teulière <ipkiss>      07/12/14 12:35:38

Modified files:
        game           : board_search.cpp cross.cpp cross.h 

Log message:
        Several search optimizations (which could have been done a long time 
ago...).
        The number of calls to some functions (like Dictionary::getCode()) 
drops by almost 20% on my test case!

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/eliot/game/board_search.cpp?cvsroot=eliot&only_with_tag=cppdic&r1=1.11.2.4&r2=1.11.2.5
http://cvs.savannah.gnu.org/viewcvs/eliot/game/cross.cpp?cvsroot=eliot&only_with_tag=cppdic&r1=1.6.2.1&r2=1.6.2.2
http://cvs.savannah.gnu.org/viewcvs/eliot/game/cross.h?cvsroot=eliot&only_with_tag=cppdic&r1=1.7.2.2&r2=1.7.2.3

Patches:
Index: board_search.cpp
===================================================================
RCS file: /cvsroot/eliot/eliot/game/board_search.cpp,v
retrieving revision 1.11.2.4
retrieving revision 1.11.2.5
diff -u -b -r1.11.2.4 -r1.11.2.5
--- board_search.cpp    27 Nov 2007 18:01:05 -0000      1.11.2.4
+++ board_search.cpp    14 Dec 2007 12:35:37 -0000      1.11.2.5
@@ -110,9 +110,16 @@
     if (iTilesMx[iRow][iCol].isEmpty())
     {
         if (iDic.isEndOfWord(iNode) && iCol > iAnchor)
+        {
             BoardSearchEvalMove(iBoard, iTilesMx, iPointsMx, iJokerMx,
                                 iResults, ioPartialWord);
+        }
+
+        // Optimization: avoid entering the for loop if no tile can match
+        if (iCrossMx[iRow][iCol].isNone())
+            return;
 
+        bool hasJokerInRack = iRack.in(Tile::Joker());
         for (succ = iDic.getSucc(iNode); succ; succ = iDic.getNext(succ))
         {
             l = Tile(iDic.getChar(succ));
@@ -121,21 +128,21 @@
                 if (iRack.in(l))
                 {
                     iRack.remove(l);
-                    ioPartialWord.addRightFromRack(l, 0);
+                    ioPartialWord.addRightFromRack(l, false);
                     ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
                                 iJokerMx, iRack, ioPartialWord, iResults,
                                 succ, iRow, iCol + 1, iAnchor);
-                    ioPartialWord.removeRightToRack(l, 0);
+                    ioPartialWord.removeRightToRack(l, false);
                     iRack.add(l);
                 }
-                if (iRack.in(Tile::Joker()))
+                if (hasJokerInRack)
                 {
                     iRack.remove(Tile::Joker());
-                    ioPartialWord.addRightFromRack(l, 1);
+                    ioPartialWord.addRightFromRack(l, true);
                     ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
                                 iJokerMx, iRack, ioPartialWord, iResults,
                                 succ, iRow, iCol + 1, iAnchor);
-                    ioPartialWord.removeRightToRack(l, 1);
+                    ioPartialWord.removeRightToRack(l, true);
                     iRack.add(Tile::Joker());
                 }
             }
@@ -144,15 +151,19 @@
     else
     {
         l = iTilesMx[iRow][iCol];
+        wint_t upperChar = towupper(l.toChar());
         for (succ = iDic.getSucc(iNode); succ ; succ = iDic.getNext(succ))
         {
-            if ((wint_t)iDic.getChar(succ) == towupper(l.toChar()))
+            if ((wint_t)iDic.getChar(succ) == upperChar)
             {
                 ioPartialWord.addRightFromBoard(l);
                 ExtendRight(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
                             iJokerMx, iRack, ioPartialWord,
                             iResults, succ, iRow, iCol + 1, iAnchor);
                 ioPartialWord.removeRightToBoard(l);
+                // The letter will be present only once in the dictionary,
+                // so we can stop looping
+                break;
             }
         }
     }
@@ -177,31 +188,32 @@
 
     if (iLimit > 0)
     {
+        bool hasJokerInRack = iRack.in(Tile::Joker());
         for (succ = iDic.getSucc(n); succ; succ = iDic.getNext(succ))
         {
             l = Tile(iDic.getChar(succ));
             if (iRack.in(l))
             {
                 iRack.remove(l);
-                ioPartialWord.addRightFromRack(l, 0);
+                ioPartialWord.addRightFromRack(l, false);
                 
ioPartialWord.accessCoord().setCol(ioPartialWord.getCoord().getCol() - 1);
                 LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
                          iJokerMx, iRack, ioPartialWord, iResults,
                          succ, iRow, iAnchor, iLimit - 1);
                 
ioPartialWord.accessCoord().setCol(ioPartialWord.getCoord().getCol() + 1);
-                ioPartialWord.removeRightToRack(l, 0);
+                ioPartialWord.removeRightToRack(l, false);
                 iRack.add(l);
             }
-            if (iRack.in(Tile::Joker()))
+            if (hasJokerInRack)
             {
                 iRack.remove(Tile::Joker());
-                ioPartialWord.addRightFromRack(l, 1);
+                ioPartialWord.addRightFromRack(l, true);
                 
ioPartialWord.accessCoord().setCol(ioPartialWord.getCoord().getCol() - 1);
                 LeftPart(iBoard, iDic, iTilesMx, iCrossMx, iPointsMx,
                          iJokerMx, iRack, ioPartialWord, iResults,
                          succ, iRow, iAnchor, iLimit - 1);
                 
ioPartialWord.accessCoord().setCol(ioPartialWord.getCoord().getCol() + 1);
-                ioPartialWord.removeRightToRack(l, 1);
+                ioPartialWord.removeRightToRack(l, true);
                 iRack.add(Tile::Joker());
             }
         }
@@ -224,7 +236,7 @@
     vector<Tile> rackTiles;
     iRack.getTiles(rackTiles);
     vector<Tile>::const_iterator it;
-    bool match;
+    vector<Tile>::const_iterator itEnd;
 
     for (row = 1; row <= BOARD_DIM; row++)
     {
@@ -261,13 +273,13 @@
                 // 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++)
+                bool match = false;
+                for (it = rackTiles.begin(); it != rackTiles.end(); it++)
                 {
                     if (iCrossMx[row][col].check(*it))
                     {
                         match = true;
+                        break;
                     }
                 }
                 if (match)

Index: cross.cpp
===================================================================
RCS file: /cvsroot/eliot/eliot/game/cross.cpp,v
retrieving revision 1.6.2.1
retrieving revision 1.6.2.2
diff -u -b -r1.6.2.1 -r1.6.2.2
--- cross.cpp   5 Nov 2006 17:27:03 -0000       1.6.2.1
+++ cross.cpp   14 Dec 2007 12:35:38 -0000      1.6.2.2
@@ -22,26 +22,25 @@
 
 #define CROSS_MASK 0xFFFFFFFF
 
+
 Cross::Cross()
 {
     // The default behaviour is to match everything
     setAny();
 }
 
+
 void Cross::setAny()                   
 { 
     m_mask = CROSS_MASK;
 }
 
+
 bool Cross::isAny() const
 { 
     return m_mask == CROSS_MASK; 
 }
 
-void Cross::setNone()
-{
-    m_mask = 0;
-}
 
 string Cross::getHexContent() const
 {
@@ -51,22 +50,21 @@
     return s;
 }
 
+
 bool Cross::check(const Tile& iTile) const
 {
     return (iTile.isJoker() && m_mask != 0) || (m_mask & (1 << 
iTile.toCode()));
 }
 
+
 void Cross::insert(const Tile& iTile)
 { 
     m_mask |= (1 << iTile.toCode());
 }
 
+
 bool Cross::operator==(const Cross &iOther) const
 {
-    /* 
-     *  if (isAny() || iOther.isAny())
-     *    return isAny() && iOther.isAny();
-     */
     return m_mask == iOther.m_mask;
 }
 

Index: cross.h
===================================================================
RCS file: /cvsroot/eliot/eliot/game/cross.h,v
retrieving revision 1.7.2.2
retrieving revision 1.7.2.3
diff -u -b -r1.7.2.2 -r1.7.2.3
--- cross.h     13 Dec 2007 12:11:07 -0000      1.7.2.2
+++ cross.h     14 Dec 2007 12:35:38 -0000      1.7.2.3
@@ -36,10 +36,10 @@
     Cross();
 
     void setAny();
-    void setNone();
+    void setNone() { m_mask = 0; }
 
     bool isAny() const;
-    bool isNone() const;
+    bool isNone() const { return m_mask == 0; }
 
     bool check(const Tile& iTile) const;