module GrahamScan where
import Test.QuickCheck
import Data.List

type Point           = (Double, Double)
data Direction       = LeftDir
                     | RightDir
                     | Straight
                     deriving (Eq, Show)

-- sample values
---------------------------
pa = (2.0, 2.0)
pb = (6.0, 3.0)
pc = (3.0, 4.0)
pd = (4.0, 5.0)
pe = (1.0, 5.0)
pf = (3.0, 3.0)
pg = (4.0, 7.0)
ph = (6.0, 7.0)
pj = (5.0, 2.0)
givenList  = [pa,pb,pc,pd,pe,pf]
givenList2 = [pa,pb,pc,pd,pe,pf,pg]
givenList3 = [pa,pb,pc,pd,pe,pf,pg,ph]
givenList4 = [pa,pb,pc,pd,pe,pf,pg,ph,pj]

signToDir             :: Double -> Direction
signToDir n | n >  0  =  RightDir
            | n <  0  =  LeftDir
            | n == 0  =  Straight

direction             :: (Point, Point, Point) -> Direction
direction ((x1,y1),(x2,y2),(x3,y3)) = signToDir ((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1))

group3                :: [a] -> [(a,a,a)]
group3  xs | length xs < 3 = []
           | otherwise     = zip3 xs (tail xs) (tail $ tail xs)

dirList               :: [Point] -> [Direction]
dirList ps | length ps < 3 = []
           | otherwise     = map direction (group3 ps)

-- order of Point
ordPoint              :: Point -> Point -> Ordering
ordPoint (x1,y1) (x2,y2) | x1 == x2 && y1 == y2 = EQ
                         | y1 < y2              = LT
                         | y1 == y2 && x1 <  x2 = LT
                         | otherwise            = GT

getPivot              :: [Point] -> Point
getPivot              =  minimumBy ordPoint

-- cosin of two Points
mycos                 :: Point -> Point -> Double
mycos (x1,y1) (x2,y2) =  (x2 - x1)/sqrt((x2-x1)^2+(y2-y1)^2)

-- order of p1 p2 based on p
ordCosPoint           :: Point -> Point -> Point -> Ordering
ordCosPoint p p1 p2 | mycos p p1 == mycos p p2  = EQ
                    | mycos p p1 >  mycos p p2  = GT
                    | otherwise                 = LT

-- sort given List of Points by cosin based on pivot
-- result begins with pivot
sortedList              :: [Point] -> [Point]
sortedList ps           =  p:(sortBy (ordCosPoint p) (filter (/= p) ps))
                           where p = getPivot ps

-- utility function for graham scan
-- add means
---- 'adding a point (x) from sortedList
----  to the candidates list of convex hull (xs)
----  as far as this adding does not violate the condition given by p (ifNotRight),
----  otherwise, regenerate the candidates list of convex hull.'
add                    :: ((a,a,a) -> Bool) -> [a] -> a -> [a]
add p xs x
       | length xs < 2 =  (x:xs)
add p (x1:x0:[]) x
       | p (x, x0, x1) =  [x, x1, x0]
       | otherwise     =  [x, x0]
add p (x1:x0:xs) x
       | p (x, x0, x1) =  (x:x1:x0:xs)
       | otherwise     =  add p (x0:xs) x

ifNotRight            :: (Point, Point, Point) -> Bool
ifNotRight ps         =  direction ps /= RightDir

-- graham scan
gS                    :: [Point] -> [Point]
gS                    =  foldl' (add ifNotRight) []

gScan                        :: [Point] -> [Point]
gScan ps | length ps <= 3    = ps
         | otherwise         = gS $ sortedList ps

-- result check
isConvex                     :: [Point] -> Bool
isConvex ps | length ps <= 3 =  True
            | otherwise      =  all (/= LeftDir) (dirList ps)

prop_gScan ps = isConvex $ gScan ps
       where types = ps::[Point]

{-
exec check like this:

GHCi> quickCheck prop_gScan

then, you will get a result like below ;-)
+++ OK, passed 100 tests.

-}