-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | 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.5.0


-- | An implementation of bidirectional maps between values of two key
--   types. A <a>Bimap</a> 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 <tt>R</tt>
--   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 <tt>a</tt> and <tt>b</tt>.
data Bimap a b

-- | <i>O(1)</i>. Is the bimap empty? <i>Version: 0.2</i>
null :: Bimap a b -> Bool

-- | <i>O(1)</i>. The number of elements in the bimap. <i>Version: 0.2</i>
size :: Bimap a b -> Int

-- | <i>O(log n)</i>. Is the specified value a member of the bimap?
--   <i>Version: 0.2</i>
member :: (Ord a, Ord b) => a -> Bimap a b -> Bool

-- | <i>O(log n)</i>. A version of <a>member</a> specialized to the right
--   key. <i>Version: 0.2</i>
memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool

-- | <i>O(log n)</i>. Is the specified value not a member of the bimap?
--   <i>Version: 0.2</i>
notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool

-- | <i>O(log n)</i>. A version of <a>notMember</a> specialized to the
--   right key. <i>Version: 0.2</i>
notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool

-- | <i>O(log n)</i>. Are the two values associated <i>with each other</i>
--   in the bimap?
--   
--   This function is uncurried in its first two arguments, so that it can
--   be used infix.
--   
--   <i>Version: 0.2</i>
pairMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool

