jagua_rs/collision_detection/quadtree/
qt_hazard_vec.rs

1use crate::collision_detection::hazards::HazKey;
2use crate::collision_detection::hazards::filter::HazardFilter;
3use crate::collision_detection::quadtree::QTHazPresence;
4use crate::collision_detection::quadtree::QTHazard;
5use std::cmp::Ordering;
6use std::ops::Not;
7
8/// Vector of `QTHazard`s, which always remains sorted by presence.
9/// <br>
10/// This is a performance optimization to be able to quickly return the "strongest" hazard
11/// Strongest meaning the highest [`QTHazPresence`] (`Entire` > `Partial` > `None`)
12#[derive(Clone, Debug, Default)]
13pub struct QTHazardVec {
14    hazards: Vec<QTHazard>,
15    /// Number of edges from active hazards in the vector
16    n_active_edges: usize,
17}
18
19impl QTHazardVec {
20    pub fn new() -> Self {
21        Self::default()
22    }
23
24    pub fn add(&mut self, haz: QTHazard) {
25        debug_assert!(!matches!(haz.presence, QTHazPresence::None));
26        debug_assert!(
27            self.hazards
28                .iter()
29                .filter(|other| other.entity == haz.entity || other.hkey == haz.hkey)
30                .count()
31                == 0,
32            "More than one hazard from same entity or key in the vector! (This should never happen!)"
33        );
34        match self
35            .hazards
36            .binary_search_by(|probe| order_by_descending_strength(probe, &haz))
37        {
38            Ok(pos) | Err(pos) => {
39                self.n_active_edges += haz.n_edges();
40                self.hazards.insert(pos, haz);
41            }
42        }
43    }
44
45    pub fn remove(&mut self, hkey: HazKey) -> Option<QTHazard> {
46        let pos = self.hazards.iter().position(|ch| ch.hkey == hkey);
47        match pos {
48            Some(pos) => {
49                let haz = self.hazards.remove(pos);
50                self.n_active_edges -= haz.n_edges();
51                Some(haz)
52            }
53            None => None,
54        }
55    }
56
57    #[inline(always)]
58    /// Returns the strongest hazard (if any) (`Entire` > `Partial` > `None`)
59    /// Ignores any hazards that are deemed irrelevant by the filter.
60    pub fn strongest(&self, filter: &impl HazardFilter) -> Option<&QTHazard> {
61        debug_assert!(assert_caches_correct(self));
62        self.iter().find(|hz| !filter.is_irrelevant(hz.hkey))
63    }
64
65    pub fn is_empty(&self) -> bool {
66        self.hazards.is_empty()
67    }
68
69    pub fn len(&self) -> usize {
70        self.hazards.len()
71    }
72    pub fn no_partial_hazards(&self) -> bool {
73        self.hazards
74            .iter()
75            .any(|hz| matches!(hz.presence, QTHazPresence::Partial(_)))
76            .not()
77    }
78
79    pub fn iter(&self) -> impl Iterator<Item = &QTHazard> {
80        self.hazards.iter()
81    }
82
83    pub fn n_active_edges(&self) -> usize {
84        debug_assert!(assert_caches_correct(self));
85        self.n_active_edges
86    }
87}
88
89fn order_by_descending_strength(qth1: &QTHazard, qth2: &QTHazard) -> Ordering {
90    let qth_presence_sortkey = |qth: &QTHazard| match qth.presence {
91        QTHazPresence::None => 0,
92        QTHazPresence::Partial(_) => 1,
93        QTHazPresence::Entire => 2,
94    };
95
96    //sort by presence (Entire > Partial > None)
97    qth_presence_sortkey(qth1)
98        .cmp(&qth_presence_sortkey(qth2))
99        .reverse()
100}
101
102fn assert_caches_correct(qthazard_vec: &QTHazardVec) -> bool {
103    assert!(
104        qthazard_vec
105            .hazards
106            .windows(2)
107            .all(|w| order_by_descending_strength(&w[0], &w[1]) != Ordering::Greater),
108        "Hazards are not sorted correctly!"
109    );
110    assert_eq!(
111        qthazard_vec
112            .hazards
113            .iter()
114            .map(|hz| hz.n_edges())
115            .sum::<usize>(),
116        qthazard_vec.n_active_edges,
117        "Active edges count is not correct!"
118    );
119    true
120}
jagua_rs/collision_detection/quadtree/qt_hazard_vec.rs

jagua_rs/collision_detection/quadtree/
qt_hazard_vec.rs
