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
use num_traits::One;
use std::collections::{HashSet, VecDeque};
use std::iter::IntoIterator;
use std::ops::Deref;
use crate::anahash::*;
use crate::types::*;
///////////////////////////////////////////////////////////////////////////////////////
/// Returns all AnaValues that are formed
/// when doing single deletion. This
/// is the most basic iterator form
/// from which most others are derived.
///
/// The iterator yields values in order
/// of descending alphabet index.
///
/// So given an anagram value for abcd it will yield
/// anagram values abc, abd, acd, bcd
pub struct DeletionIterator<'a> {
value: &'a AnaValue,
alphabet_size: CharIndexType,
iteration: usize,
}
impl<'a> DeletionIterator<'a> {
pub fn new(value: &'a AnaValue, alphabet_size: CharIndexType) -> DeletionIterator {
DeletionIterator {
value: value,
alphabet_size: alphabet_size,
iteration: 0,
}
}
}
#[derive(Clone, Debug)]
pub struct DeletionResult {
pub value: AnaValue,
pub charindex: CharIndexType,
}
impl Deref for DeletionResult {
type Target = AnaValue;
fn deref(&self) -> &Self::Target {
&self.value
}
}
impl<'a> Iterator for DeletionIterator<'a> {
type Item = DeletionResult;
fn next(&mut self) -> Option<Self::Item> {
if self.value == &AnaValue::one() || self.iteration == self.alphabet_size as usize {
None
} else {
let charindex: CharIndexType = self.alphabet_size - (self.iteration as u8) - 1;
self.iteration += 1;
if let Some(result) = self.value.delete(&AnaValue::character(charindex)) {
Some(DeletionResult {
value: result,
charindex: charindex,
})
} else {
self.next() //recurse
}
}
}
}
///////////////////////////////////////////////////////////////////////////////////////
pub enum VisitedMap<'a> {
Internal(HashSet<AnaValue>),
External(&'a mut HashSet<AnaValue>),
}
impl VisitedMap<'_> {
pub fn contains(&self, key: &AnaValue) -> bool {
match self {
VisitedMap::Internal(map) => map.contains(key),
VisitedMap::External(map) => map.contains(key),
}
}
pub fn insert(&mut self, key: AnaValue) -> bool {
match self {
VisitedMap::Internal(map) => map.insert(key),
VisitedMap::External(map) => map.insert(key),
}
}
}
pub struct RecurseDeletionIterator<'a> {
queue: VecDeque<(DeletionResult, u32)>, //second tuple argument is the depth at which the iterator starts
alphabet_size: CharIndexType,
singlebeam: bool, //caps the queue at every expansion
breadthfirst: bool,
mindepth: u32,
maxdepth: Option<u32>, //max depth
///Allow returning empty leaves at the maximum depth of the search (needed if you want to
///inspect the charindex)
empty_leaves: bool,
///Ensure all returned items are unique, no duplicates are yielded
unique: bool,
///Used to keep track of visited values if unique is set
visited: VisitedMap<'a>,
}
impl<'a> RecurseDeletionIterator<'a> {
pub fn new(
value: AnaValue,
alphabet_size: CharIndexType,
singlebeam: bool,
mindepth: Option<u32>,
maxdepth: Option<u32>,
breadthfirst: bool,
unique: bool,
empty_leaves: bool,
external_visited_map: Option<&'a mut HashSet<AnaValue>>,
) -> RecurseDeletionIterator<'a> {
let queue: Vec<(DeletionResult, u32)> = vec![(
DeletionResult {
value: value,
charindex: 0,
},
0,
)];
RecurseDeletionIterator {
queue: VecDeque::from(queue),
alphabet_size: alphabet_size,
singlebeam: singlebeam,
breadthfirst: breadthfirst,
mindepth: mindepth.unwrap_or(1),
maxdepth: maxdepth,
unique: unique,
empty_leaves: empty_leaves,
visited: match external_visited_map {
Some(mapref) => VisitedMap::External(mapref),
None => VisitedMap::Internal(HashSet::new()),
},
}
}
}
impl Iterator for RecurseDeletionIterator<'_> {
type Item = (DeletionResult, u32);
fn next(&mut self) -> Option<Self::Item> {
if self.breadthfirst {
//------------------ breadth first search --------------------
if let Some((node, depth)) = self.queue.pop_front() {
if self.unique && self.visited.contains(&node.value) {
return self.next(); //node was already visited, recurse to next
}
if self.maxdepth.is_none() || depth < self.maxdepth.expect("get maxdepth") {
let iter_children = DeletionIterator::new(&node.value, self.alphabet_size);
if self.unique {
let visited = &self.visited; //borrow outside closure otherwise borrow checker gets confused
self.queue.extend(
iter_children
.filter(|child| !visited.contains(&child.value))
.map(|child| (child, depth + 1)),
);
} else {
self.queue
.extend(iter_children.map(|child| (child, depth + 1)));
}
}
//don't yield the root element (or empty leaves if we don't want them), just recurse in that case
if (depth < self.mindepth) || (!self.empty_leaves && node.value.is_empty()) {
self.next()
} else {
if self.unique {
self.visited.insert(node.value.clone());
}
Some((node, depth))
}
} else {
None
}
} else {
//------------------ depth first search (pre-order) --------------------
if let Some((node, depth)) = self.queue.pop_back() {
//note: pop from back instead of front here
if self.maxdepth.is_none() || depth < self.maxdepth.expect("get maxdepth") {
if self.unique && self.visited.contains(&node.value) {
return self.next(); //node was already visited, recurse to next
}
let mut iter_children = DeletionIterator::new(&node.value, self.alphabet_size);
if self.singlebeam {
// single beam, just dive to the bottom in a single line and stop
if let Some(child) = iter_children.next() {
self.queue.push_back((child, depth + 1));
}
} else {
//reverse the order in which we obtained them
let children = iter_children.collect::<Vec<_>>();
let children = children.into_iter().rev();
if self.unique {
let visited = &self.visited; //borrow outside closure otherwise borrow checker gets confused
self.queue.extend(
children
.filter(|child| !visited.contains(&child.value))
.map(|child| (child, depth + 1)),
);
} else {
self.queue.extend(children.map(|child| (child, depth + 1)));
}
}
}
//don't yield the root element (or empty leaves if we don't want them), just recurse in that case
if (depth < self.mindepth) || (!self.empty_leaves && node.value.is_empty()) {
self.next()
} else {
if self.unique {
self.visited.insert(node.value.clone());
}
Some((node, depth))
}
} else {
None
}
}
}
}