-
Notifications
You must be signed in to change notification settings - Fork 0
/
sequence_analysis.go
144 lines (122 loc) · 4.12 KB
/
sequence_analysis.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
package common
import (
"errors"
)
// SequenceCoordinate : contains both the sequence id of a signer, and the index of the occurence in the sequence
type SequenceCoordinate struct {
Signer, Index uint32
}
// FindNextIndex analyses the specified sequence and tries to find the next occurence of id after the specified index (excluded)
// Therefore to find the first occurence of the id in the sequence, use -1 as the index
//
// If there is no occurence of id, then -1 is returned
//
// The sequence is supposed to be correct (in regards to its mathematical definition), and id is supposed to be a valid id for the sequence
func FindNextIndex(s []uint32, id uint32, index int) (int, error) {
if index >= len(s) || index < -1 {
return -1, errors.New("Index out of range")
}
for i := index + 1; i < len(s); i++ {
if s[i] == id {
return i, nil
}
}
return -1, nil
}
// GetPendingSet analyses the specified sequence and computes the set of ids occuring between index (excluded) and the previous occurence of id
//
// The sequence is supposed to be correct (in regards to its mathematical definition), and id is supposed to be a valid id for the sequence
//
// If the index is not the one of the specified id in the sequence, the result still holds, but may be incomplete for your needs
// If the id is not valid for the specified sequence, the result will be the set of ids of the sequence
func GetPendingSet(s []uint32, id uint32, index int) ([]SequenceCoordinate, error) {
res := []SequenceCoordinate{}
if index >= len(s) || index < 0 {
return res, errors.New("Index out of range")
}
curIndex := index - 1
if curIndex < 0 {
return res, nil
}
for curIndex > -1 && s[curIndex] != id {
curID := s[curIndex]
if !containsCoordinate(res, curID) {
res = append(res, SequenceCoordinate{Signer: curID, Index: uint32(curIndex)})
}
curIndex--
}
return res, nil
}
// GetSendSet analyses the specified sequence and computes the set of ids occuring between index (excluded) and the next occurence of id
//
// The sequence is supposed to be correct (in regards to its mathematical definition), and id is supposed to be a valid id for the sequence
//
// If the index is not the one of the specified id in the sequence, the result still holds, but may be incomplete for your needs
// If the id is not valid for the specified sequence, the result will be the set of ids of the sequence
func GetSendSet(s []uint32, id uint32, index int) ([]SequenceCoordinate, error) {
res := []SequenceCoordinate{}
if index >= len(s) || index < 0 {
return res, errors.New("Index out of range")
}
curIndex := index + 1
if curIndex >= len(s) {
return res, nil
}
for curIndex < len(s) && s[curIndex] != id {
curID := s[curIndex]
if !containsCoordinate(res, curID) {
res = append(res, SequenceCoordinate{Signer: curID, Index: uint32(curIndex)})
}
curIndex++
}
return res, nil
}
// containsCoordinate: determines if s contains the specified signer sequence id e
func containsCoordinate(s []SequenceCoordinate, e uint32) bool {
for _, a := range s {
if a.Signer == e {
return true
}
}
return false
}
// contains : determines if s contains e
func contains(s []uint32, e uint32) bool {
for _, a := range s {
if a == e {
return true
}
}
return false
}
// GetAllButOne creates the slice of all sequence ids, except the one specified
//
// TODO This is O(n^2) and need a rework with a map
func GetAllButOne(s []uint32, e uint32) []uint32 {
var res = make([]uint32, 0)
for i := 0; i < len(s); i++ {
curID := s[i]
if !contains(res, curID) && curID != e {
res = append(res, curID)
}
}
return res
}
// RemoveCoordinate : removes the first occurence of an ID from the coordinates array
func RemoveCoordinate(s []SequenceCoordinate, e uint32) ([]SequenceCoordinate, error) {
for i, a := range s {
if a.Signer == e {
return append(s[:i], s[i+1:]...), nil
}
}
return s, errors.New("ID not in sequence")
}
// Remove the first occurence of an ID from the ids array
func Remove(s []uint32, e uint32) ([]uint32, error) {
for i, a := range s {
if a == e {
return append(s[:i], s[i+1:]...), nil
}
}
return s, errors.New("ID not in sequence")
}