keyed_priority_queue/
lib.rs

Help
1//! This is priority queue that supports elements priority modification and early removal.
2//!
3//! It uses HashMap and own implementation of binary heap to achieve this.
4//!
5//! Each entry has associated *key* and *priority*.
6//! Keys must be unique, and hashable; priorities must implement Ord trait.
7//!
8//! Popping returns element with biggest priority.
9//! Pushing adds element to queue.
10//! Also it is possible to change priority or remove item by key.
11//!
12//! Pop, push, change priority, remove by key have ***O(log n)*** time complexity;
13//! peek, lookup by key are ***O(1)***.
14//!
15//! # Examples
16//!
17//! This is implementation of [A* algorithm][a_star] for 2D grid.
18//! Each cell in grid has the cost.
19//! This algorithm finds shortest path to target using heuristics.
20//!
21//! Let open set be the set of position where algorithm can move in next step.
22//! Sometimes better path for node in open set is found
23//! so the priority of it needs to be updated with new value.
24//!
25//! This example shows how to change priority in [`KeyedPriorityQueue`] when needed.
26//!
27//! [a_star]: https://en.wikipedia.org/wiki/A*_search_algorithm
28//! [`KeyedPriorityQueue`]: struct.KeyedPriorityQueue.html
29//!
30//! ```
31//! use keyed_priority_queue::{KeyedPriorityQueue, Entry};
32//! use std::cmp::Reverse;
33//! use std::collections::HashSet;
34//! use std::ops::Index;
35//!
36//! struct Field {
37//!     rows: usize,
38//!     columns: usize,
39//!     costs: Box<[u32]>,
40//! }
41//!
42//! #[derive(Eq, PartialEq, Debug, Hash, Copy, Clone)]
43//! struct Position {
44//!     row: usize,
45//!     column: usize,
46//! }
47//!
48//! impl Index<Position> for Field {
49//!     type Output = u32;
50//!
51//!     fn index(&self, index: Position) -> &Self::Output {
52//!         &self.costs[self.columns * index.row + index.column]
53//!     }
54//! }
55//!
56//! // From cell we can move upper, right, bottom and left
57//! fn get_neighbors(pos: Position, field: &Field) -> Vec<Position> {
58//!     let mut items = Vec::with_capacity(4);
59//!     if pos.row > 0 {
60//!         items.push(Position { row: pos.row - 1, column: pos.column });
61//!     }
62//!     if pos.row + 1 < field.rows {
63//!         items.push(Position { row: pos.row + 1, column: pos.column });
64//!     }
65//!     if pos.column > 0 {
66//!         items.push(Position { row: pos.row, column: pos.column - 1 });
67//!     }
68//!     if pos.column + 1 < field.columns {
69//!         items.push(Position { row: pos.row, column: pos.column + 1 });
70//!     }
71//!     items
72//! }
73//!
74//! fn find_path(start: Position, target: Position, field: &Field) -> Option<u32> {
75//!     if start == target {
76//!         return Some(field[start]);
77//!     }
78//!     let calc_heuristic = |pos: Position| -> u32 {
79//!         ((target.row as isize - pos.row as isize).abs()
80//!             + (target.column as isize - pos.column as isize).abs()) as u32
81//!     };
82//!
83//!     // Already handled this points
84//!     let mut closed_set: HashSet<Position> = HashSet::new();
85//!     // Positions sortered by total cost and real cost.
86//!     // We prefer items with lower real cost if total ones are same.
87//!     #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
88//!     struct Cost {
89//!         total: u32,
90//!         real: u32,
91//!     }
92//!     // Queue that contains all nodes that available for next step
93//!     // Min-queue required so Reverse struct used as priority.
94//!     let mut available = KeyedPriorityQueue::<Position, Reverse<Cost>>::new();
95//!     available.push(
96//!         start,
97//!         Reverse(Cost {
98//!             total: calc_heuristic(start),
99//!             real: 0,
100//!         }),
101//!     );
102//!     while let Some((current_pos, Reverse(current_cost))) = available.pop() {
103//!         // We have reached target
104//!         if current_pos == target {
105//!             return Some(current_cost.real);
106//!         }
107//!
108//!         closed_set.insert(current_pos);
109//!
110//!         for next in get_neighbors(current_pos, &field).into_iter()
111//!             .filter(|x| !closed_set.contains(x))
112//!             {
113//!                 let real = field[next] + current_cost.real;
114//!                 let total = current_cost.real + calc_heuristic(next);
115//!                 let cost = Cost { total, real };
116//!                 // Entire this interaction will make only one hash lookup
117//!                 match available.entry(next) {
118//!                     Entry::Vacant(entry) => {
119//!                         // Add new position to queue
120//!                         entry.set_priority(Reverse(cost));
121//!                     }
122//!                     Entry::Occupied(entry) if *entry.get_priority() < Reverse(cost) => {
123//!                         // Have found better path to node in queue
124//!                         entry.set_priority(Reverse(cost));
125//!                     }
126//!                     _ => { /* Have found worse path. */ }
127//!                 };
128//!             }
129//!     }
130//!     None
131//! }
132//!
133//!let field = Field {
134//!    rows: 4,
135//!    columns: 4,
136//!    costs: vec![
137//!        1, 3, 3, 6, //
138//!        4, 4, 3, 8, //
139//!        3, 1, 2, 4, //
140//!        4, 8, 9, 4, //
141//!    ].into_boxed_slice(),
142//!};
143//!
144//!let start = Position { row: 0, column: 0 };
145//!let end = Position { row: 3, column: 3 };
146//!assert_eq!(find_path(start, end, &field), Some(18));
147//! ```
148//!
149
150mod editable_binary_heap;
151mod keyed_priority_queue;
152mod mediator;
153
154pub use crate::keyed_priority_queue::{
155    Entry, KeyedPriorityQueue, KeyedPriorityQueueBorrowIter, KeyedPriorityQueueIterator,
156    OccupiedEntry, SetPriorityNotFoundError, VacantEntry,
157};
158
159#[doc = include_str!("../../Readme.md")]
160#[cfg(doctest)]
161pub struct ReadmeDoctests;
keyed_priority_queue/lib.rs

keyed_priority_queue/
lib.rs
