#include
#include
#include
#include
#include
#include
#include
using namespace std;

// Źródło kodu do licznika czasu: http://stackoverflow.com/questions/1739259/how-to-use-queryperformancecounter
double PCFreq = 0.0;
__int64 licznik = 0;


void czasStart()
{
LARGE_INTEGER li;
if (!QueryPerformanceFrequency(&li))
cout << "Błąd!\n";

PCFreq = double(li.QuadPart) / 1000.0;

QueryPerformanceCounter(&li);
licznik = li.QuadPart;
}
void pobierzCzas()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
cout << "Operacja zajela: " << (li.QuadPart - licznik) / PCFreq << " milisekund" << endl;

}

class ElementListy
{
public:
ElementListy *nastepnyElement, *poprzedniElement;
int klucz;
};
class Lista
{
private:
ElementListy *glowa, *ogon;
public:
int liczbaElementow;
public:
Lista()
{

ogon = glowa = NULL;
liczbaElementow = 0;

}
~Lista()
{
ElementListy * element;

while (glowa)
{
element = glowa->nastepnyElement;
delete glowa;
glowa = element;
}
liczbaElementow = 0;
}
void zapelnijLosowo(int ile)
{
for (int i = 1; i <= ile; i++)
dodajNaPoczatek((rand() % 2000) - 1000);
}
bool szukaj(int liczbaDoZnalezienia)
{
bool czyJest = false;
ElementListy *element;
element = glowa;
for (int i = 1; i <= liczbaElementow; i++)
{
if (element->klucz == liczbaDoZnalezienia) { czyJest = true; break; }
else element = element->nastepnyElement;
}
return czyJest;
}
void zbudujZPliku(string nazwa)
{
string s;
int i = 1;
nazwa = nazwa + ".txt";
ifstream plik(nazwa);
if (!plik)
cout << "Nie mozna otworzyc pliku" << endl;
else
{
getline(plik, s);
int n = atoi(s.c_str());

while (!plik.eof())
{
if (i <= n)

{
getline(plik, s);
int klucz = atoi(s.c_str());
dodajNaKoniec(klucz);
i++;
}
else break;
}
plik.close();
for (i; i <= n; i++)
{
dodajNaKoniec(0);
}
}

}
void dodajNowyElementZaElementemOPodanymKluczu(int kluczElementuZaKtorymWstawiamy, int nowyKlucz)
{
licznik = 0;
czasStart();
ElementListy *element;
ElementListy * nowyElement = new ElementListy();
if (!(szukaj(kluczElementuZaKtorymWstawiamy)))
{
dodajNaPoczatek(nowyKlucz);
cout << "Na liscie nie ma elementu o podanej wartosci - wstawiono na poczatek listy" << endl;
}
else
{
element = glowa;
for (unsigned i = 1; i <= liczbaElementow; i++)
{
if (element->klucz == kluczElementuZaKtorymWstawiamy)
{
nowyElement->nastepnyElement = element->nastepnyElement; nowyElement->poprzedniElement = element;
element->nastepnyElement = nowyElement;
if (nowyElement->nastepnyElement) nowyElement->nastepnyElement->poprzedniElement = nowyElement;
else ogon = nowyElement;
nowyElement->klucz = nowyKlucz;
liczbaElementow++;
break;
}
else element = element->nastepnyElement;
}

}
pobierzCzas();
}
void dodajNaPoczatek(int nowyKlucz)
{
ElementListy * nowyElement = new ElementListy();
nowyElement->nastepnyElement = glowa;
nowyElement->poprzedniElement = NULL;
if (glowa) glowa->poprzedniElement = nowyElement;
glowa = nowyElement;
if (!ogon) ogon = glowa;
nowyElement->klucz = nowyKlucz;
liczbaElementow++;
}
void dodajNaKoniec(int nowyKlucz)
{
ElementListy * nowyElement = new ElementListy();
nowyElement->poprzedniElement = ogon;
nowyElement->nastepnyElement = NULL;
if (ogon) ogon->nastepnyElement = nowyElement;
ogon = nowyElement;
if (!glowa) glowa = ogon;
nowyElement->klucz = nowyKlucz;
liczbaElementow++;
}
void usunZPoczatku()
{
if (liczbaElementow == 0) cout << "Lista jest pusta, nie mozna nic usunac" << endl;
else
{
licznik = 0;
czasStart();
glowa = glowa->nastepnyElement;
liczbaElementow--;
pobierzCzas();
}

}

void usunZKonca()
{
if (liczbaElementow == 0) cout << "Lista jest pusta, nie mozna nic usunac" << endl;
else
{
licznik = 0;
czasStart();
ogon->poprzedniElement->nastepnyElement = NULL;
ogon->poprzedniElement = ogon;
liczbaElementow--;
pobierzCzas();
}
}
void usun(int kluczDoUsuniecia)
{
ElementListy *element;
element = glowa;
if (liczbaElementow == 0) cout << "Lista jest pusta, nie mozna nic usunac" << endl;
else
{
licznik = 0;
czasStart();
while ((element->nastepnyElement != NULL) && (element->klucz != kluczDoUsuniecia)) { element = element->nastepnyElement; }
if (element->klucz == kluczDoUsuniecia)
{
if (element->nastepnyElement) element->nastepnyElement->poprzedniElement = element->poprzedniElement;
else ogon = element->poprzedniElement;
if (element->poprzedniElement) { element->poprzedniElement->nastepnyElement = element->nastepnyElement; }
else glowa = element->nastepnyElement;
liczbaElementow--;
pobierzCzas();
}
else cout << "Na liscie nie ma elementu o podanym kluczu!" << endl;
}
}
void wyswietl()
{
ElementListy * element = new ElementListy();
int i = 1;
if (!glowa) cout << "Lista jest pusta." << endl;
else
{
element = glowa;
while (element)
{
cout << i << ". " << element->klucz << endl;
element = element->nastepnyElement;
i++;
}
cout << endl;

}
delete element;
}
};
class Tablica
{
public:
int liczbaElementow;
private:
int *w;
public: Tablica()
{
liczbaElementow = 0;
w = new int[liczbaElementow];
}
~Tablica()
{
delete[]w;
liczbaElementow = 0;
}
void zapelnijLosowo(int ile)
{
liczbaElementow = ile;
w = new int[2*liczbaElementow];
for (int i = 0; i < liczbaElementow; i++)
{
w[i] = ((rand() % 2000) - 1000);
}

}
void wyswietl()
{
if (liczbaElementow == 0) cout << "Tablica jest pusta" << endl;
else
{
for (int i = 0; i < liczbaElementow; i++){ cout << i << ": " << w[i] << endl; }
cout << endl;
}
}

void usun(int indeksElDoUsuniecia)
{
if (liczbaElementow == 0) { cout << "Tablica jest pusta, nie mozna nic usunac" << endl; }
else if (indeksElDoUsuniecia >= liczbaElementow) cout << "Tablica ma mniej elementow!" << endl;
else{
licznik = 0;
czasStart();
for (int i = indeksElDoUsuniecia; i < liczbaElementow; i++)
{
w[i] = w[i + 1];

}

liczbaElementow--;
pobierzCzas();
relokuj();
}
}
void relokuj()

{
int *t = new int[liczbaElementow];
for (int i = 0; i < liczbaElementow; i++)
{
t[i] = w[i];
}
w = new int[2*liczbaElementow];
for (int i = 0; i < liczbaElementow; i++)
{
w[i] = t[i];
}
delete[]t;
}
void usunZPoczatku()
{
if (liczbaElementow == 0) { cout << "Tablica jest pusta, nie mozna nic usunac" << endl; }
else
{
licznik = 0;
czasStart();
liczbaElementow--;
for (int i = 0; i < liczbaElementow; i++)
{
w[i] = w[i + 1];
}
relokuj();
pobierzCzas();
}

}

void usunZKonca()
{
if (liczbaElementow == 0) { cout << "Tablica jest pusta, nie mozna nic usunac" << endl; }

else
{
licznik = 0;
czasStart();
w[liczbaElementow - 1] = NULL;
liczbaElementow--;
pobierzCzas();
relokuj();
}
}
void dodajNaPoczatek(int wartoscNowegoElementu)
{
liczbaElementow++;

for (int i = liczbaElementow - 1; i > 0; i--)
{
w[i] = w[i - 1];
}
w[0] = wartoscNowegoElementu;
relokuj();
}
void dodajNaKoniec(int wartoscNowegoElementu)
{
licznik = 0;
czasStart();
w[liczbaElementow] = wartoscNowegoElementu;
liczbaElementow++;
pobierzCzas();
relokuj();

}
void dodaj(int indeksNowegoEl, int wartoscNowegoElementu)
{


if (indeksNowegoEl >= liczbaElementow)
{

dodajNaKoniec(wartoscNowegoElementu);
cout << "Podano indeks wykraczajacy poza rozmiar tablicy. Element zostal dodany na koncu tablicy" << endl;
}
else
{
licznik = 0;
czasStart();
liczbaElementow++;
for (int i = liczbaElementow - 1; i > indeksNowegoEl; i--)
{
w[i] = w[i - 1];
}
w[indeksNowegoEl] = wartoscNowegoElementu;
pobierzCzas();
//relokuj();
}

}
void szukaj(int liczbaDoZnalezienia)
{
licznik = 0;
czasStart();
bool czyJest = false;
for (int i = 0; i < liczbaElementow; i++){ if (liczbaDoZnalezienia == w[i]) { czyJest = true; break; } }
pobierzCzas();
if (czyJest) cout << "Szukany element znajduje sie w tablicy" << endl;
if (!czyJest) cout << "Szukego elementu nie ma w tablicy" << endl;

}
void zbudujZPliku(string nazwa)
{
string s;
int i = 0;

nazwa = nazwa + ".txt";
ifstream plik(nazwa);

if (!plik)
{
cout << "Nie mozna otworzyc pliku" << endl;;

}
else
{
getline(plik, s);
int n = atoi(s.c_str());
liczbaElementow = n;
while (!plik.eof())
{
if (i < liczbaElementow)
{
getline(plik, s);
w[i] = atoi(s.c_str());
i++;
}
else break;

}
plik.close();
for (i; i < liczbaElementow; i++)
{
w[i] = 0;
}
}

}
};
class Kopiec
{
public:
int liczbaElementow;
private:
int *w;
string gornyRog, dolnyRog, pion;
public:
Kopiec()
{
gornyRog = dolnyRog = pion = " ";
gornyRog[0] = 218; gornyRog[1] = 196;
dolnyRog[0] = 192; dolnyRog[1] = 196;
pion[0] = 179;
liczbaElementow = 0;
w = new int[liczbaElementow + 1];
}
~Kopiec()
{
liczbaElementow = 0;
delete[]w;

}
void zapelnijLosowo(int ile)
{
liczbaElementow = ile;
w = new int[liczbaElementow + 1];
for (int i = 1; i <= liczbaElementow; i++)
w[i] = ((rand() % 2000) - 1000);
budujKopiec();
}

void zbudujZPliku(string nazwa)
{
string s;
int i = 0;
int *t;
nazwa = nazwa + ".txt";
ifstream plik(nazwa);

if (!plik)
{
cout << "Nie mozna otworzyc pliku" << endl;;

}
else
{
getline(plik, s);
int n = atoi(s.c_str());
liczbaElementow = n;
t = new int[liczbaElementow];
while (!plik.eof())
{
if (i <= liczbaElementow)
{
getline(plik, s);
t[i] = atoi(s.c_str());
i++;
}
else break;
}
plik.close();
for (i; i <= liczbaElementow; i++)
{
t[i] = 0;
}
w = t;
budujKopiec();
}
}
void budujKopiec()
{
for (int i = 2; i <= liczbaElementow; i++)
{
int pozycjaElementu, pozycjaPrzodka, element;
pozycjaElementu = i;
pozycjaPrzodka = (pozycjaElementu) / 2;
element = w[i];
while ((pozycjaPrzodka > 0) && (w[pozycjaPrzodka] < element))
{
w[pozycjaElementu] = w[pozycjaPrzodka];
pozycjaElementu = pozycjaPrzodka;
pozycjaPrzodka = (pozycjaElementu) / 2;
}
w[pozycjaElementu] = element;
}
}
void wyswietl(string tekst1, string tekst2, int nrWezla)
{
if (liczbaElementow == 0)
cout << "Kopiec jest pusty" << endl;
string tekst;

if (nrWezla <= liczbaElementow)
{
tekst = tekst1;
if (tekst2 == gornyRog)
tekst[tekst.length() - 2] = ' ';

wyswietl(tekst + pion, gornyRog, 2 * nrWezla + 1);

tekst = tekst.substr(0, tekst1.length() - 2);

cout << tekst << tekst2 << w[nrWezla] << endl;

tekst = tekst1;
if (tekst2 == dolnyRog)
tekst[tekst.length() - 2] = ' ';
wyswietl(tekst + pion, dolnyRog, 2 * nrWezla);
}
}
bool szukaj(int liczbaDoZnalezienia)
{
bool czyJest = false;
for (int i = 1; i <= liczbaElementow; i++)
{
if (liczbaDoZnalezienia == w[i])
{
czyJest = true;
break;
}
}
return czyJest;

}
void dodaj(int liczbaDoDodania)
{
licznik = 0;
czasStart();
liczbaElementow++;
w[liczbaElementow] = liczbaDoDodania;
int pozycjaNowegoElementu = liczbaElementow;
while ((w[pozycjaNowegoElementu] > w[pozycjaNowegoElementu / 2]) && (pozycjaNowegoElementu > 1))
{
int temp = w[pozycjaNowegoElementu / 2];
w[pozycjaNowegoElementu / 2] = w[pozycjaNowegoElementu];
w[pozycjaNowegoElementu] = temp;
pozycjaNowegoElementu = (pozycjaNowegoElementu / 2);
}
pobierzCzas();
}
void relokuj()
{
int *t = new int[liczbaElementow + 1];
for (int i = 1; i <= liczbaElementow; i++)
{
t[i] = w[i];
}
w = new int[liczbaElementow + 1];
for (int i = 1; i <= liczbaElementow; i++)
{
w[i] = t[i];
}
delete[]t;
}
void usun(int liczbaDoUsuniecia)
{

if (liczbaElementow == 0) cout << "Kopiec jest pusty, nie mozna nic usunac" << endl;
else
{
if (!szukaj(liczbaDoUsuniecia)) cout << "W kopcu nie ma takiej liczby, nie mozna usunac!" << endl;
else
{
licznik = 0;
czasStart();
int i;
for (i = 1; i <= liczbaElementow; i++)
{
if (w[i] == liczbaDoUsuniecia) break;
}
if (i == liczbaElementow)
{
w[i] = NULL;
liczbaElementow--;
pobierzCzas();
}
if (i < liczbaElementow)
{
w[i] = w[liczbaElementow];
w[liczbaElementow] = NULL;
liczbaElementow--;
if (2 * i > liczbaElementow)
{
while (i > 1)
{
if (w[i] > w[i / 2])
{
int temp = w[i / 2];
w[i / 2] = w[i];
w[i] = temp;
}
i = i / 2;
}
}
else
{
while (i <= liczbaElementow / 2)
{
if ((w[i] < (w[2 * i])) || (w[i] < (w[2 * i + 1])))
{
if (w[2 * i] > w[2 * i + 1])
{
int temp = w[i];
w[i] = w[2 * i];
w[2 * i] = temp;
i = 2 * i;
}
else
{
int temp = w[i];
w[i] = w[2 * i + 1];
w[2 * i + 1] = temp;
i = 2 * i + 1;
}
}
else break;
}

}
}
pobierzCzas();
relokuj();
}
}
}
};

