oxihuman_core/
priority_queue_ext.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Extended priority queue with decrease-key via BinaryHeap + HashMap.
6
7use std::cmp::Reverse;
8use std::collections::{BinaryHeap, HashMap};
9
10/// An entry in the priority queue.
11#[derive(Debug, Clone, PartialEq)]
12pub struct PqEntry {
13    pub key: String,
14    pub priority: i64,
15}
16
17impl Eq for PqEntry {}
18
19impl PartialOrd for PqEntry {
20    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
21        Some(self.cmp(other))
22    }
23}
24
25impl Ord for PqEntry {
26    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
27        self.priority.cmp(&other.priority) /* natural order; Reverse wrapper makes min-heap */
28    }
29}
30
31/// Extended priority queue supporting decrease-key.
32pub struct PriorityQueueExt {
33    heap: BinaryHeap<Reverse<PqEntry>>,
34    current: HashMap<String, i64>,
35}
36
37/// Construct a new PriorityQueueExt.
38pub fn new_priority_queue_ext() -> PriorityQueueExt {
39    PriorityQueueExt {
40        heap: BinaryHeap::new(),
41        current: HashMap::new(),
42    }
43}
44
45impl PriorityQueueExt {
46    /// Insert or update the priority of `key`.
47    pub fn insert(&mut self, key: &str, priority: i64) {
48        self.current.insert(key.to_string(), priority);
49        self.heap.push(Reverse(PqEntry {
50            key: key.to_string(),
51            priority,
52        }));
53    }
54
55    /// Decrease the priority of `key` (lower value = higher priority).
56    pub fn decrease_key(&mut self, key: &str, new_priority: i64) {
57        if let Some(p) = self.current.get_mut(key) {
58            if new_priority < *p {
59                *p = new_priority;
60                self.heap.push(Reverse(PqEntry {
61                    key: key.to_string(),
62                    priority: new_priority,
63                }));
64            }
65        }
66    }
67
68    /// Pop the entry with the lowest priority value.
69    pub fn pop_min(&mut self) -> Option<PqEntry> {
70        while let Some(Reverse(entry)) = self.heap.pop() {
71            if let Some(&cur) = self.current.get(&entry.key) {
72                if cur == entry.priority {
73                    self.current.remove(&entry.key);
74                    return Some(entry);
75                }
76                /* stale entry, skip */
77            }
78        }
79        None
80    }
81
82    /// Peek at the minimum entry without removing.
83    pub fn peek_min(&self) -> Option<(&str, i64)> {
84        self.current
85            .iter()
86            .min_by_key(|(_, &p)| p)
87            .map(|(k, &p)| (k.as_str(), p))
88    }
89
90    /// Number of live entries.
91    pub fn len(&self) -> usize {
92        self.current.len()
93    }
94
95    /// Whether the queue is empty.
96    pub fn is_empty(&self) -> bool {
97        self.current.is_empty()
98    }
99
100    /// Check whether `key` is in the queue.
101    pub fn contains(&self, key: &str) -> bool {
102        self.current.contains_key(key)
103    }
104
105    /// Get the current priority of `key`.
106    pub fn priority_of(&self, key: &str) -> Option<i64> {
107        self.current.get(key).copied()
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn test_empty() {
117        /* new queue is empty */
118        let pq = new_priority_queue_ext();
119        assert!(pq.is_empty());
120        assert_eq!(pq.len(), 0);
121    }
122
123    #[test]
124    fn test_insert_and_pop() {
125        /* insert then pop returns the entry */
126        let mut pq = new_priority_queue_ext();
127        pq.insert("a", 10);
128        let e = pq.pop_min().expect("should succeed");
129        assert_eq!(e.key, "a");
130        assert_eq!(e.priority, 10);
131    }
132
133    #[test]
134    fn test_min_heap_order() {
135        /* pop_min returns entries in ascending priority order */
136        let mut pq = new_priority_queue_ext();
137        pq.insert("c", 30);
138        pq.insert("a", 10);
139        pq.insert("b", 20);
140        let first = pq.pop_min().expect("should succeed");
141        assert_eq!(first.priority, 10);
142    }
143
144    #[test]
145    fn test_decrease_key() {
146        /* decrease_key lowers priority and affects pop order */
147        let mut pq = new_priority_queue_ext();
148        pq.insert("a", 50);
149        pq.insert("b", 20);
150        pq.decrease_key("a", 5);
151        let first = pq.pop_min().expect("should succeed");
152        assert_eq!(first.key, "a");
153        assert_eq!(first.priority, 5);
154    }
155
156    #[test]
157    fn test_contains() {
158        /* contains returns correct bool */
159        let mut pq = new_priority_queue_ext();
160        pq.insert("x", 1);
161        assert!(pq.contains("x"));
162        assert!(!pq.contains("y"));
163    }
164
165    #[test]
166    fn test_priority_of() {
167        /* priority_of returns current priority */
168        let mut pq = new_priority_queue_ext();
169        pq.insert("z", 42);
170        assert_eq!(pq.priority_of("z"), Some(42));
171        assert_eq!(pq.priority_of("missing"), None);
172    }
173
174    #[test]
175    fn test_pop_removes_from_len() {
176        /* len decreases after pop */
177        let mut pq = new_priority_queue_ext();
178        pq.insert("a", 1);
179        pq.insert("b", 2);
180        assert_eq!(pq.len(), 2);
181        pq.pop_min();
182        assert_eq!(pq.len(), 1);
183    }
184
185    #[test]
186    fn test_decrease_key_no_increase() {
187        /* decrease_key with larger value is a no-op */
188        let mut pq = new_priority_queue_ext();
189        pq.insert("a", 10);
190        pq.decrease_key("a", 20);
191        assert_eq!(pq.priority_of("a"), Some(10));
192    }
193}
oxihuman_core/priority_queue_ext.rs

oxihuman_core/
priority_queue_ext.rs
