immutable_map/lib.rs
1//! Immutable binary search tree.
2//!
3//! This crate provides functional programming style binary search trees which returns modified
4//! copy of original map or set with the new data, and preserves the original. Many features and
5//! algorithms are borrowed from `Data.Map` of Haskell's standard library.
6//!
7//! See https://yoichihirai.com/bst.pdf for the balancing algorithm.
8//!
9//! To share the data between the old and the new data structure after modification, most of the
10//! functions require the key and value type to implement `Clone`. If you want to store non-
11//! clonable data into this map, you can wrap it under shared pointer such as `Rc` or `Arc`.
12
13#[cfg(test)]
14#[macro_use]
15extern crate quickcheck;
16#[cfg(test)]
17extern crate rand;
18
19#[cfg(test)]
20use quickcheck::{Arbitrary, Gen};
21
22/// An immutable set based on binary search tree
23pub mod set;
24/// An immutable map based on binary search tree
25pub mod map;
26mod tree;
27
28pub use set::TreeSet;
29pub use map::TreeMap;
30
31/// An endpoint of a range of keys.
32#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
33pub enum Bound<T> {
34 /// An infinite endpoint. Indicates that there is no bound in this direction.
35 Unbounded,
36 /// An inclusive bound.
37 Included(T),
38 /// An exclusive bound.
39 Excluded(T)
40}
41
42#[cfg(test)]
43impl<T: Arbitrary> Arbitrary for Bound<T> {
44 fn arbitrary<G: Gen>(g: &mut G) -> Bound<T> {
45 match g.size() % 3 {
46 0 => Bound::Unbounded,
47 1 => Bound::Included(Arbitrary::arbitrary(g)),
48 2 => Bound::Excluded(Arbitrary::arbitrary(g)),
49 _ => panic!("remainder is greater than 3")
50 }
51 }
52}