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

1234567890123456789012345678901234567890123456789012345678901234567890

2016-03-22: Developed Scala version from 2015 Haskell version
2016-03-21: Made comments more consistent with 2018 ELIFP Ch. 23 and
            revised trait Digraph

LIST 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: some implementations, it may be desirable to require
VertexType to be totally ordered.


** Labeled Digraph Representation **

This implementation represents a labeled digraph as an instance of the
Scala class DigraphList(vs,es).

In an instance DigraphList(vs, es):
    vs is a list of tuples (v,vl) where
      - v has VertexType and represents a vertex of the digraph
      - vl has VertexLabelType and is the unique label associated
        with vertex v
      - a vertex v occurs at most once in vs
        (i.e., vs encodes a function from vertices to vertex labels)

    es is a list of tuples (v1,v2,el) where
      - v1 and v2 are vertices occurring in vs, representing a 
        directed edge from v1 to v2
      - el has EdgeLabelType and is the unique label associated with
        edge (v1,v2)
      - an edge (v1,v2) occurs at most once in vs
        (i.e., es encodes a function from edges to edge labels)

In terms of the abstract model, vs encodes VL directly and, because VL
is a total function on V, it encodes V indirectly.  Similarly, es
encodes EL directly and E indirectly.

** Implementation Invariant **

    Any Scala Digraph value DigraphList(vs,es) 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 v, l :: (v,l) IN vs  <=> (v,l) IN VL ) &&
        (ForAll v1, v2, m :: (v1,v2,m) IN es  <=> ((v1,v2),m) IN EL )

 */

class DigraphList[A,B,C] private 
      (private val vs: List[(A,B)], private val es: List[(A,A,C)])
      extends Digraph[A,B,C] {

/* Class DigraphList mixes in trait Digraph. It has a private default
   constructor, which can only be called from within the class. The
   constructor parameters are also fields private to the class.

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

 */

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

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

  def this() {
    this(Nil,Nil)
  }

/* A copy constructor constructs this DigraphList 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 DigraphList. To do this, adding a
   function that dumps the entire graph in a standard list form would
   be helpful (e.g. combining allVertexLabels and fromEdgeLabels
   functionality).

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

  def this(dg: DigraphList[A,B,C]) {
    this(dg.vs,dg.es)
  }
  

/* Accessor 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 = vs match {
    case Nil => true  // assumes invariant holds, so es == Nil
    case _   => false
  }


/* Mutator 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 DigraphList((nv,nl)::vs, es)
    else 
      sys.error(s"addVertex: Vertex ${nv} already in digraph.")


/* Mutator 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 DigraphList( vs filter (w => w._1 != ov),
                       es filter (f => f._1 != ov && f._2 != ov) )
    else
      sys.error(s"removeVertex: Vertex ${ov} not in digraph.")


/* Mutator 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))
      new DigraphList(
        vs map (w => if (w._1 == ov) (ov,nl) else w), es )
    else
      sys.error(s"updateVertex: Vertex ${ov} not in digraph.")


/* Mutator 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 = 
    (vs dropWhile (w => w._1 != ov)) match {
      case Nil        =>
        sys.error(s"getVertexLabel: Vertex ${ov} not in digraph.")
      case ((_,l)::_) => l
    } // perhaps change to return Option[B]


/* Accessor 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 = 
    (vs dropWhile (w => w._1 != ov )) match {
      case Nil => false
      case _   => true
    }


/* Mutator addEdge(v1,v2,nl) 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(
        s"addEdge: Cannot add edge. Vertex ${v1} not in digraph.")
    else if (!hasVertex(v2))
      sys.error(
        s"addEdge: Cannot add edge. Vertex ${v2} not in digraph.")
    else if (hasEdge(v1,v2))
      sys.error(s"addEdge: Edge (${v1},${v2}) already in digraph.")
    else
      new DigraphList (vs, (v1,v2,nl)::es)


/* Mutator 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))
      new DigraphList( vs,
                       es filter (w => w._1 != v1 || w._2 != v2) )
    else
      sys.error("removeEdge: Edge (${v1},${v2}) not in digraph.")


/* Mutator 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))
      new DigraphList(
        vs,
        es map (f => if ((f._1,f._2) == (v1,v2)) (v1,v2,nl) else f) )
    else
      sys.error("updateEdge: Edge (${v1},${v2}) not in digraph.")


/* Accessor 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 =
    (es flatMap
      (f => if ((f._1,f._2) == (v1,v2)) List(f._3) else Nil))
    match {
      case Nil    =>
        sys.error(s"getEdgeLabel: Edge (${v1},${v2}) not in digraph.")
      case (l::_) => l
     }  // perhaps change to return Option[C]


/* Accessor 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 =
    (es dropWhile (f => (f._1,f._2) != (v1,v2))) match {
      case Nil => false
      case _   => true
    }


/* Accessor allVertices returns a sequence of all the vertices in this
   graph.  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] = vs map (v => v._1)


/* Accessor 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')

   Note: Implementation extended to return empty list when v1 NOTIN V.
 */

  def fromEdges(v1: A): List[A] =
    es flatMap (f => if (f._1 == v1) List(f._2) else Nil)


/* Accessor 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)] = vs


/* Accessor 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')

   Note: Implementation extended to return empty list when v1 NOTIN V. */

  def fromEdgesLabels(v1: A): List[(A,C)] = 
    es flatMap (f => if (f._1 == v1) List((f._2,f._3)) else Nil)


/* Override toString to print DigraphList
 */

  override def toString = s"DigraphList(${vs}; ${es})"
}