Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

BoardUtils.hpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file BoardUtils.hpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #ifndef BOARDUTILS_HPP
00007 #define BOARDUTILS_HPP
00008 
00009 #include "Hex.hpp"
00010 #include "HexBoard.hpp"
00011 
00012 _BEGIN_BENZENE_NAMESPACE_
00013 
00014 //----------------------------------------------------------------------------
00015 
00016 /** Utilities on Boards. */
00017 namespace BoardUtils
00018 {
00019     //------------------------------------------------------------------------
00020 
00021     /** @name Cells */
00022     // @{
00023 
00024     /** Returns HexPoint at the coordinates (x, y). Note that edges
00025         have a single coordinate equal to -1 or width()/height().
00026         That is, (-1, ?) is WEST, (?, -1) is NORTH, etc. Returns
00027         INVALID_POINT if (x, y) do not correspond to a valid point. */
00028     HexPoint CoordsToPoint(const ConstBoard& brd, int x, int y);
00029 
00030     /** Returns HexPoint in direction dir from the point p. 
00031         If p is an edge, returns p. */
00032     HexPoint PointInDir(const ConstBoard& brd, HexPoint p, 
00033                         HexDirection dir);
00034 
00035     /** Rotates the given point 180' about the center of the board. */
00036     HexPoint Rotate(const ConstBoard& brd, HexPoint p);
00037 
00038     /** Mirrors the given point in the diagonal joining acute corners.
00039     Note that this function requires square boards! */
00040     HexPoint Mirror(const ConstBoard& brd, HexPoint p);
00041 
00042     /** Returns the center point on boards where both dimensions are
00043     odd (fails on all other boards). */
00044     HexPoint CenterPoint(const ConstBoard& brd);
00045 
00046     /** These two methods return the two points nearest the center of
00047     the board. On boards with one or more even dimensions, out of
00048     the center-most points the "top right" and "bottom left"
00049     points are returned as they relate to the main
00050     diagonals/visually. On boards with two odd dimensions, both of
00051     these methods return the same point as centerPoint(). */
00052     HexPoint CenterPointRight(const ConstBoard& brd);
00053 
00054     /** @see centerPointRight(). */
00055     HexPoint CenterPointLeft(const ConstBoard& brd);
00056 
00057     /** Returns a random empty cell or INVALID_POINT if the board is
00058         full. */
00059     HexPoint RandomEmptyCell(const StoneBoard& brd);
00060 
00061     // @}
00062 
00063     //-------------------------------------------------------------------------
00064 
00065     /** @name Bitsets */
00066     // @{
00067 
00068     /** Packs a bitset on this boardsize. Output bitset has a bit for
00069         each cell on the board, starting at a1. That is, an 8x8 board
00070         can fit into exactly 64 bits. If in has a bit set at a1, then
00071         the packed bitset will have its 0th bit set; if in has a bit
00072         at a2, the second bit is set, etc, etc. */
00073     bitset_t PackBitset(const ConstBoard& brd, const bitset_t& in);
00074 
00075     /** Unpacks a bitset to the canonical representation. 
00076         @see PackBitset() */
00077     bitset_t UnpackBitset(const ConstBoard& brd, const bitset_t& in);
00078 
00079     /** Shifts bitset in direction dir using PointInDir(). Returns
00080         true if each interior point is still an interior point. */
00081     bool ShiftBitset(const ConstBoard& brd, 
00082                      const bitset_t& bs, HexDirection dir,
00083                      bitset_t& out);
00084 
00085     /** Rotates the given bitset 180' about the center of the
00086         board. */
00087     bitset_t Rotate(const ConstBoard& brd, const bitset_t& bs);
00088 
00089     /** Mirrors the given bitset in the acute diagonal (requires that
00090     width equals height). */
00091     bitset_t Mirror(const ConstBoard& brd, const bitset_t& bs);
00092 
00093     /** Returns true if p1 is connected to p2 on the bitset; p1 and p2
00094         are assumed to be inside the bitset.  */
00095     bool ConnectedOnBitset(const ConstBoard& brd, 
00096                            const bitset_t& carrier,
00097                            HexPoint p1, HexPoint p2);
00098 
00099     /** Returns a subset of carrier: the points that are reachable
00100         from start. Flow will enter and leave cells in carrier, and
00101         enter but not leave cells in stopset. */
00102     bitset_t ReachableOnBitset(const ConstBoard& brd, 
00103                                const bitset_t& carrier,
00104                                const bitset_t& stopset, 
00105                                HexPoint start);
00106 
00107     // @}
00108 
00109     //-------------------------------------------------------------------------
00110 
00111     /** @name Decompositions */
00112     // @{
00113 
00114     /** Must be called before any decomposition related function is
00115         called. */
00116     void InitializeDecompositions();
00117 
00118     /** Returns true if there is a combinatorial decomposition for
00119         color where the opposing color edges are VC-connected. The
00120         VC's carrier will be stored in captured.
00121         InitializeDecompositions() must be called once before this can
00122         be used. */
00123     bool FindCombinatorialDecomposition(const HexBoard& brd, HexColor color, 
00124                                         bitset_t& captured);
00125 
00126     /** Returns true if there is a combinatorial decomposition for
00127         color that splits the board (i.e. touches both edges of the
00128         opposite color).  Group that splits the board is stored in
00129         group. InitializeDecompositions() must be called once before
00130         this can be used. */
00131     bool FindSplittingDecomposition(const HexBoard& brd, HexColor color, 
00132                     HexPoint& group);
00133     // @}
00134 
00135     //----------------------------------------------------------------------
00136 
00137     /** Dumps all cells outside the consider set and the remove set
00138         in a format the gui expects. */
00139     std::string GuiDumpOutsideConsiderSet(const StoneBoard& brd, 
00140                                           const bitset_t& consider,
00141                                           const bitset_t& remove);
00142 }
00143 
00144 //----------------------------------------------------------------------------
00145 
00146 _END_BENZENE_NAMESPACE_
00147 
00148 #endif // BOARDUTILS_HPP


6 Jan 2011 Doxygen 1.6.3