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


-- | Extensions to Data.Map
--   
--   Extensions to Data.Map
@package map-exts
@version 0.2.0.0


-- | This module is a drop-in replacement for <a>Map</a>. It is intended to
--   be imported as <tt>import qualified Data.Map.Extensions as Map</tt>.
module Data.Map.Extensions

-- | Drops <tt>n</tt> elements from the (left hand side of the) <a>Map</a>.
dropLeft :: Int -> Map k v -> Map k v

-- | Drops <tt>n</tt> elements from the (right hand side of the)
--   <a>Map</a>.
dropRight :: Int -> Map k v -> Map k v

-- | Takes <tt>n</tt> elements from the (left hand side of the) <a>Map</a>.
takeLeft :: Int -> Map k v -> Map k v

-- | Takes <tt>n</tt> elements from the (right hand side of the)
--   <a>Map</a>.
takeRight :: Int -> Map k v -> Map k v

-- | Inclusive key-based slice. Returns a map whose keys are all between
--   the lower and upper bounds (inclusive).
--   
--   O(log n)
slice :: Ord k => Map k v -> k -> k -> Map k v

-- | Inclusive index-based slice. Run an inclusive slice given left and
--   right indices. if the left or right index is out of bounds, the left
--   index of <tt>0</tt> or right index of (<tt>Map.size m - 1</tt>) will
--   be used respectively.
--   
--   O(log n)
slicei :: Ord k => Map k v -> Int -> Int -> Map k v

-- | This generalizes <a>filter</a> to a monadic predicate.
filterM :: (Ord k, Monad m) => (v -> m Bool) -> Map k v -> m (Map k v)

-- | Transpose the first two indexes of a nested <a>Map</a>.
transpose :: (Ord a, Ord b) => Lookup2 a b v -> Lookup2 b a v

-- | Perform a left scan on the values of a <a>Map</a>.
--   
--   <pre>
--   Map.elems (Map.scanl1 f xs) = List.scanl1 f (Map.elems xs)
--   </pre>
scanl1 :: (Ord k) => (a -> a -> a) -> Lookup k a -> Lookup k a

-- | Perform a right scan on the values of a <a>Map</a>.
--   
--   <pre>
--   Map.elems (Map.scanr1 f xs) = List.scanr1 f (Map.elems xs)
--   </pre>
scanr1 :: (Ord k) => (a -> a -> a) -> Lookup k a -> Lookup k a

-- | Run a grouping function over a <a>Map</a>. The supplied function will
--   map each element of the list to a group. The resulting <a>Map</a> will
--   map the groups produced by the supplied function to the lists of
--   elements which produced that group.
--   
--   Perhaps this is better illustrated by example:
--   
--   <pre>
--   &gt;&gt;&gt; let even s = s `mod` 2 == 0
--   
--   &gt;&gt;&gt; groupBy even [1,2,3,4]
--   fromList [(False,[3,1]),(True,[4,2])]
--   </pre>
--   
--   O(n * log(n))
groupBy :: Ord b => (a -> b) -> [a] -> Map b [a]

-- | Run a grouping function over the keys of a <a>Map</a>.
--   
--   O(n * log(n))
groupKeysBy :: (Ord a, Ord b) => (a -> b) -> Lookup a v -> Lookup2 b a v

-- | Run a grouping function over the values of a <a>Map</a>.
--   
--   O(n * log(n))
groupElemsBy :: (Ord a, Ord b) => (v -> b) -> Lookup a v -> Lookup2 b a v

-- | Generate a Lookup2 from a list of triples.
fromList2 :: (Ord a, Ord b) => [(a, b, v)] -> Lookup2 a b v

-- | Create a Map from a list of keys and a list of values.
--   
--   <pre>
--   fromLists ks vs = fromList (zip ks vs)
--   </pre>
fromLists :: Ord k => [k] -> [v] -> Map k v

-- | Lookup a value two levels deep in a Lookup2
lookup2 :: (Ord a, Ord b) => a -> b -> Lookup2 a b v -> Maybe v

-- | Lookup a value three levels deep in a Lookup3
lookup3 :: (Ord a, Ord b, Ord c) => a -> b -> c -> Lookup3 a b c v -> Maybe v

-- | Lookup a value four levels deep in a Lookup4
lookup4 :: (Ord a, Ord b, Ord c, Ord d) => a -> b -> c -> d -> Lookup4 a b c d v -> Maybe v

-- | Synonym for Map
type Lookup ix1 tgt = Map ix1 tgt

-- | A doubly nested Map
type Lookup2 ix1 ix2 tgt = Map ix1 (Map ix2 tgt)

-- | A triply nested Map
type Lookup3 ix1 ix2 ix3 tgt = Map ix1 (Lookup2 ix2 ix3 tgt)

-- | A quadruply nested Map
type Lookup4 ix1 ix2 ix3 ix4 tgt = Lookup2 ix1 ix2 (Lookup2 ix3 ix4 tgt)