src/grid.h

   1 /*
   2   Copyright (c) 2006 Paolo Capriotti <p.capriotti@sns.it>
   3             (c) 2006 Maurizio Monge <maurizio.monge@kdemail.net>
   4
   5   This program is free software; you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation; either version 2 of the License, or
   8   (at your option) any later version.
   9 */
  10
  11 #ifndef GRID_H
  12 #define GRID_H
  13
  14 #include <vector>
  15 #include <iostream>
  16
  17 #include <QString>
  18 #include <QPoint>
  19 #include "point.h"
  20 #include "pathinfo.h"
  21
  22 template <typename T>
  23 class Grid {
  24   int sizeX, sizeY;
  25 protected:
  26   std::vector<T> board;
  27 public:
  28
  29   template<typename T1> friend class Grid;
  30
  31   Grid(int sizeX, int sizeY, const T& defaultValue)
  32   : sizeX(sizeX), sizeY(sizeY) {
  33     board.resize(sizeX * sizeY, defaultValue);
  34   }
  35
  36   Grid(int sizeX, int sizeY)
  37   : sizeX(sizeX), sizeY(sizeY) {
  38     board.resize(sizeX * sizeY);
  39   }
  40
  41   Grid(const Grid& other)
  42   : sizeX(other.sizeX), sizeY(other.sizeY)
  43   , board(other.board) { }
  44
  45   template <typename T1>
  46   Grid(const Grid<T1>& other)
  47   : sizeX(other.getSize().x), sizeY(other.getSize().y) {
  48     board.resize(sizeX * sizeY);
  49     for(int i=sizeX * sizeY-1; i>=0;i--)
  50       board[i] = other.board[i];
  51   }
  52
  53   Point getSize() const {
  54     return Point(sizeX, sizeY);
  55   }
  56
  57   void changeSize(int x, int y) {
  58     sizeX = x;
  59     sizeY = y;
  60     board.resize(sizeX * sizeY);
  61   }
  62
  63   const T& operator[](Point p) const {
  64     Q_ASSERT(valid(p));
  65
  66     return board[p.x + p.y * sizeX];
  67   }
  68   T& operator[](Point p) {
  69     Q_ASSERT(valid(p));
  70
  71     return board[p.x + p.y * sizeX];
  72   }
  73
  74   /** \return the nth point in the grid, that is not guaranteed to be valid */
  75   Point nTh(int index) const { return Point(index%sizeX, index/sizeX); }
  76
  77   Point first() const { return Point(0,0); }
  78   Point last() const { return Point(sizeX-1, sizeY-1); }
  79
  80   Point next(const Point& p) const {
  81     if (p.x >= sizeX-1)
  82       return Point(0, p.y+1);
  83     else
  84       return Point(p.x+1, p.y);
  85   }
  86   bool valid(const Point& p) const {
  87     return (0 <= p.x) && (p.x < sizeX) && (0 <= p.y) && (p.y < sizeY);
  88   }
  89
  90   bool operator==(const Grid& g) const {
  91     if(g.sizeX != sizeX || g.sizeY != sizeY)
  92       return false;
  93     for(unsigned int i=0;i<board.size();i++)
  94     if(board[i].operator!=(g.board[i]))
  95       return false;
  96     return true;
  97   }
  98
  99   bool operator!=(const Grid& g) const {
 100     return !(*this == g);
 101   }
 102
 103   PathInfo path(const Point& from, const Point& to) const {
 104     Point delta = to - from;
 105     PathInfo::Direction direction;
 106
 107     if (delta.x == 0)
 108       direction = PathInfo::Vertical;
 109     else if (delta.y == 0)
 110       direction = PathInfo::Horizontal;
 111     else if (delta.x == delta.y)
 112       direction = PathInfo::Diagonal1;
 113     else if (delta.x == -delta.y)
 114       direction = PathInfo::Diagonal2;
 115     else
 116       direction = PathInfo::Undefined;
 117
 118     int num_obs = 0;
 119     if (direction != PathInfo::Undefined) {
 120       Point step = delta.normalizeInfinity();
 121       Point position = from;
 122       while ((position += step) != to) {
 123         if((*this)[position].operator!())
 124           continue;
 125         num_obs++;
 126       }
 127     }
 128
 129     return PathInfo(direction, num_obs);
 130   }
 131 };
 132
 133 #endif // GRID_H