-- | <i>O(log n)</i>. Are the two values not in the bimap, or not
--   associated with each other? (Complement of <a>pairMember</a>.)
--   <i>Version: 0.2</i>
pairNotMember :: (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool

-- | <i>O(log n)</i>. Lookup a left key in the bimap, returning the
--   associated right key.
--   
--   This function will <tt>return</tt> the result in the monad, or
--   <tt>fail</tt> if the value isn't in the bimap.
--   
--   Note that the signature differs slightly from Data.Map's
--   <tt>lookup</tt>. This one is more general - it functions the same way
--   as the "original" if <tt>m</tt> is cast (or inferred) to Maybe.
--   
--   <i>Version: 0.2</i>
lookup :: (Ord a, Ord b, MonadThrow m) => a -> Bimap a b -> m b

-- | <i>O(log n)</i>. A version of <a>lookup</a> that is specialized to the
--   right key, and returns the corresponding left key.
--   
--   <i>Version: 0.2</i>
lookupR :: (Ord a, Ord b, MonadThrow m) => b -> Bimap a b -> m a

-- | <i>O(log n)</i>. Find the right key corresponding to a given left key.
--   Calls <tt><a>error</a></tt> when the key is not in the bimap.
--   <i>Version: 0.2</i>
(!) :: (Ord a, Ord b) => Bimap a b -> a -> b

-- | <i>O(log n)</i>. A version of <tt>(!)</tt> that is specialized to the
--   right key, and returns the corresponding left key. <i>Version: 0.2</i>
(!>) :: (Ord a, Ord b) => Bimap a b -> b -> a

-- | <i>O(log n)</i>. See <a>lookup</a>.
(!?) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> a -> m b

-- | <i>O(log n)</i>. See <a>lookupR</a>.
(!?>) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> b -> m a

-- | <i>O(1)</i>. The empty bimap. <i>Version: 0.2</i>
empty :: Bimap a b

-- | <i>O(1)</i>. A bimap with a single element. <i>Version: 0.2</i>
singleton :: a -> b -> Bimap a b

-- | <i>O(log n)</i>. 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.
--   
--   <i>Version: 0.2</i>
insert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Insert a pair of values into the bimap, but only if
--   neither is already in the bimap. <i>Version: 0.2.2</i>
tryInsert :: (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Update a value at a specific left key with the result
--   of the provided function.
--   
--   When the left key is not a member of the bimap, the original bimap is
--   returned.
adjust :: (Ord a, Ord b) => (b -> b) -> a -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Update a value at a specific right key with the
--   result of the provided function.
--   
--   When the right key is not a member of the bimap, the original bimap is
--   returned.
adjustR :: (Ord a, Ord b) => (a -> a) -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Adjust a value at a specific left key.
--   
--   When the left key is not a member of the bimap, the original bimap is
--   returned.
adjustWithKey :: (Ord a, Ord b) => (a -> b -> b) -> a -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Adjust a value at a specific right key.
--   
--   When the right key is not a member of the bimap, the original bimap is
--   returned.
adjustWithKeyR :: (Ord a, Ord b) => (b -> a -> a) -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. The expression (<tt><a>update</a> f a bimap</tt>)
--   updates the right value <tt>b</tt> at <tt>a</tt> (if it is in the
--   bimap).
--   
--   If (<tt>f b</tt>) is <a>Nothing</a>, the element is deleted.
--   
--   If it is (<tt><a>Just</a> y</tt>), the left key <tt>a</tt> is bound to
--   the new value <tt>y</tt>.
update :: (Ord a, Ord b) => (b -> Maybe b) -> a -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. The expression (<tt><a>updateR</a> f b bimap</tt>)
--   updates the left value <tt>a</tt> at <tt>b</tt> (if it is in the
--   bimap).
--   
--   If (<tt>f a</tt>) is <a>Nothing</a>, the element is deleted.
--   
--   If it is (<tt><a>Just</a> x</tt>), the right key <tt>b</tt> is bound
--   to the new value <tt>x</tt>.
updateR :: (Ord a, Ord b) => (a -> Maybe a) -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKey</a> f a
--   bimap</tt>) updates the right value <tt>b</tt> at <tt>a</tt> (if it is
--   in the bimap).
--   
--   If (<tt>f a b</tt>) is <a>Nothing</a>, the element is deleted.
--   
--   If it is (<tt><a>Just</a> y</tt>), the left key <tt>a</tt> is bound to
--   the new value <tt>y</tt>.
updateWithKey :: (Ord a, Ord b) => (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. The expression (<tt><a>updateWithKeyR</a> f b
--   bimap</tt>) updates the left value <tt>a</tt> at <tt>b</tt> (if it is
--   in the bimap).
--   
--   If (<tt>f b a</tt>) is <a>Nothing</a>, the element is deleted.
--   
--   If it is (<tt><a>Just</a> x</tt>), the right key <tt>b</tt> is bound
--   to the new value <tt>x</tt>.
updateWithKeyR :: (Ord a, Ord b) => (b -> a -> Maybe a) -> b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Delete a value and its twin from a bimap.
--   
--   When the value is not a member of the bimap, the original bimap is
--   returned.
--   
--   <i>Version: 0.2</i>
delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i> A version of <a>delete</a> specialized to the right
--   key. <i>Version: 0.2</i>
deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Find the element with minimal left key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
findMin :: Bimap a b -> (a, b)

-- | <i>O(log n)</i>. Find the element with minimal right key. The
--   right-hand key is the first entry in the pair. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
findMinR :: Bimap a b -> (b, a)

-- | <i>O(log n)</i>. Find the element with maximal left key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
findMax :: Bimap a b -> (a, b)

-- | <i>O(log n)</i>. Find the element with maximal right key. The
--   right-hand key is the first entry in the pair. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
findMaxR :: Bimap a b -> (b, a)

-- | <i>O(log n)</i>. Delete the element with minimal left key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
deleteMin :: Ord b => Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Delete the element with minimal right key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
deleteMinR :: Ord a => Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Delete the element with maximal left key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
deleteMax :: Ord b => Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Delete the element with maximal right key. Calls
--   <tt><a>error</a></tt> if the bimap is empty. <i>Version: 0.2.2</i>
deleteMaxR :: Ord a => Bimap a b -> Bimap a b

-- | <i>O(log n)</i>. Delete and find the element with minimal left key.
--   Calls <tt><a>error</a></tt> if the bimap is empty. <i>Version:
--   0.2.2</i>
deleteFindMin :: Ord b => Bimap a b -> ((a, b), Bimap a b)

-- | <i>O(log n)</i>. Delete and find the element with minimal right key.
--   Calls <tt><a>error</a></tt> if the bimap is empty. <i>Version:
--   0.2.2</i>
deleteFindMinR :: Ord a => Bimap a b -> ((b, a), Bimap a b)

-- | <i>O(log n)</i>. Delete and find the element with maximal left key.
--   Calls <tt><a>error</a></tt> if the bimap is empty. <i>Version:
--   0.2.2</i>
deleteFindMax :: Ord b => Bimap a b -> ((a, b), Bimap a b)

-- | <i>O(log n)</i>. Delete and find the element with maximal right key.
--   Calls <tt><a>error</a></tt> if the bimap is empty. <i>Version:
--   0.2.2</i>
deleteFindMaxR :: Ord a => Bimap a b -> ((b, a), Bimap a b)

-- | <i>O(n)</i>. Filter all association pairs that satisfy the predicate.
--   
--   Note that the predicate will be applied <i>twice</i> for each
--   association in the bimap.
--   
--   <i>Version: 0.2.4</i>
filter :: (Ord a, Ord b) => (a -> b -> Bool) -> Bimap a b -> Bimap a b

-- | <i>O(n)</i>. Partition the bimap according to a predicate. The first
--   bimap contains all associations that satisfy the predicate; the second
--   contains all associations that fail the predicate.
--   
--   Note that the predicate will be applied <i>twice</i> for each
--   association in the bimap.
--   
--   <i>Version: 0.2.4</i>
partition :: (Ord a, Ord b) => (a -> b -> Bool) -> Bimap a b -> (Bimap a b, Bimap a b)

-- | <i>O(n*log n)</i>. 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. <i>Version: 0.2</i>
fromList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b

-- | <i>O(n*log n)</i>. Build a map from a list of pairs. Unlike
--   <a>fromList</a>, earlier pairs will take precedence over later ones.
--   
--   The name <tt>fromAList</tt> 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,
--   <tt>fromList xs /= fromAList (reverse xs)</tt>. However, if either
--   contains no duplicates, then the equality holds.
--   
--   <i>Version: 0.2.2</i>
fromAList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b

-- | <i>O(n)</i>. Build a bimap from a list of pairs, where both the
--   <tt>fst</tt> and <tt>snd</tt> halves of the list are in strictly
--   ascending order.
--   
--   This precondition is checked; an invalid list will cause an error.
--   
--   <i>Version: 0.2.3</i>
fromAscPairList :: (Ord a, Ord b) => [(a, b)] -> Bimap a b

-- | <i>O(n)</i>. Build a bimap from a list of pairs, where both the
--   <tt>fst</tt> and <tt>snd</tt> halves of the list are in strictly
--   ascending order.
--   
--   This precondition is <i>not</i> checked; an invalid list will produce
--   a malformed bimap.
--   
--   <i>Version: 0.2.3</i>
fromAscPairListUnchecked :: (Ord a, Ord b) => [(a, b)] -> Bimap a b

-- | <i>O(n)</i>. Convert to a list of associated pairs. <i>Version:
--   0.2</i>
toList :: Bimap a b -> [(a, b)]

-- | <i>O(n)</i>. 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.
--   
--   <i>Version: 0.2</i>
toAscList :: Bimap a b -> [(a, b)]

-- | <i>O(n)</i>. 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.
--   
--   <i>Version: 0.2</i>
toAscListR :: Bimap a b -> [(b, a)]

-- | <i>O(n)</i>. Return all left-hand keys in the bimap in ascending
--   order. <i>Version: 0.2</i>
keys :: Bimap a b -> [a]

-- | <i>O(n)</i>. Return all right-hand keys in the bimap in ascending
--   order. <i>Version: 0.2</i>
keysR :: Bimap a b -> [b]

-- | <i>O(n)</i>. An alias for <a>keysR</a>. <i>Version: 0.2</i>
elems :: Bimap a b -> [b]

-- | <i>O(n)</i>. Return all associated pairs in the bimap, with the
--   left-hand values in ascending order. <i>Version: 0.2</i>
assocs :: Bimap a b -> [(a, b)]

-- | <i>O(n)</i>. Fold the association pairs in the map, such that
--   <tt><a>fold</a> f z == <a>foldr</a> f z . <a>assocs</a></tt>.
--   <i>Version: 0.2</i>
fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c

-- | <i>O(n*log n)</i> Map a function over all the left keys in the map.
--   <i>Version 0.3</i>
map :: Ord c => (a -> c) -> Bimap a b -> Bimap c b

-- | <i>O(n*log n)</i> Map a function over all the right keys in the map.
--   <i>Version 0.3</i>
mapR :: Ord c => (b -> c) -> Bimap a b -> Bimap a c

-- | <i>O(n)</i>. Map a strictly increasing function over all left keys in
--   the map. <i>The precondition is not checked.</i> <i>Version 0.3</i>
mapMonotonic :: (a -> c) -> Bimap a b -> Bimap c b

-- | <i>O(n)</i>. Map a strictly increasing function over all right keys in
--   the map. <i>The precondition is not checked.</i> <i>Version 0.3</i>
mapMonotonicR :: (b -> c) -> Bimap a b -> Bimap a c

-- | <i>O(1)</i>. Extract only the left-to-right component of a bimap.
--   <i>Version: 0.2.1</i>
toMap :: Bimap a b -> Map a b

-- | <i>O(1)</i>. Extract only the right-to-left component of a bimap.
--   <i>Version: 0.2.1</i>
toMapR :: Bimap a b -> Map b a

-- | <i>O(n*log n)</i>. Test if the internal bimap structure is valid. This
--   should be true for any bimap created using the public interface,
--   unless <a>fromAscPairListUnchecked</a> has been used inappropriately.
--   <i>Version: 0.2</i>
valid :: (Ord a, Ord b) => Bimap a b -> Bool

-- | <i>O(1)</i>. Reverse the positions of the two element types in the
--   bimap. <i>Version: 0.2</i>
twist :: Bimap a b -> Bimap b a

-- | <i>O(1)</i>. Reverse the positions of the two element types in a bimap
--   transformation. <i>Version: 0.2</i>
twisted :: (Bimap a b -> Bimap a b) -> Bimap b a -> Bimap b a
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (Data.Bimap.Bimap a b)
instance GHC.Classes.Eq Data.Bimap.BimapException
instance GHC.Internal.Exception.Type.Exception Data.Bimap.BimapException
instance GHC.Internal.Generics.Generic (Data.Bimap.Bimap a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Internal.IsList.IsList (Data.Bimap.Bimap a b)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData b) => Control.DeepSeq.NFData (Data.Bimap.Bimap a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (Data.Bimap.Bimap a b)
instance (GHC.Internal.Show.Show a, GHC.Internal.Show.Show b) => GHC.Internal.Show.Show (Data.Bimap.Bimap a b)
instance GHC.Internal.Show.Show Data.Bimap.BimapException
