-
Notifications
You must be signed in to change notification settings - Fork 2
/
section.go
157 lines (127 loc) · 3.33 KB
/
section.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
package tracker
import (
"github.com/Zondax/zindexer/components/connections/database/postgres"
"sort"
)
// Section defines an interval of heights with inclusive boundaries [StartIdx, EndIdx]
type Section struct {
StartIdx uint64
EndIdx uint64
}
type Sections = []Section
func (Section) TableName() string {
return postgres.GetTableName("tracking")
}
func BuildSectionsFromSlice(heights *[]uint64) Sections {
var sections Sections
if heights == nil {
return sections
}
for i := 0; i < len(*heights); i++ {
sections = append(sections, Section{
StartIdx: (*heights)[i],
EndIdx: (*heights)[i],
})
}
return MergeSections(sections)
}
func BuildSliceFromSections(sections Sections) *[]uint64 {
sections = MergeSections(sections)
if len(sections) == 0 {
return &[]uint64{}
}
maxCapacity := sections[len(sections)-1].EndIdx - sections[0].StartIdx
if maxCapacity == 0 {
// this section contains the same value for StartIdx and EndIdx, maxCapacity should be 1
maxCapacity = 1
}
var a = make([]uint64, 0, maxCapacity)
for _, section := range sections {
for i := section.StartIdx; i <= section.EndIdx; i++ {
a = append(a, i)
}
}
return &a
}
func FindGapsInSections(sections Sections) *[]uint64 {
// Merge sections and estimate max capacity
sections = MergeSections(sections)
if len(sections) < 2 {
return &[]uint64{}
}
maxCapacity := sections[len(sections)-1].StartIdx - sections[0].EndIdx
var missing = make([]uint64, 0, maxCapacity)
for i := 1; i < len(sections); i++ {
lastSection := sections[i-1]
high := sections[i].StartIdx
if high > 0 {
high--
}
low := lastSection.EndIdx
for j := high; j > low; j-- {
missing = append(missing, j)
}
}
// Return missing in desc order prioritizing newer blocks
sort.Slice(missing, func(i, j int) bool {
return missing[j] < missing[i]
})
return &missing
}
func MergeSections(sections Sections) Sections {
var merged Sections
if len(sections) > 1 {
sort.Slice(sections, func(i, j int) bool {
return sections[i].StartIdx < sections[j].StartIdx
})
}
for _, section := range sections {
if section.StartIdx > section.EndIdx {
t := section
section.StartIdx = t.EndIdx
section.EndIdx = t.StartIdx
}
last := len(merged) - 1
if last < 0 {
merged = append(merged, section)
continue
}
if section.StartIdx == merged[last].EndIdx+1 {
merged[last].EndIdx = section.EndIdx
continue
}
if section.StartIdx > merged[last].EndIdx {
merged = append(merged, section)
continue
}
if section.EndIdx > merged[last].EndIdx {
merged[last].EndIdx = section.EndIdx
continue
}
}
return merged
}
// RemoveSections removes any sections included in (toRemove: Sections) that intersect with (sections: Sections)
func RemoveSections(sections, toRemove Sections) Sections {
sectionsFlat := BuildSliceFromSections(sections)
toRemoveFlat := BuildSliceFromSections(toRemove)
resultFlat := make([]uint64, 0, len(*sectionsFlat))
i := 0
j := 0
for i < len(*sectionsFlat) && j < len(*toRemoveFlat) {
if (*sectionsFlat)[i] == (*toRemoveFlat)[j] {
i++
j++
continue
}
if (*sectionsFlat)[i] < (*toRemoveFlat)[j] {
resultFlat = append(resultFlat, (*sectionsFlat)[i])
i++
} else {
j++
}
}
resultFlat = append(resultFlat, (*sectionsFlat)[i:]...)
result := BuildSectionsFromSlice(&resultFlat)
return result
}