-
Notifications
You must be signed in to change notification settings - Fork 0
/
sorted_cmp.go
112 lines (98 loc) · 2.97 KB
/
sorted_cmp.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
// Copyright (c) 2018-2023 Jean-Francois SMIGIELSKI
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
package bags
import (
"sort"
)
// SortedCmp implements a sorted array of comparable objects.
// The sorted storage allows O(log N) lookups, efficient sorted scans but
// average O(N log N) insertions.
// SortedCmp proves useful for stable collection which are frequently accessed
// for paginated listings.
type SortedCmp[T WithCompare[T]] []T
type WithCompare[T any] interface {
Compare(other T) int
}
// Len implements a method of the sort.Interface
func (s SortedCmp[T]) Len() int { return len(s) }
// Swap implements a method of the sort.Interface
func (s SortedCmp[T]) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
// Less implements a method of the sort.Interface
func (s SortedCmp[T]) Less(i, j int) bool { return s[i].Compare(s[j]) < 0 }
// Add introduces a new item in the sorted array, regardless the presence of the same item,
// and preserves the ordering of the array.
func (s *SortedCmp[T]) Add(a T) {
*s = append(*s, a)
switch nb := len(*s); nb {
case 1:
return
case 2:
sort.Sort(s)
default:
// Only sort the array if the last 2 element are not sorted: in other words,
// adding the new biggest element maintains the ordering
if !sort.IsSorted((*s)[nb-2:]) {
sort.Sort(s)
}
}
}
// Append introduces several items in the sorted array, regardless the presence of identical items
// and preserves the ordering of the array.
func (s *SortedCmp[T]) Append(a ...T) {
*s = append(*s, a...)
sort.Sort(s)
}
func (s SortedCmp[T]) Slice(marker T, max uint32) []T {
if max < MinSliceSize {
max = MinSliceSize
} else if max > MaxSliceSize {
max = MaxSliceSize
}
start := sort.Search(len(s), func(i int) bool {
return marker.Compare(s[i]) < 0
})
if start < 0 || start >= s.Len() {
return s[:0]
}
remaining := uint32(s.Len() - start)
if remaining > max {
remaining = max
}
return s[start : uint32(start)+remaining]
}
// GetIndex returns the position of the first items that matches (Compare returns 0) to the given other item,
// or -1 in case of no match.
func (s SortedCmp[T]) GetIndex(id T) int {
i := sort.Search(len(s), func(i int) bool {
return id.Compare(s[i]) <= 0
})
if i < len(s) && id.Compare(s[i]) == 0 {
return i
}
return -1
}
func (s SortedCmp[T]) Get(id T) (out T, ok bool) {
idx := s.GetIndex(id)
if idx >= 0 {
return s[idx], true
}
return out, false
}
// Has tests for the presence of an item in the set, given a copy of the item
func (s SortedCmp[T]) Has(id T) bool { return s.GetIndex(id) >= 0 }
// Remove forwards the call to RemovePK with the primary key of the given
// element.
func (s *SortedCmp[T]) Remove(a T) {
idx := s.GetIndex(a)
if idx >= 0 && idx < len(*s) {
if len(*s) == 1 {
*s = (*s)[:0]
} else {
s.Swap(idx, s.Len()-1)
*s = (*s)[:s.Len()-1]
sort.Sort(*s)
}
}
}