{- | This is the second assignment for IB016, semester spring 2015.
  Name: Name Surname
  UID: 123456

  === Additional documentation / useful links

  *   <http://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Set.html Data.Set>

  *   <http://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Lazy.html Data.Map>

  *   <http://hackage.haskell.org/package/base-4.7.0.2/docs/Data-List.html Data.List>


  === Points
  You should implement all the functions as documented below. All functions
  except for 'shortestPath' are for 10 points altogether. The remaining 10 point are 
  for 'shortestPath'. You can get some bonus points for nice implementation
  or multiple algorithms.
 -}

module Graph (
    -- * Data types
      Vertex (..)
    , Edge (..)
    , Graph (..)
    -- * Construction and data manipulation helpers
    , graph
    , addVertex
    , addEdge
    , deleteVertex
    , deleteEdge
    -- * Basic querying functions
    , findVertex
    , findOutgoing
    , vertexCount
    , edgeCount
    , totalWeight
    , averageWeight
    , medianWeight
    -- * Graph search
    , shortestPath
    -- * Test graph
    , testGraph
    ) where

import Data.List
import Data.Set ( Set )
import Data.Map ( Map )
import qualified Data.Set as S
import qualified Data.Map as M

-- | Vertex of graph.
newtype Vertex = Vertex Integer deriving (Eq, Ord, Show, Read)

-- | Oriented edge.
data Edge = Edge { from :: Vertex, to :: Vertex } deriving (Eq, Ord, Show, Read)

-- | Graph, it contains set of vertices, and a associative map from edges to
-- edge values (which behaves like set with additionally associated edge value).
data Graph = Graph { vertices :: Set Vertex, edges :: Map Edge Integer }
             deriving (Eq, Show, Read)

-- | Pre-defined graph for testing purposes.
-- Corresponds to graph displayed in <https://en.wikipedia.org/wiki/Dijkstra's_algorithm>
testGraph :: Graph
testGraph = Graph (S.fromList $ map Vertex [1..6]) (M.fromList $ concatMap makeEdges edges)
  where makeEdges (from, to, weight) = [ (Edge (Vertex from) (Vertex to), weight)
                                       , (Edge (Vertex to) (Vertex from), weight)]
        edges = [ (1, 2, 7)
                , (1, 3, 9)
                , (1, 6, 14)
                , (2, 3, 10)
                , (2, 4, 15)
                , (3, 4, 11)
                , (3, 6, 2)
                , (4, 5, 6)
                , (5, 6, 9)
                ]

-- | Create empty graph.
graph :: Graph
graph = undefined

-- | Add a vetex to the graph, if it is already present, it will be overridden.
addVertex :: Vertex -> Graph -> Graph
addVertex = undefined

-- | Add an edge with given value to the graph, if the edge is present already
-- it will be overriden. If any of the edge's vertices are not in graph
-- they will be added.
addEdge :: Edge -> Integer -> Graph -> Graph
addEdge = undefined

-- | Delete vertex from graph, together will all edges which contain it.
-- If vertex is not present, nothing function has no effect.
deleteVertex :: Vertex -> Graph -> Graph
deleteVertex = undefined

-- | Delete edge from graph, does not modify vertex set. If edge is not present,
-- function has no effect.
deleteEdge :: Edge -> Graph -> Graph
deleteEdge = undefined

-- | Find all edges containing given vertex and return map from those edges to
-- their value
-- 
-- >>> findVertex (Vertex 5) testGraph
-- fromList [(Edge {from = Vertex 4, to = Vertex 5},6),
--           (Edge {from = Vertex 5, to = Vertex 4},6),
--           (Edge {from = Vertex 5, to = Vertex 6},9),
--           (Edge {from = Vertex 6, to = Vertex 5},9)]
findVertex :: Vertex -> Graph -> Map Edge Integer
findVertex = undefined

-- | Like 'findVertex' but finds all outgoing edges of given vertex.
-- 
-- >>> findOutgoing (Vertex 5) testGraph
-- fromList [(Edge {from = Vertex 5, to = Vertex 4},6),
--           (Edge {from = Vertex 5, to = Vertex 6},9)]
findOutgoing :: Vertex -> Graph -> Map Edge Integer
findOutgoing = undefined

-- | Calculte number of vertices in graph.
-- 
-- >>> vertexCount testGraph
-- 6
vertexCount :: Graph -> Int
vertexCount = undefined

-- | Calculte number of edges in graph.
-- 
-- >>> edgeCount testGraph
-- 18
edgeCount :: Graph -> Int
edgeCount = undefined

-- | Sum of all edge values.
--
-- >>> totalWeight testGraph
-- 166
totalWeight :: Graph -> Integer
totalWeight = undefined

-- | Average value of edges, if no edges are present 'Nothing' is returned.
-- Bonus: calculate average in one pass
--
-- >>> averageWeight testGraph
-- Just 9.222222222222221
averageWeight :: Fractional a => Graph -> Maybe a
averageWeight = undefined

-- | Median value of edges, if no edges are present 'Nothing' is returned.
-- In case of even number of edges, use integer division to obtain median.
--
-- >>> medianWeight testGraph
-- Just 9
medianWeight :: Graph -> Maybe Integer
medianWeight = undefined

{- | Find shortest path from one vertex to another. If there is no such path,
  or vertices are not present, return 'Nothing'.
  You can use one of:

  * Dijkstra: <https://en.wikipedia.org/wiki/Dijkstra's_algorithm>

  * Bellman-Ford: <https://en.wikipedia.org/wiki/Bellman-Ford_algorithm>

  * Floyd-Warshall: <https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm>


  Dijkstra's algorithm is the fastest if properly implemented, but its implementation
  is also the hardest. You can assume there are no edges with negative values. However,
  if the algorithm of your choice can handle them, you can detect them and return
  'Nothing' in such case.

  You can also get bonus points if you implement multiple algorithms. Just name
  them @spDijkstra@ // @spFloydWarshall@ // @spBellmanFord@ and use 'shortestPath'
  as an alias to one of them.

  >>> shortestPath (Vertex 1) (Vertex 5) testGraph
  Just 20
-}
shortestPath :: Vertex -> Vertex -> Graph -> Maybe Integer
shortestPath = undefined