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

-- | Set- and Map-like types that remember the order elements were inserted
--   
--   Set- and Map-like types that remember the order elements were inserted
@package ordered-containers
@version 0.2.4

-- | An OMap behaves much like a Map, with mostly the same
--   asymptotics, but also remembers the order that keys were inserted. All
--   operations whose asymptotics are worse than Map have
--   documentation saying so.
module Data.Map.Ordered.Strict
data OMap k v
empty :: OMap k v
singleton :: (k, v) -> OMap k v
(<|) :: Ord k => (k, v) -> OMap k v -> OMap k v
infixr 5 <|
(|<) :: Ord k => (k, v) -> OMap k v -> OMap k v
infixr 5 |<
(>|) :: Ord k => OMap k v -> (k, v) -> OMap k v
infixl 5 >|
(|>) :: Ord k => OMap k v -> (k, v) -> OMap k v
infixl 5 |>

-- | When a key occurs in both maps, prefer the value from the second map.
--   
--   See asymptotics of unionWithR.
(<>|) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 <>|

-- | When a key occurs in both maps, prefer the value from the first map.
--   
--   See asymptotics of unionWithL.
(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 |<>

-- | Take the union. The first OMap 's argument's indices are lower
--   than the second. If a key appears in both maps, the first argument's
--   index takes precedence, and the supplied function is used to combine
--   the values.
--   
--   O(r*log(r)) where r is the size of the result
unionWithL :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v

-- | Take the union. The first OMap 's argument's indices are lower
--   than the second. If a key appears in both maps, the second argument's
--   index takes precedence, and the supplied function is used to combine
--   the values.
--   
--   O(r*log(r)) where r is the size of the result
unionWithR :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v

-- | A newtype to hang a Monoid instance on. The phantom first
--   parameter tells whether mappend will prefer the indices of its
--   first or second argument if there are shared elements in both.
newtype Bias (dir :: IndexPreference) a
Bias :: a -> Bias (dir :: IndexPreference) a
[unbiased] :: Bias (dir :: IndexPreference) a -> a
type L = 'L
type R = 'R
delete :: Ord k => k -> OMap k v -> OMap k v

-- | filter f m contains exactly the key-value pairs of m
--   that satisfy f, without changing the order they appear
filter :: Ord k => (k -> v -> Bool) -> OMap k v -> OMap k v

-- | m \\ n deletes all the keys that exist in n from
--   m
--   
--   O(m*log(n)) where m is the size of the smaller map and
--   n is the size of the larger map.
(\\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Intersection. (The /\ is intended to look a bit like the
--   standard mathematical notation for set intersection.)
--   
--   See asymptotics of intersectionWith.
(|/\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Intersection. (The /\ is intended to look a bit like the
--   standard mathematical notation for set intersection.)
--   
--   See asymptotics of intersectionWith.
(/\|) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Take the intersection. The first OMap 's argument's indices are
--   used for the result.
--   
--   O(m*log(n/(m+1)) + r*log(r)) where m is the size of the
--   smaller map, n is the size of the larger map, and r is
--   the size of the result.
intersectionWith :: Ord k => (k -> v -> v' -> v'') -> OMap k v -> OMap k v' -> OMap k v''
null :: OMap k v -> Bool
size :: OMap k v -> Int
member :: Ord k => k -> OMap k v -> Bool
notMember :: Ord k => k -> OMap k v -> Bool
lookup :: Ord k => k -> OMap k v -> Maybe v

-- | A 0-based index, much like the indices used by lists' !!
--   operation. All indices are with respect to insertion order.
type Index = Int
findIndex :: Ord k => k -> OMap k v -> Maybe Index
elemAt :: OMap k v -> Index -> Maybe (k, v)

-- | If a key appears multiple times, the first occurrence is used for
--   ordering and the last occurrence is used for its value. The library
--   author welcomes comments on whether this default is sane.
fromList :: Ord k => [(k, v)] -> OMap k v

-- | Return key-value pairs in the order they were inserted.
assocs :: OMap k v -> [(k, v)]

-- | Return key-value pairs in order of increasing key.
toAscList :: OMap k v -> [(k, v)]

-- | Convert an OMap to a Map.
--   
--   O(n), where n is the size of the OMap.
toMap :: OMap k v -> Map k v

-- | An OMap behaves much like a Map, with mostly the same
--   asymptotics, but also remembers the order that keys were inserted. All
--   operations whose asymptotics are worse than Map have
--   documentation saying so.
module Data.Map.Ordered
data OMap k v
empty :: OMap k v
singleton :: (k, v) -> OMap k v
(<|) :: Ord k => (k, v) -> OMap k v -> OMap k v
infixr 5 <|
(|<) :: Ord k => (k, v) -> OMap k v -> OMap k v
infixr 5 |<
(>|) :: Ord k => OMap k v -> (k, v) -> OMap k v
infixl 5 >|
(|>) :: Ord k => OMap k v -> (k, v) -> OMap k v
infixl 5 |>

-- | When a key occurs in both maps, prefer the value from the second map.
--   
--   See asymptotics of unionWithR.
(<>|) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 <>|

-- | When a key occurs in both maps, prefer the value from the first map.
--   
--   See asymptotics of unionWithL.
(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 |<>

-- | Take the union. The first OMap 's argument's indices are lower
--   than the second. If a key appears in both maps, the first argument's
--   index takes precedence, and the supplied function is used to combine
--   the values.
--   
--   O(r*log(r)) where r is the size of the result
unionWithL :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v

-- | Take the union. The first OMap 's argument's indices are lower
--   than the second. If a key appears in both maps, the second argument's
--   index takes precedence, and the supplied function is used to combine
--   the values.
--   
--   O(r*log(r)) where r is the size of the result
unionWithR :: Ord k => (k -> v -> v -> v) -> OMap k v -> OMap k v -> OMap k v

-- | A newtype to hang a Monoid instance on. The phantom first
--   parameter tells whether mappend will prefer the indices of its
--   first or second argument if there are shared elements in both.
newtype Bias (dir :: IndexPreference) a
Bias :: a -> Bias (dir :: IndexPreference) a
[unbiased] :: Bias (dir :: IndexPreference) a -> a
type L = 'L
type R = 'R
delete :: Ord k => k -> OMap k v -> OMap k v

-- | filter f m contains exactly the key-value pairs of m
--   that satisfy f, without changing the order they appear
filter :: Ord k => (k -> v -> Bool) -> OMap k v -> OMap k v

-- | m \\ n deletes all the keys that exist in n from
--   m
--   
--   O(m*log(n)) where m is the size of the smaller map and
--   n is the size of the larger map.
(\\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Intersection. (The /\ is intended to look a bit like the
--   standard mathematical notation for set intersection.)
--   
--   See asymptotics of intersectionWith.
(|/\) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Intersection. (The /\ is intended to look a bit like the
--   standard mathematical notation for set intersection.)
--   
--   See asymptotics of intersectionWith.
(/\|) :: Ord k => OMap k v -> OMap k v' -> OMap k v

-- | Take the intersection. The first OMap 's argument's indices are
--   used for the result.
--   
--   O(m*log(n/(m+1)) + r*log(r)) where m is the size of the
--   smaller map, n is the size of the larger map, and r is
--   the size of the result.
intersectionWith :: Ord k => (k -> v -> v' -> v'') -> OMap k v -> OMap k v' -> OMap k v''

-- | Alter the value (or its absence) associated with a key.
alter :: Ord k => (Maybe v -> Maybe v) -> k -> OMap k v -> OMap k v
null :: OMap k v -> Bool
size :: OMap k v -> Int
member :: Ord k => k -> OMap k v -> Bool
notMember :: Ord k => k -> OMap k v -> Bool
lookup :: Ord k => k -> OMap k v -> Maybe v

-- | A 0-based index, much like the indices used by lists' !!
--   operation. All indices are with respect to insertion order.
type Index = Int
findIndex :: Ord k => k -> OMap k v -> Maybe Index
elemAt :: OMap k v -> Index -> Maybe (k, v)

-- | If a key appears multiple times, the first occurrence is used for
--   ordering and the last occurrence is used for its value. The library
--   author welcomes comments on whether this default is sane.
fromList :: Ord k => [(k, v)] -> OMap k v

-- | Return key-value pairs in the order they were inserted.
assocs :: OMap k v -> [(k, v)]

-- | Return key-value pairs in order of increasing key.
toAscList :: OMap k v -> [(k, v)]

-- | Convert an OMap to a Map.
--   
--   O(n), where n is the size of the OMap.
toMap :: OMap k v -> Map k v

-- | An OSet behaves much like a Set, with mostly the same
--   asymptotics, but also remembers the order that values were inserted.
--   All operations whose asymptotics are worse than Set have
--   documentation saying so.
module Data.Set.Ordered
data OSet a
empty :: OSet a
singleton :: a -> OSet a
(<|) :: Ord a => a -> OSet a -> OSet a
infixr 5 <|
(|<) :: Ord a => a -> OSet a -> OSet a
infixr 5 |<
(>|) :: Ord a => OSet a -> a -> OSet a
infixl 5 >|
(|>) :: Ord a => OSet a -> a -> OSet a
infixl 5 |>

-- | O(m*log(n)+n), where m is the size of the smaller set
--   and n is the size of the larger set.
(<>|) :: Ord a => OSet a -> OSet a -> OSet a
infixr 6 <>|

-- | O(m*log(n)+n), where m is the size of the smaller set
--   and n is the size of the larger set.
(|<>) :: Ord a => OSet a -> OSet a -> OSet a
infixr 6 |<>

-- | A newtype to hang a Monoid instance on. The phantom first
--   parameter tells whether mappend will prefer the indices of its
--   first or second argument if there are shared elements in both.
newtype Bias (dir :: IndexPreference) a
Bias :: a -> Bias (dir :: IndexPreference) a
[unbiased] :: Bias (dir :: IndexPreference) a -> a
type L = 'L
type R = 'R
null :: OSet a -> Bool
size :: OSet a -> Int
member :: Ord a => a -> OSet a -> Bool
notMember :: Ord a => a -> OSet a -> Bool
delete :: Ord a => a -> OSet a -> OSet a
filter :: Ord a => (a -> Bool) -> OSet a -> OSet a

-- | Set difference: r \\ s deletes all the values in s
--   from r. The order of r is unchanged.
--   
--   O(m*log(n)) where m is the size of the smaller set and
--   n is the size of the larger set.
(\\) :: Ord a => OSet a -> OSet a -> OSet a

-- | Intersection. (/\ is meant to look a bit like the standard
--   mathematical notation for intersection.)
--   
--   O(m*log(n/(m+1)) + r*log(r)), where m is the size of the
--   smaller set, n the size of the larger set, and r the
--   size of the result.
(|/\) :: Ord a => OSet a -> OSet a -> OSet a

-- | 
--   flip (|/\)
--   
--   
--   See asymptotics of |/\.
(/\|) :: Ord a => OSet a -> OSet a -> OSet a

-- | A 0-based index, much like the indices used by lists' !!
--   operation. All indices are with respect to insertion order.
type Index = Int
findIndex :: Ord a => a -> OSet a -> Maybe Index
elemAt :: OSet a -> Index -> Maybe a

-- | If a value occurs multiple times, only the first occurrence is used.
fromList :: Ord a => [a] -> OSet a

-- | Returns values in ascending order. (Use toList to return them
--   in insertion order.)
toAscList :: OSet a -> [a]

-- | Convert an OSet to a Set.
--   
--   O(n), where n is the size of the OSet.
toSet :: OSet a -> Set a
instance (GHC.Internal.Data.Data.Data a, GHC.Classes.Ord a) => GHC.Internal.Data.Data.Data (Data.Set.Ordered.OSet a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Set.Ordered.OSet a)
instance GHC.Internal.Data.Foldable.Foldable Data.Set.Ordered.OSet
instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.Set.Ordered.OSet a)
instance GHC.Classes.Ord a => GHC.Internal.IsList.IsList (Data.Set.Ordered.OSet a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Monoid (Data.Map.Util.Bias Data.Map.Util.L (Data.Set.Ordered.OSet a))
instance GHC.Classes.Ord a => GHC.Internal.Base.Monoid (Data.Map.Util.Bias Data.Map.Util.R (Data.Set.Ordered.OSet a))
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Set.Ordered.OSet a)
instance (GHC.Classes.Ord a, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Data.Set.Ordered.OSet a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.Map.Util.Bias Data.Map.Util.L (Data.Set.Ordered.OSet a))
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.Map.Util.Bias Data.Map.Util.R (Data.Set.Ordered.OSet a))
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Set.Ordered.OSet a)
