Могу ли я реализовать черту во время съемки окружающей среды?

Question

Я пытаюсь реализовать поиск A * Advent of Code 2019 (да, Slowpoke, я знаю). Я начал так:

fn find_path(start: Coords, goal: Coords, map: &Vec<Vec<char>>) -> Vec<Coords> {        
    struct Node {
        distance: u32,
        pos: Coords,
    }
    impl PartialEq for Node {
        fn eq(&self, other: &Self) -> bool {
            self.distance + manhattan(self.pos, goal) == other.distance + manhattan(other.pos, goal)
        }
    }
    ...
    let mut edge = BinaryHeap::new();        
    edge.push(Node{distance: 0, pos: start});
    ...

Coords - это структура с x и y. Проблема здесь в том, что я не могу использовать goal в признаке, потому что это не входит в сферу. Замыкание сможет захватить его, но я сомневаюсь, что смогу использовать здесь вместо fn. Если так, какой синтаксис? Если нет, есть ли фундаментальная причина, почему это не может быть сделано? Я не смог найти ответ в Интернете.

Я знаю, что простое решение - включить goal в Node, но это излишне, потому что я буду создавать тысячи Node во время A * , все из которых будут иметь одну и ту же цель, тратя память и циклы процессора. В принципе, goal может быть единственной глобальной переменной, но это неопрятный вариант.

Несмотря на то, что я уверен, что включение goal в Node будет работать на практике, я бы не стал .

Есть ли другой идиоматический c способ выполнить то, что я пытаюсь сделать?

Answer 1

Нет, вы не можете захватить любую среду в блоке impl. Замыкания захватывают среду, поэтому вы не можете использовать замыкание как функцию в блоке impl.

Функции и методы предназначены для вызова из любого контекста, поэтому нет гарантии, что даже существует среда, которая будет захвачена. Тот факт, что мы можем объявить типы, функции, методы и т. Д. c. внутри другой функции в основном синтаксическая хитрость.

Я бы, вероятно, создал бы тип, который обернул бы Node и goal:

struct Foo(Node, Coord);

impl Foo {
    fn value(&self) -> WhateverType {
        self.0.distance + manhattan(self.0.pos, self.1)
    }
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool {
         self.value() == other.value()
    }
}

См. Также:

• Ящик с петграфом
• Реализация графоподобной структуры данных в Rust
• Какой алгоритм из petgraph найдет кратчайший путь от A до B?

Answer 2

Причина, по которой мне нужен PartialEq, заключается в том, что Node s впоследствии переходят в BinaryHeap. Если бы у BinaryHeap была возможность предоставить пользовательский компаратор, это было бы идеально: мне бы не понадобилось Node, чтобы быть Ord, и я мог бы позволить goal находиться в этом компараторе (замыкание).

Похоже, это рассматривается: https://github.com/rust-lang/rust/pull/69454

Между тем, есть ящик, который обеспечивает эту функциональность: https://crates.io/crates/binary-heap-plus

Пока что я собираюсь принять накладные расходы на goal внутри Node, но хорошо знать мои варианты.