Makes elm-make sad :(

indexed-min-heap-error.elm

module IndexedMinHeap exposing (empty, insert, deleteMin)

import Array
import Dict exposing (Dict)
import Maybe
import Tuple


type alias IndexedMinHeap comparable comparable1 =
    { heap : Array.Array ( comparable, comparable1 )
    , lookup : Dict comparable1 Int
    , lookupShift : Int
    }


empty : IndexedMinHeap comparable comparable1
empty =
    { heap = Array.empty
    , lookup = Dict.empty
    , lookupShift = 0
    }


bubbleUp_ : Int -> IndexedMinHeap comparable comparable1 -> IndexedMinHeap comparable comparable1
bubbleUp_ i h =
    if i == 0 then
        h
    else
        let
            p =
                (parentIdx_ i)
        in
            case Maybe.map2 (<) (Maybe.map Tuple.first (Array.get i h.heap)) (Maybe.map Tuple.first (Array.get p h.heap)) of
                Nothing ->
                    h

                Just False ->
                    h

                Just True ->
                    bubbleUp_ p (swap_ i p h)


bubbleDown_ : Int -> IndexedMinHeap comparable comparable1 -> IndexedMinHeap comparable comparable1
bubbleDown_ i h =
    if i > (Array.length h.heap) - 1 then
        h
    else
        let
            li =
                leftIdx_ i

            ri =
                rightIdx_ i

            ix =
                Maybe.map Tuple.first (Array.get i h.heap)

            lx =
                Maybe.map Tuple.first (Array.get li h.heap)

            rx =
                Maybe.map Tuple.first (Array.get ri h.heap)
        in
            case ( Maybe.map2 (<) ix lx, Maybe.map2 (<) ix rx, Maybe.map2 (<) lx rx ) of
                ( Just True, Just True, Just True ) ->
                    bubbleDown_ li (swap_ i li h)

                ( _, Just True, _ ) ->
                    bubbleDown_ li (swap_ i ri h)

                ( Just True, _, _ ) ->
                    bubbleDown_ li (swap_ i li h)

                _ ->
                    h


parentIdx_ : Int -> Int
parentIdx_ x =
    (x - 1) // 2


leftIdx_ : Int -> Int
leftIdx_ x =
    x * 2 + 1


rightIdx_ : Int -> Int
rightIdx_ x =
    x * 2 + 2


swap_ : Int -> Int -> IndexedMinHeap comparable comparable1 -> IndexedMinHeap comparable comparable1
swap_ i j h =
    let
        ikv =
            Array.get i h.heap

        jkv =
            Array.get j h.heap

        newHeap =
            Maybe.map2 (\ix jx -> h.heap |> Array.set i jx |> Array.set j ix) ikv jkv

        newLookup =
            Maybe.map2
                (\ix jx ->
                    h.lookup
                        |> Dict.update (Tuple.second ix) (Maybe.map (always i))
                        |> Dict.update (Tuple.second jx) (Maybe.map (always j))
                )
                ikv
                jkv
    in
        Maybe.map2
            (\newHeap newLookup ->
                { heap = newHeap
                , lookup = newLookup
                , lookupShift = h.lookupShift
                }
            )
            newHeap
            newLookup
            |> Maybe.withDefault h


insert : ( comparable, comparable1 ) -> IndexedMinHeap comparable comparable1 -> IndexedMinHeap comparable comparable1
insert x h =
    let
        onlyX =
            Array.initialize 1 (always x)

        l =
            Array.length h.heap
    in
        case l of
            0 ->
                { heap = onlyX
                , lookup = Dict.fromList [ ( Tuple.second x, 0 ) ]
                , lookupShift = 0
                }

            _ ->
                { h
                    | heap = Array.append h.heap onlyX
                    , lookupShift = h.lookupShift + 1
                }
                    |> swap_ 0 l
                    |> bubbleUp_ l


deleteMin : IndexedMinHeap comparable comparable1 -> ( Maybe comparable, IndexedMinHeap comparable comparable1 )
deleteMin h =
    let
        l =
            Array.length h.heap
    in
        case l of
            0 ->
                ( Nothing, h )

            _ ->
                let
                    v =
                        Array.get 0 h.heap

                    swapped =
                        h
                            |> swap_ 0 (l - 1)

                    rem =
                        { swapped
                            | heap = Array.slice 0 (l - 1) swapped.heap
                            , lookupShift = swapped.lookupShift - 1
                        }
                            |> bubbleDown_ 0
                in
                    ( v, rem )