A azul (e indentadas uma vez) as respostas às questões.

Questão 1

Assinale com V (Verdadeiro) as expressões que estão correctas e com F (Falso) as que estão incorrectas.

Deve preencher todos os espaços indicados por um sublinhado (___) com V ou F. Qualquer espaço não preenchido será considerado como uma resposta errada.

Em geral as alíneas podem ter zero ou mais respostas correctas.  Cada resposta correctamente assinalada vale 0,5 valores.

Nas alíneas em que apenas uma resposta está correcta (se existirem estão assinaladas no texto), responder com mais ou menos do que um V anula a cotação.  A resposta correcta corresponde à cotação completa.  Qualquer outra resposta corresponde a zero valores.

Em todos os casos em que não é explicitamente referida a localização de uma instrução, considere que esta é dada na função main() do programa seguinte:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class A {
  public:
    int z;

    A(int const, int const = 1);

    int f1();
    int f2();
    int f3(int);

  private:
    vector<int> x;
    int f4();
};

...

int main()
{
    int const i = 1;
    A meu_a(2, 3);
    A const outro_a(2, 3);
    vector<int> v(1);
    v[0] = 3;
    ...
}

  F    A a;
  V    A a(2);
  V    A a(v[0], v[0]);

[cotação: 1,5]

O construtor de A tem um argumento inteiro obrigatório e um argumento inteiro opcional.

  F   int c = meu_a.x[2];
  F   i = meu_a.f4();

A::x e A::f4() são membros privados e portanto não podem ser acedidos a partir da função main(), pois esta não é membro nem amiga da classe A..

A::f1() é um método não-constante, i.e., não garante a não alteração da instância para o qual é invocado, e por isso não pode ser invocado através de uma constante.

A instrução está correcta.  Mas note: é muito má ideia que os atributos de uma classe sejam públicos!

[cotação: 2]

1.3  Assuma que as seguintes instruções são dadas dentro de uma função ou procedimento membro da classe A e que não são declaradas quaisquer variáveis ou constantes dentro dessa função ou procedimento (que não tem quaisquer parâmetros).  Quais das seguintes instruções estão correctas?

  F    v[0] = 1;
  F    x[0] = f4();

Não existe nenhum atributo de nome v na classe A. No segundo caso nada indica que A::x tenha pelo menos um item.  Por isso talvez se devesse ter usado x.push_back(f4()).

1.4  Suponha as seguintes definições dos métodos acima declarados:

A::A(int const i, int const n)
    : x(n), z(i)
{
}

void A::f2()
{
    for(vector<int>::size_type i = 0; i != x.size(); ++i)
        x[i] = z;
}

int A::f3(int const i)
{
    return x[i];
}

int main()
{
    A a(4, 5);
    cout << a.f3(2);
    a.f2();
    cout << ' ' << a.f3(3) << endl;
}

  F     5 4
  F     0 5
  V     0 4
  F     5 0

[cotação: 0,5] 

A construção da variável a leva a que o vector membro A::x seja construído com 5 itens de valor nulo (valor por omissão dos inteiros) e a variável membro A::z seja inicializada com o valor 4.  A invocação do método A::f3(), com argumento 2, devolve o valor do item de A::x na posição 2, que é 0.  A invocação do método A::f2() atribui o valor de A::z (que é 4) a todos os itens do vector A::x.  A invocação do método A::f3(), com argumento 3, devolve o valor do item de A::x na posição 3, que é 4.

Questão 2

Considere o problema da gestão dos navios que atracam no Porto de Lisboa para cargas e descargas.  Quando chega, um navio pede autorização para atracar, enviando para isso a sua informação (nome e matrícula) a um dos controladores do Porto de Lisboa.  Nesse momento é-lhe atribuído um cais livre (existem 10 cais de carga/descarga de mercadorias, numerados de 1 a 10, cada um dos quais suporta apenas um navio).  Caso não exista um cais disponível, o navio é colocado em fila de espera até que um dos cais seja libertado.  A fila de espera tem um limite de 50 navios (os que cabem no Mar da Palha).  Logo que um cais esteja disponível, o navio é autorizado a atracar e proceder à carga e descarga das mercadorias.  Quando termina a operação, o navio envia um aviso a um dos controladores do Porto de Lisboa indicando que  libertou o cais que lhe estava atribuído, o que poderá permitir a atracação de um navio em espera.  Pretende-se construir e testar uma parte do sistema de controlo do Porto de Lisboa.

2.1  Defina a classe RegistoDeNavio de modo a guardar:

1. O nome do navio.  Uma cadeia de caracteres sem espaços.
2. A matrícula do navio.  Uma cadeia de caracteres sem espaços.
3. O número do cais onde está a carregar/descarregar mercadoria.  Caso o navio não esteja em nenhum cais o valor desta variável deverá ser zero (0).

• Um construtor que constrói o registo de um navio dados o seu nome e a sua matrícula.  O registo assume que o navio não se encontra em nenhum cais.
• Um outro construtor que, além do nome e da matrícula, receba o cais de atracação do navio.  Admite-se o número do cais indicado é superior ou igual a um (pré-condição).
• Inspectores para o nome, a matrícula e o cais do registo.
• Um modificador que permita modificar o cais do registo.  O número do novo cais deve ser passado como argumento e admite-se superior ou igual a um (pré-condição).
• Um método que mostre no ecrã toda a informação sobre o registo de um navio.

