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