1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
/*
* cNode.h
*
* Created on: Jan 25, 2017
* Author: jonas
*/
#ifndef SRC_CNODE_H_
#define SRC_CNODE_H_
#include "cData.h"
#include <list>
#include <iostream>
using namespace std;
class cNode {
public:
cNode();
virtual ~cNode();
virtual cData getDataObject() = 0;
/*
* returns dataObject
*/
virtual void insert(cData*, cNode** = NULL) = 0;
/*
* Inserts *cData into tree
* cNode** required to change pointer in the caller's pointer to next element
*/
virtual void remove(cData*, list<cData>*, cNode**) = 0;
/*
* Removes *cData from tree. Its subtree is stored in list<cData>*. cNode** refers to pointer to pointer to self to be able to change reference
*/
virtual cData* search(string) = 0;
/*
* 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)
* int: wanted if
* int&: id counter
*/
virtual void getSortet(list<cData>* _list) = 0;
/*
* saves inorder list to *_list
*/
virtual unsigned int getSubtreeSize() = 0;
/*
* returns size of subtree
*/
virtual unsigned int getDepth(unsigned int) = 0;
/*
* returns maximum depth under node
* unsigned int: depth of parent
*/
virtual void draw(int _depth) = 0;
/*
*draws tree in Ascii
*/
};
class cDatanode:public cNode
{
public:
cDatanode(cData* _data);
~cDatanode();
cData getDataObject();
/*
* returns dataObject
*/
void insert(cData*, cNode** = NULL);
/*
* Inserts *cData into tree
*/
void remove(cData*, list<cData>*, cNode**);
/*
* Removes *cData from tree
*/
cData* search(string);
/*
* 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
*/
void draw(int _depth);
unsigned int getSubtreeSize();
unsigned int getDepth(unsigned int);
private:
cNode *nextSmaller, *nextBigger;
cData *data;
};
class cEndnode:public cNode
{
public:
//TODO Optimize! there are 2^(n+1) endnodes in a tree wich each take 4B!
cEndnode();
~cEndnode();
cData getDataObject();
/*
* returns dataObject
*/
void insert(cData*, cNode** );
/*
* Inserts *cData into tree
*/
void remove(cData*, list<cData>*, cNode**);
/*
* Removes *cData from tree
*/
cData* search(string);
/*
* 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);
private:
};
#endif /* SRC_CNODE_H_ */
|