-
Notifications
You must be signed in to change notification settings - Fork 0
/
compact.go
142 lines (125 loc) · 4.2 KB
/
compact.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
package list
import "sort"
// Compact is a list of sorted Elements with a specific maximum size.
// It supports insertion, updating elements in place, and removing
// elements.
type Compact struct {
elements []Element
Size int
Comparator
}
// NewCompact returns a Compact with the given maximum size and
// using the given Comparator to sort its contents.
func NewCompact(size int, comp Comparator) *Compact {
return &Compact{
Size: size,
Comparator: comp,
}
}
func (c *Compact) mapping() map[Serial]int {
serialToRaw := make(map[Serial]int)
for i, elem := range c.elements {
serialToRaw[elem.Serial()] = i
}
return serialToRaw
}
// Apply inserts, updates, and removes elements from within the contents
// of the compact.
func (c *Compact) Apply(insertOrUpdate []Element, updateOnly []Element, remove []Serial) {
serialToRaw := c.mapping()
// Search newElems for elements that already exist within the Raw slice.
SliceFilter(&insertOrUpdate, func(elem Element) bool {
rawIndex, exists := serialToRaw[elem.Serial()]
if exists {
// Update the stored existing element.
c.elements[rawIndex] = elem
return false
}
return true
})
// Update elements if and only if they are present.
for _, elem := range updateOnly {
index, isPresent := serialToRaw[elem.Serial()]
if !isPresent {
continue
}
c.elements[index] = elem
}
// Find the index of each element needing removal.
targetIndices := make([]int, len(remove))
for _, serial := range remove {
idx, ok := serialToRaw[serial]
if !ok {
continue
}
targetIndices = append(targetIndices, idx)
}
// Remove them by swapping and re-slicing, starting from the highest
// index to ensure that we do not move a removed element into the
// middle of the list as part of the swap.
sort.Sort(sort.Reverse(sort.IntSlice(targetIndices)))
for _, target := range targetIndices {
SliceRemove(&c.elements, target)
}
c.elements = append(c.elements, insertOrUpdate...)
// Re-sort elements.
sort.SliceStable(c.elements, func(i, j int) bool {
return c.Comparator(c.elements[i], c.elements[j])
})
}
// Compact returns a compacted slice of the elements managed by the Compact.
// The resulting elements are guaranteed to be sorted using the
// Compact's Comparator and there will usually be no more than c.Size elements.
// The exception is when c.Size is smaller than 3 times the distance between
// keepStart and keepEnd. In that case, Compact will attempt to return a slice
// containing the region described by [keepStart,keepEnd] with the same number
// of elements on either side.
func (c *Compact) Compact(keepStart, keepEnd Serial) (contents []Element, compacted []Serial) {
if len(c.elements) < 1 {
return nil, nil
}
serialToRaw := c.mapping()
keepStartIdx, ok := serialToRaw[keepStart]
if !ok || keepStart == NoSerial {
keepStartIdx = 0
}
keepEndIdx, ok := serialToRaw[keepEnd]
if !ok || keepEnd == NoSerial {
keepEndIdx = len(c.elements) - 1
}
visible := 1 + keepEndIdx - keepStartIdx
size := max(c.Size, 3*visible)
additional := size - visible
if additional > 0 {
// cut the additional size in half, ensuring that no element is
// lost to integer truncation.
half := additional / 2
secondHalf := additional - half
if keepStartIdx < half {
// Donate any unused quota at the beginning of the list to
// the end.
secondHalf += half - keepStartIdx
}
if newEnd := keepEndIdx + secondHalf; newEnd >= len(c.elements) {
// Donate any unused quota at the end of the list to
// the beginning.
half += newEnd - (len(c.elements) - 1)
}
keepStartIdx = max(keepStartIdx-half, 0)
keepEndIdx = min(keepEndIdx+secondHalf, len(c.elements)-1)
}
// Collect the serials of elements that are being deallocated by compaction.
for i := 0; i < keepStartIdx; i++ {
compacted = append(compacted, c.elements[i].Serial())
}
for i := keepEndIdx + 1; i < len(c.elements); i++ {
compacted = append(compacted, c.elements[i].Serial())
}
// Allocate a new Raw slice to house the data, allowing the older,
// longer slice to be garbage collected.
newLength := keepEndIdx - keepStartIdx + 1
newRaw := make([]Element, newLength)
copy(newRaw, c.elements[keepStartIdx:keepEndIdx+1])
c.elements = newRaw
return c.elements, compacted
}