Dvostrani niz (uprošćeni dek)

Projektovati šablon klase DvostraniNiz<T>:

template <typename T>
class DvostraniNiz {
public:
    DvostraniNiz(std::size_t pocetni_kapacitet = 4);
    ~DvostraniNiz();

    DvostraniNiz(const DvostraniNiz& drugi) = delete;
    DvostraniNiz& operator=(const DvostraniNiz& drugi) = delete;

    std::size_t velicina() const;
    bool prazan() const;

    T& operator[](std::size_t indeks);
    const T& operator[](std::size_t indeks) const;

    void dodaj_na_pocetak(const T& vrednost);
    void dodaj_na_kraj(const T& vrednost);
    void obrisi_sa_pocetka();
    void obrisi_sa_kraja();
};

Dodavanje na oba kraja radi u amortizovanom vremenu $O(1)$, a brisanje sa oba kraja, operator[] i velicina u vremenu $O(1)$. Kopiranje je zabranjeno sa = delete.

Ideja: ostaviti rezervu na obe strane. Elementi zauzimaju pozicije [pocetak, pocetak + velicina) u bloku, a pri realokaciji se smeštaju na sredinu dvostruko većeg bloka.

Pitanja za razmišljanje: Zašto dodaj_na_pocetak ne može da pomera sve elemente za jedno mesto? Šta je invarijanta klase?

Pored komandi sa ulaza, program kada se pokrene sa argumentima test N izvršava N nasumičnih operacija istovremeno nad DvostraniNiz i std::deque i ispisuje OK ako se ponašaju isto (u testu je STL dozvoljen).

./program test 100000

Ulaz

U prvom redu učitava se broj komandi q $(1 \le q \le 2 \cdot 10^5)$, a zatim q komandi:

Komanda Značenje
DP x dodaj_na_pocetak(x)
DK x dodaj_na_kraj(x)
OP obrisi_sa_pocetka() (niz nije prazan)
OK obrisi_sa_kraja() (niz nije prazan)
G i ispis elementa na poziciji i
I ispis svih elemenata

Izlaz

Za svaku komandu G i I ispisati rezultat u posebnom redu.

Primer

Ulaz

8
DK 1
DK 2
DP 0
DP -1
I
OP
OK
G 1

Izlaz

-1 0 1 2
1

Postavka

main.cpp

#include <cassert>
#include <cstddef>
#include <deque>
#include <iostream>
#include <random>
#include <string>

namespace matf {

    // Niz u koji se dodaje i iz kog se brise na oba kraja u amortizovanom
    // vremenu O(1), uz pristup proizvoljnom elementu u vremenu O(1).
    template <typename T>
    class DvostraniNiz {
    private:
        // Ovde ide vasa implementacija

    public:
        DvostraniNiz(std::size_t pocetni_kapacitet = 4);
        ~DvostraniNiz();

        DvostraniNiz(const DvostraniNiz& drugi) = delete;
        DvostraniNiz& operator=(const DvostraniNiz& drugi) = delete;

        std::size_t velicina() const;
        bool prazan() const;

        T& operator[](std::size_t indeks);
        const T& operator[](std::size_t indeks) const;

        void dodaj_na_pocetak(const T& vrednost);
        void dodaj_na_kraj(const T& vrednost);
        void obrisi_sa_pocetka();
        void obrisi_sa_kraja();
    };

    // Ovde ide vasa implementacija

} // namespace matf

// Nasumicno poredjenje sa std::deque (u testu je STL dozvoljen).
bool uporedi_sa_dekom(int broj_operacija)
{
    std::mt19937 gen(12345);
    std::uniform_int_distribution<int> operacija(0, 5);
    std::uniform_int_distribution<int> vrednost(-1000, 1000);

    matf::DvostraniNiz<int> niz(1);
    std::deque<int> dek;

    for (int k = 0; k < broj_operacija; ++k) {
        int op = operacija(gen);
        if (op <= 1) {
            int x = vrednost(gen);
            niz.dodaj_na_pocetak(x);
            dek.push_front(x);
        } else if (op <= 3) {
            int x = vrednost(gen);
            niz.dodaj_na_kraj(x);
            dek.push_back(x);
        } else if (op == 4 && !dek.empty()) {
            niz.obrisi_sa_pocetka();
            dek.pop_front();
        } else if (op == 5 && !dek.empty()) {
            niz.obrisi_sa_kraja();
            dek.pop_back();
        }

        if (niz.velicina() != dek.size())
            return false;
        if (!dek.empty() && (niz[0] != dek.front() || niz[niz.velicina() - 1] != dek.back()))
            return false;
    }

    for (std::size_t i = 0; i < dek.size(); ++i)
        if (niz[i] != dek[i])
            return false;

    return true;
}

