general_sam/utils/
rope.rs

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

general_sam/utils/
rope.rs