Não é necessário nesta questão definir qualquer um dos métodos (funções ou procedimentos membro) da classe.

A interface desta classe é fundamental para as alíneas seguintes!

[cotação: 1]

Em cada uma das alíneas seguintes considere como completa a resolução das alíneas anteriores, mesmo que a não tenha realizado.

2.2  Considere a seguinte classe:

class ConjuntoDeRegistosDeNavios {
   public:
    ConjuntoDeRegistosDeNavios();

    RegistoDeNavio registoDeNavioComMatrícula(string const& matrícula) const;

    bool contémRegistoDeNavioComMatrícula(string const& matrícula) const;

    void mostra() const;

    void insere(RegistoDeNavio const& registo_de_navio);
    void removeRegistoDeNavioComMatrícula(string const& matrícula);

  private:
 
};

• ConjuntoDeRegistosDeNavios() constrói um novo conjunto (vazio) de registos de navios.
• RegistoDeNavio registoDeNavioComMatrícula(string const& matrícula) const devolve uma cópia do registo do navio do conjunto com a matrícula indicada, que se admite pertencer a algum dos registos no conjunto (pré-condição).
• bool contémRegistoDeNavioComMatrícula(string const& matrícula) const devolve verdadeiro se o conjunto contiver o registo de um navio com a matrícula dada.
• void mostra() const mostra no ecrã todos os registos de navios que se encontram no conjunto.
• void insere(RegistoDeNavio const& registo_de_navio) acrescenta um registo de navio a um conjunto, admitindo que não existe no conjunto nenhum outro registo com a mesma matrícula do registo passado como argumento (pré-condição).
• void removeRegistoDeNavioComMatrícula(string const& matrícula) remove do conjunto o registo do navio com a matrícula indicada, que se admite pertencer a algum dos registos no conjunto (pré-condição).

• void ConjuntoDeRegistosDeNavio::insere(RegistoDeNavio const& registo_de_navio)
• void ConjuntoDeRegistosDeNavio::removeRegistoDeNavioComMatrícula(string const& matrícula)

[cotação: 2]

2.3  Considere a seguinte classe:

class FilaDeRegistosDeNavios {
   public:
    FilaDeRegistosDeNavios();

    RegistoDeNavio primeiro() const;

    bool contémRegistoDeNavioComMatrícula(string const& matrícula) const;

    bool vazia() const;
    bool cheia() const;

    void mostra() const;

    int comprimento() const;

    void põe(RegistoDeNavio const& registo_de_navio);
    void tira();

  private:
 
};

• FilaDeRegistosNavios() constrói uma nova fila (vazia) de registos de navios.
• RegistoDeNavio primeiro() const devolve uma cópia do registo do navio que está na frente da fila, admitindo-se que a fila não está vazia (pré-condição).
• bool contémRegistoDeNavioComMatrícula(string const& matrícula) const devolve verdadeiro se a fila contiver o registo de um navio com a matrícula dada.
• bool vazia() const devolve verdadeiro se a fila estiver vazia.
• bool cheia() const devolve verdadeiro se a fila estiver cheia.
• void mostra() const mostra no ecrã todos os registos de navios que se encontram na fila.
• int comprimento() const devolve o número de registos de navios que se encontram na fila.
• void põe(RegistoDeNavio const& registo_de_navio) acrescenta um registo de navio a uma fila, admitindo-se que não existe na fila nenhum outro registo com a mesma matrícula do registo passado como argumento e que a fila não está cheia (pré-condição).
• void tira() remove o primeiro registo de navio da fila, que se admite não estar vazia (pré-condição).

• RegistoDeNavio primeiro() const devolve uma cópia do registo do navio que está na frente da fila, admitindo-se que a fila não está vazia (pré-condição).
• bool vazia() const devolve verdadeiro se a fila estiver vazia.
• void põe(RegistoDeNavio const& registo_de_navio) acrescenta um registo de navio a uma fila, admitindo que não existe na fila nenhum outro registo com a mesma matrícula do registo passado como argumento e que a fila não está cheia (pré-condição).
• void tira() remove o primeiro registo de navio na fila, que se admite não estar vazia (pré-condição).

[cotação: 2]

2.4  Defina a classe ControladorDoPorto que representa e controla o estado do porto em cada instante de tempo.  Deve incluir os métodos necessários para:

1. Construir uma nova variável do tipo ControladorDoPorto dado o número de cais do porto em questão (e.g. 10).
2. Registar a chegada de um navio (sendo a informação sobre o navio dada como argumento na forma de um registo de navio).  Admite-se que a matrícula do navio chegado é diferente de todos os outros navios em causa, incluindo os que estão nos cais e os que estão em espera (pré-condição).  Se houver lugar num cais, o navio é autorizado a atracar nele.  Se não houver lugar, o navio deve ficar em espera.  Se não houver espaço para o navio esperar, nada deve acontecer (ou seja, o navio é mandado embora).
3. Registar a partida de um navio que se encontrava num cais (recebe a  matrícula do navio que está de partida).  Admite-se que existe um navio num cais com a matrícula dada (pré-condição).  Se existirem navios em espera, o primeiro da fila tem ordem para entrar no porto e atracar no cais que foi libertado.
4. Verificar se há algum cais disponível ou não.
5. Verificar se há espaço no porto, quer em algum cais quer na fila de espera.
6. Devolver o número de navios na fila de espera.
7. Mostrar todos os navios na fila de espera.
8. Mostrar todos os navios que se encontram atracados.
9. Verificar se um navio com uma matrícula dada se encontra atracado.
10. Verificar se um navio com uma matrícula dada se encontra na fila à espera de atracar.

