A dictionary with a maximum size. Items are removed from the dictionary on a FIFO basis when the dictionary reaches its maximum size.
A dictionary with a maximum size.
Create an empty dictionary.
Create a singleton dictionary.
Insert a key-value pair into a dictionary. Replaces value when there is a collision.
Remove a key-value pair from a dictionary. If the key is not found, no changes are made.
Determine if a dictionary is empty.
Determine if a key is in a dictionary.
Get the value associated with a key. If the key is not found, return
Nothing
.
Determine the number of key-value pairs in a dictionary.
Determine the maximum number of key-value pairs in a dictionary.
module MaxSizeDict
exposing
( MaxSizeDict
, empty
, get
, insert
, isEmpty
, maxSize
, member
, remove
, singleton
, size
)
{-| A dictionary with a maximum size. Items are removed from the dictionary on a
FIFO basis when the dictionary reaches its maximum size.
# Dictionaries
@docs MaxSizeDict
# Build
@docs empty, singleton, insert, remove
# Query
@docs isEmpty, member, get, size, maxSize
-}
import Dict exposing (Dict)
import Fifo exposing (Fifo)
{-| A dictionary with a maximum size.
-}
type MaxSizeDict k v
= MaxSizeDict
{ dict : Dict k v
, maxSize : Int
, keys : Fifo k
}
-- Build
{-| Create an empty dictionary.
-}
empty : Int -> MaxSizeDict k v
empty maxSize =
MaxSizeDict
{ dict = Dict.empty
, maxSize = maxSize
, keys = Fifo.empty
}
{-| Create a singleton dictionary.
-}
singleton : Int -> comparable -> v -> MaxSizeDict comparable v
singleton maxSize key value =
MaxSizeDict
{ dict = Dict.singleton key value
, maxSize = maxSize
, keys = Fifo.insert key Fifo.empty
}
{-| Insert a key-value pair into a dictionary. Replaces value when there is
a collision.
-}
insert :
comparable
-> v
-> MaxSizeDict comparable v
-> MaxSizeDict comparable v
insert key value ((MaxSizeDict dict) as maxSizeDict) =
if member key maxSizeDict then
let
keys =
removeKey key dict.keys |> Fifo.insert key
in
MaxSizeDict
{ dict
| dict = Dict.insert key value dict.dict
, keys = keys
}
else if size maxSizeDict == maxSize maxSizeDict then
case Fifo.remove dict.keys of
-- should NOT happen
( Nothing, _ ) ->
maxSizeDict
( Just oldest, keys ) ->
MaxSizeDict
{ dict
| dict =
Dict.remove oldest dict.dict
|> Dict.insert key value
, keys = Fifo.insert key keys
}
else
MaxSizeDict
{ dict
| dict = Dict.insert key value dict.dict
, keys = Fifo.insert key dict.keys
}
{-| Remove a key-value pair from a dictionary. If the key is not found,
no changes are made.
-}
remove : comparable -> MaxSizeDict comparable v -> MaxSizeDict comparable v
remove key ((MaxSizeDict dict) as maxSizeDict) =
if member key maxSizeDict then
MaxSizeDict
{ dict
| dict = Dict.remove key dict.dict
, keys = removeKey key dict.keys
}
else
maxSizeDict
-- Query
{-| Determine if a dictionary is empty.
-}
isEmpty : MaxSizeDict k v -> Bool
isEmpty (MaxSizeDict dict) =
Dict.isEmpty dict.dict
{-| Determine the maximum number of key-value pairs in a dictionary.
-}
maxSize : MaxSizeDict k v -> Int
maxSize (MaxSizeDict dict) =
dict.maxSize
{-| Determine the number of key-value pairs in a dictionary.
-}
size : MaxSizeDict k v -> Int
size (MaxSizeDict dict) =
Dict.size dict.dict
{-| Determine if a key is in a dictionary.
-}
member : comparable -> MaxSizeDict comparable v -> Bool
member key (MaxSizeDict dict) =
Dict.member key dict.dict
{-| Get the value associated with a key. If the key is not found, return
`Nothing`.
-}
get : comparable -> MaxSizeDict comparable v -> Maybe v
get key (MaxSizeDict dict) =
Dict.get key dict.dict
-- Internal functions
removeKey : comparable -> Fifo comparable -> Fifo comparable
removeKey key keys =
Fifo.toList keys |> List.filter (\k -> k /= key) |> Fifo.fromList