asp2dz1

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

const int MAX = 100;

class povecanaTabela {

private:

    int brojElem;
    int zauzetoElem;
    int prosirenje;
    int *niz, *flagNiz;

    void sort(int* &niz, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (niz[i] > niz[j]) {
                    int pom = niz[i];
                    niz[i] = niz[j];
                    niz[j] = pom;
                }
            }
        }
    }

    void realociraj() {
        cout << endl << "Doslo je do realokacije tabele!!!" << endl;
        int k = 2 * brojElem;
        int *niz2 = new int[k];
        int *flagNiz2 = new int[k];

        for (int i = 0; i < k; i++) {
            niz2[i] = niz[i / 2];
            flagNiz2[i] = (i % 2 ? 0 : 1);
        }

        delete[] niz;
        delete[] flagNiz;
        flagNiz = flagNiz2;
        niz = niz2;
        brojElem *= 2;
    }

    int ternPret(int key) const {
        int low = 0;
        int high = brojElem - 1;

        while (high >= low) {
            int p1 = low + ceil((high - low)) / 3;
            int p2 = high - ceil((high - low)) / 3;

            if (key == niz[p1]) {
                int k = p1;
                while (flagNiz[k] == 0 and k >= 0) {
                    if (niz[k] != key) break;
                    k--;
                }
                if (niz[k] == key and flagNiz[k] == 1) return k;
                else {
                    while (flagNiz[k] == 0) k++;
                    if (niz[k] == key) return k;
                }

            }
            else if (key == niz[p2]) {
                int k = p2;
                while (flagNiz[k] == 0 and k >= 0) {
                    if (niz[k] != key) break;
                    k--;
                }
                if (niz[k] == key and flagNiz[k] == 1) return k;

            }
            else if (key < niz[p1]) high = p1 - 1;
            else if (key > niz[p1] and key < niz[p2]) {
                low = p1;
                high = p2 - 1;
            }
            else if (key > niz[p2]) low = p2 + 1;
        }

        int k = low;
        while (k >= 0) {
            if (flagNiz[k] == 1 and niz[k] < key) break;
            k--;
        }
        while (flagNiz[k] == 1 and niz[k] == key) k++;
        if (k == 0 and key < niz[k]) return -1;
        else return k;
    }     //UVEK VRACA ELEMENT IZA KOGA TREBA DA SE UBACI NOVI ELEMENT




