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

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

blockTreeOfBlocks :: [Block] -> BlockTree

size block = block.height * block.width

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

blocksWithin blocks block = filter (\b -> b `within` block) blocks

-- determina se um bloco é filho de algum irmão.
-- complexidade: O(n)
let immediateChild child siblings =
    and (map (\sibling -> not (child `within` sibling)) siblings)

-- divide uma lista de blocos em filhos diretos (aqueles que não são filhos de nenhum irmão)
-- e filhos indiretos (aqueles que são). Esta função espera receber os blocos ordenados por tamanho
-- por questão de otimização (um bloco não pode ser filho de um bloco menor do que ele)
-- complexidade: O(n^2). O pior caso ocorre quando todos os blocos são filhos diretos.
let partitionChildren children =
    let partitionR children (immediates, nonImmediates) =
        case children of
            child :: rest -> if (child `immediateChild` immediates)
                             then partitionR rest (child :: immediates, nonImmediates)
                             else partitionR rest (immediates, child :: nonImmediates)
            []            -> (immediates, nonImmediates)
    in partitionR children ([], [])


{-
 recebe uma lista de blocos, uma lista de filhos diretos, e uma lista de filhos indiretos e monta
 uma árvore. Para cada um dos filhos diretos, são determinados quais estão ou não contidos naquele filho,
 e são divididos em filhos diretos e filhos indiretos para a nova chamada recursiva.

 A princípio, isso seria uma operação de custo N * M^2 sem contar a recursão,
 onde N é o número de filhos diretos
 e M o de filhos indiretos, mas quando o custo da operação de partição se aproxima de M^2 não há
 chamada recursiva (porque todos os filhos são diretos). Ou seja, se o número de filhos da árvore é
 alto, o custo em cada nível fica baixo e vice-versa. No caso de uma árvore binária, o custo fica
 N em cada nível * log N níveis, ou seja N log N, e no caso de uma árvore com apenas um nível,
 o custo tende a N^2. Nos casos intermediários, o custo fica entre N log N e N^2.
 Portanto, podemos concluir que a complexidade desta operação é O(N^2).
-}
let blockTreeNode parent immediateChildrenBlocks nonImmediateChildrenBlocks =
    let childrenTrees = map (\child ->
            let childrenOfChild = (nonImmediateChildrenBlocks `blocksWithin` child) `sortBy` size
                (immediateChildrenOfChild, nonImmediateChildrenOfChild) = partitionChildren childrenOfChild
            in blockTreeNode child immediateChildrenOfChild nonImmediateChildrenOfChild
        ) immediateChildrenBlocks
    in BlockTree parent childrenTrees

-- A função principal só inicia a recursão adicionando uma operação em tempo constante.
-- Portanto, a complexidade total é O(N^2)
let blockTreeOfBlocks blocks =
    let (parent :: children) = blocks `sortBy` size
        (immediateChildren, nonImmediateChildren) = partitionChildren children
    in blockTreeNode parent immediateChildren nonImmediateChildren