1{-# LANGUAGE TypeFamilies #-}
2
3-- ---------------------------------------------------------------------------
4-- |
5-- Module      : Data.Vector.Algorithms.Insertion
6-- Copyright   : (c) 2008-2010 Dan Doel
7-- Maintainer  : Dan Doel
8-- Stability   : Experimental
9-- Portability : Portable
10--
11-- A simple insertion sort. Though it's O(n^2), its iterative nature can be
12-- beneficial for small arrays. It is used to sort small segments of an array
13-- by some of the more heavy-duty, recursive algorithms.
14
15module Data.Vector.Algorithms.Insertion
16       ( sort
17       , sortBy
18       , sortByBounds
19       , sortByBounds'
20       , Comparison
21       ) where
22
23
24import Prelude hiding (read, length)
25
26import Control.Monad.Primitive
27
28import Data.Vector.Generic.Mutable
29
30import Data.Vector.Algorithms.Common (Comparison)
31
32import qualified Data.Vector.Algorithms.Optimal as O
33
34-- | Sorts an entire array using the default comparison for the type
35sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()
36sort = sortBy compare
37{-# INLINABLE sort #-}
38
39-- | Sorts an entire array using a given comparison
40sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m ()
41sortBy cmp a = sortByBounds cmp a 0 (length a)
42{-# INLINE sortBy #-}
43
44-- | Sorts the portion of an array delimited by [l,u)
45sortByBounds :: (PrimMonad m, MVector v e)
46             => Comparison e -> v (PrimState m) e -> Int -> Int -> m ()
47sortByBounds cmp a l u
48  | len < 2   = return ()
49  | len == 2  = O.sort2ByOffset cmp a l
50  | len == 3  = O.sort3ByOffset cmp a l
51  | len == 4  = O.sort4ByOffset cmp a l
52  | otherwise = O.sort4ByOffset cmp a l >> sortByBounds' cmp a l (l + 4) u
53 where
54 len = u - l
55{-# INLINE sortByBounds #-}
56
57-- | Sorts the portion of the array delimited by [l,u) under the assumption
58-- that [l,m) is already sorted.
59sortByBounds' :: (PrimMonad m, MVector v e)
60              => Comparison e -> v (PrimState m) e -> Int -> Int -> Int -> m ()
61sortByBounds' cmp a l m u = sort m
62 where
63 sort i
64   | i < u     = do v <- unsafeRead a i
65                    insert cmp a l v i
66                    sort (i+1)
67   | otherwise = return ()
68{-# INLINE sortByBounds' #-}
69
70-- Given a sorted array in [l,u), inserts val into its proper position,
71-- yielding a sorted [l,u]
72insert :: (PrimMonad m, MVector v e)
73       => Comparison e -> v (PrimState m) e -> Int -> e -> Int -> m ()
74insert cmp a l = loop
75 where
76 loop val j
77   | j <= l    = unsafeWrite a l val
78   | otherwise = do e <- unsafeRead a (j - 1)
79                    case cmp val e of
80                      LT -> unsafeWrite a j e >> loop val (j - 1)
81                      _  -> unsafeWrite a j val
82{-# INLINE insert #-}
83