geo_buffer/priority_queue/
mod.rs

1#![allow(dead_code)]
2pub(crate) struct PriorityQueue<T: std::cmp::PartialOrd>{
3    size: usize,
4    content: Vec<T>,
5}
6
7impl<T: std::cmp::PartialOrd> PriorityQueue<T>{
8    pub fn new() -> Self{
9        Self { size: 0, content: Vec::new(), }
10    }
11
12    pub fn initialize(&mut self){
13        self.size = 0;
14        self.content = Vec::new();
15    }
16
17    pub fn is_empty(&self) -> bool{
18        self.size == 0
19    }
20
21    pub fn insert(&mut self, item: T){
22        self.content.push(item);
23        let mut cur = self.size;
24        let mut par;
25        while cur != 0{
26            par = (cur-1)/2;
27            if self.content[cur] < self.content[par] {
28                self.content.swap(cur, par);
29                cur = par;
30            }
31            else {break;}
32        }
33        self.size += 1;
34    }
35
36    pub fn peek(&self) -> Option<&T>{
37        if self.is_empty() == true {
38            return None;
39        }
40        Some(&self.content[0])
41    }
42
43    pub fn pop(&mut self) -> Option<T>{
44        if self.is_empty() == true {return None;}
45        let ret = self.content.swap_remove(0);
46        let mut cur = 0;
47        let mut nc;
48        self.size -= 1;
49        while cur < self.size{
50            let lc = cur*2 + 1;
51            let rc = cur*2 + 2;
52            if lc >= self.size {break;}
53            else if rc >= self.size {nc = lc;}
54            else {nc = if self.content[lc] < self.content[rc] {lc} else {rc};}
55            if self.content[nc] < self.content[cur] {
56                self.content.swap(cur, nc);
57                cur = nc;
58            }
59            else {break;}
60        }
61        Some(ret)
62    }
63}
geo_buffer/priority_queue/mod.rs

geo_buffer/priority_queue/
mod.rs
