hex.h

Go to the documentation of this file.

/*                            Package   : libhex
 * hex.h                      Created   : 2007/10/11
 *                            Author    : Alex Tingle
 *
 *    Copyright (C) 2007-2008, Alex Tingle.
 *
 *    This file is part of the libhex application.
 *
 *    libhex is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License as published by the Free Software Foundation; either
 *    version 2.1 of the License, or (at your option) any later version.
 *
 *    libhex is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    Lesser General Public License for more details.
 *
 *    You should have received a copy of the GNU Lesser General Public
 *    License along with this library; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef FIRETREE__HEX_H
#define FIRETREE__HEX_H 1


#include <list>
#include <set>
#include <map>
#include <stdexcept>
#include <ostream>
#include <string>


#define HEX_PARANOID_CHECKS

namespace hex {


//
// Exceptions

class exception: public std::exception
{
public:
  std::string _what;
  exception(const std::string& w) throw(): _what(w) {}
  virtual ~exception() throw() {}
  virtual const char* what() const throw() { return this->_what.c_str(); }
};

class invalid_argument: public hex::exception
{
public:
  invalid_argument(const std::string& w) throw(): hex::exception(w) {}
  virtual ~invalid_argument() throw() {}
};

class out_of_range: public hex::exception
{
public:
  out_of_range(const std::string& w) throw(): hex::exception(w) {}
  virtual ~out_of_range() throw() {}
};


//
// Distance

typedef double Distance;

const Distance M_SQRT3 =1.73205080756887729352744634150587236; // sqrt(3)
const Distance I =1.0;         
const Distance J =M_SQRT3/2.0; 
const Distance K =1.0/M_SQRT3; 

//
// Direction

enum Direction {  A=0, B=1, C=2,  D=3, E=4, F=5 };
const int DIRECTIONS =6;

Direction to_direction(char c) throw(hex::invalid_argument);
char to_char(Direction d);

// Direction arithmetic.

Direction& operator+= (Direction& d, int i);
Direction  operator+  (const Direction& d, int i);
Direction& operator++ (Direction& d);
Direction  operator++ (const Direction& d,int);
Direction& operator-= (Direction& d, int i);
Direction  operator-  (const Direction& d, int i);
Direction& operator-- (Direction& d);
Direction  operator-- (const Direction& d,int);

std::ostream& operator<<(std::ostream& os, const Direction& d);

std::string rotate(const std::string& steps, int i);


//
// svg::Identity

namespace svg {
  class Identity
  {
  public:
    std::string  id;
    std::string  style;
    std::string  className;
    virtual ~Identity(void) {}
    std::string attributes(void) const;
  };
} // end namespace svg


//
// Forward declarations

class Grid;
class Edge;
class Hex;
class Area;
class Path;
class Boundary;


struct Point
{
  Distance x,y;
  Point offset(Distance dx, Distance dy) const { return Point(x+dx,y+dy); }
  Point(): x(0.0), y(0.0) {}
  Point(Distance x_, Distance y_): x(x_), y(y_) {}
  Point(const std::string s) throw (out_of_range,invalid_argument);
  Point& operator+=(const Point& p) { x+=p.x; y+=p.y; return *this; }
  Point& operator-=(const Point& p) { x-=p.x; y-=p.y; return *this; }
  Point operator+(const Point& p) const { return Point(x+p.x,y+p.y); }
  Point operator-(const Point& p) const { return Point(x-p.x,y-p.y); }
  Point operator*(double v) const { return Point(x*v,y*v); }
  Point operator/(double v) const { return Point(x/v,y/v); }
  bool operator==(const Point& p) const { return(x==p.x && y==p.y); }
  bool operator!=(const Point& p) const { return !operator==(p); }
  std::string str(void) const;
};

class Grid
{
  mutable std::map<int,Hex*> _hexes;
  int _cols;
  int _rows;
public:
  int  cols(void) const { return _cols; }
  int  rows(void) const { return _rows; }
  Distance width(void) const { return I/2.0 + I*cols(); }
  Distance height(void) const { return K*2 + J*(rows()-1); }
  bool is_in_range(int i, int j) const {return 0<=i&&i<cols()&&0<=j&&j<rows();}
  Hex* hex(int i, int j) const throw(hex::out_of_range);
  Hex* hex(Distance x, Distance y) const throw(hex::out_of_range);
  Hex* hex(const Point& p) const throw(hex::out_of_range);
  Area to_area(void) const;
public: // construction
  Grid(int cols, int rows) throw(hex::out_of_range);
public: // housekeeping
  Grid(const Grid& right);
  virtual ~Grid();
private:
  Grid& operator=(const Grid&); 
public: // factory methods
  Hex* hex(const std::string& s) const
    throw(out_of_range,invalid_argument);
  std::set<Hex*> hexes(const std::string& s) const
    throw(out_of_range,invalid_argument);
  Area area(const std::string& s) const
    throw(out_of_range,invalid_argument);
  Path path(const std::string& s) const
    throw(out_of_range,invalid_argument);
  Boundary boundary(const std::string& s) const
    throw(out_of_range,invalid_argument);
};


class Edge
{
  Hex* const  _hex;
  const Direction  _direction;
public:
  Hex*       hex(void) const { return _hex; }
  Direction  direction(void) const { return _direction; }
  Edge*      complement(void) const;
  bool       is_next(const Edge& v) const;
  Edge*      next_in(bool clockwise=false) const;
  Edge*      next_out(bool clockwise=false) const;
  Point      start_point(float bias =0.0, bool clockwise=false) const;
  Point      end_point(float bias =0.0, bool clockwise=false) const;
  Point      join_point(const Edge* next, float bias =0.0) const;
private:
  friend class Hex;
  Edge(Hex* h, Direction d): _hex(h), _direction(d) {}
  ~Edge() {}
};


class Hex
{
  Edge  _edgeA,_edgeB,_edgeC,_edgeD,_edgeE,_edgeF;
  const Grid& _grid;
public:
  const int  i; 
  const int  j; 
  const Grid&  grid(void) const { return _grid; }
  const Edge*  edge(const Direction& d) const;
  Edge*        edge(const Direction& d);
  Hex*         go(const Direction& d, int distance=1) const;
  Hex*         go(const std::string& steps) const;
  Point        centre(void) const;
  std::string  str(void) const;
  static int   _key(int i, int j) { return (i<<14) | j; }
public: // construction
  Hex(const Grid& grid, int i_, int j_);
private:
  friend class Grid;
  Hex(const Hex& right);               
  Hex& operator=(const Hex&);          
  Hex(const Grid& grid, const Hex& h); 
  ~Hex() {}                            
};


class Area: public svg::Identity
{
  std::set<Hex*>  _hexes;
public:
  int                    size(void) const { return int(_hexes.size()); }
  bool                   contains(Hex* h) const { return _hexes.count(h)>0; }
  Boundary               boundary(void) const;
  const std::set<Hex*>&  hexes(void) const { return _hexes; }
  std::list<Area>        enclosed_areas(void) const;
  std::list<Boundary>    skeleton(bool include_boundary =true) const;
  std::list<hex::Path>   fillpaths(Hex* origin =NULL) const;
  std::string            str(Hex* origin =NULL) const;
public: // transformations
  Area  go(const Direction& d, int distance=1) const throw(hex::out_of_range);
  Area  go(const std::string& steps) const throw(hex::out_of_range);
public: // construction
  Area(void): _hexes() {} 
  Area(const std::set<Hex*>& hexes);
  Area(Hex* h): _hexes() { _hexes.insert(h); }
  Area(Hex* h, int distance); 
};


class Path: public svg::Identity
{
  std::list<Hex*>  _hexes;
public:
  Area                    to_area(void) const;
  const std::list<Hex*>&  hexes(void) const { return _hexes; }
  int                     length(void) const; 
  std::string             steps(void) const;
  std::string             str(void) const;
public: // construction
  Path(void): _hexes() {} 
  Path(const std::list<Hex*>& hexes): _hexes(hexes) {}
  Path(Hex* start, const std::string& steps)
    throw(hex::out_of_range,hex::invalid_argument);
  Path(Hex* from, const Hex* to) throw();
};


class Boundary: public svg::Identity
{
  std::list<Edge*>  _edges;
public:
  int                      length(void) const; 
  bool                     is_closed(void) const; 
  bool                     is_container(void) const; 
  Boundary                 complement(void) const throw(hex::out_of_range);
  const std::list<Edge*>&  edges(void) const { return _edges; }
  Path                     to_path(void) const;
  bool                     clockwise(void) const; 
  std::string              str(void) const;
  std::list<Point>         stroke(float bias =0.0) const;
  Area                     area(void) const;
public: // construction
  Boundary(void): _edges() {} 
  Boundary(const std::list<Edge*>& edges): _edges(edges) {}
};


//
// Algorithms


void
go(int& i, int& j, Direction d, int distance=1);


void
go(int& i, int& j, const std::string& steps);


std::string
steps(const Hex* from, const Hex* to);


int
distance(const Hex* from, const Hex* to);


std::set<Hex*>
range(Hex* h, int distance);


std::set<Hex*>
set_difference(const std::set<Hex*>& a, const std::set<Hex*>& b);


std::set<Hex*>
set_intersection(const std::set<Hex*>& a, const std::set<Hex*>& b);


std::set<Hex*>
set_union(const std::set<Hex*>& a, const std::set<Hex*>& b);


std::string
set_str(const std::set<Hex*>& a);


bool
bounding_box(const std::set<Hex*>& a, int& i0, int& j0, int& i1, int& j1);


Area
fill(const std::set<Hex*>& beyond, Hex* h);


Area
fill(const std::set<Hex*>& beyond, const Area& a);


std::list<Area>
areas(const std::set<Hex*>& s);


bool
is_connected(const std::set<Hex*>& s);


std::list<Boundary>
skeleton(const std::list<Area>& a, bool include_boundary =true);


} // end namespace hex

#endif

---