[REBOL] Re: bitset help
From: brett:codeconscious at: 28-Sep-2002 0:24
Hi Romano,
> I do not understand how can be used all this new stuff from the new betas.
Can
> someone make an useful example to me? I knows only how to use bitset in
parse
> rule for char, but this seems something different.
A number inserted into a bitset is turns on a bit in the position indicated
by that number. Starting with zero. So if you have a set of things and to
each thing you assign an integer, you could encode the presence of each
thing in a bitset
people: [{Romano} {Anton} {Allen} {Gabriele} {Petr}]
0 will represent Romano
1 will represent Anton
etc.
Now I can use a bitset to represent set membership. My first set will be
people that have Italian email addresses:
italian-email-address: make bitset! 8
insert italian-email-address 0
insert italian-email-address 3
I can query the set - does Petr have an Italian email address?
>> find italian-email-address 4
== none
No is the answer.
I can create another set this time of people that have a name in which the
first letter falls into the A-K range.
a-k-names: make bitset! 8
repeat n [1 2 3] [insert a-k-names n]
Now if I can calculate the set of people that belong to both sets.
resulting-set: intersect italian-email-address a-k-names
But there does not seem to a function to enumerate a bitset - so I do it
myself and find that Gabriele is a member of both sets:
>> repeat i subtract length? resulting-set 1 [if find resulting-set i
[print i]]
3
== none
Bitset lengths are always a multiple of 8. If you have 18 possible values
you will need a bitset of length 24
make bitset! 24
length? returns the capacity of the bitset
>> length? make bitset! 24
== 24
empty? will show you if any bits are set:
>> empty? make bitset! 2000
== true
Clear resets all the bits:
>> clear probe insert make bitset! 8 5
make bitset! #{20}
== make bitset! #{00}
On my machine and with this version a bitset seems to have a maximum size of
2040.
Here's a little function to represent the bits of a bitset:
stringbits: func [bitset [bitset!]][
enbase/base head reverse to-string load find/tail/last form bitset
{ } 2
]
This nicely shows how each number is mapped to a bit position:
>> stringbits insert make bitset! 8 0
== "00000001"
>> stringbits insert make bitset! 8 1
== "00000010"
>> stringbits insert make bitset! 8 2
== "00000100"
>> stringbits insert make bitset! 8 3
== "00001000"
>> stringbits insert insert make bitset! 8 0 3
== "00001001"
Don't know if that was what you wanted.
I found this article when looking at what bitsets can be used for. Quite
interesting I thought:
http://www.flipcode.com/tutorials/tut_bloomfilter.shtml
Regards,
Brett.
