ranges_ext/
lib.rs

1#![cfg_attr(target_os = "none", no_std)]
2
3#[cfg(feature = "alloc")]
4extern crate alloc;
5
6use core::{fmt::Debug, ops::Range};
7
8#[cfg(feature = "alloc")]
9mod vec;
10
11mod less;
12
13#[cfg(not(target_os = "none"))]
14pub mod test_helper;
15
16pub trait RangeOp: Debug + Clone + Sized + Default {
17    type Kind: Debug + Eq + Clone;
18    type Type: Ord + Copy;
19    fn range(&self) -> Range<Self::Type>;
20    fn kind(&self) -> Self::Kind;
21    fn overwritable(&self, other: &Self) -> bool;
22    fn mergeable(&self, other: &Self) -> bool {
23        self.kind() == other.kind()
24    }
25    fn clone_with_range(&self, range: Range<Self::Type>) -> Self;
26}
27
28#[allow(clippy::len_without_is_empty)]
29pub trait VecOp<T: RangeOp>: Send + 'static {
30    fn push(&mut self, item: T) -> Result<(), RangeError<T>>;
31    fn as_slice(&self) -> &[T];
32    fn len(&self) -> usize;
33    fn remove(&mut self, index: usize) -> T;
34    fn insert(&mut self, index: usize, item: T) -> Result<(), RangeError<T>>;
35
36    /// 合并相同类型且相邻或重叠的range
37    ///
38    /// 此方法会遍历集合，找到所有相同kind且范围相邻或重叠的range，
39    /// 并将它们合并成更大的range，以减少集合中的元素数量。
40    fn merge_same_kind(&mut self) {
41        loop {
42            let mut merge_pair: Option<(usize, usize)> = None;
43
44            // 找到第一对可以合并的range
45            for i in 0..self.len() {
46                for j in (i + 1)..self.len() {
47                    let slice = self.as_slice();
48                    let current = &slice[i];
49                    let next = &slice[j];
50
51                    // 检查是否同类型
52                    if current.mergeable(next) {
53                        let current_range = current.range();
54                        let next_range = next.range();
55
56                        // 检查是否相邻或重叠
57                        // 相邻：current.end >= next.start 且 next.end >= current.start
58                        if current_range.end >= next_range.start
59                            && next_range.end >= current_range.start
60                        {
61                            merge_pair = Some((i, j));
62                            break;
63                        }
64                    }
65                }
66                if merge_pair.is_some() {
67                    break;
68                }
69            }
70
71            // 如果找到可以合并的pair，执行合并
72            if let Some((i, j)) = merge_pair {
73                let slice = self.as_slice();
74                let current = &slice[i];
75                let next = &slice[j];
76                let current_range = current.range();
77                let next_range = next.range();
78
79                // 计算合并后的范围
80                let new_start = current_range.start.min(next_range.start);
81                let new_end = current_range.end.max(next_range.end);
82                let merged = current.clone_with_range(new_start..new_end);
83
84                // 删除两个旧的range（先删除索引较大的）
85                self.remove(j);
86                self.remove(i);
87                // 插入合并后的range
88                let _ = self.insert(i, merged);
89            } else {
90                // 没有可以合并的pair了，退出循环
91                break;
92            }
93        }
94    }
95
96    fn merge_add(&mut self, item: T) -> Result<(), RangeError<T>> {
97        let new_range = item.range();
98        let mut i = 0;
99
100        // 遍历现有ranges，处理重叠情况
101        while i < self.len() {
102            let existing = &self.as_slice()[i];
103            let existing_range = existing.range();
104
105            // 检查是否有重叠: new.start < existing.end && new.end > existing.start
106            if new_range.start < existing_range.end && new_range.end > existing_range.start {
107                // 有重叠，检查是否可覆盖
108                if !existing.overwritable(&item) {
109                    // 不可覆盖，返回冲突错误
110                    return Err(RangeError::Conflict {
111                        new: item,
112                        existing: existing.clone(),
113                    });
114                }
115
116                // 可覆盖，根据重叠情况处理
117                if new_range.start <= existing_range.start && new_range.end >= existing_range.end {
118                    // 情况1: 新range完全覆盖旧range，删除旧的
119                    self.remove(i);
120                    // 不增加i，因为删除后当前位置是下一个元素
121                } else if new_range.start > existing_range.start
122                    && new_range.end < existing_range.end
123                {
124                    // 情况2: 新range在旧range中间，分割成两块
125                    let left = existing.clone_with_range(existing_range.start..new_range.start);
126                    let right = existing.clone_with_range(new_range.end..existing_range.end);
127
128                    self.remove(i);
129                    self.insert(i, left)?;
130                    self.insert(i + 1, right)?;
131                    i += 2; // 跳过刚插入的两个
132                } else if new_range.start <= existing_range.start {
133                    // 情况3: 新range覆盖旧range的左侧部分，保留右侧
134                    let adjusted = existing.clone_with_range(new_range.end..existing_range.end);
135                    self.remove(i);
136                    self.insert(i, adjusted)?;
137                    i += 1;
138                } else {
139                    // 情况4: 新range覆盖旧range的右侧部分，保留左侧
140                    let adjusted = existing.clone_with_range(existing_range.start..new_range.start);
141                    self.remove(i);
142                    self.insert(i, adjusted)?;
143                    i += 1;
144                }
145            } else {
146                i += 1;
147            }
148        }
149
150        // 添加新的item
151        self.push(item)?;
152        // 合并相同类型的相邻range
153        self.merge_same_kind();
154        Ok(())
155    }
156}
157
158/// RangeSet 错误类型
159#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
160pub enum RangeError<T>
161where
162    T: RangeOp,
163{
164    /// 容量不足错误
165    #[error("RangeSet capacity exceeded")]
166    Capacity,
167    /// 区间冲突错误：尝试覆盖不可覆盖的区间
168    #[error("Range conflict: new {new:?} conflicts with existing non-overwritable {existing:?}")]
169    Conflict {
170        /// 新添加的区间
171        new: T,
172        /// 已存在的冲突区间
173        existing: T,
174    },
175}
ranges_ext/lib.rs

ranges_ext/
lib.rs
