Archived

This topic is now archived and is closed to further replies.

Solstice

Trees

Recommended Posts

Could anyone suggest a good STL-like Tree class? I need iterators and resonable documentation. I would use STL, but ummmm, there *isn''t* an STL tree class!! -Solstice deninet.com aeris.deninet.com "...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Do you actually _need_ a tree, or do you merely want one?

The associative containers are normally implemented with some kind of a tree (I think all the implementations I use use red-black trees).

They provide iterators and there exists good documentation. Do they not do what you want?

Binary trees are normally a means to an end rather than the desired structure. They provide a convenient mechanism for building maps and sets and things like that (they have fast lookups), and that''s normally the kind of interface you''d want to give them, as generally you don''t care to mess about with nodes and tree pointers and other such nonsense.

Share this post


Link to post
Share on other sites
As I do not completeley trust stl I made an own tree. Of course it works just fine and I used it in conjunction with a list class that I developed to sort a random file containing 1,000,000 integer numbers in less that 2 and a half minuit.(irellevant) Solstices question was quite good and I as him/her would like to know what you ''want'' a tree for. Trees can be great for sorting stuff (Hash tables are also a fine choise although it took my non-optimized hashing algorith 10 seconds longer to sort the file) but you most definateley do not want to use them as lists (as you need a recursive function to step through it from "front" to "end").

If you think the time it took my algorithm to sort the integers was very long you should keep in mind that my processors frequency is 200 MHz and the time I specified also includes I/O to two ASCII files.



Message from above:
Damn, my hair is grey!

Share this post


Link to post
Share on other sites
(*yawn* mutters: "I should have known better to have cherry coke just before going to bed...")

All very good points. Well, as of right now I''m designing a script interpreter for a game I''m developing. The idea is to have the languge define a hierarchial structure in addition to having some logic elements (Think XML plus funtions and operations). This is why I''m not using Lua or SmallC, being that their function oriented.

Later, however, when I design my game engine, the structures go into Scene tree. This is my theory: Because the script breaks down into a tree, and the Scene tree is the basis of game engine parsing...

So, I think that I need a k-ary tree that can support customizing the node data via an object. I found this class last night:
http://www.damtp.cam.ac.uk/user/kp229/tree/
but I would like to know if there''s something better I can use.



-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Solstice,
The tree you linked to looks GREAT! I''d recommend that you use it. Writing your own tree is not a fun proposition unless you''re nuts (I wrote my own tree, draw your own conclusions.)

One thing you MUST consider before you use this tree is the license. This tree code is GPL. It would be a violation of the code license agreement, and against the law to include this tree code in your software if your software was not "free" as in speech, by the terms of the GPL.

By using GPL code in your source, your code, by default becomes GPL. This is known as the VIRAL nature of the GPL. You can still sell your software but you MUST provide the source code to the opensource/free software community once your software hits the public domain. If you do not provide the source code you are breaking the law and damaging the free software community.

I''d give you my tree but it is GPL as well and I''m afraid this other fella did a better job than I.

RandomTask

Share this post


Link to post
Share on other sites
So how can I work around GPL? I personally don''t mind open-sourcing my project, but everyone else who is working on this might. So how can I work around it?

Currently, I''m studying the tree class I found and then writing my own based on the ideas there.

-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
quote:
Original post by Solstice
So how can I work around GPL? I personally don''t mind open-sourcing my project, but everyone else who is working on this might. So how can I work around it?

Currently, I''m studying the tree class I found and then writing my own based on the ideas there.



Stick it in a DLL. Release the source to the DLL version. Write a wrapper DLL. Link that against the GPLed DLL. The wrapper is tainted, by the GPLed code it''s linked against, so release its source.

Link your program against the wrapper. Your program ought to be tainted by the wrapper -- but you can grant yourself (as the author of the wrapper) a special license whereby you''re permitted to link to it without releasing the source. Because you wrote the wrapper, you can release it under any license you choose (as well as the virally-induced GPL).

Or rewrite the tree using the original as the inspiration. Proving anything would be nigh impossible; one tree class is, more than likely, going to bear a striking resemblance to any other class representing the same kind of tree.

BSDL r0x0r, GPL sux0r.

Share this post


