module OrderedMap exposing (OrderedMap, new, upsert, get, toList, reserve)

{-|
This module allows creating map data structures which preserve order of inserts

# Definition
@docs OrderedMap, new

# Usage
@docs upsert, get, toList

# Reserving Locations
@docs reserve

-}

import Dict exposing (Dict)
import Maybe

{-| Type alias for storing an ordered map
-}
type alias OrderedMap comparable b = {
    list: List comparable,
    map: Dict comparable (Maybe b)
}

{-| Create a new ordered map.

    om = new
-}
new : OrderedMap comparable b
new = OrderedMap [] Dict.empty 

set : comparable -> Maybe b -> OrderedMap comparable b -> OrderedMap comparable b
set key value orderedMap =
    if Dict.member key orderedMap.map then
        let
            newMap = Dict.update key (always <| Just value) orderedMap.map
        in
            OrderedMap orderedMap.list newMap
    else
        let
            newMap = Dict.insert key value orderedMap.map
            newList = key :: orderedMap.list
        in
            OrderedMap newList newMap

{-| Upsert a key pair to the ordered map.

    upsert 42 "the answer" om
-}
upsert : comparable -> b -> OrderedMap comparable b -> OrderedMap comparable b
upsert key value = set key <| Just value

{-| Reserve a key for a value, but insert nothing there. This is used when the order of keys is known already, but their data
may be inserted in an arbitrary order.

    reserve 1337 om
-}
reserve : comparable -> OrderedMap comparable b -> OrderedMap comparable b
reserve key = set key Nothing


{-| Pull inserted data out of an ordered map. Returns nothing fo either a nonexistant, or a reserved value.

    get 42 om == "the answer"
-}
get : comparable -> OrderedMap comparable b -> Maybe b
get key orderedMap =
    Dict.get key orderedMap.map
        |> Maybe.andThen identity

{-| Convert an orderd map to a list, with items in the order that they were inserted.

    new
        |> upsert 2 "hello"
        |> upsert 1 "world"
        |> toList
        
    == ["hello", "world"]
-}
toList : OrderedMap comparable b -> List b
toList orderedMap =
    List.map (\key -> Dict.get key orderedMap.map) orderedMap.list
        |> List.foldl (\ item list ->
            case (item |> Maybe.andThen identity) of
                Nothing ->
                    list
                Just value ->
                    value :: list
            ) []