diff options
| -rw-r--r-- | tree/src/cData.cpp | 6 | ||||
| -rw-r--r-- | tree/src/cData.h | 1 | ||||
| -rw-r--r-- | tree/src/cNode.cpp | 28 | ||||
| -rw-r--r-- | tree/src/cNode.h | 9 | ||||
| -rw-r--r-- | tree/src/cTree.cpp | 44 | ||||
| -rw-r--r-- | tree/src/cTree.h | 7 | ||||
| -rw-r--r-- | tree/src/main.cpp | 28 |
7 files changed, 85 insertions, 38 deletions
diff --git a/tree/src/cData.cpp b/tree/src/cData.cpp index f0919c6..44b6f1e 100644 --- a/tree/src/cData.cpp +++ b/tree/src/cData.cpp @@ -30,6 +30,7 @@ bool cData::operator<(cData _data) else return false; } + bool cData::operator>(cData _data) { if(sData.compare(_data.getData()) > 0) @@ -37,6 +38,7 @@ bool cData::operator>(cData _data) else return false; } + bool cData::operator<(string _string) { if(sData.compare(_string) < 0) @@ -44,6 +46,7 @@ bool cData::operator<(string _string) else return false; } + bool cData::operator>(string _string) { if(sData.compare(_string) > 0) @@ -51,18 +54,21 @@ bool cData::operator>(string _string) else return false; } + bool cData::operator==(cData _data) { if(_data.getData() == sData) return true; return false; } + bool cData::operator==(string _data) { if(sData == _data) return true; return false; } + cData *cData::clone() { return new cData(sData); diff --git a/tree/src/cData.h b/tree/src/cData.h index 4fbfdb3..14c916a 100644 --- a/tree/src/cData.h +++ b/tree/src/cData.h @@ -34,6 +34,7 @@ public: * clones current cData instance */ + //Define operators bool operator<(cData); bool operator>(cData); bool operator<(string); diff --git a/tree/src/cNode.cpp b/tree/src/cNode.cpp index 3213fda..4597e7c 100644 --- a/tree/src/cNode.cpp +++ b/tree/src/cNode.cpp @@ -68,12 +68,27 @@ cData* cDatanode::search(string _search) return NULL; }//search +cData* cDatanode::getById(unsigned int _id, unsigned int &_cntr) +{ + cData* tmpData = nextSmaller->getById(_id, _cntr); + + if(tmpData) + return tmpData; + + if(_id == _cntr) + return data; + + _cntr++; + + return nextBigger->getById(_id, _cntr); +} + void cDatanode::getSortet(list<cData>* _list) { nextSmaller->getSortet(_list); _list->push_back(*data); nextBigger->getSortet(_list); -}//getSorte +}//getSortet void cDatanode::draw(int _depth) { @@ -84,7 +99,7 @@ void cDatanode::draw(int _depth) nextSmaller->draw(_depth + 1); nextBigger->draw(_depth + 1); -} +}//draw unsigned int cDatanode::getDepth(unsigned int _depth) { @@ -94,12 +109,12 @@ unsigned int cDatanode::getDepth(unsigned int _depth) depth2 = nextBigger->getDepth(_depth + 1); return depth1 < depth2 ? depth2:depth1; //return bigger depth -} +}//getDepth unsigned int cDatanode::getSubtreeSize() { return nextSmaller->getSubtreeSize() + nextBigger->getSubtreeSize() + 1; -} +}//getSubtreeSize // //============================================================================================================================== // @@ -128,6 +143,11 @@ cData* cEndnode::search(string) return NULL; } +cData* cEndnode::getById(unsigned int _id, unsigned int& _cntr) +{ + return NULL; +} + void cEndnode::getSortet(list<cData>* _list) { return; diff --git a/tree/src/cNode.h b/tree/src/cNode.h index deaffa8..c8ffe50 100644 --- a/tree/src/cNode.h +++ b/tree/src/cNode.h @@ -36,6 +36,10 @@ public: /* * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result) */ + virtual cData* getById(unsigned int, unsigned int&) = 0; + /* + * searches for obejct ID (-> inorder) + */ virtual void getSortet(list<cData>* _list) = 0; /* * gets sortet list @@ -76,6 +80,8 @@ public: /* * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result) */ + cData* getById(unsigned int, unsigned int&); + void getSortet(list<cData>* _list); /* * Copy all cData Instances into _list @@ -111,9 +117,12 @@ public: /* * Searches for a Object by its Primary Key, returns pointer pointing at result (NULL if no result) */ + cData* getById(unsigned int, unsigned int&); + void getSortet(list<cData>* _list); unsigned int getSubtreeSize(); + unsigned int getDepth(unsigned int); void draw(int _depth); diff --git a/tree/src/cTree.cpp b/tree/src/cTree.cpp index 0538872..f4fcf9a 100644 --- a/tree/src/cTree.cpp +++ b/tree/src/cTree.cpp @@ -10,23 +10,23 @@ cTree::cTree() { root = new cEndnode(); -} +}//Constructor cTree::~cTree() { delete root; -} +}//Destructor void cTree::insert(cData* _data) { root->insert(_data, &root); -} +}//insert void cTree::insert(string _data) { cData* tmp = new cData(_data); insert(tmp); -} +}//insert void cTree::remove(cData* _data) { @@ -34,32 +34,32 @@ void cTree::remove(cData* _data) root->remove(_data, &dataList, &root); insertList(&dataList); -} +}//remove void cTree::getList(list<cData>* _list) { root->getSortet(_list); -} +}//getList void cTree::draw() { root->draw(0); -} +}//draw cData* cTree::search(string _search) { return root->search(_search); -} +}//search void cTree::clear() { delete root; root = new cEndnode(); -} +}//clear void cTree::insertList(list<cData>* _list) { - unsigned int oldSize = _list->size(); //used bc size of list changes during for loop + unsigned int oldSize = _list->size(); //used bc size of list changes during for-loop list<cData> tmpList; if (oldSize <= 0) //Nothing to do if list is empty @@ -81,15 +81,8 @@ void cTree::insertList(list<cData>* _list) if(_list->size() <= 0) //Nothing to do if list is empty return; - //TODO Redundant! For loop not needed! - oldSize = _list->size(); - for (unsigned int i = 0; i < oldSize; i++) - { - tmpList.push_back(_list->front()); - _list->pop_front(); - } - insertList(&tmpList); //Insert second half(bigger value) of list below new root -} + insertList(_list); //Insert second half(bigger value) of list below new root +}//insertList void cTree::sort() { @@ -97,17 +90,17 @@ void cTree::sort() root->getSortet(&sortetList); //get inorder clear(); //clear tree insertList(&sortetList); //re insert inorderlist -} +}//sort unsigned int cTree::size() { return root->getSubtreeSize(); -} +}//size unsigned int cTree::depth() { return root->getDepth(0); -} +}//depth unsigned int cTree::gradeOfUnbalance() { @@ -115,8 +108,13 @@ unsigned int cTree::gradeOfUnbalance() unsigned int iDepth = depth(); return (iDepth / minDepth) - 1; //-1 so 100% = 0 -} +}//gradeOfUnbalance +cData *cTree::operator [](unsigned int _i) +{ + unsigned int a = 0; + return root->getById(_i, a); +} diff --git a/tree/src/cTree.h b/tree/src/cTree.h index 514478c..5bd3df8 100644 --- a/tree/src/cTree.h +++ b/tree/src/cTree.h @@ -57,17 +57,20 @@ public: */ unsigned int gradeOfUnbalance(); /* - * + * returns integer value indicating to with the tree is unsymmetrical + * 0: tree is symmetrical + * x: tree is x-times deeper than it could */ cData* search(string); /* * returns pointer to matching object + * NULL if no match */ - void draw(); /* * draws subtree in ASCII */ + cData* operator[](unsigned int); private: diff --git a/tree/src/main.cpp b/tree/src/main.cpp index 6e990c3..869ccb1 100644 --- a/tree/src/main.cpp +++ b/tree/src/main.cpp @@ -5,6 +5,8 @@ * Author: jonas */ #include <iostream> +#include <string> +#include <sstream> #include "cTree.h" using namespace std; @@ -13,22 +15,30 @@ int main (void) { cTree* a = new cTree(); - /*for (char i = ' '; i <= '~'; i ++) + for (char b = ' '; b <= '~'; b++) { - string s(&i); - a->insert(&s[0]); + stringstream ss; + string y; + + ss << b; + ss >> y; + + a->insert(y); } a->draw(); - cout << a->size() << "/" << a->depth() << endl; - cout << a->gradeOfUnbalance() << endl; cout << "-------------------" << endl; a->sort(); a->draw(); - cout << a->size() << "/" << a->depth() << endl; - cout << a->gradeOfUnbalance() << endl;*/ - while(1) + for(unsigned int i = 0; i < a->size(); i++) + { + cout << (*a)[i]->getData() << ", "; + } + cout << endl; + + + /*while(1) { for (char i = ' '; i <= '~'; i ++) { @@ -37,7 +47,7 @@ int main (void) } a->sort(); a->clear(); - } + }*/ delete a; |