Seq2D.cpp

#include "Seq2D.h"

#include "PointADT.h"
#include "LineADT.h"
#include "PathADT.h"
#include "MapTypes.h"
#include "Exceptions.h"

#include <vector>
#include <queue>
#include <unordered_set>

using std::vector;
using std::queue;
using std::unordered_set;


template <class T>
Seq2D<T>::Seq2D(vector<vector<T>> s, double scale)
{
  if(scale <= 0) throw invalid_argument();
  if(s.empty()) throw invalid_argument();
  if(s[0].empty()) throw invalid_argument();
  
  for(auto row : s)
    if( row.size() != s[0].size() )
      throw invalid_argument();
  
  this->s = s;
  this->scale = scale;
  this->nRow = s.size();
  this->nCol = s[0].size();
}

template <class T>
void Seq2D<T>::set(PointT p, T v)
{
  if(!(validPoint(p)))
    throw outside_bounds();
  
  s[p.y()][p.x()] = v;
}

template <class T>
T Seq2D<T>::get(PointT p) const
{ 
  if(!(validPoint(p)))
    throw outside_bounds();
  
  return s[p.y()][p.x()];
}

template <class T>
nat Seq2D<T>::getNumRow() const
{
  return nRow;
}

template <class T>
nat Seq2D<T>::getNumCol() const
{
  return nCol;
}

template <class T>
double Seq2D<T>::getScale() const
{
  return scale;
}

template <class T>
nat Seq2D<T>::count(T t) const
{
  nat cnt = 0;
  
  for(auto row : s)
    for(auto element : row)
      if(element == t)
        ++cnt;
      
  return cnt;
}

template <class T>
nat Seq2D<T>::count(LineT l, T t) const
{
  if(!validLine(l))
    throw invalid_argument();
  
  nat cnt = 0;
  
  for(auto pt : pointsInLine(l))
    if(get(pt) == t)
      ++cnt;
  
  return cnt;
}

template <class T>
nat Seq2D<T>::count(PathT pth, T t) const
{
  if(!validPath(pth))
    throw invalid_argument();
  
  nat cnt = 0;
  
  for(auto pt : pointsInPath(pth))
    if(get(pt) == t)
      ++cnt;
    
  return cnt;
}

template <class T>
double Seq2D<T>::length(PathT pth) const
{
  if(!validPath(pth))
    throw invalid_argument();
  
  return pth.len() * scale;
}

template <class T>
bool Seq2D<T>::connected(PointT p1, PointT p2) const
{
  if(!validPoint(p1) || !validPoint(p2))
    throw invalid_argument();
  
  T t = get(p1);
  
  if(get(p2) != t)
    return false;
  
  // use BFS
  queue<PointT> q;
  unordered_set<PointT> marked;
  
  q.push(p1);
  marked.insert(p1);
  
  while(!q.empty()){
    PointT p = q.front();
    q.pop();
    
    // get adjacent points
    unordered_set<PointT> adj = 
      { p.translate(0,1), 
        p.translate(0,-1), 
        p.translate(1,0), 
        p.translate(-1,0) };
      
    for(auto pAdj : adj){
      if(pAdj == p2) return true;
      if(validPoint(pAdj) && marked.find(pAdj) == marked.end())
        if(get(pAdj) == t){
          q.push(pAdj);
          marked.insert(pAdj);
        }
    }    
  }
    
  return false; 
}



// private methods
template <class T>
bool Seq2D<T>::validRow(nat i) const
{
  return i <= (nRow - 1);
}

template <class T>
bool Seq2D<T>::validCol(nat j) const
{
  return j <= (nCol - 1);
}

template <class T>
bool Seq2D<T>::validPoint(PointT p) const
{
  return validRow(p.x()) && validCol(p.y());
}

template <class T>
bool Seq2D<T>::validLine(LineT l) const
{
  return validPoint(l.strt()) && validPoint(l.end());
}

template <class T>
bool Seq2D<T>::validPath(PathT pth) const
{
  for(nat i = 0; i < pth.size(); ++i)
    if(!validLine(pth.line(i)))
      return false;
   
  return true;
}

template <class T>
vector<PointT> Seq2D<T>::pointsInLine(LineT ln) const
{
  vector<PointT> pts;
  
  int xFactor = 0;
  int yFactor = 0;
  
  switch(ln.orient()){
    case N:
      yFactor = 1;
      break;
    case S:
      yFactor = -1;
      break;
    case E:
      xFactor = 1;
      break;
    case W:
      xFactor = -1;
      break;
  }
  
  for(nat i = 0; i < ln.len(); ++i)
    pts.push_back(ln.strt().translate(i*xFactor, i*yFactor));
  
  return pts;
}

template <class T>
vector<PointT> Seq2D<T>::pointsInPath(PathT pth) const
{
  vector<PointT> pts;
  
  for(nat i = 0; i < pth.size(); ++i)
    for(auto pt : pointsInLine(pth.line(i)))
      pts.push_back(pt);
    
  return pts;
}


// explicit instantiations of Seq2D
template class Seq2D<LanduseT>;
template class Seq2D<int>;