/* Labeled Digraph ADT, Immutable Method Chaining Functions
   Using immutable Scala HashMaps
   CSci 555: Functional Programming, Spring 2016
   H. Conrad Cunningham, Professor
   Computer and Information Science
   University of Mississippi

1234567890123456789012345678901234567890123456789012345678901234567890

2016-03-22: Developed Scala verson from 2015 Haskell version and 2016
            Scala List version


MAP IMPLEMENTATION OF LABELED DIGRAPH ADT

** Type Parameters **

    Type A (VertexType) objects can be compared for equality and 
    converted to strings.

    Type B (VertexLabelType) objects can be compared for equality and
    converted to strings.

    Type C (EdgeLabelType) objects that can be compared for equality
    and converted to strings.

Note: In the List version of this ADT, VertexType is only required to
be compare for equality. However, the use of the Map module for
implementation in this version requires the new type constraints.

** Labeled Digraph Representation **

This implementation represents a labeled digraph as an instance of the
Scala class DigraphMap(m), where m is a Scala Map implemented as a
trie (i.e., HashMap).

An instance of DigraphMap(m) corresponds to the abstract model as
follows:

    The keys for Map m are from VertexLabelType.

    Map m is defined for all keys v1 in vertex set V and undefined for
    all other keys.

    For some vertex v1, the value of m at key v1 is a pair (l,es) 
    where
        - l is an element of VertexLabelType and is the unique label
          associated with v1, that is, l = VL(v1).

        - es is the list of all tuples (v2,el) such that
          (v1,v2) IN E, el IN EdgeLabelType, and el = EL((v1,v2)).
          That is, (v1,v2) is an edge and el is its unique label.

** Implementation Invariant **

    Any Scala Digraph value Digraph(m) with abstract model G =
    (V,E,VL,EL), appearing in either the implicit or explicit
    parameters or return value of an operation, must also satisfy 
    the following:

        (ForAll v1, l, es :: 
            ( m(v1) defined && m(v1) == (l,es) ) <=> 
            ( VL(v1) == l && 
                (ForAll v2, el :: (v2,el) IN es <=> 
                                  EL((v1,v2)) == el) ) )

 */

import scala.collection.immutable.HashMap