Faça uso das classes FilaDeRegistosDeNavios e ConjuntoDeRegistosDeNavio para guardar os navios em espera e os navios atracados, respectivamente.

Não é necessário nesta questão definir qualquer um dos métodos.  Coloque comentários indicando claramente para que serve cada uma das variáveis membro que definir.

[cotação: 2]

2.5  Defina os seguintes métodos da classe ControladorDoPorto:

1. Construir uma nova variável do tipo ControladorDoPorto dado o número de cais do porto em questão (e.g. 10).
2. Registar a partida de um navio que se encontrava num cais (recebe a  matrícula do navio que está de partida).  Admite-se que existe um navio num cais com a matrícula dada (pré-condição).  Se existirem navios em espera, o primeiro da fila tem ordem para entrar no porto e atracar no cais que foi libertado.
3. Verificar se um navio com uma matrícula dada se encontra atracado.

2.6  Escreva um programa que simule o funcionamento do Porto de Lisboa.  Admita que no início não existem navios atracados ou em fila de espera.  O programa deve mostrar ao utilizador um menu que permita as seguintes operações:

1. Registar a chegada de um navio.  Deve pedir ao utilizador para inserir toda a informação sobre um navio e registar a entrada desse navio.  Se a matrícula já existir quer em algum cais quer em espera, deve simplesmente avisar o utilizador.  Caso não haja lugar nem em cais nem em fila, deve simplesmente avisar o utilizador.
2. Registar a partida de um navio de um cais.  Deve pedir ao utilizador a matrícula do navio a retirar (o que tem como consequência a atracagem do primeiro navio em espera, se existir algum).  Se não houver nenhum barco com a matrícula indicada, deve simplesmente avisar o utilizador.
3. Mostrar todos os navios que se encontram atracados e em fila de espera.

Exemplo de interacção:

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 1

Qual o nome do navio? Maria_das_Ondas
Qual a matrícula? 123sq45

Navio registado.  Atracagem permitida.

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 3

Navios em cais:

Cais 1: Maria_das_ondas (123sq45)
Cais 3: Xpto (123xpto45)
Cais 2: Titanic (ko123)
Cais 4: Gingão (g8932g)
Cais 6: USS_George_Bush (123gb)
Cais 5: HMS_Sheakspeare (123sh)
Cais 8: FaraoDosMares (345ty9)
Cais 9: Solha (sub.pt1)
Cais 10: CacilheiroPerdido (TT456)
Cais 7: NaoVaiAoFundo (sub.pt2)

Navios em espera:

LixoDoMar (petro$$$)
ZeZe_dos_Oceanos (123456)
 

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 2

Qual a matrícula? sub.pt3

Não está atracado nenhum navio com essa matrícula.
 

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 2

Qual a matrícula? sub.pt2

Registo de partida efectuado.

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 3

Navios em cais:

Cais 1: Maria_das_ondas (123sq45)
Cais 3: Xpto (123xpto45)
Cais 2: Titanic (ko123)
Cais 4: Gingão (g8932g)
Cais 6: USS_George_Bush (123gb)
Cais 5: HMS_Sheakspeare (123sh)
Cais 8: FaraoDosMares (345ty9)
Cais 9: Solha (sub.pt1)
Cais 10: CacilheiroPerdido (TT456)
Cais 7: LixoDoMar (petro$$$)

Navios em espera:

ZeZe_dos_Oceanos (123456)
 

Controlador do Porto De Lisboa

1. Registar entrada
2. Registar partida
3. Mostrar situação do porto
Opção: 1

Nome do navio: ReiDosMares
Matrícula: 345ty9

Um navio com essa matrícula já se encontra no porto!

Resolução de todas as alíneas da pergunta 2 (partes deste programa não sáo pedidos em qualquer alínea e por isso não era necessário dar uma resposta tão completa quanto esta).  A negrito as partes correspondentes a respostas ao enunciado.

#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

/** Representa registos de navios que podem estar atracados em cais de
    um porto.
    @invariant 0 <= numero_do_cais. */
class RegistoDeNavio {
  public:
    /** Existe um construtor por omissão por razões técnicas apenas.
        Nomeadamente para ser possível definir um vector ou uma matriz
        de registos sem inicialização explícita.  Há melhores soluções
        para este problema, mas exigem matéria mais avançada. */
    RegistoDeNavio();

    /** Controi registo de navio que não está em cais.
        @pre V. */
    RegistoDeNavio(string const& nome, string const& matricula);

    /** Controi registo de navio num determinado número de cais.
        @pre 0 < numero_do_cais. */
    RegistoDeNavio(string const& nome, string const& matricula,
                   int numero_do_cais);

    /// Devolve nome do navio.
    string nome() const;

    /// Devolve matricula do navio.
    string matricula() const;
 
    /// Indica se o navio está num cais.
    bool estaEmCais() const;
 
    /** Devolve o número do cais onde o navio se encontra atracado.
        @pre estaEmCais(). */
    int numeroDoCais() const;
 
    /// Mostra informação sobre o registo.
    void mostra() const;
 
    /** Muda cais onde o navio se encontra atracado.
        @pre ¬estaEmCais() e 0 < numero_do_cais_.
        @post numeroDoCais() == numero_do_cais_ */
    void colocaEmCaisNumero(int numero_do_cais_);
 
