PROG2-2_Set_05-04-2016

// Array dinamico

#include <iostream>
using namespace std;

class Set{
private:
    int *A;
    int size;           // numero di elementi
    int length;         // dimensione dell'array
    void raddoppia();   // raddoppia la dimensione dell'array e copia gli elementi

public:
    Set();
    Set* insert(int x);
    void del(int pos);
    void print();
    int search(int x);
    int is_empty();
    int get_size();
};

Set::Set(){
    this->length = 1;
    this->size = 0;
    A = new int[1];
}

void Set::raddoppia(){
    int *B = new int[length*2];
    for(int i = 0; i < size; i++) B[i] = A[i];
    delete [] A;
    A = B;
    length *= 2;
}

int Set::get_size(){ return size; }
int Set::is_empty(){ return !size; }

int Set::search(int x){
    for(int i = 0; i < size; i++) if(A[i] == x) return i;
    return -1;
}

void Set::del(int pos){
    if(pos < 0) return;
    A[pos] = A[--size];
}

// in questo modo posso richiamare la funzione insert in cascata
Set* Set::insert(int x){
    if(size == length) raddoppia();
    A[size++] = x;
    return this; // ritorno il puntatore all'oggetto che ha generato la chiamata
}

void Set::print(){
    cout << "[" << length << ", " << size << "] ";
    for(int i = 0; i < size; i++)
        cout << A[i] << " ";
    cout << endl;
}

int main(){
    Set *s = new Set();

    s->insert(5)->insert(2)->insert(1)->insert(6);
    s->print();

    cout << s->search(1) << endl;

    s->del(s->search(1)); // cerco il valore 1 e lo elimino (se esiste)
    s->print();

    return 0;
}

/*
    Come ingrandire l'array ogni volta che viene superata la dimensione massima

    9 3 11 1 7 5 13 2
                                                } O(n)
    - - - - - - - - - - - - - - - - - -

    Devo copiare m elementi da un vettore all'altro:
    m operazioni ( complessità O(m) )

    1 -> O(1)
    2 -> O(2)
    3 -> O(3)
    .
    .
    .
    .
    m -> O(m)

    Questo algoritmo non è molto efficiente... la sua complessità è infatti data da:
    sommatoria per i = 1 a m di i = O(m^2)

    in realtà la complessità non è proprio m^2 perché la funzione
    raddoppia non sempre viene utilizzata...

    [x] (2)

    [x] (1) [x] (2)

    [x] (0) [x] (0) [x] (2) [x] (2)

          ALGORITMO           MEDIA
    1 _                     1 _ _ _
    2 _ _                   2 _ _ _
    3 _ _ _                 3 _ _ _
    4 _                     4 _ _ _
    5 _ _ _ _ _             5 _ _ _
    6 _                     6 _ _ _
    7 _                     7 _ _ _
    8 _                     8 _ _ _
    9 _ _ _ _ _ _ _ _ _     9 _ _ _

    Il tempo per ogni operazione varia da molto poco a tanto però in media il tempo
    di esecuzione è di 3 unità di tempo computazionale

    Complessità O(3m) -> O(m)

    nel caso della cancellazione prima di rimpicciolire l'array devo
    arrivare ad un quarto della sua dimensione.

*/