Tarefa 8 - Base de cidades

Prazo de entrega:
Segunda chance:
Esta tarefa tem peso 4.

Implemente um banco de dados geográfico que permite cadastrar cidades, bem como buscar pontos de interesse em uma região. Para fazer isso eficientemente, você irá utilizar uma árvore quaternária.


Até então, temos estudado mecanismos que facilitam acesso de informações baseados em uma chave de busca (como filas de prioridades e árvores binárias de busca). Entretanto, é comum a existência de entradas multidimensionais, isto é, cada registro possui múltiplos campos que podem ser utilizados como chaves de uma busca. Isso ocorre, por exemplo, quando guardamos pontos de um espaço multidimensional, em que cada coordenada é um campo da estrutura que representa um ponto. Esses tipos de dados aparecem em diversas aplicações de banco de dados, computação gráfica, geometria computacional, processamento de imagens, etc.

Para ilustrar, imagine uma base de dados que armazena cidades e, para cada uma, as coordenadas do ponto associado no mapa. Nessa base de dados, deve ser possível pesquisar qual cidade está mais próxima de um determinado ponto. Uma maneira de se armazenar esses dados é guardar os pontos associados às cidades em um vetor ou uma lista ligada, sem nenhuma outra organização. Para buscar uma determinada cidade nessa estrutura de dados, no entanto, seria necessário percorrer todos os pontos cadastrados, acessando as coordenadas de cada um.

Árvores quaternárias

É possível melhorar a implementação da base de dados utilizando uma estrutura de dados mais sofisticada para armazenar os pontos. Vamos estudar árvores quaternárias de busca, que são semelhantes às árvores binárias de busca, mas lidam com entradas de duas dimensões. Nesta tarefa, as entradas correspondem às coordenadas x e y dos pontos (não serão feitas buscas pelo nome da cidade).

Com árvores binárias de busca, dividimos o espaço das entradas correspondente a um nó da árvore em dois espaços menores: um com entradas menores do que a chave e outro com entradas maiores do que a chave. Com árvores quaternárias, dividiremos o espaço bidimensional de busca em quatro quadrantes de tamanhos iguais: noroeste do ponto central (NO), nordeste do ponto central (NE), sudoeste do ponto central (SO) e sudeste do ponto central (SE). Essa divisão é feita recursivamente até que se tenha apenas um ponto em cada quadrante. Assim, construímos uma árvore em que os nós internos representam uma região e que possui exatamente 4 nós filhos, cada um representando um dos quadrantes da região do nó pai. A figura abaixo mostra como é feita a subdivisão de uma área.

Nesta representação de árvores quaternárias, os pontos serão armazenados somente nos nós folha e os nós internos representam regiões que contém mais que um ponto. Desta forma, cada nó de uma árvore quaternária pode ser:

Busca

Para buscar um ponto em uma árvore quaternária, basta encontrar o quadrante da região que contém o ponto e realizar uma busca no filho associado recursivamente, até encontrar um nó folha. Quando o nó é uma folha, é fácil decidir se ele contém o ponto sendo buscado ou se o ponto não está na base de dados.

Mas as árvore quaternárias se destacam principalmente porque permitem encontrar eficientemente todos os pontos em uma região. Mais precisamente, queremos encontrar todos os pontos a distância até r de um ponto P, isso é, todos os pontos contidos no disco de raio r e de centro P. Realizar essa busca por região não é muito diferente da busca simples. Começando da raiz, temos que descobrir os quadrantes que interceptam o disco e continuar a busca recursivamente em cada um deles.

Inserção

Assim como nas árvores binárias, um novo elemento é sempre inserido em um nó folha e, também como nas árvores, é mais simples descrever a inserção como um algoritmo recursivo. Basta olhar para o nó raiz da árvore e analisar cada caso:

Para ilustrar, podemos observar a subdivisão do espaço conforme inserimos pontos de acordo com a ordem Chicago (35,42), Mobile (52,10), Toronto (62,77) e Buffalo (82,65).

