now able to get Objects by their inorder position

+cTree::operator[]
+cNode::getByID

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;