use std::{hash::Hash, sync::Arc};
use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::cmp::Ordering;
use std::cmp::Ordering::{Greater, Less};
use compare::Compare;
use rustc_hash::FxHashMap;
use crate::*;
use self::Action::{BubbleDown, BubbleUp, DoNothing};
#[derive(Debug, Copy, Clone)]
struct NodeId(usize);
#[derive(Debug, Copy, Clone)]
enum Action {
DoNothing,
BubbleUp(NodeId),
BubbleDown(NodeId),
}
pub struct NoDupFrontier<O>
where
O: SubProblemRanking,
O::State: Eq + Hash + Clone,
{
cmp: CompareSubProblem<O>,
states: FxHashMap<Arc<O::State>, NodeId>,
nodes: Vec<SubProblem<O::State>>,
pos: Vec<usize>,
heap: Vec<NodeId>,
recycle_bin: Vec<NodeId>,
}
impl<O> Frontier for NoDupFrontier<O>
where
O: SubProblemRanking,
O::State: Eq + Hash + Clone,
{
type State = O::State;
fn push(&mut self, mut node: SubProblem<O::State>) {
let state = Arc::clone(&node.state);
let action = match self.states.entry(state) {
Occupied(e) => {
let id = *e.get();
let old_lp = self.nodes[id.0].value;
let old_ub = self.nodes[id.0].ub;
let new_lp = node.value;
let new_ub = node.ub;
node.ub = new_ub.max(old_ub);
let action = if self.cmp.compare(&node, &self.nodes[id.0]) == Greater {
BubbleUp(id)
} else {
DoNothing
};
if new_lp > old_lp {
self.nodes[id.0] = node;
}
if new_ub > old_ub {
self.nodes[id.0].ub = new_ub;
}
action
}
Vacant(e) => {
let id = if self.recycle_bin.is_empty() {
let id = NodeId(self.nodes.len());
self.nodes.push(node);
self.pos.push(0); id
} else {
let id = self.recycle_bin.pop().unwrap();
self.nodes[id.0] = node;
id
};
self.heap.push(id);
self.pos[id.0] = self.heap.len() - 1;
e.insert(id);
BubbleUp(id)
}
};
self.process_action(action);
}
fn pop(&mut self) -> Option<SubProblem<Self::State>> {
if self.is_empty() {
return None;
}
let id = self.heap.swap_remove(0);
let action = if self.heap.is_empty() {
DoNothing
} else {
self.pos[self.heap[0].0] = 0;
BubbleDown(self.heap[0])
};
self.process_action(action);
self.recycle_bin.push(id);
let node = self.nodes[id.0].clone();
self.states.remove(&node.state);
Some(node)
}
fn clear(&mut self) {
self.states.clear();
self.nodes.clear();
self.pos.clear();
self.heap.clear();
self.recycle_bin.clear();
}
fn len(&self) -> usize {
self.heap.len()
}
}
impl<O> NoDupFrontier<O>
where
O: SubProblemRanking,
O::State: Eq + Hash + Clone,
{
pub fn new(ranking: O) -> Self {
Self {
cmp: CompareSubProblem::new(ranking),
states: Default::default(),
nodes: vec![],
pos: vec![],
heap: vec![],
recycle_bin: vec![],
}
}
pub fn is_empty(&self) -> bool {
self.heap.is_empty()
}
fn process_action(&mut self, action: Action) {
match action {
BubbleUp(id) => self.bubble_up(id),
BubbleDown(id) => self.bubble_down(id),
DoNothing => { }
}
}
fn position(&self, n: NodeId) -> usize {
self.pos[n.0]
}
fn compare_at_pos(&self, x: usize, y: usize) -> Ordering {
let node_x = &self.nodes[self.heap[x].0];
let node_y = &self.nodes[self.heap[y].0];
self.cmp.compare(node_x, node_y)
}
fn bubble_up(&mut self, id: NodeId) {
let mut me = self.position(id);
let mut parent = self.parent(me);
while !self.is_root(me) && self.compare_at_pos(me, parent) == Greater {
let p_id = self.heap[parent];
self.pos[p_id.0] = me;
self.pos[id.0] = parent;
self.heap[me] = p_id;
self.heap[parent] = id;
me = parent;
parent = self.parent(me);
}
}
fn bubble_down(&mut self, id: NodeId) {
let mut me = self.position(id);
let mut kid = self.max_child_of(me);
while kid > 0 && self.compare_at_pos(me, kid) == Less {
let k_id = self.heap[kid];
self.pos[k_id.0] = me;
self.pos[id.0] = kid;
self.heap[me] = k_id;
self.heap[kid] = id;
me = kid;
kid = self.max_child_of(me);
}
}
fn parent(&self, pos: usize) -> usize {
if self.is_root(pos) {
pos
} else if self.is_left(pos) {
pos / 2
} else {
pos / 2 - 1
}
}
fn max_child_of(&self, pos: usize) -> usize {
let size = self.len();
let left = self.left_child(pos);
let right = self.right_child(pos);
if left >= size {
return 0;
}
if right >= size {
return left;
}
match self.compare_at_pos(left, right) {
Greater => left,
_ => right,
}
}
fn left_child(&self, pos: usize) -> usize {
pos * 2 + 1
}
fn right_child(&self, pos: usize) -> usize {
pos * 2 + 2
}
fn is_root(&self, pos: usize) -> bool {
pos == 0
}
fn is_left(&self, pos: usize) -> bool {
pos % 2 == 1
}
}
#[cfg(test)]
#[allow(clippy::many_single_char_names)]
mod test_no_dup_frontier {
use crate::*;
use std::{sync::Arc, cmp::Ordering};
#[test]
fn by_default_it_is_empty() {
assert!(empty_frontier().is_empty())
}
#[test]
fn when_the_size_is_zero_then_it_is_empty() {
let frontier = empty_frontier();
assert_eq!(frontier.len(), 0);
assert!(frontier.is_empty());
}
#[test]
fn when_the_size_is_greater_than_zero_it_is_not_empty() {
let frontier = non_empty_frontier();
assert_eq!(frontier.len(), 1);
assert!(!frontier.is_empty());
}
#[test]
fn when_i_push_a_non_existing_node_onto_the_frontier_then_the_length_increases() {
let mut frontier = empty_frontier();
frontier.push(SubProblem {
state: Arc::new(42),
value: 0,
path : vec![],
ub : 0
});
assert_eq!(frontier.len(), 1);
frontier.push(SubProblem{
state: Arc::new(43),
value: 0,
path : vec![],
ub: 0
});
assert_eq!(frontier.len(), 2);
}
#[test]
fn when_i_push_an_existing_node_onto_the_frontier_then_the_length_does_not_increases() {
let mut frontier = empty_frontier();
frontier.push(SubProblem {
state: Arc::new(42),
value: 0,
path : vec![],
ub : 0
});
assert_eq!(frontier.len(), 1);
frontier.push(SubProblem {
state: Arc::new(42),
value: 12,
path : vec![],
ub : 5
});
assert_eq!(frontier.len(), 1);
}
#[test]
fn when_i_pop_a_node_off_the_frontier_then_the_length_decreases() {
let mut frontier = non_empty_frontier();
assert_eq!(frontier.len(), 1);
frontier.pop();
assert_eq!(frontier.len(), 0);
}
#[test]
fn when_i_try_to_pop_a_node_off_an_empty_frontier_i_get_none() {
let mut frontier = empty_frontier();
assert_eq!(frontier.pop(), None);
}
#[test]
fn when_i_pop_a_node_it_is_always_the_one_with_the_largest_ub_then_lp() {
let mut frontier = empty_frontier();
let a = SubProblem {
state: Arc::new(1),
value: 1,
path : vec![],
ub : 1
};
let b = SubProblem {
state: Arc::new(2),
value: 2,
path : vec![],
ub : 2
};
let c = SubProblem {
state: Arc::new(3),
value: 3,
path : vec![],
ub : 3
};
let d = SubProblem {
state: Arc::new(4),
path: vec![],
value: 4,
ub: 4
};
let e = SubProblem{
state: Arc::new(5),
path: vec![],
value: 4,
ub: 5
};
let f = SubProblem{
state: Arc::new(5),
path: vec![],
value: 5,
ub: 5
};
frontier.push(a.clone());
frontier.push(f.clone());
frontier.push(b.clone());
frontier.push(d.clone());
frontier.push(c.clone());
frontier.push(e);
assert_eq!(frontier.pop(), Some(f));
assert_eq!(frontier.pop(), Some(d));
assert_eq!(frontier.pop(), Some(c));
assert_eq!(frontier.pop(), Some(b));
assert_eq!(frontier.pop(), Some(a));
}
#[test]
fn when_i_pop_a_node_off_the_frontier_for_which_multiple_copies_have_been_added_then_i_retrieve_the_one_with_longest_path(){
let pe = vec![
Decision {variable: Variable(0), value: 4},
];
let pf = vec![
Decision {variable: Variable(1), value: 5},
];
let ne = SubProblem{
state: Arc::new(5),
path: pe,
value: 4,
ub: 5
};
let nf = SubProblem{
state: Arc::new(5),
path: pf,
value: 5,
ub: 5
};
let mut frontier = empty_frontier();
frontier.push(ne);
frontier.push(nf.clone());
assert_eq!(frontier.pop(), Some(nf));
}
#[test]
fn when_i_clear_an_empty_frontier_it_remains_empty() {
let mut frontier = empty_frontier();
assert!(frontier.is_empty());
frontier.clear();
assert!(frontier.is_empty());
}
#[test]
fn when_i_clear_a_non_empty_frontier_it_becomes_empty() {
let mut frontier = non_empty_frontier();
assert!(!frontier.is_empty());
frontier.clear();
assert!(frontier.is_empty());
}
#[derive(Debug, Clone, Copy, Default)]
struct UsizeRanking;
impl StateRanking for UsizeRanking {
type State = usize;
fn compare(&self, a: &Self::State, b: &Self::State) -> Ordering {
a.cmp(b)
}
}
fn empty_frontier() -> NoDupFrontier<MaxUB<'static, UsizeRanking>> {
NoDupFrontier::new(MaxUB::new(&UsizeRanking))
}
fn non_empty_frontier() -> NoDupFrontier<MaxUB<'static, UsizeRanking>> {
let mut frontier = empty_frontier();
frontier.push(SubProblem{
state: Arc::new(42),
path: vec![],
value: 0,
ub: 0
});
frontier
}
#[test]
fn popped_in_order() {
let nodes = [
fnode(1, 10, 100),
fnode(2, 10, 101),
fnode(3, 10, 102),
fnode(4, 10, 103),
fnode(5, 10, 104),
];
let mut heap = empty_frontier();
push_all(&mut heap, &nodes);
assert_eq!(5, heap.len());
assert_eq!(false, heap.is_empty());
let actual = pop_all(&mut heap);
let expected = vec![5, 4, 3, 2, 1];
assert_eq!(expected, actual);
assert_eq!(0, heap.len());
assert_eq!(true, heap.is_empty());
}
#[test]
fn pushing_same_node_multiple_times_does_not_alter_pop_order() {
let nodes = [
fnode(1, 10, 100),
fnode(2, 10, 101),
fnode(3, 10, 102),
fnode(4, 10, 103),
fnode(5, 10, 104),
];
let mut heap = empty_frontier();
push_all(&mut heap, &nodes);
push_all(&mut heap, &nodes);
push_all(&mut heap, &nodes);
push_all(&mut heap, &nodes);
push_all(&mut heap, &nodes);
assert_eq!(5, heap.len());
assert_eq!(false, heap.is_empty());
let actual = pop_all(&mut heap);
let expected = vec![5, 4, 3, 2, 1];
assert_eq!(expected, actual);
assert_eq!(0, heap.len());
assert_eq!(true, heap.is_empty());
}
#[test]
fn pushing_nodes_triggers_reordering_if_lplen_is_better_up() {
let nodes_1 = [
fnode(1, 10, 100),
fnode(2, 10, 101),
fnode(3, 10, 102),
fnode(4, 10, 103),
fnode(5, 10, 104),
];
let nodes_2 = [
fnode(1, 15, 100),
fnode(2, 15, 99),
fnode(3, 15, 98),
fnode(4, 15, 97),
fnode(5, 15, 96),
];
let nodes_3 = [
fnode(1, 20, 92),
fnode(2, 20, 93),
fnode(3, 20, 94),
fnode(4, 20, 95),
fnode(5, 20, 96),
];
let mut heap = empty_frontier();
push_all(&mut heap, &nodes_1);
push_all(&mut heap, &nodes_2);
push_all(&mut heap, &nodes_3);
assert_eq!(5, heap.len());
assert_eq!(false, heap.is_empty());
let actual = pop_all(&mut heap);
let expected = vec![5, 4, 3, 2, 1];
assert_eq!(expected, actual);
assert_eq!(0, heap.len());
assert_eq!(true, heap.is_empty());
}
fn push_all<T: SubProblemRanking<State = usize>>(heap: &mut NoDupFrontier<T>, nodes: &[SubProblem<usize>]) {
for n in nodes.iter() {
heap.push(n.clone());
}
}
fn pop_all<T: SubProblemRanking<State = usize>>(heap: &mut NoDupFrontier<T>) -> Vec<usize> {
let mut popped = vec![];
while let Some(n) = heap.pop() {
popped.push(*n.state)
}
popped
}
fn fnode(state: usize, value: isize, ub: isize) -> SubProblem<usize> {
SubProblem {
state: Arc::new(state),
path : vec![],
value,
ub
}
}
}