A árvore resultante dessas inserções será:

Remoção

O processo de remoção para esta implementação de árvores quaternárias pode ser feito da seguinte forma: como cada ponto está armazenado em um nó folha ocupado, basta substituir esse nó por um nó folha vazio, sem fazer nenhum tipo de reorganização da árvore.

No entanto, pode ser que depois de removermos um ponto, um nó interno p passe a ter três filhos que são nós folha vazios e um filho q que é um nó folha ocupado. Nesse caso, a subdivisão representada pelo nó interno p torna-se desnecessária, então devemos substituir o nó p pelo nó q, liberando os nós que não são mais necessários. Por exemplo, se removermos o ponto associado a Buffalo na árvore acima, obteremos a seguinte árvore como resultado:

Tarefa

O objetivo deste trabalho é implementar uma base de dados que armazena cidades. O seu binário deverá se chamar cidades. Uma cidade é representada por um nome e por um ponto no mapa. A base de dado deve suportar as operações de inserção, remoção, busca por ponto e busca por região. Cada operação corresponde a uma linha da entrada, que inclui uma letra identificando a operação e os parâmetros, separados por espaços. As operações suportadas pela simulação são detalhadas abaixo:

  1. Inserção

    i <x> <y> <nome>
    

    Insere uma nova cidade no banco de dados. Você pode supor que o nome de cada cidade tem no máximo 10 caracteres e que as coordenadas do ponto são inteiros não negativos. Após realizada a inserção, deverá mostrar na saída uma mensagem na forma:

    Cidade <nome> inserida no ponto (<x>,<y>).
    
  2. Busca por ponto

    b <x> <y>
    

    Busca uma cidade associada ao ponto do banco de dados. Se o ponto for encontrado, deverá mostrar na saída uma mensagem na forma:

    Cidade <nome> encontrada no ponto (<x>,<y>).
    

    Se não houver cidade no banco, então deverá mostrar:

    Nenhuma cidade encontrada no ponto (<x>,<y>).
    
  3. Busca por região

    o <x> <y> <r>
    

    Busca todas as cidades cujos pontos estejam contidos no disco de raio r e de centro (x,y). Deve mostrar uma saída incluindo cada cidade encontrada, como no formato:

    Cidades a distancia <r> de (<x>,<y>): <nome1> <nome2> ...
    

    As cidades não precisam ser classificadas e podem ser listadas em qualquer ordem.

  4. Remoção

    r <x> <y>
    

    Remover a cidade associada ao ponto do banco de dados. Após realizada a remoção, deverá mostrar na saída uma mensagem na forma:

    Cidade <nome> removida do ponto (<x>,<y>).
    
  5. Impressão (opcional)

    p
    

    Realiza um percurso em pré-ordem da árvore atual. Para nós internos, imprima apenas a letra I; para nós folha vazios, imprima a letra V; e, para nós folha ocupados, imprima o nome da cidade e suas suas coordenadas como em Cidade (<x>, <y>). Por exemplo, se percorrermos a árvore da seção Inserir acima visitando os filhos na ordem NO, NE, SO, SE, teríamos uma árvore como:

    Arvore:
      I
      |
      +---V
      |
      +---I
      |   |
      |   +---Toronto (62,77)
      |   |
      |   +---V
      |   |
      |   +---V
      |   |
      |   +---Buffalo (82,65)
      |
      +---Chicago (35,42)
      |
      +---Mobile (52,10)
    

    Esta operação não é necessária para passar nos testes automáticos, mas implementá-la ou implementar uma versão simplificada dela pode ser útil para investigar a estrutura da árvore e descobrir bugs. Dependendo da implementação da árvore quaternária e da ordem com que os filhos de um nó são percorridos, a estrutura da árvore pode ser um pouco diferente. Não se preocupe em reproduzir este exemplo exatamente.

  6. Encerramento

    s
    

    Libera toda memória do banco de dados, mostra a mensagem abaixo e finaliza a execução.

    Sistema encerrado.
    