  private:
    string nome_;
    string matricula_;
    int numero_do_cais;

    bool cumpreInvariante() const;
};

RegistoDeNavio::RegistoDeNavio()
    : numero_do_cais(0)
{
    assert(cumpreInvariante());
}

RegistoDeNavio::RegistoDeNavio(string const& nome, string const& matricula)
    : nome_(nome),
      matricula_(matricula),
      numero_do_cais(0)
{
    assert(cumpreInvariante());
}

RegistoDeNavio::RegistoDeNavio(string const& nome, string const& matricula,
                               int const numero_do_cais)
    : nome_(nome),
      matricula_(matricula),
      numero_do_cais(numero_do_cais)
{
    assert(0 < numero_do_cais);

    assert(cumpreInvariante());
}

string RegistoDeNavio::nome() const
{
    assert(cumpreInvariante());

    return nome_;
}

string RegistoDeNavio::matricula() const
{
    assert(cumpreInvariante());

    return matricula_;
}

bool RegistoDeNavio::estaEmCais() const
{
    assert(cumpreInvariante());

    return 0 < numero_do_cais;
}

int RegistoDeNavio::numeroDoCais() const
{
    assert(cumpreInvariante());

    return numero_do_cais;
}

void RegistoDeNavio::mostra() const
{
    assert(cumpreInvariante());

    if(numeroDoCais() != 0)
        cout << "Cais " << numeroDoCais() << ": ";
    cout << nome_ << " " << matricula() << endl;
}

void RegistoDeNavio::colocaEmCaisNumero(int const numero_do_cais_)
{
    assert(cumpreInvariante());
    assert(not estaEmCais() and 0 < numero_do_cais_);

    numero_do_cais = numero_do_cais_;

    assert(numeroDoCais() == numero_do_cais_);
    assert(cumpreInvariante());
}

bool RegistoDeNavio::cumpreInvariante() const
{
    return 0 <= numero_do_cais;
}
 

/** Representa conjuntos de registos de navios.
    @invariant Todos os registos têm matrículas diferentes. */
class ConjuntoDeRegistosDeNavios
{
  public:
    /* Omitiu-se o construtor por omissão pois o construtor fornecido
       pelo C++ é suficiente. */

    /** Devolve registo do navio com a matrícula dada.
        @pre contemRegistoDeNavioComMatricula(matricula).
        @post registoDeNavioComMatricula.matricula() == matricula. */
    RegistoDeNavio registoDeNavioComMatricula(string const& matricula) const;

    /// Indica se o conjunto contém um registo de navio com a matrícula dada.
    bool contemRegistoDeNavioComMatricula(string const& matricula) const;

    /// Mostra todos os registos contidos no conjunto.
    void mostra() const;

    /** Insere um novo registo de navio no conjunto.
        @pre ¬contemRegistoDeNavioComMatricula(
        registo_de_navio.matricula()). */
    void insere(RegistoDeNavio const& registo_de_navio);

    /** Remove um registo de navio do conjunto dada a sua matrícula.
        @pre contemRegistoDeNavioComMatricula(matricula). */
    void removeRegistoDeNavioComMatricula(string const& matricula);

  private:
    vector<RegistoDeNavio> registos_de_navios;

    /** Método auxiliar devolvendo o índice no vector do registo com
        uma dada matrícula.  Devolve a dimensão do vector no caso de a
        matrícula não existir.
        @pre V.
        @post (¬(E i : 0 <= i < registo_de_navios.size() :
                 registo_de_navios[i].matricula() = matricula) e
               indiceDeRegisto = registo_de_navios.size()) ou
              (0 <= indiceDeRegisto < registo_de_navios.size() e
               registo_de_navios[indiceDeRegisto].matricula() = matricula). */
    vector<RegistoDeNavio>::size_type
    indiceDeRegisto(string const& matricula) const;

    bool cumpreInvariante() const;
};

RegistoDeNavio ConjuntoDeRegistosDeNavios::
registoDeNavioComMatricula(string const& matricula) const
{
    assert(cumpreInvariante());
    assert(contemRegistoDeNavioComMatricula(matricula));

    return registos_de_navios[indiceDeRegisto(matricula)];
}
 
bool ConjuntoDeRegistosDeNavios::contemRegistoDeNavioComMatricula(
    string const& matricula) const
{
    assert(cumpreInvariante());

    return indiceDeRegisto(matricula) != registos_de_navios.size();
}
 
void ConjuntoDeRegistosDeNavios::mostra() const
{
    assert(cumpreInvariante());

    for(vector<RegistoDeNavio>::size_type i = 0;
        i != registos_de_navios.size(); ++i)
        registos_de_navios[i].mostra();
}
 
void ConjuntoDeRegistosDeNavios::insere(
    RegistoDeNavio const& registo_de_navio)
{
    assert(cumpreInvariante());
    assert(not contemRegistoDeNavioComMatricula(
               registo_de_navio.matricula()));

    registos_de_navios.push_back(registo_de_navio);

    assert(cumpreInvariante());
}

void ConjuntoDeRegistosDeNavios::removeRegistoDeNavioComMatricula(
    string const& matricula)
{
    assert(cumpreInvariante());
    assert(contemRegistoDeNavioComMatricula(matricula));

    registos_de_navios[indiceDeRegisto(matricula)] = registos_de_navios.back();
    registos_de_navios.pop_back();

    assert(cumpreInvariante());
}

