module QuadTree where

import GTypes

data QuadTree a = Empty Rect
                | Value Rect Point a
                | Partition Rect (QuadTree a) (QuadTree a) (QuadTree a) (QuadTree a)

instance Show a => Show (QuadTree a) where
    show qt = "(fromList "++ show (boundingRect qt) ++ " " ++ show (searchR (boundingRect qt) qt) ++ ")"

empty :: Rect -> QuadTree a
empty r = Empty r

boundingRect :: QuadTree a -> Rect
boundingRect (Empty r) = r
boundingRect (Value r _ _) = r
boundingRect (Partition r _ _ _ _) = r

insert :: Point -> a -> QuadTree a -> QuadTree a

insert p a (Empty r) = (Value r p a)

insert p a (Value r p' a')
    | p == p' = (Value r p a)            
    | otherwise = (insert p a.insert p' a') e
  where
    e = Partition r (Empty r1) (Empty r2) (Empty r3) (Empty r4)
    (r1,r2,r3,r4) = qsplit r

insert p@(x,y) a (Partition r q1 q2 q3 q4)
       | x < cx  && y < cy = (Partition r (insert p a q1) q2 q3 q4)
       | x >= cx && y < cy = (Partition r q1 (insert p a q2) q3 q4)
       | x < cx && y >= cy = (Partition r q1 q2 (insert p a q3) q4)
       | otherwise         = (Partition r q1 q2 q3 (insert p a q4))
  where
    (cx,cy) = centre r

fromList :: Rect -> [(Point,a)] -> QuadTree a
fromList r ps = foldr (\(p,a) q -> insert p a q) (empty r) ps

searchS :: Rect -> QuadTree a -> ([(Point,a)]->[(Point,a)])

searchS r (Empty _) = id

searchS r (Value r' p' a')
    | intersectR r r' = ((p',a'):)
    | otherwise = id

searchS r (Partition r' q1 q2 q3 q4)
    | intersectR r r' = (searchS r q1.searchS r q2.searchS r q3.searchS r q4)
    | otherwise = id

searchR :: Rect -> QuadTree a -> [(Point,a)]
searchR r qt = searchS r qt []


search :: Point -> QuadTree a -> Maybe a

search p (Empty _) = Nothing

search p (Value _ p' a)
    | p == p' = Just a
    | otherwise = Nothing

search p@(x,y) (Partition r q1 q2 q3 q4)
       | x < cx  && y < cy = search p q1
       | x >= cx && y < cy = search p q2
       | x < cx && y >= cy = search p q3
       | otherwise         = search p q4
  where
    (cx,cy) = centre r

size :: QuadTree a -> Int
size (Empty _) = 0
size (Value _ _ _) = 1
size (Partition _ q1 q2 q3 q4) = size q1 + size q2 + size q3 + size q4