Isecanje opsega

Klasi DvostrukaLista dodati funkciju članicu

void iseci(Cvor* pocetak, Cvor* kraj_opsega, DvostrukaLista& druga);

koja čvorove iz opsega [pocetak, kraj_opsega) ove liste premešta na početak liste druga, u istom redosledu. Čvor pocetak pripada opsegu, a kraj_opsega ne pripada (može da bude i kraj()). Ako su pocetak i kraj_opsega isti, ništa se ne menja.

Funkcija ne sme da pravi ni da briše čvorove, niti da prepisuje podatke. Pokazivači se menjaju u $O(1)$, nezavisno od dužine opsega.

Funkcija proveri_invarijantu iz zadatka 1 već je data u postavci.

Pitanja za razmišljanje: Koliko pokazivača se menja? Šta je jedini razlog da cela funkcija ne bude $O(1)$? Zašto je zbog toga i std::list::splice za opseg iz druge liste linearan?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva prve liste. Zatim se na isti način učitava broj m $(0 \le m \le 10^5)$ i m celih brojeva druge liste. Na kraju se učitavaju brojevi l i r $(0 \le l \le r \le n)$: pocetak je čvor prve liste sa indeksom l, a kraj_opsega čvor sa indeksom r, brojano od 0 (za r = n to je kraj()).

Izlaz

U prvom redu ispisati prvu listu, u drugom drugu, a u trećem njihove veličine. U četvrtom redu program ispisuje da ako je invarijanta obe liste očuvana, a ne inače.

Primer

Ulaz

6
1 2 3 4 5 6
2
7 8
2 4

Izlaz

1 2 5 6
3 4 7 8
4 4
da

Primer

Ulaz

5
10 20 30 40 50
0
0 5

Izlaz


10 20 30 40 50
0 5
da

Postavka

dvostruka_lista.h

#ifndef DVOSTRUKA_LISTA_H
#define DVOSTRUKA_LISTA_H

#include <cassert>
#include <cstddef>

// Dvostruko povezana lista sa sentinel-cvorom iz glave 4.
//
// Sentinel-cvor stoji izmedju poslednjeg i prvog elementa, pa cvorovi
// cine krug. U praznoj listi sentinel pokazuje sam na sebe. Zahvaljujuci
// tome nijedan pokazivac nije nullptr i umetanje i brisanje nemaju
// posebnih slucajeva.
//
// Pored operacija iz knjige, klasa ima i nekoliko koje se iz njih lako
// izvode, kao i iterator (vidi odeljak o iteratorima u glavi i README).
//
// Tip T mora da podrzava kopiranje i podrazumevano konstruisanje (zbog
// polja podatak u sentinel-cvoru). Funkcija pronadji zahteva operator ==.
//
// Invarijanta:
//   Za svaki cvor c, ukljucujuci i sentinel, vazi
//   c->sledeci->prethodni == c i c->prethodni->sledeci == c.
//   Izmedju dva prolaska kroz sentinel nalazi se tacno velicina_ cvorova.

template <typename T>
class DvostrukaLista {
public:
    struct Cvor {
        T podatak;
        Cvor* prethodni;
        Cvor* sledeci;

        Cvor() : podatak(), prethodni(this), sledeci(this) {}
        Cvor(const T& p, Cvor* pre, Cvor* sl)
            : podatak(p), prethodni(pre), sledeci(sl) {}
    };

    class Iterator;

    DvostrukaLista() : sentinel(new Cvor()), velicina_(0) {}

    ~DvostrukaLista()
    {
        isprazni();
        delete sentinel;
    }

    DvostrukaLista(const DvostrukaLista&) = delete;
    DvostrukaLista& operator=(const DvostrukaLista&) = delete;

    bool prazna() const { return sentinel->sledeci == sentinel; }
    std::size_t velicina() const { return velicina_; }

    Cvor* prvi() const { return sentinel->sledeci; }
    Cvor* poslednji() const { return sentinel->prethodni; }
    Cvor* kraj() const { return sentinel; }

    void umetni_ispred(Cvor* c, const T& x);
    void obrisi(Cvor* c);

    void dodaj_na_pocetak(const T& x) { umetni_ispred(prvi(), x); }
    void dodaj_na_kraj(const T& x) { umetni_ispred(kraj(), x); }
    void umetni_iza(Cvor* c, const T& x) { umetni_ispred(c->sledeci, x); }

    void obrisi_sa_pocetka() { obrisi(prvi()); }
    void obrisi_sa_kraja() { obrisi(poslednji()); }
    void isprazni();

    void iseci(Cvor* pocetak, Cvor* kraj_opsega, DvostrukaLista& druga);

    Cvor* pronadji(const T& x) const;

