Proposal for Tree API for JSAV

5 replies [Last post]
ville
ville's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 559

Hi,

Based on email discussions with Tom, here is an initial version for an API for tree support in JSAV. I hope this is detailed enough for us to start a conversation to tune it, since I’m sure I’ve not considered all details. The following draft is based on the implementations in Matrix and JHAVÉ.

The idea is for the structures to form a "class" hierarchy: Tree <- Binary Tree <- Binary Search Tree and TreeNode <- BinaryTreeNode.

The structures can be initialized using the functions of an JSAV instance. For example:
jsav.ds.tree(5) would return a new tree with root element 5
jsav.ds.binarytree(5) would return a new tree with root element 5
jsav.ds.bst([5, 3, 9, 10]) would return a BST with value 5, 3, 9, and 10 inserted

Common functions

These are functions that all the structures below will have.
- css(propertyName): returns the value for the given CSS property
- css(propertyName, value): sets the value of the given CSS property
- css({map}): sets values of the CSS properties in the map
- id(): returns the ID of the structure
- id(newId): sets the ID of the structure

Tree

- root(): returns the root of this tree
- root(Node): sets the root of this tree
- newNode(value): creates a new node that can be added to this tree, "subclasses" should override
- height(): returns the height of the tree
- layout(): (re)calculates the layout for the tree

Binary Tree

- root(BinaryNode)
- newNode(value)

Binary Search Tree

- insert(value): inserts the given value to this tree
- search(value): searches for the given value from this tree
- delete(value): deletes the given value from this tree
- empty(): empties the tree (do we need this????)

TreeNode

- value(): returns the value stored in this node
- value(newValue): sets the value
- parent(): returns the parent of this node
- parent(newParent): sets the parent
- edgeToParent(): returns the edge that connects this node to its parent
- edgeToParent(newEdge): sets the edge
- child(pos): returns the pos:th child of this node
- child(pos, Node): sets the pos:th child
- child(Node): adds a child node

BinaryTreeNode

- left(): returns the left child, undefined if no left child
- left(Node): sets the left child
- right(): returns the right child, undefined if no right child
- right(Node): sets the right child

Edge

- start(): returns the start node of this edge
- start(Node): sets the start node of this edge
- end(): returns the end node of this edge
- end(Node): sets the end node of this edge
- weight(): returns the weight of this edge
- weight(newWeight): sets the weight of this edge

In addition to these, Matrix specifies algorithms for Tree, more specifically, different tree traversal algorithms. I don’t think these should be in the Tree structure itself, but rather in their own namespace. Perhaps JSAV.ds.tree.inorder or something similar. Same could be done for insert, search, and delete for BST, but I do think them more as properties of the structure than algorithms.
The visualizing algorithm for shellsort could be in JSAV.ds.array.shellsort also. It would be nice to have a library of algorithms that can be called to visualize that algorithm. What do you think?

Ville Karavirta, Aalto University, http://villekaravirta.com/

shaffer
shaffer's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 2019
Re: Proposal for Tree API for JSAV

Ville — This looks like a good start! I have a few comments and questions.

> The structures can be initialized using the functions of an JSAV instance. For example:
> jsav.ds.tree(5) would return a new tree with root element 5
> jsav.ds.binarytree(5) would return a new tree with root element 5
> jsav.ds.bst([5, 3, 9, 10]) would return a BST with value 5, 3, 9, and 10 inserted

We might need some more complex support if you want to handle initializing a tree with multiple values. While yes, a set of values can be inserted into a BST, the BST is not uniquely determined simply by a set of values (though one could uniquely determine it by the order of the inserts). More generally, if I want a specific binary tree (not a BST), or specific heap, or other tree-like structure, I will have to be able to provide structure information to get the desired shape.

Common functions

> - css({map}): sets values of the CSS properties in the map

I don’t understand this one.


> - id(): returns the ID of the structure
> - id(newId): sets the ID of the structure

I don’t understand why we want to get/set an ID.

Tree

> - layout(): (re)calculates the layout for the tree

How is the layout represented, returned, and manipulated?

Binary Search Tree

>- empty(): empties the tree (do we need this????)

I doubt that we need it. It is probably just as easy to re-create/re-initialize.

TreeNode

Take a look at the splaytree insert at http://research.cs.vt.edu/AVresearch/searchtree/all3applets.html for an example of the sort of animation that I ultimately will want to be able to do.


> The visualizing algorithm for shellsort could be in JSAV.ds.array.shellsort also. It would be nice to have a library of algorithms that can be called to visualize that algorithm. What do you think?

I do not understand what you want to do with this. I do not see how I would "reuse" the shellsort visualization elsewhere.

 

 

ville
ville's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 559
Re: Proposal for Tree API for JSAV

shaffer wrote:

> The structures can be initialized using the functions of an JSAV instance. For example:

> jsav.ds.tree(5) would return a new tree with root element 5 

> jsav.ds.binarytree(5) would return a new tree with root element 5 

> jsav.ds.bst([5, 3, 9, 10]) would return a BST with value 5, 3, 9, and 10 inserted

We might need some more complex support if you want to handle initializing a tree with multiple values. While yes, a set of values can be inserted into a BST, the BST is not uniquely determined simply by a set of values (though one could uniquely determine it by the order of the inserts). More generally, if I want a specific binary tree (not a BST), or specific heap, or other tree-like structure, I will have to be able to provide structure information to get the desired shape.

Any suggestions on how to provide the structure information? Something like a nested array describing the structure, perhaps?

I think it should be possible to initialize a tree from HTML as well, like for the array. So something like:

