Complemented bitsets

Carl Sassenrath, CTO
REBOL Technologies
19-Oct-2009 20:34 GMT

Article #0278
Main page || Index || Prior Article [0277] || Next Article [0279] || 6 Comments || Send feedback

The A91 release will include complemented bitsets.

Note that I've written new Bitset Documentation that explains them in much greater detail.

This change makes character classes viable again in parse and find. For example, you can write:

no-space: complement charset " "
parse string [.... some no-space ...]

and also:

find string no-space

Such a line will work for all characters because the bitset is now logically complemented (not physically complemented.) That is, a flag indicates that it is a complement. Its actual bits are not modified.

This method solves the problems of virtual charsets (you can check bits that are even outside of the range of the physical bitset) but it creates a few new challenges...

For example, if I type the line above:

>> complement charset " "
== make bitset! [not bits #{0000000080}]

As you can see, the bitset! constructor is now a block. The not indicates the inverted state, and the bits indicates that the binary! is the actual bitmap, not an array of bytes. Also, note that the bitmap itself is not inverted.

Of course, you can also write this directly:

make bitset! [not " "]
make bitset! [not "abc" "123"]

The not applies to the entire bitset.

There are a few other issues to be resolved. For example, if you append to a complemented bitset, you are adding the inverted bit(s). For example:

>> b: complement charset " "
== make bitset! [not bits #{0000000080}]

>> append b "."
== make bitset! [not bits #{000000008002}]

I think we also need some method of determining if a bitset is complemented. The obvious method would be something like:

negative? bitset

although, it is stretching the definition a bit.

And finally, we must consider what happens when we and, or, and xor such bitsets.


Updated 29-Mar-2017 - Edit - Copyright REBOL Technologies -