This module exposes the same API as Dict.
Since JavaScript's number type is kind of messed up, Elm's Int is not particularly
well-behaved wrt. bitwise operations. Currently, JS supports 32 bit integers, so there is
probably enough room for key picks. However, when sanitizing user input, it is mandatory
that a prior isValidKey or one of the safe versions in IntDict.Safe is used! This is
to prevent the overflow behavior.
This library is inspired by Haskells IntMap, which in turn implements Okasaki and Gill's Fast mergable integer maps.
As noted in the references, here are some runtimes:
O(min(n, W)): insert, update, remove, get, member
O(n + m): uniteWith, union, intersection, diff, merge
where n and m are the sizes of the first and second dictionary respectively and W
is the number of bits in Int (so a constant with current value 32).
Validates that a given integer is usable as a key.
This is necessary due to JavaScript's weird number type.
Basically this assures that we can use the functions
from Bitwise without risking integer overflow.
This function is a necessity for sanitizing user input! Alternatively,
use the safe functions from IntDict.Safe which perform the check for you.
As with the current version of JavaScript (2015), only 32 bit signed integers are supported. If this ever changes, contact me! Certain parts of the implementation depend on this!
Create an empty dictionary.
Create a dictionary with one key-value pair.
Insert a key-value pair into a dictionary. Replaces value when there is a collision.
Update the value of a dictionary for a specific key with a given function.
Remove a key-value pair from a dictionary. If the key is not found, no changes are made.
Check if the dictionary contains no items.
The number of items in the dictionary. O(1).
Determine if a key is in a dictionary.
Get the value associated with a key. If the key is not found, return
Nothing. This is useful when you are not sure if a key will be in the
dictionary.
Find the minimum key and value in the dictionary.
Find the maximum key and value in the dictionary.
uniteWith merger l r combines two dictionaries. If there is a collision, merger
is called with the conflicting key, the value from l and that from r.
Combine two dictionaries. If there is a collision, preference is given to the first dictionary.
Keep a key-value pair when its key appears in the second dictionary. Preference is given to values in the first dictionary.
Keep a key-value pair when its key does not appear in the second dictionary. Preference is given to the first dictionary.
The most general way of combining two dictionaries. You provide three accumulators for when a given key appears:
Note that uniteWith, union, intersect and diff could all be implemented
in terms of this function. The only reason that's not the case is to have more
sharing of substructure.
uniteWith merger l r = merge insert merger insert l r empty union l r = merge insert (\k a _ d -> insert k a d) insert l r empty intersect l r = merge (_ _ d -> d) (\k a _ d -> insert k a d) (_ _ d -> d) l r empty diff l r = merge insert (_ _ _ d -> d) (_ _ d -> d) l r empty
Get all of the keys in a dictionary.
Get all of the values in a dictionary.
Convert a dictionary into an association list of key-value pairs.
Convert an association list into a dictionary.
Apply a function to all values in a dictionary.
Fold over the key-value pairs in a dictionary, in order from lowest key to highest key.
Fold over the key-value pairs in a dictionary, in order from highest key to lowest key.
Keep a key-value pair when it satisfies a predicate.
Partition a dictionary according to a predicate. The first dictionary contains all key-value pairs which satisfy the predicate, and the second contains the rest.
Generates a string representation similar to what toString
generates for Dict.
A dictionary mapping
Ints to values of a typev. Analogous toDict Int v.