-- Establishing a bijection between the values of the type a and integers, with
-- the operations to retrieve the value given its key,
-- to find the key for the existing value, and to extend the
-- bijection with a new association.
-- The type 'a' of values should at least permit equality comparison;
-- In the present implementation, we require 'a' to be a member
-- of Ord.
-- There are many ways to implement bi-maps, for example, using hash tables,
-- or maps.
-- Our implementation uses Data.Map and Data.IntMap to record
-- both parts of the association.
module BiMap (
BiMap, empty,
lookup_key,
lookup_val,
insert,
size,
)
where
import qualified Data.Map as M
import qualified Data.IntMap as IM
data BiMap a = BiMap (M.Map a Int) (IM.IntMap a)
-- Find a key for a value
lookup_key :: Ord a => a -> BiMap a -> Maybe Int
lookup_key v (BiMap m _) = M.lookup v m
-- Find a value for a key
lookup_val :: Int -> BiMap a -> a
lookup_val k (BiMap _ m) = m IM.! k
-- Insert the value and return the corresponding key
-- and the new map
-- Alas, Map interface does not have an operation to insert and find the index
-- at the same time (although such an operation is easily possible)
insert :: Ord a => a -> BiMap a -> (Int, BiMap a)
insert v (BiMap m im) = (k, BiMap m' im')
where m' = M.insert v k m
im' = IM.insert k v im
k = IM.size im
empty :: BiMap a
empty = BiMap (M.empty) (IM.empty)
instance Show a => Show (BiMap a) where
show (BiMap _ m) = "BiMap" ++ show (IM.toList m)
size :: BiMap a -> Int
size (BiMap _ m) = IM.size m