-
Notifications
You must be signed in to change notification settings - Fork 0
/
merged.go
166 lines (147 loc) · 3.98 KB
/
merged.go
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
package intervals
import (
"github.com/relvox/iridescence_go/utils"
)
type mergedIntervals[T Number] []Interval[T]
func RawMerged[T Number](intervals ...Interval[T]) Interval[T] {
intervals = utils.CropElements(intervals, nil, NewEmpty[T]())
if len(intervals) == 0 {
return NewEmpty[T]()
}
if len(intervals) == 1 {
return NewClosed(intervals[0].Min(), intervals[0].Max())
}
return mergedIntervals[T](intervals)
}
func NewMerged[T Number](intervals ...Interval[T]) Interval[T] {
intervals = utils.CropElements(intervals, nil, NewEmpty[T]())
if len(intervals) == 0 {
return NewEmpty[T]()
}
if len(intervals) == 1 {
return intervals[0]
}
rawIntervals := make([][2]T, 0, len(intervals))
for i := 0; i < len(intervals); i++ {
subInts := intervals[i].Intervals()
if subInts == nil {
rawIntervals = append(rawIntervals, [2]T{intervals[i].Min(), intervals[i].Max()})
continue
}
for _, subInt := range subInts {
rawIntervals = append(rawIntervals, [2]T{subInt.Min(), subInt.Max()})
}
}
rawResult := FindCover(rawIntervals)
var res []Interval[T] = make([]Interval[T], len(rawResult)/2)
for i := 0; i < len(res); i++ {
res[i] = NewClosed(rawResult[i*2], rawResult[i*2+1])
}
return mergedIntervals[T](res)
}
func (mis mergedIntervals[T]) Min() T { return mis[0].Min() }
func (mis mergedIntervals[T]) Max() T { return mis[len(mis)-1].Max() }
func (mis mergedIntervals[T]) Len() T {
var result T
for _, v := range mis.Intervals() {
result += v.Len()
}
return result
}
func (mis mergedIntervals[T]) IsEmpty() bool { return false }
func (mis mergedIntervals[T]) IsSingleton() bool { return false }
func (mis mergedIntervals[T]) IsCompound() bool { return true }
func (mis mergedIntervals[T]) Enumerate(step T) []T {
var res []T
for _, subInt := range mis {
res = append(res, subInt.Enumerate(step)...)
}
return res
}
func (mis mergedIntervals[T]) Intervals() []Interval[T] {
for _, v := range mis {
if v.IsCompound() {
panic("DO NOT WANT!")
}
}
return mis
}
func (mis mergedIntervals[T]) Contains(value T) bool {
for _, subInt := range mis {
if subInt.Contains(value) {
return true
}
}
return false
}
func (mis mergedIntervals[T]) Overlaps(other Interval[T]) bool {
for _, subInt := range mis {
if subInt.Overlaps(other) {
return true
}
}
return false
}
func (mis mergedIntervals[T]) Equals(other Interval[T]) bool {
if other == nil || other.IsEmpty() || other.IsSingleton() || !other.IsCompound() {
return false
}
subInts := other.Intervals()
if len(subInts) != len(mis) {
return false
}
for si, subInt := range subInts {
if !subInt.Equals(mis[si]) {
return false
}
}
return true
}
func (mis mergedIntervals[T]) Union(other Interval[T]) Interval[T] {
if other == nil || other.IsEmpty() {
return mis
}
if !other.IsCompound() {
return other.Union(mis)
}
return NewMerged(other, mis)
}
func (mis mergedIntervals[T]) Intersection(other Interval[T]) Interval[T] {
if other == nil || other.IsEmpty() {
return NewEmpty[T]()
}
var res []Interval[T]
for _, subInt := range mis {
res = append(res, other.Intersection(subInt))
}
return RawMerged(res...)
}
func (mis mergedIntervals[T]) Difference(other Interval[T]) Interval[T] {
if other == nil || other.IsEmpty() || !other.Overlaps(mis) {
return mis
}
var res []Interval[T]
if !other.IsCompound() {
for _, subInt := range mis {
res = append(res, subInt.Difference(other).Intervals()...)
}
return RawMerged(res...)
}
otherIntervals := other.Intervals()
for _, subInt := range mis {
for _, otherSubInt := range otherIntervals {
subInt = subInt.Difference(otherSubInt)
}
res = append(res, subInt)
}
return RawMerged(res...)
}
func (mis mergedIntervals[T]) Resize(newSize T, growMode GrowFlags) Interval[T] {
panic("#TODO: not implemented")
}
func (mis mergedIntervals[T]) Scale(scale float64, growMode GrowFlags) Interval[T] {
panic("#TODO: not implemented")
}
func (mis mergedIntervals[T]) Translate(offset T, back bool) Interval[T] {
panic("#TODO: not implemented")
}