vector<RegistoDeNavio>::size_type
ConjuntoDeRegistosDeNavios::indiceDeRegisto(string const& matricula) const
{
    vector<RegistoDeNavio>::size_type indice_de_registo = 0;
    while(indice_de_registo != registos_de_navios.size() and
          matricula != registos_de_navios[indice_de_registo].matricula())
        ++indice_de_registo;
    return indice_de_registo;
}

bool ConjuntoDeRegistosDeNavios::cumpreInvariante() const
{
    for(vector<RegistoDeNavio>::size_type i = 0;
        i != registos_de_navios.size(); ++i)
        for(vector<RegistoDeNavio>::size_type j = i + 1;
            j != registos_de_navios.size(); ++j)
            if(registos_de_navios[i].matricula() ==
               registos_de_navios[j].matricula())
                return false;
    return true;
}
 

/** Representa filas de registos de navios.  As filas têm uma dimensão
    máxima fixa em tempo de compilação.  De momento o limite são 50
    registos.

    @invariant Todos os registos têm matrículas diferentes e
    0 <= primeiro_ < dimensao e
    0 <= comprimento_ <= dimensao. */
class FilaDeRegistosDeNavios {
  public:
    /// Constrói uma fila vazia.
    FilaDeRegistosDeNavios();

    /** Devolve o primeiro registo de navio na (frente da) fila.
        @pre ¬estaVazia(). */
    RegistoDeNavio primeiro() const;

    // Os nomes forma alterados para serem mais legíveis.

    /// Indica se a fila está vazia.
    bool estaVazia() const;

    /// Indica se a fila está cheia.
    bool estaCheia() const;

    /** Devolve o comprimento da fila, i.e., o número de registos que
        contém. */
    int comprimento() const;

    /// Indica se a fila contém algum registo de navio com a matrícula dada.
    bool contemRegistoDeNavioComMatricula(string const& matricula) const;
 
    /// Mostra todos os registos de navios na fila, por ordem de entrada.
    void mostra() const;
 
    /** Acrescenta um novo registo de navio ao fim da fila.
        @pre ¬estaCheia() e
        ¬contemRegistoDeNavioComMatricula(
        registo_de_navio.matricula()).
        @post ¬estaVazia(). */
    void poe(RegistoDeNavio const& registo_de_navio);

    /** Retira o registo de navio na frente da fila.
        @pre ¬estaVazia().
        @post ¬estaCheia(). */
    void tira();
 
  private:
    static int const dimensao = 50;

    RegistoDeNavio registos_de_navios[dimensao];
    int comprimento_;
    int primeiro_;

    /** Converte a indexação natura (em que 0 corresponde ao item na frente
        da fila) na indexação real.
        @pre 0 <= i <= comprimento(). */
    int indice(int i) const;

    bool cumpreInvariante() const;
};
 
FilaDeRegistosDeNavios::FilaDeRegistosDeNavios()
    : comprimento_(0), primeiro_(0)
{
    assert(cumpreInvariante());
}

RegistoDeNavio FilaDeRegistosDeNavios::primeiro() const
{
    assert(cumpreInvariante());
    assert(not estaVazia());

    return registos_de_navios[indice(0)];
}

bool FilaDeRegistosDeNavios::estaVazia() const
{
    assert(cumpreInvariante());

    return comprimento() == 0;
}

bool FilaDeRegistosDeNavios::estaCheia() const
{
    assert(cumpreInvariante());

    return comprimento() == dimensao;
}
 
int FilaDeRegistosDeNavios::comprimento() const
{
    assert(cumpreInvariante());

    return comprimento_;
}
 
bool FilaDeRegistosDeNavios::
contemRegistoDeNavioComMatricula(string const& matricula) const
{
    assert(cumpreInvariante());

    int i = 0;
    while(i != comprimento() and
          matricula != registos_de_navios[indice(i)].matricula())
        ++i;

    return i != comprimento();
}
 
void FilaDeRegistosDeNavios::mostra() const
{
    assert(cumpreInvariante());

    for(int i = 0; i != comprimento(); ++i)
        registos_de_navios[indice(i)].mostra();
}
 
void FilaDeRegistosDeNavios::poe(RegistoDeNavio const& registo_de_navio)
{
    assert(cumpreInvariante());
    assert(not contemRegistoDeNavioComMatricula(registo_de_navio.matricula())
           and not estaCheia());

    registos_de_navios[indice(comprimento_++)] = registo_de_navio;

    assert(not estaVazia());
    assert(cumpreInvariante());
}

void FilaDeRegistosDeNavios::tira()
{
    assert(cumpreInvariante());
    assert(not estaVazia());

    primeiro_ = indice(1);
    --comprimento_;

    assert(not estaCheia());
    assert(cumpreInvariante());
}

int FilaDeRegistosDeNavios::indice(int const i) const
{
    assert(0 <= i and i <= comprimento_);

    return (primeiro_ + i) % dimensao;
}

bool FilaDeRegistosDeNavios::cumpreInvariante() const
{
    if(not (0 <= primeiro_ and primeiro_ < dimensao and
            0 <= comprimento_ and comprimento_ <= dimensao))
        return false;
    for(int i = 0; i != comprimento_; ++i)
        for(int j = i + 1; j != comprimento_; ++j)
            if(registos_de_navios[indice(i)].matricula() ==
               registos_de_navios[indice(j)].matricula())
                return false;
    return true;
}
 
