2009/6/10 Jeffrey Bosboom <jbosboom@uci.edu>:
I almost exclusively use this structure in a way that interval nodes represent sequences of 1 bits, but it can just as easily be used the other way around, where intervals represent sequences of 0 bits. In fact now that I think about it probably doesn't even matter.
Since it will use less space if the bitset is sparse with occasional 0 or 1 bits, this sounds like a good choice for a nontype template parameter. Obviously the user could just invert the sense of the bits themselves (instead of representing presence in a set, it could represent "lack of absence"), but a template parameter would be more user-friendly. A converting constructor could be provided for converting between the two.
I'm not sure it's worth the complexity. It's usually not that hard to invert a condition in user code, since renaming the variable from visited to pending, free to allocated, or similar makes it just about as readable. I remember hearing about an interval template library; Is there any possible useful overlap here? Also, at first glace I thought you were talking about what I'd call a sparse_bitset, where the storage is an optimization of a map<offset, bitset<128> >. (Specifically I'm thinking of the LLVM class described here: http://llvm.org/docs/ProgrammersManual.html#dss_sparsebitvector) Obviously the interval method is more efficient for long runs of ones, but the offset one is much better for short runs. Can you elaborate more on your usage? Should boost maybe provide both? And out of curiosity, did you compare the T-tree to other trees? Perhaps there's also an intrusive::t_tree hiding in here =)