This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.
README OrderedSet

OrderedDict

A dictionary type that when iterated or converted to a list, the order of entries will be the same as the order they were inserted.

As it uses Dict under the hood, the keys can only be comparable types, which include Int, Float, Time, Char, String, and tuples or lists of comparable types.

Dictionaries

type OrderedDict comparable v = OrderedDict (List comparable) (Dict comparable v)

A type of Dict that is iterated by the order of insertion.

Build

empty : OrderedDict comparable v

Create an empty dictionary.

singleton : comparable -> v -> OrderedDict comparable v

Create a dictionary with one key-value pair.

insert : comparable -> v -> OrderedDict comparable v -> OrderedDict comparable v

Insert a key-value pair into a dictionary. Replace the value if the key already exists.

update : comparable -> (Maybe v -> Maybe v) -> OrderedDict comparable v -> OrderedDict comparable v

Update the value of a specific key with an updater function.

Since the key may not exist before or after the update, the updater function takes a Maybe v and returns a Maybe v.

remove : comparable -> OrderedDict comparable v -> OrderedDict comparable v

Remove a key-value pair from a dictionary. If the key doesn't exist, no changes are made.

Query

isEmpty : OrderedDict comparable v -> Bool

Check if a dictionary is empty.

member : comparable -> OrderedDict comparable v -> Bool

Check if a key is in a dictionary.

get : comparable -> OrderedDict comparable v -> Maybe v

Get the value associated with a key. Return Nothing if the key is not found.

size : OrderedDict comparable v -> Int

Get the number of key-value pairs in the dictionary.

Lists

keys : OrderedDict comparable v -> List comparable

Get all of the keys in a dictionary, in insertion order.

values : OrderedDict comparable v -> List v

Get all of the values in a dictionary, in insertion order.

toList : OrderedDict comparable v -> List ( comparable, v )

Convert a dictionary into an association list of key-value pairs, in insertion order.

fromList : List ( comparable, v ) -> OrderedDict comparable v

Convert an association list into a dictionary.

Transform

map : (comparable -> a -> b) -> OrderedDict comparable a -> OrderedDict comparable b

Apply a function to all values in a dictionary.

foldl : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b

Fold the key-value pairs in a dictionary, in insertion order.

foldr : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b

Fold the key-value pairs in a dictionary, in reverse insertion order.

filter : (comparable -> v -> Bool) -> OrderedDict comparable v -> OrderedDict comparable v

Return a new OrderedDict that only contains entries that satisfy a predicate.

partition : (comparable -> v -> Bool) -> OrderedDict comparable v -> ( OrderedDict comparable v, OrderedDict comparable v )

Split a OrderedDict to a tuple of OrderedDict. The first contains all entries that satisfy the predicate, and the second contains the rest.

Combine

union : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v

Combine two dictionaries. If there is a collision, preference is given to the first dictionary.

union (singleton "x" 1) (singleton "x" 2) == singleton "x" 1
intersect : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v

Keep a key-value pair when its key appears in the second dictionary. Preference is given to values in the first dictionary.

diff : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v

Keep a key-value pair when its key does not appear in the second dictionary.

module OrderedDict
    exposing
        ( OrderedDict
        , empty
        , singleton
        , insert
        , remove
        , update
        , isEmpty
        , get
        , member
        , size
        , filter
        , partition
        , foldl
        , foldr
        , map
        , keys
        , values
        , toList
        , fromList
        , union
        , intersect
        , diff
        )

{-| A dictionary type that when iterated or converted to a list, the order of
entries will be the same as the order they were inserted.

As it uses `Dict` under the hood, the keys can only be comparable types, which
include `Int`, `Float`, `Time`, `Char`, `String`, and tuples or lists of
comparable types.


# Dictionaries

@docs OrderedDict


# Build

@docs empty, singleton, insert, update, remove


# Query

@docs isEmpty, member, get, size


# Lists

@docs keys, values, toList, fromList


# Transform

@docs map, foldl, foldr, filter, partition


# Combine

@docs union, intersect, diff

-}

import Dict exposing (Dict)
import List


{-| A type of `Dict` that is iterated by the order of insertion.
-}
type OrderedDict comparable v
    = OrderedDict (List comparable) (Dict comparable v)


{-| Create an empty dictionary.
-}
empty : OrderedDict comparable v
empty =
    OrderedDict [] Dict.empty


{-| Check if a dictionary is empty.
-}
isEmpty : OrderedDict comparable v -> Bool
isEmpty odict =
    odict == empty


{-| Get the value associated with a key. Return `Nothing` if the key is not found.
-}
get : comparable -> OrderedDict comparable v -> Maybe v
get key (OrderedDict _ dict) =
    Dict.get key dict


{-| Check if a key is in a dictionary.
-}
member : comparable -> OrderedDict comparable v -> Bool
member key (OrderedDict _ dict) =
    Dict.member key dict


{-| Get the number of key-value pairs in the dictionary.
-}
size : OrderedDict comparable v -> Int
size (OrderedDict list _) =
    List.length list


