pub struct RangeSet<T, V>{ /* private fields */ }Expand description
一个「区间集合」数据结构:维护一组有序、互不重叠的半开区间 [start, end)。
- 插入时会把重叠/相邻且 kind 相等的区间自动合并。
- 删除一个区间时,会从集合里移除交集;必要时把已有区间拆成左右两段。
约定:空区间(start >= end)会被忽略。
Implementations§
Source§impl<T, V> RangeSet<T, V>
impl<T, V> RangeSet<T, V>
Sourcepub fn as_slice(&self) -> &[T]
pub fn as_slice(&self) -> &[T]
返回内部区间的切片(已排序、已合并、互不重叠)。
Examples found in repository?
examples/debug_demo.rs (line 70)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 let mut set: RangeSetHeapless<DemoRange<i32>, 16> = RangeSetHeapless::default();
49 set.add(DemoRange::new(1..5, true))?;
50 set.add(DemoRange::new(3..8, true))?;
51 set.add(DemoRange::new(10..15, true))?;
52 set.add(DemoRange::new(12..18, true))?;
53
54 println!("=== 区间合并结果 ===");
55 for (i, info) in set.iter().enumerate() {
56 println!(
57 "Element {}: [{}, {})",
58 i,
59 info.range().start,
60 info.range().end
61 );
62 }
63
64 println!("\n=== Debug 格式 ===");
65 for (i, info) in set.iter().enumerate() {
66 println!("Element {}: {:?}", i, info);
67 }
68
69 println!("\n=== 完整切片 ===");
70 println!("{:?}", set.as_slice());
71
72 Ok(())
73}Sourcepub fn iter(&self) -> impl Iterator<Item = &T>
pub fn iter(&self) -> impl Iterator<Item = &T>
返回区间迭代器(零拷贝)。
Examples found in repository?
examples/debug_demo.rs (line 55)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 let mut set: RangeSetHeapless<DemoRange<i32>, 16> = RangeSetHeapless::default();
49 set.add(DemoRange::new(1..5, true))?;
50 set.add(DemoRange::new(3..8, true))?;
51 set.add(DemoRange::new(10..15, true))?;
52 set.add(DemoRange::new(12..18, true))?;
53
54 println!("=== 区间合并结果 ===");
55 for (i, info) in set.iter().enumerate() {
56 println!(
57 "Element {}: [{}, {})",
58 i,
59 info.range().start,
60 info.range().end
61 );
62 }
63
64 println!("\n=== Debug 格式 ===");
65 for (i, info) in set.iter().enumerate() {
66 println!("Element {}: {:?}", i, info);
67 }
68
69 println!("\n=== 完整切片 ===");
70 println!("{:?}", set.as_slice());
71
72 Ok(())
73}More examples
examples/key_demo.rs (line 101)
90fn main() -> Result<(), Box<dyn std::error::Error>> {
91 // 使用字符串作为 kind 的示例
92 let mut set: RangeSetHeapless<StrRange<i32>> = RangeSetHeapless::default();
93
94 // 添加不同类型的区间(使用不同的 kind)
95 set.add(StrRange::new(0..10, "type_a", true))?;
96 set.add(StrRange::new(5..15, "type_b", true))?; // 与 type_a 重叠,但 kind 不同,会分割
97 set.add(StrRange::new(20..30, "type_a", true))?;
98 set.add(StrRange::new(25..35, "type_a", true))?; // 与上一个 type_a 重叠,会合并
99
100 println!("=== 带 kind 的区间集合 ===");
101 for info in set.iter() {
102 println!(
103 "Range: [{}, {}), Kind: {:?}",
104 info.range().start,
105 info.range().end,
106 info.kind()
107 );
108 }
109
110 // 演示:只有 kind 相同的相邻区间才会合并
111 let mut set2: RangeSetHeapless<IntRange<i32>> = RangeSetHeapless::default();
112 set2.add(IntRange::new(0..10, 1, true))?;
113 set2.add(IntRange::new(10..20, 1, true))?; // kind 相同且相邻,会合并
114 set2.add(IntRange::new(20..30, 2, true))?; // kind 不同,不合并
115 set2.add(IntRange::new(30..40, 2, true))?; // kind 相同且相邻,会合并
116
117 println!("\n=== 相邻区间合并示例 ===");
118 for info in set2.iter() {
119 println!(
120 "Range: [{}, {}), Kind: {}",
121 info.range().start,
122 info.range().end,
123 info.kind()
124 );
125 }
126
127 Ok(())
128}examples/overlap_demo.rs (line 56)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 println!("=== 测试:kind 不同时,后者覆盖交集 ===\n");
49
50 let mut set = RangeSetHeapless::<StrRange<i32>>::default();
51
52 // 场景 1: 完全覆盖
53 println!("场景 1: 完全覆盖");
54 set.add(StrRange::new(10..20, "A", true))?;
55 println!("添加 [10, 20) kind=A");
56 for info in set.iter() {
57 println!(
58 " [{}, {}) kind={}",
59 info.range().start,
60 info.range().end,
61 info.kind()
62 );
63 }
64
65 set.add(StrRange::new(10..20, "B", true))?;
66 println!("添加 [10, 20) kind=B (完全覆盖)");
67 for info in set.iter() {
68 println!(
69 " [{}, {}) kind={}",
70 info.range().start,
71 info.range().end,
72 info.kind()
73 );
74 }
75
76 // 场景 2: 部分覆盖(左侧)
77 println!("\n场景 2: 部分覆盖(左侧)");
78 set.clear();
79 set.add(StrRange::new(10..30, "A", true))?;
80 println!("添加 [10, 30) kind=A");
81 for info in set.iter() {
82 println!(
83 " [{}, {}) kind={}",
84 info.range().start,
85 info.range().end,
86 info.kind()
87 );
88 }
89
90 set.add(StrRange::new(5..20, "B", true))?;
91 println!("添加 [5, 20) kind=B (覆盖左侧)");
92 for info in set.iter() {
93 println!(
94 " [{}, {}) kind={}",
95 info.range().start,
96 info.range().end,
97 info.kind()
98 );
99 }
100
101 // 场景 3: 部分覆盖(右侧)
102 println!("\n场景 3: 部分覆盖(右侧)");
103 set.clear();
104 set.add(StrRange::new(10..30, "A", true))?;
105 println!("添加 [10, 30) kind=A");
106 for info in set.iter() {
107 println!(
108 " [{}, {}) kind={}",
109 info.range().start,
110 info.range().end,
111 info.kind()
112 );
113 }
114
115 set.add(StrRange::new(20..35, "B", true))?;
116 println!("添加 [20, 35) kind=B (覆盖右侧)");
117 for info in set.iter() {
118 println!(
119 " [{}, {}) kind={}",
120 info.range().start,
121 info.range().end,
122 info.kind()
123 );
124 }
125
126 // 场景 4: 中间覆盖(分裂原区间)
127 println!("\n场景 4: 中间覆盖(分裂原区间)");
128 set.clear();
129 set.add(StrRange::new(10..40, "A", true))?;
130 println!("添加 [10, 40) kind=A");
131 for info in set.iter() {
132 println!(
133 " [{}, {}) kind={}",
134 info.range().start,
135 info.range().end,
136 info.kind()
137 );
138 }
139
140 set.add(StrRange::new(20..30, "B", true))?;
141 println!("添加 [20, 30) kind=B (覆盖中间,分裂 A)");
142 for info in set.iter() {
143 println!(
144 " [{}, {}) kind={}",
145 info.range().start,
146 info.range().end,
147 info.kind()
148 );
149 }
150
151 // 场景 5: kind 相同时合并
152 println!("\n场景 5: kind 相同时合并(对比)");
153 set.clear();
154 set.add(StrRange::new(10..20, "A", true))?;
155 set.add(StrRange::new(30..40, "A", true))?;
156 println!("添加 [10, 20) kind=A 和 [30, 40) kind=A");
157 for info in set.iter() {
158 println!(
159 " [{}, {}) kind={}",
160 info.range().start,
161 info.range().end,
162 info.kind()
163 );
164 }
165
166 set.add(StrRange::new(15..35, "A", true))?;
167 println!("添加 [15, 35) kind=A (相同 kind,合并)");
168 for info in set.iter() {
169 println!(
170 " [{}, {}) kind={}",
171 info.range().start,
172 info.range().end,
173 info.kind()
174 );
175 }
176
177 // 场景 6: 复杂场景 - 多个区间
178 println!("\n场景 6: 复杂场景 - 覆盖多个不同 kind 的区间");
179 set.clear();
180 set.add(StrRange::new(0..10, "A", true))?;
181 set.add(StrRange::new(10..20, "B", true))?;
182 set.add(StrRange::new(20..30, "C", true))?;
183 println!("初始状态:");
184 for info in set.iter() {
185 println!(
186 " [{}, {}) kind={}",
187 info.range().start,
188 info.range().end,
189 info.kind()
190 );
191 }
192
193 set.add(StrRange::new(5..25, "D", true))?;
194 println!("添加 [5, 25) kind=D (覆盖三个区间的部分)");
195 for info in set.iter() {
196 println!(
197 " [{}, {}) kind={}",
198 info.range().start,
199 info.range().end,
200 info.kind()
201 );
202 }
203
204 Ok(())
205}pub fn is_empty(&self) -> bool
pub fn len(&self) -> usize
Sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Examples found in repository?
examples/overlap_demo.rs (line 78)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 println!("=== 测试:kind 不同时,后者覆盖交集 ===\n");
49
50 let mut set = RangeSetHeapless::<StrRange<i32>>::default();
51
52 // 场景 1: 完全覆盖
53 println!("场景 1: 完全覆盖");
54 set.add(StrRange::new(10..20, "A", true))?;
55 println!("添加 [10, 20) kind=A");
56 for info in set.iter() {
57 println!(
58 " [{}, {}) kind={}",
59 info.range().start,
60 info.range().end,
61 info.kind()
62 );
63 }
64
65 set.add(StrRange::new(10..20, "B", true))?;
66 println!("添加 [10, 20) kind=B (完全覆盖)");
67 for info in set.iter() {
68 println!(
69 " [{}, {}) kind={}",
70 info.range().start,
71 info.range().end,
72 info.kind()
73 );
74 }
75
76 // 场景 2: 部分覆盖(左侧)
77 println!("\n场景 2: 部分覆盖(左侧)");
78 set.clear();
79 set.add(StrRange::new(10..30, "A", true))?;
80 println!("添加 [10, 30) kind=A");
81 for info in set.iter() {
82 println!(
83 " [{}, {}) kind={}",
84 info.range().start,
85 info.range().end,
86 info.kind()
87 );
88 }
89
90 set.add(StrRange::new(5..20, "B", true))?;
91 println!("添加 [5, 20) kind=B (覆盖左侧)");
92 for info in set.iter() {
93 println!(
94 " [{}, {}) kind={}",
95 info.range().start,
96 info.range().end,
97 info.kind()
98 );
99 }
100
101 // 场景 3: 部分覆盖(右侧)
102 println!("\n场景 3: 部分覆盖(右侧)");
103 set.clear();
104 set.add(StrRange::new(10..30, "A", true))?;
105 println!("添加 [10, 30) kind=A");
106 for info in set.iter() {
107 println!(
108 " [{}, {}) kind={}",
109 info.range().start,
110 info.range().end,
111 info.kind()
112 );
113 }
114
115 set.add(StrRange::new(20..35, "B", true))?;
116 println!("添加 [20, 35) kind=B (覆盖右侧)");
117 for info in set.iter() {
118 println!(
119 " [{}, {}) kind={}",
120 info.range().start,
121 info.range().end,
122 info.kind()
123 );
124 }
125
126 // 场景 4: 中间覆盖(分裂原区间)
127 println!("\n场景 4: 中间覆盖(分裂原区间)");
128 set.clear();
129 set.add(StrRange::new(10..40, "A", true))?;
130 println!("添加 [10, 40) kind=A");
131 for info in set.iter() {
132 println!(
133 " [{}, {}) kind={}",
134 info.range().start,
135 info.range().end,
136 info.kind()
137 );
138 }
139
140 set.add(StrRange::new(20..30, "B", true))?;
141 println!("添加 [20, 30) kind=B (覆盖中间,分裂 A)");
142 for info in set.iter() {
143 println!(
144 " [{}, {}) kind={}",
145 info.range().start,
146 info.range().end,
147 info.kind()
148 );
149 }
150
151 // 场景 5: kind 相同时合并
152 println!("\n场景 5: kind 相同时合并(对比)");
153 set.clear();
154 set.add(StrRange::new(10..20, "A", true))?;
155 set.add(StrRange::new(30..40, "A", true))?;
156 println!("添加 [10, 20) kind=A 和 [30, 40) kind=A");
157 for info in set.iter() {
158 println!(
159 " [{}, {}) kind={}",
160 info.range().start,
161 info.range().end,
162 info.kind()
163 );
164 }
165
166 set.add(StrRange::new(15..35, "A", true))?;
167 println!("添加 [15, 35) kind=A (相同 kind,合并)");
168 for info in set.iter() {
169 println!(
170 " [{}, {}) kind={}",
171 info.range().start,
172 info.range().end,
173 info.kind()
174 );
175 }
176
177 // 场景 6: 复杂场景 - 多个区间
178 println!("\n场景 6: 复杂场景 - 覆盖多个不同 kind 的区间");
179 set.clear();
180 set.add(StrRange::new(0..10, "A", true))?;
181 set.add(StrRange::new(10..20, "B", true))?;
182 set.add(StrRange::new(20..30, "C", true))?;
183 println!("初始状态:");
184 for info in set.iter() {
185 println!(
186 " [{}, {}) kind={}",
187 info.range().start,
188 info.range().end,
189 info.kind()
190 );
191 }
192
193 set.add(StrRange::new(5..25, "D", true))?;
194 println!("添加 [5, 25) kind=D (覆盖三个区间的部分)");
195 for info in set.iter() {
196 println!(
197 " [{}, {}) kind={}",
198 info.range().start,
199 info.range().end,
200 info.kind()
201 );
202 }
203
204 Ok(())
205}Sourcepub fn add(&mut self, new_info: T) -> Result<(), RangeError<T>>
pub fn add(&mut self, new_info: T) -> Result<(), RangeError<T>>
添加一个区间;会把与其重叠或相邻且 kind 相等的区间自动合并。 对于 kind 不同的重叠区间:
- 如果旧区间可覆盖,则用新区间覆盖交集部分
- 如果旧区间不可覆盖,则返回冲突错误
§Errors
- 如果容量不足,返回
RangeSetError::Capacity。 - 如果与不可覆盖的区间冲突,返回
RangeSetError::Conflict。
Examples found in repository?
examples/debug_demo.rs (line 49)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 let mut set: RangeSetHeapless<DemoRange<i32>, 16> = RangeSetHeapless::default();
49 set.add(DemoRange::new(1..5, true))?;
50 set.add(DemoRange::new(3..8, true))?;
51 set.add(DemoRange::new(10..15, true))?;
52 set.add(DemoRange::new(12..18, true))?;
53
54 println!("=== 区间合并结果 ===");
55 for (i, info) in set.iter().enumerate() {
56 println!(
57 "Element {}: [{}, {})",
58 i,
59 info.range().start,
60 info.range().end
61 );
62 }
63
64 println!("\n=== Debug 格式 ===");
65 for (i, info) in set.iter().enumerate() {
66 println!("Element {}: {:?}", i, info);
67 }
68
69 println!("\n=== 完整切片 ===");
70 println!("{:?}", set.as_slice());
71
72 Ok(())
73}More examples
examples/key_demo.rs (line 95)
90fn main() -> Result<(), Box<dyn std::error::Error>> {
91 // 使用字符串作为 kind 的示例
92 let mut set: RangeSetHeapless<StrRange<i32>> = RangeSetHeapless::default();
93
94 // 添加不同类型的区间(使用不同的 kind)
95 set.add(StrRange::new(0..10, "type_a", true))?;
96 set.add(StrRange::new(5..15, "type_b", true))?; // 与 type_a 重叠,但 kind 不同,会分割
97 set.add(StrRange::new(20..30, "type_a", true))?;
98 set.add(StrRange::new(25..35, "type_a", true))?; // 与上一个 type_a 重叠,会合并
99
100 println!("=== 带 kind 的区间集合 ===");
101 for info in set.iter() {
102 println!(
103 "Range: [{}, {}), Kind: {:?}",
104 info.range().start,
105 info.range().end,
106 info.kind()
107 );
108 }
109
110 // 演示:只有 kind 相同的相邻区间才会合并
111 let mut set2: RangeSetHeapless<IntRange<i32>> = RangeSetHeapless::default();
112 set2.add(IntRange::new(0..10, 1, true))?;
113 set2.add(IntRange::new(10..20, 1, true))?; // kind 相同且相邻,会合并
114 set2.add(IntRange::new(20..30, 2, true))?; // kind 不同,不合并
115 set2.add(IntRange::new(30..40, 2, true))?; // kind 相同且相邻,会合并
116
117 println!("\n=== 相邻区间合并示例 ===");
118 for info in set2.iter() {
119 println!(
120 "Range: [{}, {}), Kind: {}",
121 info.range().start,
122 info.range().end,
123 info.kind()
124 );
125 }
126
127 Ok(())
128}examples/overlap_demo.rs (line 54)
47fn main() -> Result<(), Box<dyn std::error::Error>> {
48 println!("=== 测试:kind 不同时,后者覆盖交集 ===\n");
49
50 let mut set = RangeSetHeapless::<StrRange<i32>>::default();
51
52 // 场景 1: 完全覆盖
53 println!("场景 1: 完全覆盖");
54 set.add(StrRange::new(10..20, "A", true))?;
55 println!("添加 [10, 20) kind=A");
56 for info in set.iter() {
57 println!(
58 " [{}, {}) kind={}",
59 info.range().start,
60 info.range().end,
61 info.kind()
62 );
63 }
64
65 set.add(StrRange::new(10..20, "B", true))?;
66 println!("添加 [10, 20) kind=B (完全覆盖)");
67 for info in set.iter() {
68 println!(
69 " [{}, {}) kind={}",
70 info.range().start,
71 info.range().end,
72 info.kind()
73 );
74 }
75
76 // 场景 2: 部分覆盖(左侧)
77 println!("\n场景 2: 部分覆盖(左侧)");
78 set.clear();
79 set.add(StrRange::new(10..30, "A", true))?;
80 println!("添加 [10, 30) kind=A");
81 for info in set.iter() {
82 println!(
83 " [{}, {}) kind={}",
84 info.range().start,
85 info.range().end,
86 info.kind()
87 );
88 }
89
90 set.add(StrRange::new(5..20, "B", true))?;
91 println!("添加 [5, 20) kind=B (覆盖左侧)");
92 for info in set.iter() {
93 println!(
94 " [{}, {}) kind={}",
95 info.range().start,
96 info.range().end,
97 info.kind()
98 );
99 }
100
101 // 场景 3: 部分覆盖(右侧)
102 println!("\n场景 3: 部分覆盖(右侧)");
103 set.clear();
104 set.add(StrRange::new(10..30, "A", true))?;
105 println!("添加 [10, 30) kind=A");
106 for info in set.iter() {
107 println!(
108 " [{}, {}) kind={}",
109 info.range().start,
110 info.range().end,
111 info.kind()
112 );
113 }
114
115 set.add(StrRange::new(20..35, "B", true))?;
116 println!("添加 [20, 35) kind=B (覆盖右侧)");
117 for info in set.iter() {
118 println!(
119 " [{}, {}) kind={}",
120 info.range().start,
121 info.range().end,
122 info.kind()
123 );
124 }
125
126 // 场景 4: 中间覆盖(分裂原区间)
127 println!("\n场景 4: 中间覆盖(分裂原区间)");
128 set.clear();
129 set.add(StrRange::new(10..40, "A", true))?;
130 println!("添加 [10, 40) kind=A");
131 for info in set.iter() {
132 println!(
133 " [{}, {}) kind={}",
134 info.range().start,
135 info.range().end,
136 info.kind()
137 );
138 }
139
140 set.add(StrRange::new(20..30, "B", true))?;
141 println!("添加 [20, 30) kind=B (覆盖中间,分裂 A)");
142 for info in set.iter() {
143 println!(
144 " [{}, {}) kind={}",
145 info.range().start,
146 info.range().end,
147 info.kind()
148 );
149 }
150
151 // 场景 5: kind 相同时合并
152 println!("\n场景 5: kind 相同时合并(对比)");
153 set.clear();
154 set.add(StrRange::new(10..20, "A", true))?;
155 set.add(StrRange::new(30..40, "A", true))?;
156 println!("添加 [10, 20) kind=A 和 [30, 40) kind=A");
157 for info in set.iter() {
158 println!(
159 " [{}, {}) kind={}",
160 info.range().start,
161 info.range().end,
162 info.kind()
163 );
164 }
165
166 set.add(StrRange::new(15..35, "A", true))?;
167 println!("添加 [15, 35) kind=A (相同 kind,合并)");
168 for info in set.iter() {
169 println!(
170 " [{}, {}) kind={}",
171 info.range().start,
172 info.range().end,
173 info.kind()
174 );
175 }
176
177 // 场景 6: 复杂场景 - 多个区间
178 println!("\n场景 6: 复杂场景 - 覆盖多个不同 kind 的区间");
179 set.clear();
180 set.add(StrRange::new(0..10, "A", true))?;
181 set.add(StrRange::new(10..20, "B", true))?;
182 set.add(StrRange::new(20..30, "C", true))?;
183 println!("初始状态:");
184 for info in set.iter() {
185 println!(
186 " [{}, {}) kind={}",
187 info.range().start,
188 info.range().end,
189 info.kind()
190 );
191 }
192
193 set.add(StrRange::new(5..25, "D", true))?;
194 println!("添加 [5, 25) kind=D (覆盖三个区间的部分)");
195 for info in set.iter() {
196 println!(
197 " [{}, {}) kind={}",
198 info.range().start,
199 info.range().end,
200 info.kind()
201 );
202 }
203
204 Ok(())
205}Sourcepub fn remove(&mut self, range: Range<T::Type>) -> Result<(), RangeError<T>>
pub fn remove(&mut self, range: Range<T::Type>) -> Result<(), RangeError<T>>
删除一个区间:从集合中移除与其相交的部分。
若被删除区间位于某个已有区间内部,会导致该已有区间被拆分为两段(保留原有 kind)。
§Errors
如果容量不足(删除操作导致区间分裂,新区间数量超过容量),返回 RangeSetError::Capacity。
Sourcepub fn extend<I>(&mut self, ranges: I) -> Result<(), RangeError<T>>where
I: IntoIterator<Item = T>,
pub fn extend<I>(&mut self, ranges: I) -> Result<(), RangeError<T>>where
I: IntoIterator<Item = T>,
Trait Implementations§
Auto Trait Implementations§
impl<T, V> Freeze for RangeSet<T, V>where
V: Freeze,
impl<T, V> RefUnwindSafe for RangeSet<T, V>where
V: RefUnwindSafe,
T: RefUnwindSafe,
impl<T, V> Send for RangeSet<T, V>
impl<T, V> Sync for RangeSet<T, V>
impl<T, V> Unpin for RangeSet<T, V>
impl<T, V> UnwindSafe for RangeSet<T, V>where
V: UnwindSafe,
T: UnwindSafe,
Blanket Implementations§
§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
§unsafe fn clone_to_uninit(&self, dest: *mut u8)
unsafe fn clone_to_uninit(&self, dest: *mut u8)
🔬This is a nightly-only experimental API. (
clone_to_uninit)