class WezelDrzewa
{
public:
WezelDrzewa *ojciec, *lewySyn, *prawySyn;
int klucz;
string kolor;
};

class DrzewoCzerwonoCzarne
{
private:
WezelDrzewa straznik;
string gornyRog, dolnyRog, pion;
string czarny;
string czerwony;
public:
WezelDrzewa *korzen;
int liczbaElementow;

DrzewoCzerwonoCzarne()
{
gornyRog = dolnyRog = pion = " ";
gornyRog[0] = 218; gornyRog[1] = 196;
dolnyRog[0] = 192; dolnyRog[1] = 196;
pion[0] = 179;
czarny = "CZAR";
czerwony = "CZERW";
straznik.kolor = czarny;
straznik.ojciec = &straznik;
straznik.lewySyn = &straznik;
straznik.prawySyn = &straznik;
korzen = &straznik;
liczbaElementow = 0;
}
~DrzewoCzerwonoCzarne()
{
usunDrzewo(korzen);
liczbaElementow = 0;
}
void usunDrzewo(WezelDrzewa *wezel)
{
if (wezel != &straznik)
{
usunDrzewo(wezel->lewySyn);
usunDrzewo(wezel->prawySyn);
delete wezel;
}
}
void zbudujZPliku(string nazwa)
{
string s;
int i = 1;
nazwa = nazwa + ".txt";
ifstream plik(nazwa);
if (!plik)
cout << "Nie mozna otworzyc pliku" << endl;
else
{

getline(plik, s);
int n = atoi(s.c_str());

while (!plik.eof())
{
if (i <= n)

{
getline(plik, s);
int klucz = atoi(s.c_str());
dodaj(klucz);
i++;
}
else break;
}
plik.close();
for (i; i <= n; i++)
{
dodaj(0);
}
}
}
void rotacjaL(WezelDrzewa* wezel)
{
WezelDrzewa * prawySyn, *ojciec;

prawySyn = wezel->prawySyn;
if (prawySyn != &straznik)
{
ojciec = wezel->ojciec;
wezel->prawySyn = prawySyn->lewySyn;
if (wezel->prawySyn != &straznik)
wezel->prawySyn->ojciec = wezel;

prawySyn->lewySyn = wezel;
prawySyn->ojciec = ojciec;
wezel->ojciec = prawySyn;

if (ojciec != &straznik)
{
if (ojciec->lewySyn == wezel) ojciec->lewySyn = prawySyn; else ojciec->prawySyn = prawySyn;
}
else korzen = prawySyn;
}
}
void rotacjaP(WezelDrzewa* wezel)
{
WezelDrzewa * lewySyn, *ojciec;

lewySyn = wezel->lewySyn;
if (lewySyn != &straznik)
{
ojciec = wezel->ojciec;
wezel->lewySyn = lewySyn->prawySyn;
if (wezel->lewySyn != &straznik)
wezel->lewySyn->ojciec = wezel;

lewySyn->prawySyn = wezel;
lewySyn->ojciec = ojciec;
wezel->ojciec = lewySyn;

if (ojciec != &straznik)
{
if (ojciec->lewySyn == wezel) ojciec->lewySyn = lewySyn; else ojciec->prawySyn = lewySyn;
}
else korzen = lewySyn;
}
}
void zapelnijLosowo(int ile)
{
int i;
int *t;
t = new int[ile];
for (i = 0; i < ile; i++)
t[i] = ((rand() % 2000) - 1000);

for (i = 0; i < ile; i++)
dodaj(t[i]);
}
void wyswietl(string tekst1, string tekst2, WezelDrzewa * wezel)
{
string tekst;
if (liczbaElementow == 0) cout << "Drzewo jest puste" << endl;
else if (wezel != &straznik)
{
tekst = tekst1;
if (tekst2 == gornyRog)
tekst[tekst.length() - 2] = ' ';
wyswietl(tekst + pion, gornyRog, wezel->prawySyn);

tekst = tekst.substr(0, tekst1.length() - 2);
cout << tekst << tekst2 << wezel->kolor << ":" << wezel->klucz << endl;

tekst = tekst1;
if (tekst2 == dolnyRog)
tekst[tekst.length() - 2] = ' ';
wyswietl(tekst + pion, dolnyRog, wezel->lewySyn);
}
}
void dodaj(int klucz)
{
WezelDrzewa *nowyElement, *wujek;

nowyElement = new WezelDrzewa;
nowyElement->lewySyn = &straznik;
nowyElement->prawySyn = &straznik;
nowyElement->ojciec = korzen;
nowyElement->klucz = klucz;
if (nowyElement->ojciec == &straznik) korzen = nowyElement;
else
while (true)
{
if (klucz < nowyElement->ojciec->klucz)
{
if (nowyElement->ojciec->lewySyn == &straznik)
{
nowyElement->ojciec->lewySyn = nowyElement;
break;
}
nowyElement->ojciec = nowyElement->ojciec->lewySyn;
}
if (klucz >= nowyElement->ojciec->klucz)
{
if (nowyElement->ojciec->prawySyn == &straznik)

{
nowyElement->ojciec->prawySyn = nowyElement;
break;
}
nowyElement->ojciec = nowyElement->ojciec->prawySyn;
}
}
nowyElement->kolor = czerwony;
while ((nowyElement != korzen) && (nowyElement->ojciec->kolor == czerwony))
{
if (nowyElement->ojciec == nowyElement->ojciec->ojciec->lewySyn)
{
wujek = nowyElement->ojciec->ojciec->prawySyn;

if (wujek->kolor == czerwony)
{
nowyElement->ojciec->kolor = czarny;
wujek->kolor = czarny;
nowyElement->ojciec->ojciec->kolor = czerwony;
nowyElement = nowyElement->ojciec->ojciec;
continue;
}

if (nowyElement == nowyElement->ojciec->prawySyn)
{
nowyElement = nowyElement->ojciec;
rotacjaL(nowyElement);
}

nowyElement->ojciec->kolor = czarny;
nowyElement->ojciec->ojciec->kolor = czerwony;
rotacjaP(nowyElement->ojciec->ojciec);
break;
}
else
{
wujek = nowyElement->ojciec->ojciec->lewySyn;

if (wujek->kolor == czerwony)
{
nowyElement->ojciec->kolor = czarny;
wujek->kolor = czarny;
nowyElement->ojciec->ojciec->kolor = czerwony;
nowyElement = nowyElement->ojciec->ojciec;
continue;
}

if (nowyElement == nowyElement->ojciec->lewySyn)
{
nowyElement = nowyElement->ojciec;
rotacjaP(nowyElement);
}

nowyElement->ojciec->kolor = czarny;
nowyElement->ojciec->ojciec->kolor = czerwony;
rotacjaL(nowyElement->ojciec->ojciec);
break;
}

}
korzen->kolor = czarny;
liczbaElementow++;
}
bool sprawdzCzyJest(int klucz)
{
WezelDrzewa * wezel;
bool czyJest = false;
wezel = korzen;
while ((wezel != &straznik) && (wezel->klucz != klucz))
{
if (klucz < wezel->klucz)
wezel = wezel->lewySyn;
else
wezel = wezel->prawySyn;
}

if (wezel == &straznik) czyJest = false;
else czyJest = true;
return czyJest;
}
WezelDrzewa* znajdzWezel(int klucz)
{
WezelDrzewa * wezel;
wezel = korzen;
while ((wezel != &straznik) && (wezel->klucz != klucz))
{
if (klucz < wezel->klucz)
wezel = wezel->lewySyn;
else
wezel = wezel->prawySyn;
}

if (wezel == &straznik) return NULL;
return wezel;
}
void usun(int klucz)
{
if (!sprawdzCzyJest(klucz))
cout << "W drzewie nie ma elementu o takim kluczu!" << endl;
else if (liczbaElementow == 0)
cout << "Drzewo jest puste!" << endl;
else
{
licznik = 0;
czasStart();
WezelDrzewa *wezelDoUsuniecia, *wujek, *syn;
wezelDoUsuniecia = znajdzWezel(klucz);
if ((wezelDoUsuniecia->lewySyn == &straznik) || (wezelDoUsuniecia->prawySyn == &straznik)) {}
else
{
if (wezelDoUsuniecia != &straznik)
{
if (wezelDoUsuniecia->prawySyn != &straznik)
{
if (wezelDoUsuniecia->prawySyn != &straznik)
{
while (wezelDoUsuniecia->prawySyn->lewySyn != &straznik)
wezelDoUsuniecia->prawySyn = wezelDoUsuniecia->prawySyn->lewySyn;
}
wezelDoUsuniecia = wezelDoUsuniecia->prawySyn;
}
else
{
wezelDoUsuniecia = wezelDoUsuniecia->ojciec;
while ((wezelDoUsuniecia != &straznik) && (wezelDoUsuniecia == wezelDoUsuniecia->prawySyn))
{
wezelDoUsuniecia = wezelDoUsuniecia;
wezelDoUsuniecia = wezelDoUsuniecia->ojciec;
}
}
}
else
wezelDoUsuniecia = &straznik;
}

if (wezelDoUsuniecia->lewySyn != &straznik)
syn = wezelDoUsuniecia->lewySyn;
else
syn = wezelDoUsuniecia->prawySyn;

syn->ojciec = wezelDoUsuniecia->ojciec;

if (wezelDoUsuniecia->ojciec == &straznik)
korzen = syn;
else if
(wezelDoUsuniecia == wezelDoUsuniecia->ojciec->lewySyn) wezelDoUsuniecia->ojciec->lewySyn = syn;
else
wezelDoUsuniecia->ojciec->prawySyn = syn;

if (wezelDoUsuniecia != wezelDoUsuniecia) wezelDoUsuniecia->klucz = wezelDoUsuniecia->klucz;

if (wezelDoUsuniecia->kolor == czarny)
while ((syn != korzen) && (syn->kolor == czarny))
{
if (syn == syn->ojciec->lewySyn)
{
wujek = syn->ojciec->prawySyn;

if (wujek->kolor == czerwony)
{
wujek->kolor == czarny;
syn->ojciec->kolor = czerwony;
rotacjaL(syn->ojciec);
wujek = syn->ojciec->prawySyn;
}

if ((wujek->lewySyn->kolor == czarny) && (wujek->prawySyn->kolor == czarny))
{
wujek->kolor = czerwony;
syn = syn->ojciec;
continue;
}

if (wujek->prawySyn->kolor == czarny)
{
wujek->lewySyn->kolor == czarny;
wujek->kolor = czerwony;
rotacjaP(wujek);
wujek = syn->ojciec->prawySyn;
}
wujek->kolor = syn->ojciec->kolor;
syn->ojciec->kolor = czarny;
wujek->prawySyn->kolor = czarny;
rotacjaL(syn->ojciec);
syn = korzen;
}
else
{
wujek = syn->ojciec->lewySyn;

if (wujek->kolor == czerwony)
{
wujek->kolor = czarny;
syn->ojciec->kolor = czerwony;
rotacjaP(syn->ojciec);
wujek = syn->ojciec->lewySyn;
}

if ((wujek->lewySyn->kolor == czarny) && (wujek->prawySyn->kolor == czarny))
{
wujek->kolor = czerwony;
syn = syn->ojciec;
continue;
}

if (wujek->lewySyn->kolor == czarny)
{
wujek->prawySyn->kolor == czarny;
wujek->kolor = czerwony;
rotacjaL(wujek);
wujek = syn->ojciec->lewySyn;
}

wujek->kolor = syn->ojciec->kolor;
syn->ojciec->kolor = czarny;
wujek->lewySyn->kolor = czarny;
rotacjaP(syn->ojciec);
syn = korzen;
}
}
syn->kolor = czarny;
liczbaElementow--;
pobierzCzas();
}

}
};
int main()
{
srand(time(NULL));
bool naPoczatek = true;
while (naPoczatek == true){

int wybor;
cout << "Wybierz strukture do testow" << endl
<< "1. Tablica" << endl << "2. Lista" << endl << "3. Kopiec" << endl << "4. Drzewo czerwono-czarne" << endl;
cin >> wybor;


system("cls");
switch (wybor)
{
case 1:
{
naPoczatek = false;
Tablica* tablica;
tablica = new Tablica();
int ile;
while (naPoczatek == false)
{
cout << "Tablica - " << tablica->liczbaElementow << " elementow" << endl << "Co chcesz zrobic z ta struktura?" <<
endl << "1. Zbuduj z pliku " << endl << "2. Wylosuj tablice" << endl << "3. Usun" << endl << "4. Dodaj" << endl << "5. Wyszukaj" <<
endl << "6. Wyswietl" << endl << "7. Zniszcz strukture" << endl << "8. Wroc do wyboru struktury" << endl << "9. Zakoncz program" << endl;
cin >> wybor;

switch (wybor)
{
case 1:{
string nazwa;
tablica = new Tablica();
cout << "Podaj nazwe pliku do wczytania danych" << endl;
cin >> nazwa;
cout << endl;
tablica->zbudujZPliku(nazwa);
} break;
case 2:
{

while (true)
{
cout << "Ilu elementowa tablice stworzyc?" << endl;
cin >> ile;
if (ile <= 0) cout << "Podaj liczbe wieksza od zera!" << endl;
else break;
}
tablica = new Tablica();
cout << endl;
tablica->zapelnijLosowo(ile);
}break;
case 3:{
int wartosc;
cout << "1. Usun z poczatku " << endl << "2. Usun z konca" << endl << "3. Usun wybrany element" << endl;
cin >> wybor;
switch (wybor)

{

case 1:
{
tablica->usunZPoczatku();

}break;

case 2:
{
tablica->usunZKonca();
}break;
case 3:{
while (true)
{
cout << "Podaj indeks elementu do usuniecia" << endl;
cin >> ile;
cout << endl;
if (ile < 0) cout << "Podaj liczbe wieksza od zera!" << endl;
else break;
}

tablica->usun(ile);

}break;

}

}break;
case 4:{
int wartosc;
cout << "1. Dodaj na poczatek " << endl << "2. Dodaj na koniec" << endl << "3. Dodaj na wybranym miejscu" << endl;
cin >> wybor;
switch (wybor)

{

case 1:
{
cout << "Podaj wartosc nowego elementu" << endl;
cin >> wartosc;
cout << endl;
licznik = 0;
czasStart();
tablica->dodajNaPoczatek(wartosc);
pobierzCzas();

}break;

case 2:
{
cout << "Podaj wartosc nowego elementu" << endl;
cin >> wartosc;
cout << endl;
tablica->dodajNaKoniec(wartosc);
}break;
case 3:{
while (true)
{
cout << "Podaj indeks miejsca, gdzie ma byc wstawiony nowy element" << endl;
cin >> ile;
cout << endl;
if (ile < 0) cout << "Podaj liczbe wieksza od zera!" << endl;
else break;
}

cout << "Podaj wartosc nowego elementu" << endl;
cin >> wartosc;
cout << endl;
tablica->dodaj(ile, wartosc);

}break;

}


}break;
case 5:{
int wartosc;
cout << "Podaj wartosc, ktora chcesz sprawdzic, czy jest w tablicy" << endl;
cin >> wartosc;
cout << endl;
tablica->szukaj(wartosc);
}break;
case 6:{
tablica->wyswietl();
}break;
case 7:{
tablica->~Tablica();
tablica = new Tablica();
}break;
case 8:{
delete tablica;
system("cls");
naPoczatek = true;
}break;
case 9:{
delete tablica;
return 0;
}break;
}
}
}break;
case 2:{
naPoczatek = false;
unsigned ile;
Lista* lista;
lista = new Lista();

while (naPoczatek == false){
cout << "Lista - " << lista->liczbaElementow << " elementow" << endl << "Co chcesz zrobic z ta struktura?" <<
endl << "1. Zbuduj z pliku " << endl << "2. Wylosuj liste" << endl << "3. Usun" << endl << "4. Dodaj" << endl << "5. Wyszukaj" <<
endl << "6. Wyswietl" << endl << "7. Zniszcz strukture" << endl << "8. Wroc do wyboru struktury" << endl << "9. Zakoncz program" << endl;
cin >> wybor;
switch (wybor)
{
case 1:{
lista->~Lista();
lista = new Lista();
string nazwa;
cout << "Podaj nazwe pliku do wczytania danych" << endl;
cin >> nazwa;
cout << endl;
lista->zbudujZPliku(nazwa);
}break;
case 2:{
lista->~Lista();
while (true)
{
cout << "Ilu elementowa liste stworzyc?" << endl;
cin >> ile;
cout << endl;
if (ile <= 0) cout << "Podaj liczbe wieksza od zera!" << endl;
else break;
}
lista = new Lista();
lista->zapelnijLosowo(ile);
}break;
case 3:{
int wartosc;
cout << "1. Usun z poczatku " << endl << "2. Usun z konca" << endl << "3. Usun wybrany element" << endl;
cin >> wybor;
switch (wybor)

{

case 1:
{
lista->usunZPoczatku();

}break;

case 2:
{
lista->usunZKonca();
}break;
case 3:{

cout << "Co usunac (klucz elementu)?" << endl;
cin >> ile;
cout << endl;
lista->usun(ile);

}break;

}

}break;

case 4:{
int wartosc;
cout << "1. Dodaj na poczatek " << endl << "2. Dodaj na koniec" << endl << "3. Dodaj za wybranym elementem" << endl;
cin >> wybor;
switch (wybor)

{
case 1:
{
cout << "Podaj klucz nowego elementu" << endl;
cin >> wartosc;
cout << endl;
licznik = 0;
czasStart();
lista->dodajNaPoczatek(wartosc);
pobierzCzas();

}break;

case 2:
{
cout << "Podaj klucz nowego elementu" << endl;
cin >> wartosc;
cout << endl;
licznik = 0;
czasStart();
lista->dodajNaKoniec(wartosc);
pobierzCzas();
}break;
case 3:{
int klucz;
cout << "Podaj klucz elementu do wstawienia" << endl;
cin >> klucz;
cout << endl;
cout << "Za ktorym elementem chcesz wstawic nowy (podaj klucz)?" << endl;
cin >> ile;
cout << endl;
lista->dodajNowyElementZaElementemOPodanymKluczu(ile, klucz);

}break;

}



}break;
case 5:{
cout << "Podaj klucz, ktory chcesz sprawdzic, czy jest na liscie" << endl;
cin >> ile;
cout << endl;
licznik = 0;
czasStart();
lista->szukaj(ile);
pobierzCzas();
if (lista->szukaj(ile)) cout << "Szukany element znajduje sie na liscie" << endl;
if (!lista->szukaj(ile)) cout << "Szukego elementu nie ma na liscie" << endl;


}break;
case 6:{
lista->wyswietl();
}break;
case 7:{
lista->~Lista();
lista = new Lista();


}break;
case 8:{
delete lista;
system("cls");
naPoczatek = true;

}break;
case 9:{
delete lista;
return 0;
}break;

}


}break;
}break;
case 3:{
naPoczatek = false;
int ile;
system("cls");
Kopiec *kopiec;
kopiec = new Kopiec();
while (naPoczatek == false)
{
cout << "Kopiec - " << kopiec->liczbaElementow << " elementow" << endl << "Co chcesz zrobic z ta struktura?" <<
endl << "1. Zbuduj z pliku " << endl << "2. Wylosuj kopiec" << endl << "3. Usun" << endl << "4. Dodaj" << endl << "5. Wyszukaj" <<
endl << "6. Wyswietl" << endl << "7. Zniszcz strukture" << endl << "8. Wroc do wyboru struktury" << endl << "9. Zakoncz program" << endl;
cin >> wybor;

switch (wybor)
{
case 1:{
string nazwa;
cout << "Podaj nazwe pliku do wczytania danych" << endl;
cin >> nazwa;
cout << endl;
kopiec = new Kopiec();
kopiec->zbudujZPliku(nazwa);
}break;

case 2:
{
while (true)
{
cout << "Ilu elementowa strukture stworzyc?" << endl;
cin >> ile;
if (ile > 0) break;
else cout << "Podaj liczbe wieksza od zera!" << endl;

}
kopiec = new Kopiec();
kopiec->zapelnijLosowo(ile);
}break;
case 3:{
cout << "Co usunac (klucz)?" << endl;
cin >> ile;
cout << endl;
kopiec->usun(ile);

}break;

case 4:{
cout << "Podaj klucz elementu do wstawienia" << endl;
cin >> ile;
cout << endl;
kopiec->dodaj(ile);


}break;

case 5:{
cout << "Podaj wartosc, ktora chcesz sprawdzic, czy jest w kopcu" << endl;
cin >> ile;
cout << endl;
licznik = 0;
czasStart();
kopiec->szukaj(ile);
pobierzCzas();
if (kopiec->szukaj(ile)) cout << "Szukany element znajduje sie w kopcu" << endl;
if (!kopiec->szukaj(ile)) cout << "Szukego elementu nie ma w kopcu" << endl;
}break;
case 6:{
kopiec->wyswietl(" ", " ", 1);
}break;
case 7:{
kopiec->~Kopiec();
kopiec = new Kopiec();
}break;
case 8:{
system("cls");
delete kopiec;
naPoczatek = true;
}break;
case 9:{
delete kopiec;
return 0;
}break;
}
}

}break;
case 4:
{
naPoczatek = false;
int ile;
system("cls");
DrzewoCzerwonoCzarne *drzewo;
drzewo = new DrzewoCzerwonoCzarne();

while (naPoczatek == false)
{
cout << "Drzewo czerwono-czarne - " << drzewo->liczbaElementow << " elementow" << endl << "Co chcesz zrobic z ta struktura?" <<
endl << "1. Zbuduj z pliku " << endl << "2. Wylosuj drzewo" << endl << "3. Usun" << endl << "4. Dodaj" << endl << "5. Wyszukaj" <<
endl << "6. Wyswietl" << endl << "7. Zniszcz strukture" << endl << "8. Wroc do wyboru struktury" << endl << "9. Zakoncz program" << endl;
cin >> wybor;
switch (wybor)
{
case 1:{
drzewo->~DrzewoCzerwonoCzarne();
drzewo = new DrzewoCzerwonoCzarne();
string nazwa;
cout << "Podaj nazwe pliku do wczytania danych" << endl;
cin >> nazwa;
cout << endl;
drzewo->zbudujZPliku(nazwa);
}break;

case 2:
{
drzewo->~DrzewoCzerwonoCzarne();
while (true)
{
cout << "Ilu elementowa strukture stworzyc?" << endl;
cin >> ile;
if (ile > 0) break;
else cout << "Podaj liczbe wieksza od zera!" << endl;
}
drzewo = new DrzewoCzerwonoCzarne();
drzewo->zapelnijLosowo(ile);

}break;
case 3:{
cout << "Co usunac?" << endl;
cin >> ile;
cout << endl;
drzewo->usun(ile);

}break;

case 4:{
cout << "Podaj wartosc elementu do wstawienia" << endl;
cin >> ile;
cout << endl;
licznik = 0;
czasStart();
drzewo->dodaj(ile);
pobierzCzas();

}break;

case 5:{
cout << "Podaj wartosc, ktora chcesz sprawdzic, czy jest w drzewie" << endl;
cin >> ile;
cout << endl;
licznik = 0;
czasStart();
drzewo->sprawdzCzyJest(ile);
pobierzCzas();
if (drzewo->sprawdzCzyJest(ile)) cout << "Szukany element znajduje sie w drzewie" << endl;
if (!drzewo->sprawdzCzyJest(ile)) cout << "Szukego elementu nie ma w drzewie" << endl;
}break;
case 6:{
drzewo->wyswietl(" ", "", drzewo->korzen);
}break;
case 7:{
drzewo->~DrzewoCzerwonoCzarne();
drzewo = new DrzewoCzerwonoCzarne();
}break;
case 8:{
delete drzewo;
system("cls");
naPoczatek = true;
}break;
case 9:{
delete drzewo;
return 0;
}break;
}
}

}break;
}
}
system("pause");
return 0;
}