<div class="jsavbinarytree" id="mytree">

  <div class="jsavnode" id="root">10</div>

  <div class="jsavnode" data-parent="root" data-role="rightchild">7</div>

  <div class="jsavnode" data-parent="root" data-role="rightchild">9</div>

</div>

 and then only give the ID of the HTML DOM element as a parameter to the constructor.

 

shaffer wrote:

 > - css({map}): sets values of the CSS properties in the map

 I don’t understand this one.

 The idea is to have a general function that enables animating the colors of parts of the structure. Like in the shellsort animation, you set the blue color with arr.css({"background-color": "blue"}) or something similar.

shaffer wrote:

> - id(): returns the ID of the structure

> - id(newId): sets the ID of the structure

I don’t understand why we want to get/set an ID.

 There will be cases where we need to refer to a certain element (see, for example, the tree HTML above). The array already has these functions, even though they are not documented.

 

shaffer wrote:

 > - layout(): (re)calculates the layout for the tree

 How is the layout represented, returned, and manipulated? 

 I imagine it would work like for the array. The layout() function of a tree can be called whenever it needs to be updated. It does not return the layout, but changes the CSS positioning properties (properties left and top) of the elements of the tree. I think we’ll also need an option to specify if the changes in the layout should be animated or not.

 The layout will be presented with HTML elements for the nodes and an SVG overlay for the edges. The positioning will be done with CSS for the nodes and with pixel based layout for the SVG elements. I already have a layout algorithm implemented as part of JSXaal library, and it should be simple to change it to work with JSAV.

 

shaffer wrote:

 >- empty(): empties the tree (do we need this????)

 I doubt that we need it. It is probably just as easy to re-create/re-initialize. 

 True. We can always add it if we suddenly need it.

shaffer wrote:

 Take a look at the splaytree insert at http://research.cs.vt.edu/AVresearch/searchtree/all3applets.html for an example of the sort of animation that I ultimately will want to be able to do. 

 The animations don’t work well enough on my Mac for me to get a clear picture of what the animation does. For some reason, the animation is *really* slow, and some of the elements move where they probably should not.

 

shaffer wrote:

 > The visualizing algorithm for shellsort could be in JSAV.ds.array.shellsort also. It would be nice to have a library of algorithms that can be called to visualize that algorithm. What do you think? 

I do not understand what you want to do with this. I do not see how I would "reuse" the shellsort visualization elsewhere.

 Well, I think we already have the same implementation of shellsort in the slideshow version and the AV version. And it will probably be needed in the proficiency exercise as well. But you’re right, outside of the shellsort visualizations, there is not much use for it.

naps
Offline
White BeltYellow BeltGreen BeltRed Belt
Joined: 2009-06-11
Posts:
Points: 65
Re: Proposal for Tree API for JSAV

ville wrote:
 

  The idea is to have a general function that enables animating the colors of parts of the structure. Like in the shellsort animation, you set the blue color with arr.css({"background-color": "blue"}) or something similar.

 I imagine it would work like for the array. The layout() function of a tree can be called whenever it needs to be updated. It does not return the layout, but changes the CSS positioning properties (properties left and top) of the elements of the tree. I think we’ll also need an option to specify if the changes in the layout should be animated or not.

 The layout will be presented with HTML elements for the nodes and an SVG overlay for the edges. The positioning will be done with CSS for the nodes and with pixel based layout for the SVG elements. I already have a layout algorithm implemented as part of JSXaal library, and it should be simple to change it to work with JSAV.

 

So what I’m gathering from this is that the visual effects of the tree AV will be almost entirely controlled by CSS.   That’s not bad, but it does force us to really document all the CSS properties that control the visual effects.   Right now the tree API tends to focus on functions that manipulate the tree and not on the CSS that will define the visual effects.   Ultimately it seems to me that the API must also include thorough documentation of those effects controlled by CSS and also a description of how to add to those effects by extending the existing CSS.   Is that what’s envisioned?   If not, I fear we will discourage a variety of people from becoming involved in developing JSAV-based AV’s because the details of how to make the AV look the way one wants it to look will be buried in the CSS.   

ville
ville's picture
Offline
White BeltYellow BeltGreen BeltRed BeltBlack Belt
Joined: 2009-05-28
Posts:
Points: 559
Re: Proposal for Tree API for JSAV

naps wrote:

So what I’m gathering from this is that the visual effects of the tree AV will be almost entirely controlled by CSS.   That’s not bad, but it does force us to really document all the CSS properties that control the visual effects.   Right now the tree API tends to focus on functions that manipulate the tree and not on the CSS that will define the visual effects.   Ultimately it seems to me that the API must also include thorough documentation of those effects controlled by CSS and also a description of how to add to those effects by extending the existing CSS.   Is that what’s envisioned?   If not, I fear we will discourage a variety of people from becoming involved in developing JSAV-based AV’s because the details of how to make the AV look the way one wants it to look will be buried in the CSS.   

Yes, good documentation is something we must have in order for anyone to use the library.

While the API only has the general css(…) function at the moment, nothing prevents us from adding functions that make specific effects on the tree/node/edge, kind of like the highlight() funciton for array. Adding new functions using the general css function should be simple. At this point, I couldn’t figure out what such functions we need, so I left it to the general version. If you have some specific needs in mind, let me know.

naps
Offline
White BeltYellow BeltGreen BeltRed Belt
Joined: 2009-06-11
Posts:
Points: 65
Re: Proposal for Tree API for JSAV

 I’ve now created the draft of a storyboard for BST’s (follow this link) that requires some slideshows and other AV’s.   Hopefully, as progress is made developing the Tree API, the API can then be used to splice the appropriate slideshows and AV’s into the storyboard.