-
Notifications
You must be signed in to change notification settings - Fork 31
/
sorting.go
128 lines (103 loc) · 3.19 KB
/
sorting.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
// Package sorting includes utilities for ordering slices of Entries.
package sorting
import (
"bytes"
"fmt"
"sort"
"strings"
"berty.tech/go-ipfs-log/errmsg"
"berty.tech/go-ipfs-log/iface"
)
func SortByClocks(a, b iface.IPFSLogEntry, resolveConflict func(a iface.IPFSLogEntry, b iface.IPFSLogEntry) (int, error)) (int, error) {
diff := a.GetClock().Compare(b.GetClock())
if diff == 0 {
return resolveConflict(a, b)
}
return diff, nil
}
func SortByClockID(a, b iface.IPFSLogEntry, resolveConflict func(a iface.IPFSLogEntry, b iface.IPFSLogEntry) (int, error)) (int, error) {
comparedIDs := bytes.Compare(a.GetClock().GetID(), b.GetClock().GetID())
if comparedIDs == 0 {
return resolveConflict(a, b)
}
return comparedIDs, nil
}
func First(_, _ iface.IPFSLogEntry) (int, error) {
return 1, nil
}
func FirstWriteWins(a, b iface.IPFSLogEntry) (int, error) {
res, err := LastWriteWins(a, b)
if err != nil {
return 0, errmsg.ErrTiebreakerFailed.Wrap(err)
}
return res * -1, nil
}
func LastWriteWins(a, b iface.IPFSLogEntry) (int, error) {
sortByID := func(a, b iface.IPFSLogEntry) (int, error) {
return SortByClockID(a, b, First)
}
sortByEntryClocks := func(a, b iface.IPFSLogEntry) (int, error) {
return SortByClocks(a, b, sortByID)
}
return sortByEntryClocks(a, b)
}
func SortByEntryHash(a, b iface.IPFSLogEntry) (int, error) {
// Ultimate conflict resolution (compare hashes)
compareHash := func(a, b iface.IPFSLogEntry) (int, error) {
return strings.Compare(a.GetHash().String(), b.GetHash().String()), nil
}
// Sort two entries by their clock id, if the same then compare hashes
sortByID := func(a, b iface.IPFSLogEntry) (int, error) {
return SortByClockID(a, b, compareHash)
}
// Sort two entries by their clock time, if concurrent,
// determine sorting using provided conflict resolution function
// Sort entries by clock time as the primary sort criteria
return SortByClocks(a, b, sortByID)
}
func NoZeroes(compFunc func(a, b iface.IPFSLogEntry) (int, error)) func(a, b iface.IPFSLogEntry) (int, error) {
return func(a, b iface.IPFSLogEntry) (int, error) {
ret, err := compFunc(a, b)
if err != nil {
return 0, errmsg.ErrTiebreakerFailed.Wrap(err)
}
if ret != 0 {
return ret, nil
}
return 0, errmsg.ErrTiebreakerBogus
}
}
func Reverse(a []iface.IPFSLogEntry) {
for i := len(a)/2 - 1; i >= 0; i-- {
opp := len(a) - 1 - i
a[i], a[opp] = a[opp], a[i]
}
}
func Compare(a, b iface.IPFSLogEntry) (int, error) {
// TODO: Make it a Golang slice-compatible sort function
if a == nil || b == nil || !a.Defined() || !b.Defined() {
return 0, errmsg.ErrEntryNotDefined
}
return a.GetClock().Compare(b.GetClock()), nil
}
func Sort(compFunc func(a, b iface.IPFSLogEntry) (int, error), values []iface.IPFSLogEntry, reverse bool) {
if reverse {
sort.SliceStable(values, func(i, j int) bool {
ret, err := compFunc(values[i], values[j])
if err != nil {
fmt.Printf("error while comparing: %v\n", err)
return false
}
return ret > 0
})
} else {
sort.SliceStable(values, func(i, j int) bool {
ret, err := compFunc(values[i], values[j])
if err != nil {
fmt.Printf("error while comparing: %v\n", err)
return false
}
return ret < 0
})
}
}