use std::collections::HashMap;
pub struct GraphStack<T> {
items: Vec<T>,
ancestors: HashMap<usize, Vec<usize>>,
}
impl<T> GraphStack<T> {
pub fn new() -> Self {
GraphStack {
items: Vec::new(),
ancestors: HashMap::new(),
}
}
pub fn push(&mut self, value: T, ancestors: &[usize]) -> usize {
if ancestors.iter().any(|a| *a >= self.items.len()) {
panic!(
"Invalid ancestors. GS size={}, ancestors={:#?}",
self.items.len(),
ancestors
);
}
self.items.push(value);
let item_id = self.items.len() - 1;
self.ancestors
.insert(item_id, ancestors.iter().cloned().collect());
item_id
}
pub fn add_ancestors(&mut self, id: usize, ancestors: &[usize]) {
if !self.ancestors.contains_key(&id) {
panic!("Invalid ancestor id={}", id);
}
self.ancestors.entry(id).or_default().extend(ancestors);
}
pub fn stacks(&self, start_item: usize) -> Stacks<T> {
Stacks::new(&self, start_item)
}
}
#[derive(Debug)]
struct Cursor {
item: usize,
ancestor: usize,
}
pub struct Stacks<'a, T> {
cursors: Vec<Cursor>,
unstack: Vec<&'a T>,
gs: &'a GraphStack<T>,
}
impl<'a, T> Stacks<'a, T> {
fn new(gs: &'a GraphStack<T>, start_item: usize) -> Self {
Stacks {
cursors: vec![Cursor {
item: start_item,
ancestor: 0,
}],
unstack: vec![&gs.items[start_item]],
gs,
}
}
}
impl<'a, T> Iterator for Stacks<'a, T> {
type Item = Vec<&'a T>;
fn next(&mut self) -> Option<Self::Item> {
if self.cursors.is_empty() {
return None;
}
while let Some(cursor) = self.cursors.last() {
let ref item_ancestors = self.gs.ancestors[&cursor.item];
if item_ancestors.is_empty() {
break;
}
let prev_item_id = item_ancestors[cursor.ancestor];
self.unstack.push(&self.gs.items[prev_item_id]);
self.cursors.push(Cursor {
item: prev_item_id,
ancestor: 0,
});
}
let stack_snapshot = self.unstack.clone();
while let Some(cursor) = self.cursors.last_mut() {
let num_item_ancestors = self.gs.ancestors[&cursor.item].len();
if cursor.ancestor + 1 < num_item_ancestors {
cursor.ancestor += 1;
break;
}
self.cursors.pop();
}
self.unstack.truncate(self.cursors.len());
Some(stack_snapshot)
}
}
#[cfg(test)]
mod tests {
use super::GraphStack;
use std::collections::HashMap;
#[test]
fn check_iterator() {
let mut gs = GraphStack::new();
let idmap: HashMap<_, _> = ["a", "b", "c", "d", "e", "f", "g", "h"]
.iter()
.cloned()
.map(|value| (value, gs.push(value, &[])))
.collect();
gs.add_ancestors(idmap["b"], &[idmap["a"]]);
gs.add_ancestors(idmap["c"], &[idmap["b"]]);
gs.add_ancestors(idmap["d"], &[idmap["b"]]);
gs.add_ancestors(idmap["e"], &[idmap["c"], idmap["d"]]);
gs.add_ancestors(idmap["f"], &[idmap["e"]]);
gs.add_ancestors(idmap["g"], &[idmap["d"], idmap["f"]]);
gs.add_ancestors(idmap["h"], &[idmap["g"]]);
let mut it = gs.stacks(idmap["h"]);
assert_eq!(it.next().unwrap(), vec![&"h", &"g", &"d", &"b", &"a"]);
assert_eq!(
it.next().unwrap(),
vec![&"h", &"g", &"f", &"e", &"c", &"b", &"a"]
);
assert_eq!(
it.next().unwrap(),
vec![&"h", &"g", &"f", &"e", &"d", &"b", &"a"]
);
assert!(it.next().is_none());
}
#[test]
fn disjoint_stacks() {
let mut gs = GraphStack::new();
let idmap: HashMap<_, _> = ["a", "b", "c", "d", "e"]
.iter()
.cloned()
.map(|value| (value, gs.push(value, &[])))
.collect();
gs.add_ancestors(idmap["b"], &[idmap["a"]]);
gs.add_ancestors(idmap["c"], &[idmap["b"]]);
gs.add_ancestors(idmap["e"], &[idmap["d"]]);
let mut it = gs.stacks(idmap["e"]);
assert_eq!(it.next().unwrap(), vec![&"e", &"d"]);
assert!(it.next().is_none());
let mut it = gs.stacks(idmap["c"]);
assert_eq!(it.next().unwrap(), vec![&"c", &"b", &"a"]);
assert!(it.next().is_none());
}
#[test]
fn x_stack() {
let mut gs = GraphStack::new();
let idmap: HashMap<_, _> = ["a", "b", "c", "d", "e"]
.iter()
.cloned()
.map(|value| (value, gs.push(value, &[])))
.collect();
gs.add_ancestors(idmap["b"], &[idmap["a"], idmap["d"]]);
gs.add_ancestors(idmap["c"], &[idmap["b"]]);
gs.add_ancestors(idmap["e"], &[idmap["b"]]);
let mut it = gs.stacks(idmap["e"]);
assert_eq!(it.next().unwrap(), vec![&"e", &"b", &"a"]);
assert_eq!(it.next().unwrap(), vec![&"e", &"b", &"d"]);
assert!(it.next().is_none());
let mut it = gs.stacks(idmap["c"]);
assert_eq!(it.next().unwrap(), vec![&"c", &"b", &"a"]);
assert_eq!(it.next().unwrap(), vec![&"c", &"b", &"d"]);
assert!(it.next().is_none());
let mut it = gs.stacks(idmap["b"]);
assert_eq!(it.next().unwrap(), vec![&"b", &"a"]);
assert_eq!(it.next().unwrap(), vec![&"b", &"d"]);
assert!(it.next().is_none());
}
}