general_sam/utils/
rope.rs

1//! Persistent rope.
2
3use std::borrow::Cow;
4use std::ops::Deref;
5
6use super::treap::{NeedSwap, SplitTo, TreapNodeData, TreapTree};
7
8pub trait RopeData: Clone {
9    type TagType: Default;
10
11    fn get_tag(&self) -> Option<Self::TagType>;
12    fn reset_tag(&mut self);
13    fn add_tag(&mut self, tag: Self::TagType) -> NeedSwap;
14
15    fn update(&mut self, left: Option<&Self>, right: Option<&Self>);
16}
17
18#[derive(Clone, Debug)]
19pub struct RopeTreapData<Inner: RopeData> {
20    inner: Inner,
21    num: usize,
22    rev_tag: bool,
23}
24
25impl<Inner: RopeData> RopeTreapData<Inner> {
26    fn new(data: Inner) -> Self {
27        Self {
28            inner: data,
29            num: 1,
30            rev_tag: false,
31        }
32    }
33}
34
35impl<Inner: RopeData> Deref for RopeTreapData<Inner> {
36    type Target = Inner;
37
38    fn deref(&self) -> &Self::Target {
39        &self.inner
40    }
41}
42
43impl<Inner: RopeData> TreapNodeData for RopeTreapData<Inner> {
44    type TagType = (bool, Option<Inner::TagType>);
45
46    fn get_tag(&self) -> Option<Self::TagType> {
47        match (self.rev_tag, self.inner.get_tag()) {
48            (false, None) => None,
49            other => Some(other),
50        }
51    }
52
53    fn reset_tag(&mut self) {
54        self.rev_tag = false;
55        self.inner.reset_tag();
56    }
57
58    fn add_tag(&mut self, tag: Self::TagType) -> NeedSwap {
59        self.rev_tag ^= tag.0;
60        if let Some(inner_tag) = tag.1 {
61            self.inner.add_tag(inner_tag) ^ tag.0
62        } else {
63            tag.0
64        }
65    }
66
67    fn update(&mut self, left: Option<&Self>, right: Option<&Self>) {
68        self.inner
69            .update(left.map(|x| &x.inner), right.map(|x| &x.inner));
70        self.num = left.map_or(0, |x| x.num) + right.map_or(0, |x| x.num) + 1;
71    }
72}
73
74pub trait RopeBase: Sized + Clone {
75    type InnerRopeData: RopeData;
76
77    #[must_use]
78    fn new(data: Self::InnerRopeData) -> Self;
79    #[must_use]
80    fn reverse(&self) -> Self;
81    #[must_use]
82    fn split(&self, num: usize) -> (Self, Self);
83    #[must_use]
84    fn merge(&self, other: &Self) -> Self;
85    #[must_use]
86    fn add_tag(&self, tag: <Self::InnerRopeData as RopeData>::TagType) -> Self;
87
88    fn root_data_ref(&self) -> Option<&Self::InnerRopeData>;
89    fn is_empty(&self) -> bool;
90    fn len(&self) -> usize;
91    fn for_each<F: FnMut(Self::InnerRopeData)>(&self, f: F);
92
93    #[must_use]
94    fn insert(&self, pos: usize, data: Self::InnerRopeData) -> Self {
95        let (left, right) = self.split(pos);
96        left.merge(&Self::new(data)).merge(&right)
97    }
98
99    #[must_use]
100    fn remove(&self, pos: usize) -> (Self, Option<Self::InnerRopeData>) {
101        if pos >= self.len() {
102            return (self.clone(), None);
103        }
104        let (left, right) = self.split(pos);
105        let (middle, right) = right.split(1);
106        (left.merge(&right), middle.get(0))
107    }
108
109    #[must_use]
110    fn push_back(&self, data: Self::InnerRopeData) -> Self {
111        self.insert(self.len(), data)
112    }
113
114    #[must_use]
115    fn push_front(&self, data: Self::InnerRopeData) -> Self {
116        self.insert(0, data)
117    }
118
119    fn get(&self, pos: usize) -> Option<Self::InnerRopeData> {
120        self.split(pos).1.split(1).0.root_data_ref().cloned()
121    }
122}
123
124pub trait TreapBasedRopeBase:
125    RopeBase
126    + Deref<Target = TreapTree<RopeTreapData<Self::InnerRopeData>>>
127    + From<TreapTree<RopeTreapData<Self::InnerRopeData>>>
128{
129    fn new_from_rng<R: FnMut() -> u64>(data: Self::InnerRopeData, rng: R) -> Self {
130        TreapTree::new_from_rng(RopeTreapData::new(data), rng).into()
131    }
132
133    fn insert_from_rng<R: FnMut() -> u64>(
134        &self,
135        pos: usize,
136        data: Self::InnerRopeData,
137        rng: R,
138    ) -> Self {
139        let (left, right) = self.split(pos);
140        left.merge(&Self::new_from_rng(data, rng)).merge(&right)
141    }
142
143    fn push_back_from_rng<R: FnMut() -> u64>(&self, data: Self::InnerRopeData, rng: R) -> Self {
144        self.insert_from_rng(self.len(), data, rng)
145    }
146
147    fn push_front_from_rng<R: FnMut() -> u64>(&self, data: Self::InnerRopeData, rng: R) -> Self {
148        self.insert_from_rng(0, data, rng)
149    }
150
151    fn query(&self, mut pos: usize) -> Option<Cow<'_, RopeTreapData<Self::InnerRopeData>>> {
152        self.deref().query(|node| {
153            let left_size = node
154                .get_left()
155                .deref()
156                .as_ref()
157                .map_or(0, |left| left.data.num);
158            let res = pos.cmp(&left_size);
159            if pos > left_size {
160                pos -= left_size + 1;
161            }
162            res
163        })
164    }
165}
166
167impl<
168    InnerRopeData: RopeData,
169    TreapBasedRope: From<TreapTree<RopeTreapData<InnerRopeData>>>
170        + Deref<Target = TreapTree<RopeTreapData<InnerRopeData>>>
171        + Clone,
172> TreapBasedRopeBase for TreapBasedRope
173{
174}
175impl<
176    InnerRopeData: RopeData,
177    TreapBasedRope: From<TreapTree<RopeTreapData<InnerRopeData>>>
178        + Deref<Target = TreapTree<RopeTreapData<InnerRopeData>>>
179        + Clone,
180> RopeBase for TreapBasedRope
181{
182    type InnerRopeData = InnerRopeData;
183
184    fn new(data: Self::InnerRopeData) -> Self {
185        TreapTree::new(RopeTreapData::new(data)).into()
186    }
187
188    fn is_empty(&self) -> bool {
189        self.is_none()
190    }
191
192    fn len(&self) -> usize {
193        self.deref().root_data_ref().map_or(0, |x| x.num)
194    }
195
196    fn for_each<F: FnMut(Self::InnerRopeData)>(&self, mut f: F) {
197        self.deref().for_each(&mut |x| f(x.inner))
198    }
199
200    fn reverse(&self) -> Self {
201        self.deref().add_tag((true, None)).into()
202    }
203
204    fn split(&self, mut num: usize) -> (Self, Self) {
205        let (u, v) = self.deref().split(|node| {
206            let to_left_num = node.get_left().deref().as_ref().map_or(0, |x| x.data.num) + 1;
207            if num >= to_left_num {
208                num -= to_left_num;
209                SplitTo::Left
210            } else {
211                SplitTo::Right
212            }
213        });
214        (u.into(), v.into())
215    }
216
217    fn merge(&self, other: &Self) -> Self {
218        self.deref().merge(other.deref()).into()
219    }
220
221    fn root_data_ref(&self) -> Option<&Self::InnerRopeData> {
222        self.deref().root_data_ref().map(|x| &x.inner)
223    }
224
225    fn add_tag(&self, tag: <Self::InnerRopeData as RopeData>::TagType) -> Self {
226        self.deref().add_tag((false, Some(tag))).into()
227    }
228}
229
230#[derive(Clone, Debug)]
231pub struct Rope<Inner: RopeData>(TreapTree<RopeTreapData<Inner>>);
232
233impl<Inner: RopeData> From<TreapTree<RopeTreapData<Inner>>> for Rope<Inner> {
234    fn from(value: TreapTree<RopeTreapData<Inner>>) -> Self {
235        Self(value)
236    }
237}
238
239impl<Inner: RopeData> Deref for Rope<Inner> {
240    type Target = TreapTree<RopeTreapData<Inner>>;
241
242    fn deref(&self) -> &Self::Target {
243        &self.0
244    }
245}
246
247impl<Inner: RopeData> Default for Rope<Inner> {
248    fn default() -> Self {
249        Self(Default::default())
250    }
251}
252
253#[derive(Clone, Debug, Default)]
254pub struct RopeUntaggedInner<T: Clone>(T);
255
256impl<T: Clone> RopeUntaggedInner<T> {
257    pub fn into_inner(self) -> T {
258        self.0
259    }
260}
261
262impl<T: Clone> Deref for RopeUntaggedInner<T> {
263    type Target = T;
264
265    fn deref(&self) -> &Self::Target {
266        &self.0
267    }
268}
269
270impl<T: Clone> From<T> for RopeUntaggedInner<T> {
271    fn from(value: T) -> Self {
272        Self(value)
273    }
274}
275
276impl<T: Clone> RopeData for RopeUntaggedInner<T> {
277    type TagType = ();
278    fn get_tag(&self) -> Option<Self::TagType> {
279        None
280    }
281    fn reset_tag(&mut self) {}
282    fn update(&mut self, _: Option<&Self>, _: Option<&Self>) {}
283    fn add_tag(&mut self, _: Self::TagType) -> NeedSwap {
284        false
285    }
286}
287
288pub type UntaggedRope<T> = Rope<RopeUntaggedInner<T>>;
general_sam/utils/rope.rs

general_sam/utils/
rope.rs
