00001 #ifndef _PD_NTESUKI_TABLE_H
00002 #define _PD_NTESUKI_TABLE_H
00003 #include "osl/ntesuki/ntesukiRecord.h"
00004 #include "osl/ntesuki/ntesukiMove.h"
00005 #include "osl/misc/carray.h"
00006 #include "osl/stl/hash_set.h"
00007 #include "osl/pathEncoding.h"
00008 #include "osl/hash/hashKey.h"
00009 #include "osl/stl/hash_map.h"
00010 #include "osl/stl/slist.h"
00011 #include <boost/scoped_ptr.hpp>
00012 #include <stdexcept>
00013
00014 namespace osl
00015 {
00016 namespace stl
00017 {
00018 template <>
00019 struct hash<Position>{
00020 unsigned long operator()(const Position& p) const
00021 {
00022 return p.uintValue();
00023 }
00024 };
00025 }
00026
00027 namespace ntesuki
00028 {
00032 struct TableFull : std::runtime_error
00033 {
00034 TableFull() : std::runtime_error("table full")
00035 {
00036 }
00037 };
00038
00043 struct RootStateNotSet : std::runtime_error
00044 {
00045 RootStateNotSet () : std::runtime_error("root node not set")
00046 {
00047 }
00048 };
00052 class NtesukiTable
00053 {
00054 private:
00055 typedef hash_map<SignatureKey, NtesukiRecord::RecordList> ntesuki_hash_map;
00056
00057 public:
00058 class Table : public ntesuki_hash_map
00059 {
00060 public:
00061 unsigned int capacity, default_gc_size;
00062 bool verbose, no_gc, gc_request;
00063 unsigned int numEntry, numCacheHit, gcCount;
00064 NtesukiRecord *root;
00065 boost::scoped_ptr<NumEffectState> rootState;
00066 static int largeGCCount;
00067
00068 Table(unsigned int capacity,
00069 unsigned int default_gc_size,
00070 bool verbose);
00071
00072 ~Table();
00073
00081 NtesukiRecord *allocate(const HashKey& key,
00082 const PieceStand& white_stand,
00083 signed short distance);
00084
00091 NtesukiRecord *find(const HashKey& key);
00092
00096 void erase(const HashKey key);
00097
00101 template <class F> void forEachRecord(F& f);
00102 template <class F> void forEachRecordFrom(F&,
00103 NumEffectState&,
00104 NtesukiRecord *);
00105 template <class F> void forEachRecordFromRoot(F& f);
00106
00111 void collectGarbage(unsigned int gc_size);
00112 };
00113
00114
00115 private:
00116 boost::scoped_ptr<Table> table;
00117 bool verbose;
00118
00119 public:
00120 typedef NtesukiRecord record_t;
00121
00122 struct HashPathEncoding
00123 {
00124 unsigned long operator()(PathEncoding const& pe) const
00125 {
00126 return pe.getPath();
00127 }
00128 };
00129 typedef hash_set<PathEncoding, HashPathEncoding> PathSet;
00130
00131 std::vector<int> depths;
00132
00136 NtesukiTable(unsigned int capacity,
00137 unsigned int default_gc_size=0,
00138 bool verbose=false);
00139 ~NtesukiTable();
00140
00141 void clear()
00142 {
00143 table->clear();
00144 }
00145
00146 Table::const_iterator begin() const
00147 {
00148 return table->begin();
00149 }
00150 Table::const_iterator end() const
00151 {
00152 return table->end();
00153 }
00154
00160 NtesukiRecord *allocateRoot(const HashKey& key,
00161 const PieceStand& white_stand,
00162 signed short distance,
00163 const NumEffectState* root_state = NULL)
00164 {
00165 table->root = table->allocate(key, white_stand, distance);
00166 if (root_state)
00167 {
00168 table->rootState.reset(new NumEffectState(*root_state));
00169 }
00170 return table->root;
00171 }
00172
00173 NtesukiRecord *allocateWithMove(NtesukiRecord* record,
00174 const NtesukiMove& move)
00175 {
00176
00177 PieceStand white_stand = record->white_stand;
00178 const Move m = move.getMove();
00179 if (!move.isPass() && m.player())
00180 {
00181 if (m.isDrop())
00182 {
00183 white_stand.sub(m.ptype());
00184 }
00185 else if (m.capturePtype() != PTYPE_EMPTY)
00186 {
00187 white_stand.add(unpromote(m.capturePtype()));
00188 }
00189 }
00190 unsigned short child_distance = record->distance + 1;
00191 NtesukiRecord *child = table->allocate(record->key.newHashWithMove(m),
00192 white_stand, child_distance);
00193 if (child)
00194 {
00195 child->distance = std::min(child->distance, child_distance);
00196 child->checkNewParent(record);
00197 }
00198 return child;
00199 }
00200
00204 NtesukiRecord *find(const HashKey& key)
00205 {
00206 return table->find(key);
00207 }
00208
00209 const NtesukiRecord *find(const HashKey& key) const
00210 {
00211 return table->find(key);
00212 }
00213
00217 void erase(const HashKey key)
00218 {
00219 table->erase(key);
00220 }
00221
00225 void collectGarbage(unsigned int gc_size)
00226 {
00227 table->collectGarbage(gc_size);
00228 }
00229
00234 NtesukiRecord *findWithMove(NtesukiRecord *record,
00235 const NtesukiMove& move)
00236 {
00237
00238
00239
00240
00241
00242 if (move.isNormal() && move.isDrop())
00243 {
00244 const Ptype drop_type = unpromote(move.getMove().ptype());
00245 const PieceStand ps = record->getPieceStandSlow(move.getMove()
00246 .player());
00247 if (ps.get(drop_type) == 0)
00248 {
00249 return NULL;
00250 }
00251 }
00252 NtesukiRecord *child = table->find(record->key.newHashWithMove(move.getMove()));
00253 if (child)
00254 {
00255 child->checkNewParent(record);
00256 }
00257 return child;
00258 }
00259
00260 NtesukiRecord *findWithMoveConst(const NtesukiRecord *record,
00261 const NtesukiMove& move)
00262 {
00263
00264
00265
00266
00267
00268 if (move.isNormal() && move.isDrop())
00269 {
00270 const Ptype drop_type = unpromote(move.getMove().ptype());
00271 const PieceStand ps = record->getPieceStandSlow(move.getMove()
00272 .player());
00273 if (ps.get(drop_type) == 0)
00274 {
00275 return NULL;
00276 }
00277 }
00278 return table->find(record->key.newHashWithMove(move.getMove()));
00279 }
00280
00284 template <class F> void forEachRecord(F& f)
00285 {
00286 table->forEachRecord<F>(f);
00287 }
00288
00292 template <class F> void forEachRecordFromRoot(F& f)
00293 {
00294 table->forEachRecordFromRoot<F>(f);
00295 }
00296
00300 unsigned int size() const
00301 {
00302 return table->numEntry;
00303 }
00304
00305 unsigned int capacity() const
00306 {
00307 return table->capacity;
00308 }
00309
00310 void lockGC()
00311 {
00312 table->no_gc = true;
00313 }
00314
00315 void unlockGC()
00316 {
00317 table->no_gc = false;
00318 if (table->gc_request && (table->default_gc_size > 0))
00319 {
00320 table->collectGarbage(table->default_gc_size);
00321 table->gc_request = false;
00322 }
00323 }
00324
00325 bool isVerbose() const;
00326 };
00327 }
00328 }
00329
00330 #endif
00331
00332
00333
00334