Complementing virtual bitsets

Carl Sassenrath, CTO
REBOL Technologies
12-Feb-2008 22:27 GMT

Article #0004
Main page || Index || Prior Article [0003] || Next Article [0005] || 7 Comments || Send feedback

In R3, bitsets are just as long as they need to be and no longer.

For example:

>> b: make bitset! " "
== make bitset! #{0000000080}

If you test a value outside the bitset range, it returns as not found. For example:

>> find b #"a"
== none

This is quite useful because we might use Unicode values that are far beyond the range of the set. This line works fine:

>> find b #"^(03d6)"  ; Greek symbol for PI
== none

But, there is a problem: We use complement to invert a bitset, and this is quite useful to do. However, if you do that now, you get:

>> c: complement make bitset! " "
== make bitset! #{FFFFFFFF7F}


>> find c #"a"
== none

should return true but does not.

Issue to resolve:

How do we want to invert bitsets?

It seems to me, if we want the bitset itself to represent its inverted state, then it is necessary to internally flag the bitset to indicate that it is complemented.

The case above would then be:

>> find c #"a"
== true

The problem with this solution is that a molded bitset can no longer be represented in source code as a set of bits. We need to extend it to include a complement indication. For example:

>> mold/all c
== #[bitset! not #{0000000080}]

Of course, this is not a problem for evaluated creation of bitsets, which can simply remain:

>> c: complement make bitset! " "
Secondary issue:

But, there is a secondary issue. What if you perform a data set function such as intersect on the inverted dataset?

For example, what if you write:

>> a: intersect a complement b

Ignoring the fact that this is really a difference operation, what we will need to do internally is perform the logical intersect operation, and return the most appropriate result, which could itself be a complemented dataset.

Although this makes the internal implementation slightly more complicated, it should not affect performance because it can all be done with a single pass using the proper sequence of bitwise operators.

Just a note...

Note that the bitset complement problem can also be addressed by providing additional refinements to find and a new word in parse.

For example, this would be possible:

>> find/not b #"a"
== true

and also:

>> parse data [to not b here: "about"]

Note, however, that these two changes are not a requirement for the above virtual complement to work. They would be additional, so we'll make those a subject for another note here in the future.


Updated 20-Jul-2013 - Edit - Copyright REBOL Technologies -