1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
// Copyright (C) 2022-2023 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
package containers
import (
"fmt"
"testing"
"github.com/stretchr/testify/assert"
)
func (t *IntervalTree[K, V]) ASCIIArt() string {
return t.inner.ASCIIArt()
}
func (v intervalValue[K, V]) String() string {
return fmt.Sprintf("%v) ([%v,%v]",
v.Val,
v.ChildSpan.Min,
v.ChildSpan.Max)
}
func (v NativeOrdered[T]) String() string {
return fmt.Sprintf("%v", v.Val)
}
type SimpleInterval struct {
Min, Max int
}
func (ival SimpleInterval) String() string {
return fmt.Sprintf("[%v,%v]", ival.Min, ival.Max)
}
func TestIntervalTree(t *testing.T) {
t.Parallel()
tree := IntervalTree[NativeOrdered[int], SimpleInterval]{
MinFn: func(ival SimpleInterval) NativeOrdered[int] { return NativeOrdered[int]{ival.Min} },
MaxFn: func(ival SimpleInterval) NativeOrdered[int] { return NativeOrdered[int]{ival.Max} },
}
// CLRS Figure 14.4
// level 0
tree.Insert(SimpleInterval{16, 21})
// level 1
tree.Insert(SimpleInterval{8, 9})
tree.Insert(SimpleInterval{25, 30})
// level 2
tree.Insert(SimpleInterval{5, 8})
tree.Insert(SimpleInterval{15, 23})
tree.Insert(SimpleInterval{17, 19})
tree.Insert(SimpleInterval{26, 26})
// level 3
tree.Insert(SimpleInterval{0, 3})
tree.Insert(SimpleInterval{6, 10})
tree.Insert(SimpleInterval{19, 20})
t.Log("\n" + tree.ASCIIArt())
// find intervals that touch [9,20]
var intervals []SimpleInterval
tree.Subrange(
func(k NativeOrdered[int]) int {
if k.Val < 9 {
return 1
}
if k.Val > 20 {
return -1
}
return 0
},
func(v SimpleInterval) bool {
intervals = append(intervals, v)
return true
})
assert.Equal(t,
[]SimpleInterval{
{6, 10},
{8, 9},
{15, 23},
{16, 21},
{17, 19},
{19, 20},
},
intervals)
}
|
