Here's my attempt at implementing Map in LV8.5. Very straightforward. I need someone to write the tree balancing algorithm on one of the subVIs (Map.lvlib:Branch Node.lvclass:Node Insert Pair.vi). I don't have the patience to hunt down the AVL-tree balancing algorithm and make it into LabVIEW code.

New users of LabVIEW classes:
THE CODE IN THIS .zip FILE IS REALLY ADVANCED USE CASE OF LabVIEW CLASSES. Novices to classes may be scared off from LabVIEW classes thinking that all the code is this "magickal". Please be aware that this is something I've cooked up to test the limits of LV's power, and I've used some quite arcane syntax. The Map class itself is really useful and you're free to try it out in your code. Just don't take its complexity as typical of LVClasses.

For the cutting edge leet:
You'll find some *fascinating* code that definitely only works in LV8.5 (uses the new inplaceness nodes) on the block diagram of Map.lvlib:Branch Node.lvclass:Node Delete Key.vi. 20 points and a bowl of gruel to the first person who can explain why the *empty* Sequence Structure is labeled "Do not delete". ;-)

 Map_Class.zip ( 272.73K ) Number of downloads: 220


[EDIT as of November 2007] There is a new revision of the Map Class which now includes tree balancing. Many thanks to Jason Dunham who did the work of implementing the tree balancing algorithm. Dunham has released his changes to these VIs to NI so that we can move toward including them in a future shipping version of LabVIEW. These VIs are released today under the same license as applies to any VIs in vi.lib that ship from National Instruments. You have the same rights to copy, distribute and modify these VIs as you have to copy, distribute or modify the VIs in vi.lib. Please see your National Instruments LabVIEW license agreement for details.
 MapClassAVL.zip ( 836.03K ) Number of downloads: 179

...and I'll throw in some parsley to garnish the gruel for an explanation of the two Always Copy and Swap Value nodes to the left of the "Do Not Delete" Sequence Structure.

-D

This post has been edited by Darren: Aug 23 2007, 05:08 AM

That's a tricky one, I guess it has to do something with garbage collection.
Here is how it looks if you analyse it with a LabVIEW based UML Modeller ;-)


BTW, how do you set the default data to a leaf Node in the Map class attribute named Root which is a Map Node Object?

Cheers, Mikael

I modified your class to have a little more informative probing system. Now each class in the project has a probe that populates a tree recursively. This way you can actually see what is the structure of the binary tree used in this implementation.
 Map_Class_TM.zip ( 337.43K ) Number of downloads: 95




This particular VI is actually quite weird. Would you like to shed light on what's happing in the method and why all those switch nodes are needed and why do you have always copy nodes and why do you have that 'do not remove' sequence.

EDIT: I spend some time trying to figure out what the heck is going on in this particular VI. I can understand from dataflow point of view what's going on but I've no freaking idea of why AQ is using swap values and always copy nodes as well as this empty structure. I tried to profile the VI with LabVIEW memory profiler. The memory consumption was not always the same, which is weird. Removing the wire between the sequence frame and the bundle node seem to decrease the memory usage according to the profiler. I tried to use show buffer allocations tool. It seems that this tool is not very informative with LVOOP as there were dots everywhere. Champion or not, I still don't understand LabVIEW memory management and the functionality of the in-placeness algorithm at the depth I'd like to. If only there was some material to read but I guess I've read all there is.

p.s. Can you refer to some location such as Wikipedia where they describe this binary tree map algorithm you are using.

Tomi

http://en.wikipedia.org/wiki/AVL_tree

a) the show buffers tool works fine for LabVIEW classes, and all those dots are places where buffers are allocated, but you need to know that allocating a new LVClass is dirt cheap -- 1 pointer in all cases since there's only a single shared copy of the default default value.
b) As for explanation of the various swap nodes and force copy blocks, read the LVOOP white paper and focus on the section titled "What is the in-memory layout of a class?" and the paragraph that starts with " For advanced LVOOP programmers there is a counterintuitive feature that we considered removing"



In 8.5, drop a constant of class Child and wire it to an indicator of class Parent. Run the VI and then use Make Current Value Default. Change the indicator to a control and move it into the private data control.

Make Current Value Default does not work for LabVIEW classes in LV8.2.

PS: This may be a situation that your UML tool should be aware of ... Class A may have a control of class Parent in its private data, but it may use an even lower Child class as the default value of that control. I don't know if you care to highlight such a situation in the UML, but it is a relationship that LabVIEW has to track in order to know to load the child class into memory whenever Class A loads.

Ok. I read it. I still don't understand what's going on. I now understand that using LabVIEW in recursive data structures may not be safe. However I've created graphs and trees before and they've functioned if you don't care about occasional crashes. I didn't have any of these in-place memory nodes available in LabVIEW 8.2 or 8.2.1. If I interpret you correctly AQ, you are saying that one can use recrusive memory structures but one needs to use some hocus-pocus non-dataflow programming techniques to do this safely. Did I interpret you completely incorrectly? If not, what are these hocus-pocus tricks one needs to use?

My guess: Node Delete Key.vi of Branch Node class calls itself recursively from within in-place memory structure. The in-place memory structure can optimize memory usage only if the buffer that is being edited in-place doesn't get garbage collected. The empty sequence frame is there to keep the edited buffer in memory while the VI is being executed. This somehow affects LabVIEW compilers ability to optimize the execution of the outer in-place memory structure of the calling clone of Node Delete Key.vi.

Was it even close?

The default values is visualized like this:
MyAttribut:int=23
MyObject:BaseClass=LeafClass

But the UML modeller don't look at the default values right now.
When it comes to the default values for a referenced based class, these default values should be wired up in the Create/Constuct-method.
You could still add the equal sign in your design when generating code, but when you do a reverse engineering those will be overwritten.


