module Chae.Tree
    exposing
        ( Tree
        , nil
        , map
        , map2
        , zip
        , reduce
        , filter
        , deepFilter
        , push
        , fromList
        , subTreeFor
        )

{-| Tree is list of nodes.
Tree is main data structure this package provides and this module implements the most essential functions
which really differs from general Rose Tree implementation. Along side with functor functions
trees support operation like `push`, `subTreeFor` and `fromList`. These functions make it easy to create
and manipulate trees only by knowing Ids of items.


# Definition

@docs Tree


# Constructors

@docs nil, fromList


# Query a Tree

@docs subTreeFor


# Common Operations

@docs push


# Map - Reduce

@docs map, map2, zip, reduce, filter, deepFilter

-}

import Tuple
import List
import Chae.Id exposing (..)
import Chae.Node as Node
import Maybe exposing (Maybe(..))


-- Types


{-| -}
type alias Tree a =
    List (Node.Node a)


{-| Construct empty tree
Alias for []
-}
nil : Tree a
nil =
    []


{-| Map function over tree
Similar to `List.map` but working with trees
-}
map : (a -> b) -> Tree a -> Tree b
map fc =
    List.map <| Node.map fc


{-| Map function over two trees to produce new tree from both combined
Similar to `List.map2` but working with trees
-}
map2 :
    (a -> b -> c)
    -> Tree a
    -> Tree b
    -> Tree c
map2 fc =
    List.map2 <| Node.map2 fc


{-| Zip two trees to tree of tuple
Similar to `List.zip` but working with trees
-}
zip : Tree a -> Tree b -> Tree ( a, b )
zip =
    map2 (,)


{-| Reduce Tree by given function
Similar to `List.foldr` but working with trees
-}
reduce :
    (a -> b -> b)
    -> b
    -> Tree a
    -> b
reduce reducer =
    List.foldr <| flip <| Node.reduce reducer


{-| Filter Tree.
Similar to `List.filter` but working on trees.
If parent node do not pass condition its children are no included in result

    tree = [Node.node "5" 5 [ Node.singleton "1" 1, Node.singleton "10" 10 ] ]

    filter ((<) 4) tree == [ Node "5" 5 ([Node "10" 10 []]) ]
    filter ((<) 6) tree == []
    filter ((<) 0) tree == tree

-}
filter :
    (a -> Bool)
    -> Tree a
    -> Tree a
filter fc =
    let
        sieve ( id, a, c ) acc =
            if fc a then
                Node.node id a (filter fc c) :: acc
            else
                acc
    in
        List.foldr (sieve << Node.toTuple) []


{-| Similar to `filter` but includes node when some of its child matches.

    tree = [ Node.node "5" 5 [ Node.node "1" 1 [ Node.singleton "9" 9 ], Node.singleton "10" 10 ] ]

    deepFilter ((<) 6) tree == [[ Node.node "5" 5 ([ Node.node "1" 1 ([ Node.node "9" 9 [] ]), Node.node "10" 10 [] ]) ]]
    deepFilter ((<) 11) tree == []
    deepFilter ((<) 0) tree == tree

-}
deepFilter :
    (a -> Bool)
    -> Tree a
    -> Tree a
deepFilter fc =
    let
        sieve ( id, a, c ) acc =
            let
                c_ =
                    deepFilter fc c
            in
                if fc a || not (List.isEmpty c_) then
                    Node.node id a c_ :: acc
                else
                    acc
    in
        List.foldr (sieve << Node.toTuple) []


{-| Produce new tree with given item pushed under its parent.
First argument is function from item to `Id/String`.

Second argument is `Maybe Id` is ether:

  - `Nothing` => push to root

  - `Just parentId` => push to sub Tree

    push toId Nothing 1 [] == [Node "1" 1 []]
    push toId (Just (toId 1)) 2 [ Node.singleton "1" 1 ] == [Node "1" 1 ([Node "2" 2 []])]

-}
push :
    (a -> Id)
    -> Maybe Id
    -> a
    -> Tree a
    -> Tree a
