Tree API blog post
Locked
 
|
Hello everyone,
Next week I'm consulting with mentors on how to design an API for Tree data structures. I was researching a bit and wrote this blog post as a starting point: https://pharokeepers.github.io/pharo/2019/06/30/Application-Programming-Interface-API.html Feedback and ideas are more than welcome :) Best regards, Smiljana Knezev |
Re: Tree API blog post
|
|
Hi Smiljana,
In the ideas/inspiration front maybe you could check my outliner prototype for data activism, visualization and storytelling, called Grafoscopio[1] [1] https://mutabit.com/grafoscopio/index.en.html The notebook interface models a document as a tree. It was my first program made on Pharo to learn it (and also to make research based design for my PhD), so there is newbie code still there. I'm slowly remaking it, but was really helpful to have an environment that didn't punish me for my learning process and allowed me to refactor the prototype as my understanding of the problem, prototype and coding environment as improving. In any case, I remember needing tree objects implemented in Pharo, but I didn't find anything, so I implemented them by my own. Install it and check the manual (is a little bit outdated, but it should work). Hopefully Grafoscopio can be insightful for your project and also I'm interested in feedback about it (and with more time to address it, after finally finishing the PhD and just waiting for the long bureaucratic graduation process and paperwork to finish). Cheers, Offray On 30/06/19 5:38 a. m., Smiljana Knezev wrote: > Hello everyone, > > Next week I'm consulting with mentors on how to design an API for Tree > data structures. I was researching a bit and wrote this blog post as a > starting > point: https://pharokeepers.github.io/pharo/2019/06/30/Application-Programming-Interface-API.html > > Feedback and ideas are more than welcome :) > > Best regards, > Smiljana Knezev |
|
|
Hi Offray, Thank you for your suggestion I will definitely look into it and tell you what I think. It sounds interesting. Good luck with your PhD! I hope everything goes well :) All the best, Smiljana чет, 18. јул 2019. у 23:23 Offray Vladimir Luna Cárdenas <[hidden email]> је написао/ла: Hi Smiljana, |
|
|
In reply to this post by Smiljana Knezev
I've been pondering this reply for a while. There are so *many* kinds of tree. There are rooted trees (very popular in computing) and unrooted trees (what you get from some phylogenetic reconstructions and of course the spanning tree of a graph). There are trees with and without parent links. There are inverted trees with child->parent but no parent->child links. There are fully threaded, half threaded, and unthreaded trees. There are binary, ternary, ..., and rose trees. There are ordered and unordered trees. There are unbalanced, height balanced, and weight balanced trees. There are trees with shareable substructures and trees where everything is locked into place (the DOM). There are trees with no fingers, single fingers, and multiple fingers. There are trees that do not support concurrency, that support concurrent lookup, and that support concurrent changes. The model described at your link is pretty close to the DOM except for modelling the child sequence of a node as an array instead of a doubly linked list. This means that while you *can* implement "left/right sibling" - if no parent, return nil - find index of node in parent's child array - if at beginning/end return nil - otherwise report previous/next element of parent's child array but it takes O(#children) time instead of O(1) time. For argument's sake, let us imagine a storage model in which - an object with n slots takes n+1 words - an array with n elements takes n+2 words and let us consider a node with n children. Your structure (label, array of children, parent) takes 6+n words in addition to the space needed by the child nodes themselves. A (label, first child, next sibling) structure takes 4 words. With a grand total of M nodes, your structure takes 7M words, while the other takes 4M words. The two data structures can represent exactly the same abstract values, but they are good at different things. My library, for example, contains Tree TreeWithParent KeyedTree KeyedTreeWithParent AssociationTree AssociationTreeWithParent SortedSet (a splay tree) SortedBag (a splay tree) SortedDictionary (a splay tree) TernarySet (a ternary search tree) TernaryBag (ditto) TernaryDictionary (ditto) The sets, bags, and dictionaries *hide* the internal trees; what matters is that they are sets, bags, and dictionaries, not that they are trees. With such a great variety, I think it would be most useful to pick a *task* for which some kind of tree is useful and implement *that* kind of tree and use it for *that* task. As one possible example, consider the Document Object Model, which can be implemented using (parent, first child, last child, previous sibling, next sibling) with node-specific additional data, and build an implementation of CSS selectors atop it. plus a number of other kinds of trees, including On Sun, 30 Jun 2019 at 22:39, Smiljana Knezev <[hidden email]> wrote:
|
«
Return to Pharo Smalltalk Users
|
1 view|%1 views
| Free forum by Nabble | Edit this page |