Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

PatternState.hpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file PatternState.hpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #ifndef PATTERNBOARD_HPP
00007 #define PATTERNBOARD_HPP
00008 
00009 #include "Hex.hpp"
00010 #include "HashedPatternSet.hpp"
00011 #include "Pattern.hpp"
00012 #include "StoneBoard.hpp"
00013 
00014 _BEGIN_BENZENE_NAMESPACE_
00015 
00016 //----------------------------------------------------------------------------
00017 
00018 /** Instance of a pattern matching a subset of the board.  */
00019 class PatternHit
00020 {
00021 public:
00022     /** Creates an instance with a single encoded move1, and
00023         move2 is empty. */
00024     PatternHit(const Pattern* pat, HexPoint move);
00025 
00026     /** Creates an instance with a set of encoded move1, and
00027         move2 is empty. */
00028     PatternHit(const Pattern* pat, const std::vector<HexPoint>& moves1);
00029 
00030     /** Creates an instance with two sets of encoded moves. */
00031     PatternHit(const Pattern* pat, 
00032                const std::vector<HexPoint>& moves1,
00033                const std::vector<HexPoint>& moves2);
00034 
00035     /** Returns the pattern. */
00036     const Pattern* pattern() const;
00037 
00038     /** Returns the set of moves the pattern encodes. */
00039     const std::vector<HexPoint>& moves1() const;
00040 
00041     const std::vector<HexPoint>& moves2() const;
00042 
00043 private:
00044 
00045     const Pattern* m_pattern;
00046 
00047     std::vector<HexPoint> m_moves1;
00048 
00049     std::vector<HexPoint> m_moves2;
00050 };
00051 
00052 inline PatternHit::PatternHit(const Pattern* pat, HexPoint move)
00053     : m_pattern(pat),
00054       m_moves1(1, move),
00055       m_moves2()
00056 {
00057 }
00058 
00059 inline PatternHit::PatternHit(const Pattern* pat, 
00060                               const std::vector<HexPoint>& moves1)
00061     : m_pattern(pat),
00062       m_moves1(moves1),
00063       m_moves2()
00064 {
00065 }
00066 
00067 inline PatternHit::PatternHit(const Pattern* pat, 
00068                               const std::vector<HexPoint>& moves1,
00069                               const std::vector<HexPoint>& moves2)
00070     : m_pattern(pat),
00071       m_moves1(moves1),
00072       m_moves2(moves2)
00073 {
00074 }
00075 
00076 inline const Pattern* PatternHit::pattern() const
00077 {
00078     return m_pattern;
00079 }
00080 
00081 inline const std::vector<HexPoint>& PatternHit::moves1() const
00082 {
00083     return m_moves1;
00084 }
00085 
00086 inline const std::vector<HexPoint>& PatternHit::moves2() const
00087 {
00088     return m_moves2;
00089 }
00090 
00091 /** Vector of PatternHits. */
00092 typedef std::vector<PatternHit> PatternHits;
00093 
00094 //----------------------------------------------------------------------------
00095 
00096 /** Data used for pattern matching. */
00097 class PatternMatcherData
00098 {
00099 public:
00100 
00101     /** Returns instance for given board. */
00102     static const PatternMatcherData* Get(const ConstBoard* brd);
00103 
00104     /** Board data is defined on. */
00105     const ConstBoard* brd;
00106 
00107     /** For x: slice in which y resides. */
00108     int played_in_slice[BITSETSIZE][BITSETSIZE];
00109 
00110     /** For x: godel in the slice in which y resides. */
00111     int played_in_godel[BITSETSIZE][BITSETSIZE];
00112 
00113     /** For x, edge y, slice s: set of godels edge hits. */
00114     int played_in_edge[BITSETSIZE][4][Pattern::NUM_SLICES];
00115 
00116     /** Maps a cell's (slice,godel) to a point. */
00117     HexPoint inverse_slice_godel[BITSETSIZE][Pattern::NUM_SLICES][32];
00118 
00119     /** Returns the HexPoint of the position (slice, bit) centered on cell
00120         and rotated by angle. */
00121     HexPoint GetRotatedMove(HexPoint cell, int slice, 
00122                             int bit, int angle) const;
00123 
00124 private:
00125 
00126     /** Constructor. */
00127     PatternMatcherData(const ConstBoard* brd);
00128 
00129     void Initialize();
00130 };
00131 
00132 //----------------------------------------------------------------------------
00133 
00134 /** Tracks pattern state info on a board. */
00135 class PatternState
00136 {
00137 public:
00138     /** Track the pattern state on the given board. */
00139     explicit PatternState(StoneBoard& brd);
00140 
00141     ~PatternState();
00142 
00143     //-----------------------------------------------------------------------
00144 
00145     /** Returns board state is tracking. */
00146     const StoneBoard& Board() const;
00147 
00148     /** Returns board state is tracking. */
00149     StoneBoard& Board();
00150 
00151     /** Sets the distance to which we update pattern info from the
00152         last played cell; used in Update(cell). Default is
00153         Pattern::MAX_EXTENSION. */
00154     int UpdateRadius() const;
00155 
00156     /** See SetUpdateRadius(). */
00157     void SetUpdateRadius(int radius);
00158 
00159     //-----------------------------------------------------------------------
00160 
00161     /** Computes the pattern checking information for this board
00162         state.  Calls update(cell) for each occupied cell. */
00163     void Update();
00164 
00165     /** Updates the pattern checking information only for the given
00166         move.  Sweeps over all cells updateRadius() distance from
00167         cell. */
00168     void Update(HexPoint cell);
00169 
00170     /** Calls update(cell) for each move in changed, each of which
00171         must correspond to an occupied cell. */
00172     void Update(const bitset_t& changed);
00173 
00174     /** Update only the ring godels of the neighbours of cell. */
00175     void UpdateRingGodel(HexPoint cell);
00176 
00177     //-----------------------------------------------------------------------
00178 
00179     /** Copies state from other. */
00180     void CopyState(const PatternState& other);
00181 
00182     //-----------------------------------------------------------------------
00183 
00184     /** Options controlling pattern matching behavoir at a cell. */
00185     typedef enum 
00186     {
00187         /** Stops the search after first hit. */
00188         STOP_AT_FIRST_HIT, 
00189 
00190         /** Continues search after first hit, storing all results. */
00191         MATCH_ALL 
00192 
00193     } MatchMode;
00194 
00195     //-----------------------------------------------------------------------
00196 
00197     /** Matches the hashed patterns at the specified cell, storing hit
00198         information in hits, using the given matching mode. */
00199     void MatchOnCell(const HashedPatternSet& patset, 
00200                      HexPoint cell, MatchMode mode,
00201                      PatternHits& hits) const;
00202 
00203     /** Matches the hashed patterns on the consider set, returning a
00204         set of cells where at least one pattern matched. Note that
00205         hits must be large enough that it can be indexed by each cell
00206         in consider. Matching mode refers to a single cell, not the
00207         search as a whole; that is, a hit on cell A does not abort the
00208         entire search, it only moves the search on to the remaining
00209         cells.
00210         
00211         @todo Can we switch hits to be a map instead of a vector?
00212         Will a map be too slow?
00213     */
00214     bitset_t MatchOnBoard(const bitset_t& consider, 
00215                           const HashedPatternSet& patset, 
00216                           MatchMode mode, 
00217                           std::vector<PatternHits>& hits) const;
00218 
00219     /** Matches the hashed patterns on the given consider set,
00220         returning a set of cells where at least one pattern
00221         matched. For each cell, the search is aborted after the first
00222         match. No information on the hits is returned. This is a
00223         convience method. */
00224     bitset_t MatchOnBoard(const bitset_t& consider,
00225                           const HashedPatternSet& patset) const;
00226         
00227     //-----------------------------------------------------------------------
00228 
00229     /** Reset the pattern checking statistics. */
00230     void ClearPatternCheckStats();
00231 
00232     /** Return a string containing the pattern checking statistics. */
00233     std::string DumpPatternCheckStats() const;
00234 
00235 private:
00236 
00237     //-----------------------------------------------------------------------
00238 
00239     /** Pattern checking statistics. */
00240     struct Statistics
00241     {
00242         /** Number of pattern checks. */
00243         size_t pattern_checks;
00244 
00245         /** Number of calls to checkRingGodel(). */
00246         size_t ring_checks;
00247 
00248         /** Number of slice checks. */
00249         size_t slice_checks;
00250     };
00251 
00252     //-----------------------------------------------------------------------
00253 
00254     StoneBoard& m_brd;
00255 
00256     const PatternMatcherData* m_data;
00257 
00258     /** See UpdateRadius() */
00259     int m_update_radius;
00260 
00261     int m_slice_godel[BITSETSIZE][BLACK_AND_WHITE][Pattern::NUM_SLICES];
00262 
00263     RingGodel m_ring_godel[BITSETSIZE];
00264 
00265     mutable Statistics m_statistics;
00266 
00267     //-----------------------------------------------------------------------
00268 
00269     /** Non-assignable. */
00270     void operator=(const PatternState& other);
00271     
00272     /** Non-copyable. */
00273     PatternState(const PatternState& other);
00274 
00275     void ClearGodels();
00276 
00277     //-----------------------------------------------------------------------
00278 
00279     bool CheckRotatedSlices(HexPoint cell, 
00280                             const Pattern& pat, int angle) const;
00281 
00282     bool CheckRotatedSlices(HexPoint cell, 
00283                             const RotatedPattern& rotpat) const;
00284         
00285     bool CheckRingGodel(HexPoint cell, 
00286                         const Pattern& pattern, int angle) const;
00287 
00288     bool CheckRingGodel(HexPoint cell, 
00289                         const RotatedPattern& rotpat) const;
00290 
00291     bool CheckRotatedPattern(HexPoint cell, 
00292                              const RotatedPattern& rotpat,
00293                              std::vector<HexPoint>& moves1,
00294                              std::vector<HexPoint>& moves2) const;
00295 };
00296 
00297 inline const StoneBoard& PatternState::Board() const
00298 {
00299     return m_brd;
00300 }
00301 
00302 inline StoneBoard& PatternState::Board()
00303 {
00304     return m_brd;
00305 }
00306 
00307 inline void PatternState::SetUpdateRadius(int radius)
00308 {
00309     HexAssert(1 <= radius);
00310     HexAssert(radius <= Pattern::MAX_EXTENSION);
00311     m_update_radius = radius;
00312 }
00313 
00314 inline int PatternState::UpdateRadius() const
00315 {
00316     return m_update_radius;
00317 }
00318 
00319 //----------------------------------------------------------------------------
00320 
00321 _END_BENZENE_NAMESPACE_
00322 
00323 #endif // PATTERNBOARD_HPP


6 Jan 2011 Doxygen 1.6.3