1use crate::{
2 segment_map_node::SegmentMapNode,
3 Segment,
4};
5
6#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
7pub struct SegmentMap<K, V> {
8 root: Option<SegmentMapNode<K, V>>,
9}
10
11impl<K, V> SegmentMap<K, V>
12where
13 K: PartialOrd
14{
15 pub fn new() -> SegmentMap<K, V> {
16 SegmentMap { root: None }
17 }
18
19 pub fn segments(&self) -> Segments<'_, K, V> {
20 Segments { inner: self.iter() }
21 }
22
23 pub fn values(&self) -> Values<'_, K, V> {
24 Values { inner: self.iter() }
25 }
26
27 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
28 ValuesMut { inner: self.iter_mut() }
29 }
30
31 pub fn iter(&self) -> Iter<'_, K, V> {
32 Iter {
33 current: self.root.as_ref(),
34 stack: Vec::new(),
35 }
36 }
37
38 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
39 IterMut {
40 current: self.root.as_mut(),
41 stack: Vec::new(),
42 }
43 }
44
45 pub fn span(&self) -> Option<Segment<&K>> {
46 self.root.as_ref().map(|root| root.span())
47 }
48
49 pub fn is_empty(&self) -> bool {
50 self.root.is_none()
51 }
52
53 pub fn clear(&mut self) {
54 self.root = None;
55 }
56
57 pub fn get(&self, key: &K) -> Option<&V> {
58 self.root.as_ref().and_then(|root| root.get(key))
59 }
60
61 pub fn get_entry(&self, key: &K) -> Option<(&Segment<K>, &V)> {
62 self.root.as_ref().and_then(|root| root.get_entry(key))
63 }
64
65 pub fn contains_key(&self, key: &K) -> bool {
66 self.get_entry(key).is_some()
67 }
68
69 pub fn insert(&mut self, segment: Segment<K>, value: V) {
70 if let Some(root) = self.root.as_mut() {
71 root.insert(segment, value);
72 } else {
73 self.root = Some(SegmentMapNode::new(segment, value, None, None));
74 }
75 }
76}
77
78impl<K, V> SegmentMap<K, V>
79where
80 K: Clone + PartialOrd,
81 V: Clone,
82{
83 pub fn remove(&mut self, segment: &Segment<K>) {
84 if let Some(root) = self.root.take() {
85 self.root = root.remove(segment);
86 }
87 }
88
89 pub fn update<F>(&mut self, segment: &Segment<K>, value: F)
90 where
91 F: Fn(Option<V>) -> Option<V> + Clone
92 {
93 if let Some(root) = self.root.take() {
94 self.root = root.update(segment, value);
95 } else if let Some(value) = value(None) {
96 self.insert(segment.clone(), value);
97 }
98 }
99
100 pub fn update_entry<F>(&mut self, segment: &Segment<K>, value: F)
101 where
102 F: Fn(&Segment<K>, Option<V>) -> Option<V> + Clone
103 {
104 if let Some(root) = self.root.take() {
105 self.root = root.update_entry(segment, value);
106 } else if let Some(value) = value(segment, None) {
107 self.insert(segment.clone(), value);
108 }
109 }
110}
111
112pub struct Segments<'a, K, V> {
113 inner: Iter<'a, K, V>
114}
115
116impl<'a, K, V> Iterator for Segments<'a, K, V> {
117 type Item = &'a Segment<K>;
118
119 fn next(&mut self) -> Option<&'a Segment<K>> {
120 self.inner.next().map(|(segment, _)| segment)
121 }
122}
123
124pub struct Values<'a, K, V> {
125 inner: Iter<'a, K, V>
126}
127
128impl<'a, K, V> Iterator for Values<'a, K, V> {
129 type Item = &'a V;
130
131 fn next(&mut self) -> Option<&'a V> {
132 self.inner.next().map(|(_, value)| value)
133 }
134}
135
136pub struct ValuesMut<'a, K, V> {
137 inner: IterMut<'a, K, V>
138}
139
140impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
141 type Item = &'a mut V;
142
143 fn next(&mut self) -> Option<&'a mut V> {
144 self.inner.next().map(|(_, value)| value)
145 }
146}
147
148pub struct Iter<'a, K, V> {
149 current: Option<&'a SegmentMapNode<K, V>>,
150 stack: Vec<(&'a Segment<K>, &'a V, Option<&'a SegmentMapNode<K, V>>)>,
151}
152
153impl<'a, K, V> Iterator for Iter<'a, K, V> {
154 type Item = (&'a Segment<K>, &'a V);
155
156 fn next(&mut self) -> Option<(&'a Segment<K>, &'a V)> {
157 while let Some(current) = self.current.take() {
158 self.stack.push((¤t.segment, ¤t.value, (*current.right).as_ref()));
159 self.current = (*current.left).as_ref();
160 }
161 if let Some((segment, value, right)) = self.stack.pop() {
162 self.current = right;
163 Some((segment, value))
164 } else { None }
165 }
166}
167
168pub struct IterMut<'a, K, V> {
169 current: Option<&'a mut SegmentMapNode<K, V>>,
170 stack: Vec<(&'a Segment<K>, &'a mut V, Option<&'a mut SegmentMapNode<K, V>>)>,
171}
172
173impl<'a, K, V> Iterator for IterMut<'a, K, V> {
174 type Item = (&'a Segment<K>, &'a mut V);
175
176 fn next(&mut self) -> Option<(&'a Segment<K>, &'a mut V)> {
177 while let Some(current) = self.current.take() {
178 self.stack.push((¤t.segment, &mut current.value, (*current.right).as_mut()));
179 self.current = (*current.left).as_mut();
180 }
181 if let Some((segment, value, right)) = self.stack.pop() {
182 self.current = right;
183 Some((segment, value))
184 } else { None }
185 }
186}
187
188impl<K, V> Extend<(Segment<K>, V)> for SegmentMap<K, V>
189where
190 K: Clone + PartialOrd,
191 V: Clone,
192{
193 fn extend<I>(&mut self, iter: I)
194 where
195 I: IntoIterator<Item = (Segment<K>, V)>
196 {
197 for (segment, value) in iter {
198 self.insert(segment, value);
199 }
200 }
201}
202
203impl<K, V> IntoIterator for SegmentMap<K, V> {
204 type Item = (Segment<K>, V);
205 type IntoIter = IntoIter<K, V>;
206
207 fn into_iter(self) -> IntoIter<K, V> {
208 IntoIter {
209 current: self.root,
210 stack: Vec::new(),
211 }
212 }
213}
214
215pub struct IntoIter<K, V> {
216 current: Option<SegmentMapNode<K, V>>,
217 stack: Vec<(Segment<K>, V, Option<SegmentMapNode<K, V>>)>,
218}
219
220impl<K, V> Iterator for IntoIter<K, V> {
221 type Item = (Segment<K>, V);
222
223 fn next(&mut self) -> Option<(Segment<K>, V)> {
224 while let Some(current) = self.current.take() {
225 self.stack.push((current.segment, current.value, *current.right));
226 self.current = *current.left;
227 }
228 if let Some((segment, value, right)) = self.stack.pop() {
229 self.current = right;
230 Some((segment, value))
231 } else { None }
232 }
233}
234
235#[macro_export]
236macro_rules! segment_map {
237 ($($x:expr => $y:expr),*) => {{
238 #[allow(unused_mut)]
239 let mut temp_segment_map = $crate::SegmentMap::new();
240 $(temp_segment_map.insert($x, $y);)*
241 temp_segment_map
242 }}
243}
244
245#[cfg(test)]
246mod tests {
247 use crate::{
248 Segment,
249 SegmentMap,
250 };
251
252 #[test]
253 fn test_insert_multiple_empty() {
254 let mut segment_map = SegmentMap::new();
255 segment_map.insert(Segment::new(0, 1), 0);
256 segment_map.insert(Segment::new(1, 1), 1);
257 assert!(std::panic::catch_unwind(move || segment_map.insert(Segment::new(1, 1), 2)).is_err());
258 }
259
260 #[test]
261 fn test_remove() {
262 let permutations = vec![(
263 format!("{}\n{}\n{}\n{}\n{}\n",
264 " [0----)",
265 " \\",
266 " [1----)",
267 " \\",
268 " [2----)"
269 ),
270 vec![0, 1, 2]
271 ), (
272 format!("{}\n{}\n{}\n{}\n{}\n",
273 " [0----)",
274 " \\",
275 " [2----)",
276 " /",
277 " [1----)"
278 ),
279 vec![0, 2, 1]
280 ), (
281 format!("{}\n{}\n{}\n",
282 " [1----)",
283 " / \\",
284 " [0----) [2----)",
285 ),
286 vec![1, 0, 2]
287 ), (
288 format!("{}\n{}\n{}\n{}\n{}\n",
289 " [2----)",
290 " /",
291 " [0----)",
292 " \\",
293 " [1----)"
294 ),
295 vec![2, 0, 1]
296 ), (
297 format!("{}\n{}\n{}\n{}\n{}\n",
298 " [2----)",
299 " /",
300 " [1----)",
301 " /",
302 " [0----)"
303 ),
304 vec![2, 1, 0]
305 )
306 ];
307 let cases = vec![(
308 format!("{}\n{}\n{}\n",
309 " [-----------------)",
310 " -> -------------------",
311 " [0----|1----|2----)"
312 ),
313 Segment::new(0, 18),
314 vec![
315 (Segment::new(0, 6), 0),
316 (Segment::new(6, 12), 1),
317 (Segment::new(12, 18), 2)
318 ],
319 vec![],
320 ), (
321 format!("{}\n{}\n{}\n",
322 " [--------------)---",
323 " -> ---------------[2-)",
324 " [0----|1----|2----)"
325 ),
326 Segment::new(0, 15),
327 vec![
328 (Segment::new(0, 6), 0),
329 (Segment::new(6, 12), 1),
330 (Segment::new(12, 18), 2)
331 ],
332 vec![
333 (Segment::new(15, 18), 2)
334 ],
335 ), (
336 format!("{}\n{}\n{}\n",
337 " [-----------)------",
338 " -> ------------[2----)",
339 " [0----|1----|2----)"
340 ),
341 Segment::new(0, 12),
342 vec![
343 (Segment::new(0, 6), 0),
344 (Segment::new(6, 12), 1),
345 (Segment::new(12, 18), 2)
346 ],
347 vec![
348 (Segment::new(12, 18), 2)
349 ],
350 ), (
351 format!("{}\n{}\n{}\n",
352 " [--------)---------",
353 " -> ---------[1-|2----)",
354 " [0----|1----|2----)"
355 ),
356 Segment::new(0, 9),
357 vec![
358 (Segment::new(0, 6), 0),
359 (Segment::new(6, 12), 1),
360 (Segment::new(12, 18), 2)
361 ],
362 vec![
363 (Segment::new(9, 12), 1),
364 (Segment::new(12, 18), 2)
365 ],
366 ), (
367 format!("{}\n{}\n{}\n",
368 " [-----)------------",
369 " -> ------[1----|2----)",
370 " [0----|1----|2----)"
371 ),
372 Segment::new(0, 6),
373 vec![
374 (Segment::new(0, 6), 0),
375 (Segment::new(6, 12), 1),
376 (Segment::new(12, 18), 2)
377 ],
378 vec![
379 (Segment::new(6, 12), 1),
380 (Segment::new(12, 18), 2)
381 ],
382 ), (
383 format!("{}\n{}\n{}\n",
384 " [--)---------------",
385 " -> ---[0-|1----|2----)",
386 " [0----|1----|2----)"
387 ),
388 Segment::new(0, 3),
389 vec![
390 (Segment::new(0, 6), 0),
391 (Segment::new(6, 12), 1),
392 (Segment::new(12, 18), 2)
393 ],
394 vec![
395 (Segment::new(3, 6), 0),
396 (Segment::new(6, 12), 1),
397 (Segment::new(12, 18), 2)
398 ],
399 ), (
400 format!("{}\n{}\n{}\n",
401 " |------------------",
402 " -> [0----|1----|2----)",
403 " [0----|1----|2----)"
404 ),
405 Segment::new(0, 0),
406 vec![
407 (Segment::new(0, 6), 0),
408 (Segment::new(6, 12), 1),
409 (Segment::new(12, 18), 2)
410 ],
411 vec![
412 (Segment::new(0, 6), 0),
413 (Segment::new(6, 12), 1),
414 (Segment::new(12, 18), 2)
415 ],
416 ), (
417 format!("{}\n{}\n{}\n",
418 " ---[--------------)",
419 " -> [0-)---------------",
420 " [0----|1----|2----)"
421 ),
422 Segment::new(3, 18),
423 vec![
424 (Segment::new(0, 6), 0),
425 (Segment::new(6, 12), 1),
426 (Segment::new(12, 18), 2)
427 ],
428 vec![
429 (Segment::new(0, 3), 0)
430 ],
431 ), (
432 format!("{}\n{}\n{}\n",
433 " ---[-----------)---",
434 " -> [0-)-----------[2-)",
435 " [0----|1----|2----)"
436 ),
437 Segment::new(3, 15),
438 vec![
439 (Segment::new(0, 6), 0),
440 (Segment::new(6, 12), 1),
441 (Segment::new(12, 18), 2)
442 ],
443 vec![
444 (Segment::new(0, 3), 0),
445 (Segment::new(15, 18), 2)
446 ],
447 ), (
448 format!("{}\n{}\n{}\n",
449 " ---[--------)------",
450 " -> [0-)--------[2----)",
451 " [0----|1----|2----)"
452 ),
453 Segment::new(3, 12),
454 vec![
455 (Segment::new(0, 6), 0),
456 (Segment::new(6, 12), 1),
457 (Segment::new(12, 18), 2)
458 ],
459 vec![
460 (Segment::new(0, 3), 0),
461 (Segment::new(12, 18), 2)
462 ],
463 ), (
464 format!("{}\n{}\n{}\n",
465 " ---[-----)---------",
466 " -> [0-)-----[1-|2----)",
467 " [0----|1----|2----)"
468 ),
469 Segment::new(3, 9),
470 vec![
471 (Segment::new(0, 6), 0),
472 (Segment::new(6, 12), 1),
473 (Segment::new(12, 18), 2)
474 ],
475 vec![
476 (Segment::new(0, 3), 0),
477 (Segment::new(9, 12), 1),
478 (Segment::new(12, 18), 2)
479 ],
480 ), (
481 format!("{}\n{}\n{}\n",
482 " ---[--)------------",
483 " -> [0-)--[1----|2----)",
484 " [0----|1----|2----)"
485 ),
486 Segment::new(3, 6),
487 vec![
488 (Segment::new(0, 6), 0),
489 (Segment::new(6, 12), 1),
490 (Segment::new(12, 18), 2)
491 ],
492 vec![
493 (Segment::new(0, 3), 0),
494 (Segment::new(6, 12), 1),
495 (Segment::new(12, 18), 2)
496 ],
497 ), (
498 format!("{}\n{}\n{}\n",
499 " --[-)--------------",
500 " -> [0)-[0|1----|2----)",
501 " [0----|1----|2----)"
502 ),
503 Segment::new(2, 4),
504 vec![
505 (Segment::new(0, 6), 0),
506 (Segment::new(6, 12), 1),
507 (Segment::new(12, 18), 2)
508 ],
509 vec![
510 (Segment::new(0, 2), 0),
511 (Segment::new(4, 6), 0),
512 (Segment::new(6, 12), 1),
513 (Segment::new(12, 18), 2)
514 ],
515 ), (
516 format!("{}\n{}\n{}\n",
517 " ---|---------------",
518 " -> [0-|0-|1----|2----)",
519 " [0----|1----|2----)"
520 ),
521 Segment::new(3, 3),
522 vec![
523 (Segment::new(0, 6), 0),
524 (Segment::new(6, 12), 1),
525 (Segment::new(12, 18), 2)
526 ],
527 vec![
528 (Segment::new(0, 3), 0),
529 (Segment::new(3, 6), 0),
530 (Segment::new(6, 12), 1),
531 (Segment::new(12, 18), 2)
532 ],
533 ), (
534 format!("{}\n{}\n{}\n",
535 " ------[-----------)",
536 " -> [0----)------------",
537 " [0----|1----|2----)"
538 ),
539 Segment::new(6, 18),
540 vec![
541 (Segment::new(0, 6), 0),
542 (Segment::new(6, 12), 1),
543 (Segment::new(12, 18), 2)
544 ],
545 vec![
546 (Segment::new(0, 6), 0)
547 ],
548 ), (
549 format!("{}\n{}\n{}\n",
550 " ------[--------)---",
551 " -> [0----)--------[2-)",
552 " [0----|1----|2----)"
553 ),
554 Segment::new(6, 15),
555 vec![
556 (Segment::new(0, 6), 0),
557 (Segment::new(6, 12), 1),
558 (Segment::new(12, 18), 2)
559 ],
560 vec![
561 (Segment::new(0, 6), 0),
562 (Segment::new(15, 18), 2)
563 ],
564 ), (
565 format!("{}\n{}\n{}\n",
566 " ------[-----)------",
567 " -> [0----)-----[2----)",
568 " [0----|1----|2----)"
569 ),
570 Segment::new(6, 12),
571 vec![
572 (Segment::new(0, 6), 0),
573 (Segment::new(6, 12), 1),
574 (Segment::new(12, 18), 2)
575 ],
576 vec![
577 (Segment::new(0, 6), 0),
578 (Segment::new(12, 18), 2)
579 ],
580 ), (
581 format!("{}\n{}\n{}\n",
582 " ------[--)---------",
583 " -> [0----)--[1-|2----)",
584 " [0----|1----|2----)"
585 ),
586 Segment::new(6, 9),
587 vec![
588 (Segment::new(0, 6), 0),
589 (Segment::new(6, 12), 1),
590 (Segment::new(12, 18), 2)
591 ],
592 vec![
593 (Segment::new(0, 6), 0),
594 (Segment::new(9, 12), 1),
595 (Segment::new(12, 18), 2)
596 ],
597 ), (
598 format!("{}\n{}\n{}\n",
599 " ------|------------",
600 " -> [0----|1----|2----)",
601 " [0----|1----|2----)"
602 ),
603 Segment::new(6, 6),
604 vec![
605 (Segment::new(0, 6), 0),
606 (Segment::new(6, 12), 1),
607 (Segment::new(12, 18), 2)
608 ],
609 vec![
610 (Segment::new(0, 6), 0),
611 (Segment::new(6, 12), 1),
612 (Segment::new(12, 18), 2)
613 ],
614 ), (
615 format!("{}\n{}\n{}\n",
616 " |------------------",
617 " -> [1----|2----)------",
618 " [1----|2----)------"
619 ),
620 Segment::new(0, 0),
621 vec![
622 (Segment::new(0, 0), 0),
623 (Segment::new(0, 6), 1),
624 (Segment::new(6, 12), 2)
625 ],
626 vec![
627 (Segment::new(0, 6), 1),
628 (Segment::new(6, 12), 2)
629 ],
630 )
631
632 ];
633 for (case_description, remove_segment, insert_segments, expected_segments) in cases {
634 for (permutation_description, indices) in &permutations {
635 let mut segment_map = SegmentMap::new();
636 for &index in indices {
637 let (insert_segment, insert_value) = insert_segments[index];
638 segment_map.insert(insert_segment, insert_value);
639 }
640 segment_map.remove(&remove_segment);
641 assert_eq!(expected_segments, segment_map.into_iter().collect::<Vec<_>>(), "\npermutation:\n\n{}\ncase:\n\n{}\n", permutation_description, case_description);
642 }
643 }
644 }
645
646 #[test]
647 fn test_update() {
648 let permutations = vec![
649 vec![
650 ], vec![(
651 format!("{}\n",
652 " [0----)"
653 ),
654 vec![0]
655 )
656 ], vec![(
657 format!("{}\n{}\n{}\n",
658 " [0----)",
659 " \\",
660 " [1----)"
661 ),
662 vec![0, 1]
663 ), (
664 format!("{}\n{}\n{}\n",
665 " [1----)",
666 " /",
667 " [0----)"
668 ),
669 vec![1, 0]
670 )
671 ], vec![(
672 format!("{}\n{}\n{}\n{}\n{}\n",
673 " [0----)",
674 " \\",
675 " [1----)",
676 " \\",
677 " [2----)"
678 ),
679 vec![0, 1, 2]
680 ), (
681 format!("{}\n{}\n{}\n{}\n{}\n",
682 " [0----)",
683 " \\",
684 " [2----)",
685 " /",
686 " [1----)"
687 ),
688 vec![0, 2, 1]
689 ), (
690 format!("{}\n{}\n{}\n",
691 " [1----)",
692 " / \\",
693 " [0----) [2----)",
694 ),
695 vec![1, 0, 2]
696 ), (
697 format!("{}\n{}\n{}\n{}\n{}\n",
698 " [2----)",
699 " /",
700 " [0----)",
701 " \\",
702 " [1----)"
703 ),
704 vec![2, 0, 1]
705 ), (
706 format!("{}\n{}\n{}\n{}\n{}\n",
707 " [2----)",
708 " /",
709 " [1----)",
710 " /",
711 " [0----)"
712 ),
713 vec![2, 1, 0]
714 )
715 ]
716 ];
717 let cases = vec![(
718 format!("{}\n{}\n{}\n",
719 " [3----------------)",
720 " -> [3----|3----|3----)",
721 " [0----|1----|2----)"
722 ),
723 (Segment::new(0, 18), 3),
724 vec![
725 (Segment::new(0, 6), 0),
726 (Segment::new(6, 12), 1),
727 (Segment::new(12, 18), 2)
728 ],
729 vec![
730 (Segment::new(0, 6), 3),
731 (Segment::new(6, 12), 3),
732 (Segment::new(12, 18), 3)
733 ],
734 ), (
735 format!("{}\n{}\n{}\n",
736 " [3-------------)---",
737 " -> [3----|3----|3-|2-)",
738 " [0----|1----|2----)"
739 ),
740 (Segment::new(0, 15), 3),
741 vec![
742 (Segment::new(0, 6), 0),
743 (Segment::new(6, 12), 1),
744 (Segment::new(12, 18), 2)
745 ],
746 vec![
747 (Segment::new(0, 6), 3),
748 (Segment::new(6, 12), 3),
749 (Segment::new(12, 15), 3),
750 (Segment::new(15, 18), 2)
751 ],
752 ), (
753 format!("{}\n{}\n{}\n",
754 " [3----------)------",
755 " -> [3----|3----|2----)",
756 " [0----|1----|2----)"
757 ),
758 (Segment::new(0, 12), 3),
759 vec![
760 (Segment::new(0, 6), 0),
761 (Segment::new(6, 12), 1),
762 (Segment::new(12, 18), 2)
763 ],
764 vec![
765 (Segment::new(0, 6), 3),
766 (Segment::new(6, 12), 3),
767 (Segment::new(12, 18), 2)
768 ],
769 ), (
770 format!("{}\n{}\n{}\n",
771 " [3-------)---------",
772 " -> [3----|3-|1-|2----)",
773 " [0----|1----|2----)"
774 ),
775 (Segment::new(0, 9), 3),
776 vec![
777 (Segment::new(0, 6), 0),
778 (Segment::new(6, 12), 1),
779 (Segment::new(12, 18), 2)
780 ],
781 vec![
782 (Segment::new(0, 6), 3),
783 (Segment::new(6, 9), 3),
784 (Segment::new(9, 12), 1),
785 (Segment::new(12, 18), 2)
786 ],
787 ), (
788 format!("{}\n{}\n{}\n",
789 " [3----)------------",
790 " -> [3----|1----|2----)",
791 " [0----|1----|2----)"
792 ),
793 (Segment::new(0, 6), 3),
794 vec![
795 (Segment::new(0, 6), 0),
796 (Segment::new(6, 12), 1),
797 (Segment::new(12, 18), 2)
798 ],
799 vec![
800 (Segment::new(0, 6), 3),
801 (Segment::new(6, 12), 1),
802 (Segment::new(12, 18), 2)
803 ],
804 ), (
805 format!("{}\n{}\n{}\n",
806 " [3-)---------------",
807 " -> [3-|0-|1----|2----)",
808 " [0----|1----|2----)"
809 ),
810 (Segment::new(0, 3), 3),
811 vec![
812 (Segment::new(0, 6), 0),
813 (Segment::new(6, 12), 1),
814 (Segment::new(12, 18), 2)
815 ],
816 vec![
817 (Segment::new(0, 3), 3),
818 (Segment::new(3, 6), 0),
819 (Segment::new(6, 12), 1),
820 (Segment::new(12, 18), 2)
821 ],
822 ), (
823 format!("{}\n{}\n{}\n",
824 " |------------------",
825 " -> [0----|1----|2----)",
826 " [0----|1----|2----)"
827 ),
828 (Segment::new(0, 0), 3),
829 vec![
830 (Segment::new(0, 6), 0),
831 (Segment::new(6, 12), 1),
832 (Segment::new(12, 18), 2)
833 ],
834 vec![
835 (Segment::new(0, 0), 3),
836 (Segment::new(0, 6), 0),
837 (Segment::new(6, 12), 1),
838 (Segment::new(12, 18), 2)
839 ],
840 ), (
841 format!("{}\n{}\n{}\n",
842 " ---[3-------------)",
843 " -> [0-|3-|3----|3----)",
844 " [0----|1----|2----)"
845 ),
846 (Segment::new(3, 18), 3),
847 vec![
848 (Segment::new(0, 6), 0),
849 (Segment::new(6, 12), 1),
850 (Segment::new(12, 18), 2)
851 ],
852 vec![
853 (Segment::new(0, 3), 0),
854 (Segment::new(3, 6), 3),
855 (Segment::new(6, 12), 3),
856 (Segment::new(12, 18), 3)
857 ],
858 ), (
859 format!("{}\n{}\n{}\n",
860 " ---[3----------)---",
861 " -> [0-|3-|3----|3-|2-)",
862 " [0----|1----|2----)"
863 ),
864 (Segment::new(3, 15), 3),
865 vec![
866 (Segment::new(0, 6), 0),
867 (Segment::new(6, 12), 1),
868 (Segment::new(12, 18), 2)
869 ],
870 vec![
871 (Segment::new(0, 3), 0),
872 (Segment::new(3, 6), 3),
873 (Segment::new(6, 12), 3),
874 (Segment::new(12, 15), 3),
875 (Segment::new(15, 18), 2)
876 ],
877 ), (
878 format!("{}\n{}\n{}\n",
879 " ---[3-------)------",
880 " -> [0-|3-|3----|2----)",
881 " [0----|1----|2----)"
882 ),
883 (Segment::new(3, 12), 3),
884 vec![
885 (Segment::new(0, 6), 0),
886 (Segment::new(6, 12), 1),
887 (Segment::new(12, 18), 2)
888 ],
889 vec![
890 (Segment::new(0, 3), 0),
891 (Segment::new(3, 6), 3),
892 (Segment::new(6, 12), 3),
893 (Segment::new(12, 18), 2)
894 ],
895 ), (
896 format!("{}\n{}\n{}\n",
897 " ---[3----)---------",
898 " -> [0-|3-|3-|1-|2----)",
899 " [0----|1----|2----)"
900 ),
901 (Segment::new(3, 9), 3),
902 vec![
903 (Segment::new(0, 6), 0),
904 (Segment::new(6, 12), 1),
905 (Segment::new(12, 18), 2)
906 ],
907 vec![
908 (Segment::new(0, 3), 0),
909 (Segment::new(3, 6), 3),
910 (Segment::new(6, 9), 3),
911 (Segment::new(9, 12), 1),
912 (Segment::new(12, 18), 2)
913 ],
914 ), (
915 format!("{}\n{}\n{}\n",
916 " ---[3-)------------",
917 " -> [0-|3-|1----|2----)",
918 " [0----|1----|2----)"
919 ),
920 (Segment::new(3, 6), 3),
921 vec![
922 (Segment::new(0, 6), 0),
923 (Segment::new(6, 12), 1),
924 (Segment::new(12, 18), 2)
925 ],
926 vec![
927 (Segment::new(0, 3), 0),
928 (Segment::new(3, 6), 3),
929 (Segment::new(6, 12), 1),
930 (Segment::new(12, 18), 2)
931 ],
932 ), (
933 format!("{}\n{}\n{}\n",
934 " --[3)--------------",
935 " -> [0|3|0|1----|2----)",
936 " [0----|1----|2----)"
937 ),
938 (Segment::new(2, 4), 3),
939 vec![
940 (Segment::new(0, 6), 0),
941 (Segment::new(6, 12), 1),
942 (Segment::new(12, 18), 2)
943 ],
944 vec![
945 (Segment::new(0, 2), 0),
946 (Segment::new(2, 4), 3),
947 (Segment::new(4, 6), 0),
948 (Segment::new(6, 12), 1),
949 (Segment::new(12, 18), 2)
950 ],
951 ), (
952 format!("{}\n{}\n{}\n",
953 " ---|---------------",
954 " -> [0-|0-|1----|2----)",
955 " [0----|1----|2----)"
956 ),
957 (Segment::new(3, 3), 3),
958 vec![
959 (Segment::new(0, 6), 0),
960 (Segment::new(6, 12), 1),
961 (Segment::new(12, 18), 2)
962 ],
963 vec![
964 (Segment::new(0, 3), 0),
965 (Segment::new(3, 3), 3),
966 (Segment::new(3, 6), 0),
967 (Segment::new(6, 12), 1),
968 (Segment::new(12, 18), 2)
969 ],
970 ), (
971 format!("{}\n{}\n{}\n",
972 " ------[3----------)",
973 " -> [0----|3----|3----)",
974 " [0----|1----|2----)"
975 ),
976 (Segment::new(6, 18), 3),
977 vec![
978 (Segment::new(0, 6), 0),
979 (Segment::new(6, 12), 1),
980 (Segment::new(12, 18), 2)
981 ],
982 vec![
983 (Segment::new(0, 6), 0),
984 (Segment::new(6, 12), 3),
985 (Segment::new(12, 18), 3)
986 ],
987 ), (
988 format!("{}\n{}\n{}\n",
989 " ------[3-------)---",
990 " -> [0----|3----|3-|2-)",
991 " [0----|1----|2----)"
992 ),
993 (Segment::new(6, 15), 3),
994 vec![
995 (Segment::new(0, 6), 0),
996 (Segment::new(6, 12), 1),
997 (Segment::new(12, 18), 2)
998 ],
999 vec![
1000 (Segment::new(0, 6), 0),
1001 (Segment::new(6, 12), 3),
1002 (Segment::new(12, 15), 3),
1003 (Segment::new(15, 18), 2)
1004 ],
1005 ), (
1006 format!("{}\n{}\n{}\n",
1007 " ------[3----)------",
1008 " -> [0----|3----|2----)",
1009 " [0----|1----|2----)"
1010 ),
1011 (Segment::new(6, 12), 3),
1012 vec![
1013 (Segment::new(0, 6), 0),
1014 (Segment::new(6, 12), 1),
1015 (Segment::new(12, 18), 2)
1016 ],
1017 vec![
1018 (Segment::new(0, 6), 0),
1019 (Segment::new(6, 12), 3),
1020 (Segment::new(12, 18), 2)
1021 ],
1022 ), (
1023 format!("{}\n{}\n{}\n",
1024 " ------[3-)---------",
1025 " -> [0----|3-|1-|2----)",
1026 " [0----|1----|2----)"
1027 ),
1028 (Segment::new(6, 9), 3),
1029 vec![
1030 (Segment::new(0, 6), 0),
1031 (Segment::new(6, 12), 1),
1032 (Segment::new(12, 18), 2)
1033 ],
1034 vec![
1035 (Segment::new(0, 6), 0),
1036 (Segment::new(6, 9), 3),
1037 (Segment::new(9, 12), 1),
1038 (Segment::new(12, 18), 2)
1039 ],
1040 ), (
1041 format!("{}\n{}\n{}\n",
1042 " ------|------------",
1043 " -> [0----|1----|2----)",
1044 " [0----|1----|2----)"
1045 ),
1046 (Segment::new(6, 6), 3),
1047 vec![
1048 (Segment::new(0, 6), 0),
1049 (Segment::new(6, 12), 1),
1050 (Segment::new(12, 18), 2)
1051 ],
1052 vec![
1053 (Segment::new(0, 6), 0),
1054 (Segment::new(6, 6), 3),
1055 (Segment::new(6, 12), 1),
1056 (Segment::new(12, 18), 2)
1057 ],
1058 ), (
1059 format!("{}\n{}\n{}\n",
1060 " [3----------------)",
1061 " -> [3----|3----|3----)",
1062 " ------[1----|2----)"
1063 ),
1064 (Segment::new(0, 18), 3),
1065 vec![
1066 (Segment::new(6, 12), 1),
1067 (Segment::new(12, 18), 2)
1068 ],
1069 vec![
1070 (Segment::new(0, 6), 3),
1071 (Segment::new(6, 12), 3),
1072 (Segment::new(12, 18), 3)
1073 ],
1074 ), (
1075 format!("{}\n{}\n{}\n",
1076 " [3-------------)---",
1077 " -> [3----|3----|3-|2-)",
1078 " ------[1----|2----)"
1079 ),
1080 (Segment::new(0, 15), 3),
1081 vec![
1082 (Segment::new(6, 12), 1),
1083 (Segment::new(12, 18), 2)
1084 ],
1085 vec![
1086 (Segment::new(0, 6), 3),
1087 (Segment::new(6, 12), 3),
1088 (Segment::new(12, 15), 3),
1089 (Segment::new(15, 18), 2)
1090 ],
1091 ), (
1092 format!("{}\n{}\n{}\n",
1093 " [3----------)------",
1094 " -> [3----|3----|2----)",
1095 " ------[1----|2----)"
1096 ),
1097 (Segment::new(0, 12), 3),
1098 vec![
1099 (Segment::new(6, 12), 1),
1100 (Segment::new(12, 18), 2)
1101 ],
1102 vec![
1103 (Segment::new(0, 6), 3),
1104 (Segment::new(6, 12), 3),
1105 (Segment::new(12, 18), 2)
1106 ],
1107 ), (
1108 format!("{}\n{}\n{}\n",
1109 " [3-------)---------",
1110 " -> [3----|3-|1-|2----)",
1111 " ------[1----|2----)"
1112 ),
1113 (Segment::new(0, 9), 3),
1114 vec![
1115 (Segment::new(6, 12), 1),
1116 (Segment::new(12, 18), 2)
1117 ],
1118 vec![
1119 (Segment::new(0, 6), 3),
1120 (Segment::new(6, 9), 3),
1121 (Segment::new(9, 12), 1),
1122 (Segment::new(12, 18), 2)
1123 ],
1124 ), (
1125 format!("{}\n{}\n{}\n",
1126 " [3----)------------",
1127 " -> [3----|1----|2----)",
1128 " ------[1----|2----)"
1129 ),
1130 (Segment::new(0, 6), 3),
1131 vec![
1132 (Segment::new(6, 12), 1),
1133 (Segment::new(12, 18), 2)
1134 ],
1135 vec![
1136 (Segment::new(0, 6), 3),
1137 (Segment::new(6, 12), 1),
1138 (Segment::new(12, 18), 2)
1139 ],
1140 ), (
1141 format!("{}\n{}\n{}\n",
1142 " [3-)---------------",
1143 " -> [3-)--[1----|2----)",
1144 " ------[1----|2----)"
1145 ),
1146 (Segment::new(0, 3), 3),
1147 vec![
1148 (Segment::new(6, 12), 1),
1149 (Segment::new(12, 18), 2)
1150 ],
1151 vec![
1152 (Segment::new(0, 3), 3),
1153 (Segment::new(6, 12), 1),
1154 (Segment::new(12, 18), 2)
1155 ],
1156 ), (
1157 format!("{}\n{}\n{}\n",
1158 " |------------------",
1159 " -> |-----[1----|2----)",
1160 " ------[1----|2----)"
1161 ),
1162 (Segment::new(0, 0), 3),
1163 vec![
1164 (Segment::new(6, 12), 1),
1165 (Segment::new(12, 18), 2)
1166 ],
1167 vec![
1168 (Segment::new(0, 0), 3),
1169 (Segment::new(6, 12), 1),
1170 (Segment::new(12, 18), 2)
1171 ],
1172 ), (
1173 format!("{}\n{}\n{}\n",
1174 " [3----------------)",
1175 " -> [3----|3----|3----)",
1176 " [0----)-----[2----)"
1177 ),
1178 (Segment::new(0, 18), 3),
1179 vec![
1180 (Segment::new(0, 6), 0),
1181 (Segment::new(12, 18), 2)
1182 ],
1183 vec![
1184 (Segment::new(0, 6), 3),
1185 (Segment::new(6, 12), 3),
1186 (Segment::new(12, 18), 3)
1187 ],
1188 ), (
1189 format!("{}\n{}\n{}\n",
1190 " [3-------------)---",
1191 " -> [3----|3----|3-|2-)",
1192 " [0----)-----[2----)"
1193 ),
1194 (Segment::new(0, 15), 3),
1195 vec![
1196 (Segment::new(0, 6), 0),
1197 (Segment::new(12, 18), 2)
1198 ],
1199 vec![
1200 (Segment::new(0, 6), 3),
1201 (Segment::new(6, 12), 3),
1202 (Segment::new(12, 15), 3),
1203 (Segment::new(15, 18), 2)
1204 ],
1205 ), (
1206 format!("{}\n{}\n{}\n",
1207 " [3----------)------",
1208 " -> [3----|3----|2----)",
1209 " [0----)-----[2----)"
1210 ),
1211 (Segment::new(0, 12), 3),
1212 vec![
1213 (Segment::new(0, 6), 0),
1214 (Segment::new(12, 18), 2)
1215 ],
1216 vec![
1217 (Segment::new(0, 6), 3),
1218 (Segment::new(6, 12), 3),
1219 (Segment::new(12, 18), 2)
1220 ],
1221 ), (
1222 format!("{}\n{}\n{}\n",
1223 " [3-------)---------",
1224 " -> [3----|3-)--[2----)",
1225 " [0----)-----[2----)"
1226 ),
1227 (Segment::new(0, 9), 3),
1228 vec![
1229 (Segment::new(0, 6), 0),
1230 (Segment::new(12, 18), 2)
1231 ],
1232 vec![
1233 (Segment::new(0, 6), 3),
1234 (Segment::new(6, 9), 3),
1235 (Segment::new(12, 18), 2)
1236 ],
1237 ), (
1238 format!("{}\n{}\n{}\n",
1239 " ---[3-------------)",
1240 " -> [0-|3-|3----|3----)",
1241 " [0----)-----[2----)"
1242 ),
1243 (Segment::new(3, 18), 3),
1244 vec![
1245 (Segment::new(0, 6), 0),
1246 (Segment::new(12, 18), 2)
1247 ],
1248 vec![
1249 (Segment::new(0, 3), 0),
1250 (Segment::new(3, 6), 3),
1251 (Segment::new(6, 12), 3),
1252 (Segment::new(12, 18), 3)
1253 ],
1254 ), (
1255 format!("{}\n{}\n{}\n",
1256 " ---[3----------)---",
1257 " -> [0-|3-|3----|3-|2-)",
1258 " [0----)-----[2----)"
1259 ),
1260 (Segment::new(3, 15), 3),
1261 vec![
1262 (Segment::new(0, 6), 0),
1263 (Segment::new(12, 18), 2)
1264 ],
1265 vec![
1266 (Segment::new(0, 3), 0),
1267 (Segment::new(3, 6), 3),
1268 (Segment::new(6, 12), 3),
1269 (Segment::new(12, 15), 3),
1270 (Segment::new(15, 18), 2)
1271 ],
1272 ), (
1273 format!("{}\n{}\n{}\n",
1274 " ---[3-------)------",
1275 " -> [0-|3-|3----|2----)",
1276 " [0----)-----[2----)"
1277 ),
1278 (Segment::new(3, 12), 3),
1279 vec![
1280 (Segment::new(0, 6), 0),
1281 (Segment::new(12, 18), 2)
1282 ],
1283 vec![
1284 (Segment::new(0, 3), 0),
1285 (Segment::new(3, 6), 3),
1286 (Segment::new(6, 12), 3),
1287 (Segment::new(12, 18), 2)
1288 ],
1289 ), (
1290 format!("{}\n{}\n{}\n",
1291 " ---[3----)---------",
1292 " -> [0-|3-|3-)--[2----)",
1293 " [0----)-----[2----)"
1294 ),
1295 (Segment::new(3, 9), 3),
1296 vec![
1297 (Segment::new(0, 6), 0),
1298 (Segment::new(12, 18), 2)
1299 ],
1300 vec![
1301 (Segment::new(0, 3), 0),
1302 (Segment::new(3, 6), 3),
1303 (Segment::new(6, 9), 3),
1304 (Segment::new(12, 18), 2)
1305 ],
1306 ), (
1307 format!("{}\n{}\n{}\n",
1308 " [3----------------)",
1309 " -> [3----|3----|3----)",
1310 " [0----|1----)------"
1311 ),
1312 (Segment::new(0, 18), 3),
1313 vec![
1314 (Segment::new(0, 6), 0),
1315 (Segment::new(6, 12), 1)
1316 ],
1317 vec![
1318 (Segment::new(0, 6), 3),
1319 (Segment::new(6, 12), 3),
1320 (Segment::new(12, 18), 3)
1321 ],
1322 ), (
1323 format!("{}\n{}\n{}\n",
1324 " [3-------------)---",
1325 " -> [3----|3----|3-)---",
1326 " [0----|1----)------"
1327 ),
1328 (Segment::new(0, 15), 3),
1329 vec![
1330 (Segment::new(0, 6), 0),
1331 (Segment::new(6, 12), 1)
1332 ],
1333 vec![
1334 (Segment::new(0, 6), 3),
1335 (Segment::new(6, 12), 3),
1336 (Segment::new(12, 15), 3)
1337 ],
1338 ), (
1339 format!("{}\n{}\n{}\n",
1340 " ---[3-------------)",
1341 " -> [0-|3-|3----|3----)",
1342 " [0----|1----)------"
1343 ),
1344 (Segment::new(3, 18), 3),
1345 vec![
1346 (Segment::new(0, 6), 0),
1347 (Segment::new(6, 12), 1)
1348 ],
1349 vec![
1350 (Segment::new(0, 3), 0),
1351 (Segment::new(3, 6), 3),
1352 (Segment::new(6, 12), 3),
1353 (Segment::new(12, 18), 3)
1354 ],
1355 ), (
1356 format!("{}\n{}\n{}\n",
1357 " [3----------------)",
1358 " -> [3----|3----|3----)",
1359 " ------[1----)------"
1360 ),
1361 (Segment::new(0, 18), 3),
1362 vec![
1363 (Segment::new(6, 12), 1)
1364 ],
1365 vec![
1366 (Segment::new(0, 6), 3),
1367 (Segment::new(6, 12), 3),
1368 (Segment::new(12, 18), 3)
1369 ],
1370 ), (
1371 format!("{}\n{}\n{}\n",
1372 " |------------------",
1373 " -> [1----|2----)------",
1374 " [1----|2----)------"
1375 ),
1376 (Segment::new(0, 0), 3),
1377 vec![
1378 (Segment::new(0, 0), 0),
1379 (Segment::new(0, 6), 1),
1380 (Segment::new(6, 12), 2)
1381 ],
1382 vec![
1383 (Segment::new(0, 0), 3),
1384 (Segment::new(0, 6), 1),
1385 (Segment::new(6, 12), 2)
1386 ],
1387 )
1388 ];
1389 for (case_description, update_segment, insert_segments, expected_segments) in cases {
1390 for (permutation_description, indices) in &permutations[insert_segments.len()] {
1391 let mut segment_map = SegmentMap::new();
1392 for &index in indices {
1393 let (insert_segment, insert_value) = insert_segments[index];
1394 segment_map.insert(insert_segment, insert_value);
1395 }
1396 let (update_segment, update_value) = update_segment;
1397 segment_map.update(&update_segment, |_| Some(update_value));
1398 assert_eq!(expected_segments, segment_map.into_iter().collect::<Vec<_>>(), "\npermutation:\n\n{}\ncase:\n\n{}\n", permutation_description, case_description);
1399 }
1400 }
1401 }
1402
1403 #[test]
1404 fn test_update_remove() {
1405 let permutations = vec![
1406 vec![
1407 ], vec![(
1408 format!("{}\n",
1409 " [0----)"
1410 ),
1411 vec![0]
1412 )
1413 ], vec![(
1414 format!("{}\n{}\n{}\n",
1415 " [0----)",
1416 " \\",
1417 " [1----)"
1418 ),
1419 vec![0, 1]
1420 ), (
1421 format!("{}\n{}\n{}\n",
1422 " [1----)",
1423 " /",
1424 " [0----)"
1425 ),
1426 vec![1, 0]
1427 )
1428 ], vec![(
1429 format!("{}\n{}\n{}\n{}\n{}\n",
1430 " [0----)",
1431 " \\",
1432 " [1----)",
1433 " \\",
1434 " [2----)"
1435 ),
1436 vec![0, 1, 2]
1437 ), (
1438 format!("{}\n{}\n{}\n{}\n{}\n",
1439 " [0----)",
1440 " \\",
1441 " [2----)",
1442 " /",
1443 " [1----)"
1444 ),
1445 vec![0, 2, 1]
1446 ), (
1447 format!("{}\n{}\n{}\n",
1448 " [1----)",
1449 " / \\",
1450 " [0----) [2----)",
1451 ),
1452 vec![1, 0, 2]
1453 ), (
1454 format!("{}\n{}\n{}\n{}\n{}\n",
1455 " [2----)",
1456 " /",
1457 " [0----)",
1458 " \\",
1459 " [1----)"
1460 ),
1461 vec![2, 0, 1]
1462 ), (
1463 format!("{}\n{}\n{}\n{}\n{}\n",
1464 " [2----)",
1465 " /",
1466 " [1----)",
1467 " /",
1468 " [0----)"
1469 ),
1470 vec![2, 1, 0]
1471 )
1472 ]
1473 ];
1474 let cases = vec![(
1475 format!("{}\n{}\n{}\n",
1476 " [-----------------)",
1477 " -> -------------------",
1478 " [0----|1----|2----)"
1479 ),
1480 Segment::new(0, 18),
1481 vec![
1482 (Segment::new(0, 6), 0),
1483 (Segment::new(6, 12), 1),
1484 (Segment::new(12, 18), 2)
1485 ],
1486 vec![],
1487 ), (
1488 format!("{}\n{}\n{}\n",
1489 " [--------------)---",
1490 " -> ---------------[2-)",
1491 " [0----|1----|2----)"
1492 ),
1493 Segment::new(0, 15),
1494 vec![
1495 (Segment::new(0, 6), 0),
1496 (Segment::new(6, 12), 1),
1497 (Segment::new(12, 18), 2)
1498 ],
1499 vec![
1500 (Segment::new(15, 18), 2)
1501 ],
1502 ), (
1503 format!("{}\n{}\n{}\n",
1504 " [-----------)------",
1505 " -> ------------[2----)",
1506 " [0----|1----|2----)"
1507 ),
1508 Segment::new(0, 12),
1509 vec![
1510 (Segment::new(0, 6), 0),
1511 (Segment::new(6, 12), 1),
1512 (Segment::new(12, 18), 2)
1513 ],
1514 vec![
1515 (Segment::new(12, 18), 2)
1516 ],
1517 ), (
1518 format!("{}\n{}\n{}\n",
1519 " [--------)---------",
1520 " -> ---------[1-|2----)",
1521 " [0----|1----|2----)"
1522 ),
1523 Segment::new(0, 9),
1524 vec![
1525 (Segment::new(0, 6), 0),
1526 (Segment::new(6, 12), 1),
1527 (Segment::new(12, 18), 2)
1528 ],
1529 vec![
1530 (Segment::new(9, 12), 1),
1531 (Segment::new(12, 18), 2)
1532 ],
1533 ), (
1534 format!("{}\n{}\n{}\n",
1535 " [-----)------------",
1536 " -> ------[1----|2----)",
1537 " [0----|1----|2----)"
1538 ),
1539 Segment::new(0, 6),
1540 vec![
1541 (Segment::new(0, 6), 0),
1542 (Segment::new(6, 12), 1),
1543 (Segment::new(12, 18), 2)
1544 ],
1545 vec![
1546 (Segment::new(6, 12), 1),
1547 (Segment::new(12, 18), 2)
1548 ],
1549 ), (
1550 format!("{}\n{}\n{}\n",
1551 " [--)---------------",
1552 " -> ---[0-|1----|2----)",
1553 " [0----|1----|2----)"
1554 ),
1555 Segment::new(0, 3),
1556 vec![
1557 (Segment::new(0, 6), 0),
1558 (Segment::new(6, 12), 1),
1559 (Segment::new(12, 18), 2)
1560 ],
1561 vec![
1562 (Segment::new(3, 6), 0),
1563 (Segment::new(6, 12), 1),
1564 (Segment::new(12, 18), 2)
1565 ],
1566 ), (
1567 format!("{}\n{}\n{}\n",
1568 " |------------------",
1569 " -> [0----|1----|2----)",
1570 " [0----|1----|2----)"
1571 ),
1572 Segment::new(0, 0),
1573 vec![
1574 (Segment::new(0, 6), 0),
1575 (Segment::new(6, 12), 1),
1576 (Segment::new(12, 18), 2)
1577 ],
1578 vec![
1579 (Segment::new(0, 6), 0),
1580 (Segment::new(6, 12), 1),
1581 (Segment::new(12, 18), 2)
1582 ],
1583 ), (
1584 format!("{}\n{}\n{}\n",
1585 " ---[--------------)",
1586 " -> [0-)---------------",
1587 " [0----|1----|2----)"
1588 ),
1589 Segment::new(3, 18),
1590 vec![
1591 (Segment::new(0, 6), 0),
1592 (Segment::new(6, 12), 1),
1593 (Segment::new(12, 18), 2)
1594 ],
1595 vec![
1596 (Segment::new(0, 3), 0)
1597 ],
1598 ), (
1599 format!("{}\n{}\n{}\n",
1600 " ---[-----------)---",
1601 " -> [0-)-----------[2-)",
1602 " [0----|1----|2----)"
1603 ),
1604 Segment::new(3, 15),
1605 vec![
1606 (Segment::new(0, 6), 0),
1607 (Segment::new(6, 12), 1),
1608 (Segment::new(12, 18), 2)
1609 ],
1610 vec![
1611 (Segment::new(0, 3), 0),
1612 (Segment::new(15, 18), 2)
1613 ],
1614 ), (
1615 format!("{}\n{}\n{}\n",
1616 " ---[--------)------",
1617 " -> [0-)--------[2----)",
1618 " [0----|1----|2----)"
1619 ),
1620 Segment::new(3, 12),
1621 vec![
1622 (Segment::new(0, 6), 0),
1623 (Segment::new(6, 12), 1),
1624 (Segment::new(12, 18), 2)
1625 ],
1626 vec![
1627 (Segment::new(0, 3), 0),
1628 (Segment::new(12, 18), 2)
1629 ],
1630 ), (
1631 format!("{}\n{}\n{}\n",
1632 " ---[-----)---------",
1633 " -> [0-)-----[1-|2----)",
1634 " [0----|1----|2----)"
1635 ),
1636 Segment::new(3, 9),
1637 vec![
1638 (Segment::new(0, 6), 0),
1639 (Segment::new(6, 12), 1),
1640 (Segment::new(12, 18), 2)
1641 ],
1642 vec![
1643 (Segment::new(0, 3), 0),
1644 (Segment::new(9, 12), 1),
1645 (Segment::new(12, 18), 2)
1646 ],
1647 ), (
1648 format!("{}\n{}\n{}\n",
1649 " ---[--)------------",
1650 " -> [0-)--[1----|2----)",
1651 " [0----|1----|2----)"
1652 ),
1653 Segment::new(3, 6),
1654 vec![
1655 (Segment::new(0, 6), 0),
1656 (Segment::new(6, 12), 1),
1657 (Segment::new(12, 18), 2)
1658 ],
1659 vec![
1660 (Segment::new(0, 3), 0),
1661 (Segment::new(6, 12), 1),
1662 (Segment::new(12, 18), 2)
1663 ],
1664 ), (
1665 format!("{}\n{}\n{}\n",
1666 " --[-)--------------",
1667 " -> [0)-[0|1----|2----)",
1668 " [0----|1----|2----)"
1669 ),
1670 Segment::new(2, 4),
1671 vec![
1672 (Segment::new(0, 6), 0),
1673 (Segment::new(6, 12), 1),
1674 (Segment::new(12, 18), 2)
1675 ],
1676 vec![
1677 (Segment::new(0, 2), 0),
1678 (Segment::new(4, 6), 0),
1679 (Segment::new(6, 12), 1),
1680 (Segment::new(12, 18), 2)
1681 ],
1682 ), (
1683 format!("{}\n{}\n{}\n",
1684 " ---|---------------",
1685 " -> [0-|0-|1----|2----)",
1686 " [0----|1----|2----)"
1687 ),
1688 Segment::new(3, 3),
1689 vec![
1690 (Segment::new(0, 6), 0),
1691 (Segment::new(6, 12), 1),
1692 (Segment::new(12, 18), 2)
1693 ],
1694 vec![
1695 (Segment::new(0, 3), 0),
1696 (Segment::new(3, 6), 0),
1697 (Segment::new(6, 12), 1),
1698 (Segment::new(12, 18), 2)
1699 ],
1700 ), (
1701 format!("{}\n{}\n{}\n",
1702 " ------[-----------)",
1703 " -> [0----)------------",
1704 " [0----|1----|2----)"
1705 ),
1706 Segment::new(6, 18),
1707 vec![
1708 (Segment::new(0, 6), 0),
1709 (Segment::new(6, 12), 1),
1710 (Segment::new(12, 18), 2)
1711 ],
1712 vec![
1713 (Segment::new(0, 6), 0)
1714 ],
1715 ), (
1716 format!("{}\n{}\n{}\n",
1717 " ------[--------)---",
1718 " -> [0----)--------[2-)",
1719 " [0----|1----|2----)"
1720 ),
1721 Segment::new(6, 15),
1722 vec![
1723 (Segment::new(0, 6), 0),
1724 (Segment::new(6, 12), 1),
1725 (Segment::new(12, 18), 2)
1726 ],
1727 vec![
1728 (Segment::new(0, 6), 0),
1729 (Segment::new(15, 18), 2)
1730 ],
1731 ), (
1732 format!("{}\n{}\n{}\n",
1733 " ------[-----)------",
1734 " -> [0----)-----[2----)",
1735 " [0----|1----|2----)"
1736 ),
1737 Segment::new(6, 12),
1738 vec![
1739 (Segment::new(0, 6), 0),
1740 (Segment::new(6, 12), 1),
1741 (Segment::new(12, 18), 2)
1742 ],
1743 vec![
1744 (Segment::new(0, 6), 0),
1745 (Segment::new(12, 18), 2)
1746 ],
1747 ), (
1748 format!("{}\n{}\n{}\n",
1749 " ------[--)---------",
1750 " -> [0----)--[1-|2----)",
1751 " [0----|1----|2----)"
1752 ),
1753 Segment::new(6, 9),
1754 vec![
1755 (Segment::new(0, 6), 0),
1756 (Segment::new(6, 12), 1),
1757 (Segment::new(12, 18), 2)
1758 ],
1759 vec![
1760 (Segment::new(0, 6), 0),
1761 (Segment::new(9, 12), 1),
1762 (Segment::new(12, 18), 2)
1763 ],
1764 ), (
1765 format!("{}\n{}\n{}\n",
1766 " ------|------------",
1767 " -> [0----|1----|2----)",
1768 " [0----|1----|2----)"
1769 ),
1770 Segment::new(6, 6),
1771 vec![
1772 (Segment::new(0, 6), 0),
1773 (Segment::new(6, 12), 1),
1774 (Segment::new(12, 18), 2)
1775 ],
1776 vec![
1777 (Segment::new(0, 6), 0),
1778 (Segment::new(6, 12), 1),
1779 (Segment::new(12, 18), 2)
1780 ],
1781 ), (
1782 format!("{}\n{}\n{}\n",
1783 " [-----------------)",
1784 " -> -------------------",
1785 " ------[1----|2----)"
1786 ),
1787 Segment::new(0, 18),
1788 vec![
1789 (Segment::new(6, 12), 1),
1790 (Segment::new(12, 18), 2)
1791 ],
1792 vec![],
1793 ), (
1794 format!("{}\n{}\n{}\n",
1795 " [--------------)---",
1796 " -> ---------------[2-)",
1797 " ------[1----|2----)"
1798 ),
1799 Segment::new(0, 15),
1800 vec![
1801 (Segment::new(6, 12), 1),
1802 (Segment::new(12, 18), 2)
1803 ],
1804 vec![
1805 (Segment::new(15, 18), 2)
1806 ],
1807 ), (
1808 format!("{}\n{}\n{}\n",
1809 " [-----------)------",
1810 " -> ------------[2----)",
1811 " ------[1----|2----)"
1812 ),
1813 Segment::new(0, 12),
1814 vec![
1815 (Segment::new(6, 12), 1),
1816 (Segment::new(12, 18), 2)
1817 ],
1818 vec![
1819 (Segment::new(12, 18), 2)
1820 ],
1821 ), (
1822 format!("{}\n{}\n{}\n",
1823 " [--------)---------",
1824 " -> ---------[1-|2----)",
1825 " ------[1----|2----)"
1826 ),
1827 Segment::new(0, 9),
1828 vec![
1829 (Segment::new(6, 12), 1),
1830 (Segment::new(12, 18), 2)
1831 ],
1832 vec![
1833 (Segment::new(9, 12), 1),
1834 (Segment::new(12, 18), 2)
1835 ],
1836 ), (
1837 format!("{}\n{}\n{}\n",
1838 " [-----)------------",
1839 " -> ------[1----|2----)",
1840 " ------[1----|2----)"
1841 ),
1842 Segment::new(0, 6),
1843 vec![
1844 (Segment::new(6, 12), 1),
1845 (Segment::new(12, 18), 2)
1846 ],
1847 vec![
1848 (Segment::new(6, 12), 1),
1849 (Segment::new(12, 18), 2)
1850 ],
1851 ), (
1852 format!("{}\n{}\n{}\n",
1853 " [--)---------------",
1854 " -> ------[1----|2----)",
1855 " ------[1----|2----)"
1856 ),
1857 Segment::new(0, 3),
1858 vec![
1859 (Segment::new(6, 12), 1),
1860 (Segment::new(12, 18), 2)
1861 ],
1862 vec![
1863 (Segment::new(6, 12), 1),
1864 (Segment::new(12, 18), 2)
1865 ],
1866 ), (
1867 format!("{}\n{}\n{}\n",
1868 " |------------------",
1869 " -> ------[1----|2----)",
1870 " ------[1----|2----)"
1871 ),
1872 Segment::new(0, 0),
1873 vec![
1874 (Segment::new(6, 12), 1),
1875 (Segment::new(12, 18), 2)
1876 ],
1877 vec![
1878 (Segment::new(6, 12), 1),
1879 (Segment::new(12, 18), 2)
1880 ],
1881 ), (
1882 format!("{}\n{}\n{}\n",
1883 " [-----------------)",
1884 " -> -------------------",
1885 " [0----)-----[2----)"
1886 ),
1887 Segment::new(0, 18),
1888 vec![
1889 (Segment::new(0, 6), 0),
1890 (Segment::new(12, 18), 2)
1891 ],
1892 vec![],
1893 ), (
1894 format!("{}\n{}\n{}\n",
1895 " [--------------)---",
1896 " -> ---------------[2-)",
1897 " [0----)-----[2----)"
1898 ),
1899 Segment::new(0, 15),
1900 vec![
1901 (Segment::new(0, 6), 0),
1902 (Segment::new(12, 18), 2)
1903 ],
1904 vec![
1905 (Segment::new(15, 18), 2)
1906 ],
1907 ), (
1908 format!("{}\n{}\n{}\n",
1909 " [-----------)------",
1910 " -> ------------[2----)",
1911 " [0----)-----[2----)"
1912 ),
1913 Segment::new(0, 12),
1914 vec![
1915 (Segment::new(0, 6), 0),
1916 (Segment::new(12, 18), 2)
1917 ],
1918 vec![
1919 (Segment::new(12, 18), 2)
1920 ],
1921 ), (
1922 format!("{}\n{}\n{}\n",
1923 " [--------)---------",
1924 " -> ------------[2----)",
1925 " [0----)-----[2----)"
1926 ),
1927 Segment::new(0, 9),
1928 vec![
1929 (Segment::new(0, 6), 0),
1930 (Segment::new(12, 18), 2)
1931 ],
1932 vec![
1933 (Segment::new(12, 18), 2)
1934 ],
1935 ), (
1936 format!("{}\n{}\n{}\n",
1937 " ---[--------------)",
1938 " -> [0-)---------------",
1939 " [0----)-----[2----)"
1940 ),
1941 Segment::new(3, 18),
1942 vec![
1943 (Segment::new(0, 6), 0),
1944 (Segment::new(12, 18), 2)
1945 ],
1946 vec![
1947 (Segment::new(0, 3), 0)
1948 ],
1949 ), (
1950 format!("{}\n{}\n{}\n",
1951 " ---[-----------)---",
1952 " -> [0-)-----------[2-)",
1953 " [0----)-----[2----)"
1954 ),
1955 Segment::new(3, 15),
1956 vec![
1957 (Segment::new(0, 6), 0),
1958 (Segment::new(12, 18), 2)
1959 ],
1960 vec![
1961 (Segment::new(0, 3), 0),
1962 (Segment::new(15, 18), 2)
1963 ],
1964 ), (
1965 format!("{}\n{}\n{}\n",
1966 " ---[--------)------",
1967 " -> [0-)--------[2----)",
1968 " [0----)-----[2----)"
1969 ),
1970 Segment::new(3, 12),
1971 vec![
1972 (Segment::new(0, 6), 0),
1973 (Segment::new(12, 18), 2)
1974 ],
1975 vec![
1976 (Segment::new(0, 3), 0),
1977 (Segment::new(12, 18), 2)
1978 ],
1979 ), (
1980 format!("{}\n{}\n{}\n",
1981 " ---[-----)---------",
1982 " -> [0-)--------[2----)",
1983 " [0----)-----[2----)"
1984 ),
1985 Segment::new(3, 9),
1986 vec![
1987 (Segment::new(0, 6), 0),
1988 (Segment::new(12, 18), 2)
1989 ],
1990 vec![
1991 (Segment::new(0, 3), 0),
1992 (Segment::new(12, 18), 2)
1993 ],
1994 ), (
1995 format!("{}\n{}\n{}\n",
1996 " [-----------------)",
1997 " -> -------------------",
1998 " [0----|1----)------"
1999 ),
2000 Segment::new(0, 18),
2001 vec![
2002 (Segment::new(0, 6), 0),
2003 (Segment::new(6, 12), 1)
2004 ],
2005 vec![],
2006 ), (
2007 format!("{}\n{}\n{}\n",
2008 " [--------------)---",
2009 " -> -------------------",
2010 " [0----|1----)------"
2011 ),
2012 Segment::new(0, 15),
2013 vec![
2014 (Segment::new(0, 6), 0),
2015 (Segment::new(6, 12), 1)
2016 ],
2017 vec![],
2018 ), (
2019 format!("{}\n{}\n{}\n",
2020 " ---[--------------)",
2021 " -> [0-)---------------",
2022 " [0----|1----)------"
2023 ),
2024 Segment::new(3, 18),
2025 vec![
2026 (Segment::new(0, 6), 0),
2027 (Segment::new(6, 12), 1)
2028 ],
2029 vec![
2030 (Segment::new(0, 3), 0)
2031 ],
2032 ), (
2033 format!("{}\n{}\n{}\n",
2034 " [-----------------)",
2035 " -> -------------------",
2036 " ------[1----)------"
2037 ),
2038 Segment::new(0, 18),
2039 vec![
2040 (Segment::new(6, 12), 1)
2041 ],
2042 vec![],
2043 ), (
2044 format!("{}\n{}\n{}\n",
2045 " |------------------",
2046 " -> [1----|2----)------",
2047 " [1----|2----)------"
2048 ),
2049 Segment::new(0, 0),
2050 vec![
2051 (Segment::new(0, 0), 0),
2052 (Segment::new(0, 6), 1),
2053 (Segment::new(6, 12), 2)
2054 ],
2055 vec![
2056 (Segment::new(0, 6), 1),
2057 (Segment::new(6, 12), 2)
2058 ],
2059 )
2060 ];
2061 for (case_description, update_segment, insert_segments, expected_segments) in cases {
2062 for (permutation_description, indices) in &permutations[insert_segments.len()] {
2063 let mut segment_map = SegmentMap::new();
2064 for &index in indices {
2065 let (insert_segment, insert_value) = insert_segments[index];
2066 segment_map.insert(insert_segment, insert_value);
2067 }
2068 segment_map.update(&update_segment, |_| None);
2069 assert_eq!(expected_segments, segment_map.into_iter().collect::<Vec<_>>(), "\npermutation:\n\n{}\ncase:\n\n{}\n", permutation_description, case_description);
2070 }
2071 }
2072 }
2073}