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

1234567890123456789012345678901234567890123456789012345678901234567890

2016-03-22: Developed Scala version from 2015 Haskell version


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: For 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 
    paramters 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))

 */

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

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

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

/* 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., combinding 
   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)
  }
  

/* 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
  }


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


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


/* 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
    }


/* 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("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
      new DigraphList (vs, (v1,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))
      new DigraphList( vs,
                       es filter (w => w._1 != v1 || w._2 != v2) )
    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))
      new DigraphList(
        vs,
        es map (f => if ((f._1,f._2) == (v1,v2)) (v1,v2,nl) else f) )
    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 =
    (es flatMap
        (f => if ((f._1,f._2) == (v1,v2)) List(f._3) else Nil)) match {
      case Nil    =>
        sys.error("Edge (" + v1 + "," + v2 ++ ") not in digraph")
      case (l::_) => l
     }  // perhaps change to return Option[C]


/* 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
    }


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


/* 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] =
    es flatMap (f => if (f._1 == v1) List(f._2) else Nil)


/* 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


/* 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)] = 
    es flatMap (f => if (f._1 == v1) List((f._2,f._3)) else Nil)


  /* Override toString to print DigraphList
  */

  override def toString =
    "DigraphMap(" + vs + "; " + es + ")"
}