-
Notifications
You must be signed in to change notification settings - Fork 0
/
ds.go
240 lines (221 loc) · 9.04 KB
/
ds.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
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
// Package gods provides core interfaces and functions for data structures.
package gods
// Container is a basic interface that all data structures implement.
type Container interface {
// Empty indicates if the Container is empty.
Empty() bool
// Size retrieves Container size.
Size() int
// Clear resets Container, it will be empty with size 0.
Clear()
}
// IndexRangerFunc is an iteration function for ranging an IndexRanger.
type IndexRangerFunc func(index int, value interface{}) bool
// IndexRanger enables to traverse a Container with an IndexRangerFunc.
type IndexRanger interface {
// RangeWithIndex iterates a Container with an IndexRangerFunc.
// Stop iterating if the IndexRangerFunc returns false.
RangeWithIndex(IndexRangerFunc)
}
// KeyRangerFunc is an iteration function for ranging a KeyRanger.
type KeyRangerFunc func(key interface{}) bool
// KeyRanger enables to traverse a Container with a KeyRangerFunc.
type KeyRanger interface {
// RangeWithKey iterates a Container with a KeyRangerFunc.
// Stop iterating if the KeyRangerFunc returns false.
RangeWithKey(KeyRangerFunc)
}
// KVRangerFunc is an iteration function for ranging a KVRanger.
type KVRangerFunc func(key, value interface{}) bool
// KVRanger enables to traverse a Container with a KVRangerFunc.
type KVRanger interface {
// RangeKV iterates a Container with a KVRangerFunc.
// Stop iterating if the KVRangerFunc returns false.
RangeKV(KVRangerFunc)
}
// Peeker gives access to the top without modifying the Container.
type Peeker interface {
// Peek inspects topmost element of Container without modifying the Container.
// Returns (nil, false) if the Container is empty.
Peek() (interface{}, bool)
}
// Stack represents a last-in-first-out (LIFO) data structure provides
// the principal push and pop operations, as well as a method to peek at the
// top element on the stack.
type Stack interface {
Container
Peeker
// Push adds an element to the top of Stack.
Push(interface{})
// Pop ejects the most recently added element that was not yet removed
// and removes it.
Pop() interface{}
}
// Queue represents a first-in-first-out (FIFO) data structure.
type Queue interface {
Container
Peeker
// Push appends an element to the end of Queue.
Push(interface{})
// Pop ejects the start element of Queue and removes it.
Pop() interface{}
}
// Deque aka double-ends queue is an abstract data structure that
// generalizes a queue, for which elements can be added to or
// removed from either the front (head) or back (tail)
type Deque interface {
Container
// PushFront appends an element to the front of Deque.
PushFront(interface{})
// PopFront ejects the start element of Deque and removes it.
PopFront() interface{}
// PeekFront inspects the start element of Deque without modifying
// the Deque. Returns (nil, false) if the Deque is empty.
PeekFront() (interface{}, bool)
// PushBack appends an element to the back of Deque.
PushBack(interface{})
// PopBack ejects the end element of Deque and removes it.
PopBack() interface{}
// PeekBack inspects the end element of Deque without modifying
// the Deque. Returns (nil, false) if the Deque is empty.
PeekBack() (interface{}, bool)
}
// PriorityQueue is an abstract data structure similar to a regular
// Queue in which each element additionally has a "priority"
// associated with it.
//
// In a priority queue, an element with high priority is served before
// an element with low priority.
type PriorityQueue interface {
Container
Peeker
// Push appends an element to the PriorityQueue.
Push(interface{})
// Pop ejects the highest "priority" element of PriorityQueue, and
// removes it.
Pop() interface{}
}
// MonotoneQueue is a variant of the priority queue abstract structure
// in which the priorities of extracted elements are required to form a
// monotonic sequence. That is, for a priority queue in which each
// successively extracted item is the one with the minimum priority (a min-heap),
// the minimum priority should be monotonically increasing. Conversely for
// a max-heap the maximum priority should be monotonically decreasing.
//
// A necessary and sufficient condition on a MonotoneQueue is that one never
// attempts to add an element with lower priority than the most recently
// extracted one.
type MonotoneQueue interface {
Container
Peeker
// Push appends an element to the end of MonotoneQueue if it makes the
// queue still monotony, and removes lower priority elements if necessary.
Push(interface{})
// Pop ejects the start element of MonotoneQueue and removes it.
Pop() interface{}
}
// Set is an abstract data structure that can store unique values.
type Set interface {
Container
// Add adds the elements to Set, if they are not present already.
Add(...interface{}) Set
// Has checks whether the element is in the Set.
Has(interface{}) bool
// Delete removes the elements from Set, if they are present.
Delete(...interface{})
}
// Map is an abstract data structure composed of a Container of
// (key, value) pairs, such that each possible key appears at most
// once in the Container.
type Map interface {
Container
// Add adds a new (key,value) pair to the Map, mapping
// the new key to its new value.
Add(interface{}, interface{}) Map
// Get finds the value (if any) that is bound to a given key.
Get(interface{}) (interface{}, bool)
// Has checks whether the key is in the Map.
Has(interface{}) bool
// Delete removes a (key,value) pair from the Map, unmapping
// a given key from its value.
Delete(interface{})
}
// Tree is an abstract data structure that simulates a hierarchical
// tree structure, with a root value and subtrees of children with
// a parent node, represented as a set of linked nodes.
type Tree interface {
Container
// Size is the numbers of nodes in the Tree, aka degree.
Size() int
// Height is the length of the longest downward path to a leaf
// from the root.
Height() int
}
// Slice is a slice wrapper which provides various handy methods.
type Slice interface {
Container
IndexRanger
// Raw returns the raw slice of Slice.
Raw() []interface{}
// Pop removes the last element from a Slice and returns it.
// Returns (nil, false) if there is no more element.
Pop() (interface{}, bool)
// PopFront removes the first element from a Slice and returns it.
// Returns (nil, false) if there is no more element.
PopFront() (interface{}, bool)
// Append appends new elements to the end of a Slice.
Append(...interface{}) Slice
// Prepend inserts new elements at the start of a Slice.
Prepend(...interface{}) Slice
// Concat combines two Slices.
Concat(slice Slice) Slice
// Reverse reverses the elements in a Slice in place.
Reverse() Slice
// Sort sorts a Slice in place.
Sort(compare func(raw []interface{}, i, j int) bool) Slice
// Slice returns a copy of a section of a Slice.
Slice(...int) Slice
// Splice removes elements from a Slice and, if necessary, inserts
// new elements in their place, returning the deleted elements.
// Remove all elements after the start position(including start one)
// if deleteCount is -1.
Splice(start int, deleteCount int, elements ...interface{}) Slice
// Map projects every element in Slice with the projection function
// and returns a Slice that contains all the results.
Map(project func(interface{}) interface{}) Slice
// Filter returns the elements of a Slice that meet the condition
// specified in a predicate function.
Filter(predicate func(interface{}) bool) Slice
// Reject returns the elements of a Slice that does not meet the
// condition specified in a predicate function.
Reject(predicate func(interface{}) bool) Slice
// Every determines whether all the elements of a Slice satisfy the
// specified predicate function.
Every(predicate func(interface{}) bool) bool
// Some determines whether the specified predicate function returns
// true for any element of a Slice.
Some(predicate func(interface{}) bool) bool
// Reduce calls the specified callback function for all the elements in a Slice.
// The return value of the callback function is the accumulated result, and is
// provided as an argument in the next call to the callback function.
Reduce(fn func(previousValue, currentValue interface{}, currentIndex int) interface{}, initialValue interface{}) interface{}
// ReduceRight calls the specified callback function for all the elements in
// a Slice, in descending order. The return value of the callback function is the
// accumulated result, and is provided as an argument in the next call to the
// callback function.
ReduceRight(fn func(previousValue, currentValue interface{}, currentIndex int) interface{}, initialValue interface{}) interface{}
}
// Slicer can convert all elements in a Container to a Slice.
type Slicer interface {
// ToSlice returns a Slice with all elements in the Container.
ToSlice() Slice
}
// Comparer is an interface has a Compare method for a ordered Container. It can carry
// value and is comparable to other Comparer items.
type Comparer interface {
// Compare compares itself to other item and returns:
// negative self < other
// zero self == other
// positive self > other
Compare(other Comparer) int
}