7 fn as_index(&self) -> usize;
10 // A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
11 // The elements are sorted by integer keys.
13 pub struct IndexdMinHeap<T: Ord + Indexing> {
14 positions: Vec<usize>,
18 const TREE_ARITY: usize = 4;
19 const INVALID_POSITION: usize = std::usize::MAX;
21 impl<T: Ord + Indexing> IndexdMinHeap<T> {
22 pub fn new(max_id: usize) -> IndexdMinHeap<T> {
24 positions: vec![INVALID_POSITION; max_id],
29 pub fn len(&self) -> usize {
33 pub fn is_empty(&self) -> bool {
37 pub fn contains_index(&self, id: usize) -> bool {
38 self.positions[id] != INVALID_POSITION
41 pub fn clear(&mut self) {
42 for element in &self.data {
43 self.positions[element.as_index()] = INVALID_POSITION;
48 pub fn peek(&self) -> Option<&T> {
52 pub fn pop(&mut self) -> Option<T> {
53 self.data.pop().map(|mut item| {
54 self.positions[item.as_index()] = INVALID_POSITION;
56 self.positions[item.as_index()] = 0;
57 self.positions[self.data[0].as_index()] = INVALID_POSITION;
58 swap(&mut item, &mut self.data[0]);
59 self.move_down_in_tree(0);
65 pub fn push(&mut self, element: T) {
66 assert!(!self.contains_index(element.as_index()));
67 let insert_position = self.len();
68 self.positions[element.as_index()] = insert_position;
69 self.data.push(element);
70 self.move_up_in_tree(insert_position);
73 // Updates the key of an element if the new key is smaller than the old key.
74 // Does nothing if the new key is larger.
75 // Undefined if the element is not part of the queue.
76 pub fn decrease_key(&mut self, element: T) {
77 let position = self.positions[element.as_index()];
78 self.data[position] = element;
79 self.move_up_in_tree(position);
82 // Updates the key of an element if the new key is larger than the old key.
83 // Does nothing if the new key is smaller.
84 // Undefined if the element is not part of the queue.
85 pub fn increase_key(&mut self, element: T) {
86 let position = self.positions[element.as_index()];
87 self.data[position] = element;
88 self.move_down_in_tree(position);
91 fn move_up_in_tree(&mut self, position: usize) {
93 let mut position = position;
94 let mut hole = Hole::new(&mut self.data, position);
97 let parent = (position - 1) / TREE_ARITY;
99 if hole.get(parent) < hole.element() {
103 self.positions[hole.get(parent).as_index()] = position;
104 hole.move_to(parent);
108 self.positions[hole.element().as_index()] = position;
112 fn move_down_in_tree(&mut self, position: usize) {
114 let mut position = position;
115 let heap_size = self.len();
116 let mut hole = Hole::new(&mut self.data, position);
119 if let Some(smallest_child) = IndexdMinHeap::<T>::children_index_range(position, heap_size).min_by_key(|&child_index| hole.get(child_index)) {
120 if hole.get(smallest_child) >= hole.element() {
121 self.positions[hole.element().as_index()] = position;
122 return; // no child is smaller
125 self.positions[hole.get(smallest_child).as_index()] = position;
126 hole.move_to(smallest_child);
127 position = smallest_child;
129 self.positions[hole.element().as_index()] = position;
130 return; // no children at all
136 fn children_index_range(parent_index: usize, heap_size: usize) -> std::ops::Range<usize> {
137 let first_child = TREE_ARITY * parent_index + 1;
138 let last_child = min(TREE_ARITY * parent_index + TREE_ARITY + 1, heap_size);
139 first_child..last_child
144 // This is an optimization copied straight from the rust stdlib binary heap
145 // it allows to avoid always swapping elements pairwise and rather
146 // move each element only once.
149 /// Hole represents a hole in a slice i.e. an index without valid value
150 /// (because it was moved from or duplicated).
151 /// In drop, `Hole` will restore the slice by filling the hole
152 /// position with the value that was originally removed.
153 struct Hole<'a, T: 'a> {
155 /// `elt` is always `Some` from new until drop.
160 impl<'a, T> Hole<'a, T> {
161 /// Create a new Hole at index `pos`.
163 /// Unsafe because pos must be within the data slice.
165 unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
166 debug_assert!(pos < data.len());
167 let elt = ptr::read(&data[pos]);
175 /// Returns a reference to the element removed.
177 fn element(&self) -> &T {
178 self.elt.as_ref().unwrap()
181 /// Returns a reference to the element at `index`.
183 /// Unsafe because index must be within the data slice and not equal to pos.
185 unsafe fn get(&self, index: usize) -> &T {
186 debug_assert!(index != self.pos);
187 debug_assert!(index < self.data.len());
188 self.data.get_unchecked(index)
191 /// Move hole to new location
193 /// Unsafe because index must be within the data slice and not equal to pos.
195 unsafe fn move_to(&mut self, index: usize) {
196 debug_assert!(index != self.pos);
197 debug_assert!(index < self.data.len());
198 let index_ptr: *const _ = self.data.get_unchecked(index);
199 let hole_ptr = self.data.get_unchecked_mut(self.pos);
200 ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
205 impl<'a, T> Drop for Hole<'a, T> {
208 // fill the hole again
211 ptr::write(self.data.get_unchecked_mut(pos), self.elt.take().unwrap());