Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

Groups.hpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file Groups.hpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #ifndef GROUPS_HPP
00007 #define GROUPS_HPP
00008 
00009 #include "Hex.hpp"
00010 #include "SafeBool.hpp"
00011 #include "StoneBoard.hpp"
00012 #include <boost/utility.hpp>
00013 
00014 _BEGIN_BENZENE_NAMESPACE_
00015 
00016 //---------------------------------------------------------------------------
00017 
00018 class Groups;
00019 
00020 /** A group on the board. 
00021     
00022     A group is a maximal set of like-colored stones. Groups of 
00023     color EMPTY are always singletons.
00024 */
00025 class Group
00026 {
00027 public:
00028 
00029     /** Creates an empty invalid group. 
00030         Only GroupBuilder can construct valid groups.
00031     */
00032     Group();
00033 
00034     /** Number of stones in group. */
00035     std::size_t Size() const;
00036 
00037     /** Color of the group. */
00038     HexColor Color() const;
00039 
00040     /** Point used as the representative of this group. */
00041     HexPoint Captain() const;
00042 
00043     /** Returns true if point is a member of group, false otherwise. */
00044     bool IsMember(HexPoint point) const;
00045 
00046     /** Returns the members. */
00047     const bitset_t& Members() const;
00048 
00049     /** Returns neighbours. */
00050     const bitset_t& Nbs() const;
00051     
00052     /** Returns the captains of neighboring groups whose color belongs
00053         to colorset. If first time, neighbors in each colorset will be
00054         computed. */
00055     const bitset_t& Nbs(HexColorSet colorset) const;
00056 
00057 private:
00058 
00059     friend class GroupBuilder;
00060 
00061     HexColor m_color;
00062 
00063     HexPoint m_captain;
00064 
00065     bitset_t m_members;
00066 
00067     bitset_t m_nbs;
00068 
00069     /** Pointer to Groups object which this Group belongs. */
00070     const Groups* m_groups;
00071 
00072     /** Indices of neighbouring groups in parent Groups's list of
00073         groups. We don't use pointers because then it would be
00074         difficult to copy a Groups object. */
00075     std::vector<std::size_t> m_nbs_index;
00076 
00077     /** True if the colorset neighbours have been computed yet. */
00078     mutable bool m_colorsets_computed;
00079 
00080     /** Computed colorset neighbours. */
00081     mutable bitset_t m_nbs_colorset[NUM_COLOR_SETS];
00082 
00083     Group(const Groups* groups, HexColor color, HexPoint captain, 
00084           const bitset_t& members, const bitset_t& nbs);
00085 
00086     void ComputeColorsetNbs() const;
00087 };
00088 
00089 inline Group::Group()
00090     : m_captain(INVALID_POINT),
00091       m_groups(0),
00092       m_colorsets_computed(false)
00093 {
00094 }
00095 
00096 /** Used only by GroupBuilder::Build(). */
00097 inline Group::Group(const Groups* groups, HexColor color, HexPoint captain, 
00098                     const bitset_t& members, const bitset_t& nbs)
00099     : m_color(color),
00100       m_captain(captain),
00101       m_members(members),
00102       m_nbs(nbs),
00103       m_groups(groups),
00104       m_colorsets_computed(false)
00105 {
00106 }
00107 
00108 inline std::size_t Group::Size() const
00109 {
00110     /** @todo Cache group size for speed? */
00111     return m_members.count();
00112 }
00113 
00114 inline HexColor Group::Color() const
00115 {
00116     return m_color;
00117 }
00118 
00119 inline HexPoint Group::Captain() const
00120 {
00121     return m_captain;
00122 }
00123 
00124 inline bool Group::IsMember(HexPoint point) const
00125 {
00126     return m_members.test(point);
00127 }
00128 
00129 inline const bitset_t& Group::Members() const
00130 {
00131     return m_members;
00132 }
00133 
00134 inline const bitset_t& Group::Nbs() const
00135 {
00136     return m_nbs;
00137 }
00138 
00139 //---------------------------------------------------------------------------
00140 
00141 /** Collection of groups. 
00142 
00143    @todo If a HexPosition class is ever created, store the 
00144    HexPosition for which these groups were computed.
00145 */
00146 class Groups
00147 {
00148 public:
00149 
00150     /** Creates an empty set of groups. */
00151     Groups();
00152 
00153     /** Returns point's group. */
00154     const Group& GetGroup(HexPoint point) const;
00155 
00156     /** Returns captain of point's group. */
00157     HexPoint CaptainOf(HexPoint point) const;
00158 
00159     /** Returns true if point is captain of its group. */
00160     bool IsCaptain(HexPoint point) const;
00161 
00162     /** @name Group indexing methods. */
00163     // @{
00164 
00165     /** Returns number of groups. */
00166     std::size_t NumGroups() const;
00167 
00168     /** Returns number of groups with color belonging to colorset. */
00169     std::size_t NumGroups(HexColorSet colorset) const;
00170 
00171     /** Returns number of groups of color. */
00172     std::size_t NumGroups(HexColor color) const;
00173 
00174     /** Returns index of point's group in all groups belonging to
00175         to colorset. 
00176         @todo Take this out? Only used in Resistance.
00177     */
00178     std::size_t GroupIndex(HexPoint point, HexColorSet colorset) const;
00179 
00180     /** Returns index of point's group in all groups of color. 
00181         @todo Take this out? Only used in Resistance.
00182     */
00183     std::size_t GroupIndex(HexPoint point, HexColor color) const;
00184 
00185     // @}
00186 
00187     /** @name Neighbor convenience methods. */
00188     // @{
00189 
00190     bitset_t Nbs(HexPoint point) const;
00191 
00192     bitset_t Nbs(HexPoint point, HexColorSet colorset) const;
00193 
00194     bitset_t Nbs(HexPoint point, HexColor color) const;
00195 
00196     bitset_t Nbs(const Group& group) const;
00197 
00198     bitset_t Nbs(const Group& group, HexColorSet colorset) const;
00199 
00200     bitset_t Nbs(const Group& group, HexColor color) const;
00201 
00202     // @}
00203 
00204     /** Returns true if black or white has won. */
00205     bool IsGameOver() const;
00206 
00207     /** Returns color of winning player, EMPTY if IsGameOver() is
00208         false. */
00209     HexColor GetWinner() const;
00210 
00211     /** Returns bitset with only the captains of any set groups. */
00212     bitset_t CaptainizeBitset(bitset_t locations) const;
00213 
00214     /** Returns reference to board groups were computed on. Does not
00215         guarantee the board is in the same state it was in when groups
00216         where computed. */
00217     StoneBoard& Board();
00218 
00219     /** See Board(). */
00220     const StoneBoard& Board() const;
00221 
00222 private:
00223 
00224     friend class Group;
00225 
00226     friend class GroupBuilder;
00227 
00228     friend class GroupIterator;
00229 
00230     StoneBoard* m_brd;
00231 
00232     std::vector<Group> m_groups;
00233 
00234     std::vector<std::size_t> m_group_index; // HexPoint -> index of m_groups
00235 };
00236 
00237 inline Groups::Groups()
00238     : m_brd(0)
00239 {
00240 }
00241 
00242 inline std::size_t Groups::NumGroups() const
00243 {
00244     return m_groups.size();
00245 }
00246 
00247 inline std::size_t Groups::NumGroups(HexColor color) const
00248 {
00249     return NumGroups(HexColorSetUtil::Only(color));
00250 }
00251 
00252 inline std::size_t Groups::GroupIndex(HexPoint point, HexColor color) const
00253 {
00254     return GroupIndex(point, HexColorSetUtil::Only(color));
00255 }
00256 
00257 inline const Group& Groups::GetGroup(HexPoint point) const
00258 {
00259     return m_groups[m_group_index[point]];
00260 }
00261 
00262 inline bitset_t Groups::Nbs(HexPoint point) const
00263 {
00264     return GetGroup(point).Nbs();
00265 }
00266 
00267 inline bitset_t Groups::Nbs(HexPoint point, HexColor color) const
00268 {
00269     return GetGroup(point).Nbs(HexColorSetUtil::Only(color));
00270 }
00271 
00272 inline bitset_t Groups::Nbs(HexPoint point, HexColorSet colorset) const
00273 {
00274     return GetGroup(point).Nbs(colorset);
00275 }
00276 
00277 inline bitset_t Groups::Nbs(const Group& group) const
00278 {
00279     return GetGroup(group.Captain()).Nbs();
00280 }
00281 
00282 inline bitset_t Groups::Nbs(const Group& group, HexColor color) const
00283 {
00284     return GetGroup(group.Captain()).Nbs(HexColorSetUtil::Only(color));
00285 }
00286 
00287 inline bitset_t Groups::Nbs(const Group& group, HexColorSet colorset) const
00288 {
00289     return GetGroup(group.Captain()).Nbs(colorset);
00290 }
00291 
00292 inline HexPoint Groups::CaptainOf(HexPoint point) const
00293 {
00294     return GetGroup(point).Captain();
00295 }
00296 
00297 inline bool Groups::IsCaptain(HexPoint point) const
00298 {
00299     return GetGroup(point).Captain() == point;
00300 }
00301 
00302 inline StoneBoard& Groups::Board()
00303 {
00304     return *m_brd;
00305 }
00306 
00307 inline const StoneBoard& Groups::Board() const
00308 {
00309     return *m_brd;
00310 }
00311 
00312 //---------------------------------------------------------------------------
00313 
00314 /** Iterates over an instance of Groups. */
00315 class GroupIterator : public SafeBool<GroupIterator>
00316 {
00317 public:
00318 
00319     /** Creates an iterator over all groups. */
00320     GroupIterator(const Groups& groups);
00321 
00322     /** Creates an iterator over only those groups in colorset. */
00323     GroupIterator(const Groups& groups, HexColorSet colorset);
00324 
00325     /** Creates an iterator over only those groups of color. */
00326     GroupIterator(const Groups& groups, HexColor color);
00327 
00328     /** Returns current group. */
00329     const Group& operator*() const;
00330 
00331     /** Allows access to current group's methods. */
00332     const Group* operator->() const;
00333 
00334     /** Moves to the next group. */
00335     void operator++();
00336 
00337     /** Used by SafeBool. */
00338     bool boolean_test() const;
00339 
00340 private:
00341 
00342     const Groups* m_groups;
00343 
00344     HexColorSet m_colorset;
00345 
00346     std::size_t m_index;
00347 
00348     void FindNextInColorSet();
00349 };
00350 
00351 inline GroupIterator::GroupIterator(const Groups& groups)
00352     : m_groups(&groups),
00353       m_colorset(ALL_COLORS),
00354       m_index(0)
00355 {
00356 }
00357 
00358 inline GroupIterator::GroupIterator(const Groups& groups, HexColorSet colorset)
00359     : m_groups(&groups),
00360       m_colorset(colorset),
00361       m_index(0)
00362 {
00363     FindNextInColorSet();
00364 }
00365 
00366 inline GroupIterator::GroupIterator(const Groups& groups, HexColor color)
00367     : m_groups(&groups),
00368       m_colorset(HexColorSetUtil::Only(color)),
00369       m_index(0)
00370 {
00371     FindNextInColorSet();
00372 }
00373 
00374 inline const Group& GroupIterator::operator*() const
00375 {
00376     return m_groups->m_groups[m_index];
00377 }
00378 
00379 inline const Group* GroupIterator::operator->() const
00380 {
00381     return &m_groups->m_groups[m_index];
00382 }
00383 
00384 inline void GroupIterator::operator++()
00385 {
00386     ++m_index;
00387     FindNextInColorSet();
00388 }
00389 
00390 inline void GroupIterator::FindNextInColorSet()
00391 {
00392     while (m_index < m_groups->m_groups.size() 
00393            && !HexColorSetUtil::InSet(m_groups->m_groups[m_index].Color(),
00394                                       m_colorset))
00395         ++m_index;
00396 }
00397 
00398 inline bool GroupIterator::boolean_test() const
00399 {
00400     return m_index < m_groups->m_groups.size();
00401 }
00402 
00403 //---------------------------------------------------------------------------
00404 
00405 /** Builds Groups from a StoneBoard. */
00406 class GroupBuilder
00407 {
00408 public:
00409 
00410     /** Computes Groups. */
00411     static void Build(const StoneBoard& brd, Groups& groups);
00412 
00413 private:
00414 
00415 };
00416 
00417 //---------------------------------------------------------------------------
00418 
00419 _END_BENZENE_NAMESPACE_
00420 
00421 #endif // GROUPS_HPP


6 Jan 2011 Doxygen 1.6.3