dtrees_rs/caching/
mod.rs

1//! The cache of subproblems used by DL8.5.
2//!
3//! [`Trie`] identifies a subproblem by the sorted itemset of its path.
4//! [`CoverMap`] identifies it by its depth and instances.
5
6use crate::caching::entry::CacheEntryUpdater;
7use crate::cover::Cover;
8
9mod cover_map;
10mod entry;
11mod helpers;
12mod trie;
13pub use cover_map::CoverMap;
14pub use entry::{CacheEntry, EXACT};
15pub use helpers::{CacheKey, Index, SearchPath};
16pub use trie::Trie;
17
18/// A cache of subproblems. Lookups take the sorted itemset of the path and
19/// `cover`, positioned on the instances of that path.
20pub trait Caching {
21    /// Clears the cache and creates the root entry.
22    fn init(&mut self) -> Index;
23
24    /// Index of the root entry.
25    fn root_index(&mut self) -> Index;
26
27    /// The root entry.
28    fn root(&self) -> Option<&CacheEntry>;
29
30    /// Finds the entry of the subproblem, creating it if needed. The index is
31    /// `New` for an entry that has not been evaluated yet.
32    fn insert(&mut self, path: &[usize], cover: &Cover) -> Index;
33
34    /// The entry of the subproblem, if cached.
35    fn find(&self, path: &[usize], cover: &Cover) -> Option<&CacheEntry>;
36
37    /// Whether lookups use `cover`.
38    fn keyed_by_cover(&self) -> bool;
39
40    /// The entry for `key`.
41    fn node(&self, key: &CacheKey) -> Option<&CacheEntry>;
42
43    /// Whether the cache has an entry for `key`.
44    fn contains(&self, key: &CacheKey) -> bool;
45
46    /// An updater for the root entry.
47    fn update_root(&mut self) -> Option<CacheEntryUpdater<'_>>;
48
49    /// An updater for the entry of `key`.
50    fn update_node(&mut self, key: &CacheKey) -> Option<CacheEntryUpdater<'_>>;
51
52    /// Number of entries.
53    fn size(&self) -> usize;
54
55    /// Whether the cache has no entry.
56    fn is_empty(&self) -> bool;
57}
dtrees_rs/caching/mod.rs

dtrees_rs/caching/
mod.rs
