301 lines
11 KiB
C++
301 lines
11 KiB
C++
/**
|
|
* Implementujte metodu insert (vkládání), erase (mazání prvků
|
|
* ze stromu a zároveň je potřeba uchovat správné pořádí podle
|
|
* data vkládání) a vlastní destruktor, ostatní metody jsou
|
|
* naimplentované. Kopírující konstruktor i operátor přiřazení
|
|
* zakázán. Není povolené si přidat žádnou členskou proměnnou,
|
|
* ale lze naimplementovat vlastní pomocné metody.
|
|
*
|
|
* Za správnost šablony neručím :-).
|
|
*/
|
|
|
|
#include <string>
|
|
#include <cassert>
|
|
|
|
// https://fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-pa2/pa2_zkou%C5%A1ka_2022-06-16
|
|
|
|
using namespace std;
|
|
|
|
class CTree
|
|
{
|
|
public:
|
|
CTree() = default;
|
|
~CTree() {
|
|
CNode* i = m_First;
|
|
while (i) {
|
|
CNode* j = i->m_NextOrder;
|
|
delete i;
|
|
i = j;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
CTree(const CTree &src) = delete;
|
|
|
|
bool operator=(const CTree &other) = delete;
|
|
|
|
bool isSet(string key) {
|
|
CNode * n = m_Root;
|
|
while (n) {
|
|
if (key == n->m_Key)
|
|
return true;
|
|
else if (key > n->m_Key)
|
|
n = n->m_R;
|
|
else
|
|
n = n->m_L;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool insert(string key) {
|
|
if (!m_Root)
|
|
return m_Root = m_First = m_Last = new CNode(key);
|
|
|
|
CNode* i = nullptr;
|
|
CNode* n = m_Root;
|
|
while (n) {
|
|
if (key == n->m_Key) {
|
|
return false;
|
|
} else if (key > n->m_Key) {
|
|
i = n;
|
|
n = n->m_R;
|
|
} else {
|
|
i = n;
|
|
n = n->m_L;
|
|
}
|
|
}
|
|
|
|
n = new CNode(key);
|
|
if (key > i->m_Key)
|
|
i->m_R = n;
|
|
else
|
|
i->m_L = n;
|
|
|
|
n->m_PrevOrder = m_Last;
|
|
m_Last = m_Last->m_NextOrder = n;
|
|
return true;
|
|
}
|
|
|
|
bool erase(string key) {
|
|
CNode** p = &m_Root;
|
|
CNode* n = m_Root;
|
|
while (n) {
|
|
if (key == n->m_Key)
|
|
goto found;
|
|
else if (key > n->m_Key) {
|
|
p = &n->m_R;
|
|
n = n->m_R;
|
|
} else {
|
|
p = &n->m_L;
|
|
n = n->m_L;
|
|
}
|
|
}
|
|
return false;
|
|
|
|
found:
|
|
if (!(n->m_L && n->m_R)) { // one or none child
|
|
*p = (CNode*)((ptrdiff_t)n->m_L | (ptrdiff_t)n->m_R);
|
|
} else {
|
|
CNode* ts = n->m_L;
|
|
CNode** tsp = &n->m_L;
|
|
while (ts->m_R) {
|
|
tsp = &ts->m_R;
|
|
ts = ts->m_R;
|
|
}
|
|
swapTree( n, ts );
|
|
*tsp = ts->m_L;
|
|
n = ts;
|
|
}
|
|
eraseList(n);
|
|
delete n;
|
|
return true;
|
|
}
|
|
|
|
protected:
|
|
class CNode {
|
|
public:
|
|
CNode(string key) : m_Key(key) {}
|
|
string m_Key;
|
|
CNode * m_L = nullptr;
|
|
CNode * m_R = nullptr;
|
|
CNode * m_PrevOrder = nullptr;
|
|
CNode * m_NextOrder = nullptr;
|
|
};
|
|
CNode * m_Root = nullptr;
|
|
CNode * m_First = nullptr;
|
|
CNode * m_Last = nullptr;
|
|
|
|
void swapTree( CNode* a, CNode* b ) {
|
|
if (a == m_Last) m_Last = b;
|
|
else if (b == m_Last) m_Last = a;
|
|
|
|
if (a == m_First) m_First = b;
|
|
else if (b == m_First) m_First = a;
|
|
|
|
if (a->m_NextOrder) a->m_NextOrder->m_PrevOrder = b;
|
|
if (a->m_PrevOrder) a->m_PrevOrder->m_NextOrder = b;
|
|
if (b->m_NextOrder) b->m_NextOrder->m_PrevOrder = a;
|
|
if (b->m_PrevOrder) b->m_PrevOrder->m_NextOrder = a;
|
|
|
|
std::swap(a->m_NextOrder, b->m_NextOrder);
|
|
std::swap(a->m_PrevOrder, b->m_PrevOrder);
|
|
std::swap(a->m_Key, b->m_Key);
|
|
}
|
|
|
|
void eraseList( CNode* a ) {
|
|
if (a->m_PrevOrder)
|
|
a->m_PrevOrder->m_NextOrder = a->m_NextOrder;
|
|
else
|
|
m_First = a->m_NextOrder;
|
|
|
|
if (a->m_NextOrder)
|
|
a->m_NextOrder->m_PrevOrder = a->m_PrevOrder;
|
|
else
|
|
m_Last = a->m_PrevOrder;
|
|
}
|
|
};
|
|
|
|
class CTester : public CTree
|
|
{
|
|
public:
|
|
CTester () = default;
|
|
void test()
|
|
{
|
|
CTester t0;
|
|
assert(t0.insert("PA1")==true);
|
|
assert(t0.m_First->m_Key=="PA1" && t0.m_First->m_NextOrder == nullptr);
|
|
assert(t0.isSet("PA1")==true);
|
|
assert(t0.insert("UOS")==true);
|
|
assert(t0.insert("PA2")==true);
|
|
assert(t0.isSet("PA2")==true);
|
|
assert(t0.isSet("PA3")==false);
|
|
|
|
assert(t0.insert("PA2")==false);
|
|
assert(t0.insert("CAO")==true);
|
|
assert(t0.insert("LIN")==true);
|
|
assert(t0.insert("AAG")==true);
|
|
assert(t0.insert("AG1")==true);
|
|
assert(t0.insert("ZDM")==true);
|
|
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "UOS"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "CAO"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AAG"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "ZDM");
|
|
|
|
assert(t0.m_Last->m_Key == "ZDM"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "AAG"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "CAO"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "UOS"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
|
|
assert(t0.erase("")==false);
|
|
|
|
assert(t0.erase("ZDM")==true);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "UOS"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "CAO"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AAG"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "AAG"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "CAO"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "UOS"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("ZDM")==false);
|
|
|
|
assert(t0.erase("AAG")==true);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "UOS"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "CAO"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "CAO"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "UOS"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("AAG")==false);
|
|
|
|
assert(t0.erase("CAO")==true);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "UOS"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "UOS"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("CAO")==false);
|
|
|
|
assert(t0.erase("UOS")==true);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("UOS")==false);
|
|
|
|
assert(t0.erase("UOS")==false);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "LIN"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "LIN"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("UOS")==false);
|
|
|
|
assert(t0.erase("LIN")==true);
|
|
assert(t0.m_First->m_Key == "PA1"
|
|
&& t0.m_First->m_NextOrder->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "PA2"
|
|
&& t0.m_Last->m_PrevOrder->m_PrevOrder->m_Key == "PA1");
|
|
assert(t0.isSet("LIN")==false);
|
|
|
|
assert(t0.erase("PA1")==true);
|
|
assert(t0.m_First->m_Key == "PA2"
|
|
&& t0.m_First->m_NextOrder->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1"
|
|
&& t0.m_Last->m_PrevOrder->m_Key == "PA2");
|
|
assert(t0.isSet("PA1")==false);
|
|
|
|
assert(t0.erase("PA2")==true);
|
|
assert(t0.m_First->m_Key == "AG1");
|
|
assert(t0.m_Last->m_Key == "AG1");
|
|
assert(t0.isSet("PA2")==false);
|
|
|
|
assert(t0.erase("AG1")==true);
|
|
assert(t0.m_First == t0.m_Last);
|
|
assert(t0.isSet("AG1")==false);
|
|
}
|
|
};
|
|
#include <iostream>
|
|
int main ( )
|
|
{
|
|
CTester t;
|
|
t.test();
|
|
std::cout << "success!\n";
|
|
return EXIT_SUCCESS;
|
|
} |