-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Bidirectional mapping between two key types -- -- A data structure representing a bidirectional mapping between two key -- types. Each value in the bimap is associated with exactly one value of -- the opposite type. @package bimap @version 0.2.2 -- | An implementation of bidirectional maps between values of two key -- types. A Bimap is essentially a bijection between subsets of -- its two argument types. -- -- Each element of the left-hand type is associated with an element of -- the right-hand type, and vice-versa, such that the two mappings are -- inverses. Deleting an element will cause its twin to be deleted, and -- inserting a pair of elements will cause any overlapping bindings to be -- deleted. -- -- Most functions implicitly consider the left-hand type to be the key, -- and the right-hand type to be the value. Functions with an R -- suffix reverse this convention, treating the right-hand type as the -- key and the left-hand type as the value. module Data.Bimap -- | A bidirectional map between values of types a and b. data Bimap a b -- | O(1). Is the bimap empty? Version: 0.2 null :: Bimap a b -> Bool -- | O(1). The number of elements in the bimap. Version: 0.2 size :: Bimap a b -> Int -- | O(log n). Is the specified value a member of the bimap? -- Version: 0.2 member :: (Ord a, Ord b) => a -> Bimap a b -> Bool -- | O(log n). A version of member specialized to the right -- key. Version: 0.2 memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool -- | O(log n). Is the specified value not a member of the bimap? -- Version: 0.2 notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool -- | O(log n). A version of notMember specialized to the -- right key. Version: 0.2 notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool -- | O(log n). Are the two values associated with each other -- in the bimap? -- -- This function is uncurried in its first two arguments, so that it can -- be used infix. -- -- Version: 0.2 pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool -- | O(log n). Are the two values not in the bimap, or not -- associated with each other? (Complement of pairMember.) -- Version: 0.2 pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool -- | O(log n). Lookup a left key in the bimap, returning the -- associated right key. -- -- This function will return the result in the monad, or -- fail if the value isn't in the bimap. -- -- Version: 0.2 lookup :: (Ord a, Ord b, Monad m) => a -> Bimap a b -> m b -- | O(log n). A version of lookup that is specialized to the -- right key, and returns the corresponding left key. Version: 0.2 lookupR :: (Ord a, Ord b, Monad m) => b -> Bimap a b -> m a -- | O(log n). Find the right key corresponding to a given left key. -- Calls error when the key is not in the bimap. -- Version: 0.2 (!) :: (Ord a, Ord b) => Bimap a b -> a -> b -- | O(log n). A version of (!) that is specialized to the -- right key, and returns the corresponding left key. Version: 0.2 (!>) :: (Ord a, Ord b) => Bimap a b -> b -> a -- | O(1). The empty bimap. Version: 0.2 empty :: Bimap a b -- | O(1). A bimap with a single element. Version: 0.2 singleton :: a -> b -> Bimap a b -- | O(log n). Insert a pair of values into the bimap, associating -- them. -- -- If either of the values is already in the bimap, any overlapping -- bindings are deleted. -- -- Version: 0.2 insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b -- | O(log n). Insert a pair of values into the bimap, but only if -- neither is already in the bimap. Version: 0.2.2 tryInsert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b -- | O(log n). Delete a value and its twin from a bimap. -- -- When the value is not a member of the bimap, the original bimap is -- returned. -- -- Version: 0.2 delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b -- | O(log n) A version of delete specialized to the right -- key. Version: 0.2 deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b -- | O(log n). Find the element with minimal left key. Calls -- error if the bimap is empty. Version: 0.2.2 findMin :: Bimap a b -> (a, b) -- | O(log n). Find the element with minimal right key. The -- right-hand key is the first entry in the pair. Calls -- error if the bimap is empty. Version: 0.2.2 findMinR :: Bimap a b -> (b, a) -- | O(log n). Find the element with maximal left key. Calls -- error if the bimap is empty. Version: 0.2.2 findMax :: Bimap a b -> (a, b) -- | O(log n). Find the element with maximal right key. The -- right-hand key is the first entry in the pair. Calls -- error if the bimap is empty. Version: 0.2.2 findMaxR :: Bimap a b -> (b, a) -- | O(log n). Delete the element with minimal left key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMin :: (Ord b) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with minimal right key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMinR :: (Ord a) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with maximal left key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMax :: (Ord b) => Bimap a b -> Bimap a b -- | O(log n). Delete the element with maximal right key. Calls -- error if the bimap is empty. Version: 0.2.2 deleteMaxR :: (Ord a) => Bimap a b -> Bimap a b -- | O(log n). Delete and find the element with minimal left key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMin :: (Ord b) => Bimap a b -> ((a, b), Bimap a b) -- | O(log n). Delete and find the element with minimal right key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMinR :: (Ord a) => Bimap a b -> ((b, a), Bimap a b) -- | O(log n). Delete and find the element with maximal left key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMax :: (Ord b) => Bimap a b -> ((a, b), Bimap a b) -- | O(log n). Delete and find the element with maximal right key. -- Calls error if the bimap is empty. Version: -- 0.2.2 deleteFindMaxR :: (Ord a) => Bimap a b -> ((b, a), Bimap a b) -- | O(n*log n). Build a map from a list of pairs. If there are any -- overlapping pairs in the list, the later ones will override the -- earlier ones. Version: 0.2 fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b -- | O(n*log n). Build a map from a list of pairs. Unlike -- fromList, earlier pairs will take precedence over later ones. -- -- The name fromAList is a reference to Lisp-style association -- lists, where associations can be overridden by prepending new ones. -- -- Note that when duplicates occur in both the keys and in the values, -- fromList xs /= fromAList (reverse xs). However, if either -- contains no duplicates, then the equality holds. -- -- Version: 0.2.2 fromAList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b -- | O(n). Convert to a list of associated pairs. Version: -- 0.2 toList :: Bimap a b -> [(a, b)] -- | O(n). Convert to a list of associated pairs, with the left-hand -- values in ascending order. -- -- Since pair ordering is lexical, the pairs will also be in ascending -- order. -- -- Version: 0.2 toAscList :: Bimap a b -> [(a, b)] -- | O(n). Convert to a list of associated pairs, with the -- right-hand values first in the pair and in ascending order. -- -- Since pair ordering is lexical, the pairs will also be in ascending -- order. -- -- Version: 0.2 toAscListR :: Bimap a b -> [(b, a)] -- | O(n). Return all left-hand keys in the bimap in ascending -- order. Version: 0.2 keys :: Bimap a b -> [a] -- | O(n). Return all right-hand keys in the bimap in ascending -- order. Version: 0.2 keysR :: Bimap a b -> [b] -- | O(n). An alias for keysR. Version: 0.2 elems :: Bimap a b -> [b] -- | O(n). Return all associated pairs in the bimap, with the -- left-hand values in ascending order. Version: 0.2 assocs :: Bimap a b -> [(a, b)] -- | O(n). Fold the association pairs in the map, such that -- fold f z == foldr f z . assocs. -- Version: 0.2 fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c -- | O(1). Extract only the left-to-right component of a bimap. -- Version: 0.2.1 toMap :: Bimap a b -> Map a b -- | O(1). Extract only the right-to-left component of a bimap. -- Version: 0.2.1 toMapR :: Bimap a b -> Map b a -- | O(n*log n). Test if the internal bimap structure is valid. This -- should be true for any bimap created using the public interface. -- Version: 0.2 valid :: (Ord a, Ord b) => Bimap a b -> Bool -- | O(1). Reverse the positions of the two element types in the -- bimap. Version: 0.2 twist :: Bimap a b -> Bimap b a -- | O(1). Reverse the positions of the two element types in a bimap -- transformation. Version: 0.2 twisted :: (Bimap a b -> Bimap a b) -> (Bimap b a -> Bimap b a) instance (Eq a, Eq b) => Eq (Bimap a b) instance (Show a, Show b) => Show (Bimap a b)