1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
use crate::algorithms::{Queue, QueueType}; use crate::StateId; #[derive(Debug, Default, Clone)] pub struct StateOrderQueue { front: StateId, back: Option<StateId>, enqueued: Vec<bool>, } impl Queue for StateOrderQueue { fn head(&mut self) -> Option<usize> { Some(self.front) } fn enqueue(&mut self, state: usize) { if self.back.is_none() || self.front > self.back.unwrap() { self.front = state; self.back = Some(state) } else if state > self.back.unwrap() { self.back = Some(state); } else if state < self.front { self.front = state; } while self.enqueued.len() <= state { self.enqueued.push(false); } self.enqueued[state] = true; } fn dequeue(&mut self) { self.enqueued[self.front] = false; if let Some(back_) = self.back { while self.front <= back_ && !self.enqueued[self.front] { self.front += 1; } } } fn update(&mut self, _state: usize) {} fn is_empty(&self) -> bool { if let Some(back_) = self.back { self.front > back_ } else { true } } fn clear(&mut self) { if let Some(back_) = self.back { for i in self.front..=back_ { self.enqueued[i] = false; } } self.front = 0; self.back = None; } fn queue_type(&self) -> QueueType { QueueType::StateOrderQueue } }