range_action_map/
range_area.rs

1//! 一段数据结构内维护的区间，相比用户给出的区间，还需要额外存区间端点
2
3use super::{ArgsType, CutSet, DiffSet, IdentType, Segment};
4#[derive(Debug)]
5pub struct RangeArea<SegmentType: Segment> {
6    pub start: usize,
7    pub end: usize,
8    pub segment: SegmentType,
9}
10
11impl<SegmentType: Segment> RangeArea<SegmentType> {
12    #[inline]
13    /// 当前区间是否包含 pos 这个点
14    pub fn contains(&self, pos: usize) -> bool {
15        self.start <= pos && pos < self.end
16    }
17    /// 尝试空出[start, end)区间。即删除当前区间中和[start, end)相交的部分。
18    ///
19    /// **注意，这个函数在内部已经 unmap 了对应的区间中的映射，调用后不需要再手动 unmap**。
20    /// 这个函数默认参数中的 start 和 end 是按页对齐的
21    pub fn shrink_or_split_if_overlap(
22        &mut self,
23        start: usize,
24        end: usize,
25        args: ArgsType,
26    ) -> DiffSet<SegmentType> {
27        if end <= self.start || self.end <= start {
28            // 不相交
29            DiffSet::Unchanged
30        } else if start <= self.start && self.end <= end {
31            // 被包含
32            self.segment.remove(args);
33            DiffSet::Removed
34        } else if self.start < start && end < self.end {
35            // 需要分割
36            let old_end = self.end;
37            self.end = start;
38            DiffSet::Splitted(Self {
39                start: end,
40                end: old_end,
41                segment: self.segment.split_and_remove_middle(start, end, args),
42            })
43        } else if end < self.end {
44            // 需要删除前半段
45            self.segment.shrink_to_right(end, args);
46            self.start = end;
47            DiffSet::Shrinked
48        } else {
49            // 删除后半段
50            assert!(self.start < start); // 最后一种情况一定是后半段重叠
51            self.segment.shrink_to_left(start, args);
52            self.end = start;
53            DiffSet::Shrinked
54        }
55    }
56    /// 尝试修改与 [start, end) 区间相交的部分的权限。
57    /// 如果这一修改导致区间分裂，则分别返回分出的每个区间。
58    pub fn split_and_modify_if_overlap(
59        &mut self,
60        start: usize,
61        end: usize,
62        new_flag: IdentType,
63        args: ArgsType,
64    ) -> CutSet<SegmentType> {
65        if end <= self.start || self.end <= start {
66            // 不相交
67            CutSet::Unchanged
68        } else if start <= self.start && self.end <= end {
69            // 被包含
70            self.segment.modify(new_flag, args);
71            CutSet::WholeModified
72        } else if self.start < start && end < self.end {
73            // 包含区间，需要分割三段
74            let pos_left = start; // 第一个裁剪点
75            let pos_right = end; // 第二个裁剪点
76            let (seg_middle, seg_right) = self
77                .segment
78                .modify_middle(pos_left, pos_right, new_flag, args);
79            let old_end = self.end;
80            self.end = start;
81            CutSet::ModifiedMiddle(
82                Self {
83                    start: start,
84                    end: end,
85                    segment: seg_middle,
86                },
87                Self {
88                    start: end,
89                    end: old_end,
90                    segment: seg_right,
91                },
92            )
93        } else if end < self.end {
94            // 前半段相交
95            let old_end = self.end;
96            self.end = end;
97            // 注意返回的是右半段
98            CutSet::ModifiedLeft(Self {
99                start: end,
100                end: old_end,
101                segment: self.segment.modify_left(end, new_flag, args),
102            })
103        } else {
104            // 后半段相交
105            assert!(self.start < start); // 最后一种情况一定是后半段重叠
106            let old_end = self.end;
107            self.end = start;
108            CutSet::ModifiedRight(Self {
109                start: start,
110                end: old_end,
111                segment: self.segment.modify_right(start, new_flag, args),
112            })
113        }
114    }
115
116    /// 当前区间与 [start, end) 是否相交
117    pub fn is_overlap_with(&self, start: usize, end: usize) -> bool {
118        !(self.end <= start || self.start >= end)
119    }
120}
range_action_map/range_area.rs

range_action_map/
range_area.rs
