Sorting.hs

-- | Utilities for sorting.

module Hydra.Sorting where

import qualified Hydra.Lib.Lists as Lists
import qualified Hydra.Lib.Logic as Logic
import qualified Hydra.Lib.Maps as Maps
import qualified Hydra.Lib.Optionals as Optionals
import qualified Hydra.Mantle as Mantle
import qualified Hydra.Tarjan as Tarjan
import qualified Hydra.Topology as Topology
import Prelude hiding  (Enum, Ordering, fail, map, pure, sum)
import qualified Data.Int as I
import qualified Data.List as L
import qualified Data.Map as M
import qualified Data.Set as S

createOrderingIsomorphism :: (Ord t0) => ([t0] -> [t0] -> Topology.OrderingIsomorphism t1)
createOrderingIsomorphism sourceOrd targetOrd =  
  let sourceToTargetMapping = (\els ->  
          let mp = (Maps.fromList (Lists.zip sourceOrd els))
          in (Optionals.cat (Lists.map (\n -> Maps.lookup n mp) targetOrd)))
  in  
    let targetToSourceMapping = (\els ->  
            let mp = (Maps.fromList (Lists.zip targetOrd els))
            in (Optionals.cat (Lists.map (\n -> Maps.lookup n mp) sourceOrd)))
    in Topology.OrderingIsomorphism {
      Topology.orderingIsomorphismEncode = sourceToTargetMapping,
      Topology.orderingIsomorphismDecode = targetToSourceMapping}

topologicalSort :: (Ord t0) => ([(t0, [t0])] -> Mantle.Either [[t0]] [t0])
topologicalSort pairs =  
  let sccs = (topologicalSortComponents pairs)
  in  
    let isCycle = (\scc -> Logic.not (Lists.null (Lists.tail scc)))
    in  
      let withCycles = (Lists.filter isCycle sccs)
      in (Logic.ifElse (Lists.null withCycles) (Mantle.EitherRight (Lists.concat sccs)) (Mantle.EitherLeft withCycles))

topologicalSortComponents :: (Ord t0) => ([(t0, [t0])] -> [[t0]])
topologicalSortComponents pairs =  
  let graphResult = (Tarjan.adjacencyListsToGraph pairs)
  in  
    let g = (fst graphResult)
    in  
      let getKey = (snd graphResult)
      in (Lists.map (\comp -> Lists.map getKey comp) (Tarjan.stronglyConnectedComponents g))

topologicalSortNodes :: (Ord t1) => ((t0 -> t1) -> (t0 -> [t1]) -> [t0] -> [[t0]])
topologicalSortNodes getKey getAdj nodes =  
  let nodesByKey = (Maps.fromList (Lists.map (\n -> (getKey n, n)) nodes))
  in  
    let pairs = (Lists.map (\n -> (getKey n, (getAdj n))) nodes)
    in  
      let comps = (topologicalSortComponents pairs)
      in (Lists.map (\c -> Optionals.cat (Lists.map (\k -> Maps.lookup k nodesByKey) c)) comps)