Stack.elm

module PedroHLC.Stack
    exposing
        ( Stack
        , empty
        , isEmpty
        , reverse
        , singleton
        , length
        , push
        , pop
        , head
        , last
        , get
        , reverse
        , map
        , filter
        , filterMap
        , foldl
        , foldr
        , toCoreList
        )


type Stack a
    = Empty
    | Node a (Stack a)
    | KeyNode a (Stack a) Int


isEmpty : Stack a -> Bool
isEmpty src =
    case src of
        Empty ->
            True

        _ ->
            False


push : a -> Stack a -> Stack a
push elem dest =
    case dest of
        Empty ->
            KeyNode elem dest 0

        Node _ Empty ->
            KeyNode elem dest 1

        KeyNode _ Empty _ ->
            KeyNode elem dest 1

        Node _ _ ->
            KeyNode elem dest (count dest)

        KeyNode head tail counter ->
            KeyNode elem (Node head tail) (counter + 1)


get : Int -> Stack a -> Maybe a
get x src =
    case ( x, src ) of
        ( 0, Node head Empty ) ->
            Just head

        ( 0, KeyNode head Empty _ ) ->
            Just head

        ( _, Empty ) ->
            Nothing

        ( _, KeyNode head tail counter ) ->
            dive (counter - x) (Node head tail)

        ( _, Node head tail ) ->
            count src
                |> KeyNode head tail
                |> get x


dive : Int -> Stack a -> Maybe a
dive qty src =
    case ( qty, src ) of
        ( 0, Node head _ ) ->
            Just head

        ( 0, KeyNode head _ _ ) ->
            Just head

        ( _, Empty ) ->
            Nothing

        ( _, Node _ Empty ) ->
            Nothing

        ( _, KeyNode _ Empty _ ) ->
            Nothing

        ( _, Node head tail ) ->
            dive (qty - 1) tail

        ( _, KeyNode head tail counter ) ->
            dive (qty - 1) tail


count : Stack a -> Int
count src =
    case src of
        Empty ->
            0

        Node _ Empty ->
            0

        KeyNode _ Empty _ ->
            0

        Node _ child ->
            (count child) + 1

        KeyNode _ _ counter ->
            counter


length : Stack a -> Int
length src =
    case src of
        Empty ->
            0

        _ ->
            (count src) + 1


head : Stack a -> Maybe a
head src =
    case src of
        Empty ->
            Nothing

        Node head Empty ->
            Just head

        KeyNode head Empty _ ->
            Just head

        Node _ tail ->
            head tail

        KeyNode _ tail _ ->
            head tail


last : Stack a -> Maybe a
last src =
    case src of
        Empty ->
            Nothing

        Node head _ ->
            Just head

        KeyNode head _ _ ->
            Just head


pop : Stack a -> ( Maybe a, Stack a )
pop src =
    case src of
        Empty ->
            ( Nothing, Empty )

        Node head tail ->
            ( Just head, tail )

        KeyNode head tail counter ->
            case tail of
                Node head2 tail2 ->
                    ( Just head
                    , KeyNode head2 tail2 (counter - 1)
                    )

                _ ->
                    ( Just head, tail )


reverse : Stack a -> Stack a
reverse src =
    case src of
        Empty ->
            src

        Node _ _ ->
            reverseReduce src empty

        KeyNode _ _ _ ->
            reverseReduce src empty


reverseReduce : Stack a -> Stack a -> Stack a
reverseReduce src acu =
    case src of
        Empty ->
            acu

        Node head tail ->
            acu
                |> push head
                |> reverseReduce tail

        KeyNode head tail _ ->
            acu
                |> push head
                |> reverseReduce tail


empty : Stack a
empty =
    Empty


singleton : a -> Stack a
singleton src =
    KeyNode src Empty 0


map : (a -> b) -> Stack a -> Stack b
map mapper src =
    case src of
        Empty ->
            Empty

        Node head tail ->
            Node
                (mapper head)
                (map mapper tail)

        KeyNode head tail counter ->
            KeyNode
                (mapper head)
                (map mapper tail)
                counter


filter : (a -> Bool) -> Stack a -> Stack a
filter test src =
    case src of
        Empty ->
            Empty

        Node head tail ->
            let
                tail2 =
                    filter test tail
            in
                if (test head) then
                    Node head tail2
                else
                    tail2

        KeyNode head tail counter ->
            Tuple.first <| filterCounting test src


filterCounting : (a -> Bool) -> Stack a -> ( Stack a, Int )
filterCounting test src =
    case src of
        Empty ->
            ( Empty, 0 )

        Node head tail ->
            let
                src2 =
                    filterCounting test tail

                ( tail2, counter ) =
                    src2
            in
                if (test head) then
                    ( Node head tail2
                    , counter + 1
                    )
                else
                    src2

        KeyNode head tail counter ->
            let
                src2 =
                    filterCounting test tail

                ( tail2, counter ) =
                    src2
            in
                if (test head) then
                    ( KeyNode head tail2 counter
                    , counter + 1
                    )
                else
                    case tail2 of
                        Node head tail3 ->
                            ( KeyNode head tail3 (counter - 1)
                            , counter
                            )

                        _ ->
                            src2


filterMap : (a -> Maybe b) -> Stack a -> Stack b
filterMap mapper src =
    case src of
        Empty ->
            Empty

        Node head tail ->
            let
                tail2 =
                    filterMap mapper tail
            in
                case (mapper head) of
                    Just head ->
                        Node head tail2

                    Nothing ->
                        tail2

        KeyNode head tail counter ->
            Tuple.first <| filterMapCounting mapper src


filterMapCounting : (a -> Maybe b) -> Stack a -> ( Stack b, Int )
filterMapCounting mapper src =
    case src of
        Empty ->
            ( Empty, 0 )

        Node head tail ->
            let
                src2 =
                    filterMapCounting mapper tail

                ( tail2, counter ) =
                    src2
            in
                case (mapper head) of
                    Just head ->
                        ( Node head tail2
                        , counter + 1
                        )

                    Nothing ->
                        src2

        KeyNode head tail counter ->
            let
                src2 =
                    filterMapCounting mapper tail

                ( tail2, counter ) =
                    src2
            in
                case (mapper head) of
                    Just head ->
                        ( KeyNode head tail2 counter
                        , counter + 1
                        )

                    Nothing ->
                        case tail2 of
                            Node head tail3 ->
                                ( KeyNode head tail3 (counter - 1)
                                , counter
                                )

                            _ ->
                                src2


foldr : (a -> b -> b) -> Stack a -> b
foldr reducer src =
    todo


foldl : (a -> b -> b) -> Stack a -> b
foldl reducer src =
    todo


toCoreList : Stack a -> List a
toCoreList src =
    case src of
        Empty ->
            []

        Node _ _ ->
            toCoreListReduce src []

        KeyNode _ _ _ ->
            toCoreListReduce src []


toCoreListReduce : Stack a -> List a -> List a
toCoreListReduce src acu =
    case src of
        Empty ->
            acu

        Node head tail ->
            acu
                |> (::) head
                |> toCoreListReduce tail

        KeyNode head tail _ ->
            acu
                |> (::) head
                |> toCoreListReduce tail