ranges_ext/
lib.rs

1#![no_std]
2
3#[cfg(feature = "alloc")]
4extern crate alloc;
5
6use core::{
7    cmp::{max, min},
8    fmt::Debug,
9    ops::Range,
10};
11
12pub(crate) mod core_ops;
13mod heapless_ops;
14pub(crate) mod helpers;
15pub mod prelude;
16
17#[cfg(feature = "alloc")]
18mod alloc_ops;
19
20pub trait VecOps<T: RangeInfo> {
21    fn push(&mut self, item: T) -> Result<(), RangeError<T>>;
22    fn as_slice(&self) -> &[T];
23    fn drain<R>(&mut self, range: R) -> impl Iterator<Item = T>
24    where
25        R: core::ops::RangeBounds<usize>;
26    fn len(&self) -> usize;
27    fn is_empty(&self) -> bool {
28        self.len() == 0
29    }
30    fn remove(&mut self, index: usize) -> T;
31    fn insert(&mut self, index: usize, item: T) -> Result<(), RangeError<T>>;
32    fn clear(&mut self);
33}
34
35pub trait RangeExtBaseOps<T: RangeInfo>: VecOps<T> {
36    fn merge_add_with_temp(
37        &mut self,
38        new_info: T,
39        temp: &mut impl VecOps<T>,
40    ) -> Result<(), RangeError<T>> {
41        temp.clear();
42        if !core_ops::validate_range(&new_info) {
43            return Ok(());
44        }
45
46        // 检查冲突
47        core_ops::check_conflicts(self.as_slice(), &new_info)?;
48
49        for elem in self.drain(..) {
50            if !helpers::ranges_overlap(&elem.range(), &new_info.range()) {
51                temp.push(elem)?;
52                continue;
53            }
54
55            if elem.kind() == new_info.kind() {
56                temp.push(elem)?;
57                continue;
58            }
59
60            let split_parts = helpers::split_range(&elem, &new_info.range());
61            for part in split_parts.iter().flatten() {
62                temp.push(part.clone())?;
63            }
64        }
65
66        // 将处理后的结果复制回原数组（正序）
67        for elem in temp.as_slice() {
68            self.push(elem.clone())?;
69        }
70
71        // 插入新区间并合并
72        if self.is_empty() {
73            self.push(new_info).map_err(|_| RangeError::Capacity)?;
74            return Ok(());
75        }
76
77        // 二分查找插入位置
78        let insert_at = core_ops::find_insert_position(self.as_slice(), &new_info.range());
79
80        let mut merged_range = new_info.range();
81        let mut insert_at = insert_at;
82
83        // 向左合并
84        while insert_at > 0 {
85            let left = &self.as_slice()[insert_at - 1];
86            if left.range().end < merged_range.start || left.kind() != new_info.kind() {
87                break;
88            }
89            merged_range.start = min(merged_range.start, left.range().start);
90            merged_range.end = max(merged_range.end, left.range().end);
91            self.remove(insert_at - 1);
92            insert_at -= 1;
93        }
94
95        // 向右合并
96        while insert_at < self.len() {
97            let right = &self.as_slice()[insert_at];
98            if right.range().start > merged_range.end || right.kind() != new_info.kind() {
99                break;
100            }
101            merged_range.start = min(merged_range.start, right.range().start);
102            merged_range.end = max(merged_range.end, right.range().end);
103            self.remove(insert_at);
104        }
105
106        self.insert(insert_at, new_info.clone_with_range(merged_range))?;
107        Ok(())
108    }
109
110    fn merge_remove_with_temp(
111        &mut self,
112        range: Range<T::Type>,
113        temp: &mut impl VecOps<T>,
114    ) -> Result<(), RangeError<T>> {
115        temp.clear();
116        if range.start >= range.end || self.is_empty() {
117            return Ok(());
118        }
119
120        for elem in self.drain(..) {
121            if !helpers::ranges_overlap(&elem.range(), &range) {
122                temp.push(elem)?;
123                continue;
124            }
125
126            let split_parts = helpers::split_range(&elem, &range);
127            for part in split_parts.iter().flatten() {
128                temp.push(part.clone())?;
129            }
130        }
131
132        // 将处理后的结果复制回原数组（正序）
133        for elem in temp.as_slice() {
134            self.push(elem.clone())?;
135        }
136
137        Ok(())
138    }
139}
140
141pub trait RangeVecOps<T: RangeInfo> {
142    fn merge_add(&mut self, new_info: T, temp: &mut [u8]) -> Result<(), RangeError<T>>;
143
144    fn merge_remove(&mut self, range: Range<T::Type>, temp: &mut [u8])
145    -> Result<(), RangeError<T>>;
146
147    fn merge_extend<I>(&mut self, ranges: I, temp: &mut [u8]) -> Result<(), RangeError<T>>
148    where
149        I: IntoIterator<Item = T>;
150
151    fn contains_point(&self, value: T::Type) -> bool;
152}
153
154/// RangeSet 操作 trait（alloc 版本），为带分配器的容器提供区间集合功能
155/// 相比 RangeSetOps，不需要用户提供临时缓冲区
156#[cfg(feature = "alloc")]
157pub trait RangeVecAllocOps<T: RangeInfo> {
158    /// 添加一个区间（会自动合并相邻区间）
159    fn merge_add(&mut self, new_info: T) -> Result<(), RangeError<T>>;
160
161    /// 删除一个区间
162    fn merge_remove(&mut self, range: Range<T::Type>) -> Result<(), RangeError<T>>;
163
164    /// 批量添加多个区间
165    fn merge_extend<I>(&mut self, ranges: I) -> Result<(), RangeError<T>>
166    where
167        I: IntoIterator<Item = T>;
168
169    /// 查询某个值是否落在任意一个区间中
170    fn contains_point(&self, value: T::Type) -> bool;
171}
172
173/// RangeSet 错误类型
174#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
175pub enum RangeError<T>
176where
177    T: RangeInfo,
178{
179    /// 容量不足错误
180    #[error("RangeSet capacity exceeded")]
181    Capacity,
182    /// 区间冲突错误：尝试覆盖不可覆盖的区间
183    #[error("Range conflict: new {new:?} conflicts with existing non-overwritable {existing:?}")]
184    Conflict {
185        /// 新添加的区间
186        new: T,
187        /// 已存在的冲突区间
188        existing: T,
189    },
190}
191
192pub trait RangeInfo: Debug + Clone + Sized + Default {
193    type Kind: Debug + Eq + Clone;
194    type Type: Ord + Copy;
195    fn range(&self) -> Range<Self::Type>;
196    fn kind(&self) -> Self::Kind;
197    fn overwritable(&self) -> bool;
198    fn clone_with_range(&self, range: Range<Self::Type>) -> Self;
199}
ranges_ext/lib.rs

ranges_ext/
lib.rs
