[Eliot-dev] eliot/game rack.cpp rack.h tile.cpp tile.h [multibyte]

[eliot-dev]

CVSROOT:        /sources/eliot
Module name:    eliot
Branch:         multibyte
Changes by:     Olivier Teulière <address@hidden>      06/01/08 16:58:27

Modified files:
        game           : rack.cpp rack.h tile.cpp tile.h 

Log message:
        Do not use a multiset in Rack, as it generates too many calls to
        Tile::operator<(). The search is now much faster.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/rack.cpp.diff?only_with_tag=multibyte&tr1=1.5.2.2&tr2=1.5.2.3&r1=text&r2=text
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/rack.h.diff?only_with_tag=multibyte&tr1=1.7.2.2&tr2=1.7.2.3&r1=text&r2=text
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/tile.cpp.diff?only_with_tag=multibyte&tr1=1.5.2.4&tr2=1.5.2.5&r1=text&r2=text
http://cvs.savannah.gnu.org/viewcvs/eliot/eliot/game/tile.h.diff?only_with_tag=multibyte&tr1=1.6.2.4&tr2=1.6.2.5&r1=text&r2=text

Patches:
Index: eliot/game/rack.cpp
diff -u eliot/game/rack.cpp:1.5.2.2 eliot/game/rack.cpp:1.5.2.3
--- eliot/game/rack.cpp:1.5.2.2 Sun Jan  8 11:38:52 2006
+++ eliot/game/rack.cpp Sun Jan  8 16:58:27 2006
@@ -26,22 +26,45 @@
  */
 
 #include "rack.h"
+#include "debug.h"
 
+// FIXME: should not be here (duplicated from tile.cpp)
+#define TILES_NUMBER 28
+#define MIN_CODE 1
+
+
+Rack::Rack()
+    : m_tiles(TILES_NUMBER, 0), m_ntiles(0)
+{
+}
 
 void Rack::remove(const Tile &t)
 {
-    multiset<Tile>::const_iterator it = m_tiles.find(t);
-    if (it != m_tiles.end())
-        m_tiles.erase(it);
+    ASSERT(in(t),
+           "The rack does not contain the letter " + convertToMb(t.toChar()));
+    m_tiles[t.toCode()]--;
+    m_ntiles--;
+}
+
+
+void Rack::clear()
+{
+    for (unsigned int i = 0; i < m_tiles.size(); i++)
+    {
+        m_tiles[i] = 0;
+    }
+    m_ntiles = 0;
 }
 
 
 void Rack::getTiles(list<Tile> &oTiles) const
 {
-    multiset<Tile>::const_iterator it;
-    for (it = m_tiles.begin(); it != m_tiles.end(); it++)
+    for (unsigned int i = MIN_CODE; i < m_tiles.size(); i++)
     {
-        oTiles.push_back(*it);
+        for (unsigned int j = 0; j < m_tiles[i]; j++)
+        {
+            oTiles.push_back(Tile::GetTileFromCode(i));
+        }
     }
 }
 
@@ -49,10 +72,12 @@
 wstring Rack::toString()
 {
     wstring rs;
-    multiset<Tile>::const_iterator it;
-    for (it = m_tiles.begin(); it != m_tiles.end(); it++)
+    for (unsigned int i = MIN_CODE; i < m_tiles.size(); i++)
     {
-        rs += it->toChar();
+        for (unsigned int j = 0; j < m_tiles[i]; j++)
+        {
+            rs += Tile::GetTileFromCode(i).toChar();
+        }
     }
     return rs;
 }
