dtrees_rs/cover/
mod.rs

1//! The instances reaching the current node of the search.
2
3use crate::bitsets::Bitset;
4use crate::cover::reversible_cover::{ShallowBitset, SparseBitset};
5use crate::globals::{attribute, item_type};
6
7pub mod reversible_cover;
8pub mod similarities;
9
10/// A binary dataset and the set of instances reaching the current node.
11///
12/// Features and classes are stored as bitsets over the instances. Branching
13/// on an item intersects the current set with a feature's bitset (or its
14/// complement), and backtracking restores the previous set in constant time
15/// thanks to a reversible sparse bitset.
16///
17/// An item encodes a feature and a branch: `2 * feature` is the branch where
18/// the feature is 0 (left) and `2 * feature + 1` the branch where it is 1
19/// (right). See [`crate::globals`].
20pub struct Cover {
21    /// Number of binary features.
22    pub num_attributes: usize,
23    /// Number of classes.
24    pub num_labels: usize,
25    /// Number of instances in the dataset.
26    pub num_samples: usize,
27    attributes: Vec<Bitset>,
28    labels: Vec<Bitset>,
29    cover: SparseBitset,
30    branch: Vec<usize>,
31}
32
33impl Cover {
34    /// A cover over all instances, from one bitset per feature (instances
35    /// where it is 1) and one per class.
36    pub fn new(attributes: Vec<Bitset>, labels: Vec<Bitset>, num_samples: usize) -> Self {
37        Self {
38            num_attributes: attributes.len(),
39            num_labels: labels.len(),
40            num_samples,
41            attributes,
42            labels,
43            cover: SparseBitset::new(num_samples),
44            branch: vec![],
45        }
46    }
47
48    /// Number of instances in the current node.
49    pub fn count(&self) -> usize {
50        self.cover.count()
51    }
52
53    /// Number of instances of each class in the current node.
54    pub fn labels_count(&self) -> Vec<usize> {
55        self.cover.count_intersect_with_many(&self.labels)
56    }
57
58    /// [`Self::labels_count`] writing into `buffer`.
59    pub fn labels_count_with_buffer(&self, buffer: &mut Vec<usize>) {
60        buffer.clear();
61        buffer.extend_from_slice(&self.cover.count_intersect_with_many(&self.labels));
62    }
63
64    /// Moves to the child reached by `item` and returns its number of
65    /// instances.
66    pub fn branch_on(&mut self, item: usize) -> usize {
67        self.branch.push(item);
68        let attribute = attribute(item);
69        let invert = item_type(item) == 0;
70        self.cover
71            .intersect_with(&self.attributes[attribute], invert)
72    }
73
74    /// Number of instances the child reached by `item` would have.
75    pub fn count_if_branch_on(&self, item: usize) -> usize {
76        let attribute = attribute(item);
77        let invert = item_type(item) == 0;
78        self.cover
79            .count_intersect_with(&self.attributes[attribute], invert)
80    }
81
82    /// Returns to the parent of the current node.
83    ///
84    /// # Panics
85    /// At the root.
86    pub fn backtrack(&mut self) {
87        assert_ne!(self.branch.len(), 0, "No backtrack when at root");
88        self.branch.pop();
89        self.cover.restore();
90    }
91
92    /// Ids of the instances in the current node.
93    #[inline]
94    pub fn to_vec(&self) -> Vec<usize> {
95        self.cover.to_vec()
96    }
97
98    /// A plain copy of the current set of instances.
99    pub fn shallow_cover(&self) -> ShallowBitset {
100        let cover = &self.cover;
101        cover.into()
102    }
103
104    /// The reversible set of instances.
105    pub fn sparse(&self) -> &SparseBitset {
106        &self.cover
107    }
108
109    /// Items branched on from the root to the current node.
110    pub fn path(&self) -> &[usize] {
111        &self.branch
112    }
113}
dtrees_rs/cover/mod.rs

dtrees_rs/cover/
mod.rs
