-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Please see the README on Github at
-- https://github.com/oisdk/quickselect#readme
@package quickselect
@version 0.1.0.0
-- | This module provides optimal median-finding functions for small,
-- fixed-size inputs. Each function returns the (0-based) index of the
-- argument which is the median, according to the supplied relation.
module Data.Median.Optimal
-- | Find the median of 3 items, optimally.
--
--
-- >>> median3 (<=) 1 2 3
-- 1
--
-- >>> median3 (<=) 1 3 2
-- 2
--
-- >>> median3 (<=) 2 3 1
-- 0
--
--
--
-- [x,y,z] !! median3 (<=) x y z === sort [x,y,z] !! 1
--
median3 :: (a -> a -> Bool) -> a -> a -> a -> Int
-- | Find the median of 4 items, optimally.
--
--
-- >>> median4 (<=) 1 4 3 2
-- 2
--
-- >>> median4 (<=) 1 3 2 4
-- 1
--
-- >>> median4 (<=) 2 4 1 3
-- 3
--
-- >>> median4 (<=) 3 1 4 2
-- 0
--
--
--
-- [w,x,y,z] !! median4 (<=) w x y z `elem` (init.tail.sort) [w,x,y,z]
--
median4 :: (a -> a -> Bool) -> a -> a -> a -> a -> Int
-- | Find the median of 5 items, optimally.
--
--
-- >>> median5 (<=) 1 4 3 2 5
-- 2
--
-- >>> median5 (<=) 1 3 2 4 5
-- 1
--
-- >>> median5 (<=) 2 4 1 3 5
-- 3
--
-- >>> median5 (<=) 3 1 4 2 5
-- 0
--
-- >>> median5 (<=) 2 1 4 5 3
-- 4
--
--
--
-- [v,w,x,y,z] !! median5 (<=) v w x y z === sort [v,w,x,y,z] !! 2
--
median5 :: (a -> a -> Bool) -> a -> a -> a -> a -> a -> Int
-- | This module provides optimal selection functions for small, fixed-size
-- inputs. Each function returns the (0-based) index of the argument
-- which is the nth item, according to the supplied relation.
module Data.Select.Optimal
-- | Select from 2 items.
select2 :: (a -> a -> Bool) -> Int -> a -> a -> Int
-- | Select from 3 items.
select3 :: (a -> a -> Bool) -> Int -> a -> a -> a -> Int
-- | Select from 4 items.
select4 :: (a -> a -> Bool) -> Int -> a -> a -> a -> a -> Int
-- | Select from 5 items.
select5 :: (a -> a -> Bool) -> Int -> a -> a -> a -> a -> a -> Int
module Data.Vector.Mutable.Partition
-- | partition (<=) xs lb ub n partitions the
-- section of the list defined by the inclusive slice
-- [lb,ub] around the element at n.
partition :: MVector v a => (a -> a -> Bool) -> v s a -> Int -> Int -> Int -> ST s Int
-- | Quickselect internals on mutable, generic vectors.
module Data.Select.Mutable.Quick
-- | select (<=) xs lb ub n returns the
-- nth item in the indices in the inclusive range
-- [lb,ub].
select :: MVector v a => (a -> a -> Bool) -> v s a -> Int -> Int -> Int -> ST s Int
-- | This module provides an implementation of quickselect on boxed
-- vectors. It has an average time of <math>, but a worst-case time
-- of <math>. For an algorithm with similar performance but a
-- better worst-case time, see Data.Select.Unboxed.Intro.
module Data.Select.Unboxed.Quick
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList (xs :: [Int]))
--
selectBy :: Unbox a => (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6]) :: Int
-- 3
--
select :: (Unbox a, Ord a) => Int -> Vector a -> a
-- | This module provides an implementation of quickselect on boxed
-- vectors. It has an average time of <math>, but a worst-case time
-- of <math>. For an algorithm with similar performance but a
-- better worst-case time, see Data.Select.Intro.
module Data.Select.Quick
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList xs)
--
selectBy :: (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6])
-- 3
--
select :: Ord a => Int -> Vector a -> a
-- | Median-of-medians internals on mutable, boxed vectors.
module Data.Select.Mutable.Median
-- | select (<=) xs lb ub n returns the
-- nth item in the indices in the inclusive range
-- [lb,ub].
select :: MVector v a => (a -> a -> Bool) -> v s a -> Int -> Int -> Int -> ST s Int
-- | This module provides an implementation of median-of-medians on unboxed
-- vectors. As a selection algorithm, it has optimal <math>
-- worst-case time, however it is usually beaten in practice by
-- quickselect (which has <math> worst-case time). For an algorithm
-- with the same worst-case time, but better general performance, see
-- Data.Select.Unboxed.Intro.
module Data.Select.Unboxed.Median
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList (xs :: [Int]))
--
selectBy :: Unbox a => (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6]) :: Int
-- 3
--
select :: (Unbox a, Ord a) => Int -> Vector a -> a
-- | This module provides an implementation of median-of-medians on boxed
-- vectors. As a selection algorithm, it has optimal <math>
-- worst-case time, however it is usually beaten in practice by
-- quickselect (which has <math> worst-case time). For an algorithm
-- with the same worst-case time, but better general performance, see
-- Data.Select.Intro.
module Data.Select.Median
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList xs)
--
selectBy :: (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6])
-- 3
--
select :: Ord a => Int -> Vector a -> a
-- | Introselect internals on mutable, generic vectors.
module Data.Select.Mutable.Intro
-- | select (<=) xs lb ub n returns the
-- nth item in the indices in the inclusive range
-- [lb,ub].
select :: MVector v a => (a -> a -> Bool) -> v s a -> Int -> Int -> Int -> ST s Int
-- | This module provides an implementation of introselect on unboxed
-- vectors. It begins as quickselect, but if it discovers it's in a
-- pathological case, it switches to a median-of-medians implementation.
-- This guarantees <math> worst-case time.
module Data.Select.Unboxed.Intro
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList (xs :: [Int]))
--
selectBy :: Unbox a => (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6]) :: Int
-- 3
--
select :: (Unbox a, Ord a) => Int -> Vector a -> a
-- | This module provides an implementation of introselect on boxed
-- vectors. It begins as quickselect, but if it discovers it's in a
-- pathological case, it switches to a median-of-medians implementation.
-- This guarantees <math> worst-case time.
module Data.Select.Intro
-- | <math>. Find the nth item, ordered by the supplied relation.
--
--
-- i >= 0 && i < length xs ==> sort xs !! i === selectBy (<=) i (Vector.fromList xs)
--
selectBy :: (a -> a -> Bool) -> Int -> Vector a -> a
-- | <math>. Find the nth smallest item in the vector.
--
--
-- >>> select 4 (Vector.fromList "this is an example")
-- 'a'
--
--
--
-- >>> select 3 (Vector.fromList [0,1,4,2,3,5,6])
-- 3
--
select :: Ord a => Int -> Vector a -> a