#pragma once

#include <iterator>				// for std::iterator
#include <boost/shared_ptr.hpp>		 // for boost::shared_ptr

#include <iostream>                  // for std::cout
#include <string>					 // for std::string
#include <algorithm>                 // for std::for_each
#include <vector>
#include <map>

typedef std::string T;
typedef unsigned T2;

class Graph
{
public:
	class GraphNode;
	/** This value represents the directed edge between two nodes.
	 *
	 * GraphEdge is possesed by node,
	 * so if an end point node is destructed,
	 * the edge becomes undefined.
	 * copyable? No.
	 * changeable? value.
	 */
	class GraphEdge
	{
	public:
		typedef boost::shared_ptr<GraphEdge> shared_ptr;
		typedef std::vector<GraphEdge::shared_ptr> list;
		
		GraphEdge()
				:m_signature(INVALID_SIGN)
		{
		}
		GraphEdge(GraphNode* head, GraphNode* tail, T2 value)
				:m_head(head), m_tail(tail),
				 m_value(value),
				 m_signature(VALID_SIGN)
		{
		}
		/** T2 must have default value.*/
		GraphEdge(GraphNode* head, GraphNode* tail)
				:m_head(head), m_tail(tail),
				 m_signature(VALID_SIGN)
		{
		}
		/** This is head node.*/
		GraphNode* head()const
		{
			invariant();
			return m_head;
		}
		/** This is tail node.*/
		GraphNode* tail()const
		{
			invariant();
			return m_tail;
		}
		/** This is getter method for edge value.*/
		T2 getValue()const
		{
			invariant();
			return m_value;
		}
		/** This setter method is used to assign the edge value.*/
		void setValue(T2 value)
		{
			invariant();
			m_value = value;
		}
		/** Identity; if the values are not same, they are same edge.*/
		bool operator==(const GraphEdge& rh)const
		{
			if (isValid() && rh.isValid()){
				return m_head == rh.m_head && m_tail == rh.m_tail;
			} else if (!isValid() && !rh.isValid()){
				return true;
			} else {
				return false;
			}
		}
		/** get invalid edge.*/
		static GraphEdge::shared_ptr getInvalid()
		{
			static GraphEdge::shared_ptr invalid(new GraphEdge);
			return invalid;
		}
		/** check legal signature.*/
		bool isValid()const
		{
			return m_signature == VALID_SIGN;
		}
	private:
		/** This method is set to check invariant assertions.*/
		void invariant()const
		{
			assert(isValid());
		}
		GraphNode* m_head;
		GraphNode* m_tail;
		T2 m_value;				// This can be used weight or type of edge.
		enum constant{
			VALID_SIGN = 0x1234, INVALID_SIGN,
		};
		unsigned m_signature;
	};
	/** This container allocate data in the graph.
	 *  copyable? No.
	 */
	class GraphNode
	{
	private:
		enum constant{
			VALID_SIGN = 0x1234, INVALID_SIGN,
		};
		
