#include <iostream>
using namespace std;

class P {
   public:
      int hodnota;
      P *predchozi, *dalsi;
      P(int hodnota, P * predchozi, P * dalsi) :
         hodnota(hodnota), predchozi(predchozi), dalsi(dalsi) {}
};

class S {
   protected:
      P * prvni;
   public:
      virtual void pridejNaZacatek(int hodnota);
      virtual void odeberPrvniPrvek();
      void vypisPrvky(const char * textPred = NULL, const char * textZa = NULL);
      bool neniPrazdny();
      S() : prvni(NULL) {}
      virtual ~S();
};


class S2 : public S {
   protected:
      int pocet;
      P * posledni;
   public:
      virtual void pridejNaZacatek(int hodnota);
      virtual void odeberPrvniPrvek();
      int pocetPrvku() {return pocet;}
      void pridejNaKonec(int hodnota);
      void odeberPosledni();
      S2 & pripojSeNaKonec(S2 & ceho);
      S2 & duplikat();
      bool jeShodnyS(S2 & cim);
      bool jeUsporadany();
      S2() : pocet(0), posledni(NULL) {}
};


class S3 : public S2 {
   public:
      S3 & pripojSeNaKonec(S3 & ceho);
      S3 & duplikat();
      int najdiPrvek(int hodnota);
      void vlozZaCo(int za, int co);
      void smazat(int hodnota);
      void inverze();
};


class S4 : public S3 {
   public:
      S4 & pripojSeNaKonec(S4 & ceho);
      S4 & duplikat();
      void vyprazdnit();
      void rozdel(int x, S4 & a, S4 & b);
};

// destruktor tridy "S" - smaze vsechny prvky
S::~S() {
   while (neniPrazdny()) odeberPrvniPrvek();
}

// prida na zacatek seznamu prvek s danou hodnotou
void S::pridejNaZacatek(int hodnota) {
   prvni = new P(hodnota, NULL, prvni);
   if (prvni->dalsi != NULL)
      prvni->dalsi->predchozi = prvni;
}

// odebere ze seznamu prvni prvek
void S::odeberPrvniPrvek() {
   if (!neniPrazdny()) throw "Seznam je prazdny!";
   P * smazat = prvni;
   prvni = prvni->dalsi;
   if (prvni != NULL) prvni->predchozi = NULL;
   delete smazat;
}

// vypise prvky na obrazovku
// navic je mozne zadat text, ktery se zobrazi pred a za seznamem
void S::vypisPrvky(const char * textPred, const char * textZa) {
   cout << textPred;
   for (P * pom = prvni; pom != NULL; pom=pom->dalsi) {
      if (pom != prvni) cout << ",";
      cout << pom->hodnota;
   }
   cout << textZa;
}

// test, zda seznam neni prazdny
bool S::neniPrazdny() {
   return prvni != NULL;
}

// prida na zacatek seznamu prvek s danou hodnotou
void S2::pridejNaZacatek(int hodnota) {
   S::pridejNaZacatek(hodnota);
   pocet++;
   if (pocet==1) posledni = prvni;
}

// odebere ze seznamu prvni prvek
void S2::odeberPrvniPrvek() {
   S::odeberPrvniPrvek();
   pocet--;
   if (pocet==0) posledni = NULL;
}

// prida na konec seznamu prvek s danou hodnotou
void S2::pridejNaKonec(int hodnota) {
   if (pocet == 0) {
      prvni = new P(hodnota, NULL, NULL);
      posledni = prvni;
   }
   else {
      posledni->dalsi = new P(hodnota, posledni, NULL);
      posledni = posledni->dalsi;
   }
   pocet++;
}

// odebere ze seznamu posledni prvek
void S2::odeberPosledni() {
   if (pocet==0)
      throw "Seznam je prazdny!!!";
   if (pocet==1) {
      delete posledni;
      prvni = NULL;
      posledni = NULL;
   }
   else {
      posledni = posledni->predchozi;
      delete posledni->dalsi;
      posledni->dalsi = 0;
   }
   pocet--;
}

// zkopiruje svoje prvky na konec daneho seznamu
// navratova hodnota je shodna se vstupnim seznamem
S2 & S2::pripojSeNaKonec(S2 & ceho) {
   for (P * pom = prvni; pom != NULL; pom=pom->dalsi)
      ceho.pridejNaKonec(pom->hodnota);
   return ceho;
}
S3 & S3::pripojSeNaKonec(S3 & ceho) {
   S2::pripojSeNaKonec(ceho);
   return ceho;
}
S4 & S4::pripojSeNaKonec(S4 & ceho) {
   S3::pripojSeNaKonec(ceho);
   return ceho;
}

// vytvori novy seznam a zkopiruje do nej svoje prvky
S2 & S2::duplikat() {
   return pripojSeNaKonec(*(new S2));
}
S3 & S3::duplikat() {
   return pripojSeNaKonec(*(new S3));
}
S4 & S4::duplikat() {
   return pripojSeNaKonec(*(new S4));
}

// test, zda je posloupnost shodna s danou posloupnosti
bool S2::jeShodnyS(S2 & cim) {
   if (pocet != cim.pocetPrvku()) return false;
   P * pom1 = prvni;
   P * pom2 = cim.prvni;
   while (pom1 != NULL) {
      if (pom1->hodnota != pom2->hodnota) return false;
      pom1 = pom1->dalsi;
      pom2 = pom2->dalsi;
   }
   return true;
}