Link to post
Share on other sites
I agree with GameKeeper that a tree class is easy to code. Develop a node class that has four data members: a pointer to the left child, a pointer to the right child, a pointer to the parent node, and a data storage structure. You could templatize the data storage stucture trivially.

And as for parsing the tree, you don''t need recursion. I''ve got a routine that will parse and entire tree of the above nature in about 20 lines of code and no recursion. All that and I''m a moron. 8^)

-Kirk

Share this post


Link to post
Share on other sites
Yeah come on guys trees were the first thing we were taught at school. They are realllly simple to implement. Get yourself a Data Structures and Algorithms in C++ Book of something.

Two more hours and I can get the heck out of this office and run away to sweet sweet weekend. woooo

Tony

Share this post


Link to post
Share on other sites
Well, I''ve implemented trees myself before, for the geometry tree of a 3D renderer that I wrote (I''m still quite proud of that one; texture mapping, software only, no Direct3D or OpenGL, and it still got decent framerates).

What worries me is not what pointer to put where, that''s the easy part. So far i have everything templated, and I''m using a vector to store the children. I''m not sure yet if I what this to be a doubly linked tree, I was thinking of using a stack class in my iterator to maintain the path. This way, I already have a function stack of sorts built into the tree, and there''s less book-keeping.

The hard part for me is just how to stucture the API. My original thought -- way before this thread -- was that I''d get an interator from the tree and use that to insert children. Tree.hh does the same thing but in reverse, you give the tree a interator and value . Perhaps this does make more sense to me this morning than last night. ^_^

Tree.hh also uses two iterators, tree::iterator and tree::sibling_iterator. Which, I''m guessing, interate up and down and left to right respectivly. I would think that could get annoying, so I would like to have just one iterator. Yet, everytime I sit down to code the thing, my mind locks up.

*sigh*

-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Solstice,
Don''t do too many things to get around the GPL. You''ll just make enemies in the community and you''ll be undermining the spirit of the free software community who have your freedom in mind. Just remember if you use a dll that you CANT statically link your application to it. You have to dynamically link to the code.

Tree code isn''t hard by default. If you want to have a full featured tree code base then it is hard. And, by default a binary tree is much easier to code than a dynamic number of branches per node.

RandomTask

Share this post


Link to post
Share on other sites
quote:
Original post by Gamekeeper
On the contrary, trees are quite ewasy to code.


When thinking about stuff like balancing AVL-trees or Red-Black trees there are a lot of words that come to mind. "Easy" isnt one of them.



Once there was a time when all people believed in God and the church ruled. This time is called the Dark Ages.

Share this post


Link to post
Share on other sites
I wouldn''t worry too much about me avoiding GPL completely. The application all of this will eventually end up in uses the Simple Direct Media layer, which is under LGPL. At present, the interpreter will also be under a similar licence. It''s the game that all of this goes into that I''m concerned about.

I have found a way to design the thing at last:

The tree class itself will have two classes inside of it, node and iterator. The node class stores template value T, and a vector for the children. The tree class stores a node -- not a node ref -- that serves as a "deferred root". This turns out to have some advantages.

First of all, one notices that the tree itself is only singly linked, done so to easy book-keeping. It''s the iterator class which helps us out there. The tree iterator actually interates over a vector of children, and one has the option to "step in" or "step out" of the current node. This brings you to the node''s first child or the node''s parent respectivly.

Both of these operations actually work on the "iteration stack", a stack>, are are equivilent to pushing and popping a vector to the stack Because this tree is meant as a language parser, this is really beneficial, since it operates kinda like a function stack.

I''ll have the source and documentation posted on http://docs.deninet.com within a week.


Thanx all!



-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites
Code anyone?


