base.hpp

Go to the documentation of this file.

#ifndef MSMAZES_CORE_PATTERN_BASE_HPP
#define MSMAZES_CORE_PATTERN_BASE_HPP

#include <vector>  // std::vector
#include <boost/utility.hpp>  // boost::tie
#include <boost/property_map.hpp>  // boost::property_map and boost::get
#include <boost/graph/graph_traits.hpp>  // boost::graph_traits
#include <boost/graph/graph_selectors.hpp>  // boost::vecS and boost::listS
#include <boost/graph/adjacency_list.hpp>  // boost::adjacency_list and friends

namespace msmazes {


struct BasicCellEqualityPolicy
{
    template <typename Cell>
    bool operator()(const Cell& c1, const Cell& c2) const
    {
        return c1 == c2;
    }
};


template <
#ifndef MSMAZES_DOX
    typename EdgeDirectedSelector
  , typename CellType
  , typename CellEqualityPolicyType
  , typename DirectionType
  , typename CellContainer = std::vector<CellType>
#endif  /* MSMAZES_DOX */
>
class BasePattern
{
 public:
#ifdef MSMAZES_DOX
    typedef implementation_defined Cell;
#else
    typedef CellType
            Cell;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined CellEqualityPolicy;
#else
    typedef CellEqualityPolicyType
            CellEqualityPolicy;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined Graph;
#else
    typedef boost::adjacency_list<boost::listS,boost::vecS,EdgeDirectedSelector>
            Graph;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined CellIndex;
#else
    typedef typename boost::graph_traits<Graph>::vertices_size_type
            CellIndex;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined EdgeDirectedCategory;
#else
    typedef typename boost::graph_traits<Graph>::directed_category
            EdgeDirectedCategory;
#endif  /* MSMAZES_DOX */

#ifdef MSMAZES_DOX
    typedef implementation_defined Direction;
#else
    typedef DirectionType
            Direction;
#endif  /* MSMAZES_DOX */

 private:
    Graph         _graph;
    CellContainer _cell;

    BasePattern(const BasePattern& copy)
    {
    }

 protected:

    BasePattern() : _graph(), _cell()
    {
    }

 public:

    virtual ~BasePattern()
    {
    }

 private:
    template <
        typename PatternFormer
      , typename ArgumentPack
    >
    void
        _initializeEdges(
            const PatternFormer& pattern_former
          , const ArgumentPack& p
          , boost::undirected_tag
        )
    {
        typename boost::graph_traits<Graph>::vertex_descriptor u;
        CellIndex i = boost::num_vertices(_graph);
        CellIndex j;

        while (i > 0)
        {
            u = boost::vertex(--i, _graph);
            boost::clear_vertex(u, _graph);
            Cell& u_loc = _cell[i];
            j = boost::num_vertices(_graph);

            while (--j > i)
            {
                Cell& v_loc = _cell[j];

                if (
                    PatternFormer::isLegalEdge(u_loc, v_loc, p)
                 || PatternFormer::isLegalEdge(v_loc, u_loc, p)
                )
                {
                    boost::add_edge(u, boost::vertex(j, _graph), _graph);
                }
            }
        }
    }

    template <
        typename PatternFormer
      , typename ArgumentPack
    >
    void
        _initializeEdges(
            const PatternFormer& pattern_former
          , const ArgumentPack& p
          , boost::directed_tag
        )
    {
        typename boost::graph_traits<Graph>::vertex_descriptor u, v;
        CellIndex i = boost::num_vertices(_graph);
        CellIndex j;

        while (i > 0)
        {
            u = boost::vertex(--i, _graph);
            boost::clear_vertex(u, _graph);
            Cell& u_loc = _cell[i];
            j = boost::num_vertices(_graph);

            while (--j > i)
            {
                v = boost::vertex(j, _graph);
                Cell& v_loc = _cell[j];

                if (PatternFormer::isLegalEdge(u_loc, v_loc, p))
                {
                    boost::add_edge(u, v, _graph);
                }

                if (PatternFormer::isLegalEdge(v_loc, u_loc, p))
                {
                    boost::add_edge(v, u, _graph);
                }
            }
        }
    }

 protected:
    template <
        typename PatternFormer
      , typename ArgumentPack
    >
    void
        initializeWithPatternFormer(
            const PatternFormer& pattern_former
          , const ArgumentPack& p
        )
    {
        const CellIndex volume = PatternFormer::countCells(p);

        while (boost::num_vertices(_graph) < volume)
        {
            boost::add_vertex(_graph);
        }

        typename boost::graph_traits<Graph>::vertex_descriptor vertex;
        CellIndex vertex_count = boost::num_vertices(_graph);

        while (vertex_count > volume)
        {
            vertex = boost::vertex(--vertex_count, _graph);
            boost::clear_vertex(vertex, _graph);
            boost::remove_vertex(vertex, _graph);
        }

        _cell.resize(volume);
        PatternFormer::makeCells(_cell.begin(), p);
        _initializeEdges(pattern_former, p, EdgeDirectedCategory());
    }

 public:
    inline const Graph& getGraph() const
    {
        return _graph;
    }

    inline CellIndex getCellCount() const
    {
        return boost::num_vertices(_graph);
    }

    inline const Cell& getCell(const CellIndex index) const
    {
        return _cell[index];
    }

    virtual const Cell& getEntranceCell() const = 0;

    virtual const Cell& getSourceCell() const = 0;

    virtual const Cell& getTargetCell() const = 0;

    virtual const Cell& getExitCell() const = 0;

 protected:
    virtual Direction
        getEdgeDirectionDerived(
            const Cell& source
          , const Cell& target
        ) const
    {
        return Direction();
    }

 public:
    Direction
        getEdgeDirection(
            const CellIndex source_index
          , const CellIndex target_index
        ) const
    {
        return
            (source_index == target_index)
          ? getEdgeDirectionDerived(
                getEntranceCell()
              , getCell(target_index)
            )
          : (target_index == getCellCount())
          ? getEdgeDirectionDerived(
                getCell(source_index)
              , getExitCell()
            )
          : getEdgeDirectionDerived(
                getCell(source_index)
              , getCell(target_index)
            );
    }
};
}  // namespace msmazes

#endif  /* MSMAZES_CORE_PATTERN_BASE_HPP */

---

Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.