Block :: {top, left, width, height}

BlockTree :: {block: Block, children: [BlockTree]}

blockTreeOfBlocks :: [Block] -> BlockTree

size block = block.height * block.width

-- Predicate: checks if one block is within another
within block1 block2 =
    let beginX = block2.left
        beginY = block2.top
        endX   = beginX + block2.width
        endY   = beginY + block2.height
    in block1.top > beginY && (block1.top + block1.height) < endY
    && block1.left > beginX && (block1.left + block1.width) < endX

-- Gets all blocks within a given block fom a list
blocksWithin blocks block = filter (\b -> b `within` block) blocks

-- Predicate: checks if a block is a child of any of its siblings.
-- Complexity: O(n)
isIndependentFrom child siblings =
    and (map (\sibling -> not (child `within` sibling)) siblings)

-- Splits a list of blocks (all assumed to be children of a parent)
-- into immedate and non-indirect children of their parent.
-- The input list of blocks must be sorted by size. The two output lists will be sorted by size
-- (they are built in opposite order and we reverse them at the end).
-- Complexity: O(n^2). The worst case is when all children are immediate children of the parent,
-- as comparisons are done only against immediate children (since every non-immediate children is a child
-- of an immediate child).
let partitionChildren children =
    let partitionR children (immediates, nonImmediates) =
        case children of
            child :: rest -> if (child `isIndependentFrom` immediates)
                             then partitionR rest (child :: immediates, nonImmediates)
                             else partitionR rest (immediates, child :: nonImmediates)
            []            -> (reverse immediates, reverse nonImmediates)
    in partitionR children ([], [])


{-
 Takes a block, its immediate children, its non-immediate children, (both lists sorted by size) and builds a tree.
 The process used is as follows: For each child, we find the children of that child from
 the non-immediate children. This costs O(m), where m is the number of non-immediate children.
 Since the `blocksWithin` operation preserves sorting, we still have a sorted list.

 We then split the children of the child into its immediate and non-immediate children. As stated about
 the operation above, this also preserves sorting. This costs O(m^2).

 We are then able to do a recursive call for the child with its immediate and non-immediate children.
 The amount of recursive calls done further down will depend on how many immediate and non-immediate children
 there were. The more immediate children we find, the more expensive it becomes to split the immediate from
 the non-immediate children (the cost approaches O(m^2)) But if we have few immediate children, the
 cost approaches m. The number of levels in the recursion tree here will be greater the fewer immediate children
 we have, as the tree will have lower effective branching factor. When we have a lower branching factor,
 the complexity approaches n log n, where n is the number of immediate children plus the number of non-immediate
 children. If the branching factor is higher, the complexity becomes closer to the cost of partitioning the children,
 which in the worst case, where all blocks are children of a single parent, is (m^2) = (n^2).

 Therefore, the worst-case time complexity of this operation is O(n^2).
-}
blockTreeNode parent immediateChildrenBlocks nonImmediateChildrenBlocks =
    let childrenTrees = map (\child ->
            let childrenOfChild = (nonImmediateChildrenBlocks `blocksWithin` child)
                (immediateChildrenOfChild, nonImmediateChildrenOfChild) = partitionChildren childrenOfChild
            in blockTreeNode child immediateChildrenOfChild nonImmediateChildrenOfChild
        ) immediateChildrenBlocks
    in BlockTree parent childrenTrees

-- We start off by sorting the input list, taking the tree's root node and starting the recursive process.
-- This costs n log n + n^2 = O(n^2).
blockTreeOfBlocks blocks =
    let (root :: children) = blocks `sortBy` size
        (immediateChildren, nonImmediateChildren) = partitionChildren children
    in blockTreeNode root immediateChildren nonImmediateChildren