Neuređena kolekcija

Implementirati tip podataka NeuredjenaKolekcija koji predstavlja multiskup (skup sa mogućim ponavljanjima) celih brojeva, korišćenjem neuređenog niza fiksnog kapaciteta.

Reprezentacija: velicina je trenutni broj elemenata; elementi se čuvaju u nizu elementi na pozicijama 0 .. velicina - 1, u proizvoljnom redosledu; KAPACITET niza je fiksan.

Operacije:

void dodaj(NeuredjenaKolekcija& k, int x) — dodaje jedno pojavljivanje x. Preduslov: k.velicina < KAPACITET.
bool sadrzi(const NeuredjenaKolekcija& k, int x) — vraća true ako se x nalazi u kolekciji, bar jednom.
void obrisi(NeuredjenaKolekcija& k, int x) — uklanja jedno pojavljivanje x, ako postoji; u suprotnom ne radi ništa. Element se uklanja tako što se pronađena pozicija prepiše poslednjim elementom niza (bez pomeranja ostalih elemenata).
void ispisi(const NeuredjenaKolekcija& k) — ispisuje sve elemente, onim redom kojim se nalaze u nizu.

Napomena: Zbog ovakvog brisanja, redosled elemenata u nizu je određen istorijom poziva dodaj/obrisi (semantički nebitan za samu kolekciju), pa test primeri proveravaju tačno taj redosled.

Zadaci:

Definisati invarijantu strukture.
Implementirati funkcije: dodaj, sadrzi, obrisi, ispisi. Savet: definisati pomoćnu funkciju std::size_t pozicija(const NeuredjenaKolekcija& k, int x), koja vraća indeks elementa x ako se x nalazi u kolekciji, inače vraća veličinu kolekcije.
Proveriti da li invarijanta strukture važi u odnosu na implementirane funkcije.
Odrediti najgoru vremensku složenost implementiranih funkcija.

Ulaz

U prvom redu se učitava broj upita $q$ $(1 \le q \le 1000)$. Kapacitet kolekcije je $1000$.

Svaki od narednih $q$ redova sadrži jedan od upita:

D x — dodaj(k, x) $(-10^9 \le x \le 10^9)$
B x — obrisi(k, x)
S x — sadrzi(k, x)
V — k.velicina
I — ispisi(k)

Garantovano je da broj upita tipa D ne prelazi KAPACITET.

Izlaz

Za upit S x ispisati DA ako kolekcija sadrži x, ili NE u suprotnom.

Za upit V ispisati trenutan broj elemenata.

Za upit I ispisati, u jednom redu, sve elemente kolekcije razdvojene razmakom, onim redosledom kojim se nalaze u nizu. Ako je kolekcija prazna ispisati samo novi red.

Upiti D i B ne proizvode izlaz.

Primer

Ulaz

21
D 12
D 4
D 9
D 4
D 17
D 6
I
V
S 9
S 8
B 12
I
B 4
V
S 4
B 4
V
S 4
B 100
V
I

Izlaz

12 4 9 4 17 6
6
DA
NE
6 4 9 4 17
4
DA
3
NE
3
6 17 9

Postavka

`main.cpp`

#include <cassert>
#include <cstddef>
#include <iostream>

namespace matf 
{
  const std::size_t KAPACITET = 1000;

  struct NeuredjenaKolekcija {
    int elementi[KAPACITET];
    std::size_t velicina = 0;
    // TODO (1): napisati invarijantu ovde, kao komentar
  };

  // TODO (2): implementirati dodaj, sadrzi, obrisi i ispisi.

  // preduslov: k.velicina < KAPACITET
  void dodaj(NeuredjenaKolekcija& k, int x);
  bool sadrzi(const NeuredjenaKolekcija& k, int x);
  void obrisi(NeuredjenaKolekcija& k, int x);
  void ispisi(const NeuredjenaKolekcija& k);

  // Preporuka: pomocna funkcija
  //  std::size_t pozicija(const NeuredjenaKolekcija& k, int x)

