earley_omnitool/
binary_heap.rs

1// Copyright 2019 The Rust Project Developers, Piotr Czarnecki.
2// See the COPYRIGHT
3// file at the top-level directory of this distribution and at
4// http://rust-lang.org/COPYRIGHT.
5//
6// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
7// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
8// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
9// option. This file may not be copied, modified, or distributed
10// except according to those terms.
11
12//! A priority queue implemented with a binary heap.
13
14#![allow(missing_docs)]
15#![cfg_attr(feature = "cargo-clippy", allow(nonminimal_bool))]
16
17use std::mem::swap;
18use std::u32;
19
20use forest::Forest;
21use item::{CompletedItem, CompletedItemLinked, Item};
22use recognizer::Recognizer;
23
24impl<'g, F> Recognizer<'g, F>
25    where F: Forest,
26{
27    /// Returns the greatest item in the binary heap, or `None` if it is empty.
28    #[inline]
29    pub fn heap_peek(&self) -> Option<CompletedItem<F::NodeRef>> {
30        self.complete.get(0).and_then(|&right_item|
31            self.medial.get(right_item.idx as usize).map(|left_item|
32                CompletedItem {
33                    origin: left_item.origin,
34                    dot: left_item.dot,
35                    left_node: left_item.node,
36                    right_node: right_item.node,
37                }
38            )
39        )
40    }
41
42    #[inline(always)]
43    fn heap_get(&self, idx_idx: usize) -> Option<&Item<F::NodeRef>> {
44        self.complete.get(idx_idx).and_then(|&item| self.medial.get(item.idx as usize))
45    }
46
47    /// Removes the greatest item from the binary heap and returns it, or `None` if it
48    /// is empty.
49    pub fn heap_pop(&mut self) -> Option<CompletedItem<F::NodeRef>> {
50        self.complete.pop().and_then(move |mut right_item| {
51            if !self.complete.is_empty() {
52                swap(&mut right_item, &mut self.complete[0]);
53                self.sift_down(0);
54            }
55            self.medial.get(right_item.idx as usize).map(|left_item|
56                CompletedItem {
57                    origin: left_item.origin,
58                    dot: left_item.dot,
59                    left_node: left_item.node,
60                    right_node: right_item.node,
61                }
62            )
63        })
64    }
65
66    /// Pushes an item onto the binary heap.
67    pub fn heap_push(&mut self, item: CompletedItem<F::NodeRef>) {
68        let old_indices_len = self.complete.len();
69        let old_medial_len = self.medial.len();
70        assert!(old_medial_len as u64 <= u32::MAX.into());
71        self.medial.push(item.into());
72        self.complete.push(CompletedItemLinked {
73            idx: old_medial_len as u32,
74            node: item.right_node,
75        });
76        self.sift_up(0, old_indices_len);
77    }
78
79    /// Pushes an item onto the binary heap.
80    pub fn heap_push_linked(&mut self, item: CompletedItemLinked<F::NodeRef>) {
81        let old_indices_len = self.complete.len();
82        self.complete.push(item);
83        self.sift_up(0, old_indices_len);
84    }
85
86    /// Consumes the `BinaryHeap` and returns a vector in sorted
87    /// (ascending) order.
88    fn sift_up(&mut self, start: usize, mut pos: usize) {
89        let element_idx = self.complete[pos];
90        let element = &self.medial[element_idx.idx as usize];
91        while pos > start {
92            let parent = (pos - 1) / 2;
93            let parent_idx = self.complete[parent];
94            if *element <= self.medial[parent_idx.idx as usize] {
95                break;
96            }
97            self.complete[pos] = parent_idx;
98            pos = parent;
99        }
100        self.complete[pos] = element_idx;
101    }
102
103    /// Take an element at `pos` and move it down the heap,
104    /// while its children are larger.
105    fn sift_down_range(&mut self, mut pos: usize, end: usize) {
106        let element_idx = self.complete[pos];
107        let element = &self.medial[element_idx.idx as usize];
108        let mut child = 2 * pos + 1;
109        while child < end {
110            let right = child + 1;
111            // compare with the greater of the two children
112            if right < end && !(self.heap_get(child).unwrap() > self.heap_get(right).unwrap()) {
113                child = right;
114            }
115            // if we are already in order, stop.
116            if element >= self.heap_get(child).unwrap() {
117                break;
118            }
119            self.complete[pos] = self.complete[child];
120            pos = child;
121            child = 2 * pos + 1;
122        }
123        self.complete[pos] = element_idx;
124    }
125
126    fn sift_down(&mut self, pos: usize) {
127        let len = self.complete.len();
128        self.sift_down_range(pos, len);
129    }
130}
earley_omnitool/binary_heap.rs

earley_omnitool/
binary_heap.rs