		T m_data;
		GraphEdge::list m_in_edge_list;
		GraphEdge::list m_out_edge_list;
		unsigned m_signature;
	public:
		typedef boost::shared_ptr<GraphNode> shared_ptr;
		/** default is invalid.*/
		GraphNode()
				:m_signature(INVALID_SIGN)
		{
		}
		/** This constructer is used to set entity to node */
		GraphNode(const T& data)
				:m_data(data),
				 m_signature(VALID_SIGN)
		{
		}
		/** get contained data.*/
		T get()const
		{
			invariant();
			return m_data;
		}
		/** add edge. */
		void add(GraphEdge::shared_ptr e)
		{
			invariant();
			if (e->head() == this) {
				m_out_edge_list.push_back(e);
			} else if (e->tail() == this) {
				m_in_edge_list.push_back(e);
			}
		}
		/** if v->u, then remove the edge.*/
		void remove(GraphEdge::shared_ptr e)
		{
			invariant();
			if (e->head() == this) {
				removeEdgeFrom(e, &m_out_edge_list);
			} else if (e->tail() == this) {
				removeEdgeFrom(e, &m_in_edge_list);
			}
		}
		/** clear both edge lists.*/
		void clear()
		{
			invariant();
			clearEdgeList(&m_out_edge_list);
			clearEdgeList(&m_in_edge_list);
		}
		/** O(n), This query method returns whether v -> u.
		 * it doesn't consider in edge.
		 */
		bool isAdjacent(GraphNode* that)const
		{
			invariant();
			const GraphEdge::list* list = &m_out_edge_list;
			for (auto i=list->begin(); i!=list->end();++i){
				if ((*i)->tail() == that) {
					return true;
				}
			}
			return false;
		}
		const GraphEdge::list* inEdgeList()const
		{
			invariant();
			return &m_in_edge_list;
		}
		const GraphEdge::list* outEdgeList()const
		{
			invariant();
			return &m_out_edge_list;
		}
		/** This query method represents whether this has been constructed.*/
		bool isValid()const
		{
			return m_signature == VALID_SIGN;
		}
		/** This class method provides singleton invalid. */
		static GraphNode::shared_ptr getInvalid()
		{
			static GraphNode::shared_ptr invalid(new GraphNode);
			return invalid;
		}
	private:
		/* called from remove: to get rid of the edge from the list.*/
		void removeEdgeFrom(GraphEdge::shared_ptr e, GraphEdge::list* list)
		{
			auto new_end = std::remove(list->begin(), list->end(), e);
			list->erase(new_end, list->end());
		}
		/** called from clear*/
		void clearEdgeList(GraphEdge::list* list)
		{
			for (auto i=list->begin(); i!=list->end();++i){
				if ((*i)->head() == this) {
					(*i)->tail()->remove(*i);
				} else {
					(*i)->head()->remove(*i);
				}
			}
			list->clear();
		}
		/** This method is set to check invariant assertions.*/
		void invariant()const
		{
			assert(isValid());
		}
	};
public:
	class GraphPrinter
	{
		std::ostream& os;
	public:
		GraphPrinter(std::ostream& output_stream)
				:os(output_stream)
		{
		}
		void print(const GraphEdge& edge)const
		{
			os << edge.head()->get() << " -> " << edge.tail()->get();
		}
		void print(const GraphNode& node)const
		{
			os << node.get() << std::endl;
			print(node.outEdgeList());
			print(node.inEdgeList());
		}
		void print(const GraphEdge::list* list)const
		{
			for (auto i=list->begin(); i!=list->end(); ++i) {
				print(**i);
				os << std::endl;
			}
		}
	};
	/** This value provides iteration of nodes.*/
	class GraphIterator
		: public std::iterator<std::bidirectional_iterator_tag, T>
	{
	public:
		GraphIterator()
		{
		}
		GraphIterator(const GraphIterator& that)
		{
		}
	};
	/** From here, the definition of Graph.*/
	typedef boost::shared_ptr<Graph> shared_ptr;
	typedef GraphIterator iterator;
	
