~gioverse/chat

ref: c86e075f0df33cc01ac99f167a09f981997727d0 chat/list/compact.go -rw-r--r-- 4.2 KiB
c86e075fChris Waldon debug: add function to easily log structures 10 months ago
                                                                                
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
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.
	var targetIndicies []int
	for _, serial := range remove {
		idx, ok := serialToRaw[serial]
		if !ok {
			continue
		}
		targetIndicies = append(targetIndicies, 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(targetIndicies)))
	for _, target := range targetIndicies {
		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 garanteed 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
}