ASP2DomBST3

#include<stdio.h>
#include<stdlib.h>

/* ------ Deklaracija funkcija nasledjenih iz prvog zadatka ------ */

void initTable(int **table, int **valid, int sizeKeys, int *keys, int increasFactor, int *size);
int binarySearch(int *table, int *valid, int size, int key);
int checkValid(int *table, int *valid, int key, int cur);
void deleteKey(int **table, int **valid,int size, int key);
int binaryInsert(int *table, int *valid, int size, int key);
void insertKey(int **table, int **valid, int *size, int key, int increasFactor);
void increaseTable(int **table, int **valid, int size);


/* ------ Implementacija struktura koriscenih u drugom zadatku ------ */

/* Node - struktura koji se koristi kao cvor za stablo binarne pretrage - BST */
typedef struct node{
    int key;
    struct node *left, *right;
} Node;

/* Queue node - Struktura koja se koristi za implementaciju fifo reda
 Red je implementiran kao jednostruka ulancana lista
 Red se koristi za level order obilazak stabla prilikom ispisa i brisanja stabla */
struct QueueNode{
    Node *nd;
    struct QueueNode *next;
} *frontQ, *rearQ, *tempQ, *front1Q;


/* Stack node - Struktura koja se koristi za implementaciju steka kao ulancane liste
 Element steka ce sadrzati dve promenljive, koje ce se koristiti prilikom
 Implementacije formiranja stabla koriscenjem binarne pretrage povecane tabele*/
struct StackNode {
    int low;
    int high;
    struct StackNode *next;
} *top; //Pokazivac na vrh steka3


/* ------ Deklaracija funkcijih koriscenih u drugom zadatku ------ */

// Pomocna funkcija za ubacivanje cvora
Node* newNode(int item);
// Zahtevane funkcije
Node* insert(Node *root, int key);
int search(Node *root, int key1);
Node* rotate(Node *root,int key1, int right);
//Pomocne funkcije za koriscenje steka
int StackEmpty();
void push(int l, int h);
struct StackNode* pop();
//Zahtevana funkcija koja koristi stek
Node* formBST(int *table, int *valid, int size);
//Pomocne funkcije za koriscenje reda
void enq(Node *n);
void deq();
int empty();
//Zahtevane funkcije koje korsite red
void printBST(Node* root);
void deleteBST(Node* root);

/* ------ Implementacija funkcija nasledjenih iz prvog zadatka ------ */

void initTable(int **table, int **valid, int sizeKeys, int *keys, int increasFactor, int *size){
    *size = sizeKeys*increasFactor;
    *table = (int*)calloc( *size, sizeof(int));
    *valid = (int*)calloc( *size, sizeof(int));
    for(int i = 0; i < sizeKeys; i++)
        for(int j = 0; j < increasFactor; j++){
            (*table)[j + i*increasFactor] = keys[i];
            if( j != 0)
                (*valid)[j + i*increasFactor] = 0;
           else
                (*valid)[j + i*increasFactor] = 1;
        }
}

int binarySearch(int *table, int *valid, int size, int key){
    // printf("pozvao sam binary za %d\n", key);
    int low = 0, high = size; //gornja i donja granica
    int cur;
    while(low <= high){
        cur = low+(high-low)/2;
        if(table[cur] == key)
            return checkValid(table, valid, key, cur);
        if(table[cur] > key)
            high = cur - 1;
        else
            low = cur + 1;
    }
    return -1;
}

int checkValid(int *table, int *valid, int key, int cur){ //proverava da li pronadjen kljuc validan
    while(cur >= 0 && ( valid[cur] != 1 || table[cur] != key )){ //trazi sve dok ne pronadje valid bit ili ne nadije na novi kljuc
        cur--;
    }
    if(cur < 0 ||table[cur] != key ) //izasao iz opsega ili nasao drugi kljuc
        return -1;
    if(valid[cur] == 1)  //nasao je valid bit za pitani kljuc
        return cur;
}

void deleteKey(int **table, int **valid,int size, int key){
    int loc = binarySearch(*table, *valid, size, key); //pronalazi kljuc koji se brise
    if(loc  != -1)  //ako ga je pronasao menja njegov valid bit na nulu
        (*valid)[loc] = 0;
    else
        printf("Key %d doesn't exist\n", key);

}

