Integer Sets in ActionScript

It's been awhile since I talked about data types.... thus, I thought I'd demonstrate the IntegerSet data type by providing an ActionScript 2.0 implementation.

An IntegerSet is simply a set of integers, with a relatively simple API. You can insert an element, remove an element, determine if an element is in the set, get the min element, get the max element, clear all elements from the set, union a set with another set, intersect another set with another set, get the compliment of the set, and finally output the set as a string. Some example usage:

// 01/28/04 - moved to weblog package
import com.darronschall.weblog.IntegerSet;

var set1:IntegerSet = new IntegerSet();
set1.insert(7);
set1.insert(11);
set1.del(7);
trace(set1.member(11)); // true
trace(set1.member(7)); // false

// add a large integer
set1.insert(87162386612);
trace(set1.member(87162386612)); // true
set1.del(87162386612);
trace(set1.member(87162386612)); // false

set1.compliment();
trace(set1.member(11)); // false
trace(set1.member(7)); // true

trace(set1.max()); // 10;
trace(set1.min()); // 0;

// toString is overrided, so this produces useful data
trace(set1); 

set1.del(1);
var set2:IntegerSet = new IntegerSet();
set2.insert(1);
set1.union(set2);
trace(set1.member(1)); // true

var set3:IntegerSet = new IntegerSet();
trace(set3.min() == IntegerSet.EMPTYSET); // true
set3.insert(6);
set1.intersection(set3);
trace(set1); // 6 is the only element

set1.clear();
trace(set1.min() == IntegerSet.EMPTYSET); // true
trace(set1.max() == IntegerSet.EMPTYSET); // true

If you run into any errors with this class, please let me know. I probably didn't test this as thoroughly as I should. At some point I'll be looking at using as2unit to do extensive testing. I currently know of only a minor "technical" issue where set.member(IntegerSet.EMPTYSET) will always fail, even though, "technically" the emptyset is always a member of any set by definition... I don't think it's quite that big of a deal since the statement is always true and you wouldn't need to calculate it. ;-).

The implemention for this is pretty slick. It uses an array of integers (treated more or less as an array of bits), and assigns a single bit for each element in the set. If the bit is 1 then the integer represented by the bit's location is in the set. Otherwise, the bit is 0 and the integer represented by the location is not in the set. Because everything is done with bitwise operators, the majority of the methods are lightning fast, even when dealing with very large integers. I was impressed overall by the performance.

Behind the scenes, I'm taking advantage of the fact that the Flash player will automatically resize an Array for you.. Thus, there doesn't really seem to be a limit of the max element that you can store in a set. However, if you use really large integers, some of the methods will take a long time because they're looping through all of the bits. The methods min, max, union, intersection, compliment and toString are the ones affected. Beware if you plan on using large integers with those methods.

Anyway, enough talk... go download the code. It should be pretty well commented. Let me know if you need clarification of anything - I'll be happy to provide explanations.

Next time I'll show you an example of how to use this class in an application to easily solve a problem. Stay tuned!