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

//! This crate implements an easy way to cache values for
//! a function. If you have a slow running function, this
//! can be used to speed up successive runs dramatically.
//! It is also quite useful for memoization of recursive
//! functions, to prevent calculating the same function
//! twice in different calls.
//!
//! Of particular note, this caching is done without
//! cloning or copying, allowing functions to return
//! large objects, while the cache only returns a reference
//! to them instead of copying them.
//!
//! # Allowed functions
//! This crate attempts to remain fairly flexible with
//! the functions it accepts. All of the following should
//! be allowed:
//!   * [fn][fn primitive] types.
//!   * [Fn] types that have no references.
//!   * [Fn] + 'static types that take only static references.
//!   * [Fn] + 'a types that take references of lifetime 'a.
//!
//! For obvious reasons, [FnMut] and [FnOnce] are not allowed,
//! as functions need to be rerunnable and pure.
//!
//! # Examples
//! The following example shows a recursive fibonacci
//! implementation, which would be O(2ⁿ) without
//! memoization (caching). With memoization, it becomes
//! O(n), and can easily be calculated.
//!
//! ```rust
//! use fn_cache::{FnCache, HashCache};
//!
//! let mut cache = HashCache::<u8,u128>::new(|cache, x|
//!     match x {
//!         0 => 0,
//!         1 => 1,
//!         _ => *cache.get(x - 1) + *cache.get(x - 2),
//!     }
//! );
//!
//! assert_eq!(
//!     *cache.get(186),
//!     332_825_110_087_067_562_321_196_029_789_634_457_848
//! );
//! ```
//!
//! For even bigger results, the [num] crate might be employed.
//! In order to avoid copying the `BigUint`s while accessing the
//! cache twice, you can to change the result to be stored in an
//! [Rc].
//!
//! ```rust
//! use std::rc::Rc;
//! use fn_cache::{FnCache, HashCache};
//! use num_bigint::BigUint;
//!
//! let mut cache = HashCache::<u64,Rc<BigUint>>::new(|cache, x|
//!     match x {
//!         0 => BigUint::new(vec![0]),
//!         1 => BigUint::new(vec![1]),
//!         _ => cache.get(x - 1).clone().as_ref()
//!             + cache.get(x - 2).clone().as_ref(),
//!     }.into()
//! );
//!
//! assert_eq!(
//!     cache.get(999).clone().as_ref(),
//!     &BigUint::parse_bytes(b"26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626", 10).unwrap()
//! );
//! ```
//!
//! [fn primitive]: https://doc.rust-lang.org/std/primitive.fn.html
//! [Fn]: https://doc.rust-lang.org/std/ops/trait.Fn.html
//! [FnMut]: https://doc.rust-lang.org/std/ops/trait.FnMut.html
//! [FnOnce]: https://doc.rust-lang.org/std/ops/trait.FnOnce.html
//! [HashCache]: struct.HashCache.html
//! [Rc]: https://doc.rust-lang.org/std/rc/struct.Rc.html
//! [num]: https://docs.rs/num/
mod btree_cache;
mod fn_cache;
mod hash_cache;
mod tests;
mod vec_cache;

pub use crate::btree_cache::BTreeCache;
pub use crate::fn_cache::FnCache;
pub use crate::hash_cache::HashCache;
pub use crate::vec_cache::VecCache;