//pronalazi mesto za ubacivanje uvek nadje najdesnje povoljno mesto
int binaryInsert(int *table, int *valid, int size, int key){
    int cur, high = size, low = 0; //gornja i donja granica
    while (low < high) {
        cur = (high + low) / 2;
        if (table[cur] == key)
            return cur;
        else if (table[cur] > key)
            high =  cur - 1;
        else
            low = cur + 1;
    }
    if(low == size)
        return size;
    else if(table[0] > key)
        return 0;
    else
        return low;
}

void insertKey(int **table, int **valid, int *size, int key, int increasFactor){
    printf("Ubacujem kljuc %d\n", key);
    int place = binaryInsert(*table, *valid, *size, key);// gde treba biti umetnut
    //proveri da li je taj vec ubacen
    if((*table)[place] == key){
        if(place = checkValid(*table, *valid, key, place) != -1){
            return; //Ovaj kljuc je vec u tabeli ne treba nista da se radi
        }
        else{
            //Ovaj kljuc je vec u tabeli ali nije validan, postavi ga da bude validan
            (*valid)[place] = 1;
            return;
        }
    }
    else if(place == 0){ //stavlja se na pocetak;
        if((*valid)[0] == 1){ //Ako prvi jeste validan, pokusamo da ga pomerimo u desno, ako ne moze onda prosirimo tabelu
            int i = 1;
            int oldKey = (*table)[0];
            while((*valid)[i] !=1)
                i++;
            if(i == 1){
                //Ako ne moze da se umetne povecavamo tabelu
                *size *= 2;
                increaseTable(table, valid, *size);
                insertKey(table, valid, size, key, 1 );
            }
            else
                //Ako moze da se umetne
                for(int j = 0; j < i; j++){
                    if( j < i/2 )
                        (*table)[j] = key;
                    else{
                        (*table)[j] = oldKey;
                    }
                }
                (*valid)[i/2] = 1;
        }
        else{           //Ako prvi nije validan, pregazimo ga samo
            int i = 0;
            while((*valid)[i] == 0){
                (*table)[i] = key;
                i++;
            }
            *(valid)[0] = 1;
        }
    }
    else if(place == *size){
        //Postavlja se na kraj
        printf("postavljam na kraj\n");
        place--;
        if(-1 == checkValid(*table, *valid, (*table)[place], place)){ //Ako poslednji nije validn pregazi ga
            printf("Zadnji nije validan");
            while((*valid)[place] != 1){
                (*table)[place--] = key;
            }
            (*valid)[place+1] = 1;
        }
        else {
            while((*valid[place]) != 1)
                place--;
            if(place == *size){ // Ako je poslednji zauzet, moramo da prosirimo
                   *size *= 2;
                    increaseTable(table, valid, *size);
                    insertKey(table, valid, size, key, 1 );
                    return;
            }
            else{ //Ako poslednji nije zauzet, pomerimo ga u levo i onda ubacimo novi
                place += (*size - place)/2;
                (*valid)[place] = 1;
                while(place < *size){
                    (*table)[place] = key;
                    place++;
                }
            }
        }
    }
    //postavljam negde u sredinu
    else{
        if((*valid)[place] == 1){//Ovo mesto je zauzeto pa treba pomeriti neki kljuc
            place++;

            if((*valid)[place + 1] == 0 && (*table)[place] < key){ // Moze da se pomeri unapred, i onda to i uradimo i umetnemo novi ljuce

                int i = place+1;
                while((*valid)[i] != 1 && i != *size)
                    i++;
                for(int j = place; j < place + (i- place)/2; j++)
                    (*table)[j] = key;
                (*valid)[place + (i-place)/2] = 1;
            }
            else if((*valid)[place - 2] == 0){ //Ako nije mogao da se pomeri unapred onda pokusam da se pomeri ovaj iza, ako moze pomerimo
                place -= 2;
                int i = place;
                while(i != 0 && (*valid)[i] != 1)
                    i--;
                (*valid)[i + (place - i)/2 + 1] = 1;
                for(int j = i + (place - i)/2 + 1; j < place +1; j++)
                    (*table)[j] = key;
            }
            else{ //Moramo da prosirimo
                *size *= 2;
                increaseTable(table, valid, *size);
                //ovo nije rekurzija
                insertKey(table, valid, size, key, 1 );
            }
        }
        else{ //Mesto nije zauzeto, pa mozemo slobodno da umetnemo
            int i = place - 1;
            while(i != 0 && (*valid)[i] != 1)
                i--;
            i += (place - i)/2;
            (*valid)[i+1] = 1;
            for(int j = i+1; j < place+1; j++)
                (*table)[j] = key;
        }
    }

}

