17 August 2008

Sets for ActionScript

It's been a busy couple of months!

One of the things keeping me busy is, of course, Names on Nodes, the web application I am developing that will automate phylogenetic nomenclature. As part of that project, I have developed a mathematics package that I would eventually like to release as its own package. One class, however, is so useful that I have decided to jump the gun and offer it on its own.

We (ActionScript programmers) all know how useful the Array class is. It can be used to store a sequence of anything, so it can be repurposed as a list, a vector, an edge—all manner of collections.

Well, not all manner of collections. Just ordered collections that allow duplicate elements. What if you want a set: an unordered collection with no duplicates? I find I need sets all the time, but I have to use arrays. And arrays are not optimal for looking up an element's membership, or preventing duplication. As lists they're great, but as sets they suck.

For a while I used a class I'd made called ArraySet that wrapped an array, but this was only an improvement in API, not in performance. Then I took a cue from Java and created: HashSet.


The HashSet class wraps a Dictionary object, which it uses as a hash table. If an element belongs to the set, then that element is a self-referential key in the dictionary. If it doesn't, then there is no such key in the dictionary. And HashSet extends Proxy, so you can use bracket notation for many operations,. You can also use for..in and for each..in loops.

Here's a quick example:


// Create and populate the set.
var s:HashSet = HashSet.fromObject([1, 2, 3]);

trace(s.size); // 3
trace(s[1]); // 1
trace(s[2]); // 2
trace(s[0]); // undefined
trace(s.has(1)) // true

// Trace all elements of the set.
for each (var i:int in s)
{
trace(i);
}
// Trace all elements of the set (different method).
for (var x:* in s)
{
trace(x);
}

trace(s); // {1, 2, 3}
s.add(1);
trace(s); // {1, 2, 3}
s.add(4);
trace(s); // {1, 2, 3, 4}
s.remove(1);
trace(s); // {2, 3, 4}
delete s[2];
trace(s); // {3, 4}
s[3] = undefined;
trace(s); // {4}


...and so on. Full documentation is in the class itself, so you can figure out the details for yourself. I will mention that HashSet also has a number of functions in common with Array (every, filter, forEach, map, some) and others that are unique to sets (get empty, diff, intersect, prSubsetOf, subsetOf, union). It also has a few functions that Array really ought to have (clone, equals, remove).

Download it and try it! The full version is integrated into the mathematics package that I'm still tweaking, but this is too useful to keep to myself any longer. At least, I think so—let me know what you think.

5 comments:

  1. wouldn't using "delete s[2]" break the size count?

    ReplyDelete
  2. No, look at the deleteProperty() function. It decrements size if the set contains the provided name.

    BTW, since writing this I have discovered that the delete operator only works on elements that are numbers or strings. Ditto some of the other bracket notations. I've updated the documentation in the newer version, which I hope to post before too long.

    ReplyDelete
  3. Hey Mike,

    Just a quick note to say thank-you for posting this: very useful indeed. I also found a tiny bug. There's an import for threelbmonkeybrain.relate.Equatable that's not required and causes an error if the class doesn't exists.

    Thanks again :)

    - Aral

    ReplyDelete
  4. Glad it was useful!

    Whoops, that must have slipped by me when I was exporting the standalone version. Although it should work if you remove that line, as you say, you may want to upgrade to the package. More here: My Yuletide Gift: Open Source ActionScript 3.0 Libraries!.

    ReplyDelete
  5. Note that the links above deprecated. The mathematical portion of the project has since been moved to BitBucket.

    ReplyDelete