haar_lib/ds/
persistent_queue.rs

1//! 永続キュー
2
3use std::rc::Rc;
4
5#[derive(Debug)]
6struct Node<T> {
7    value: T,
8    ancestors: Vec<Rc<Node<T>>>,
9    depth: usize,
10}
11
12impl<T> Node<T> {
13    fn new(value: T) -> Self {
14        Self {
15            value,
16            ancestors: vec![],
17            depth: 0,
18        }
19    }
20}
21
22/// 永続キュー
23#[derive(Default, Debug)]
24pub struct PersistentQueue<T> {
25    #[allow(clippy::type_complexity)]
26    front_back_node: Option<(Rc<Node<T>>, Rc<Node<T>>)>,
27}
28
29impl<T> PersistentQueue<T> {
30    /// 値`value`をただ一つだけもつ[`PersistentQueue`]を生成する。
31    pub fn new(value: T) -> Self {
32        let p = Rc::new(Node::new(value));
33
34        Self {
35            front_back_node: Some((Rc::clone(&p), p)),
36        }
37    }
38
39    /// 値`value`を末尾に追加した[`PersistentQueue`]を返す。
40    pub fn push(&self, value: T) -> Self {
41        match self.front_back_node.as_ref() {
42            None => {
43                let p = Rc::new(Node::new(value));
44                Self {
45                    front_back_node: Some((Rc::clone(&p), p)),
46                }
47            }
48            Some((front_node, back_node)) => {
49                let mut t = Node::new(value);
50
51                t.depth = back_node.depth + 1;
52
53                t.ancestors.reserve(back_node.ancestors.len() + 1);
54                t.ancestors.push(Rc::clone(back_node));
55                for i in 1.. {
56                    match t.ancestors.get(i - 1) {
57                        None => {
58                            break;
59                        }
60                        Some(s) => {
61                            if let Some(x) = s.ancestors.get(i - 1) {
62                                t.ancestors.push(Rc::clone(x));
63                            } else {
64                                break;
65                            }
66                        }
67                    }
68                }
69                t.ancestors.shrink_to_fit();
70
71                Self {
72                    front_back_node: Some((Rc::clone(front_node), Rc::new(t))),
73                }
74            }
75        }
76    }
77
78    /// 先頭の要素を削除した[`PersistentQueue`]を返す。    
79    pub fn pop(&self) -> Option<Self> {
80        self.front_back_node
81            .as_ref()
82            .map(|(front_node, back_node)| {
83                if front_node.depth == back_node.depth {
84                    Self {
85                        front_back_node: None,
86                    }
87                } else {
88                    let mut d = back_node.depth - front_node.depth - 1;
89                    let mut t = back_node;
90
91                    for i in (0..t.ancestors.len()).rev() {
92                        if d >= (1 << i) {
93                            d -= 1 << i;
94                            t = &t.ancestors[i];
95                        }
96                        if d == 0 {
97                            break;
98                        }
99                    }
100
101                    Self {
102                        front_back_node: Some((Rc::clone(t), Rc::clone(back_node))),
103                    }
104                }
105            })
106    }
107
108    /// 先頭の要素への参照を返す。
109    pub fn front(&self) -> Option<&T> {
110        self.front_back_node.as_ref().map(|(t, _)| &t.value)
111    }
112
113    /// 末尾の要素への参照を返す。
114    pub fn back(&self) -> Option<&T> {
115        self.front_back_node.as_ref().map(|(_, t)| &t.value)
116    }
117
118    /// キューが空ならば`true`を返す。
119    pub fn is_empty(&self) -> bool {
120        self.front_back_node.is_none()
121    }
122
123    /// キューの要素数を返す。
124    pub fn len(&self) -> usize {
125        self.front_back_node
126            .as_ref()
127            .map_or(0, |(f, b)| b.depth - f.depth + 1)
128    }
129}
haar_lib/ds/persistent_queue.rs

haar_lib/ds/
persistent_queue.rs
