Priority Queue by Aristos Queue

[AristosQueue (NI)]

There are several implementations of a priority queue for LabVIEW. None of them quite met my standards, so I wrote my own. I took my time getting it ready for distribution -- given my history as the author of LabVIEW's queue primitives, I figured if I was going to write a priority queue API, I should make it as solid as possible. It is now ready (*fingers crossed*) for prime time.

This API implements a priority queue. It's API is very similar to that provided by the built-in queues of LabVIEW, but with the additional ability to set a priority so that some elements get to jump ahead in line. When you obtain the priority queue, you specify how many levels of priority are desired. Thereafter, messages are enqueued along with an integer specifying that element's priority. High priority (high integer) elements are delivered first. Elements with equal priority are delivered in FIFO order.

These VIs are not polymorphic. The queue is a queue of strings. However, by saving a copy of the API and modifying the enclosed Data.ctl, you can make the queue be typed to your needs.

VIs are saved in LV 2010. The VIs are available either as a VIPackage or a zip.

[LATER] I have now published a new Bounded Priority Queue class that supports a maximum queue size. You can check it out here.

[GregSands]

It appears you've labeled the priority enum the wrong way around in the Test Example.  Apart from that, it seems easy to follow.

[AristosQueue (NI)]

*head smack* It would appear that I need a test harness for my test harness. 🙂

[LATER] Fixed it. Thanks for catching that. I grabbed an old version of the typedef when I was zipping everything up.

[kegghead]

Why do you reverse the order of your queue array before the dequeue loop in Priority Dequeue.vi? It seems to invert your priority system? Your test demonstrates this, I get a returned set of {low1, low2, low3, med, high}. Removing the reverse primitive makes things work as expected.

Interesting way of doing it. I had imagined something quite different involving a sentinal event structure which manages dequeing from the priority queues, but you opted for mutating the priority if a dequeue is pending. I'm still working through this in my mind, but could this not create priority inversion of messages if a say another high priority message manages to get pushed onto the 0th queue before the artificially elevated low priority one is shifted off?

-mje

[AristosQueue (NI)]

I reverse the array so that higher numbers equate to higher priorities. As you can tell from my accidental first post, my early drafts had the lower numbers as lower priority. The higher priority == higher integer is easier (for me and I suspect others) to keep straight mentally. Also, note what I said in my earlier comment to GregS where I posted the corrected enum. It's only the test VI that was messed up, not the queue itself.

The priority isn't mutated at all when there's a dequeue pending. We just use queue zero because it is guaranteed to exist. If there's a dequeue waiting, it doesn't matter which queue gets used --- there's only one message and it is immediately leaving the queue before any other message can arrive. You can't get any priority inversion.

[kegghead]

Ah, I was confused since your enumerator is still defined as {High:0, Med:1, Low:2} in the zip version. So I was under the assumption low number = high priority. In either case, the test.vi is returning the opposite of the expected array.

I now see what you were doing with the priority, since the wait always falls back on the 0th queue if everything is empty, if there's a pending wait due to an empty queue, you use that queue regardless of priority.

[AristosQueue (NI)]

Please try pulling the .zip file again. I think it is correct now.

[gbecker]

Is the clearance of all incoming warnings into to API is done on purpose?

[AristosQueue (NI)]

gbecker: No, that wasn't intentional. I just didn't take warnings into account. The error handling was kind of complicated, so I was trying to route wires very specifically, and in the process, I dropped that propagation. I'll look into fixing that.

[AristosQueue (NI)]

Posted a new version that preserves the warnings.

[GregSands]

These VIs are not polymorphic.

I'm interested that you didn't write these as XNodes.  Was there any technical reason that would make the implementation harder, or impossible?  Or do I mistakenly see XNodes as the answer to everything "polymorphic"?

[AristosQueue (NI)]

A) The last XNode I worked on was fairly simple and took about four months to get all the little bits and pieces fixed up. This entire API took me about a month of working at home. Five public functions prices out at 20 months of work.

B) The XNode would have to script an entirely new class, not just a diagram, since a new data type has to be created on the fly. That's a technology that is completely unexplored.

C) That newly created class would have to be saved somewhere as an external existing thing, requiring a sophisticated user interface so that every time you dropped one of these nodes you could say what class you were using, or some sort of global type-caching mechanism. It's waaaaaaay beyond just making terminals be polymorphic. XNodes were designed for when you need polymorphic behavior of a node, not when you need to create a type that has never existed before. Although they could in theory script new classes on the fly, no support infastructure exists to help.

D) XNodes have never been released and so the code would all have to be password protected. Priority queues have a number of interesting variants, and with the open code, people can see my diagrams and adjust them for specialized situations.

E) Despite A, B, C, and D, it would not be unreasonable to think that I might be looking at the level of work required to make such wrappings work. But it is a looooooong way from today.

[kegghead]

New version works like a champ. I really like the idea of falling back on the first queue when nothing is pending.

[GregSands]

Right, I hadn't realised the issues in creating a class dynamically.  I was thinking it might not be too different to defining a cluster, such as done by the "Generic Container Map" XNodes that surfaced in the Labs for a while, and now seem to be forgotten.  I imagine XNodes could work with the DVR data type easily enough, but that still wouldn't control the queue access in the way you get with a class.  Roll on the XClass....

[AristosQueue (NI)]

GregS: The comments that we got about the Generic Container Map primarily centered around "but the data type isn't sealed and so the heap can still be mucked with directly." An XClass... hm...

[GerdW]

Hi Aristos,

even when your text says the VIs are in LV2010 they seem to be saved in LV2011 (atleast the lvproj in the ZIP file is in LV2011).

Could you downconvert them to LV2010 and re-attach?

Ok, the VIs are in LV2010, but the project file isn't...

[AristosQueue (NI)]

GerdW: Thanks. I deleted the project from the .zip. It really isn't necessary since the class opens as its own window.

[doradorachan]

Any chance this will be implement into LabVIEW soon?

[AristosQueue (NI)]

doradorachan: It is implemented in LabVIEW already. The code is available above for whatever application you choose. If you are asking whether or not I will be shipping the above code as part of the LabVIEW installer, the answer is no.