/** Representa um controlador de um porto.

    @invariant Não há matriculas repetidas.  Os registos de navios em
    espera não têm cais.  O registos de navios atracados têm cais.
    Os cais registados nos navios atracados são coerentes com os
    cais ocupados (indicados pelo vector cais_ocupados). */
class ControladorDoPorto {
  public:
    /** Constrói um novo controlador para um porto com um dado
        número de cais.
        @pre 0 < numero_de_cais. */
    ControladorDoPorto(int numero_de_cais);

    /// Indica se há cais livres no porto.
    bool haCaisLivre() const;

    /// Indica se há espaço para navios em espera.
    bool haEspacoEmEspera() const;

    /// Indica se à espaço no porto, quer em cais quer em espera.
    bool haEspacoNoPorto() const;

    /// Mostra o estado do porto.
    void mostra() const;

    /** Indica se existe algum registo de navio atracado com a
        matrícula dada. */
    bool contemRegistoDeNavioAtracadoComMatricula(string const& matricula)
        const;

    /** Indica se existe algum registo de navio em espera com a
        matrícula dada. */
    bool contemRegistoDeNavioEmEsperaComMatricula(string const& matricula)
        const;

    /** Indica se existe algum registo de navio atracado ou em espera
        com a matrícula dada. */
    bool contemRegistoDeNavioComMatricula(string const& matricula)
        const;

    /** Regista a chegada de um navio ao porto.  Se houver algum cais livre
        o navio atraca, caso contrário fica em espera.
        @pre ¬contemRegistoDeNavio(navio.matricula()) e
        ¬cais.contemRegistoDeNavio(navio.matricula()) e
        haEspacoNoPorto(). */
    void registaChegadaDe(RegistoDeNavio registo_de_navio);

    /** Regista a partida de uma navio do porto, dada a sua matrícula.
        Se existirem navios em espera, é dada autorização de atracagem ao
        que estiver na frente da fila.
        @pre cais.contemRegistoDeNavio(navio.matricula()). */
    void registaPartidaDeNavioComMatricula(string const& matricula);

  private:
    FilaDeRegistosDeNavios fila_de_navios_em_espera;
    ConjuntoDeRegistosDeNavios conjunto_de_navios_atracados;
 
    /// Devolve o número do primeiro cais que estiver livre.
    int numeroDoPrimeiroCaisLivre() const;

    /** Marca o cais dado como ocupado.
        @pre 1 <= numero_do_cais <= cais_ocupados.size() e
        o cais com número numero_do_cais está livre. */
    void ocupaCaisComNumero(int numero_do_cais);

    /** Marca o cais dado como livre.
        @pre 1 <= numero_do_cais <= cais_ocupados.size() e
        o cais com número numero_do_cais está ocupado.
        @post haCaisLivre(). */
    void libertaCaisComNumero(int numero_do_cais);

    vector<bool> cais_ocupados;

    bool cumpreInvariante() const;
};

ControladorDoPorto::ControladorDoPorto(int const numero_de_cais)
    : cais_ocupados(numero_de_cais)
{
    assert(0 < numero_de_cais);

    assert(cumpreInvariante());
}

bool ControladorDoPorto::haCaisLivre() const
{
    assert(cumpreInvariante());

    vector<bool>::size_type i = 0;
    while(i != cais_ocupados.size() and cais_ocupados[i])
        ++i;
 
    return i != cais_ocupados.size();
}

bool ControladorDoPorto::haEspacoEmEspera() const
{
    assert(cumpreInvariante());

    return not fila_de_navios_em_espera.estaCheia();
}

bool ControladorDoPorto::haEspacoNoPorto() const
{
    assert(cumpreInvariante());

    return haCaisLivre() or haEspacoEmEspera();
}

void ControladorDoPorto::mostra() const
{
    assert(cumpreInvariante());

    cout << "Navios em cais:" << endl << endl;
    conjunto_de_navios_atracados.mostra();
    cout << endl
         << "Navios em espera:" << endl << endl;
    fila_de_navios_em_espera.mostra();
    cout << endl;
}

bool ControladorDoPorto::
contemRegistoDeNavioAtracadoComMatricula(string const& matricula) const
{
    assert(cumpreInvariante());

    return conjunto_de_navios_atracados.contemRegistoDeNavioComMatricula(
        matricula);
}

bool ControladorDoPorto::
contemRegistoDeNavioEmEsperaComMatricula(string const& matricula) const
{
    assert(cumpreInvariante());

    return fila_de_navios_em_espera.contemRegistoDeNavioComMatricula(
        matricula);
}

bool ControladorDoPorto::
contemRegistoDeNavioComMatricula(string const& matricula) const
{
    assert(cumpreInvariante());

    return contemRegistoDeNavioAtracadoComMatricula(matricula) or
        contemRegistoDeNavioEmEsperaComMatricula(matricula);
}

void ControladorDoPorto::registaChegadaDe(RegistoDeNavio navio)
{
    assert(cumpreInvariante());
    assert(not contemRegistoDeNavioComMatricula(navio.matricula()) and
           haEspacoNoPorto());

    if(haCaisLivre()) {
        navio.colocaEmCaisNumero(numeroDoPrimeiroCaisLivre());
        ocupaCaisComNumero(navio.numeroDoCais());
        conjunto_de_navios_atracados.insere(navio);
    } else if(not fila_de_navios_em_espera.estaCheia()) {
        fila_de_navios_em_espera.poe(navio);
    }
}

