{-|
Module      : Gargantext.Core.Viz.Graph.Bridgeness
Description : Bridgeness filter
Copyright   : (c) CNRS, 2017-Present
License     : AGPL + CECILL v3
Maintainer  : team@gargantext.org
Stability   : experimental
Portability : POSIX

Let be a graph Bridgeness filters inter-communities links in two ways.
If the partitions are known, filtering is uniform to expose the communities clearly for the beginners.
But


uniformly
filters inter-communities links.

TODO use Map LouvainNodeId (Map LouvainNodeId)
-}

{-# LANGUAGE BangPatterns #-}

module Gargantext.Core.Viz.Graph.Bridgeness -- (bridgeness)
  where

import Data.Map.Strict (Map, fromListWith, lookup, toList, mapWithKey, elems)
import Data.Maybe (catMaybes)
import Data.Ord (Down(..))
import Data.Set (Set)
import Data.Tuple.Extra (swap)
import Debug.Trace (trace)
import Gargantext.Core.Methods.Similarities (Similarity(..))
import Gargantext.Prelude
import Prelude (pi)
import Graph.Types (ClusterNode(..))
import qualified Data.List        as List
import qualified Data.Map.Strict  as Map
import qualified Data.Set         as Set
import qualified Data.Tuple.Extra as Tuple
import qualified Data.IntMap      as Dico
----------------------------------------------------------------------

type Partitions = Map (Int, Int) Double -> IO [ClusterNode]
type Partitions' = Map (Int, Int) Double -> IO [Set NodeId]
----------------------------------------------------------------------
nodeId2comId :: ClusterNode -> (NodeId, CommunityId)
nodeId2comId (ClusterNode i1 i2) = (i1, i2)

type NodeId        = Int
type CommunityId   = Int

----------------------------------------------------------------------
-- recursiveClustering : to get more granularity of a given clustering
-- tested with spinglass clustering only (WIP)
recursiveClustering' :: Partitions' -> Map (Int, Int) Double -> IO [[Set NodeId]]
recursiveClustering' f mp = do
  let
    n :: Double
    n = fromIntegral $ Set.size
      $ Set.unions  $ List.concat
      $ map (\(k1,k2) -> map Set.singleton [k1, k2])
      $ Map.keys mp

    t :: Int
    t = round $ 2 * n / sqrt n

  ss <- f mp
  mapM (\s -> if Set.size s > t then f (removeNodes s mp) else pure [s]) ss

----------------------------------------------------------------------
recursiveClustering :: Partitions -> Map (Int, Int) Double -> IO [ClusterNode]
recursiveClustering f mp = do
  let
    n :: Double
    n = fromIntegral $ Set.size
      $ Set.unions  $ List.concat
      $ map (\(k1,k2) -> map Set.singleton [k1, k2])
      $ Map.keys mp

    t :: Int
    t = round $ 2 * n / sqrt n

  (toSplit,others) <- List.span (\a -> Set.size a > t) <$> clusterNodes2sets <$> f mp
  cls' <- mapM f $ map (\s -> removeNodes s mp) toSplit
  pure $ setNodes2clusterNodes $ others <> (List.concat $ map clusterNodes2sets cls')


----------------------------------------------------------------------
setNodes2clusterNodes :: [Set NodeId] -> [ClusterNode]
setNodes2clusterNodes ns = List.concat $ map (\(n,ns') -> toCluster n ns') $ zip [1..] ns
  where
    toCluster :: CommunityId -> Set NodeId -> [ClusterNode]
    toCluster cId setNodeId = map (\n -> ClusterNode n cId) (Set.toList setNodeId)

clusterNodes2map :: [ClusterNode] -> Map NodeId Int
clusterNodes2map = Map.fromList . map (\(ClusterNode nId cId) -> (nId, cId))

removeNodes :: Set NodeId
            -> Map (NodeId, NodeId) Double
            -> Map (NodeId, NodeId) Double
removeNodes s = Map.filterWithKey (\(n1,n2) _v -> Set.member n1 s && Set.member n2 s)


clusterNodes2sets :: [ClusterNode] -> [Set NodeId]
clusterNodes2sets = Dico.elems
                  . Dico.fromListWith (<>)
                  . (map ((Tuple.second Set.singleton) . swap . nodeId2comId))

----------------------------------------------------------------------
data Bridgeness = Bridgeness_Basic { bridgeness_partitions :: [ClusterNode]
                                   , bridgeness_filter     :: Double
                                   }
                | Bridgeness_Advanced { bridgeness_similarity :: Similarity
                                      , bridgness_confluence  :: Confluence
                                      }
                | Bridgeness_Recursive { br_partitions :: [[Set NodeId]]
                                       , br_filter     :: Double
                                       }


type Confluence = Map (NodeId, NodeId) Double

-- Filter Links between the Clusters
-- Links: Map (NodeId, NodeId) Double
-- List of Clusters: [Set NodeId]
bridgeness :: Bridgeness
            -> Map (NodeId, NodeId) Double
            -> Map (NodeId, NodeId) Double
bridgeness (Bridgeness_Recursive sn f) m =
  Map.unions $ [linksBetween] <> map (\s -> bridgeness (Bridgeness_Basic (setNodes2clusterNodes s) f) m') sn
    where
      (linksBetween, m') = Map.partitionWithKey (\(n1,n2) _v -> Map.lookup n1 mapNodeIdClusterId
                                                             /= Map.lookup n2 mapNodeIdClusterId
                                                ) $ bridgeness (Bridgeness_Basic clusters (pi*f)) m
      clusters = setNodes2clusterNodes (map Set.unions sn)
      mapNodeIdClusterId = clusterNodes2map clusters


bridgeness (Bridgeness_Advanced sim c) m = Map.fromList
                $ List.filter (\x -> if sim == Conditional then snd x > 0.2 else snd x > 0.02)
                $ map (\(ks, (v1,_v2)) -> (ks,v1))
                -- $ List.take (if sim == Conditional then 2*n else 3*n)
                -- $ List.sortOn (Down . (snd . snd))
                $ Map.toList
                -- $ trace ("bridgeness3 m c" <> show (m,c))
                $ Map.intersectionWithKey
                      (\k v1 v2 -> trace ("intersectionWithKey " <> (show (k, v1, v2))) (v1, v2)) m c


bridgeness (Bridgeness_Basic ns b) m = Map.fromList
                                     $ List.concat
                                     $ Map.elems
                                     $ filterComs (round b)
                                     $ groupEdges (Map.fromList $ map nodeId2comId ns) m


groupEdges :: (Ord comId, Ord nodeId)
           => Map nodeId comId
           -> Map (nodeId, nodeId) value
           -> Map (comId, comId) [((nodeId, nodeId), value)]
groupEdges m = fromListWith (<>)
             . catMaybes
             . map (\((n1,n2), d)
                     -> let
                          n1n2_m = (,) <$> lookup n1 m <*> lookup n2 m
                          n1n2_d = Just [((n1,n2),d)]
                        in (,) <$> n1n2_m <*> n1n2_d
                    )
             . toList

filterComs :: (Ord n1, Eq n2)
           => Int
           -> Map (n2, n2) [(a3, n1)]
           -> Map (n2, n2) [(a3, n1)]
filterComs b m = Map.filter (\n -> length n > 0) $ mapWithKey filter' m
  where
    filter' (c1,c2) a
      | c1 == c2  = a
      -- TODO use n here
      | otherwise = take (b * 2*n) $ List.sortOn (Down . snd) a
           where
            n :: Int
            n = round $ 100 * a' / t
            a'= fromIntegral $ length a
            t :: Double
            t = fromIntegral $ length $ List.concat $ elems m

--------------------------------------------------------------
-- Utils
{--
map2intMap :: Map (Int, Int) a -> IntMap (IntMap a)
map2intMap m = IntMap.fromListWith (<>)
             $ map (\((k1,k2), v) -> if k1 < k2
                                   then (k1, IntMap.singleton k2 v)
                                   else (k2, IntMap.singleton k1 v)
                    )
             $ Map.toList m

look :: (Int,Int) -> IntMap (IntMap a) -> Maybe a
look (k1,k2) m = if k1 < k2
                    then case (IntMap.lookup k1 m) of
                           Just m' -> IntMap.lookup k2 m'
                           _       -> Nothing
                    else look (k2,k1) m


{-
Compute the median of a list
From:  https://hackage.haskell.org/package/dsp-0.2.5.1/docs/src/Numeric.Statistics.Median.html
Compute the center of the list in a more lazy manner
and thus halves memory requirement.
-}

median :: (Ord a, Fractional a) => [a] -> a
median [] = panic "medianFast: empty list has no median"
median zs =
   let recurse (x0:_)    (_:[])   = x0
       recurse (x0:x1:_) (_:_:[]) = (x0+x1)/2
       recurse (_:xs)    (_:_:ys) = recurse xs ys
       recurse _ _  =
          panic "median: this error cannot occur in the way 'recurse' is called"
   in  recurse zs zs

-}