Implementation of succinct bit vectors for lecture ‘advanced datastructures’ at KIT. Find code documentation here.
General usage is
confertus [bv|bp] input_file output_file (if you were to
install it via
cargo install --path .).
bpare two different algorithms/datastructures used/tested, where
bvis short for bitvector, and
bpfor balanced parantheses.
input_fileis a file containing a number of line-by-line commands.
bv, the first line specifies a number
nof elements to push, and the following
0) the bit to insert.
output_filemay or may not exist beforehand, but will be overwritten if it does.
Available commands, depending on selected algorithm:
insert i [0|1]insert a 0 or 1 at the i-th position of the bit vector
delete idelete the i-th bit
flip iflip the i-th bit
rank [0|1] iwrite rank0 or rank1 up to position i to the output file
select [0|1] iwrite select0 or select1 for the i-th occurrence to the output file
deletenode vdelete node v
insertchild v i kTODO: check lecture 05
child v iwrite i-th child of v to output file
subtre size vwrite subtree size of v (including v) to output file
parent vwrite parent of v to output file
rustup via your distributions package manager, or, according to the
official rust website via:
$ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh $ # Ensure that ~/.local/bin is in your PATH. $ # now we need to set the default toolchain $ rustup default stable $ # Or, in case of a previous rust install, update with: $ rustup update $ # Build and open documentation locally $ cargo doc --open $ # Build and run (debug, provides additional information on execution) $ cargo run [bp|bv] input_file output_file $ # Run tests $ cargo test $ # Build and run (optimized) $ RUSTFLAGS="-C target-cpu=native" cargo run --release [bp|bv] input_file output_file
either: Provides the
Either-datatype. Saves about 10min of implementing it manually.
These are dependencies required to execute tests, not for running the binary itself.
pretty_assertions: improved visualization of differences in failed assertions, useful for debugging
quickcheck: rust-reimplementation of popular eponymous haskell-based, strongly heuristic property-based fuzzing testing library
quickcheck_macros: additional macros for
test-case: macros for generating parametricized tests (unused?)
rand: access to a random number generator for tests. It has been suggested for integration in
std, but that hasn’t happened yet.
I recommend running
cargo watch on a terminal nearby during active
development. It runs
cargo check on filechange.
This project is an inefficient, incomplete and unsound implementation of a
dynamic bit vector as part of a university lecture requirement.
Again, it is not complete and contains numerous bugs. I recommend using
established implementations such as