[ruby-talk:6496] ANN: BitVector 0.1.5

Hi,

I've been posing dumb question on ruby-talk for so long now that I think
its about time I contribute something; here is a fairly extensive
BitVector extension. I know a lot of you has submitted similar extensions
but IMHO this one is more "complete" so I hope someone finds it
useful. You can find the README below and download it from RAA.

If you try it out then I'd be esepcially interested in any violations to
the "principle of Least Surprise" you might encounter. One main goal with
the extension is that it should be truly Ruby-ish...

Note that its an alpha release so there will likely be bugs. Please read
the README and the TODO to see what is missing or not fully implemented.
Documentation is thin as of now but please take a look at the unit tests
since they give a good picture of how to use the extension.

Regards,

Robert

	=============================================================
	= BitVector - Effecient bit vector class extension for Ruby =
	=          version 0.1.5 (This is an alpha release)         =
	=============================================================

Release date: 2000-11-21
Available
from: http://www.ce.chalmers.se/~feldt/ruby/extensions/bitvector/
Author: Robert Feldt, [e-mail]

What is it?
-----------
A fairly extensive and fast BitVector class for Ruby. Handles sequences of 
up to 2**32-1 bits (about 500 Mb)[FOOTNOTE 1]. Implemented as a wrapper 
around Bit::Vector version 6.0 by Steffen Beyer. Bit::Vector is a C
library 
of fast routines for handling bit vectors. See 
steffen_beyers_bit_vector/README.txt for Steffen's intro to Bit::Vector.

Installation?
-------------
1. unpack tarball (if you haven't already)
2. ruby extconf.rb
3. make
4. ruby tests/unittest_bitvector.rb runs the tests (OPTIONAL)
5. ruby install.rb

Example of use?
---------------
require 'bitvector'
b = BitVector.new(100000).randomize      # 1e5 random bits
a = BitVector.new(100000).randomize      # another 1e5 random bits
c = a^b                                  # exclusive or of 2*1e5 rand bits
File.open("mybits", "w") {|f|            # Dump bit vector to file
  f.write Marshal.dump(c)
}
BitVector.new(8, "10011011").ones        # => [0,1,3,4,7]
puts c.to_i				 # Print *large* number...

Requirements?
-------------
None known, but hey there are no garantuees here (see LICENSE). 
I've successfully compiled and used BitVector with Ruby 1.6.2
(2000-11-16) and 
cygwin 1.1.4 on Windows 2000 Professional Workstation and Windows NT 4.0 
Workstation. If it works for you on other platforms/setups I'd appreciate 
if you drop me a note. However, it should work on most Ruby-enabled 
platforms.

NOTE THAT THIS IS AN ALPHA RELEASE SO THERE WILL LIKELY BE BUGS. I've only
used a small subset of all the methods in my own projects...

Documentation?
--------------
No Ruby-specific documentation yet but Ruby class very similar to the
Perl class Bit:Vector, see 
http://www.engelschall.com/u/sb/download/Bit-Vector/ for more info.

Also take a look in the unit tests which give examples of use, see
file tests/unittest_bitvector.rb.

License?
--------
Same as the underlying Bit::Vector ie. LGPL. See LICENSE.
If this is too strict then please contact me and we can work something 
out with Steffen Beyer.

Special things to note?
-----------------------
Methods
	randomize,
	* (multiply),
	/ (divide),
	to_uint,
	to_i
are *SLOW* and calling them for large bit vectors can take
prohibitively *LONG* time.

Run 'ruby tests/perftest_bitvector.rb' to get some timing data.

Note: randomize is much faster if you use a probability of 0.5, ie. the
default value.

Plans for the future?
---------------------
See TODO. This is an alpha release so there might be (some) changes 
to the interface.

What is bitvector_extra.rb?
---------------------------
Ruby file adding some lesser used methods to BitVector class. Might
migrate
to "main" class in the future or might be moved away. It is installed when
you do "ruby install.rb". See tests/unittests_bitvector_extra.rb for some
examples of use.

Do you have comments or questions?
----------------------------------
I'd appreciate if you drop me a note if you're successfully using 
BitVector. If there are some known users I'll be more motivated to 
packing up additions / new versions and post them to RAA.

Happy coding!

Robert Feldt, [e-mail]

FOOTNOTE 1. The limit is actually the largest number that can be
represented
in an "unsigned long" in C. If you have a 64-bit machine the BitVectors
are
limited to >2e5 TeraByte so that'll probably be enough... ;-)