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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
|
package middleware
import "fmt"
// RelativePosition provides specifying the relative position of a middleware
// in an ordered group.
type RelativePosition int
// Relative position for middleware in steps.
const (
After RelativePosition = iota
Before
)
type ider interface {
ID() string
}
// orderedIDs provides an ordered collection of items with relative ordering
// by name.
type orderedIDs struct {
order *relativeOrder
items map[string]ider
}
const baseOrderedItems = 5
func newOrderedIDs() *orderedIDs {
return &orderedIDs{
order: newRelativeOrder(),
items: make(map[string]ider, baseOrderedItems),
}
}
// Add injects the item to the relative position of the item group. Returns an
// error if the item already exists.
func (g *orderedIDs) Add(m ider, pos RelativePosition) error {
id := m.ID()
if len(id) == 0 {
return fmt.Errorf("empty ID, ID must not be empty")
}
if err := g.order.Add(pos, id); err != nil {
return err
}
g.items[id] = m
return nil
}
// Insert injects the item relative to an existing item id. Returns an error if
// the original item does not exist, or the item being added already exists.
func (g *orderedIDs) Insert(m ider, relativeTo string, pos RelativePosition) error {
if len(m.ID()) == 0 {
return fmt.Errorf("insert ID must not be empty")
}
if len(relativeTo) == 0 {
return fmt.Errorf("relative to ID must not be empty")
}
if err := g.order.Insert(relativeTo, pos, m.ID()); err != nil {
return err
}
g.items[m.ID()] = m
return nil
}
// Get returns the ider identified by id. If ider is not present, returns false.
func (g *orderedIDs) Get(id string) (ider, bool) {
v, ok := g.items[id]
return v, ok
}
// Swap removes the item by id, replacing it with the new item. Returns an error
// if the original item doesn't exist.
func (g *orderedIDs) Swap(id string, m ider) (ider, error) {
if len(id) == 0 {
return nil, fmt.Errorf("swap from ID must not be empty")
}
iderID := m.ID()
if len(iderID) == 0 {
return nil, fmt.Errorf("swap to ID must not be empty")
}
if err := g.order.Swap(id, iderID); err != nil {
return nil, err
}
removed := g.items[id]
delete(g.items, id)
g.items[iderID] = m
return removed, nil
}
// Remove removes the item by id. Returns an error if the item
// doesn't exist.
func (g *orderedIDs) Remove(id string) (ider, error) {
if len(id) == 0 {
return nil, fmt.Errorf("remove ID must not be empty")
}
if err := g.order.Remove(id); err != nil {
return nil, err
}
removed := g.items[id]
delete(g.items, id)
return removed, nil
}
func (g *orderedIDs) List() []string {
items := g.order.List()
order := make([]string, len(items))
copy(order, items)
return order
}
// Clear removes all entries and slots.
func (g *orderedIDs) Clear() {
g.order.Clear()
g.items = map[string]ider{}
}
// GetOrder returns the item in the order it should be invoked in.
func (g *orderedIDs) GetOrder() []interface{} {
order := g.order.List()
ordered := make([]interface{}, len(order))
for i := 0; i < len(order); i++ {
ordered[i] = g.items[order[i]]
}
return ordered
}
// relativeOrder provides ordering of item
type relativeOrder struct {
order []string
}
func newRelativeOrder() *relativeOrder {
return &relativeOrder{
order: make([]string, 0, baseOrderedItems),
}
}
// Add inserts an item into the order relative to the position provided.
func (s *relativeOrder) Add(pos RelativePosition, ids ...string) error {
if len(ids) == 0 {
return nil
}
for _, id := range ids {
if _, ok := s.has(id); ok {
return fmt.Errorf("already exists, %v", id)
}
}
switch pos {
case Before:
return s.insert(0, Before, ids...)
case After:
s.order = append(s.order, ids...)
default:
return fmt.Errorf("invalid position, %v", int(pos))
}
return nil
}
// Insert injects an item before or after the relative item. Returns
// an error if the relative item does not exist.
func (s *relativeOrder) Insert(relativeTo string, pos RelativePosition, ids ...string) error {
if len(ids) == 0 {
return nil
}
for _, id := range ids {
if _, ok := s.has(id); ok {
return fmt.Errorf("already exists, %v", id)
}
}
i, ok := s.has(relativeTo)
if !ok {
return fmt.Errorf("not found, %v", relativeTo)
}
return s.insert(i, pos, ids...)
}
// Swap will replace the item id with the to item. Returns an
// error if the original item id does not exist. Allows swapping out an
// item for another item with the same id.
func (s *relativeOrder) Swap(id, to string) error {
i, ok := s.has(id)
if !ok {
return fmt.Errorf("not found, %v", id)
}
if _, ok = s.has(to); ok && id != to {
return fmt.Errorf("already exists, %v", to)
}
s.order[i] = to
return nil
}
func (s *relativeOrder) Remove(id string) error {
i, ok := s.has(id)
if !ok {
return fmt.Errorf("not found, %v", id)
}
s.order = append(s.order[:i], s.order[i+1:]...)
return nil
}
func (s *relativeOrder) List() []string {
return s.order
}
func (s *relativeOrder) Clear() {
s.order = s.order[0:0]
}
func (s *relativeOrder) insert(i int, pos RelativePosition, ids ...string) error {
switch pos {
case Before:
n := len(ids)
var src []string
if n <= cap(s.order)-len(s.order) {
s.order = s.order[:len(s.order)+n]
src = s.order
} else {
src = s.order
s.order = make([]string, len(s.order)+n)
copy(s.order[:i], src[:i]) // only when allocating a new slice do we need to copy the front half
}
copy(s.order[i+n:], src[i:])
copy(s.order[i:], ids)
case After:
if i == len(s.order)-1 || len(s.order) == 0 {
s.order = append(s.order, ids...)
} else {
s.order = append(s.order[:i+1], append(ids, s.order[i+1:]...)...)
}
default:
return fmt.Errorf("invalid position, %v", int(pos))
}
return nil
}
func (s *relativeOrder) has(id string) (i int, found bool) {
for i := 0; i < len(s.order); i++ {
if s.order[i] == id {
return i, true
}
}
return 0, false
}
|
