/*
    Complexitate: teta(1)
    aloca memorie de indice i (intreg)
*/

aloca() {
    int i = this->primulLiber;
    if (i != -1) {
        this->primulLiber = this->urm[i];
    }
    return i;
}

/*
    Complexitate: teta(1)
    dealoca memoria de pe indicele i
*/
dealoca(int i) {
    this->urm[i] = this->primulLiber;
    this->primulLiber = i;
}



/*
    Complexitate: teta(n)
    initializare spatiu liber
*/
void Colectie::initSpLiber() {
    for (int i = 0; i < this->cp-1; i++) {
        this->urm[i] = i+1;
    }

    this->urm[this->cp - 1] = -1; // setam urm pt ultimul element ca fiind NIL

    this->primulLiber = 0; // setam pozitia catre primul element din tablou
}


/*
    Complexitate: O(1)
    initializeaza colectia
*/
Colectie() {
    cp = 100;
    this->countElems = 0;


    this->p = new TPereche[cp];
    this->urm = new int[cp];

    this->primulLiber = -1;
    this->primul = -1;

    this->initSpLiber();
}


/*
    Complexitate: O(n)
    creeaza un nod nou in cazul in care nu se poate folosi spatiul de la un nod anterior
*/
creeazaNod(TElem e) {

    if (this->primulLiber == -1) { // daca lista este plina
        // realoca
        // copiaza elemente + legaturi
        // reinitializeaza lista spartiu liber

        TPereche* newP = new TPereche[cp * 2];
        int* newU = new int[cp * 2];

        for (int i = 0; i < cp; i++) { // copiem tot ce avem deja existent in lista
            newP[i] = this->p[i];
            newU[i] = this->urm[i];
        }

        this->primulLiber = cp; // pozitionam primul liber pe prima pozitie din a doua jumatate a noului tablou

        for (int i = cp; i < cp * 2 - 1; i++) {
            newU[i] = i + 1;
        }

        newU[cp * 2 - 1] = -1;

        // actualizam capacitatea
        this->cp = this->cp * 2;

        // stergem fostul tablou si facem noua asociere
        delete[] this->p;
        delete[] this->urm;

        this->p = newP;
        this->urm = newU;
    }

    int i = this->aloca();
    this->p[i].first = e;
    this->p[i].second = 1;
    this->urm[i] = -1;
    return i;
}