Radix.elm

module Radix exposing (..)

import List.Extra
import Tree
import Tree.Zipper as TreeZipper


empty : Tree.Tree (List a)
empty =
    Tree.singleton []


singleton : List a -> Tree.Tree (List a)
singleton element =
    Tree.singleton element


insert : List a -> Tree.Tree (List a) -> Tree.Tree (List a)
insert xs tree =
    insertHelper ( orderedIntersect, orderedRemove ) xs (TreeZipper.fromTree tree)
        |> TreeZipper.toTree


insertHelper : ( List a -> List a -> List a, List a -> List a -> List a ) -> List a -> TreeZipper.Zipper (List a) -> TreeZipper.Zipper (List a)
insertHelper funcs xs treeZipper =
    case TreeZipper.label treeZipper of
        [] ->
            -- We're at the root, which is empty, so we need to check the child.
            case treeZipper |> TreeZipper.forward of
                Nothing ->
                    -- No children, so add value here.
                    treeZipper
                        |> TreeZipper.mapTree (Tree.prependChild (Tree.singleton xs))

                Just nextTreeZipper ->
                    nextTreeZipper
                        |> insertHelper funcs xs

        ys ->
            let
                splitInfo =
                    split funcs xs ys
            in
            if List.isEmpty splitInfo.intersect then
                -- There's no match, try the next sibling, if exists.
                case treeZipper |> TreeZipper.nextSibling of
                    Just nextTreeZipper ->
                        nextTreeZipper
                            -- Recurse.
                            |> insertHelper funcs xs

                    Nothing ->
                        -- We've reached the last sibling, so we can add a new sibling.
                        treeZipper
                            |> TreeZipper.parent
                            |> Maybe.map (TreeZipper.mapTree (Tree.prependChild (Tree.singleton xs)))
                            |> Maybe.withDefault treeZipper

            else if splitInfo.intersect == ys then
                -- Add the remaining of xs under ys.
                if splitInfo.left |> List.isEmpty |> not then
                    if treeZipper |> TreeZipper.children |> List.isEmpty then
                        -- Tree has no children, so we don't need to move forward.
                        -- We can just save the rest of Left.
                        let
                            newTree =
                                treeZipper
                                    |> TreeZipper.tree
                                    |> Tree.prependChild (Tree.singleton splitInfo.left)
                        in
                        treeZipper
                            |> TreeZipper.replaceTree newTree

                    else
                        treeZipper
                            -- Try to advance
                            |> TreeZipper.forward
                            -- Recurse.
                            |> Maybe.map (insertHelper funcs splitInfo.left)
                            |> Maybe.withDefault treeZipper

                else
                    -- Nothing remains to be added.
                    treeZipper

            else
                -- We have a partial match with the existing tree. We need to add a new
                -- parent tree.
                let
                    rightTreeUpdated =
                        treeZipper
                            -- Keep only the diff elements of the Right element.
                            |> TreeZipper.replaceLabel splitInfo.right
                            -- Get the new tree from the focus point.
                            |> TreeZipper.tree

                    newTree =
                        Tree.singleton splitInfo.intersect
                            |> Tree.prependChild rightTreeUpdated
                            |> Tree.prependChild (Tree.singleton splitInfo.left)
                in
                treeZipper
                    |> TreeZipper.replaceTree newTree


split : ( List a -> List a -> List a, List a -> List a -> List a ) -> List a -> List a -> { intersect : List a, left : List a, right : List a }
split ( intersectFunc, removeFunc ) xs ys =
    let
        intersect =
            intersectFunc xs ys

        left =
            removeFunc xs intersect

        right =
            List.foldl (\x accum -> List.Extra.remove x accum) ys intersect
    in
    { intersect = intersect
    , left = left
    , right = right
    }


{-| Find the matching elements, regardless of their order in the list.
-}
unOrderedIntersect : List a -> List a -> List a
unOrderedIntersect xs ys =
    List.foldr
        (\x accum ->
            if List.member x ys then
                x :: accum

            else
                accum
        )
        []
        xs


unOrderedRemove : List a -> List a -> List a
unOrderedRemove xs intersect =
    List.foldl (\x accum -> List.Extra.remove x accum) xs intersect


{-| We start with entire list, and trim it down to find the intersecting elements.
-}
orderedIntersect : List a -> List a -> List a
orderedIntersect xs ys =
    if List.Extra.isPrefixOf xs ys then
        xs

    else if List.length xs == 1 then
        -- No match
        []

    else
        let
            xsUpdated =
                List.take (List.length xs - 1) xs
        in
        orderedIntersect xsUpdated ys


orderedRemove : List a -> List a -> List a
orderedRemove xs intersect =
    List.drop (List.length intersect) xs