class DigraphMap[A,B,C] private
      (private val m: HashMap[A,(B,List[(A,C)])])
      extends Digraph[A,B,C] {

/* Class DigraphMap mixes in trait Digraph. It has a private default
   constructor, which can only be called from within the class. The
   constructor parameter is alsoa field private to the class.

   Pre:  G(m) = (V,E,VL,EL), a valid model for a labelled digraph
   Post: G(this) = G(m) && G(this) == G(this')

 */

/* Zero-parameter constructor returns a new empty instance of the
   Digraph ADT.

   Pre:  True
   Post: G(this) == ({},{},{},{})
 */

  def this() { this( new HashMap[A,(B,List[(A,C)])]() ) }

/* Copy constructor, constructs this DigraphMap instance to have same
   state as an existing instance.  NOTE: I probably should replace 
   this with a constructor that takes a generic Digraph and builds 
   a DigraphMap. To do this, adding a function that dumps the entire 
   graph in a standard list form would be helpful (e.g., combinding 
   allVertexLabels and fromEdgeLabels functionality).

   Pre:   G(dg) = (V,E,VL,EL), a valid model for a labelled digraph
   Post:  G(this) = G(dg) && G(dg) == G(dg')
 */

  def this(dg: DigraphMap[A,B,C]) { this(dg.m) }


/* isEmpty returns true if and only if this graph is empty.

   Pre:  G(this) = (V,E,VL,EL)
   Post: Result == (V == {} && E == {}) && G(this) == G(this')
 */

  def isEmpty: Boolean = m.isEmpty


/* addVertex(nv,nl) inserts vertex nv with label nl into this graph
   and returns the resulting graph.

   Pre:  G(this) = (V,E,VL,EL) && nv NOT_IN V 
   Post: G(Result) == (V UNION {nv}, E, VL UNION {(nv,nl)}, EL) &&
         G(this) == G(this')
 */

  def addVertex(nv: A, nl: B): Digraph[A,B,C] =
    if (!hasVertex(nv))
      new DigraphMap( m + (nv -> (nl, Nil:List[(A,C)])) )
    else
      sys.error("Vertex " + nv + " already in digraph")


/* removeVertex(ov) deletes vertex ov from this graph and returns the
   resulting graph.

   Pre:  G(this) =  (V,E,VL,EL) && ov IN V
   Post: G(Result) == (V', E', VL', EL') && G(this) == G(this')
         where V'  = V  - {ov}
               E'  = E  - {(ov,*),(*,ov)}
               VL' = VL - {(ov,*)}
               EL' = EL - {((ov,*),*),((*,ov),*)}
 */

  def removeVertex(ov: A): Digraph[A,B,C] =
    if (hasVertex(ov))
      new DigraphMap( (m - ov) collect // (v,(vl,es))
        { case kv => (kv._1,(kv._2._1,removeEdgeTo(ov,kv._2._2))) } )
    else
      sys.error("Vertex " + ov + " not in digraph")

  private def removeEdgeTo(ov: A, es: List[(A,C)]): List[(A,C)] =
    es filter (f => f._1 != ov)

/* updateVertex(ov,nl) changes the label on vertex ov in this graph to
   be nl and returns the resulting graph.

   Pre:  G(this) =  (V,E,VL,EL) && ov IN V
   Post: G(Result) == (V - {ov}, E, VL', EL) && G(this) == G(this')
         where VL' = (VL - {(ov,VL(ov))}) UNION {(ov,nl)}
 */

  def updateVertex(ov: A, nl: B): Digraph[A,B,C] =
    if (hasVertex(ov))
      m(ov) match {
        case (_,es) => new DigraphMap(m.updated(ov,(nl,es)))
      }
    else
      sys.error("Vertex " + ov + " not in digraph")


/* getVertexLabel(ov) returns the label from vertex ov in this graph 

   Pre:   G(this) = (V,E,VL,EL) && ov IN V
   Post:  Result == VL(ov) && G(this) == G(this')
 */

  def getVertexLabel(ov: A): B =
    if (hasVertex(ov))
      m(ov)._1
    else
      sys.error("Vertex " + ov + " not in digraph")


/* hasVertex(ov) returns true if and only if ov is a vertex of 
   this graph.

   Pre:  G(this) = (V,E,VL,EL) && ov IN VertexLabelType
   Post: G(Result) == ov IN V && G(this) == G(this')

 */

  def hasVertex(ov: A): Boolean = m.get(ov) match {
    case None    => false
    case Some(_) => true
  }


/* addEdge(v1,v2,n) inserts an edge from vertex v1 to vertex v2 in
   this graph and returns the resulting graph.

   Pre:  G(this) = (V,E,VL,EL) && v1 IN V && v2 IN V && 
                   (v1,v2) NOT_IN E
   Post: G(Result) == (V, E', VL, EL') && G(this) == G(this')
         where E'  = E  UNION {(v1,v2)}
               EL' = EL UNION {((v1,v2),nl)}
 */

  def addEdge(v1: A, v2: A, nl: C): Digraph[A,B,C] =
    if (!hasVertex(v1))
      sys.error("Cannot add edge. Vertex " + v1 + " not in digraph")
    else if (!hasVertex(v2))
      sys.error("Cannot add edge. Vertex " + v2 + " not in digraph")
    else if (hasEdge(v1,v2))
      sys.error("Edge (" + v1 + "," + v2 + ") already in digraph")
    else m(v1) match { 
      case (l,es) => new DigraphMap(m.updated(v1,(l,(v2,nl)::es)))
    }


/* removeEdge(v1,v2) deletes the edge from vertex v1 to vertex v2 
   from this graph and returns the resulting graph.

   Pre:  G(this) =  (V,E,VL,EL) V - {ov} && (v1,v2) IN E
   Post: G(Result) == (V, E - {(v1,v2)}, VL, EL - { ((v1,v2),*) } &&
         G(this) == G(this')
*/

  def removeEdge(v1: A, v2: A): Digraph[A,B,C] =
    if (hasEdge(v1,v2))
      m(v1) match {
        case (ol,es) =>
          new DigraphMap( m.updated(v1,(ol,removeEdgeTo(v2,es))) )
      }
    else 
      sys.error("Edge (" + v1 + "," + v2 + ") not in digraph")


  /* updateEdge(v1,v2,nl) changes the label on the edge from vertex v1
   to vertex v2 in this graph to have label nl and returns the 
   resulting graph.

   Pre:  G(this) = (V,E,VL,EL) && (v1,v2) IN E
   Post: G(Result) == (V, E, VL, EL') && G(this) == G(this')
         where EL' == (EL - {((v1,v2),*)}) UNION {((v2,v2),nl)
 */

  def updateEdge(v1: A, v2: A, nl: C): Digraph[A,B,C] =
    if (hasEdge(v1,v2))
      m(v1) match { 
        case (ol,es) =>
          val nes = es map (f => if (f._1 == v2) (v2,nl) else f)
          new DigraphMap(m.updated(v1,(ol,nes)))
      }
    else
      sys.error("Edge (" + v1 + "," + v2 + ") not in digraph")


  /* getEdgeLabel(v1,v2) returns the label on the edge from vertex v1
     to vertex v2 in this graph.

   Pre:  G(this) = (V,E,VL,EL) && (v1,v2) IN E
   Post: Result == EL((v1,v2)) && G(this) == G(this')
 */

  def getEdgeLabel(v1: A, v2: A): C = m.get(v1) match {
    case None =>
      sys.error("Edge (" + v1 + "," + v2 + ") not in digraph")
    case Some((_,es)) =>
      (es flatMap (f => if (f._1 == v2) List(f._2) else Nil)) match {
        case Nil    =>
          sys.error("Edge (" + v1 + "," + v2 + ") not in digraph")
        case (l::_) => l
      }
  }


  /* hasEdge(v1,v2) returns true if and only if there is an edge
     from a vertex v1 to a vertex v2 in this graph.

   Pre:  G(this) = (V,E,VL,EL) 
   Post: Result == (v1,v2) IN E && G(this) == G(this')
 */

  def hasEdge(v1: A, v2: A): Boolean = m.get(v1) match {
    case None          => false
    case Some((vl,es)) => es exists (vl => vl._1 == v2)
  }


/* allVertices returns a sequence of all the vertices in this graph g. 
   The sequence is represented by a builtin Scala List.

   Pre:  G(this) = (V,E,VL,EL)
   Post: (ForAll ov: ov IN Result <=> ov IN V) && 
         length(Result) == size(V) && G(this) == G(this')
 */

  def allVertices: List[A] = m.keys.toList


/* fromEdges(v1) returns a sequence of all vertices v2 such that
   there is an edge from vertex v1 to vertex v2 in this graph.  The
   sequence is represented by a builtin Scala List.

   Pre:  G(this) = (V,E,VL,EL) && v1 IN V
   Post: (ForAll v2: v2 IN Result <=> (v1,v2) IN E) &&
         length(Result) == (# v2 :: (v1,v2) IN E) &&
	 G(this) == G(this')
 */

  def fromEdges(v1: A): List[A] = m.get(v1) match {
    case None         => Nil
    case Some((l,es)) => es map (_._1)
  }


/* allVerticesLabels returns a sequence of all pairs (v,l) such
   that v is a vertex and l is it's label in this graph.  The 
   sequence is represented by a builtin Scala List..

   Pre:  G(this) = (V,E,VL,EL)
   Post: (ForAll v, l: (v,l) IN Result <=> (v,l) IN VL) && 
         length(Result) == size(VL) && G(this) == G(this')
 */

  def allVerticesLabels: List [(A,B)] =
    m.iterator.toList  map  (kv => (kv._1, kv._2._1))


/* fromEdgesLabels(v1) returns a sequence of all pairs (v2,l) such
   that there is an edge (v1,v2) labeled with l in this graph.

   Pre:  G(this) = (V,E,VL,EL) && v1 IN V
   Post: (ForAll v2, l :: (v2,l) IN Result <=> ((v1,v2),l) IN EL) &&
         length(Result) == (# v2 :: (v1,v2 ) IN E) &&
	 G(this) == G(this')
 */ 

  def fromEdgesLabels(v1: A): List[(A,C)] = m.get(v1) match {
    case None         => Nil
    case Some((l,es)) => es
  }


  /* Override toString to print DigraphMap
  */

  override def toString =
    "DigraphMap(" + m.iterator.toList + ")"

}