-- | Build up shared prefix trees
module System.FilePattern.Tree(
    Tree(..), makeTree
    ) where

import Data.List.Extra
import Prelude


data Tree k v = Tree [v] [(k, Tree k v)]

makeTree :: Ord k => [(v, [k])] -> Tree k v
makeTree :: forall k v. Ord k => [(v, [k])] -> Tree k v
makeTree = forall {a} {v}. Eq a => [(v, [a])] -> Tree a v
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn forall a b. (a, b) -> b
snd
    where
        f :: [(v, [a])] -> Tree a v
f [(v, [a])]
xs = forall k v. [v] -> [(k, Tree k v)] -> Tree k v
Tree (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst [(v, [a])]
empty) [(forall a b. (a, b) -> a
fst forall a b. (a -> b) -> a -> b
$ forall a. [a] -> a
head [(a, (v, [a]))]
gs, [(v, [a])] -> Tree a v
f forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd [(a, (v, [a]))]
gs) | [(a, (v, [a]))]
gs <- [[(a, (v, [a]))]]
groups]
            where
                ([(v, [a])]
empty, [(v, [a])]
nonEmpty) = forall a. (a -> Bool) -> [a] -> ([a], [a])
span (forall (t :: * -> *) a. Foldable t => t a -> Bool
null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd) [(v, [a])]
xs
                groups :: [[(a, (v, [a]))]]
groups = forall k a. Eq k => (a -> k) -> [a] -> [[a]]
groupOn forall a b. (a, b) -> a
fst [(a
x, (v
a,[a]
xs)) | (v
a,a
x:[a]
xs) <- [(v, [a])]
nonEmpty]