public:

    int getBrojElem()const {
        return brojElem;
    }
    int getZauzetoElem()const {
        return zauzetoElem;
    }
    int getProsirenje()const {
        return prosirenje;
    }

    void formirajTabelu() {
        cout << "Unesite broj elemenata tabele: " << endl;
        int n;
        cin >> n;

        if (n < 1 or n > MAX) {
            cout << "Nevazeci broj elemenata!" << endl;
            return;
        }

        int *nizx = new int[n];
        for (int i = 0; i < n; i++) {
            cout << "Unesite " << i + 1 << ". element tabele: ";
            cin >> nizx[i];
        }
        sort(nizx, n);
        cout << "Unesite prosirenje: ";
        int p;
        cin >> p;

        int *niz2 = new int[n * p];
        flagNiz = new int[n * p];

        for (int i = 0; i < n * p; i++) {
            niz2[i] = nizx[i / p];
            flagNiz[i] = (i % p == 0 ? 1 : 0);
        }

        delete[] nizx;
        this->niz = niz2;
        this->brojElem = n * p;
        this->prosirenje = p;
        this->zauzetoElem = n;
        cout << endl << "Tabela uspesno formirana! Ispis: " << endl;
        this->ispisiTabelu();
    }
    //MOZDA POPRAVI KONZOLU

    void ispisiTabelu() const {
        cout << endl;
        for (int i = 0; i < brojElem; i++) {
            cout << niz[i] << "|";
        }
        cout << endl;
        for (int i = 0; i < brojElem; i++) {
            cout << flagNiz[i] << "|";
        }
        cout << endl;
    }
    //OVDE POPRAVI ISPIS


    void ispisiElem(int key) const { // *****
        int k = ternPret(key);
        if (niz[k] == key and flagNiz[k] == 1){
            cout << "Element " << key << " nadjen na poziciji " << k << "." << endl;
            return;
        } else {
            cout << "Nije nadjen element koji ima vrednost " << key << endl;
            return;
        }
    }

    void umetanjeKljuca(int key) {

        if (zauzetoElem == brojElem) realociraj();

        int k = ternPret(key);
        if(k != brojElem - 1) k++; //pozicija gde treba da stavimo element

        if (k == -1) {
            k = 0;
            while (1) {
                if (flagNiz[k] == 0) break;
                k++;
            }
            for (int i = k; i > 0 ; i--) {
                flagNiz[i] = flagNiz[i - 1];
                niz[i] = niz[i - 1];
            }
            flagNiz[0] = 1;
            niz[0] = key;
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << 0 << endl;
            return;
        }

        if (k == brojElem - 1) {
            while (1) {
                if (flagNiz[k] == 0) break;
                k--;
            }
            for (int i = k; i < brojElem - 1; i++) {
                flagNiz[i] = flagNiz[i + 1];
                niz[i] = niz[i + 1];
            }
            flagNiz[brojElem - 1] = 1;
            niz[brojElem - 1] = key;
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << brojElem - 1 << endl;
            return;
        }

        int poz = k;

        if (flagNiz[k] == 0) {
            niz[k] = key;
            flagNiz[k] = 1;
            k++;
            while (flagNiz[k] == 0) {
                niz[k] = key;
                k++;
            }
            zauzetoElem++;
            cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
            return;
        }

        // trazenje mesta udesno

        else {
            while (k < brojElem - 1) {
                if (flagNiz[k] == 0) break;
                k++;
            }
            if (flagNiz[k] == 0) {
                for (int i = k; i > poz; i--) {
                    niz[i] = niz[i - 1];
                    flagNiz[i] = flagNiz[i - 1];
                }
                niz[poz] = key;
                flagNiz[poz] = 1;
                zauzetoElem++;
                cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
                return;
            }

            // trazenje mesta ulevo

            poz--;

            while (k >= 0) {
                if (flagNiz[k] == 0) break;
                k--;
            }

            if (flagNiz[k] == 0) {
                for (int i = k; i < poz; i++) {
                    niz[i] = niz[i + 1];
                    flagNiz[i] = flagNiz[i + 1];
                }
                niz[poz] = key;
                flagNiz[poz] = 1;
                zauzetoElem++;
                cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
                return;
            }
        }
    }

    void brisanjeKljuca(int key){ // ****
        int k = ternPret(key);
        if (niz[k] == key and flagNiz[k] == 1){
            flagNiz[k] = 0;
            cout << "Uspesno brisanje kljuca na poziciji " << k << endl;
            return;
        } else {
            cout << "Element nije pronadjen ili je nevazeci! " << endl;
        }
    }
};

void konzola(){
    cout << endl << "Unosom rednog broja izaberite komandu: " << endl << endl;
    cout << "1. Pravljenje i inicijalizacija prosirene tabele" << endl;
    cout << "2. Ispisivanje indeksa(pozicije) odredjenog elementa u tabeli" << endl;
    cout << "3. Umetanje odredjenog elementa u tabelu" << endl;
    cout << "4. Brisanje odredjenog elementa iz tabele" << endl;
    cout << "5. Ispis cele tabele" << endl;
    cout << "0. Izlazak iz programa" << endl << endl << endl;
}


int main(void) {

    cout << "Dobrodosli u program!!! :) :) :)" << endl;
    int napravljenaTabela = 0;
    povecanaTabela *povTab = nullptr;



    while(1){
        konzola();
        cout << "Unesite komandu: ";
        int komanda;
        cin >> komanda;
        int key;
        switch (komanda) {
            case 1:
                if (napravljenaTabela){
                    cout << "Tabela je vec napravljena!" << endl;
                    break;
                }
                cout << "Formiranje povecane tabele: " << endl;
                povTab = new povecanaTabela;
                povTab->formirajTabelu();
                napravljenaTabela = 1;
                break;
            case 2:
                if (!napravljenaTabela){
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite element(key) za pretragu: ";
                cin >> key;
                povTab->ispisiElem(key);
                break;
            case 3:
                if (!napravljenaTabela){
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite vrednost elementa koji stavljate u tabelu: ";
                cin >> key;
                povTab->umetanjeKljuca(key);
                povTab->ispisiTabelu();
                break;
            case 4:
                if (!napravljenaTabela){
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Unesite vrednost(key) elementa za brisanje: ";
                cin >> key;
                povTab->brisanjeKljuca(key);
                povTab->ispisiTabelu();
                break;
            case 5:
                if (!napravljenaTabela){
                    cout << "Tabela jos ne postoji!" << endl;
                    break;
                }
                cout << "Ispis cele tabele: " << endl;
                povTab->ispisiTabelu();
                break;
            case 0:
                exit(1);
                break;

            default:
                cout << "Nevazeca komanda!!!" << endl;
                break;
        }


    }

}