On Wed, 2012-05-23 at 17:19 +0200, tobi wrote: > On Thu, 24 May 2012, Bruce wrote: > > On Mon, 2012-05-21 at 22:25 +0200, Benoît Minisini wrote: > > > > > * Tree > > > * Graph > > > > > > Native implementation of that would be interesting. > > > > > > Any volunteer? :-) > > > > > I think trees are easily implemented directly in gambas using Emil's > > suggestions regarding object references as a general n-tree can be > > implemented as a B-tree using something like > > > > Class CNode > > public data as Variant > > public left as CNode > > public right as CNode > > Public Sub PreOrder() as Variant[] > > blah blah ... etc according to Mr Knuth > > End > > > > where "left" is the first child and "right" is the first sibling. Read > > Knuth Vol 3 for the truth (I had to go searching through the attic to > > find my copy.) > > > > Now Graphs are M U C H more interesting! > > > > Someone said that they couldn't think of a use for them. Well > > here's one, UML diagrams are all directed graphs. In fact much > > of OO thinking is actually (mathematically) directed graphs. > > Nodes and edges. From use cases through structural models, > > component models, in fact the whole she-bang. > > > > > > Getting back to trees. The funny thing is that I had a real need to > > construct a n-tree this week to solve a problem I had with populating a > > gambas treeview from a persistence store where the nodes where out of > > order, i.e. the parents were later in the storage than the children (the > > code is a hack and I choose not to share it.) Suffice to say that > > Demosthenes original post prompted me to go searching through the attic. > > > > .. found some interesting stuff, by the way .. (No, lets not go there.) > > > > Getting back to the point, I think a gb.datastructures component is an > > excellent idea. I can't help much on the dev side as I'm pretty poor at > > C/C++ (can "read only") and am totally lost with Benoit's macros but I'd > > be willing to put in much effort at testing and proving. Ah! Linked > > lists, how many times have I needed them and built them from scratch. > > > > Bruce > > > > > > > > ------------------------------------------------------------------------------ > > Live Security Virtual Conference > > Exclusive live event will cover all the ways today's security and > > threat landscape has changed and how IT managers can respond. Discussions > > will include endpoint security, mobile security and the latest in malware > > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > _______________________________________________ > > Gambas-user mailing list > > Gambas-user@lists.sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/gambas-user > > Hi, > > so what syntax did you desire for an n-tree then? You presented a b-tree > above, this appears generic > to me... I certainly lack theory on those things. > > But shouldn't it be less annoying to get to level 3 than > "Root.left.left.left" ? > There are a lot of purposes and designs of trees (graphs), right? To > implement a certain idea would > not be too difficult but instead to implement only one of those as a generic > tree (graph) which is > then able to be inherited and specialised, maybe in gambas, - that's what I > find difficult (no > wonder without theory). > > Regards, > Tobi Hi Tobi,
I probably didn't make it clear. "Any n-tree can be transformed into a b-tree where the left branch is the first child and the right branch is the first sibling." To be more correct I should have said "Any k-ary tree can be represented as a binary tree where the left branch is the first child and the right branch is the next sibling". The theory is in wikipedia here: http://en.wikipedia.org/wiki/Binary_tree#Encoding_general_trees_as_binary_trees. These binary trees have well known (Knuth and others) algrorithms for different actions to be used on the binary tree, insertions, deletions, (graft and prune), traversals in particular orders, searches, sorts etc etc. The application of a binary tree structure to suit a particular problem is a different matter. This is what you can use the tree for or how to apply the tree "structure" to solve a particular problem. In my case, which was a set of rows in a database containing a "data" component and a "parent" value that I was trying to populate a treeview with (1800 records) where the rows were out of order with respect to building the treeview. It was an n-level "table of contents" thing. Rather than try to traverse the database several times and resolve getting each toc level resolved, I just read the whole thing as a single db.result and created a binary tree of the above type, creating dummy parent nodes as soon as I had a need for them and setting their "data" to a placebo value. When I later located the real parent row in the db.result iteration all I had to do was replace the placebo value with the nodes real data. At the end of the db.result iteration, the treeview could be populated via a pre-order traversal of that tree. Bingo. Regarding your "root,left,left,left" annoyance. No that is the way you need to get to the first node at a particular level of the tree. But once you're there there is an algorithm for traversing the tree at that level, an in-order traverse. In fact I could have used the in-order traversal equally well to solve my problem. What I am saying regarding "it would be nice to have" these things in a gb.component is they could provide the structure and the fundamental algorithms. The application of those things to the problem at hand still requires an understanding of how such structures and methods can be used to solve that problem, but at least the underlying infrastructure would be there. Every time one of these problems pops up in my life I have to go find which gambas project it was where I created the structures and algorithms. The trouble is I only ever do the minimum necessary in a particular project. So if, for problem "x" I reckon that a binary tree in-order search is needed then which *^%$@ project did I use that last in, etc. etc. and then get wrapped up in the code for the tree itself rather than its' application to the problem at hand. I think that the binary tree structure only requires two classes, say "bintree" and "bintreenode". The bintree class contains the root node and all the basic algorithms. The bintreenode class is a dumb data and reference holder. Unlike what I inferred in my first post it has no algorithm methods, it is just a structure. I'd also hazard a guess that much of the code needed is already somewhere in gambas hiding in the Collection indexing code, all it needs is exposing! Bruce ------------------------------------------------------------------------------ Live Security Virtual Conference Exclusive live event will cover all the ways today's security and threat landscape has changed and how IT managers can respond. Discussions will include endpoint security, mobile security and the latest in malware threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ _______________________________________________ Gambas-user mailing list Gambas-user@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/gambas-user
