Author
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..."
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.
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.
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!
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!
Author
(*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..."
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..."
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
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
Author
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..."
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..."
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.
On the contrary, trees are quite ewasy to code.
Message from above:
Damn, my hair is grey!
Message from above:
Damn, my hair is grey!
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
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
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
Two more hours and I can get the heck out of this office and run away to sweet sweet weekend. woooo
Tony
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
