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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
use super::Config;
use super::t_iterator::TInteractionIter;
use std::cmp::{Ordering, min};
use std::collections::HashSet;
use std::fmt::{Display, Formatter};
use std::iter;
use streaming_iterator::StreamingIterator;
/// Represents a (partial) sample of configs.
/// The sample differentiates between complete and partial configs.
/// A config is complete (in the context of this sample) if it contains all variables this sample
/// defines. Otherwise the config is partial.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Sample {
/// Configs that contain all variables of this sample
pub complete_configs: Vec<Config>,
/// Configs that do not contain all variables of this sample
pub partial_configs: Vec<Config>,
/// The variables that Configs of this sample may contain
pub vars: HashSet<u32>,
/// The literals that actually occur in this sample, this is not a HashSet because we want
/// a stable iteration order.
pub literals: Vec<i32>,
}
impl PartialOrd<Self> for Sample {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Sample {
fn cmp(&self, other: &Self) -> Ordering {
self.len().cmp(&other.len())
}
}
impl Extend<Config> for Sample {
fn extend<T: IntoIterator<Item = Config>>(&mut self, iter: T) {
for config in iter {
self.add(config);
}
}
}
impl Display for Sample {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
let last_index = self.len() - 1;
self.iter().enumerate().try_for_each(|(index, config)| {
config.fmt(f)?;
if index == last_index {
return Ok(());
}
writeln!(f)
})
}
}
impl Sample {
/// Create an empty sample that may contain the given variables
pub fn new(vars: HashSet<u32>) -> Self {
Self {
complete_configs: vec![],
partial_configs: vec![],
vars,
literals: vec![],
}
}
/// Create a new sample that will contain the given configs
///
/// # Examples
/// ```
/// use ddnnife::ddnnf::anomalies::t_wise_sampling::{Config, Sample};
///
/// let conf_a = Config::from(&[1,2], 3);
/// let conf_b = Config::from(&[1,2,3], 3);
/// let sample = Sample::new_from_configs(vec![conf_a, conf_b]);
///
/// assert_eq!(2, sample.len());
/// assert_eq!(1, sample.complete_configs.len());
/// assert_eq!(1, sample.partial_configs.len());
/// assert_eq!(Some(&Config::from(&[1,2,3], 3)), sample.complete_configs.get(0));
/// assert_eq!(Some(&Config::from(&[1,2], 3)), sample.partial_configs.get(0));
/// ```
pub fn new_from_configs(configs: Vec<Config>) -> Self {
let mut literals: Vec<i32> = configs
.iter()
.flat_map(|c| c.get_decided_literals())
.collect();
literals.sort_unstable();
literals.dedup();
let vars: HashSet<u32> = literals.iter().map(|x| x.unsigned_abs()).collect();
let mut sample = Self {
complete_configs: vec![],
partial_configs: vec![],
vars,
literals,
};
sample.extend(configs);
sample
}
pub fn new_from_samples(samples: &[&Self]) -> Self {
let vars: HashSet<u32> = samples
.iter()
.flat_map(|sample| sample.vars.iter())
.cloned()
.collect();
let literals: HashSet<i32> = samples
.iter()
.flat_map(|sample| sample.get_literals().iter().copied())
.collect();
let mut sample = Self::new(vars);
sample.literals = literals.into_iter().collect();
sample.literals.sort_unstable();
sample
}
/// Create a sample that only contains a single configuration with a single literal
pub fn from_literal(literal: i32, number_of_variables: usize) -> Self {
let mut sample = Self::new(HashSet::from([literal.unsigned_abs()]));
sample.literals = vec![literal];
sample.add_complete(Config::from(&[literal], number_of_variables));
sample
}
pub fn get_literals(&self) -> &[i32] {
&self.literals
}
pub fn get_vars(&self) -> &HashSet<u32> {
&self.vars
}
/// Adds a config to this sample. Only use this method if you know that the config is
/// complete. The added config is treated as a complete config without checking
/// if it actually is complete.
pub fn add_complete(&mut self, config: Config) {
self.complete_configs.push(config)
}
/// Adds a config to this sample. Only use this method if you know that the config is
/// partial. The added config is treated as a partial config without checking
/// if it actually is partial.
pub fn add_partial(&mut self, config: Config) {
self.partial_configs.push(config)
}
/// Adds a config to this sample and automatically determines whether the config is complete
/// or partial.
pub fn add(&mut self, config: Config) {
if self.is_config_complete(&config) {
self.add_complete(config)
} else {
self.add_partial(config)
}
}
/// Determines whether the config is complete (true) or partial (false).
///
/// # Examples
/// ```
/// use std::collections::HashSet;
/// use ddnnife::ddnnf::anomalies::t_wise_sampling::{Config, Sample};
///
/// let sample = Sample::new(HashSet::from([1,2,3]));
///
/// assert!(sample.is_config_complete(&Config::from(&[1,2,3], 3)));
/// assert!(!sample.is_config_complete(&Config::from(&[1,2], 3)));
/// ```
pub fn is_config_complete(&self, config: &Config) -> bool {
let decided_literals = config.n_decided_literals;
debug_assert!(
decided_literals <= self.vars.len(),
"Can not insert config with more vars than the sample defines"
);
decided_literals == self.vars.len()
}
/// Creates an iterator that first iterates over complete_configs and then over partial_configs
pub fn iter(&self) -> impl Iterator<Item = &Config> {
self.complete_configs
.iter()
.chain(self.partial_configs.iter())
}
pub fn iter_with_completeness(&self) -> impl Iterator<Item = (&Config, bool)> {
let partial_iter = self.partial_configs.iter().zip(iter::repeat(false));
self.complete_configs
.iter()
.zip(iter::repeat(true))
.chain(partial_iter)
}
/// Returns the number of configs in this sample
pub fn len(&self) -> usize {
self.complete_configs.len() + self.partial_configs.len()
}
/// Returns true if the sample contains no configs
///
/// # Examples
/// ```
/// use std::collections::HashSet;
/// use ddnnife::ddnnf::anomalies::t_wise_sampling::{Config, Sample};
/// let mut s = Sample::new(HashSet::from([1,2,3]));
///
/// assert!(s.is_empty());
/// s.add_partial(Config::from(&[1,3], 3));
/// assert!(!s.is_empty());
/// ```
pub fn is_empty(&self) -> bool {
self.complete_configs.is_empty() && self.partial_configs.is_empty()
}
/// Checks if this sample covers the given interaction
pub fn covers(&self, interaction: &[i32]) -> bool {
debug_assert!(!interaction.contains(&0));
self.iter().any(|conf| conf.covers(interaction))
}
pub fn is_t_wise_covered(&self, config: &Config, t: usize) -> bool {
let literals: Vec<i32> = config.get_decided_literals().collect();
debug_assert!(!literals.contains(&0));
TInteractionIter::new(&literals, min(t, literals.len()))
.all(|interaction| self.covers(interaction))
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_sample_covering() {
let sample = Sample {
complete_configs: vec![Config::from(&[1, 2, 3, -4, -5], 5)],
partial_configs: vec![],
vars: HashSet::from([1, 2, 3, 4, 5]),
literals: vec![1, 2, 3, -4, -5],
};
let covered_interaction = vec![1, 2, -4];
assert!(sample.covers(&covered_interaction));
let uncovered_interaction = vec![1, 2, 4];
assert!(!sample.covers(&uncovered_interaction));
}
}