-Mikael

Hm... I'd consider that a bug. Just as an int can have a specified value of 23, you ought to be able to fully specify the default value of the BaseClass. I wouldn't allow the UML to specify all the fields (after all, the UML didn't go through the class' API to set those fields, so you might be coding an inconsistent class state). But if the fields are already set, the UML shouldn't overwrite with a default instance. In this particular case, the default instance is what is used, but that won't always be true.

At the very least, you should compare the existing value against a default instance before scripting over it and post a warning that the data has been changed to default default value.


Answers will be posted over the weekend or possibly on Monday.

I'm like a child eagerly waiting for Christmas...

oooooh goodie goodie goodie. I'm all a twitter!

And since we all saw what happened the last time Norm got excited, I'm going to go ahead and post this now before it gets worse. ;-)

Let's start with something easy... the case when we are setting a key-data pair into the map and we discover that the value is already in the map. Take a look at the block diagram of Map.lvlib:Branch Node.lvclass:Node Insert Pair.vi

Here we are taking the existing data and swapping it with the new value. What does the Swap primitive buy us? Why didn't I just cross those wires? In this case, I could have, but by using the Swap prim, I'm avoiding two copies of data -- one copy out of the Map structure and one copy into the map structure. No copying needed at all. We're playing with pointers in memory here, gentlemen and ladies. Directly touching memory in a way that LabVIEW has never done before. I point out this simple case since it'll help understand the far trickier case of deleting a node from the tree...

For those of you without LV8.5, here is the block diagram for Map.lvlib:Branch.lvclass:Node Delete Key.vi which caused such consternation in previous posts...

What in Hades is going on here?

1. We are implementing a binary tree. That means that when we delete a node, we now have a left node and a right node. One of those gets put into the tree to take the position of the deleted node. The other must be inserted into the tree as if it was a new node.
2. We want to do #1 WITHOUT MAKING A COPY OF ANYTHING. Why? Because a single node really is an entire sub-tree. We want to simply connect that subtree into a new place in the graph without duplicating all the pointers. Otherwise all of our efficiency is lost.
3. The node that we're going to delete has the left and right subtrees as member data values. When the deleted node reaches the end of its wire, it will disappear from memory AND WILL TAKE ALL OF ITS MEMBER DATA WITH IT. So the first thing to do is to give the node about to be deleted some new values for its left and right nodes. We use the Leaf Node constants. The Force Copy primitives (those little small dots for those of you without LV8.5) keeps LabVIEW from trying to be too smart about optimizing copies. It guarantees that we have an independent value of a Leaf Node, one for left and one for right. We Swap those two in place of the current subtrees of the node being deleted. So our left and right subtrees are now disconnected from the main tree.
4. Why is the Sequence Structure there? Because if we don't wire the output of the Bundle node, LabVIEW will look at the diagram and say, "Hey! This output is unwired. That means the node is a no-op." And it will optimize out the bundle. But in this diagram, even though we're never going to use the deleted node ever again, it isn't a no-op -- it is what severs the deleted node's connection to the left and right subtrees. (Note: After further questions, I posted a clarification of this point here.)
5. Now we have two subtrees. We test to see which one is the deeper tree and swap the wire values so that the deeper one is on the top wire. That one gets to be put in place of the deleted node because it keeps the maximum number of nodes at the highest possible level of the tree. The shallower subtree is then inserted into the map as if it were a new node.

Now, let's consider the implications of this entire VI hierarchy:

There are points in this graph where we are modifying a value on one wire which results in a change in value on another parallel wire. This is a massive no-no for dataflow programming. And yet it works in this situation -- reliably, predictably, and quickly -- without any semaphore or mutex locking. It is the sort of thing that a human being can prove is safe by code inspection but no amount of automated work from the compiler can confirm that (at least with the compiler tech that I have at my disposal -- the NI AI is still holding a grudge against me for introducing it to Goedel's Incompleteness Theorem).

If you coded it wrong, you could crash LabVIEW. Should I then close this door in the compiler? I don't think so. First of all, you can't do any of this without the memory management primitives. Anyone trying to make this work without the Swap will find themselves coding regular LabVIEW and completely unable to get the map to work the way they'd like it to work. Anyone who uses the Swap primitives is definitely on the cutting edge of LabVIEW, because it is so non-intuitive compared with simply crossing the wires. And if you're advanced enough to be playing with these, then I think the full power of options should be open to you.

This hierarchy gives you a Map that is perfect dataflow outside the class --- if you fork the wire, the entire Map duplicates and is thus dataflow safe for all operations, and it can be freely stored in LV2-style globals, global VIs or single-element queues if you decide you need a reference to one. It hides all the "pointer arithmetic" inside its private member VIs, thus guaranteeing the coherency and consistency of the Map and keeping the dangerous dataflow-unsafe functions from being called directly under conditions that might not be safe.

I'm thinking an essay covering the analysis of this diagram and the related VI hierarchy should be added to the Certified LabVIEW Architect exam.

Now, my next challenge to everyone...
Do any of you recall me posting this request for a hack? The suggestion to use MoveBlock is an excellent one. You'll need that in order to complete the next challenge...
Write a VI Hierarchy to implement an arbitrary cyclic graph in pure G. To VIs not in the Graph.lvclass hierarchy, the graph objects should be perfect dataflow -- if you fork the wire, the entire graph replicates. The exposed API should allow you to create a connection between arbitrary nodes in the graph, including the creation of cycles. Inside the class, you may do many dataflow unsafe activities, far worse than the moment to moment crimes of the Map.

I have no idea if this is even possible. This is what we call "research." It's what I spend my spare time on. :-) Good night, and good luck.