/*
 *  graph.cpp
 * 
 *  (c) Daniel Jackson 2004. 
 *  CIS 11 Data Structures & Algorithms 
 * 
 
Implements the graph class. 
 
Class Invariant: 

  allocated = current capacity of the arrays. 
  numVertices = number of vertices 
  if an edge does not exist, edges[][].exists = false and .weight =-1 
  if an edge does exist, edges[][].exists = true and .weight = its weight 
  data[] = data stored in a vertex.
  
*/ 

#include <cassert>   // Provides assert()
#include <cstdlib>   // Provides size_t
#include <set>       // Provides set
#include <algorithm> // Provides swap()

template <class Item>
graph<Item>::graph(std::size_t capacity) {
  allocated = capacity;
  numVertices = 0;
  data = new Item[allocated];
  edges = new (weightedEdge*)[allocated];
  for (std::size_t i = 0; i < allocated; ++i) {
    edges[i] = new weightedEdge[allocated];
    for (std::size_t j = 0; j < allocated; ++j) {
      edges[i][j].exists = false;
      edges[i][j].weight = -1; } }
}

template <class Item>
graph<Item>& graph<Item>::operator=(const graph<Item>& source) {
  if (this == &source)
    return this;
  delete [] data;
  for (std::size_t i = 0; i < allocated; ++i)
    delete [] edges[i];
  delete [] edges;
  data = new Item[source.allocated];
  edges = new weightedEdge*[source.allocated];
  allocated = source.allocated;
  numVertices = source.numVertices;
  for (std::size_t i = 0; i < allocated; ++i) {
    edges[i] = new weightedEdge[allocated];
    data[i] = source.data[i];
    for (std::size_t j = 0; j < allocated; ++j) {
      edges[i][j].exists = source.edges[i][j].exists;
      edges[i][j].weight = source.edges[i][j].weight; } }
  return this;
}

template <class Item>
graph<Item>::graph(const graph<Item>& source) {
  data = new Item[source.allocated];
  edges = new weightedEdge*[source.allocated];
  allocated = source.allocated;
  numVertices = source.numVertices;
  for (std::size_t i = 0; i < allocated; ++i) {
    edges[i] = new weightedEdge[allocated];
    data[i] = source.data[i];
    for (std::size_t j = 0; j < allocated; ++j) {
      edges[i][j].exists = source.edges[i][j].exists;
      edges[i][j].weight = source.edges[i][j].weight; } }
}

template <class Item>
graph<Item>::~graph() {
  delete [] data;
  for (std::size_t i = 0; i < allocated; ++i)
    delete [] edges[i];
  delete [] edges;
  numVertices = 0;
  allocated = 0;
}

template <class Item>
void graph<Item>::AddVertex(const Item& label) {
  if ( size() == allocated )
    Resize(2*(allocated + 1));
  data[numVertices] = label;
  ++numVertices;
}

template <class Item>
void graph<Item>::AddEdge(std::size_t source, std::size_t target, int newWeight) {
  assert(source < size());
  assert(target < size());
  assert(newWeight >= 0);
  edges[source][target].exists = true;
  edges[source][target].weight = newWeight;
}

template <class Item>
void graph<Item>::RemoveEdge(std::size_t source, std::size_t target) {
  assert(source < size());
  assert(target < size());
  edges[source][target].exists = false;
  edges[source][target].weight = -1;
}

template <class Item>
void graph<Item>::Resize(std::size_t newSize) {
  if (newSize < size())
    newSize = size();
  graph<Item> duplicate(newSize);
  for (std::size_t i = 0; i < size(); ++i) {
    duplicate.data[i] = data[i];
    for (std::size_t j = 0; j < size(); ++j) {
      duplicate.edges[i][j].exists = edges[i][j].exists;
      duplicate.edges[i][j].weight = edges[i][j].weight; } }
  duplicate.numVertices = numVertices;
  std::swap(allocated, duplicate.allocated);
  std::swap(data, duplicate.data);
  std::swap(edges, duplicate.edges);
}

template <class Item>
Item& graph<Item>::operator[] (std::size_t vertex) {
  assert(vertex < size());
  return data[vertex];
}

template <class Item>
bool graph<Item>::IsEdge(std::size_t source, std::size_t target) const {
  assert(source < size());
  assert(target < size());
  return edges[source][target].exists;
}

template <class Item>
std::set<std::size_t> graph<Item>::Neighbors(std::size_t vertex) const {
  std::set<std::size_t> answer;
  assert(vertex < size());
  for (std::size_t i = 0; i < size(); ++i) {
    if (edges[vertex][i].exists)
      answer.insert(i); }
  return answer;
}

template <class Item>
Item graph<Item>::operator[](std::size_t vertex) const {
  assert(vertex < size());
  return data[vertex];
}

template <class Item>
int graph<Item>::EdgeWeight(std::size_t source, std::size_t target) const {
  assert(source < size());
  assert(target < size());
  return edges[source][target].weight;
}