// AdjacencyListGraph.h
#pragma once

#include <iterator>
#include <queue>
#include <stack>
#include <vector>

namespace csc280
{
  template <typename V, typename E>
  class AdjacencyListGraph final
  {
#include "private/ALGDefs.h"

  public:
#include "private/ALGVertexIterator.h"
#include "private/ALGEdgeIterator.h"

    using vertex_iterator = ALGVertexIterator<V, E>;
    using edge_iterator = ALGEdgeIterator<V, E>;

    explicit AdjacencyListGraph( std::size_t initialSize = 32 )
    {
      graph.reserve( initialSize );
    }

    ~AdjacencyListGraph() = default;

    AdjacencyListGraph( const AdjacencyList& ) = delete;
    AdjacencyListGraph& operator=( const AdjacencyList& ) = delete;

    template <typename ...Args>
    auto emplace( Args... args ) -> vertex_iterator;
    auto insert( V vertex ) -> vertex_iterator;

    template <typename ...Args>
    auto emplaceEdge( const V& source, const V& destination, Args... args ) -> edge_iterator;
    auto insertEdge( const V& source, const V& destination, E value ) -> edge_iterator;

    void erase( const V& vertex );
    void erase( const vertex_iterator& iter );
    void eraseByIndex( const std::size_t index );

    using EdgeValue = std::tuple<V, E>;
    auto insertEdge( const V& source, EdgeValue&& tuple ) -> edge_iterator;

    void eraseEdge( const V& source, const V& destination, const E& edge );

    auto cbegin() const -> vertex_iterator { return ALGVertexIterator<V,E>( graph.cbegin() ); }
    auto cend() const -> vertex_iterator { return ALGVertexIterator<V, E>( graph.cend() ); }

    auto cbegin( const V& vertex ) const -> edge_iterator;
    auto cend( const V& vertex ) const -> edge_iterator;

    auto operator[]( const std::size_t index ) const -> reference_type;
    bool exists( const V& vertex ) const;
    auto find( const V& vertex ) const -> vertex_iterator;

    auto find( const V& source, const V& destination ) const -> edge_iterator;

    std::size_t size() const { return graph.size(); }
    bool empty() const { return graph.empty(); }

    template <typename Visitor>
    void depthFirstSearch( const Visitor& visitor ) const;

    template <typename Visitor>
    void breadthFirstSearch( const Visitor& visitor ) const;

  private:
    auto indexOf( const V& vertex ) -> typename Graph::iterator;

    template <typename Visitor>
    void visitDfs( const std::size_t index, Visited& visited, const Visitor& visitor ) const;

    template <typename Visitor>
    void visitBfs( const std::size_t index, Visited& visited, const Visitor& visitor ) const;

    Graph graph;
  };

#include "private/ALGImpl.h"
}

// private/ALGDefs.h
using value_type = V;
using pointer_type = value_type const*;
using reference_type = const value_type&;
using edge_value_type = E;

struct Edge
{
  edge_value_type value;
  std::size_t index;

  bool operator==( const Edge& rhs ) const
  {
    return value == rhs.value && index == rhs.index;
  }
};

using AdjacencyList = std::vector<Edge>;

struct Vertex
{
  Vertex( value_type value ) : value{ std::move( value ) }
  {
    edges.reserve( 8 );
  }

  bool operator==( const Vertex& rhs ) const
  {
    return value == rhs.value;
  }

  value_type value;
  AdjacencyList edges;
};

using Graph = std::vector<Vertex>;
using Visited = std::vector<bool>;

// private/ALGVertexIterator.h
template <typename Vertex, typename Edge>
struct ALGVertexIterator final
{
  using difference_type = std::ptrdiff_t;
  using value_type = Vertex;
  using reference = Vertex&;
  using const_reference = const Vertex&;
  using pointer = Vertex*;
  using const_pointer = const Vertex*;
  using iterator_category = std::bidirectional_iterator_tag;

  ALGVertexIterator() = delete;
  ALGVertexIterator( const ALGVertexIterator& ) = default;
  ALGVertexIterator& operator= ( const ALGVertexIterator& ) = default;

