How to back a HashMap with a Vec

Question

I tried implementing a generic A* tree search algorithm. The important part is in the function hucs marked with a TODO:

use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::cmp::Ordering;

pub trait SearchTree<A> {
    fn available_actions(&self) -> Vec<A>;
    fn apply_action(&self, act: &A) -> Self;
}

pub trait CostSearchTree<A>: SearchTree<A> + Eq {
    fn action_cost(&self, act: &A) -> f64;
}

/// Node in the expanded search tree for uniform cost search with heuristic
struct HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    cost: f64,
    heuristic_cost: f64,
    parent_index: usize,
    action: Option<A>,
    tree: T,
}

impl<A, T> PartialEq for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn eq(&self, other: &HucsNode<A, T>) -> bool {
        // Can be used for closed list checking if we just compare the trees
        return self.tree == other.tree;
    }
}

impl<A, T> Eq for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
}

impl<A, T> PartialOrd for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn partial_cmp(&self, other: &HucsNode<A, T>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<A, T> Ord for HucsNode<A, T>
where
    T: CostSearchTree<A>,
{
    fn cmp(&self, other: &HucsNode<A, T>) -> Ordering {
        let self_cost = self.cost + self.heuristic_cost;
        let other_cost = other.cost + other.heuristic_cost;

        // Flip for min-heap
        match other_cost.partial_cmp(&self_cost) {
            Some(order) => order,
            _ => Ordering::Equal,
        }
    }
}

/// Perform a uniform cost search with a monotonous heuristic function on a search tree.
/// Returns a sequence of actions if a state is found that satisfies the predicate or None if the search terminates before.
pub fn hucs<A, T: CostSearchTree<A> + Hash>(
    tree: T,
    predicate: &Fn(&T) -> bool,
    heuristic: &Fn(&T) -> f64,
) -> Option<Vec<A>> {

    let mut node_heap = BinaryHeap::new() as BinaryHeap<HucsNode<A, T>>;

    // Push the initial node onto the tree
    node_heap.push(HucsNode {
        action: None,
        parent_index: usize::max_value(),
        cost: 0.0,
        heuristic_cost: heuristic(&tree),
        tree: tree,
    });

    let mut old_nodes = Vec::new();
    let mut last_node_index = 0 as usize;

    'outer: while let Some(current_node) = node_heap.pop() {
        // Break borrows with scope so current_node can be moved out
        {
            if predicate(&current_node.tree) {
                return Some(form_action_sequence(current_node, old_nodes));
            }

            // Check if visited nodes already contains this tree with less cost
            // TODO: Time complexity is hardly ideal
            for old_node in old_nodes.iter() {
                if old_node.tree == current_node.tree && old_node.cost <= current_node.cost {
                    continue 'outer;
                }
            }

            let ref current_tree = current_node.tree;

            for action in current_tree.available_actions() {

                let action_cost = current_tree.action_cost(&action);
                let new_tree = current_tree.apply_action(&action);
                let new_cost = current_node.cost + action_cost;

                let new_node = HucsNode {
                    action: Some(action),
                    cost: new_cost,
                    parent_index: last_node_index,
                    heuristic_cost: heuristic(&new_tree),
                    tree: new_tree,
                };

                node_heap.push(new_node);
            }
        }

        old_nodes.push(current_node);
        last_node_index += 1;
    }

    return None;
}

/// Restore the sequence of actions that was used to get to this node by climbing the tree of expanded nodes
fn form_action_sequence<A, T: CostSearchTree<A>>(
    leaf: HucsNode<A, T>,
    mut older_nodes: Vec<HucsNode<A, T>>,
) -> Vec<A> {

    let mut action_vector = Vec::new();

    let mut current = leaf;

    while let Some(action) = current.action {
        action_vector.insert(0, action);

        // Safe to swap as nodes' parents are always before them
        current = older_nodes.swap_remove(current.parent_index);
    }

    return action_vector;
}

The problem is that looking up whether the current node was in the old nodes by scanning over the old nodes takes way too long. Therefore I wanted to add a HashMap. Since I however also need to be able to access the old nodes by indices to form the solution action sequence at the end, I also need to keep the Vec. To solve this I tried adding a wrapper that I can insert into the HashMap as a key that just looks up its content in the Vec like this:

use std::hash::Hash;
use std::hash::Hasher;

struct BackedHashWrapper<'a, T: 'a + Hash + Eq> {
    source: &'a Vec<T>,
    index: usize,
}

impl<A, T> Hash for HucsNode<A, T>
where
    T: CostSearchTree<A> + Hash,
{
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.tree.hash(state);
    }
}

impl<'a, T> Hash for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.source[self.index].hash(state);
    }
}

impl<'a, T> PartialEq for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
    fn eq(&self, other: &BackedHashWrapper<T>) -> bool {
        self.source[self.index] == other.source[other.index]
    }
}

impl<'a, T> Eq for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
}

I cannot figure out how to implement this in the hucs method, I tried the following just for adding elements to the hashmap

...
let mut old_nodes = Vec::new();
let mut hash_map = HashMap::new();
...

    ...
    hash_map.insert(BackedHashWrapper {source: &old_nodes, index: last_node_index}, current_node.cost);
    old_nodes.push(current_node);
    last_node_index += 1;
    ...

but the borrow checker will not allow me to create such a BackedHashWrapper while the source vector is mutable. Clearly I am doing this completely the wrong way, so how could I accomplish this without having to clone either the tree or any actions?

Answer 1

I suppose it is easier to use other type of backing storage (TypedArena from typed-arena crate, for example).

But taking the question at face value, the problem you are dealing with is caused by Rust borrowing rules. That is you can't have shared (&) and mutable (&mut) references or multiple mutable references to the same object in the same scope.

hash_map in your example holds shared references to the vector, "freezing" it, which makes it impossible to modify the vector while hash_map is in the scope.

Solution to this problem is interior mutability pattern.

In your case, you can use RefCell<Vec<T>> to be able to modify vector while holding multiple references to it.

use std::cell::RefCell;

type RVec<T> = RefCell<Vec<T>>;

struct BackedHashWrapper<'a, T: 'a + Hash + Eq> {
    source: &'a RVec<T>,
    index: usize,
}

...
impl<'a, T> Hash for BackedHashWrapper<'a, T>
where
    T: Eq + Hash,
{
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.source.borrow()[self.index].hash(state);
    }
}
...
// Similar changes for Eq and PartialEq
...
let mut old_nodes: RVec<_> = RefCell::default();
let mut hash_map = HashMap::new();
...

    ...
    hash_map.insert(BackedHashWrapper {source: &old_nodes, index: last_node_index}, current_node.cost);
    old_nodes.borrow_mut().push(current_node);
    last_node_index += 1;
    ...

Maybe a couple of borrow()s and borrow_mut()s will be required in other places.