|
1 "{ Package: 'stx:libbasic2' }" |
|
2 |
|
3 "{ NameSpace: Smalltalk }" |
|
4 |
|
5 Collection subclass:#SkipList |
|
6 instanceVariableNames:'sortBlock pointers numElements level splice' |
|
7 classVariableNames:'Rand' |
|
8 poolDictionaries:'' |
|
9 category:'Collections-Ordered-Trees' |
|
10 ! |
|
11 |
|
12 SkipList comment:'From "Skip Lists: A Probabilistic Alternative to Balanced Trees" by William Pugh ( http://epaperpress.com/sortsearch/download/skiplist.pdf ): |
|
13 |
|
14 "Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforcing balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees." |
|
15 |
|
16 Notes: |
|
17 |
|
18 The elements of the skip list must implement #< or you must provide a sort block. |
|
19 |
|
20 ' |
|
21 ! |
|
22 |
|
23 !SkipList class methodsFor:'documentation'! |
|
24 |
|
25 documentation |
|
26 " |
|
27 From 'Skip Lists: A Probabilistic Alternative to Balanced Trees' by William Pugh |
|
28 ( http://epaperpress.com/sortsearch/download/skiplist.pdf ): |
|
29 |
|
30 Skip lists are a data structure that can be used in place of balanced trees. |
|
31 Skip lists use probabilistic balancing rather than strictly enforcing balancing |
|
32 and as a result the algorithms for insertion and deletion in skip lists are much simpler |
|
33 and significantly faster than equivalent algorithms for balanced trees. |
|
34 |
|
35 Notes: |
|
36 |
|
37 The elements of the skip list must implement #< or you must provide a sort block. |
|
38 " |
|
39 ! ! |
|
40 |
|
41 !SkipList class methodsFor:'instance creation'! |
|
42 |
|
43 maxLevel: maxLevel |
|
44 " |
|
45 SkipList maxLevel: 5 |
|
46 " |
|
47 ^ super new initialize: maxLevel |
|
48 ! |
|
49 |
|
50 maxLevel: anInteger sortBlock: aBlock |
|
51 ^ (self maxLevel: anInteger) sortBlock: aBlock |
|
52 ! |
|
53 |
|
54 new |
|
55 " |
|
56 SkipList new |
|
57 " |
|
58 ^ super new initialize: 10 |
|
59 ! |
|
60 |
|
61 new: anInteger |
|
62 ^ self maxLevel: (anInteger log: 2) ceiling |
|
63 ! |
|
64 |
|
65 new: anInteger sortBlock: aBlock |
|
66 ^ (self new: anInteger) sortBlock: aBlock |
|
67 ! |
|
68 |
|
69 sortBlock: aBlock |
|
70 ^ self new sortBlock: aBlock |
|
71 ! ! |
|
72 |
|
73 !SkipList methodsFor:'accessing'! |
|
74 |
|
75 level |
|
76 ^ level |
|
77 ! |
|
78 |
|
79 maxLevel |
|
80 ^ pointers size |
|
81 ! |
|
82 |
|
83 maxLevel: n |
|
84 | newLevel oldPointers | |
|
85 newLevel := n max:level. |
|
86 oldPointers := pointers. |
|
87 pointers := Array new:newLevel. |
|
88 splice := Array new:newLevel. |
|
89 1 to: level do: [:i | pointers at: i put: (oldPointers at: i)] |
|
90 |
|
91 "Modified (format): / 18-06-2017 / 17:42:51 / cg" |
|
92 ! |
|
93 |
|
94 size |
|
95 ^ numElements |
|
96 ! |
|
97 |
|
98 sortBlock |
|
99 ^ sortBlock |
|
100 ! |
|
101 |
|
102 sortBlock: aBlock |
|
103 sortBlock := aBlock |
|
104 |
|
105 "Modified (format): / 18-06-2017 / 17:44:44 / cg" |
|
106 ! ! |
|
107 |
|
108 !SkipList methodsFor:'adding'! |
|
109 |
|
110 add: element |
|
111 self add: element ifPresent: nil. |
|
112 ^ element |
|
113 ! |
|
114 |
|
115 add: element ifPresent: aBlock |
|
116 | node lvl s | |
|
117 node := self search:element updating:splice. |
|
118 node notNil ifTrue: [aBlock notNil ifTrue: [^ aBlock value: node]]. |
|
119 lvl := self randomLevel. |
|
120 node := SkipListNode on:element level:lvl. |
|
121 level + 1 to: lvl do: [:i | splice at: i put: self]. |
|
122 1 to: lvl do: [:i | |
|
123 s := splice at:i. |
|
124 node atForward: i put: (s forward: i). |
|
125 s atForward: i put: node]. |
|
126 numElements := numElements + 1. |
|
127 splice atAllPut: nil. |
|
128 ^ element |
|
129 |
|
130 "Modified: / 18-06-2017 / 17:32:23 / cg" |
|
131 ! ! |
|
132 |
|
133 !SkipList methodsFor:'element comparison'! |
|
134 |
|
135 is: element1 equalTo: element2 |
|
136 ^ element1 = element2 |
|
137 ! ! |
|
138 |
|
139 !SkipList methodsFor:'enumerating'! |
|
140 |
|
141 do: aBlock |
|
142 self nodesDo: [:node | aBlock value: node object] |
|
143 ! ! |
|
144 |
|
145 !SkipList methodsFor:'initialization'! |
|
146 |
|
147 initialize: maxLevel |
|
148 pointers := Array new:maxLevel. |
|
149 splice := Array new:maxLevel. |
|
150 numElements := 0. |
|
151 level := 0. |
|
152 Rand ifNil: [Rand := RandomGenerator new] |
|
153 |
|
154 "Modified: / 18-06-2017 / 17:40:56 / cg" |
|
155 ! ! |
|
156 |
|
157 !SkipList methodsFor:'node enumeration'! |
|
158 |
|
159 nodesDo: aBlock |
|
160 | node | |
|
161 node := pointers first. |
|
162 [node notNil] |
|
163 whileTrue: |
|
164 [aBlock value: node. |
|
165 node := node next] |
|
166 |
|
167 "Modified (format): / 18-06-2017 / 17:31:41 / cg" |
|
168 ! ! |
|
169 |
|
170 !SkipList methodsFor:'private'! |
|
171 |
|
172 atForward: i put: node |
|
173 level := node |
|
174 ifNil: [pointers findLast: [:n | n notNil]] |
|
175 ifNotNil: [level max: i]. |
|
176 ^ pointers at: i put: node |
|
177 |
|
178 "Modified (format): / 18-06-2017 / 17:32:30 / cg" |
|
179 ! |
|
180 |
|
181 forward: i |
|
182 ^ pointers at: i |
|
183 ! |
|
184 |
|
185 is: node before: element |
|
186 | object | |
|
187 node isNil ifTrue: [^ false]. |
|
188 object := node object. |
|
189 ^ sortBlock isNil |
|
190 ifTrue: [object < element] |
|
191 ifFalse: [ |
|
192 (self is: object equalTo: element) |
|
193 ifTrue: [ false] |
|
194 ifFalse:[ sortBlock value: object value: element ] |
|
195 ] |
|
196 |
|
197 "Modified: / 18-06-2017 / 17:42:31 / cg" |
|
198 ! |
|
199 |
|
200 is: node theNodeFor: element |
|
201 node isNil ifTrue: [^ false]. |
|
202 node == self ifTrue: [^ false]. |
|
203 ^ self is: node object equalTo: element |
|
204 |
|
205 "Modified: / 18-06-2017 / 17:42:42 / cg" |
|
206 ! |
|
207 |
|
208 next |
|
209 ^ pointers first |
|
210 ! |
|
211 |
|
212 randomLevel |
|
213 | p answer max | |
|
214 p := 0.5. |
|
215 answer := 1. |
|
216 max := self maxLevel. |
|
217 [Rand next < p and: [answer < max]] |
|
218 whileTrue: [answer := answer + 1]. |
|
219 ^ answer |
|
220 |
|
221 "Modified (format): / 18-06-2017 / 17:42:59 / cg" |
|
222 ! |
|
223 |
|
224 search: element updating: array |
|
225 | node forward | |
|
226 node := self. |
|
227 level to: 1 by: -1 do: [:i | |
|
228 [forward := node forward: i. |
|
229 self is: forward before: element] whileTrue: [node := forward]. |
|
230 "At this point: node < element <= forward" |
|
231 array ifNotNil: [array at: i put: node]]. |
|
232 node := node next. |
|
233 ^ (self is: node theNodeFor: element) |
|
234 ifTrue: [node] |
|
235 ifFalse:[nil] |
|
236 |
|
237 "Modified: / 18-06-2017 / 17:44:37 / cg" |
|
238 ! ! |
|
239 |
|
240 !SkipList methodsFor:'removing'! |
|
241 |
|
242 remove: element ifAbsent: aBlock |
|
243 | node i s | |
|
244 node := self search:element updating:splice. |
|
245 node isNil ifTrue:[ |
|
246 ^ aBlock value |
|
247 ]. |
|
248 i := 1. |
|
249 [s := splice at:i. |
|
250 i <= level and: [(s forward: i) == node]] whileTrue: [ |
|
251 s atForward: i put: (node forward: i). |
|
252 i := i + 1 |
|
253 ]. |
|
254 numElements := numElements - 1. |
|
255 splice atAllPut: nil. |
|
256 ^ node object |
|
257 |
|
258 "Modified (format): / 18-06-2017 / 17:43:30 / cg" |
|
259 ! |
|
260 |
|
261 removeAll |
|
262 pointers atAllPut: nil. |
|
263 splice atAllPut: nil. |
|
264 numElements := 0. |
|
265 level := 0. |
|
266 |
|
267 "Modified (format): / 18-06-2017 / 17:43:39 / cg" |
|
268 ! ! |
|
269 |
|
270 !SkipList methodsFor:'testing'! |
|
271 |
|
272 includes: element |
|
273 ^ (self search: element updating: nil) notNil |
|
274 ! |
|
275 |
|
276 isEmpty |
|
277 ^ numElements = 0 |
|
278 ! ! |
|
279 |
|
280 !SkipList class methodsFor:'documentation'! |
|
281 |
|
282 version |
|
283 ^ '$Header$' |
|
284 ! |
|
285 |
|
286 version_CVS |
|
287 ^ '$Header$' |
|
288 ! ! |
|
289 |