[Gambas-user] Data Structures like C++

Thu May 24 11:07:21 CEST 2012

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 at 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 at 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