Re: Inversion list prototype

If I've understood your data structure correctly, I've written similar code to this in the past (that code isn't mine to release I'm afraid).

The initial code was brittle as hell, in that it was hard to fix a bug without introducing others. I'd *really* recommend a good set of unit tests for this data type.

There are a lot of different cases to consider, with edge cases where the ends of the unions are equal, overlap in different ways, are subsets, proper subsets etc.

However, I've also written some related code (not identical, this is for a half open interval, so the top endpoint isn't included) as part of exmap. If you're interested, it's Range.cpp/Range.hpp in there, with the tests in t_range.cpp.

In fact now I come to think of it, there's a perl version in there too, in the perl-deprecated directory, "Range.pm and test-range.pl".

If it's of any use, lift anything you like from that tarball. That project is GPL'd. (If you'd like it under Artistic License let me know, I'm the author and can re-license if required).

(Edit - can you steal the unit tests from Algorithm::InversionList? It's often quite easy to translate unit tests from one language to another)

Comment on Re: Inversion list prototype

Replies are listed 'Best First'.
Re^2: Inversion list prototype by demerphq (Chancellor) on Feb 16, 2007 at 17:43 UTC
There are a lot of different cases to consider, with edge cases where the ends of the unions are equal, overlap in different ways, are subsets, proper subsets etc. Yes indeed. I think i covered most of them in the embedded tests in the script, but perhaps not. can you steal the unit tests from Algorithm::InversionList? There actually arent that many, and they arent really relevent, since it seems his version does bitmap compression, whereas mine is working with codepoints. (Not that they arent at certain levels equivelent, but....) Also he hasnt implemented any set operations, just compression/lookup. Ill check out the exmap. And yeah, ive done code /very/ similar to this for $work, but wasnt looking at it as a set relation, rather as date ranges. --- $world=~s/war/peace/g	[reply]
Re^3: Inversion list prototype by jbert (Priest) on Feb 16, 2007 at 18:08 UTC
I think there are more cases for union. The two ranges can be disjoint, they can have upper of one == lower of the other, partially overlap, partially overlap with an end-point in common, be equal, be a strict subset and unless you canonicalise the order somehow you also have all of these the other way round (so double the number of cases, plus some I missed probably). I can think of at least ten cases anyway. (Edit: after re-reading the tests, I think most cases are covered, so sorry for originally saying "a lot more cases", that was my error in reading the tests)	[reply]
Re^4: Inversion list prototype by demerphq (Chancellor) on Feb 16, 2007 at 18:19 UTC
You motivated me to add some more tests just now. I havent named them, but I think i have most covered. A second set of eyes is always appreciated in these things, as I think you know. :-) --- $world=~s/war/peace/g	[reply]