void ControladorDoPorto::registaPartidaDeNavioComMatricula(
    string const& matricula)
{
    assert(cumpreInvariante());
    assert(conjunto_de_navios_atracados.contemRegistoDeNavioComMatricula(
               matricula));

    RegistoDeNavio registo_do_navio_de_partida =
        conjunto_de_navios_atracados.registoDeNavioComMatricula(matricula);

    libertaCaisComNumero(registo_do_navio_de_partida.numeroDoCais());

    conjunto_de_navios_atracados.removeRegistoDeNavioComMatricula(matricula);

    if (not fila_de_navios_em_espera.estaVazia()) {
        RegistoDeNavio navio_a_atracar(fila_de_navios_em_espera.primeiro());

        int numero_de_cais_livre = numeroDoPrimeiroCaisLivre();

        navio_a_atracar.colocaEmCaisNumero(numero_de_cais_livre);

        ocupaCaisComNumero(numero_de_cais_livre);

        conjunto_de_navios_atracados.insere(navio_a_atracar);

        fila_de_navios_em_espera.tira();
    }

    assert(cumpreInvariante());
}

int ControladorDoPorto::numeroDoPrimeiroCaisLivre() const
{
    assert(cumpreInvariante());
    assert(haCaisLivre());

    vector<bool>::size_type i = 0;
    while(i != cais_ocupados.size() and cais_ocupados[i])
        ++i;
 
    return int(i + 1);
}

void ControladorDoPorto::ocupaCaisComNumero(int const numero_do_cais)
{
    assert(1 <= numero_do_cais and
           numero_do_cais <= int(cais_ocupados.size()) and
           not cais_ocupados[numero_do_cais - 1]);

    cais_ocupados[numero_do_cais - 1] = true;
}

void ControladorDoPorto::libertaCaisComNumero(int const numero_do_cais)
{
    assert(1 <= numero_do_cais and
           numero_do_cais <= int(cais_ocupados.size()) and
           cais_ocupados[numero_do_cais - 1]);

    cais_ocupados[numero_do_cais - 1] = false;

    assert(haCaisLivre());
}

bool ControladorDoPorto::cumpreInvariante() const
{
    /* 1. Não há repetições de matrículas:
       Dentro do conjunto de navios atracados não há repetições, pelo
       invariante da classe ConjuntoDeRegistosDeNavios.  O mesmo se
       passa com a fila de navios em espera.

       Mas é necessário verificar se existem repetições entre os navios
       atracados e os navios em espera.  Como a interface das classes
       fornecidas não permite o acesso a todos os registos guardados,
       a resolução total deste problema implicaria alterar essa
       interface.  Como a interface foi dada no enunciado, tal não
       foi feito.

       2.  Navios em espera não têm cais:
       Seria útil verificar que todos os navios em espera não têm cais
       registado.  Pelas mesmas razões que atrás, tal verificação
       não é possível.

       3.  Navios atracados têm cais:
       Seria útil verificar que todos os navios atracados têm cais
       registado.  Pelas mesmas razões que atrás, tal verificação
       não é possível.

       4.  Coerência dos cais registados nos navios atracados com os
       cais ocupados (indicados pelo vector cais_ocupados).  Pelas
       mesmas razões que atrás, tal verificação não é possível.
       Nem mesmo é possível verificar quantos registos de navios
       existem no conjunto.

       Assim, não há outro remédio senão... */
    return true;
}

/* Note-se que se optou por manter a interface com o utilizador fora
   da classe ControladorDoPorto.  Dessa forma, se o tipo de interface
   variar, essa classe não precisa de ser alterada.  (Na realidade
   todas as classes contêm pelo menos uma parte da interface: sabem-se
   mostrar.  Em Programação Orientada para Objectos ver-se-á como é
   possível resolver o problema. */

/** Devolve a opção do menu escolhida pelo utilizador.  Esta função é
    propositadamente simples.  Não faz qualquer verificação da validade
    da introdução feita pelo utilizador.  Veja-se as folhas teóricas. */
int escolhaDoMenu()
{
    cout << "0. Sair" << endl
         << "1. Registar chegada" << endl
         << "2. Registar partida" << endl
         << "3. Mostrar situação do porto" << endl
         << "Opção: ";
    int opcao;
    cin >> opcao;
    cout << endl;

    return opcao;
}

/// Processa uma entrada no porto.
void registaChegada(ControladorDoPorto& controlador)
{
    if(not controlador.haEspacoNoPorto())
        cout << endl
             << "Impossível.  Porto cheio!" << endl;
    else {
        /* Optou-se por perguntar primeiro a matrícula do navio.
         * Desta forma o utilizador não sente que perdeu tempo
         * introduzindo o nome caso se engane na matrícula. */
        cout << "Qual a matrícula do navio? ";
        string matricula;
        cin >> matricula;
 
        if(controlador.contemRegistoDeNavioComMatricula(matricula))
            cout << endl
                 << "Um navio com essa matricula já se encontra no porto!"
                 << endl;
        else {
            cout << "Qual o nome? ";
            string nome;
            cin >> nome;
 
            cout << endl;
 
            if(controlador.haCaisLivre())
                cout << "Navio registado. Atracagem permitida." << endl;
            else
                cout << "Navio registado. Em fila de espera." << endl;
 
            controlador.registaChegadaDe(RegistoDeNavio(nome, matricula));
        }
    }
    cout << endl;
}
 
