168 lines
3.7 KiB
C++
168 lines
3.7 KiB
C++
#include<iostream>
|
|
#include<string>
|
|
#include<cassert>
|
|
#include<sstream>
|
|
using namespace std;
|
|
|
|
// https://fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-pa2/pa2_zkou%C5%A1ka_2022-06-09
|
|
|
|
class CTree{
|
|
public:
|
|
CTree() = default;
|
|
CTree(const CTree & src) = delete;
|
|
CTree & operator = (const CTree & src) = delete;
|
|
|
|
~CTree(){
|
|
delete m_Root;
|
|
}
|
|
|
|
bool isSet(const string & key){
|
|
CNode* i = nullptr;
|
|
CNode* n = m_Root;
|
|
do {
|
|
std::swap(i, n);
|
|
if (i->m_Key == key) return true;
|
|
n = i->m_Key < key ? i->m_R : i->m_L;
|
|
} while (n);
|
|
return false;
|
|
}
|
|
|
|
bool insert(const string & key, const string & val){
|
|
if (!m_Root) {
|
|
m_Root = new CNode(key, val);
|
|
m_First = m_Last = m_Root;
|
|
return true;
|
|
}
|
|
|
|
CNode* i = nullptr;
|
|
CNode* n = m_Root;
|
|
do {
|
|
std::swap(i, n);
|
|
if (i->m_Key == key) return false;
|
|
n = i->m_Key < key ? i->m_R : i->m_L;
|
|
} while (n);
|
|
n = new CNode(key, val);
|
|
|
|
|
|
if (i->m_Key < key) {
|
|
i->m_R = n;
|
|
} else {
|
|
i->m_L = n;
|
|
}
|
|
|
|
return m_Last = m_Last->m_NextOrder = n;
|
|
}
|
|
|
|
friend ostream & operator << (ostream & os, const CTree & src){
|
|
src.print(os);
|
|
return os;
|
|
}
|
|
|
|
protected:
|
|
|
|
class CNode{
|
|
public:
|
|
CNode(const string & key, const string & val)
|
|
:m_Key(key), m_Val(val) {}
|
|
~CNode() {
|
|
delete m_L;
|
|
delete m_R;
|
|
}
|
|
string m_Key, m_Val;
|
|
CNode * m_L = nullptr, * m_R = nullptr;
|
|
CNode * m_NextOrder = nullptr;
|
|
};
|
|
|
|
CNode * m_Root = nullptr;
|
|
CNode * m_First = nullptr, * m_Last = nullptr;
|
|
|
|
void print( ostream & os ) const {
|
|
os << "{";
|
|
for (CNode* i = m_First; i; i = i->m_NextOrder) {
|
|
os << i->m_Key << " => " << i->m_Val;
|
|
if (i != m_Last) os << ", ";
|
|
}
|
|
os << "}";
|
|
}
|
|
|
|
friend int main();
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
int main(void){
|
|
CTree t;
|
|
stringstream ss;
|
|
ss << t;
|
|
assert(ss.str() == "{}");
|
|
ss.clear();
|
|
ss.str("");
|
|
assert(t.insert("PA1", "done"));
|
|
assert(t.m_First == t.m_Last);
|
|
assert(t.m_First->m_Key == "PA1");
|
|
assert(!t.isSet("UOS"));
|
|
assert(t.insert("PA2", "fail"));
|
|
assert(t.insert("UOS", "funny"));
|
|
|
|
ss << t;
|
|
assert(ss.str() == "{PA1 => done, PA2 => fail, UOS => funny}");
|
|
ss.clear();
|
|
ss.str("");
|
|
|
|
|
|
assert(t.m_Root->m_L== nullptr);
|
|
assert(t.m_Last->m_Key == "UOS");
|
|
assert(t.m_Root->m_R->m_Key == "PA2");
|
|
assert(t.m_Root->m_R->m_L == nullptr);
|
|
assert(t.m_Root->m_R->m_R->m_Key == "UOS");
|
|
assert(t.m_First->m_NextOrder->m_NextOrder == t.m_Last);
|
|
assert(t.isSet("PA2"));
|
|
|
|
assert(t.insert("CAO", "lul"));
|
|
assert(t.insert("LIN", "F"));
|
|
assert(t.m_Root->m_L->m_Key == "CAO");
|
|
assert(t.m_Root->m_L->m_L == nullptr);
|
|
assert(t.m_Root->m_L->m_R->m_Key == "LIN");
|
|
assert(t.m_Last == t.m_Root->m_L->m_R );
|
|
assert(t.m_Root->m_L->m_R->m_L == nullptr);
|
|
assert(t.m_First->m_NextOrder->m_NextOrder->m_NextOrder->m_NextOrder = t.m_Root->m_L->m_R);
|
|
assert(t.isSet("LIN"));
|
|
|
|
ss << t;
|
|
assert(ss.str() == "{PA1 => done, PA2 => fail, UOS => funny, CAO => lul, LIN => F}");
|
|
ss.clear();
|
|
ss.str("");
|
|
|
|
assert(t.insert("SAP", "shit"));
|
|
assert(t.m_Root->m_R->m_R->m_L->m_Key == "SAP");
|
|
assert(t.m_Last == t.m_Root->m_R->m_R->m_L);
|
|
|
|
|
|
ss << t;
|
|
assert(ss.str() == "{PA1 => done, PA2 => fail, UOS => funny, CAO => lul, LIN => F, SAP => shit}");
|
|
ss.clear();
|
|
ss.str("");
|
|
|
|
assert(!t.isSet("PA3"));
|
|
assert(t.isSet("LIN"));
|
|
assert(t.isSet("SAP"));
|
|
|
|
std::cout << "success!\n";
|
|
return 0;
|
|
} |