{-| Create a dictionary with one key-value pair.
-}
singleton : comparable -> v -> OrderedDict comparable v
singleton key value =
    insert key value empty


{-| Insert a key-value pair into a dictionary. Replace the value if the key
already exists.
-}
insert : comparable -> v -> OrderedDict comparable v -> OrderedDict comparable v
insert key value odict =
    update key (always (Just value)) odict


{-| Remove a key-value pair from a dictionary. If the key doesn't exist,
no changes are made.
-}
remove : comparable -> OrderedDict comparable v -> OrderedDict comparable v
remove key odict =
    update key (always Nothing) odict


{-| Update the value of a specific key with an updater function.

Since the key may not exist before or after the update, the updater function
takes a `Maybe v` and returns a `Maybe v`.

-}
update :
    comparable
    -> (Maybe v -> Maybe v)
    -> OrderedDict comparable v
    -> OrderedDict comparable v
update key updater (OrderedDict list dict) =
    let
        newDict =
            Dict.update key updater dict

        newList =
            case updater (Dict.get key dict) of
                Just _ ->
                    if List.member key list then
                        list
                    else
                        list ++ [ key ]

                Nothing ->
                    if List.member key list then
                        List.filter (\k -> k /= key) list
                    else
                        list
    in
        OrderedDict newList newDict



-- TRANSFORM


{-| Apply a function to all values in a dictionary.
-}
map : (comparable -> a -> b) -> OrderedDict comparable a -> OrderedDict comparable b
map f (OrderedDict list dict) =
    OrderedDict list (Dict.map f dict)


reducer :
    Dict comparable v
    -> (comparable -> v -> b -> b)
    -> (comparable -> b -> b)
reducer dict f =
    \key acc ->
        case Dict.get key dict of
            Just value ->
                f key value acc

            Nothing ->
                acc


{-| Fold the key-value pairs in a dictionary, in insertion order.
-}
foldl : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b
foldl f acc (OrderedDict list dict) =
    List.foldl (reducer dict f) acc list


{-| Fold the key-value pairs in a dictionary, in reverse insertion order.
-}
foldr : (comparable -> v -> b -> b) -> b -> OrderedDict comparable v -> b
foldr f acc (OrderedDict list dict) =
    List.foldr (reducer dict f) acc list


{-| Return a new `OrderedDict` that only contains entries that satisfy a predicate.
-}
filter :
    (comparable -> v -> Bool)
    -> OrderedDict comparable v
    -> OrderedDict comparable v
filter predicate dictionary =
    let
        add key value odict =
            if predicate key value then
                insert key value odict
            else
                odict
    in
        foldl add empty dictionary


{-| Split a `OrderedDict` to a tuple of `OrderedDict`. The first contains all
entries that satisfy the predicate, and the second contains the rest.
-}
partition :
    (comparable -> v -> Bool)
    -> OrderedDict comparable v
    -> ( OrderedDict comparable v, OrderedDict comparable v )
partition predicate dictionary =
    let
        add key value ( odict1, odict2 ) =
            if predicate key value then
                ( insert key value odict1, odict2 )
            else
                ( odict1, insert key value odict2 )
    in
        foldl add ( empty, empty ) dictionary



-- LISTS


{-| Get all of the keys in a dictionary, in insertion order.
-}
keys : OrderedDict comparable v -> List comparable
keys (OrderedDict list _) =
    list


{-| Get all of the values in a dictionary, in insertion order.
-}
values : OrderedDict comparable v -> List v
values (OrderedDict list dict) =
    List.filterMap (\key -> Dict.get key dict) list


{-| Convert a dictionary into an association list of key-value pairs, in insertion order.
-}
toList : OrderedDict comparable v -> List ( comparable, v )
toList (OrderedDict list dict) =
    List.map2 (,) list (values <| OrderedDict list dict)


{-| Convert an association list into a dictionary.
-}
fromList : List ( comparable, v ) -> OrderedDict comparable v
fromList assocs =
    let
        ( list, _ ) =
            List.unzip assocs

        dict =
            Dict.fromList assocs
    in
        OrderedDict list dict



-- COMBINE


{-| Combine two dictionaries. If there is a collision, preference is given
to the first dictionary.

    union (singleton "x" 1) (singleton "x" 2) == singleton "x" 1

-}
union : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v
union odict1 odict2 =
    let
        reducer =
            \k v acc ->
                if member k odict1 then
                    acc
                else
                    insert k v acc
    in
        foldl reducer odict1 odict2


{-| Keep a key-value pair when its key appears in the second dictionary.
Preference is given to values in the first dictionary.
-}
intersect :
    OrderedDict comparable v
    -> OrderedDict comparable v
    -> OrderedDict comparable v
intersect odict1 odict2 =
    filter (\k _ -> member k odict2) odict1


{-| Keep a key-value pair when its key does not appear in the second dictionary.
-}
diff : OrderedDict comparable v -> OrderedDict comparable v -> OrderedDict comparable v
diff odict1 odict2 =
    foldl (\k v t -> remove k t) odict1 odict2