  ALGVertexIterator& operator++()
  {
    ++iterator;
    return *this;
  }

  ALGVertexIterator& operator--()
  {
    --iterator;
    return *this;
  }

  bool operator==( const ALGVertexIterator& rhs ) const
  {
    return iterator == rhs.iterator;
  }

  bool operator!=( const ALGVertexIterator& rhs ) const
  {
    return !operator==( rhs );
  }

  const_reference operator*() const
  {
    return iterator->value;
  }

  const_pointer operator->() const
  {
    return *( iterator->value );
  }

private:
  explicit ALGVertexIterator( typename Graph::const_iterator iterator ) :
    iterator{ iterator } {}

  typename Graph::const_iterator iterator;
  friend class AdjacencyListGraph<Vertex, Edge>;
};

// private/ALGEdgeIterator.h
template <typename VType, typename EType>
struct ALGEdgeIterator final
{
  using difference_type = std::ptrdiff_t;
  using value_type = EType;
  using reference = EType & ;
  using const_reference = const EType&;
  using pointer = EType * ;
  using const_pointer = const EType*;
  using vertex_index = std::size_t;
  using iterator_category = std::random_access_iterator_tag;

  ALGEdgeIterator() = delete;
  ALGEdgeIterator( const ALGEdgeIterator& ) = default;
  ALGEdgeIterator& operator= ( const ALGEdgeIterator& ) = default;

  ALGEdgeIterator& operator++()
  {
    ++iterator;
    return *this;
  }

  ALGEdgeIterator& operator--()
  {
    --iterator;
    return *this;
  }

  ALGEdgeIterator& operator+=( difference_type n )
  {
    iterator.operator+=( n );
    return *this;
  }

  ALGEdgeIterator operator+( difference_type n ) const
  {
    auto iter = iterator;
    iter.operator+=( n );
    return { idx, iter };
  }

  ALGEdgeIterator& operator-=( difference_type n )
  {
    iterator.operator-=( n );
    return *this;
  }

  const_reference operator[]( difference_type n ) const
  {
    operator+=( n );
    return operator*();
  }

  ALGEdgeIterator operator-( difference_type n ) const
  {
    auto iter = iterator;
    iter.operator-=( n );
    return { idx, iter };
  }

  bool operator==( const ALGEdgeIterator& rhs ) const
  {
    return idx == rhs.idx && iterator == rhs.iterator;
  }

  bool operator!=( const ALGEdgeIterator& rhs ) const
  {
    return !operator==( rhs );
  }

  bool operator<( const ALGEdgeIterator& rhs ) const
  {
    if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
    return iterator.operator<( rhs.iterator );
  }

  bool operator<=( const ALGEdgeIterator& rhs ) const
  {
    if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
    return iterator.operator<=( rhs.iterator );
  }

  bool operator>( const ALGEdgeIterator& rhs ) const
  {
    if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
    return iterator.operator>( rhs.iterator );
  }

  bool operator>=( const ALGEdgeIterator& rhs ) const
  {
    if ( idx != rhs.idx ) throw std::runtime_error( "Iterators point to different vertices" );
    return iterator.operator>=( rhs.iterator );
  }

  const_reference operator*() const
  {
    return iterator->value;
  }

  const_pointer operator->() const
  {
    return &( iterator->value );
  }

  vertex_index index() const
  {
    return iterator->index;
  }

private:
  explicit ALGEdgeIterator( difference_type index, typename AdjacencyList::const_iterator iterator ) :
    idx{ index }, iterator{ iterator } {}

  typename AdjacencyList::const_iterator iterator;
  difference_type idx;
  friend class AdjacencyListGraph<VType, EType>;
};

