import java.util.LinkedList;
import java.util.Vector;
import java.util.Iterator;

/**
 * <p>
 * Stores the topology of an instantaneous communication graph, as well
 * as the message queues between each pair of robots connected in the graph.
 * Can be used to hold directed and undirected edges.
 * Edge addition functions copy message queues from prior graph, if one
 * is provided.
 * </p> <p>
 * Graph representation is in the form of two adjacency lists
 * (see <a href="http://www.nist.gov/dads/HTML/adjacencyListRep.html">
 * http://www.nist.gov/dads/HTML/adjacencyListRep.html</a> for
 * documentation on adjacency lists) (also see Cormen, Leierson, Rivest, Stein
 * Chapter 22)
 * One adjacency list is for quick lookup for all edges incoming to a
 * particular node, the other is for all edges outgoing to a particular node.
 * The two structures edge share representation memory for each shared edge.
 * </p>
 * @author     Michael Schuresko
 * @version    %I%, %G%
 * @since      1.0
*/

public class CommGraph
{
    Vector<LinkedList<CommLink> > m_adjListTo;
    Vector<LinkedList<CommLink> > m_adjListFrom;

    IMsgChannel m_channelToClone;

    public CommGraph() {
	m_adjListTo = m_adjListFrom = null;
	m_channelToClone = new MsgQueue();
    }

    /**
     * Creates an empty graph (no edges) on nNumNodes nodes
     */
    public CommGraph(int nNumNodes)
    {
	m_adjListTo = 
		new Vector<LinkedList<CommLink> >(nNumNodes); 
	m_adjListFrom = 
		new Vector<LinkedList<CommLink> >(nNumNodes);

	// Make sure we never have an empty linked list in here
	for(int i = 0; i < nNumNodes; ++i) {
	    m_adjListTo.add(i,new LinkedList<CommLink>());
	    m_adjListFrom.add(i,new LinkedList<CommLink>());
	}
	m_channelToClone = new MsgQueue();
    }

    /**
     * Copy constructor -- performs deep copy of graph
     */
    public CommGraph(CommGraph src) {
	m_channelToClone = src.m_channelToClone.makeCopy();
	int nSrcCapacity = src.m_adjListTo.capacity(); 
	m_adjListTo = 
		new Vector<LinkedList<CommLink> >(nSrcCapacity);
	nSrcCapacity = src.m_adjListFrom.capacity();
	m_adjListFrom = 
		new Vector<LinkedList<CommLink> >(nSrcCapacity);

	for(int i = 0; i < nSrcCapacity; ++i) {
	    m_adjListTo.add(i, new LinkedList<CommLink>());
	    m_adjListFrom.add(i, new LinkedList<CommLink>());
	    Iterator<CommLink> iterTo = src.getEdgesTo(i);
	    while(iterTo.hasNext()) {
		CommLink currLink = (CommLink)iterTo.next();
		m_adjListTo.get(i).addLast(new CommLink(currLink));
	    }
	    Iterator<CommLink> iterFrom = src.getEdgesFrom(i);
	    while(iterFrom.hasNext()) {
		CommLink currLink = (CommLink)iterFrom.next();
		m_adjListFrom.get(i).addLast(new CommLink(currLink));
	    }
	}
    }

    /**
     * Changes the default channel type for new links
     * new channels are all of the same type as channelToClone
     */
    public void setChannelType(IMsgChannel channelToClone)
    {
	m_channelToClone = channelToClone.makeCopy();
    }
    
    public IMsgChannel getChannelType() 
    {
    	return m_channelToClone.makeCopy();
    }

    /**
     * @param nNodeFrom node to get outgoing edges of
     * @return iterator for list of outgoing edges of nNodeFrom 
     * Each iterator element should be cast to type CommLink.
     */
    public Iterator<CommLink> getEdgesFrom(int nNodeFrom)
    {
    	return m_adjListFrom.elementAt(nNodeFrom).iterator();
    }
    
    /**
     * @param nNodeTo node to get incoming edges of
     * @return iterator for list of incoming edges of nNodeTo
     * Each iterator element should be cast to type CommLink.
     */
    public Iterator<CommLink> getEdgesTo(int nNodeTo)
    {
    	return m_adjListTo.elementAt(nNodeTo).iterator();
    }

    /**
     * Insert an exsting CommLink into this graph.
     * @param link link to insert
     */
    public void insertExistLink(CommLink link)
    {
	// Don't check for error, instead force the exception.
    	m_adjListTo.elementAt(link.to()).addLast(link);
    	m_adjListFrom.elementAt(link.from()).addLast(link);
	}

    /**
     * Clones a link between two nodes (if it exists)
     * Used internally by addLink
     * @param iSrc source of link to clone
     * @param iDst dest of link to clone
     * @return copy of link from iSrc to iDst, or new link if none exists
     */
    CommLink cloneLink(int iSrc, int iDst)
    {
	LinkedList<CommLink> lToSearch = m_adjListFrom.get(iSrc);
	CommLink toClone = null;
	for(Iterator<CommLink> I = lToSearch.iterator(); I.hasNext();) {
	    CommLink currListEl = (CommLink)I.next();
	    if(currListEl != null && currListEl.to() == iDst) {
		toClone = currListEl;
	    }
	}
	if(toClone != null) {
	    return new CommLink(toClone);
	}
	return new CommLink(iSrc, iDst, m_channelToClone.makeLazyCopy());
    }

    /**
     * Adds a new link (directed edge) to a graph.
     * Copies channel from previous state communication graph if
     * available
     * @param iSrc source index of link to add
     * @param iDst destination index of link to add
     * @param gCopyLinksFrom previous graph (to copy communication channels from if available)  Can be null.
     * @return newly created link
     */
    public CommLink addLink(int iSrc, int iDst, CommGraph gCopyLinksFrom)
    {
	CommLink linkNew = null;
	if(gCopyLinksFrom == null) {
	    linkNew = new CommLink(iSrc, iDst, m_channelToClone);
	}
	else {
	    linkNew = gCopyLinksFrom.cloneLink(iSrc, iDst);
	}
	insertExistLink(linkNew);
	return linkNew;
    }

    /**
     * Adds a new link (directed edge) to a graph.
     * Copies channel from previous state communication graph if
     * available
     * @param iSrc source index of link to add
     * @param iDst destination index of link to add
     * @param channelData associated channel data
     * @param gCopyLinksFrom previous graph (to copy communication channels from if available)  Can be null.
     * @return newly created link
     */
    public CommLink addLink(int iSrc, int iDst, 
    		CommLink.IChannelData channelData,
    		CommGraph gCopyLinksFrom)
    {
	CommLink linkNew = null;
	if(gCopyLinksFrom == null) {
	    linkNew = new CommLink(iSrc, iDst, m_channelToClone);
	}
	else {
	    linkNew = gCopyLinksFrom.cloneLink(iSrc, iDst);
	}
	linkNew.setChannelData(channelData);
	insertExistLink(linkNew);
	return linkNew;
    }

    
    /**
     * @return Number of nodes in graph
     */
    public int getSize() { 
	if(m_adjListTo == null) {
	    return 0;
	}
	return m_adjListTo.capacity(); 
    }
}