diff options
author | jonas <himself@jonasgunz.de> | 2017-03-06 15:36:05 +0100 |
---|---|---|
committer | jonas <himself@jonasgunz.de> | 2017-03-06 15:36:05 +0100 |
commit | 79e722e97f59cd3419299194387bf46e33a42ae4 (patch) | |
tree | 7c8e1e07d86803fbb6ac45bac892f6e9ed1c626e | |
parent | 6282b54e59ac2651b682ce2c548ed8024ac92480 (diff) | |
download | tree-79e722e97f59cd3419299194387bf46e33a42ae4.tar.gz |
*NOT WORKING*
Fix in progress for new Remove functionality
-rw-r--r-- | tree/Doc | 2 | ||||
-rw-r--r-- | tree/src/cData.cpp | 8 | ||||
-rw-r--r-- | tree/src/cData.h | 5 | ||||
-rw-r--r-- | tree/src/cNode.cpp | 26 | ||||
-rw-r--r-- | tree/src/cTree.cpp | 26 |
5 files changed, 55 insertions, 12 deletions
diff --git a/tree/Doc b/tree/Doc new file mode 100644 index 0000000..6ebf907 --- /dev/null +++ b/tree/Doc @@ -0,0 +1,2 @@ + - cData.h + Storage class
\ No newline at end of file diff --git a/tree/src/cData.cpp b/tree/src/cData.cpp index 44b6f1e..513bd4b 100644 --- a/tree/src/cData.cpp +++ b/tree/src/cData.cpp @@ -7,9 +7,10 @@ #include "cData.h" -cData::cData(string _data) +cData::cData(string _data, bool _empty) { sData = _data; + empty = _empty; } cData::~cData() @@ -22,6 +23,11 @@ string cData::getData() return sData; } +bool cData::isEmpty() +{ + return empty; +} + bool cData::operator<(cData _data) { diff --git a/tree/src/cData.h b/tree/src/cData.h index 14c916a..a1e80f2 100644 --- a/tree/src/cData.h +++ b/tree/src/cData.h @@ -18,7 +18,7 @@ using namespace std; class cData{ public: - cData(string _data); + cData(string _data, bool _empty = false); /* * Initializes cData with _data as saved Information */ @@ -34,6 +34,8 @@ public: * clones current cData instance */ + bool isEmpty(); + //Define operators bool operator<(cData); bool operator>(cData); @@ -43,6 +45,7 @@ public: bool operator==(string); private: + bool empty; string sData; }; diff --git a/tree/src/cNode.cpp b/tree/src/cNode.cpp index 8e001c4..c8035f8 100644 --- a/tree/src/cNode.cpp +++ b/tree/src/cNode.cpp @@ -44,10 +44,13 @@ void cDatanode::insert(cData* _data, cNode** _me) void cDatanode::insert(cNode* _data, cNode** _me) { + if( _data->getDataObject().isEmpty()) + return; //_data is endnode, return + if (_data->getDataObject() > *data) nextBigger->insert(_data, &nextBigger); else if (_data->getDataObject() == *data) - return; + return; //data already exists, abort else nextSmaller->insert(_data, &nextSmaller); } @@ -56,7 +59,7 @@ void cDatanode::remove(cData* _data, sSubTree* _subtree, cNode** _me) { if(*_data == *data) { - //save subtree inorder before deleting + //save subtree before deleting *_subtree = getSubTree(); *_me = new cEndnode(); //set pointer to this in parent to new cEndnode delete this; @@ -140,7 +143,17 @@ sSubTree cDatanode::getSubTree() cNode *cDatanode::getFirstNode(cNode** _me) { - return nextSmaller->getFirstNode(&nextSmaller); + cNode* ret = nextSmaller->getFirstNode(&nextSmaller); + if(ret) //Pointer not empty, return ret + { + return ret; + } + else //Pointer is empty, Return me + { + cNode* tmp = *_me; + *_me = new cEndnode(); + return tmp; + } } // @@ -152,7 +165,8 @@ cEndnode::~cEndnode() { } cData cEndnode::getDataObject() { - return (cData)NULL; + cData tmp("", true); + return tmp; } void cEndnode::insert(cData* _data, cNode** _me) @@ -211,9 +225,7 @@ sSubTree cEndnode::getSubTree() } cNode *cEndnode::getFirstNode(cNode** _me){ - cNode* tmp = *_me; - *_me = new cEndnode(); - return tmp; + return NULL; } diff --git a/tree/src/cTree.cpp b/tree/src/cTree.cpp index 6a871dd..ef6556e 100644 --- a/tree/src/cTree.cpp +++ b/tree/src/cTree.cpp @@ -32,11 +32,31 @@ void cTree::remove(cData* _data) { sSubTree subTree; root->remove(_data, &subTree, &root); + cout << "Remove Finished\n"; + + if(subTree.nextBigger && subTree.nextSmaller) + { + cNode* newRoot = subTree.nextSmaller->getFirstNode( &(subTree.nextSmaller)); + cout << "Got new root\n"; + + root->insert(newRoot, &root ); + cout << "Inserted new root\n"; + } + if (subTree.nextBigger) + { + root->insert(subTree.nextBigger, &root); + cout << "nextBigger inserted\n"; + } + if(subTree.nextSmaller) + { + root->insert(subTree.nextSmaller, &root); + cout << "nextSmaller inserted\n"; + } - root->insert(subTree.nextSmaller->getFirstNode(&root), &root); //Insert new root //Insert remaining subtree - root->insert(subTree.nextSmaller, &root); - root->insert(subTree.nextBigger, &root); + + + }//remove void cTree::getList(list<cData>* _list) |