// private/ALGImpl.h
template <typename V, typename E>
template <typename ... Args>
auto AdjacencyListGraph<V, E>::emplace( Args... args ) -> vertex_iterator
{
  auto value{ args... };
  return insert( std::move( value ) );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insert( V value ) -> vertex_iterator
{
  auto iter = std::find_if( graph.cbegin(), graph.cend(),
    [&value] ( const auto& vertex ) { return vertex.value == value; } );

  if ( iter == graph.cend() )
  {
    graph.emplace_back( Vertex( std::move( value ) ) );
    iter = graph.cend();
    --iter;
  }

  return ALGVertexIterator<V, E>( iter );
}

template <typename V, typename E>
template <typename ... Args>
auto AdjacencyListGraph<V, E>::emplaceEdge( const V& source, const V& destination, Args... args ) -> edge_iterator
{
  auto value{ args... };
  return insertEdge( source, destination, std::move( value ) );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insertEdge( const V& source, const V& destination, E value ) -> edge_iterator
{
  auto siter = indexOf( source );
  auto diter = indexOf( destination );

  Edge edge{ std::move( value ), std::distance( graph.begin(), diter ) };
  auto& vector = siter->edges;
  auto iter = std::find( vector.cbegin(), vector.cend(), edge );
  if ( iter == vector.cend() )
  {
    if ( vector.empty() ) vector.reserve( 4 );
    vector.emplace_back( std::move( edge ) );
    iter = vector.cend();
    --iter;
  }

  return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), siter ), iter };
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::erase( const V& vertex )
{
  erase( find( vertex ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::erase( const vertex_iterator& iter )
{
  if ( iter.iterator != graph.cend() ) eraseByIndex( std::distance( graph.cbegin(), iter.iterator ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::eraseByIndex( const std::size_t index )
{
  for ( auto& vertex: graph )
  {
    vertex.edges.erase(
      std::remove_if( vertex.edges.begin(), vertex.edges.end(), 
      [index] ( const auto& edge ) { return index == edge.index; } ),
      vertex.edges.end() );
  }

  auto iter = graph.cbegin();
  std::advance( iter, index );
  graph.erase( iter );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::insertEdge( const V& source, EdgeValue&& tuple ) -> edge_iterator
{
  return insertEdge( source, std::get<0>( tuple ), std::get<1>( tuple ) );
}

template <typename V, typename E>
void AdjacencyListGraph<V, E>::eraseEdge( const V& source, const V& destination, const E& edge )
{
  auto siter = indexOf( source );
  if ( siter == graph.end() ) return;
  auto diter = indexOf( destination );
  if ( diter == graph.end() ) return;

  const Edge value{ edge, std::distance( graph.begin(), diter ) };
  auto& vector = siter->edges;
  auto liter = std::find( vector.cbegin(), vector.cend(), value );
  if ( liter != vector.cend() ) vector.erase( liter );
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::cbegin( const V& vertex ) const -> edge_iterator
{
  auto iter = std::find( graph.begin(), graph.end(), vertex );
  if ( iter == graph.end() ) throw std::out_of_range( "Vertex not in graph!" );
  return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), iter ), iter->edges.cbegin() };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::cend( const V& vertex ) const -> edge_iterator
{
  auto iter = std::find( graph.begin(), graph.end(), vertex );
  if ( iter == graph.end() ) throw std::out_of_range( "Vertex not in graph!" );
  return ALGEdgeIterator<V, E>{ std::distance( graph.begin(), iter ), iter->edges.cend() };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::operator[]( const std::size_t index ) const -> reference_type
{
  if ( index >= graph.size() ) throw std::out_of_range( "Index out of bounds!" );
  return graph[index].value;
}

template <typename V, typename E>
bool AdjacencyListGraph<V, E>::exists( const V& vertex ) const
{
  const auto iter = std::find_if( graph.cbegin(), graph.cend(),
    [&vertex]( const auto& v ) { return v.value == vertex; } );
  return iter != graph.cend();
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::find( const V& vertex ) const -> vertex_iterator
{
  const auto iter = std::find_if( graph.cbegin(), graph.cend(),
    [&vertex]( const auto& v ) { return v.value == vertex; } );
  return ALGVertexIterator<V, E>{ iter };
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::find( const V& source, const V& destination ) const -> edge_iterator
{
  const auto siter = std::find_if( graph.cbegin(), graph.cend(),
    [&source]( const auto& v ) { return v.value == source; } );
  if ( siter == graph.cend() ) return cend( source );

  const auto diter = std::find_if( graph.cbegin(), graph.cend(),
    [&destination]( const auto& v ) { return v.value == destination; } );
  if ( diter == graph.cend() ) return cend( source );

  const auto index = std::distance( graph.cbegin(), diter );
  const auto iter = std::find_if( siter->edges.cbegin(), siter->edges.cend(),
    [index] ( const auto& e ) { return e.index == index; } );
  return ALGEdgeIterator<V, E>{ std::distance( graph.cbegin(), siter ), iter };
}

template <typename V, typename E>
template <typename Visitor>
void AdjacencyListGraph<V, E>::depthFirstSearch( const Visitor& visitor ) const
{
  if ( empty() ) return;
  Visited visited( size(), false );
  for ( std::size_t i = 0; i < graph.size(); ++i )
  {
    if ( !visited[i] ) visitDfs( i, visited, visitor );
  }
}

template <typename V, typename E>
template <typename Visitor>
void AdjacencyListGraph<V, E>::breadthFirstSearch( const Visitor& visitor ) const
{
  if ( empty() ) return;
  Visited visited( size(), false );

  for ( std::size_t i = 0; i < graph.size(); ++i )
  {
    if ( !visited[i] ) visitBfs( i, visited, visitor );
  }
}

template <typename V, typename E>
auto AdjacencyListGraph<V, E>::indexOf( const V& vertex ) -> typename Graph::iterator
{
  auto iter = std::find( graph.begin(), graph.end(), vertex );
  if ( iter == graph.end() )
  {
    insert( vertex );
    iter = graph.end();
    --iter;
  }

  return iter;
}

template <typename V, typename E>
template <typename Visitor>
void AdjacencyListGraph<V, E>::visitDfs( const std::size_t index,
  Visited& visited, const Visitor& visitor ) const
{
  std::stack<std::size_t> stack;
  stack.push( index );

  while ( !stack.empty() )
  {
    std::size_t i = stack.top();
    stack.pop();
    const auto& node = graph[i];

    if ( !visited[i] )
    {
      visited[i] = true;
      visitor( node.value );
    }

    for ( auto iter = node.edges.cbegin(); iter != node.edges.cend(); ++iter )
    {
      if ( !visited[iter->index] ) stack.push( iter->index );
    }
  }
}

template<typename V, typename E>
template<typename Visitor>
void AdjacencyListGraph<V, E>::visitBfs( const std::size_t index,
  Visited & visited, const Visitor & visitor ) const
{
  std::queue<std::size_t> queue;
  queue.push( 0 );

  while ( !queue.empty() )
  {
    auto i = queue.front();
    queue.pop();
    const auto& node = graph[i];

    visitor( node.value );
    if ( !visited[i] ) visited[i] = true;

    for ( auto iter = node.edges.cbegin(); iter != node.edges.cend(); ++iter )
    {
      if ( !visited[iter->index] )
      {
        visited[iter->index] = true;
        queue.push( iter->index );
      }
    }
  }
}

// AdjacencyListGraph.cpp
#include "catch.hpp"
#include "../main/AdjacencyListGraph.h"

#include <iostream>
#include <sstream>

namespace csc280::graph
{
  struct NumberVisitor
  {
    void operator()( const uint32_t value ) const
    {
      ss << value << ", ";
    }

    std::string operator()() const { return ss.str(); }

  private:
    mutable std::stringstream ss;
  };
}

SCENARIO( "Creating an adjacency list based graph of strings" )
{
  GIVEN( "A graph of strings with a counter" )
  {
    csc280::AdjacencyListGraph<std::string, std::size_t> graph;

    WHEN( "Vertices are added to the graph" )
    {
      REQUIRE( graph.empty() );

      auto iter = graph.emplace( "Chicago" );
      REQUIRE( iter != graph.cend() );
      REQUIRE( 1 == graph.size() );
      REQUIRE_FALSE( graph.empty() );
      REQUIRE( "Chicago" == graph[0] );
      REQUIRE( "Chicago" == *iter );
      REQUIRE( "Chicago" == *graph.find( "Chicago") );
      REQUIRE( graph.exists( "Chicago" ) );
      REQUIRE_FALSE( graph.exists( "New York" ) );

      iter = graph.emplace( "Chicago" );
      REQUIRE( iter != graph.cend() );
      REQUIRE( 1 == graph.size() );

      iter = graph.emplace( "New York" );
      REQUIRE( iter != graph.cend() );
      REQUIRE( 2 == graph.size() );
      REQUIRE( "New York" == graph[1] );
      REQUIRE( "New York" == *iter );
      REQUIRE( "New York" == *graph.find( "New York") );
      REQUIRE( graph.exists( "New York" ) );

      THEN( "Edges may be added to the graph" )
      {
        auto eiter = graph.emplaceEdge( "Chicago", "New York", 900 );
        REQUIRE( eiter != graph.cend( "Chicago" ) );
        REQUIRE( 2 == graph.size() );
        REQUIRE( 900 == *eiter );
        REQUIRE( 1 == eiter.index() );

        eiter = graph.emplaceEdge( "Chicago", "New York", 1000 );
        REQUIRE( eiter != graph.cend( "Chicago" ) );
        REQUIRE( 2 == graph.size() );

        eiter = graph.emplaceEdge( "New York", "Chicago", 950 );
        REQUIRE( eiter != graph.cend( "New York" ) );
        REQUIRE( 2 == graph.size() );

        graph.eraseEdge( "New York", "Chicago", 950 );
        REQUIRE( graph.cbegin( "New York" ) == graph.cend( "New York" ) );

        eiter = graph.insertEdge( "New York", std::make_tuple( "Chicago", 950 ) );
        REQUIRE( eiter != graph.cend( "New York" ) );
        REQUIRE( 2 == graph.size() );
      }

      AND_THEN( "New vertex and edge may be added to graph in single operation" )
      {
        graph.insertEdge( "Springfield", "Chicago", 60 );
        REQUIRE( 3 == graph.size() );
        graph.insertEdge( "Springfield", "New York", 1000 );
        REQUIRE( 3 == graph.size() );
        REQUIRE( graph.exists( "Springfield" ) );
        REQUIRE( "Springfield" == *graph.find( "Springfield") );
      }

      AND_THEN( "Erasing vertex removes all dependent edges" )
      {
        graph.erase( "Chicago" );
        REQUIRE_FALSE( graph.exists( "Chicago" ) );
        const auto eiter = graph.find( "New York", "Chicago" );
        REQUIRE( eiter == graph.cend( "New York" ) );
      }
    }
  }
}

SCENARIO( "Depth first search traversal for adjacency list graph" )
{
  GIVEN( "A graph of numbers" )
  {
    csc280::AdjacencyListGraph<uint32_t, bool> graph;
    graph.insertEdge( 1, 0, false );
    graph.insertEdge( 2, 1, false );
    graph.insertEdge( 3, 4, false );
    graph.insertEdge( 4, 0, false );

    WHEN( "Traversing in depth first search mode" )
    {
      const auto visitor = csc280::graph::NumberVisitor{};
      graph.depthFirstSearch( visitor );
      REQUIRE( "1, 0, 2, 3, 4, " == visitor() );
    }
  }
}

SCENARIO( "Breadth first search traversal for adjacency list graph" )
{
  GIVEN( "A graph of numbers" )
  {
    csc280::AdjacencyListGraph<uint32_t, bool> graph;
    graph.insertEdge( 0, 1, false );
    graph.insertEdge( 0, 2, false );
    graph.insertEdge( 1, 2, false );
    graph.insertEdge( 2, 0, false );
    graph.insertEdge( 2, 3, false );
    graph.insertEdge( 3, 3, false );

    WHEN( "Traversing in depth first search mode" )
    {
      const auto visitor = csc280::graph::NumberVisitor{};
      graph.breadthFirstSearch( visitor );
      REQUIRE( "0, 1, 2, 3, " == visitor() );
    }
  }
}