-
Notifications
You must be signed in to change notification settings - Fork 319
/
omap.go
211 lines (189 loc) · 4.92 KB
/
omap.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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
package map1
import (
"bytes"
"fmt"
"reflect"
)
// 有序的Map的接口类型。
type OrderedMap interface {
GenericMap // 泛化的Map接口
// 获取第一个键值。若无任何键值对则返回nil。
FirstKey() interface{}
// 获取最后一个键值。若无任何键值对则返回nil。
LastKey() interface{}
// 获取由小于键值toKey的键值所对应的键值对组成的OrderedMap类型值。
HeadMap(toKey interface{}) OrderedMap
// 获取由小于键值toKey且大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。
SubMap(fromKey interface{}, toKey interface{}) OrderedMap
// 获取由大于等于键值fromKey的键值所对应的键值对组成的OrderedMap类型值。
TailMap(fromKey interface{}) OrderedMap
}
type myOrderedMap struct {
keys Keys
elemType reflect.Type
m map[interface{}]interface{}
}
func (omap *myOrderedMap) Get(key interface{}) interface{} {
return omap.m[key]
}
func (omap *myOrderedMap) isAcceptableElem(e interface{}) bool {
if e == nil {
return false
}
if reflect.TypeOf(e) != omap.elemType {
return false
}
return true
}
func (omap *myOrderedMap) Put(key interface{}, elem interface{}) (interface{}, bool) {
if !omap.isAcceptableElem(elem) {
return nil, false
}
oldElem, ok := omap.m[key]
omap.m[key] = elem
if !ok {
omap.keys.Add(key)
}
return oldElem, true
}
func (omap *myOrderedMap) Remove(key interface{}) interface{} {
oldElem, ok := omap.m[key]
delete(omap.m, key)
if ok {
omap.keys.Remove(key)
}
return oldElem
}
func (omap *myOrderedMap) Clear() {
omap.m = make(map[interface{}]interface{})
omap.keys.Clear()
}
// 获取键值对的数量
func (omap *myOrderedMap) Len() int {
return len(omap.m)
}
func (omap *myOrderedMap) Contains(key interface{}) bool {
_, ok := omap.m[key]
return ok
}
func (omap *myOrderedMap) FirstKey() interface{} {
if omap.Len() == 0 {
return nil
}
return omap.keys.Get(0)
}
func (omap *myOrderedMap) LastKey() interface{} {
length := omap.Len()
if length == 0 {
return nil
}
return omap.keys.Get(length - 1)
}
func (omap *myOrderedMap) SubMap(fromKey interface{}, toKey interface{}) OrderedMap {
newOmap := &myOrderedMap{
keys: NewKeys(omap.keys.CompareFunc(), omap.keys.ElemType()),
elemType: omap.elemType,
m: make(map[interface{}]interface{})}
omapLen := omap.Len()
if omapLen == 0 {
return newOmap
}
beginIndex, contains := omap.keys.Search(fromKey)
if !contains {
beginIndex = 0
}
endIndex, contains := omap.keys.Search(toKey)
if !contains {
endIndex = omapLen
}
var key, elem interface{}
for i := beginIndex; i < endIndex; i++ {
key = omap.keys.Get(i)
elem = omap.m[key]
newOmap.Put(key, elem)
}
return newOmap
}
func (omap *myOrderedMap) HeadMap(toKey interface{}) OrderedMap {
return omap.SubMap(nil, toKey)
}
func (omap *myOrderedMap) TailMap(fromKey interface{}) OrderedMap {
return omap.SubMap(fromKey, nil)
}
func (omap *myOrderedMap) Keys() []interface{} {
initialLen := omap.keys.Len()
keys := make([]interface{}, initialLen)
actualLen := 0
for _, key := range omap.keys.GetAll() {
if actualLen < initialLen {
keys[actualLen] = key
} else {
keys = append(keys, key)
}
actualLen++
}
if actualLen < initialLen {
keys = keys[:actualLen]
}
return keys
}
func (omap *myOrderedMap) Elems() []interface{} {
initialLen := omap.Len()
elems := make([]interface{}, initialLen)
actualLen := 0
for _, key := range omap.keys.GetAll() {
elem := omap.m[key]
if actualLen < initialLen {
elems[actualLen] = elem
} else {
elems = append(elems, elem)
}
actualLen++
}
if actualLen < initialLen {
elems = elems[:actualLen]
}
return elems
}
func (omap *myOrderedMap) ToMap() map[interface{}]interface{} {
replica := make(map[interface{}]interface{})
for k, v := range omap.m {
replica[k] = v
}
return replica
}
func (omap *myOrderedMap) KeyType() reflect.Type {
return omap.keys.ElemType()
}
func (omap *myOrderedMap) ElemType() reflect.Type {
return omap.elemType
}
func (omap *myOrderedMap) String() string {
var buf bytes.Buffer
buf.WriteString("OrderedMap<")
buf.WriteString(omap.keys.ElemType().Kind().String())
buf.WriteString(",")
buf.WriteString(omap.elemType.Kind().String())
buf.WriteString(">{")
first := true
omapLen := omap.Len()
for i := 0; i < omapLen; i++ {
if first {
first = false
} else {
buf.WriteString(" ")
}
key := omap.keys.Get(i)
buf.WriteString(fmt.Sprintf("%v", key))
buf.WriteString(":")
buf.WriteString(fmt.Sprintf("%v", omap.m[key]))
}
buf.WriteString("}")
return buf.String()
}
func NewOrderedMap(keys Keys, elemType reflect.Type) OrderedMap {
return &myOrderedMap{
keys: keys,
elemType: elemType,
m: make(map[interface{}]interface{})}
}