Nebula
Loading...
Searching...
No Matches
simpletree.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
12#include "core/types.h"
13#include "util/array.h"
14
15//------------------------------------------------------------------------------
16namespace Util
17{
18template<class VALUETYPE> class SimpleTree
19{
20public:
22 class Node
23 {
24 public:
28 Node(const Node& parent, const VALUETYPE& val);
32 const Node& operator[](IndexT i) const;
36 const Node& Child(IndexT i) const;
38 Node& Child(IndexT i);
40 bool HasParent() const;
42 Node& Parent();
44 const Node& Parent() const;
46 void Clear();
48 SizeT Size() const;
50 bool IsEmpty() const;
52 Node& Front() const;
54 Node& Back() const;
56 void Append(const VALUETYPE& val);
58 void Erase(IndexT i);
60 void Insert(IndexT index, const VALUETYPE& val);
62 IndexT Find(const VALUETYPE& val) const;
64 VALUETYPE& Value();
66 const VALUETYPE& Value() const;
67
68 private:
70 VALUETYPE value;
72 };
73
77 Node& Root();
79 const Node& Root() const;
80
81private:
83};
84
85//------------------------------------------------------------------------------
88template<class VALUETYPE>
90 parent(0)
91{
92 // empty
93}
94
95//------------------------------------------------------------------------------
98template<class VALUETYPE>
99SimpleTree<VALUETYPE>::Node::Node(const Node& p, const VALUETYPE& val) :
100 parent(const_cast<Node*>(&p)),
101 value(val)
102{
103 #if NEBULA_BOUNDSCHECKS
104 n_assert(0 != this->parent);
105 #endif
106}
107
108//------------------------------------------------------------------------------
111template<class VALUETYPE>
113{
114 for (IndexT i = 0; i < this->children.Size(); i++)
115 {
116 delete children[i];
117 }
118}
119
120//------------------------------------------------------------------------------
123template<class VALUETYPE>
124const typename SimpleTree<VALUETYPE>::Node&
126{
127 return *(this->children[i]);
128}
129
130//------------------------------------------------------------------------------
133template<class VALUETYPE>
136{
137 return *(this->children[i]);
138}
139
140//------------------------------------------------------------------------------
143template<class VALUETYPE>
144const typename SimpleTree<VALUETYPE>::Node&
146{
147 return *(this->children[i]);
148}
149
150//------------------------------------------------------------------------------
153template<class VALUETYPE>
156{
157 return *(this->children[i]);
158}
159
160//------------------------------------------------------------------------------
163template<class VALUETYPE>
164bool
166{
167 return (0 != this->parent);
168}
169
170//------------------------------------------------------------------------------
173template<class VALUETYPE>
174const typename SimpleTree<VALUETYPE>::Node&
176{
177 #if NEBULA_BOUNDSCHECKS
178 n_assert(0 != this->parent);
179 #endif
180 return *this->parent;
181}
182
183//------------------------------------------------------------------------------
186template<class VALUETYPE>
189{
190 #if NEBULA_BOUNDSCHECKS
191 n_assert(0 != this->parent);
192 #endif
193 return *this->parent;
194}
195
196//------------------------------------------------------------------------------
199template<class VALUETYPE>
200void
202{
203 this->children.Clear();
204}
205
206//------------------------------------------------------------------------------
209template<class VALUETYPE>
210SizeT
212{
213 return this->children.Size();
214}
215
216//------------------------------------------------------------------------------
219template<class VALUETYPE>
220bool
222{
223 return this->children.IsEmpty();
224}
225
226//------------------------------------------------------------------------------
229template<class VALUETYPE>
232{
233 return *(this->children.Front());
234}
235
236//------------------------------------------------------------------------------
239template<class VALUETYPE>
242{
243 return *(this->children.Back());
244}
245
246//------------------------------------------------------------------------------
249template<class VALUETYPE>
250void
252{
253 Node* newNode = new Node;
254 newNode->parent = this;
255 newNode->value = val;
256 this->children.Append(newNode);
257}
258
259//------------------------------------------------------------------------------
262template<class VALUETYPE>
263void
265{
266 delete this->children[i];
267 this->children.EraseIndex(i);
268}
269
270//------------------------------------------------------------------------------
273template<class VALUETYPE>
274const VALUETYPE&
276{
277 return this->value;
278}
279
280//------------------------------------------------------------------------------
283template<class VALUETYPE>
284VALUETYPE&
286{
287 return this->value;
288}
289
290//------------------------------------------------------------------------------
293template<class VALUETYPE>
294IndexT
295SimpleTree<VALUETYPE>::Node::Find(const VALUETYPE& val) const
296{
297 IndexT i;
298 SizeT num = this->children.Size();
299 for (i = 0; i < num; i++)
300 {
301 if (val == this->children[i]->Value())
302 {
303 return i;
304 }
305 }
306 return InvalidIndex;
307}
308
309//------------------------------------------------------------------------------
312template<class VALUETYPE>
314{
315 // empty
316}
317
318//------------------------------------------------------------------------------
321template<class VALUETYPE>
324{
325 return this->rootNode;
326}
327
328//------------------------------------------------------------------------------
331template<class VALUETYPE>
332const typename SimpleTree<VALUETYPE>::Node&
334{
335 return this->rootNode;
336}
337
338} // namespace Util
339//------------------------------------------------------------------------------
Nebula's dynamic array class.
Definition array.h:60
public node class
Definition simpletree.h:23
SizeT Size() const
number of children
Definition simpletree.h:211
const Node & operator[](IndexT i) const
get read-only child by index
Definition simpletree.h:125
Node * parent
Definition simpletree.h:69
void Insert(IndexT index, const VALUETYPE &val)
insert element before element at index
Node & Parent()
read/write access to parent
Definition simpletree.h:188
~Node()
destructor
Definition simpletree.h:112
void Append(const VALUETYPE &val)
add element at back of array
Definition simpletree.h:251
IndexT Find(const VALUETYPE &val) const
find identical element (slow);
Definition simpletree.h:295
VALUETYPE value
Definition simpletree.h:70
Node()
default constructor
Definition simpletree.h:89
void Clear()
clear children
Definition simpletree.h:201
void Erase(IndexT i)
erase at index
Definition simpletree.h:264
bool IsEmpty() const
return true if empty
Definition simpletree.h:221
bool HasParent() const
return true if the node has a parent
Definition simpletree.h:165
Node & Front() const
return first element
Definition simpletree.h:231
Node & Back() const
return last element
Definition simpletree.h:241
Array< Node * > children
Definition simpletree.h:71
VALUETYPE & Value()
read/write access to value
Definition simpletree.h:285
const Node & Child(IndexT i) const
get read-only child element at index
Definition simpletree.h:145
A simple tree class which stores its nodes in Util::Arrays.
Definition simpletree.h:19
Node rootNode
Definition simpletree.h:82
const Node & Root() const
read-only access to root element
Definition simpletree.h:333
SimpleTree()
default constructor
Definition simpletree.h:313
Node & Root()
read/write access to root element
Definition simpletree.h:323
#define n_assert(exp)
Definition debug.h:50
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
static const int InvalidIndex
Definition types.h:54
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48