  // TODO (3): proveriti invarijantu u odnosu na definisane funkcije, kao komentar

  // TODO (4): napisati najgoru vremensku slozenost svake funkcije, kao komentar

}; // namespace matf

int main()
{
  int q;
  std::cin >> q;

  matf::NeuredjenaKolekcija k;
  while (q--) {
    char op;
    std::cin >> op;
    if (op == 'D') {
      int x;
      std::cin >> x;
      matf::dodaj(k, x);
    } else if (op == 'B') {
      int x;
      std::cin >> x;
      matf::obrisi(k, x);
    } else if (op == 'S') {
      int x;
      std::cin >> x;
      std::cout << (matf::sadrzi(k, x) ? "DA" : "NE") << '\n';
    } else if (op == 'V') {
      std::cout << k.velicina << '\n';
    } else if (op == 'I') {
      matf::ispisi(k);
    }
  }

  return 0;
}

Rešenje

`main.cpp`

#include <cassert>
#include <cstddef>
#include <iostream>

namespace matf 
{
  const std::size_t KAPACITET = 1000;

  struct NeuredjenaKolekcija {
    int elementi[KAPACITET];
    std::size_t velicina = 0;
    // invarijanta: 0 <= velicina <= KAPACITET, i pozicije
    // 0 .. velicina - 1 sadrze tacno elemente kolekcije,
    // u proizvoljnom redosledu
    // Inicijalno invarijanta vazi jer velicina = 0
  };

  // O(velicina)
  // Kolekcija ostaje nepromenjena zbog const&, pa invarijanta vazi.
  std::size_t pozicija(const NeuredjenaKolekcija& k, int x)
  {
    for (std::size_t i = 0; i < k.velicina; ++i)
      if (k.elementi[i] == x)
        return i;
    return k.velicina;
  }

  // O(1);
  // Invarijanta vazi zbog assert(k.velicina < KAPACITET)
  void dodaj(NeuredjenaKolekcija& k, int x)
  {
    assert(k.velicina < KAPACITET);
    k.elementi[k.velicina] = x;
    ++k.velicina;
  }

  // O(velicina)
  // Kolekcija ostaje nepromenjena zbog const&, pa invarijanta vazi.
  bool sadrzi(const NeuredjenaKolekcija& k, int x)
  {
    return pozicija(k, x) < k.velicina;
  }

  // O(velicina)
  // Invarijanta vazi po slucajevima kada i == k.velicina i kada i != k.velicina.
  // Slucaj kada k.velicina == 0 upada u prvi slucaj, jer je tada i == 0.
  void obrisi(NeuredjenaKolekcija& k, int x)
  {
    std::size_t i = pozicija(k, x);
    if (i == k.velicina)
      return;
    k.elementi[i] = k.elementi[k.velicina - 1];
    --k.velicina;
  }

  // O(velicina)
  // Kolekcija ostaje nepromenjena zvog const&, pa invarijanta vazi.
  void ispisi(const NeuredjenaKolekcija& k)
  {
    for (std::size_t i = 0; i < k.velicina; ++i)
      std::cout << k.elementi[i] << ' ';
    std::cout << std::endl;
  }

}; // namespace matf

int main()
{
  int q;
  std::cin >> q;

  matf::NeuredjenaKolekcija k;
  while (q--) {
    char op;
    std::cin >> op;
    if (op == 'D') {
      int x;
      std::cin >> x;
      matf::dodaj(k, x);
    } else if (op == 'B') {
      int x;
      std::cin >> x;
      matf::obrisi(k, x);
    } else if (op == 'S') {
      int x;
      std::cin >> x;
      std::cout << (matf::sadrzi(k, x) ? "DA" : "NE") << std::endl;
    } else if (op == 'V') {
      std::cout << k.velicina << std::endl;
    } else if (op == 'I') {
      matf::ispisi(k);
    }
  }

  return 0;
}