1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//! # Functional random-access lists
//!
//! A functional random access list is an efficient data structure with _lookup_ and _update_
//! operations in O(log n), and _cons_ and _uncons_ operations in O(1) while preserving the
//! original list. It was introduced in Chris Okasaki's 1995 _ACM FPCA_ paper [Purely Functional
//! Random-Access Lists].
//!
//! We provide [`Arc`]-based and [`Rc`]-based implementations in [`Fral`] and [`rc::Fral`],
//! depending on your use-case. Because [`Arc`] is the most versatile, it is the "primary"
//! implementation for this crate. However, if you don't need thread-safety, [`rc::Fral`] has
//! less overhead and should be used instead — it is a drop-in replacement for [`Fral`].
//!
//! ### Comparison with `im`
//!
//! The following are benchmark results against [`Fral`], [`im::Vector`], [`im::CatList`], and
//! [`im::ConsList`] (`im` version `10.0.0`) with the `get`, `cons`, and `uncons` operations (which
//! are `push_front` and `pop_front` for `im::Vector`). Results are sorted by efficiency:
//!
//! ```plain
//! test get_im_vector ... bench: 25,968 ns/iter (+/- 113)
//! test get_fral ... bench: 37,356 ns/iter (+/- 124)
//! test get_im_catlist ... bench: 15,397,279 ns/iter (+/- 375,877)
//! test get_im_conslist ... bench: 36,834,300 ns/iter (+/- 1,073,303)
//!
//! test cons_im_conslist ... bench: 170,603 ns/iter (+/- 461)
//! test cons_fral ... bench: 294,475 ns/iter (+/- 195)
//! test cons_im_catlist ... bench: 641,423 ns/iter (+/- 2,625)
//! test cons_im_vector ... bench: 949,886 ns/iter (+/- 6,663)
//!
//! test uncons_im_conslist ... bench: 17 ns/iter (+/- 0)
//! test uncons_fral ... bench: 52 ns/iter (+/- 0)
//! test uncons_im_catlist ... bench: 149 ns/iter (+/- 0)
//! test uncons_im_vector ... bench: 454 ns/iter (+/- 2)
//! ```
//!
//! # Examples
//!
//! ```
//! # use std::sync::Arc;
//! use fral::Fral;
//!
//! // cons is O(1)
//! let mut f = Fral::new();
//! for item in vec![1, 2, 3, 4, 5] {
//! f = f.cons(item);
//! }
//!
//! // lookup is O(log n)
//! if let Some(x) = f.get(4) {
//! assert_eq!(*x, 1);
//! } else { unreachable!() }
//! // lookup out of bounds is O(1)
//! assert_eq!(f.get(5), None);
//!
//! // uncons is O(1)
//! if let Some((head, tail)) = f.uncons() {
//! assert_eq!(*head, 5);
//! assert_eq!(tail.len(), 4);
//! } else { unreachable!() }
//!
//! // in this scope, we want f to have an extra item in front.
//! // we can do this in O(1), without cloning any items.
//! {
//! let f = f.cons(42);
//!
//! assert_eq!(*f.get(0).unwrap(), 42);
//! assert_eq!(*f.get(5).unwrap(), 1);
//! }
//!
//! // our original Fral is still here
//! assert_eq!(
//! f.iter().take(2).collect::<Vec<_>>(),
//! vec![Arc::new(5), Arc::new(4)]
//! );
//! ```
//!
//! [Purely Functional Random-Access Lists]: https://www.westpoint.edu/eecs/SiteAssets/SitePages/Faculty%20Publication%20Documents/Okasaki/fpca95.pdf
//! [`Arc`]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html
//! [`Rc`]: https://doc.rust-lang.org/stable/std/rc/struct.Rc.html
//! [`Fral`]: struct.Fral.html
//! [`rc::Fral`]: rc/struct.Fral.html
//! [`im::Vector`]: https://docs.rs/im/~10.0/im/vector/struct.Vector.html
//! [`im::CatList`]: https://docs.rs/im/~10.0/im/catlist/struct.CatList.html
//! [`im::ConsList`]: https://docs.rs/im/~10.0/im/conslist/struct.ConsList.html
pub use *;