package graphs;

import java.io.*;
import java.lang.*;
import java.util.*;

public class ListGraph<E> implements Graph<E>, Serializable
{
	private HashMap<E, LinkedList<Edge>> noder =
		new HashMap<E, LinkedList<Edge>>(); 
	
	public void addNode(E nod)
	{
		if (noder.get(nod) != null)
			return;
		
		noder.put(nod, new LinkedList<Edge>());
	}
	
	public void connect(E nod1, E nod2, String namn, int vikt)
		throws NoSuchElementException, IllegalArgumentException,
		IllegalStateException
	{
		if (noder.get(nod1) == null)
			throw new NoSuchElementException(nod1.toString());
		if (noder.get(nod2) == null)
			throw new NoSuchElementException(nod2.toString());

		if (vikt < 0)
			throw new IllegalArgumentException("Vikt är negativ!");
		
		// Ta fram noderna till varje nod, och kolla om det finns
		// en kant mellan dem.
		LinkedList<Edge> l1 = noder.get(nod1);
		LinkedList<Edge> l2 = noder.get(nod2);
		if (finnsEdge(l1, nod2) || finnsEdge(l2, nod1))
			throw new IllegalStateException(
				"Det finns redan en kant mellan dessa noder!");
		
		// Om det inte finns någon kant mellan dem, lägg till.
		Edge e1 = new Edge(namn, vikt, nod2);
		l1.add(e1);
		noder.put(nod1, l1);
		
		Edge e2 = new Edge(namn, vikt, nod1);
		l2.add(e2);
		noder.put(nod2, l2); 
	}
	
	private boolean finnsEdge(LinkedList<Edge> l, E till)
	{
		return hittaEdge(l, till) != null;
	}

	private Edge hittaEdge(LinkedList<Edge> l, E till)
	{
		for (Edge e : l)
		{
			if (e.getNod() == till)
			{
				return e;
			}
		}
		return null;
	}

	public LinkedList<E> getNodes()
	{
		LinkedList<E> lista = new LinkedList<E>();
		Set<Map.Entry<E, LinkedList<Edge>>> set = noder.entrySet();
		Iterator<Map.Entry<E, LinkedList<Edge>>> i;
		for (i = set.iterator(); i.hasNext(); )
		{
			Map.Entry<E, LinkedList<Edge>> e = i.next();
			lista.add((E) e.getKey());
		}
		/*
		Iterator<E, Edge> i;
		for (i=noder.iterator(); i.hasNext(); )
		{
			lista.add(i.next());
		}
		*/
		return lista;
	}
	
	public LinkedList<Edge> getEdgesFrom(E nod) throws NoSuchElementException
	{
		if (noder.get(nod) == null)
			throw new NoSuchElementException(nod.toString());
		
		return noder.get(nod);
	}
	
	public String getEdgeName(E nod1, E nod2)
		throws NoSuchElementException // null
	{
		finnsNoder(nod1, nod2);
		
		Edge e = hittaEdge(noder.get(nod1), nod2);
		if (e == null)
			return null;
		return e.getNamn();
	}
		
	public int getEdgeWeight(E nod1, E nod2)
		throws NoSuchElementException // -1
	{
		finnsNoder(nod1, nod2);
		
		Edge e = hittaEdge(noder.get(nod1), nod2);
		if (e == null)
			return -1;
		return e.getVikt();
	}
		
	public void setEdgeWeight(E nod1, E nod2, int nyVikt)
		throws NoSuchElementException, IllegalArgumentException
	{
		finnsNoder(nod1, nod2);
		
		if (nyVikt < 0)
			throw new IllegalArgumentException("Vikt är negativ!");
		
		Edge e = hittaEdge(noder.get(nod1), nod2);
		if (e == null)
			throw new NoSuchElementException("Finns ingen edge mellan!");
		e.setVikt(nyVikt);
	}
	
	private void finnsNoder(E nod1, E nod2)
		throws NoSuchElementException // -1
	{
		if (noder.get(nod1) == null)
			throw new NoSuchElementException(nod1.toString());
		if (noder.get(nod2) == null)
			throw new NoSuchElementException(nod2.toString());
	}
		
	public String toString()
	{
		String text = "";
		Set<Map.Entry<E, LinkedList<Edge>>> entries = noder.entrySet();
		for (Map.Entry<E, LinkedList<Edge>> me : entries)
		{
			E e = me.getKey();
			LinkedList<Edge> l = me.getValue();
			text += "from " + e.toString() + ":  ";
			int i = 0;
			for (Edge edge : l)
			{
				text += edge.toString();
				if (l.size() > 1 && i < l.size() - 1)
					text += ", ";
				i++;
			}
			text += "\n"; 
		}
		return text;
	}
	
	// Frivilligt
	
	public void disconnect(E nod1, E nod2)
		throws NoSuchElementException
	{
		finnsNoder(nod1, nod2);
		
		LinkedList<Edge> l1 = noder.get(nod1);
		LinkedList<Edge> l2 = noder.get(nod2);
		Edge e1 = hittaEdge(l1, nod2);
		Edge e2 = hittaEdge(l2, nod1);
		
		if (e1 != null && e2 != null)
		{
			taBortEdge(l1, nod2);
			taBortEdge(l2, nod1);
		}
	}
		
	private void taBortEdge(LinkedList<Edge> l, E till)
	{
		Iterator<Edge> i;
		for (i = l.iterator(); i.hasNext(); )
		{
			Edge e = i.next();
			if (e.getNod() == till)
			{
				i.remove();
				return;
			}
		}
	}

	public void removeNode(E nod)
	{
		noder.remove(nod);
	}
	
	public boolean pathExists(E nod1, E nod2)
	{
		if (noder.get(nod1) == null || noder.get(nod2) == null)
			return false;
		
		HashMap<E, Boolean> wrap = new HashMap<E, Boolean>();
		
		pathExists(nod1, wrap);
		
		return wrap.get(nod2) != null && wrap.get(nod2);
	}
	
	private void pathExists(E nod, HashMap<E, Boolean> wrap)
	{
		wrap.put(nod, new Boolean(true));
		for (Edge e : noder.get(nod))
		{
			E n = (E) e.getNod();
			if (wrap.get(n) == null || !wrap.get(n))
				pathExists(n, wrap);
		}
	}
	
	public LinkedList<E> getShortestPath(E nod1, E nod2)
	{
		return null;
	}
}