00001
00002 //
00003 // detree.h
00004 //
00005 //
00006 // begin : Thu Feb 7 2002
00007 // copyright : (C) 2002 by Solstice
00008 // email : solstice@deninet.com
00009 //
00011
00012 #include <vector>
00013 #include <stack>
00014 #include <utility>
00015
00016 namespace deml
00017 {
00022 template class tree
00023 {
00024 // member classes
00025 private:
00026
00027 class node
00028 {
00029 public:
00030
00031 T data;
00032 vector children;
00033 };
00034
00035 public:
00036
00042 class iterator
00043 {
00044 public:
00046 iterator(const iterator& i);
00048 iterator& operator++(void);
00050 iterator& operator--(void);
00052 T& operator[](unsigned short);
00054 T& operator*(void);
00055
00058 void step_in(void);
00061 void step_out(void);
00062
00064 unsigned short size(void);
00066 unsigned short depth(void);
00067
00068 friend tree;
00069 private:
00070 iterator(int, vector*);
00071 stack* > > iterationPath;
00072 int iteratorPosition;
00073 vector* iteratorVector;
00074 };
00075
00076 // member functions
00077 public:
00078 /*
00079 tree(void);
00080 ~tree(void);
00081 */
00083 iterator tree_iterator(void);
00084
00086 void append(iterator, T);
00088 void insert(iterator, T);
00090 void replace(iterator, T);
00092 void erase(iterator);
00094 void clear(iterator);
00095
00096 // data members
00097 friend iterator;
00098 private:
00099
00100 node treeRoot;
00101 };
00102 /*
00103 template tree::tree(void)
00104 {
00105 // nothing yet
00106 }
00107
00108 template tree::~tree(void)
00109 {
00110 //clear();
00111 }
00112 */
00113 template tree::iterator tree::tree_iterator(void)
00114 {
00115 vector* children = &(treeRoot.children);
00116 iterator i(0, children);
00117 return i;
00118 }
00119
00120 template void tree::append(iterator i, T data)
00121 {
00122 vector* v = &i.iteratorVector;
00123 node n;
00124 n.data = data;
00125 v->push_back(n);
00126 }
00127
00128 template void tree::insert(iterator i, T data)
00129 {
00130 vector* v = &i.iteratorVector;
00131 node n;
00132 n.data = data;
00133 v->insert(i.iteratorPosition, n);
00134 }
00135
00136 template void tree::replace(iterator i, T data)
00137 {
00138 vector* v = &i.iteratorVector;
00139 node* n = v[i.iteratorPosition];
00140 n->data = data;
00141 }
00142
00143 template void tree::erase(iterator i)
00144 {
00145 vector* v = &i.iteratorVector;
00146 v->erase(i.iteratorPosition);
00147 }
00148
00149 template void tree::clear(iterator i)
00150 {
00151 vector* v = &i.iteratorVector;
00152 v->clear();
00153 }
00154
00155 template tree::iterator::iterator(const tree::iterator& i)
00156 {
00157 iterationPath = i.iterationPath;
00158 iteratorPosition = i.iteratorPosition;
00159 iteratorVector = i.iteratorVector;
00160 }
00161
00162 template tree::iterator::iterator(int i, vector* v)
00163 {
00164 iteratorPosition = i;
00165 iteratorVector = v;
00166 }
00167
00168 template tree::iterator& tree::iterator::operator++(void)
00169 {
00170 iteratorPosition++;
00171 return (*this);
00172 }
00173
00174 template tree::iterator& tree::iterator::operator--(void)
00175 {
00176 iteratorPosition--;
00177 return (*this);
00178 }
00179
00180 template T& tree::iterator::operator[](unsigned short index)
00181 {
00182 node n = iteratorVector[index];
00183 return n.data;
00184 }
00185
00186 template T& tree::iterator::operator*(void)
00187 {
00188 node* n = &iteratorVector[iteratorPosition];
00189 return n->data;
00190 }
00191
00192 template void tree::iterator::step_in(void)
00193 {
00194 node* n = &iteratorVector[iteratorPosition];
00195 pair* > p;
00196
00197 p.first = iteratorPosition;
00198 p.second = iteratorVector;
00199
00200 iterationPath.push(p);
00201 iteratorPosition = 0;
00202 iteratorVector = &n->children;
00203 }
00204
00205 template void tree::iterator::step_out(void)
00206 {
00207 pair* > p = iterationPath.pop();
00208
00209 iteratorPosition = p.first;
00210 iteratorVector = p.second;
00211 }
00212
00213 template unsigned short tree::iterator::size(void)
00214 {
00215 return iteratorVector->size();
00216 }
00217
00218 template unsigned short tree::iterator::depth(void)
00219 {
00220 return (iteratorPath->size() + 1);
00221 }
00222 };


-Solstice

deninet.com
aeris.deninet.com

"...I was given three choices, the earth, the stars, or..."

Share this post


Link to post
Share on other sites