int main(int argc, char* argv[])
{
    if (argc == 3 && std::string(argv[1]) == "test") {
        std::cout << (uporedi_sa_dekom(std::stoi(argv[2])) ? "OK" : "GRESKA") << std::endl;
        return 0;
    }

    matf::DvostraniNiz<int> niz;

    int q;
    std::cin >> q;
    for (int k = 0; k < q; ++k) {
        std::string komanda;
        std::cin >> komanda;
        if (komanda == "DP") {
            int x;
            std::cin >> x;
            niz.dodaj_na_pocetak(x);
        } else if (komanda == "DK") {
            int x;
            std::cin >> x;
            niz.dodaj_na_kraj(x);
        } else if (komanda == "OP") {
            niz.obrisi_sa_pocetka();
        } else if (komanda == "OK") {
            niz.obrisi_sa_kraja();
        } else if (komanda == "G") {
            std::size_t i;
            std::cin >> i;
            std::cout << niz[i] << std::endl;
        } else if (komanda == "I") {
            for (std::size_t i = 0; i < niz.velicina(); ++i)
                std::cout << niz[i] << " ";
            std::cout << std::endl;
        }
    }

    return 0;
}

Rešenje

main.cpp

#include <cassert>
#include <cstddef>
#include <deque>
#include <iostream>
#include <random>
#include <string>

namespace matf {

    // Niz u koji se dodaje i iz kog se brise na oba kraja u amortizovanom
    // vremenu O(1), uz pristup proizvoljnom elementu u vremenu O(1).
    template <typename T>
    class DvostraniNiz {
    private:
        // Invarijanta: elementi ukazuje na blok od kapacitet_ objekata, a
        // elementi niza su na pozicijama [pocetak_, pocetak_ + velicina_),
        // pa je pocetak_ + velicina_ <= kapacitet_; kapacitet_ > 0.
        T* elementi;
        std::size_t pocetak_;
        std::size_t velicina_;
        std::size_t kapacitet_;

        void povecaj_kapacitet();

    public:
        DvostraniNiz(std::size_t pocetni_kapacitet = 4);
        ~DvostraniNiz();

        DvostraniNiz(const DvostraniNiz& drugi) = delete;
        DvostraniNiz& operator=(const DvostraniNiz& drugi) = delete;

        std::size_t velicina() const;
        bool prazan() const;

        T& operator[](std::size_t indeks);
        const T& operator[](std::size_t indeks) const;

        void dodaj_na_pocetak(const T& vrednost);
        void dodaj_na_kraj(const T& vrednost);
        void obrisi_sa_pocetka();
        void obrisi_sa_kraja();
    };

    template <typename T>
    DvostraniNiz<T>::DvostraniNiz(std::size_t pocetni_kapacitet)
        : elementi(new T[pocetni_kapacitet]),
          pocetak_(pocetni_kapacitet / 2),
          velicina_(0),
          kapacitet_(pocetni_kapacitet)
    {
        assert(pocetni_kapacitet > 0);
    }

    template <typename T>
    DvostraniNiz<T>::~DvostraniNiz()
    {
        delete[] elementi;
    }

    template <typename T>
    std::size_t DvostraniNiz<T>::velicina() const
    {
        return velicina_;
    }

    template <typename T>
    bool DvostraniNiz<T>::prazan() const
    {
        return velicina_ == 0;
    }

    template <typename T>
    T& DvostraniNiz<T>::operator[](std::size_t indeks)
    {
        assert(indeks < velicina_);
        return elementi[pocetak_ + indeks];
    }

    template <typename T>
    const T& DvostraniNiz<T>::operator[](std::size_t indeks) const
    {
        assert(indeks < velicina_);
        return elementi[pocetak_ + indeks];
    }

