1use std::ops::RangeInclusive;
2
3use crate::{
4 common::{cast::Cast, default::default},
5 static_ref_default::StaticRefDefault,
6};
7
8pub struct Entry<Num, T>
9where
10 Num: PartialOrd,
11{
12 pub key: Num,
13 pub value: T,
14}
15
16pub struct RangeMap<Num, T>
17where
18 Num: PartialOrd,
19{
20 pub list: Vec<Entry<Num, T>>,
21}
22
23pub trait Union {
24 fn union(self, other: Self) -> Self;
25}
26
27#[derive(Clone, PartialEq, Debug)]
28pub struct State<T> {
29 pub value: Option<T>,
30}
31
32impl<T: 'static> StaticRefDefault for State<T> {
33 const STATIC_REF_DEFAULT: &'static Self = &Self { value: None };
34}
35
36impl<T> Union for State<T>
37where
38 T: Eq,
39{
40 fn union(self, other: Self) -> Self {
41 match self.value {
42 Some(a) => match other.value {
43 Some(b) => {
44 if a.eq(&b) {
45 State { value: Some(b) }
46 } else {
47 panic!("state values should be the same")
48 }
49 }
50 None => State { value: Some(a) },
51 },
52 None => other,
53 }
54 }
55}
56
57impl<Num, T> RangeMap<Num, T>
58where
59 Num: PartialOrd,
60 T: StaticRefDefault,
61{
62 pub fn get(&self, key: Num) -> &T {
63 let len = self.list.len() as i32;
64 let mut b = 0;
65 let mut e = len - 1;
66 loop {
67 if b >= len {
68 return T::STATIC_REF_DEFAULT;
69 }
70 if e < b {
71 return &self.list.get(b as usize).unwrap().value;
72 }
73 let mid = b + ((e - b) >> 1);
74 if key <= self.list.get(mid as usize).unwrap().key {
75 e = mid - 1;
76 } else {
77 b = mid + 1;
78 }
79 }
80 }
81}
82
83pub fn merge_list<Num, T>(list: Vec<RangeMap<Num, T>>) -> RangeMap<Num, T>
84where
85 T: Union,
86 T: Clone,
87 Num: PartialOrd,
88{
89 let mut result = RangeMap { list: default() };
90 for x in list {
91 result = merge(x, result);
92 }
93 result
94}
95
96pub fn merge<Num, T>(a: RangeMap<Num, T>, b: RangeMap<Num, T>) -> RangeMap<Num, T>
97where
98 T: Union,
99 T: Clone,
100 Num: PartialOrd,
101{
102 let list = merge_iter(a.list.into_iter(), b.list.into_iter());
103 RangeMap { list }
104}
105
106pub fn merge_iter<Num, T>(
107 mut a: impl Iterator<Item = Entry<Num, T>>,
108 mut b: impl Iterator<Item = Entry<Num, T>>,
109) -> Vec<Entry<Num, T>>
110where
111 T: Union,
112 T: Clone,
113 Num: PartialOrd,
114{
115 let mut res: Vec<Entry<Num, T>> = default();
116 let mut next_a = a.next();
117 let mut next_b = b.next();
118 loop {
119 match next_a {
120 Some(value_a) => match next_b {
121 Some(value_b) => {
122 let value = value_a.value.clone().union(value_b.value.clone());
123 if value_a.key > value_b.key {
124 res.push(Entry {
125 value,
126 key: value_b.key,
127 });
128 next_a = Some(value_a);
129 next_b = b.next();
130 } else if value_a.key < value_b.key {
131 res.push(Entry {
132 value,
133 key: value_a.key,
134 });
135 next_a = a.next();
136 next_b = Some(value_b);
137 } else {
138 res.push(Entry {
139 value,
140 key: value_a.key,
141 });
142 next_a = a.next();
143 next_b = b.next();
144 }
145 }
146 None => {
147 res.push(value_a);
148 next_a = a.next();
149 }
150 },
151 None => match next_b {
152 Some(value_b) => {
153 res.push(value_b);
154 next_b = b.next();
155 }
156 None => {
157 break;
158 }
159 },
160 }
161 }
162 res
163}
164
165pub fn from_range<T>(range: RangeInclusive<char>, value: T) -> RangeMap<char, State<T>> {
166 RangeMap {
167 list: [
168 Entry {
169 key: char::from_u32(*range.start() as u32 - 1).unwrap_or(*range.start()),
170 value: State { value: None },
171 },
172 Entry {
173 key: *range.end(),
174 value: State { value: Some(value) },
175 },
176 ]
177 .cast(),
178 }
179}
180
181pub fn from_one<T>(c: char, value: T) -> RangeMap<char, State<T>> {
182 RangeMap {
183 list: match char::from_u32(c as u32 - 1) {
184 Some(p) => [
185 Entry {
186 key: p,
187 value: State { value: None },
188 },
189 Entry {
190 key: c,
191 value: State { value: Some(value) },
192 },
193 ]
194 .cast(),
195 None => [Entry {
196 key: c,
197 value: State { value: Some(value) },
198 }]
199 .cast(),
200 },
201 }
202}
203
204#[cfg(test)]
205mod test {
206
207 use wasm_bindgen_test::wasm_bindgen_test;
208
209 use crate::{
210 common::{cast::Cast, default::default},
211 range_map::from_one,
212 };
213
214 use super::{from_range, merge, merge_list, Entry, RangeMap, State};
215
216 #[test]
217 #[wasm_bindgen_test]
218 fn test_get() {
219 let list = [
220 Entry {
221 key: 10,
222 value: 'a',
223 },
224 Entry {
225 key: 20,
226 value: 'b',
227 },
228 Entry {
229 key: 30,
230 value: 'c',
231 },
232 ]
233 .cast();
234 let rm = RangeMap { list };
235 let result = rm.get(5);
236 assert_eq!(result, &'a');
237 let result = rm.get(10);
238 assert_eq!(result, &'a');
239 let result = rm.get(15);
240 assert_eq!(result, &'b');
241 let result = rm.get(20);
242 assert_eq!(result, &'b');
243 let result = rm.get(25);
244 assert_eq!(result, &'c');
245 let result = rm.get(30);
246 assert_eq!(result, &'c');
247 let result = rm.get(35);
248 assert_eq!(*result, 0 as char);
249 }
250
251 #[test]
252 #[wasm_bindgen_test]
253 fn test_get_from_empty() {
254 let list = default();
255 let rm: RangeMap<i32, char> = RangeMap { list };
256 let result = rm.get(10);
257 assert_eq!(*result, 0 as char);
258 }
259
260 #[test]
261 #[wasm_bindgen_test]
262 fn test_merge() {
263 let a = RangeMap {
264 list: [Entry {
265 key: 10,
266 value: State { value: Some('a') },
267 }]
268 .cast(),
269 };
270 let b = RangeMap { list: default() };
271 let result = merge(a, b);
272 assert_eq!(result.list.len(), 1);
273 assert_eq!(result.list[0].key, 10);
274 assert_eq!(result.list[0].value, State { value: Some('a') });
275
276 let a = RangeMap { list: default() };
277 let b = RangeMap {
278 list: [Entry {
279 key: 10,
280 value: State { value: Some('a') },
281 }]
282 .cast(),
283 };
284 let result = merge(a, b);
285 assert_eq!(result.list.len(), 1);
286 assert_eq!(result.list[0].key, 10);
287 assert_eq!(result.list[0].value, State { value: Some('a') });
288
289 let a = RangeMap {
290 list: [
291 Entry {
292 key: 10,
293 value: State { value: Some('a') },
294 },
295 Entry {
296 key: 20,
297 value: State { value: Some('b') },
298 },
299 Entry {
300 key: 30,
301 value: State { value: Some('c') },
302 },
303 Entry {
304 key: 40,
305 value: State { value: None },
306 },
307 ]
308 .cast(),
309 };
310 let b = RangeMap {
311 list: [
312 Entry {
313 key: 10,
314 value: State { value: Some('a') },
315 },
316 Entry {
317 key: 20,
318 value: State { value: None },
319 },
320 Entry {
321 key: 30,
322 value: State { value: Some('c') },
323 },
324 Entry {
325 key: 40,
326 value: State { value: None },
327 },
328 Entry {
329 key: 50,
330 value: State { value: Some('d') },
331 },
332 ]
333 .cast(),
334 };
335 let result = merge(a, b);
336 assert_eq!(result.list.len(), 5);
337 assert_eq!(result.list[0].key, 10);
338 assert_eq!(result.list[0].value, State { value: Some('a') });
339 assert_eq!(result.list[1].key, 20);
340 assert_eq!(result.list[1].value, State { value: Some('b') });
341 assert_eq!(result.list[2].key, 30);
342 assert_eq!(result.list[2].value, State { value: Some('c') });
343 assert_eq!(result.list[3].key, 40);
344 assert_eq!(result.list[3].value, State { value: None });
345 assert_eq!(result.list[4].key, 50);
346 assert_eq!(result.list[4].value, State { value: Some('d') });
347 }
348
349 #[test]
350 #[wasm_bindgen_test]
351 fn test_merge_list() {
352 let result: RangeMap<i32, State<char>> = merge_list(default());
353 assert_eq!(result.list.len(), 0);
354
355 let result: RangeMap<i32, State<char>> = merge_list(
356 [
357 RangeMap {
358 list: [Entry {
359 key: 10,
360 value: State { value: Some('a') },
361 }]
362 .cast(),
363 },
364 RangeMap {
365 list: [
366 Entry {
367 key: 10,
368 value: State { value: None },
369 },
370 Entry {
371 key: 20,
372 value: State { value: Some('b') },
373 },
374 ]
375 .cast(),
376 },
377 RangeMap {
378 list: [
379 Entry {
380 key: 20,
381 value: State { value: None },
382 },
383 Entry {
384 key: 30,
385 value: State { value: Some('c') },
386 },
387 ]
388 .cast(),
389 },
390 ]
391 .cast(),
392 );
393 assert_eq!(result.list.len(), 3);
394 assert_eq!(result.list[0].key, 10);
395 assert_eq!(result.list[0].value, State { value: Some('a') });
396 assert_eq!(result.list[1].key, 20);
397 assert_eq!(result.list[1].value, State { value: Some('b') });
398 assert_eq!(result.list[2].key, 30);
399 assert_eq!(result.list[2].value, State { value: Some('c') });
400 }
401
402 #[test]
403 #[wasm_bindgen_test]
404 #[should_panic(expected = "state values should be the same")]
405 fn test_merge_panic() {
406 let a = RangeMap {
407 list: [Entry {
408 key: 10,
409 value: State { value: Some('a') },
410 }]
411 .cast(),
412 };
413 let b = RangeMap {
414 list: [Entry {
415 key: 20,
416 value: State { value: Some('b') },
417 }]
418 .cast(),
419 };
420 let _result = merge(a, b);
421 }
422
423 #[test]
424 #[wasm_bindgen_test]
425 fn test_from_range() {
426 let state = 'A';
427 let range = 'b'..='d';
428 let rm = from_range(range, state);
429 assert_eq!(rm.get('a'), &State { value: None });
430 assert_eq!(rm.get('b'), &State { value: Some('A') });
431 assert_eq!(rm.get('c'), &State { value: Some('A') });
432 assert_eq!(rm.get('d'), &State { value: Some('A') });
433 assert_eq!(rm.get('e'), &State { value: None });
434 }
435
436 #[test]
437 #[wasm_bindgen_test]
438 fn test_from_one() {
439 let state = 'A';
440 let rm = from_one('b', state);
441 assert_eq!(rm.get('a'), &State { value: None });
442 assert_eq!(rm.get('b'), &State { value: Some('A') });
443 }
444}