push getId maybeId item tree =
    case maybeId of
        Nothing ->
            Node.singleton (getId item) item :: tree

        Just id ->
            List.map (Node.pushDeep id (getId item) item) tree


{-| Build `Tree` from given list of items.
First argument is function from item to `Id/String`.
Second argument is function from item to `List Id/List String`.

    items =
        [ { id = 1, name = "first", parentIds = [] }
        , { id = 2, name = "child", parentIds = [1] }
        , { id = 3, name = "deep child", parentIds = [2] }
        ]

     itemId item =
         toId (.id item )

     itemParentIds item =
         .parentIds item |> List.map toId

     fromList itemId itemParentIds items == [Node "1" { id = 1, name = "first", parentIds = [] } ([Node "2" { id = 2, name = "child", parentIds = [1] } ([Node "3" { id = 3, name = "deep child", parentIds = [2] } []])])]

-}
fromList :
    (a -> Id)
    -> (a -> List Id)
    -> List a
    -> Tree a
fromList getId getParentId list =
    fromList_ getId getParentId list Nothing


fromList_ :
    (a -> Id)
    -> (a -> List Id)
    -> List a
    -> Maybe Id
    -> Tree a
fromList_ getId getParentId list maybeId =
    let
        children =
            case maybeId of
                Nothing ->
                    List.filter (List.isEmpty << getParentId) list

                Just id ->
                    List.filter (List.member id << getParentId) list
    in
        List.map (\i -> Node.node (getId i) i (fromList_ getId getParentId list (Just (getId i)))) children


{-| Returns sub `Tree` and ancestors for given `Id` and `Tree`.
First argument is `Maybe Id` is ether:

  - `Nothing` => result is given tree (with empty ancestors `List`).
  - `Just parentId` => result is sub tree for node with `id == parentId`.

Returns tuple containing sub tree and list of ancestors of that sub tree (from parent to root).

    items =
        [ { id = 1, name = "first", parentIds = [] }
        , { id = 2, name = "child", parentIds = [1] }
        , { id = 3, name = "dep categories", parentIds = [2] }
        ]

     itemId item =
         toId (.id item )

     itemParentIds item =
         .parentIds item |> List.map toId

     tree =
        fromList itemId itemParentIds items

     subTreeFor Nothing tree == (tree, [])
     subTreeFor (Just "1") tree == ([Node "2" { id = 2, name = "child", parentIds = [1] } ([Node "3" { id = 3, name = "dep categories", parentIds = [2] } []])],[{ id = 1, name = "first", parentIds = [] }])
     subTreeFor (Just "2") tree == ([Node "3" { id = 3, name = "dep categories", parentIds = [2] } []],[{ id = 2, name = "child", parentIds = [1] },{ id = 1, name = "first", parentIds = [] }])

-}
subTreeFor :
    Maybe Id
    -> Tree a
    -> ( Tree a, List a )
subTreeFor maybeId tree =
    case maybeId of
        Just id ->
            subTreeFor_ id ( tree, [] )

        Nothing ->
            ( tree, [] )


subTreeFor_ :
    Id
    -> ( Tree a, List a )
    -> ( Tree a, List a )
subTreeFor_ id ( tree, ancestors ) =
    let
        matches =
            List.filter ((==) id << Node.id) tree

        nest ( _, item, children ) =
            ( children, item :: ancestors )
    in
        case (List.head matches) of
            Just node ->
                nest <| Node.toTuple node

            Nothing ->
                List.foldr
                    (\child acc ->
                        let
                            subMatches =
                                subTreeFor_ id <| nest <| Node.toTuple child
                        in
                            if List.isEmpty <| Tuple.second subMatches then
                                acc
                            else
                                subMatches
                    )
                    ( [], [] )
                    tree