    // Elementi se smestaju na sredinu dvostruko veceg bloka, pa posle
    // realokacije sa obe strane ostaje bar kapacitet_ / 2 slobodnih mesta.
    // Do sledece realokacije mora proci toliko dodavanja na jednom kraju,
    // sto daje amortizovano O(1).
    template <typename T>
    void DvostraniNiz<T>::povecaj_kapacitet()
    {
        std::size_t novi_kapacitet = 2 * kapacitet_;
        std::size_t novi_pocetak = (novi_kapacitet - velicina_) / 2;

        T* novi = new T[novi_kapacitet];

        for (std::size_t i = 0; i < velicina_; ++i)
            novi[novi_pocetak + i] = elementi[pocetak_ + i];

        delete[] elementi;

        elementi = novi;
        pocetak_ = novi_pocetak;
        kapacitet_ = novi_kapacitet;
    }

    // Kao kod DinamickiNiz::dodaj, vrednost moze biti element ovog niza,
    // pa se kopira pre realokacije.
    template <typename T>
    void DvostraniNiz<T>::dodaj_na_pocetak(const T& vrednost)
    {
        T v = vrednost;
        if (pocetak_ == 0)
            povecaj_kapacitet();

        --pocetak_;
        elementi[pocetak_] = v;
        ++velicina_;
    }

    template <typename T>
    void DvostraniNiz<T>::dodaj_na_kraj(const T& vrednost)
    {
        T v = vrednost;
        if (pocetak_ + velicina_ == kapacitet_)
            povecaj_kapacitet();

        elementi[pocetak_ + velicina_] = v;
        ++velicina_;
    }

    template <typename T>
    void DvostraniNiz<T>::obrisi_sa_pocetka()
    {
        assert(velicina_ > 0);
        ++pocetak_;
        --velicina_;
    }

    template <typename T>
    void DvostraniNiz<T>::obrisi_sa_kraja()
    {
        assert(velicina_ > 0);
        --velicina_;
    }

} // namespace matf

// Nasumicno poredjenje sa std::deque (u testu je STL dozvoljen).
bool uporedi_sa_dekom(int broj_operacija)
{
    std::mt19937 gen(12345);
    std::uniform_int_distribution<int> operacija(0, 5);
    std::uniform_int_distribution<int> vrednost(-1000, 1000);

    matf::DvostraniNiz<int> niz(1);
    std::deque<int> dek;

    for (int k = 0; k < broj_operacija; ++k) {
        int op = operacija(gen);
        if (op <= 1) {
            int x = vrednost(gen);
            niz.dodaj_na_pocetak(x);
            dek.push_front(x);
        } else if (op <= 3) {
            int x = vrednost(gen);
            niz.dodaj_na_kraj(x);
            dek.push_back(x);
        } else if (op == 4 && !dek.empty()) {
            niz.obrisi_sa_pocetka();
            dek.pop_front();
        } else if (op == 5 && !dek.empty()) {
            niz.obrisi_sa_kraja();
            dek.pop_back();
        }

        if (niz.velicina() != dek.size())
            return false;
        if (!dek.empty() && (niz[0] != dek.front() || niz[niz.velicina() - 1] != dek.back()))
            return false;
    }

    for (std::size_t i = 0; i < dek.size(); ++i)
        if (niz[i] != dek[i])
            return false;

    return true;
}

int main(int argc, char* argv[])
{
    if (argc == 3 && std::string(argv[1]) == "test") {
        std::cout << (uporedi_sa_dekom(std::stoi(argv[2])) ? "OK" : "GRESKA") << std::endl;
        return 0;
    }

    matf::DvostraniNiz<int> niz;

    int q;
    std::cin >> q;
    for (int k = 0; k < q; ++k) {
        std::string komanda;
        std::cin >> komanda;
        if (komanda == "DP") {
            int x;
            std::cin >> x;
            niz.dodaj_na_pocetak(x);
        } else if (komanda == "DK") {
            int x;
            std::cin >> x;
            niz.dodaj_na_kraj(x);
        } else if (komanda == "OP") {
            niz.obrisi_sa_pocetka();
        } else if (komanda == "OK") {
            niz.obrisi_sa_kraja();
        } else if (komanda == "G") {
            std::size_t i;
            std::cin >> i;
            std::cout << niz[i] << std::endl;
        } else if (komanda == "I") {
            for (std::size_t i = 0; i < niz.velicina(); ++i)
                std::cout << niz[i] << " ";
            std::cout << std::endl;
        }
    }

    return 0;
}