// vraci TRUE, pokud je posloupnost neklesajici nebo nerostouci
bool S2::jeUsporadany() {
   bool roste = false;
   bool klesa = false;
   for (P * pom = prvni; pom != posledni; pom=pom->dalsi) {
      int rozdil = pom->dalsi->hodnota - pom->hodnota;
      if (rozdil > 0) roste = true;
      if (rozdil < 0) klesa = true;
      if (roste && klesa) return false;
   }
   return true;
}

// najde prvni vyskyt prvku a vrati jeho index (pocitano od nuly)
// pokud hodnotu nenajde, vrati -1
int S3::najdiPrvek(int hodnota) {
   P * pom = prvni;
   int i = 0;
   while (pom != NULL) {
      if (pom->hodnota == hodnota) return i;
      pom = pom->dalsi;
      i++;
   }
   return -1;
}

// vlozi hodnotu "co" za prvni prvek s hodnotou "za"
// pokud prvek "za" nenajde, prida "co" na konec seznamu
void S3::vlozZaCo(int za, int co) {
   for (P * pom = prvni; pom != posledni; pom=pom->dalsi)
      if (pom->hodnota == za) {
         pom->dalsi = new P(co, pom, pom->dalsi);
         pom->dalsi->dalsi->predchozi = pom->dalsi;
         pocet++;
         return;
      }
   pridejNaKonec(co);
}

// smaze prvni prvek s hodnotou "hodnota"
void S3::smazat(int hodnota) {
   for (P * pom = prvni; pom != NULL; pom=pom->dalsi)
      if (pom->hodnota == hodnota) {
         if (pom == prvni) {odeberPrvniPrvek(); return;} 
         if (pom == posledni) {odeberPosledni(); return;} 
         pom->predchozi->dalsi = pom->dalsi;
         pom->dalsi->predchozi = pom->predchozi;
         delete pom;
         pocet--;
         return;
      }
}

// prehazi prvky do opacneho poradi
void S3::inverze() {
   P * pom1 = prvni;
   P * pom2 = posledni;
   for (int i=0; i<pocet/2; i++) {
      int x = pom1->hodnota;
      pom1->hodnota = pom2->hodnota;
      pom2->hodnota = x;
      pom1 = pom1->dalsi;
      pom2 = pom2->predchozi;
   }
}

// vymaze ze seznamu vsechny prvky
void S4::vyprazdnit() {
   while (neniPrazdny()) odeberPrvniPrvek();
}

// zkopiruje svoje prvky tak, ze cisla mensi nez "x"
// budou v seznamu "a" a ostatni prvky v seznamu "b"
void S4::rozdel(int x, S4 & a, S4 & b) {
   a.vyprazdnit();
   b.vyprazdnit();
   for (P * pom = prvni; pom != NULL; pom=pom->dalsi)
      if (pom->hodnota < x)
         a.pridejNaKonec(pom->hodnota);
      else
         b.pridejNaKonec(pom->hodnota);
}

// hlavni metoda programu
int main(int argc, char* argv[]) {
   try {

      // test tridy S
      S s;
      s.vypisPrvky("prazdny: ", "\n");
      //s.odeberPrvniPrvek(); // test, jestli oznami, ze je seznam prazdny
      for (int i=1; i<=10; i++)
         s.pridejNaZacatek(i);
      s.vypisPrvky("prvky 1..10: ", "\n");
      s.odeberPrvniPrvek();
      s.odeberPrvniPrvek();
      s.vypisPrvky("prvni dva odebrany: ", "\n");
      cout << "---------------------------\n";

      // test tridy S2
      S4 a;
      for (int i=0; i<10; i++)
         a.pridejNaKonec(i);
      a.vypisPrvky("a=0..9: ", "\n");
      a.odeberPrvniPrvek();
      a.vypisPrvky("a=1..9: ", "\n");
      S4 b = a.duplikat();
      b.vypisPrvky("b=1..9: ", "\n");
      cout << "a==b: " << a.jeShodnyS(b) << endl;
      cout << "a.jeUsporadany: " << a.jeUsporadany() << endl;
      a.odeberPosledni();
      a.vypisPrvky("a=1..8: ", "\n");
      a.pridejNaZacatek(10);
      a.vypisPrvky("a=10,1..8: ", "\n");
      cout << "a.pocetPrvku: " << a.pocetPrvku() << endl;
      cout << "a.jeUsporadany: " << a.jeUsporadany() << endl;
      S4 c = b.pripojSeNaKonec(a.duplikat());
      c.vypisPrvky("c=a+b: ", "\n");
      cout << "c.pocetPrvku: " << c.pocetPrvku() << endl;

      // test tridy S3
      cout << "c: index prvku 4: " << c.najdiPrvek(4) << endl;
      cout << "c: index prvku 40: " << c.najdiPrvek(40) << endl;
      c.smazat(4);
      c.vypisPrvky("c: smazan prvek 4: ", "\n");
      cout << "c: index prvku 4: " << c.najdiPrvek(4) << endl;
      c.vlozZaCo(4, 40);
      c.vypisPrvky("c: za 4 vlozeno 40: ", "\n");
      c.inverze();
      c.vypisPrvky("c: inverze: ", "\n");

      // test tridy S4
      c.rozdel(9, a, b);
      a.vypisPrvky("a: prvky z 'c' <9: ", "\n");
      b.vypisPrvky("b: prvky z 'c' >=9: ", "\n");
   }
   catch (const char * chyba) {
      cout << "CHYBA!!! " << chyba << endl;
   }
   cout << "\nStisknete ENTER";
   getchar();
   return 0;
}