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


-- | An <a>OMap</a> behaves much like a <a>Map</a>, with mostly the same
--   asymptotics, but also remembers the order that keys were inserted. All
--   operations whose asymptotics are worse than <a>Map</a> 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 first map.
--   
--   See asymptotics of <a>unionWithR</a>.
(<>|) :: 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 <a>unionWithL</a>.
(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 |<>

-- | Take the union. The first <a>OMap</a> '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.
--   
--   <i>O(r*log(r))</i> where <i>r</i> 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 <a>OMap</a> '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.
--   
--   <i>O(r*log(r))</i> where <i>r</i> 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 hand a <a>Monoid</a> instance on. The phantom first
--   parameter tells whether <a>mappend</a> 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

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

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

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

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

-- | Take the intersection. The first <a>OMap</a> 's argument's indices are
--   used for the result.
--   
--   <i>O(m*log(n/(m+1)) + r*log(r))</i> where <i>m</i> is the size of the
--   smaller map, <i>n</i> is the size of the larger map, and <i>r</i> 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' <a>!!</a>
--   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 <a>OMap</a> to a <a>Map</a>.
--   
--   <i>O(n)</i>, where <i>n</i> is the size of the <a>OMap</a>.
toMap :: OMap k v -> Map k v


-- | An <a>OMap</a> behaves much like a <a>Map</a>, with mostly the same
--   asymptotics, but also remembers the order that keys were inserted. All
--   operations whose asymptotics are worse than <a>Map</a> 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 first map.
--   
--   See asymptotics of <a>unionWithR</a>.
(<>|) :: 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 <a>unionWithL</a>.
(|<>) :: Ord k => OMap k v -> OMap k v -> OMap k v
infixr 6 |<>

-- | Take the union. The first <a>OMap</a> '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.
--   
--   <i>O(r*log(r))</i> where <i>r</i> 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 <a>OMap</a> '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.
--   
--   <i>O(r*log(r))</i> where <i>r</i> 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 hand a <a>Monoid</a> instance on. The phantom first
--   parameter tells whether <a>mappend</a> 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

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

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

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

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

-- | Take the intersection. The first <a>OMap</a> 's argument's indices are
--   used for the result.
--   
--   <i>O(m*log(n/(m+1)) + r*log(r))</i> where <i>m</i> is the size of the
--   smaller map, <i>n</i> is the size of the larger map, and <i>r</i> 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 at k, or absence of. Can be used to insert delete or
--   update with the same semantics as <a>Map</a>s alter
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' <a>!!</a>
--   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 <a>OMap</a> to a <a>Map</a>.
--   
--   <i>O(n)</i>, where <i>n</i> is the size of the <a>OMap</a>.
toMap :: OMap k v -> Map k v


-- | An <a>OSet</a> behaves much like a <a>Set</a>, with mostly the same
--   asymptotics, but also remembers the order that values were inserted.
--   All operations whose asymptotics are worse than <a>Set</a> 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 |>

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

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

-- | A newtype to hand a <a>Monoid</a> instance on. The phantom first
--   parameter tells whether <a>mappend</a> 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: <tt>r \\ s</tt> deletes all the values in <tt>s</tt>
--   from <tt>r</tt>. The order of <tt>r</tt> is unchanged.
--   
--   <i>O(m*log(n))</i> where <i>m</i> is the size of the smaller set and
--   <i>n</i> is the size of the larger set.
(\\) :: Ord a => OSet a -> OSet a -> OSet a

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

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

-- | A 0-based index, much like the indices used by lists' <a>!!</a>
--   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 <a>toList</a> to return them
--   in insertion order.)
toAscList :: OSet a -> [a]

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