pumpkin_core/engine/
predicate_heap.rs

1use std::cmp::Ordering;
2use std::collections::BinaryHeap;
3
4use crate::predicates::Predicate;
5use crate::state::State;
6
7/// A max-heap of predicates. The keys are based on the trail positions of the predicates in the
8/// state, meaning predicates are popped in reverse trail order. Implied predicates are popped
9/// before the predicate on the trail that implies the predicate.
10#[derive(Clone, Debug, Default)]
11pub struct PredicateHeap {
12    heap: BinaryHeap<PredicateToExplain>,
13}
14
15impl PredicateHeap {
16    /// See [`BinaryHeap::is_empty`].
17    pub fn is_empty(&self) -> bool {
18        self.heap.is_empty()
19    }
20
21    /// See [`BinaryHeap::pop`].
22    pub fn pop(&mut self) -> Option<Predicate> {
23        self.heap.pop().map(|to_explain| to_explain.predicate)
24    }
25
26    /// Push a new predicate onto the heap.
27    ///
28    /// Its priority will be based on its trail position in the given `state`. This heap will
29    /// return elements through [`Self::pop`] by reverse-trail order.
30    ///
31    /// If the predicate is not true in the given state, this method panics.
32    pub fn push(&mut self, predicate: Predicate, state: &State) {
33        let trail_position = state
34            .trail_position(predicate)
35            .expect("predicate must be true in given state");
36
37        let priority = if state.is_on_trail(predicate) {
38            trail_position * 2
39        } else {
40            trail_position * 2 + 1
41        };
42
43        self.heap.push(PredicateToExplain {
44            predicate,
45            priority,
46        });
47    }
48}
49
50/// Used to order the predicates in the [`PredicateHeap`].
51///
52/// The priority is calculated based on the trail position of the predicate and whether the
53/// predicate is on the trail or implied.
54#[derive(Clone, Copy, Debug, PartialEq, Eq)]
55struct PredicateToExplain {
56    predicate: Predicate,
57    priority: usize,
58}
59
60impl PartialOrd for PredicateToExplain {
61    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
62        Some(self.cmp(other))
63    }
64}
65
66impl Ord for PredicateToExplain {
67    fn cmp(&self, other: &Self) -> Ordering {
68        self.priority.cmp(&other.priority)
69    }
70}
pumpkin_core/engine/predicate_heap.rs

pumpkin_core/engine/
predicate_heap.rs
