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

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

blockTreeOfBlocks :: [Block] -> BlockTree

let size block := block.height * block.width

let 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

let 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