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}