#include <vector> // Para std::vector
#include <utility> // Para std::swap
#include "pares_antes.h" // Inclui cabecalho para garantir compatibilidade.

// Funcao que organiza os valores no vetor passado de modo que todos os pares
// estejam antes de todos os impares.
void pares_antes(std::vector<int> &v) {
    // Pre-condicao: nenhuma
    long unsigned int inicio_desconhecido{0};
    long unsigned int final_desconhecido{v.size()};
    // A regiao entre inicio_desconhecido (incluido) e final_desconhecido
    // (excluido) tem valores que ainda nao foram ajustados.
    while (inicio_desconhecido != final_desconhecido) {
        // Invariante:
        //  i < inicio_desconhecido => v[i] par
        //  i >= final_desconhecido => v[i] impar
        //  inicio_desconhecido < final_desconhecido
        // Variante: final_desconhecido - inicio_desconhecido
        if (v[inicio_desconhecido] % 2 == 0) {
            // v[inicio_desconhecido] par =>
            //    podemos incrementar inicio_desconhecido
            ++inicio_desconhecido;
        }
        else if (v[final_desconhecido - 1] % 2 != 0) {
            // v[final_desconhecido] impar =>
            //    podemos decrementar final_desconhecido
            --final_desconhecido;
        }
        else {
            // v[inicio_desconhecido] impar e v[final_desconhecido] par
            //  => podemos trocar os dois de lugar e ajustar os limites.
            std::swap(v[inicio_desconhecido], v[final_desconhecido - 1]);
            ++inicio_desconhecido;
            --final_desconhecido;
        }
    }
    // Pos-condicao:
    // Qualquer i, j, i != j, se v[i] par e v[j] impar,
    // entao i < j.
}