void increaseTable(int** table, int** valid, int size){
    //napravimo nove nizove koji su duplo veci
    int* tableNew = calloc(size, sizeof(int));
    int* validNew = calloc(size, sizeof(int));
    //Prekopiramo stari sadrzaj tako da ga je sada duplo vise
    for(int i = 0; i < size/2; i++)
        tableNew[2*i+1] = (tableNew[2*i] = (*table)[i]);
    for(int i = 0; i < size/2; i++)
        if((*valid)[i])
            validNew[2*i] = 1;
    //Oslobodimo staru memoriju i tu upisemo nove lise
    free(*table);
    free(*valid);
    (*table) = tableNew;
    (*valid) = validNew;
}

/* ------ Implementacija funkcija koriscenih u drugom zadatku ------ */

// Pomocna funkcija za ubacivanje novog cvora
Node* newNode(int item){
    Node *temp = (Node *)malloc(sizeof(Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

//Funkcija koja ubacuje novi cvor u BST
//Root je pokazivac na koreni cvor, a key vrednost koja se ubacuje u BST
Node* insert(Node *root, int key){
    //Napravi novi cvor koji sadrzi vrednost key
    Node* newnode = newNode(key);
    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    Node* x = root;
    // Pointer y maintains the trailing
    // pointer of x
    Node* y = NULL;
    while (x != NULL){
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    //Ako je root NULL, onda je drvo prazno
    // Novi cvor je koreni cvor
    if (y == NULL)
        y = newnode;

    //Ako je novi kljuc manji od dodeli novi cvor kao levo dete
    else if (key < y->key)
        y->left = newnode;
    // dodeli novi cvor kao desno dete
    else
        y->right = newnode;

    if(root == NULL)
        return y;
    else
        return root;
}

// Funkija koja trazi kljuc
int search(Node *root, int key1){
    // Spustaj se niz stablo dok ne dodjes do kraja
    Node* temp = root;
    while (temp != NULL) {
        //nastavi kroz desno podstablo
        if (key1 > temp->key)
            temp = temp->right;
        //nastavi kroz levo podstablo
        else if (key1 < temp->key)
            temp = temp->left;
        else
            return 1; // Vrati jedan ako je pronadjen kljuc
    }
    return 0;
}

/* Funkija za jednostruku rotaciju
 right se koristi kao fleg
 right = 1 rotiraj u desno, right = 0, rotiraj u levo */
Node* rotate(Node *root,int key1, int right){

        // Pronadji prosledjeni kljuc(cvor) oko kog se vrsi Rotacija
        //Isti princip kao search funkcija
        Node* x = root, *prev = NULL;
        while (x != NULL) {
            if (key1 > x->key){
                prev = x;
                x = x->right;}
            else if (key1 < x->key){
                prev = x;
                x = x->left;}
            else break;
        }

        if( x == NULL){
            printf("Given node doesn't exists\n");
            return root;
        }

        Node *y = NULL, *tmp = NULL;

        //Rotacija u desno i nemamo levog sina -> nista se ne radi
        if(right && x->left==NULL){
            return root;
        }
        //Rotacija u levo i nemamo desnog sina -> nista se ne radi
        else if(!right && x->right==NULL){
            return root;
        }

        //Rotiranje u desno
        if(right){
            y = x->left;
            tmp = y->right;
            y->right = x;
            x->left = tmp;
        }else{
            //Rotiranje u levo
            y = x->right;
            tmp = y->left;
            y->left = x;
            x->right = tmp;
        }

        //Rotacija korenog cvora, novi cvor postaje koren
        if( x == root ) {root = y;}
        //Ukoliko rotirani cvor ima roditelja, menja mu se roditelj
        else if(prev->right == x) prev->right = y;
        else if(prev->left == x) prev->left = y;

        return root;
}

// Provera da li je stek prazan
int StackEmpty(){
    return top == NULL;
}

//Funkcija koja dodaje element na vrh steka
void push(int l, int h){
    struct StackNode *sn = (struct StackNode*)malloc(sizeof(struct StackNode));
    sn->low = l;
    sn->high = h;
    sn->next = top;
    top = sn; //azuriraj pokazivac na vrh
}

//Funkcija koja vraca pokazivac na element skinut sa vrha steka
struct StackNode* pop(){
    // Provera da li je doslo do underflow-a
    // Moze i da se izbaci
    if (top == NULL) {
        printf("\nStack Underflow");
        exit(1);
    }
    else {
        struct StackNode *temp;
        //ono na sta pokazuje vrh postavi na pomocni pokazivac
        temp = top;
        // pomeri vrh steka
        top = top->next;
        // unisti pokazivac na sledeci
        temp->next = NULL;
        return temp;
    }
}

//Funkcija koja formira BST koriscenjem prosirene tabele
Node* formBST(int *table, int *valid, int size){
    int low = 0, high = size;
    int mid = high/2;
    //Pomocni cvor koji ce se koristiti kao koreni
    Node *toor = NULL;
    push(low, high);

    while(!StackEmpty()){

        //Uzmi sa vrha steka element
        struct StackNode *temp = pop();
        low = temp->low;
        high = temp->high;

        free(temp);

        //Doslo je do deformacije preskoci ovaj element
        if(high < low) continue;
        //Ne mozemo na vise segmenata da delimo kod
        // Proverimo da li je validan kljuc i ako jeste ubacujemo ga
        else if( low == high )
            if(valid[low] == 1){
                //toor = insert(toor, table[low]);
                toor = insert(toor, table[low]);
                continue;
            }

        //Proveravamo da li je element na pola segmenta validan
        mid = (low+high) / 2;
        if(valid[mid] == 1)
            toor = insert(toor, table[mid]);
            //toor = insert(toor, table[mid]);

        //Ubacujemo granicnike ka gornjem i donjem preostalom segmentu
        push(mid+1, high);
        push(low,mid-1);
    }

    return toor;
}

//Provera da li je red prazan
int QueueEmpty(){
     if ((frontQ == NULL) && (rearQ == NULL))
        return 1;
    else
       return 0;
}

//Enqueue - ubaci u red novi Cvor
void enq(Node *n){
    if (rearQ == NULL){
        rearQ = (struct QueueNode *)malloc(1*sizeof(struct QueueNode));
        rearQ->next = NULL;
        rearQ->nd = n;
        frontQ = rearQ;
    }else{
        tempQ = (struct QueueNode *)malloc(1*sizeof(struct QueueNode));
        rearQ->next = tempQ;
        tempQ->nd = n;
        tempQ->next = NULL;
        rearQ = tempQ;
    }
}

//Dequeue - izbaci cvor iz reda
void deq(){
    front1Q = frontQ;
    if (front1Q == NULL){
        printf("\n Error: Trying to display elements from empty queue");
        return;
    }else
        if (front1Q->next != NULL){
            front1Q = front1Q->next;
            free(frontQ);
            frontQ = front1Q;
        } else {
            free(frontQ);
            frontQ = NULL;
            rearQ = NULL;
        }
}

// Funckija koja unistava BST u level order poretku
void deleteBST(Node *root){
    // Prazno stablo ne radi nista
    if (root == NULL)
        return;
    // ubaci koreni cvor u red
    enq(root);
    //pomocni pokazivac na cvor kojim uzimamo element iz reda
    Node *frontN = NULL;
    // vrti se u petlji dok se ne isprazni red
    while (!QueueEmpty()) {
        // delete each node in the queue one by one after pushing their
        // non-empty left and right child to the queue
        //uzmi prvog iz reda
        frontN = frontQ->nd;
        //izabci prvog iz reda
        deq();
        //Ako ima levo dete, onda ubaci to dete u red
        if (frontN->left)
           enq(frontN->left);
        //Ako ima desno dete, onda ubaci to dete u red
        if (frontN->right)
           enq(frontN->right);
        // Tek nakon sto su deca ubacena u red, oslobadja se memorija koju je zauzimao cvor
        free(frontN);
    }
}

//Funkcija koja ispisuje cvorove stabla u level order poretku
// Isti princip kao iza brisanje stabla
void printBST(Node *root){
    if (root == NULL)
        return;

    Node *frontN = NULL;

    enq(root);
    while (!QueueEmpty()) {
        frontN = frontQ->nd;
        deq();
        if (frontN->left)
           enq(frontN->left);

        if (frontN->right)
           enq(frontN->right);

        printf("%d ", frontN->key);
    }
    printf("\n"); //Novi red nakon ispisa svih cvorova
}

int main(){

    // Deklaracija koriscenih promenljivih
    int size = 0, increasFactor = 0;
    int *valid = 0;
    int *table = 0;
    int *keys;
    frontQ = rearQ = NULL;
    Node *root = NULL;
    int flag = 1, ch, n;

    while(flag){
        printf("-===Menu===-");
        printf("\n 1 - Initialize table");
        printf("\n 2 - Insert into table");
        printf("\n 3 - Search table");
        printf("\n 4 - Delete kety");
        printf("\n 5 - Display table");
        printf("\n 6 - Initialize BST");
        printf("\n 7 - Search BST");
        printf("\n 8 - Insert into BST");
        printf("\n 9 - Show BST");
        printf("\n 10 - Delete BST");
        printf("\n 11 - Rotate left");
        printf("\n 12 - Rotate right");
        printf("\n 0 - Exit");

        printf("\n Enter choice : ");
        scanf("%d", &ch);

        switch(ch){
        case 1:
            if(table != NULL){
                free(table);
                free(keys);
                free(valid);
            }
            int f;
            printf("How many starting keys?\n");
            scanf("%d", &n);
            keys = calloc(n, sizeof(int));
            printf("Enter %d differnet key, in increasing order:\n", n);
            for(int i = 0; i < n; i++)
                scanf("%d", &keys[i]);
            printf("What is increase factor?\n");
            scanf("%d", &f);
            initTable(&table, &valid, n, keys,f, &size);
            break;
        case 2:
            printf("Which key you want to insert\n");
            int new;
            scanf("%d", &new);
            insertKey(&table, &valid, &size, new, 1);
            break;
        case 3:
            printf("Which key to search for?\n");
            int key;
            scanf("%d", &key);
            int ret = binarySearch(table,valid, size,key);
            ret != -1 ? printf("Key %d is at position %d.\n",key, ret) : printf("Key %d is not in the table\n", key);
            break;
        case 4:
            printf("Which key you want to delete?\n");
            scanf("%d", &key);
            deleteKey(&table,&valid,size,key);
            break;
        case 5:
            printf("Table of keys:\n");
            for(int i = 0; i < size; i++){
                printf("%d", table[i]);
                if(table[i] < 10)
                    putchar(' ');
            }
            printf("\nValid table:\n");
            for(int i = 0; i < size; i++)
                printf("%d ", valid[i]);
            putchar('\n');
            break;
        case 6:
            root = formBST(table,valid,size);
            printf("The BST is formed.\n");
            break;
        case 7:
            printf("Insert the key: ");
            scanf("%d", &n);
            if (search(root, n))
                printf("\n The key exists in BST.\n");
            else
                printf("\nThe key doesnt exists in BST.\n");
            break;
        case 8:
            printf("Insert the key: ");
            scanf("%d", &n);
            root = insert(root, n);
            break;
        case 9:
            printBST(root);
            break;
        case 10:
            deleteBST(root);
            root = NULL;
            printf("The BST is deleted.\n");
            break;
        case 11:
            printf("Insert the key: ");
            scanf("%d", &n);
            root = rotate(root, n, 0);
            break;
        case 12:
            printf("Insert the key: ");
            scanf("%d", &n);
            root = rotate(root, n, 1);
            break;
        case 0:
            deleteBST(root);
            if(table != NULL){
                free(table);
                free(keys);
                free(valid);
            }
            flag = 0;
            break;
        default:
            printf("Wrong choice, Please enter correct choice");
            break;
        }
    }
    return 0;
}