segment_map/
segment_map.rs

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((&current.segment, &current.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((&current.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}