Entrada

A primeira linha da entrada contém um número inteiro w. Nesta tarefa, iremos considerar que todos os pontos do mapa estão no quadrado com um extremo na origem (0,0) e outro extremo no ponto (w,w). Cada uma das linhas seguintes corresponde a uma operação como descrita acima.

100
i 35 42 Chicago
i 52 10 Mobile
i 62 77 Toronto
i 82 65 Buffalo
b 62 77
r 82 65
b 82 65
i 82 65 Buffalo
o 80 75 20
p
s

Saída

Cada operação pode produzir uma ou mais linhas, conforme a descrição das operações acima.

Cidade Chicago inserida no ponto (35,42).
Cidade Mobile inserida no ponto (52,10).
Cidade Toronto inserida no ponto (62,77).
Cidade Buffalo inserida no ponto (82,65).
Cidade Toronto encontrada no ponto (62,77).
Cidade Buffalo removida do ponto (82,65).
Nenhuma cidade encontrada no ponto (82,65).
Cidade Buffalo inserida no ponto (82,65).
Cidades a distancia 20 de (80,75): Buffalo Toronto
Arvore:
  I
  |   
  +---V
  |   
  +---I
  |   |   
  |   +---Toronto (62,77)
  |   |   
  |   +---V
  |   |   
  |   +---V
  |   |   
  |   +---Buffalo (82,65)
  |   
  +---Chicago (35,42)
  |   
  +---Mobile (52,10)
Sistema encerrado.

Dicas

Um nó da árvore quaternária tem uma de três formas possíveis. Independentemente da forma, um nó guarda dados sobre a região do plano sendo representada, mas para cada forma precisamos também guardar dados diferentes que só fazem sentido para aquele tipo. Em situações como essa, um nó na memória precisa reservar espaço apenas para a maior forma, mas queremos garantir que os algoritmos lidem com cada uma delas separadamente.

Diversas linguagens de programação dão suporte para esse tipo estrutura e dão diferentes nomes para elas: variante, tipo soma, tipo disjunto, etc. Em C, não há suporte explícito para variantes, pelo menos não de forma segura, mas podemos implementar uma construção equivalente, que é conhecida como tagged union. Nesta construção, guardamos o tipo de um nó e acessamos os dados correspondentes apenas depois de checar explicitamente pelo tipo. Você não precisa utilizá-la nesta tarefa se não quiser, mas aprender sobre ela vai ser importante para o futuro. Veja um exemplo emprestado da Wikipedia que representa uma forma geométrica.

enum tipo_forma { Quadrado, Retangulo, Circulo };

typedef struct forma *p_forma;

struct forma {
    int centro_x;
    int centro_y;
    enum tipo_forma tipo;
    union {
        struct { int lado; };            /* Quadrado */
        struct { int largura, altura; }; /* Retangulo */
        struct { int raio; };            /* Circulo */
    };
};

void mover_direita(p_forma f, int distancia) {
    f->centro_x += distancia;
}

double calcular_area(p_forma f) {
    double area;
    switch(f->tipo) {
        case Quadrado:
            area = f->lado * f->lado;
            break;
        case Retangulo:
            area = f->largura * f->altura;
            break;
        case Circulo:
            area = 3.1415 * f->raio * f->raio;
            break;
        default:
            assert(false);
    }
    return area;
}

O campo enum tipo_forma define apenas um número inteiro de forma que Quadrado == 0, Retangulo == 1, Circulo == 2, mas é muito mais fácil escrever um símbolo do que se lembrar do número associado. O union reserva espaço apenas para o membro de maior tamanho (incluindo bytes de alinhamento quando necessário).

Critérios

O conjunto de cidades da base de dados deve ser representado por uma árvore quaternária de busca. As buscas por ponto e por região devem aproveitar a estrutura da árvore para completar as operações eficientemente. Por exemplo, a busca por um ponto não precisa percorrer todos os nós da árvore.