-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.go
187 lines (172 loc) · 4.27 KB
/
index.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
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
package indexer
import (
"fmt"
"math"
"reflect"
"sync"
)
// Index is a single index.
type Index struct {
keys []IndexElement
m sync.RWMutex
t reflect.Type
less []Less
}
//Less defines a single less function for sorting.
type Less func(e1, e2 IndexElement) (bool, error)
//NewIndex creates an Index instance
func NewIndex(t reflect.Type, l ...Less) *Index {
return &Index{
keys: []IndexElement{},
t: t,
less: l,
}
}
//Len returns length of the index
func (in *Index) Len() int {
in.m.RLock()
defer in.m.RUnlock()
return len(in.keys)
}
//Add adds a single IndexElement
func (in *Index) Add(element IndexElement) error {
in.m.Lock()
defer in.m.Unlock()
err := in.addElement(element)
return err
}
//Remove deletes a single IndexElement
func (in *Index) Remove(element IndexElement) error {
in.m.Lock()
defer in.m.Unlock()
if 0 == len(in.keys) {
return fmt.Errorf("There are no elements in index")
}
location := -1
min := len(in.keys)-1
minElement := in.keys[min]
if minElement.Equal(element) {
location = min
}
if -1 == location {
if in.keys[0].Equal(element) {
location = 0
}
}
if -1 == location {
loc, err := in.findInArea(element, 0, min)
if nil != err {
return err
}
location = loc
}
if -1 == location {
return fmt.Errorf("No key %v: %v found", element.Key(), element.Value())
}
keys := make([]IndexElement, min)
keys = append(in.keys[:location], in.keys[location+1:]...)
in.keys = keys
return nil
}
//Keys returns index keys slice.
func (in *Index) Keys() []IndexElement {
keys := make([]IndexElement, len(in.keys))
in.m.RLock()
defer in.m.RUnlock()
copy(keys, in.keys)
return keys
}
//ModifyLess changes the less functions.
func (in *Index) ModifyLess(l ...Less) error {
in.m.Lock()
defer in.m.Unlock()
in.less = l
keyCopy := make([]IndexElement, len(in.keys))
copy(keyCopy, in.keys)
in.keys = make([]IndexElement, 0)
for _, element := range keyCopy {
in.addElement(element)
}
return nil
}
//addElement adds a single IndexElement without a lock
func (in *Index) addElement(element IndexElement) error {
if !reflect.TypeOf(element).ConvertibleTo(in.t) {
return fmt.Errorf("Type %v is not convertible to type %v", reflect.TypeOf(element).Name(), in.t.Name())
}
if len(in.keys) == 0 {
in.keys = append(in.keys, element)
return nil
}
location := -1
bottomElement := in.keys[len(in.keys)-1]
topElement := in.keys[0]
if less, _ := in.isLess(topElement, element); less {
location = 0
} else if less, _ := in.isLess(element, bottomElement); less {
in.keys = append(in.keys, element)
return nil
}
if -1 == location {
location = in.placeInArea(element, 0, len(in.keys)-1)
}
after := make([]IndexElement, len(in.keys[location:]), 2*cap(in.keys[location:]))
copy(after, in.keys[location:])
in.keys = append(in.keys[:location], element)
in.keys = append(in.keys, after...)
return nil
}
//placeInArea finds a place for element in area
func (in *Index) placeInArea(element IndexElement, top, bottom int) int {
if 0 == top && 0 == bottom {
return 0
}
middle := int(math.Ceil(float64((top + bottom) / 2)))
middleElement := in.keys[middle]
if less, _ := in.isLess(element, middleElement); less {
if 1 == bottom-top {
return bottom
}
return in.placeInArea(element, middle, bottom)
}
if 1 == bottom-top {
return top
}
return in.placeInArea(element, top, middle)
}
//findInArea finds an element in the area
func (in *Index) findInArea(element IndexElement, top, bottom int) (int, error) {
middle := int(math.Floor(float64((top + bottom) / 2)))
if middle == top || middle == bottom {
el := in.keys[middle]
if element.Equal(el) {
return middle, nil
}
return -1, nil
}
middleElement := in.keys[middle]
if element.Equal(middleElement) {
return middle, nil
}
lower, err := in.isLess(element, middleElement)
if nil != err {
return -1, err
}
if lower {
return in.findInArea(element, middle, bottom)
}
return in.findInArea(element, top, middle)
}
//isLess returns if the first elemet should be lower than the second one
func (in *Index) isLess(e1, e2 IndexElement) (bool, error) {
less := false
for _, l := range in.less {
isLess, _ := l(e1, e2)
less = isLess
}
return less, nil
}
//swap swaps IndexElements in list
func (in *Index) swap(i, j int) {
in.keys[i], in.keys[j] = in.keys[j], in.keys[i]
}