module Chapter03 where
import Data.List (sortBy)

myLength :: [a] -> Int
myLength []     = 0
myLength (x:xs) = 1 + myLength xs

mean :: [Int] -> Float
mean [] = 0
mean xs = fromIntegral (sum xs) / fromIntegral (length xs)

makePalindrome :: [a] -> [a]
makePalindrome xs = xs ++ reverse xs

makePalindrome' :: [a] -> [a]
makePalindrome' xs = xs ++ tail (reverse xs)

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == reverse xs

lengthSort :: [[a]] -> [[a]]
lengthSort xs = sortBy lengthOrder xs
    where lengthOrder x1 x2 
              | length x1 < length x2 = LT
              | length x1 > length x2 = GT
              | otherwise             = EQ
                                      

intersperse :: a -> [[a]] -> [a]
intersperse _ []         = []
intersperse _ [xs]       = xs
intersperse sep (xs:xss) = xs ++ [sep] ++ intersperse sep xss

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

height :: Tree a -> Int
height Empty = 0
height (Node x y z) = 1 + maxHeight
    where 
      maxHeight 
        | left >= right  = left
        | otherwise      = right
      left  = height y
      right = height z

data Direction = LeftTurn | RightTurn | Straight 
                 deriving (Eq, Show)
type Point     = (Double, Double)

{-  From http://en.wikipedia.org/wiki/Graham_scan

For three points (x1,y1), (x2,y2) and (x3,y3), simply compute the direction of the cross product
  of the two vectors defined by points (x1,y1), (x2,y2) and (x1,y1), (x3,y3), characterized
  by the sign of the expression (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1). 
  If the result is 0, the points are collinear; 
  if it is positive, the three points constitute a "left turn", 
  otherwise a "right turn".
-}
direction :: Point -> Point -> Point -> Direction
direction (x1, y1) (x2, y2) (x3, y3)
     | cross < 0  = RightTurn
     | cross > 0  = LeftTurn
     | otherwise  = Straight
     where 
       cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

directions :: [Point] -> [Direction]
directions ps
    | points < 3  = []
    | otherwise   = direction a b c : directions (tail ps)
    where
      points = length ps
      a = head ps
      b = head (tail ps)
      c = head (tail (tail ps))


{-
The first step in this algorithm is to find the point with the lowest y-coordinate. 
If there is a tie, the point with the lowest x-coordinate out of the tie breaking candidates should be chosen.
 Call this point P. This step takes O(n), where n is the number of points in question.
-}

-- initialPort holds all the original points with P as the first member
initialSort :: [Point] -> [Point]
initialSort ps = foldr pointLess [head ps] (tail ps)
    where
      pointLess (x1,y1) (min:ps)
          | y1 < miny = (x1,y1):min:ps
          | y1 > miny = min:(x1,y1):ps
          | x1 < minx = (x1,y1):min:ps
          | otherwise = min:(x1,y1):ps
          where 
            minx = fst min
            miny = snd min
          
{-
Given min and 2 points p q
the smallest angle min-p or min-q is found by 
calculating the cotangent min->p and min->q 
cotan = opp/adj

cot min-p = opp min-p / adj min-p
cot min-q = opp min-q / adj min-q

cot min-p > cot min-q 
=> opp min-p / adj min-p > opp min-q / adj min-q
=> opp min-p * adj min-q > opp min-q * adj min-p

opp p = py - miny
adj p = px - minx

-}
cotanSort :: [Point] -> [Point]
cotanSort ps = initialPoint : sortBy cotanCompare remainingPoints
    where 
      initialSorting = initialSort ps
      initialPoint = head initialSorting
      remainingPoints = tail initialSorting
      (pivotx,pivoty) = initialPoint
      cotanCompare (px,py) (qx,qy)
          | pCalc > qCalc = GT
          | pCalc < qCalc = LT
          | py > qy       = LT
          | py < qy       = GT
          | px < qx       = LT
          | px > qx       = GT
          | otherwise     = EQ
          where 
            pCalc = (py-pivoty)*(qx-pivotx)
            qCalc = (qy-pivoty)*(px-pivotx)

grahamScan :: [Point] -> [Point]
grahamScan ps 
    | length ps < 3 =  error "grahamScan requires at least 3 points"
    | otherwise     = contiguousLeftTurns initialHull remainingPoints
    where 
      clockwisePoints = cotanSort ps
      remainingPoints = drop 3 clockwisePoints
      initialHull     = reverse (take 3 clockwisePoints)

{- 
The hull is formed by the set of points that form contiguous left turns.
  Progressively scan the points maintaining the current set of points in the hull
  When with the last 2 points added to the hull form a right turn with the next point
   backtrack by discarding the last point added to the hull
  When a straignt line or left turn is found
-}
contiguousLeftTurns :: [Point] -> [Point] -> [Point]
contiguousLeftTurns hull [] = reverse hull
contiguousLeftTurns (h1:h2:hs) (p:ps) 
    | rightTurn = contiguousLeftTurns (h2:hs) (p:ps) 
    | otherwise = contiguousLeftTurns (p:h1:h2:hs) ps
    where 
      rightTurn = direction h2 h1 p == RightTurn

testPoints :: [Point]
testPoints = [(0.0,0.0),  (3.0,-10.0), (-3.0,-4.0), (-7.0,-1.0), 
              (-7.0,1.0), (-3.0,4.0),  (3.0,7.0),   (5.0, 0.0)]

gridTest :: [Point]
gridTest = [(0.0,0.0), (2.0,0.0), (4.0,0.0), (6.0,0.0),
 (1.0,1.0), (3.0,1.0), (5.0,1.0),
 (0.0,2.0), (2.0,2.0), (4.0,2.0), (6.0,2.0),
 (1.0,3.0), (3.0,3.0), (5.0,3.0),
 (0.0,4.0), (2.0,4.0), (4.0,4.0), (6.0,4.0),
 (1.0,5.0), (3.0,5.0), (5.0,5.0),
 (0.0,6.0), (2.0,6.0), (4.0,6.0), (6.0,6.0) ]