rust_rsm/alg/
prio_queue.rs

1#![allow(non_camel_case_types)]
2#![allow(non_snake_case)]
3#![allow(non_upper_case_globals)]
4
5use std::cmp::{Ord,PartialOrd,Eq};
6use super::*;
7
8#[derive(Clone,Debug,PartialEq,Eq)]
9pub struct node_cost_t {
10    pub node_idx:usize,
11    pub priority:u32,
12}
13
14impl Ord for node_cost_t {
15    #[inline(always)]
16    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
17        self.priority.cmp(&other.priority).then_with(|| self.node_idx.cmp(&other.node_idx))
18    }
19}
20impl PartialOrd for node_cost_t {
21    #[inline(always)]
22    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
23        Some(self.cmp(other))
24    }
25}
26pub struct priority_queue_t {
27    start_idx:usize,
28    data:Vec<node_cost_t>,
29}
30
31impl priority_queue_t {
32
33    pub fn new()->Self {
34        return Self {
35            start_idx:0,
36            data:Vec::with_capacity(SPF_MAX_NODE_NUM*2),
37        }
38    }
39
40    pub fn push(&mut self,node_id:usize, prio:u32) {
41        let node = node_cost_t {
42            node_idx:node_id,
43            priority:prio,
44        };
45        self.data.push(node);
46        self.data.as_mut_slice()[self.start_idx..].sort();
47    }
48
49    //add a data item , but app must call sort later
50    pub fn push_nosort(&mut self,node_id:usize, prio:u32) {
51        let node = node_cost_t {
52            node_idx:node_id,
53            priority:prio,
54        };
55        self.data.push(node);
56    }
57
58    pub fn sort(&mut self) {
59        self.data.as_mut_slice()[self.start_idx..].sort();
60    }
61
62    //pop a minimum value item
63    pub fn pop_min(&mut self)->Option<node_cost_t> {
64        if self.start_idx>=self.data.len() {
65            return None
66        }
67        let v = self.data[self.start_idx].clone(); 
68        self.start_idx+=1;
69        
70        return Some(v)
71    }
72
73    /*降低一个元素的优先级*/
74    #[inline(always)]
75    pub fn decrease_priority(&mut self,node_idx:usize, prio:u32) {
76        let real_idx=node_idx+self.start_idx;
77        if real_idx>=self.data.len() || self.data[real_idx].priority==prio{
78            return
79        }
80        self.data[real_idx].priority=prio;
81        self.data.as_mut_slice()[self.start_idx..].sort();
82        
83    }
84
85    #[inline(always)]
86    pub fn get_item_by_index(&self,idx:usize)->Option<node_cost_t> {
87        let real_idx=idx+self.start_idx;
88        if real_idx>= self.data.len() {
89            return None;
90        }
91
92        return Some(unsafe { self.data.get_unchecked(real_idx).clone()})
93    }
94
95    #[inline(always)]
96    pub fn len(&self)->usize {
97        self.data.len()-self.start_idx
98    }
99}
rust_rsm/alg/prio_queue.rs

rust_rsm/alg/
prio_queue.rs
