On Thu, 24 May 2012, Bruce wrote: > 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
(Completely giving up anything I knew about binary trees now, because it wasn't much and it wasn't even from a book): You said that you can traverse from any node in the tree. Consequently every node has to provide such functionality. I don't deem it necessary to distinguish between root and other nodes. The code is only once there anyway. It could even have helped in your case to "em-parent" (sorry, not a native English speaker) a node that you formerly assumed to be the root like NewNode.Left = RootNode RootNode = NewNode As interesting as it sounds, I'm probably not the right person to work on this. I don't have much time for (I don't think so but from a pure conscientiousness point I need to prepare my A-level a bit) and nobody else wants to wait until I finish the theory ;) Regards, Tobi ------------------------------------------------------------------------------ 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
