module QuadTree2 where

import GTypes

data QuadTree = Value Rect Bool
              | Partition Rect QuadTree QuadTree QuadTree QuadTree
   deriving (Show)

empty :: Rect -> QuadTree
empty r = Value r False

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

intersect :: Rect -> QuadTree -> Bool
intersect r (Value _ False) = False
intersect r (Value rq True) = intersectR r rq
intersect r (Partition rq q1 q2 q3 q4)
    | not (intersectR r rq) = False
    | otherwise = intersect r q1 || intersect r q2 || intersect r q2 || intersect r q3 || intersect r q4

insertCircle :: Int -> Circle -> QuadTree -> QuadTree

insertCircle depth c qt@(Value _ True) = qt

insertCircle 0 c qt@(Value r False)
    | intersectsCircle c r = (Value r True)
    | otherwise = qt
  

insertCircle depth c qt@(Value r False) = case circRect c r of
    OVERLAP -> Value r True
    INTERSECT -> insertCircle depth c empty
    NONE -> qt
  where
    cr = circRect c r
    empty = Partition r (Value r1 False) (Value r2 False) (Value r3 False) (Value r4 False)
    (r1,r2,r3,r4) = qsplit r

insertCircle depth c qt@(Partition r q1 q2 q3 q4)
    | (intersectsCircle c r) = Partition r (insertCircle depth1 c q1) (insertCircle depth1 c q2)
                                           (insertCircle depth1 c q3) (insertCircle depth1 c q4)
    | otherwise = qt
  where
    depth1 = depth-1