traitgraph_algo/dijkstra/
epoch_array_dijkstra_node_weight_array.rs

1use crate::dijkstra::{DijkstraWeight, NodeWeightArray};
2
3/// An epoch counter array.
4///
5/// This can be used to check if an index is current by comparing its entry in the epoch array to the current epoch.
6/// To unmark all values, the current epoch can be increased in O(1). Only overflows have to be handled by resetting all epoch counters.
7pub struct EpochArray {
8    epochs: Vec<u32>,
9    current_epoch: u32,
10}
11
12impl EpochArray {
13    /// Create a new epoch array of given length where all values are outdated.
14    pub fn new(len: usize) -> Self {
15        Self {
16            epochs: vec![0; len],
17            current_epoch: 1,
18        }
19    }
20
21    /// Outdate all indices.
22    pub fn clear(&mut self) {
23        if self.current_epoch == u32::MAX {
24            for epoch in self.epochs.iter_mut() {
25                *epoch = 0;
26            }
27            self.current_epoch = 1;
28        } else {
29            self.current_epoch += 1;
30        }
31    }
32
33    /// Set the given index as current and returns true if the given index was current before, and false otherwise
34    ///
35    /// Safety: Undefined behaviour if the index is out of bounds of the epoch array.
36    #[inline]
37    pub fn update(&mut self, index: usize) -> bool {
38        unsafe {
39            let result = *self.epochs.get_unchecked(index) == self.current_epoch;
40            *self.epochs.get_unchecked_mut(index) = self.current_epoch;
41            result
42        }
43        //self.epochs[index] = self.current_epoch;
44    }
45
46    /// Returns true if the given index is current, and false otherwise.
47    ///
48    /// Safety: Undefined behaviour if the index is out of bounds of the epoch array.
49    #[inline]
50    pub fn get(&self, index: usize) -> bool {
51        unsafe { *self.epochs.get_unchecked(index) == self.current_epoch }
52    }
53
54    /// Updates the given index and returns true if the given index was current before, and false otherwise.
55    ///
56    /// Safety: Undefined behaviour if the index is out of bounds of the epoch array.
57    #[inline]
58    pub fn get_and_update(&mut self, index: usize) -> bool {
59        let epoch = unsafe { self.epochs.get_unchecked_mut(index) };
60        if *epoch == self.current_epoch {
61            true
62        } else {
63            *epoch = self.current_epoch;
64            false
65        }
66    }
67}
68
69/// An epoched node weight array that can be cleared in O(1) most of the times.
70/// Only if the epoch in the epoch array overflows, clearing takes linear time.
71pub struct EpochNodeWeightArray<WeightType> {
72    weights: Vec<WeightType>,
73    epochs: EpochArray,
74    size: usize,
75}
76
77impl<WeightType: DijkstraWeight> EpochNodeWeightArray<WeightType> {
78    #[inline]
79    fn make_current(&mut self, node_index: usize) {
80        if !self.epochs.get_and_update(node_index) {
81            self.weights[node_index] = WeightType::infinity();
82            self.size += 1;
83        }
84    }
85}
86
87impl<WeightType: DijkstraWeight + Copy> NodeWeightArray<WeightType>
88    for EpochNodeWeightArray<WeightType>
89{
90    fn new(len: usize) -> Self {
91        Self {
92            weights: vec![WeightType::infinity(); len],
93            epochs: EpochArray::new(len),
94            size: 0,
95        }
96    }
97
98    #[inline]
99    fn get(&self, node_index: usize) -> WeightType {
100        if self.epochs.get(node_index) {
101            self.weights[node_index]
102        } else {
103            WeightType::infinity()
104        }
105    }
106
107    #[inline]
108    fn get_mut<'this: 'result, 'result>(
109        &'this mut self,
110        node_index: usize,
111    ) -> &'result mut WeightType {
112        self.make_current(node_index);
113        &mut self.weights[node_index]
114    }
115
116    #[inline]
117    fn set(&mut self, node_index: usize, weight: WeightType) {
118        self.weights[node_index] = weight;
119        if !self.epochs.update(node_index) {
120            self.size += 1;
121        }
122    }
123
124    fn clear(&mut self) {
125        self.epochs.clear();
126        self.size = 0;
127    }
128
129    fn size(&self) -> usize {
130        self.size
131    }
132}
traitgraph_algo/dijkstra/epoch_array_dijkstra_node_weight_array.rs

traitgraph_algo/dijkstra/
epoch_array_dijkstra_node_weight_array.rs