    bool proveri_invarijantu() const;

    Iterator begin() const { return Iterator(prvi()); }
    Iterator end() const { return Iterator(kraj()); }

private:
    Cvor* sentinel;
    std::size_t velicina_;
};


// -----------------------------------------------------------------------------
// Iterator
//
// Iterator cuva pokazivac na cvor, ali ga ne otkriva korisniku: dozvoljava
// samo pristup podatku i prelazak na susedni cvor. Zahvaljujuci funkcijama
// begin() i end(), lista moze da se obilazi i petljom
//     for (int x : lista) ...
// Kao i kod std::list, end() je pozicija sentinel-cvora.
// -----------------------------------------------------------------------------

template <typename T>
class DvostrukaLista<T>::Iterator {
public:
    explicit Iterator(Cvor* c) : trenutni(c) {}

    T& operator*() const { return trenutni->podatak; }

    Iterator& operator++()
    {
        trenutni = trenutni->sledeci;
        return *this;
    }

    Iterator& operator--()
    {
        trenutni = trenutni->prethodni;
        return *this;
    }

    bool operator==(const Iterator& drugi) const { return trenutni == drugi.trenutni; }
    bool operator!=(const Iterator& drugi) const { return trenutni != drugi.trenutni; }

private:
    Cvor* trenutni;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------

template <typename T>
void DvostrukaLista<T>::umetni_ispred(Cvor* c, const T& x)
{
    Cvor* novi = new Cvor(x, c->prethodni, c);
    c->prethodni->sledeci = novi;   // jos se koristi stara vrednost c->prethodni
    c->prethodni = novi;
    ++velicina_;
}

template <typename T>
void DvostrukaLista<T>::obrisi(Cvor* c)
{
    assert(c != sentinel);
    c->prethodni->sledeci = c->sledeci;
    c->sledeci->prethodni = c->prethodni;
    delete c;
    --velicina_;
}

template <typename T>
void DvostrukaLista<T>::isprazni()
{
    while (!prazna())
        obrisi(prvi());
}

// Cvor je tip definisan unutar sablona, pa se van klase njegovo ime pise
// kao typename DvostrukaLista<T>::Cvor. Rec typename kaze prevodiocu da je
// to ime tipa.
template <typename T>
typename DvostrukaLista<T>::Cvor* DvostrukaLista<T>::pronadji(const T& x) const
{
    for (Cvor* p = prvi(); p != kraj(); p = p->sledeci)
        if (p->podatak == x)
            return p;
    return nullptr;
}


// TODO: Cvorove iz opsega [pocetak, kraj_opsega) ove liste premesta na
// pocetak liste druga, u istom redosledu.
template <typename T>
void DvostrukaLista<T>::iseci(Cvor* pocetak, Cvor* kraj_opsega, DvostrukaLista& druga)
{
    // Ovde ide vasa implementacija
}

// Obilazi listu od sentinela, proverava obe veze svakog cvora i broji cvorove.
// Obilazak je ogranicen sa velicina_, pa se zavrsava i kada je lanac sledeci
// pokvaren.
template <typename T>
bool DvostrukaLista<T>::proveri_invarijantu() const
{
    Cvor* c = sentinel;
    std::size_t broj = 0;
    do {
        if (c->sledeci->prethodni != c || c->prethodni->sledeci != c)
            return false;
        c = c->sledeci;
        ++broj;
    } while (c != sentinel && broj <= velicina_);

    return c == sentinel && broj == velicina_ + 1;
}

#endif

main.cpp

#include <iostream>

#include "dvostruka_lista.h"

template <typename T>
void ispisi(const DvostrukaLista<T>& l)
{
    for (auto p = l.prvi(); p != l.kraj(); p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

void ucitaj(DvostrukaLista<int>& l)
{
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        l.dodaj_na_kraj(x);
    }
}

// Vraca cvor sa indeksom i (brojano od 0); za i == velicina() to je kraj().
DvostrukaLista<int>::Cvor* cvor_na_poziciji(const DvostrukaLista<int>& l, int i)
{
    auto p = l.prvi();
    for (int j = 0; j < i; ++j)
        p = p->sledeci;
    return p;
}

int main()
{
    DvostrukaLista<int> a, b;
    ucitaj(a);
    ucitaj(b);

    int l, r;
    std::cin >> l >> r;

    a.iseci(cvor_na_poziciji(a, l), cvor_na_poziciji(a, r), b);

    ispisi(a);
    ispisi(b);
    std::cout << a.velicina() << " " << b.velicina() << std::endl;

    bool ispravno = a.proveri_invarijantu() && b.proveri_invarijantu();
    std::cout << (ispravno ? "da" : "ne") << std::endl;

    return 0;
}