Index: eliot/game/rack.h
diff -u eliot/game/rack.h:1.7.2.2 eliot/game/rack.h:1.7.2.3
--- eliot/game/rack.h:1.7.2.2   Sun Jan  8 11:38:52 2006
+++ eliot/game/rack.h   Sun Jan  8 16:58:27 2006
@@ -43,22 +43,24 @@
 class Rack
 {
 public:
-    Rack() {}
+    Rack();
     virtual ~Rack() {}
 
-    int nTiles() const          { return m_tiles.size(); }
+    int nTiles() const          { return m_ntiles; }
     bool isEmpty() const        { return nTiles() == 0; }
 
-    unsigned int in(const Tile &t) const { return m_tiles.count(t); }
-    void add(const Tile &t)     { m_tiles.insert(t); }
+    unsigned int in(const Tile &t) const { return m_tiles[t.toCode()]; }
+    void add(const Tile &t)     { m_tiles[t.toCode()]++; m_ntiles++; }
     void remove(const Tile &t);
-    void clear()                { m_tiles.clear(); }
+    void clear();
     void getTiles(list<Tile> &oTiles) const;
 
     wstring toString();
 
 private:
-    multiset<Tile> m_tiles;
+    /// Vector indexed by tile codes, containing the number of tiles
+    vector<unsigned int> m_tiles;
+    int m_ntiles;
 };
 
 #endif
Index: eliot/game/tile.cpp
diff -u eliot/game/tile.cpp:1.5.2.4 eliot/game/tile.cpp:1.5.2.5
--- eliot/game/tile.cpp:1.5.2.4 Sun Jan  8 13:21:05 2006
+++ eliot/game/tile.cpp Sun Jan  8 16:58:27 2006
@@ -67,9 +67,11 @@
 /***************************
  ***************************/
 
-list<Tile> Tile::m_tilesList;
 const Tile Tile::m_TheJoker(TILE_JOKER);
 const Tile Tile::m_TheDummy(0);
+list<Tile> Tile::m_tilesList;
+vector<Tile> Tile::m_tilesVect(TILES_NUMBER, Tile::dummy());
+bool Tile::m_vectInitialized(false);
 
 
 Tile::Tile(wchar_t c)
@@ -85,7 +87,7 @@
     {
         m_joker = islower(c);
         m_dummy = false;
-        m_char = toupper(c);
+        m_char = towupper(c);
         m_code = m_char - 'A' + 1;
     }
     else
@@ -151,6 +153,20 @@
 }
 
 
+const Tile& Tile::GetTileFromCode(unsigned int iCode)
+{
+    if (!m_vectInitialized)
+    {
+        // XXX: this should be filled from a "language file" instead
+        for (char i = TILE_IDX_START; i <= TILE_IDX_END; i++)
+            Tile::m_tilesVect[i] = Tile(i + 'A' - TILE_IDX_START);
+        m_tilesVect[TILE_IDX_JOKER] = Tile::Joker();
+        m_vectInitialized = true;
+    }
+    return Tile::m_tilesVect[iCode];
+}
+
+
 wchar_t Tile::toChar() const
 {
     if (m_dummy)
@@ -158,7 +174,7 @@
     if (m_joker)
     {
         if (iswalpha(m_char))
-            return tolower(m_char);
+            return towlower(m_char);
         else
             return TILE_JOKER;
     }
Index: eliot/game/tile.h
diff -u eliot/game/tile.h:1.6.2.4 eliot/game/tile.h:1.6.2.5
--- eliot/game/tile.h:1.6.2.4   Sun Jan  8 13:21:05 2006
+++ eliot/game/tile.h   Sun Jan  8 16:58:27 2006
@@ -21,9 +21,11 @@
 #define _TILE_H_
 
 #include <list>
+#include <vector>
 
 using namespace std;
 
+
 /*************************
  * A Tile is the internal representation
  * used within the game library to
@@ -54,6 +56,7 @@
     static const Tile &dummy()  { return m_TheDummy; }
     static const Tile &Joker()  { return m_TheJoker; }
     static const list<Tile>& getAllTiles();
+    static const Tile &GetTileFromCode(unsigned int iCode);
 
     bool operator <(const Tile &iOther) const;
     bool operator ==(const Tile &iOther) const;
@@ -74,8 +77,12 @@
     static const Tile m_TheJoker;
     static const Tile m_TheDummy;
 
-    // List of available tiles
+    /// List of available tiles
     static list<Tile> m_tilesList;
+    /// Vector of tiles indexed by their code, for fast look-up
+    static vector<Tile> m_tilesVect;
+    /// True when m_tilesVect is correctly initialized
+    static bool m_vectInitialized;
 };
 
 #endif