	Graph()
	{
	};
	~Graph()
	{
	}
	Graph::iterator begin()const
	{
		Graph::iterator i;
		return i;
	}
	Graph::iterator end()const
	{
		Graph::iterator i;
		return i;
	}
	unsigned size()const
	{
		return m_node_map.size();
	}
	bool empty()const
	{
		return m_node_map.empty();
	}
	Graph::iterator find(T value)
	{
		Graph::iterator i;
		return i;
	}
	void insert(Graph::iterator i)
	{
	}
	void remove(Graph::iterator i)
	{
	}
	void swap(Graph::iterator i)
	{
	}
	void clear()
	{
	}
	/** O(1): check whether node exists or not.*/
	bool hasNode(T element)const
	{
		return m_node_map.find(element) != m_node_map.end();
	}
	/** O(1): This method is get node pointer by element.*/
	GraphNode::shared_ptr getNode(T element)const
	{
		auto i = m_node_map.find(element);
		if (i != m_node_map.end()){
			return i->second;
		} else {
			return GraphNode::getInvalid();
		}
	}
	/** O(1): This method is used to create new node into the graph.*/
	void addNode(T element)
	{
		if (m_node_map.find(element) == m_node_map.end()) {
			GraphNode::shared_ptr new_node(new GraphNode(element));
			m_node_map[element] = new_node;
		}
		assert(m_node_map.find(element) != m_node_map.end());
	}
	/** O(n): This method is used to remove node and its edges.*/
	void removeNode(T element)
	{
		auto i = m_node_map.find(element);
		if (i != m_node_map.end()) {
			GraphNode::shared_ptr v = i->second;
			removeEdgeListOfNode(element);
			v->clear();
			m_node_map.erase(i);
		}
		assert(m_node_map.find(element) == m_node_map.end());
	}
	/** private: remove all edges of the node from list.*/
	void removeEdgeListOfNode(T element)
	{
		GraphEdge::list* list = &m_edge_list;
		for (auto i=list->begin(); i!=list->end(); ) {
			T head = (*i)->head()->get();
			T tail = (*i)->tail()->get();
			if (head == element || tail == element) {
				i = m_edge_list.erase(i);
			} else {
				++i;
			}
		}
	}
	bool isAdjacent(T head, T tail)const
	{
		return hasEdge(head, tail);
	}
	std::vector<T> neighbor_list(T element)const
	{
		std::vector<T> result;
		return result;
	}
	/** This query method checks whether the directed edge exists.*/
	bool hasEdge(T head, T tail)const
	{
		return getEdgeIterator(head, tail) != m_edge_list.end();
	}
	/** This query method is used to get edge by 2 elements.*/
	GraphEdge::shared_ptr getEdge(T head, T tail)const
	{
		auto i = getEdgeIterator(head, tail);
		if (i != m_edge_list.end()) {
			return *i;
		} else {
			return GraphEdge::getInvalid();
		}
	}
	/** add edge, and nodes if necessary.*/
	void addEdge(T head, T tail, T2 edge_value)
	{
		if (!hasNode(head)){
			addNode(head);
		}
		if (!hasNode(tail)) {
			addNode(tail);
		}
		GraphNode* v = getNode(head).get();
		GraphNode* u = getNode(tail).get();;
		
		GraphEdge::shared_ptr new_edge(new GraphEdge(v,u,edge_value));
		m_edge_list.push_back(new_edge);
		v->add(new_edge);
		u->add(new_edge);
	}
	/** This method is used to remove the edge from the end points and list.*/
	void removeEdge(T head, T tail)
	{
		auto i = getEdgeIterator(head, tail);
		GraphEdge::list* list = &m_edge_list;
		
		if (i != list->end()){
			(*i)->head()->remove(*i);
			(*i)->tail()->remove(*i);
			list->erase(i);
		}
	}
	/** for display */
	void displayNodeList(std::ostream& os)const
	{
		for (auto i=m_node_map.begin(); i!=m_node_map.end(); ++i) {
			GraphNode::shared_ptr v = i->second;
			os << v->get();
			os << std::endl;
		}
	}
	/** for display*/
	void displayEdgeList(std::ostream& os)const
	{
		GraphPrinter printer(os);
		printer.print(&m_edge_list);
	}
private:
	/** implement: for find and erase.*/
	GraphEdge::list::const_iterator getEdgeIterator(T head, T tail)const
	{
		for (auto i=m_edge_list.begin(); i!=m_edge_list.end(); ++i) {
			if ((*i)->head()->get() == head
				&& (*i)->tail()->get() == tail) {
				return i;
			}
		}
		return m_edge_list.end();
	}
	/** implement */
	GraphEdge::list::iterator getEdgeIterator(T head, T tail)
	{
		for (auto i=m_edge_list.begin(); i!=m_edge_list.end(); ++i) {
			if ((*i)->head()->get() == head
				&& (*i)->tail()->get() == tail) {
				return i;
			}
		}
		return m_edge_list.end();
	}
	
	std::map<T, GraphNode::shared_ptr> m_node_map;
	GraphEdge::list m_edge_list;
};