/// Processa uma partida do porto.
void registaPartida(ControladorDoPorto& controlador)
{
    cout << "Qual a matricula do navio? ";
    string matricula;
    cin >> matricula;

    cout << endl;

    if(not controlador.contemRegistoDeNavioAtracadoComMatricula(matricula))
        cout << "Não está atracado nenhum navio com essa matricula." << endl;
    else {
        controlador.registaPartidaDeNavioComMatricula(matricula);
        cout << "Registo de partida efectuado." << endl;
    }
 
    cout << endl;
}
 
int main()
{
    ControladorDoPorto controlador(10);

    // No enunciado não há opção para sair.  Como faz sentido que
    // haja, acrescentou-se essa opção:
    while(true) {
        switch(escolhaDoMenu()) {
          case 0:
            return 0;
          case 1:
            registaChegada(controlador);
            break;
          case 2:
            registaPartida(controlador);
            break;
          case 3:
            controlador.mostra() ;
            break;
        }
    }
}

Questão 3

Considere a função double produtoInterno(vector <double> const& v1, vector <double> const& v2) que faz o produto interno dos vectores v1 e v2.  Recorda-se que o produto interno de dois vectores é o somatório: v1[0] × v2[0] + v1[1] × v2[1] + ... + v1[n - 1] × v2[n - 1], em que n é a dimensão dos vectores.  A operação produto interno só faz sentido para vectores do mesmo tamanho.

3.1  Indique a  pré-condição (PC), a condição objectivo (CO), a condição invariante (CI) e a guarda (G) do ciclo necessário à construção desta função.

[cotação: 0,5]
 

PC: 0 <= v1.size() e v1.size() = v2.size().
CO: produtoInterno = (S j : 0 <= j < v1.size() : v1[j] × v2[j]).
CI: produtoInterno = (S j : 0 <= j < i : v1[j] × v2[j]) e 0 <= i <= v1.size().
G: i <> v1.size().

[cotação: 1]

double produtoInterno(vector<double> const& v1, vector<double> const& v2) 
{
    assert(0 <= v1.size() and v1.size() == v2.size());

    double produto_interno = 0.0;

    for(vector<double>::size_type i = 0; i != v1.size(); ++i)
        produto_interno  += v1[i] * v2[i];

    return produto_interno;
}

1. Se a PC for verdadeira, então a CI também é verdadeira após a inicialização das variáveis e antes da primeira iteração do ciclo, i.e.:
// PC
init
// implica CI.

// PC: 0 <= v1.size() e v1.size() = v2.size().
double produto_interno = 0.0;
vector<double>::size_type i = 0;
// CI: produtoInterno = (S j : 0 <= j < i : v1[j] × v2[j]) e 0 <= i <= v1.size() é o mesmo que
//    0 = (S j : 0 <= j < 0 : v1[ j] × v2[ j]) e 0 <= 0 <= v1.size(), que é o mesmo que
//    0 = 0 e 0 <= 0 <= v1.size(), que, dada a pré-condição, é o mesmo que
//    V.


2. Se a guarda G e a CI  do ciclo forem verdadeiras no início de um passo, então a CI também é verdadeira no fim desse passo, i.e.:
// G e CI
passo
// implica CI

// CI e G: produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) e 0 <= i <= v1.size() e i <> v1.size() é o mesmo que
//       produtoInterno = (S j : 0 <= j < i : v1[j] × v2[j]) e 0 <= i < v1.size().
produto_interno  += v1[i] * v2[i];
// produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) + v1[i] × v2[i] e 0 <= i < v1.size(), que é o mesmo que
// produtoInterno = (S j : 0 <= j < i + 1 : v1[ j] × v2[ j]) e 0 <= i < v1.size().
++i;
// produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) e 0 <= i - 1 < v1.size(), que é o mesmo que
// produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) e 1 <= i <= v1.size(), que implica
// CI: produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) e 0 <= i <= v1.size().


3. Se a guarda G for falsa e a CI for verdadeira, então a CO é verdadeira, i.e.:
// CI e ¬G implica CO.

// CI e ¬G: produtoInterno = (S j : 0 <= j < i : v1[ j] × v2[ j]) e 0 <= i <= v1.size() e i = v1.size() é o mesmo que
//         produtoInterno = (S j : 0 <= j < v1.size() : v1[ j] × v2[ j]) e 0 <= v1.size() <= v1.size() e i = v1.size()
// que, da a pré-condição, implica que
// produtoInterno = (S j : 0 <= j < v1.size() : v1[ j] × v2[ j]) e i = v1.size(), que por sua vez implica que
// CO: produtoInterno = (S j : 0 <= j < v1.size() : v1[ j] × v2[ j]).

[cotação: 1,5] 

Explique as vantagens para o desenvolvimento de programas de fazer o teste de cada módulo  (classe, função ou procedimento) logo que ele é definido em vez de escrever primeiro a solução completa e compilar e testar apenas no fim.

[cotação: 1]

A principais vantagens da compilação e teste de cada módulo no fim da construção são:

• Evitar a acumulação e o encadeamento de erros que tipicamente acontece quando se juntam vários módulos não testados.
• Evitar que erros num módulo tenham consequências nefastas em outros módulos e dificultem a depuração.
• Conseguir mais facilmente identificar a origem dos erros. 

Aliás, melhor ainda é escrever o código de teste de cada módulo ainda antes de os definir e preservar esse código de teste (que está em contínuo crescimento), para que se possa facilmente voltar a testar todos os módulos se alguma alteração for feita.