This module allows creating map data structures which preserve order of inserts
Type alias for storing an ordered map
Create a new ordered map.
om = new
Upsert a key pair to the ordered map.
upsert 42 "the answer" om
Pull inserted data out of an ordered map. Returns nothing fo either a nonexistant, or a reserved value.
get 42 om == "the answer"
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"]
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
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
) []