---TODO fmap
---TODO fmapRebuild

--------------------------------------------------------------------------------

-- | Builds an AABBTree from a list of elements with bounding boxes.
aaBBTreeBuild :: (HasBoundingBox a) => MaxDepth -> [a] -> AABBTree a
aaBBTreeBuild maxDepth xs = aaBBTreeBuildRec False 0 maxDepth xs
  where
    aaBBTreeBuildRec _ _ _ []                = AABBTreeEmpty
    aaBBTreeBuildRec _ _ _ [x]               = AABBTreeLeaf [x] (getBB x)
    aaBBTreeBuildRec compX depth maxDepth xs | done         = AABBTreeLeaf xs mergedBB
                                             | otherwise    = AABBTreeBranch (aaBBTreeBuildRec (not compX) (depth+1) maxDepth left)
                                                                             (aaBBTreeBuildRec (not compX) (depth+1) maxDepth right)
                                                                             mergedBB
      where
        done        = depth >= maxDepth
        mergedBB    = mconcat bbs
        bbs         = map getBB xs
        left        = filter (isLeft . getBB) xs
        right       = filter (isRight . getBB) xs
        splitPos    = centerBB mergedBB
        isLeft bb   = (dim $ bbMin bb) < dim splitPos
        isRight bb  = (dim $ bbMax bb) >= dim splitPos
        dim         | compX     = fst
                    | otherwise = snd

--------------------------------------------------------------------------------

-- | Finds all items of the tree which collide with the search item.
aaBBTreeBuild :: (HasBoundingBox a) => MaxDepth -> [a] -> AABBTree a
aaBBTreeBuild maxDepth xs = aaBBTreeBuildRec False 0 maxDepth xs
  where
    aaBBTreeBuildRec _ _ _ []                = AABBTreeEmpty
    aaBBTreeBuildRec _ _ _ [x]               = AABBTreeLeaf [x] (getBB x)
    aaBBTreeBuildRec compX depth maxDepth xs | done         = AABBTreeLeaf xs mergedBB
                                             | otherwise    = AABBTreeBranch (aaBBTreeBuildRec (not compX) (depth+1) maxDepth left)
                                                                             (aaBBTreeBuildRec (not compX) (depth+1) maxDepth right)
                                                                             mergedBB
      where
        done        = depth >= maxDepth
        mergedBB    = mconcat bbs
        bbs         = map getBB xs
        left        = filter (isLeft . getBB) xs
        right       = filter (isRight . getBB) xs
        splitPos    = centerBB mergedBB
        isLeft bb   = (dim $ bbMin bb) < dim splitPos
        isRight bb  = (dim $ bbMax bb) >= dim splitPos
        dim         | compX     = fst
                    | otherwise = snd

--------------------------------------------------------------------------------

-- | Finds all items of the tree which collide with the search item.
aaBBTreeBuild maxDepth xs = aaBBTreeBuildRec False 0 maxDepth xs
  where
    aaBBTreeBuildRec _ _ _ []                = AABBTreeEmpty
    aaBBTreeBuildRec _ _ _ [x]               = AABBTreeLeaf [x] (getBB x)
    aaBBTreeBuildRec compX depth maxDepth xs | done         = AABBTreeLeaf xs mergedBB
                                             | otherwise    = AABBTreeBranch (aaBBTreeBuildRec (not compX) (depth+1) maxDepth left)
                                                                             (aaBBTreeBuildRec (not compX) (depth+1) maxDepth right)
                                                                             mergedBB
      where
        done        = depth >= maxDepth
        mergedBB    = mconcat bbs
        bbs         = map getBB xs
        left        = filter (isLeft . getBB) xs
        right       = filter (isRight . getBB) xs
        splitPos    = centerBB mergedBB
        isLeft bb   = (dim $ bbMin bb) < dim splitPos
        isRight bb  = (dim $ bbMax bb) >= dim splitPos
        dim         | compX     = fst
                    | otherwise = snd

--------------------------------------------------------------------------------

-- | Finds all items of the tree which collide with the search item.