-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathskiplists.nim
567 lines (507 loc) · 16.2 KB
/
skiplists.nim
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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
import std/sequtils
import std/hashes
import std/random
from grok import ex
const
skiplistsChecks {.booldefine.} =
# better support for earlier nims in testing?
when defined(release) or defined(danger):
false
else:
true
skiplistsGrowth {.intdefine.} = 4
when (NimMajor, NimMinor) <= (1, 2):
type
SkipListError* = object of IndexError ##
## A specified index that should have existed did not.
SkipListDefect* = object of AssertionError ##
## A defect was detected in the SkipList implementation.
else:
type
SkipListError* = object of IndexDefect ##
## A specified index that should have existed did not.
SkipListDefect* = object of AssertionDefect ##
## A defect was detected in the SkipList implementation.
type
SkipListEmptyError* = object of ValueError ##
## An empty SkipList is invalid for this operation.
EmptySkipListError* {.deprecated.} = SkipListEmptyError ##
## Alias for SkipListEmptyError
SkipListObj*[T] = object
over: SkipList[T]
down: SkipList[T]
value*: T
SkipList*[T] = ref SkipListObj[T]
SkipListCmp*[T] = proc(a, b: SkipList[T]): cmp {.noSideEffect.} ##
## The procedure signature to use for comparing two SkipLists.
SkipListFind*[T] = proc(a: SkipList[T]): cmp {.noSideEffect.} ##
## The procedure signature to use for finding one SkipList.
SkipListPred*[T] = proc(up: SkipList[T]; here: SkipList[T];
child: SkipList[T]): bool ##
## The predicate used to determine whether the SkipList
## will grow during an add() operation.
##
## :up: a larger scope of the SkipList, perhaps top-most
## :here: a narrower scope of the SkipList
## :child: a SkipList holding the new value
cmp* {.pure.} = enum ## Comparisons between SkipLists
Undefined
Less
Equal
More
#
# TODO:
# faster p=.5 version
# slower version that counts search steps for p() solicitation
# version that knows your list index
# lengths, girths, etc.
#
converter toSeq[T](s: SkipList[T]): seq[T]
proc rank*(s: SkipList): int =
## The higher the rank, the shorter the SkipList.
if not s.isNil:
var s = s
while not s.down.isNil:
assert s.down.value == s.value,
"s.down is " & $s.down.value & " while s is " & $s.value
inc result
s = s.down
proc bottom*(s: SkipList): SkipList =
## Traverse to the longest SkipList, which holds all values.
if not s.isNil:
result = s
while not result.down.isNil:
assert result.down.value == result.value
result = result.down
proc newSkipList*[T](value: T): SkipList[T] =
## Instantiate a SkipList from value `value`.
result = SkipList[T](value: value)
proc isEmpty*(s: SkipList): bool =
## True if SkipList `s` holds no items.
result = true
for full in items(s):
result = false
break
proc defaultPred(up: SkipList; here: SkipList; child: SkipList): bool =
result = rand(1 .. skiplistsGrowth) == 1
func `===`*(a, b: SkipList): bool =
## `true` if SkipLists `a` and `b` share the same memory, else `false`.
result = cast[int](a) == cast[int](b)
template `=!=`*(a, b: SkipList): bool =
## `false` if SkipLists `a` and `b` share the same memory, else `true`.
not(a === b)
func `<>`[T](a, b: SkipListObj[T]): cmp =
## Compare SkipListObj `a` and `b`.
if a.value < b.value:
Less
elif a.value == b.value:
Equal
else:
More
func `<>`*[T](a, b: SkipList[T]): cmp =
## Compare SkipList `a` and `b`.
if a.isNil or b.isNil:
if a.isNil and b.isNil:
Equal
else:
Undefined
elif a === b:
Equal
else:
a[] <> b[]
proc `<`*(a, b: SkipList): bool =
## `true` if SkipList `a` is less than SkipList `b`, else `false`.
case a <> b
of Less:
result = true
of Undefined:
raise newException(SkipListEmptyError, "invalid comparison")
else:
result = false
proc `==`*(a, b: SkipList): bool =
## `true` if SkipList `a` is equal to SkipList `b`, else `false`.
case a <> b
of Equal:
result = true
of Undefined:
raise newException(SkipListEmptyError, "invalid comparison")
else:
result = false
# ref equality semantics demand this!
template `<=`*(a, b: SkipList): bool =
## `true` if SkipList `a` is less or equal to SkipList `b`, else `false`.
a < b or a == b
# ref equality semantics demand this!
template `>=`*(a, b: SkipList): bool =
## `true` if SkipList `a` is more or equal to SkipList `b`, else `false`.
a > b or a == b
template iterIt(s: typed; body: untyped) =
if not s.isNil:
var
it {.inject.} = s
while not it.down.isNil:
assert it.value == it.down.value,
$it.value & " out of order iter " & $it.down.value
it = it.down
body
while not it.over.isNil:
assert it.value <= it.over.value,
$it.value & " out of order iter " & $it.over.value
it = it.over
body
iterator rank(s: SkipList): SkipList {.used.} =
## Yield each member of SkipList `s` rank.
var s = s
while not s.isNil:
yield s
s = s.over
iterator file(s: SkipList): SkipList {.used.} =
## Yield each member of SkipList `s` file.
var s = s
while not s.isNil:
yield s
s = s.down
iterator values[T](s: SkipList[T]): string {.used.} =
## Yield each peer value of SkipList `s`.
var s = s
while not s.isNil:
when defined(release):
yield $s.value
else:
if s.down.isNil:
yield $s.value & " x " & $(cast[int](s))
else:
yield $s.value & " d " & $(cast[int](s.down))
s = s.over
proc `$`(s: SkipList): string {.raises: [].} =
## A string representing SkipList `s`; intentionally not exported.
if s.isNil:
result = "\n*[]"
else:
var q = sequtils.toSeq s.values
result = $q
result[0] = '*'
result = "\n" & result
if not s.down.isNil:
result.add $s.down
when defined(release) or not skiplistsChecks:
template checkList(s: SkipList; args: varargs[untyped]) = discard
else:
import std/strutils
proc checkList(s: SkipList; args: varargs[string, `$`]) =
## Check a SkipList for validity; `args` informs error messages.
var msg = join(args, " ")
try:
for r in s.file:
assert r <> s in {Equal}
for n in rank(r):
if not n.over.isNil:
if n.down.isNil:
# dupes are permitted at the bottom
assert n <> n.over in {Less, Equal}
else:
# no dupes in normal rank
assert n <> n.over in {Less}
if not n.down.isNil:
# all members of the rank should have the same, uh, rank
assert n.rank == r.rank
# down links should always be equal
assert n <> n.down in {Equal}
except Exception as e:
if msg.len > 0:
msg &= "; "
msg &= e.msg
echo "check input:\n", $s
raise newException(SkipListDefect, msg)
iterator mitems*[T](s: var SkipList[T]): var T {.ex.} =
## Iterate over mutable entries in SkipList `s`.
runnableExamples:
var s = newSkipList"foo"
for item in mitems(s):
item.add "bar"
for item in items(s):
assert item == "foobar"
iterIt(s):
yield it.value
iterator items*[T](s: SkipList[T]): T {.ex.} =
## Iterate over entries in SkipList `s`.
runnableExamples:
var s = newSkipList 3
for item in items(s):
assert item == 3
iterIt(s):
yield it.value
iterator pairs*[T](s: SkipList[T]): tuple[index: int, value: T] {.ex.} =
## Iterate over entries in SkipList `s`.
runnableExamples:
var s = newSkipList 3
for index, value in pairs(s):
assert index == 0
assert value == 3
var index = 0
iterIt(s):
yield (index: index, value: it.value)
inc index
proc `==`*[T](s: SkipList[T]; q: openArray[T]): bool =
## `true` if SkipList `s` holds the same values as openArray `q`.
block unequal:
var i = 0
for item in items(s):
if i <= high(q):
if item != q[i]:
break unequal
else:
break unequal
inc i
result = i == q.len
proc hash*(s: SkipList): Hash =
## The `Hash` of SkipList `s` is a function of all its values.
var h: Hash = 0
for item in items(s):
h = h !& hash(item)
result = !$h
proc find*[T](s: SkipList[T]; r: var SkipList[T];
compare: SkipListFind[T]): bool =
## Find a SkipList in `s` for which `compare r` yields `Equal`,
## storing the result in `r`;
## returns `true` if the value was found, else `false`.
if not s.isNil:
r = s
if compare(r) == Equal:
result = true
else:
r = s
while true:
case compare(r.over)
of Undefined:
if r.down.isNil:
break
else:
r = r.down
of More:
r = r.over
of Equal:
r = r.over
result = true
break
of Less:
raise newException(SkipListDefect, "out of order")
proc find*[T](s: SkipList[T]; value: SkipList[T]; r: var SkipList[T];
compare: SkipListCmp[T] = `<>`): bool =
## Find the SkipList `value` in SkipList `s`, storing the result in `r`;
## returns `true` if the value was found, else `false`.
func finder(s: SkipList[T]): cmp = compare(value, s)
result = s.find(r, compare = finder)
proc find*[T](s: SkipList[T]; value: T): SkipList[T] =
## Find the SkipList holding `value` in SkipList `s`; raises a KeyError`
## if the value was not found.
if not find(s, SkipList[T](value: value), result):
raise newException(KeyError, "not found")
proc find*[T](s: SkipList[T]; value: T; r: var SkipList[T]): bool =
## Find `value` in SkipList `s`, storing the result in `r`;
## returns `true` if the value was found, else `false`.
result = find(s, SkipList[T](value: value), r)
proc count*(s: SkipList): int {.ex.} =
## Count the number of entries in SkipList `s`.
runnableExamples:
var s: SkipList[int]
assert count(s) == 0
s.add 3
assert count(s) == 1
s.add 5
assert count(s) == 2
if not s.isNil:
inc result
var s = s
while not s.down.isNil:
s = s.down
while not s.over.isNil:
inc result
s = s.over
converter toSeq[T](s: SkipList[T]): seq[T] =
## Convert SkipList `s` into a sequence.
if not s.isNil:
let
size = count(s)
result = newSeqOfCap[T](size)
when false and defined(gcDestructors):
for item in items(s):
assert result.len <= size
add(result, item)
else:
setLen(result, size)
for index, item in pairs(s):
result[index] = item
proc contains[T](s: SkipList[T]; v: SkipList[T]): bool =
## `true` if the SkipList `s` contains SkipList `v`.
var n: SkipList[T]
result = s.find(v, n)
proc contains*[T](s: SkipList[T]; v: T): bool {.ex.} =
## `true` if the SkipList `s` contains value `v`.
runnableExamples:
var s: SkipList[int]
assert 5 notin s
s.add 5
s.add 9
assert 9 in s
assert 5 in s
let n = SkipList[T](value: v)
result = n in s
proc constrain(s: var SkipList; n: SkipList;
narrow: var SkipList; parent: var SkipList;
comp: set[cmp] = {Less, Equal}): cmp =
## Scope SkipList `s` to surround `n`, storing the result in `narrow`
## and a SkipList with a larger rank in `parent`, if possible. Supply
## `comp` to denote satisfactory cmp values for peers.
assert comp - {Less, Equal} == {}
result = s <> n
if result in comp:
narrow = s
var test = result
while test in comp:
assert narrow <> narrow.over in {Less, Equal, Undefined}
test = narrow.over <> n
if test in comp:
narrow = narrow.over
result = test
elif test in {Undefined, More}:
if not narrow.down.isNil:
assert narrow <> narrow.down == Equal, $narrow
parent = narrow
test = constrain(narrow.down, n, narrow, parent, comp)
if test in comp:
result = test
break
elif parent.rank == narrow.rank:
assert false, "probably not what you want"
proc append[T](s: var SkipList[T]; v: T): SkipList[T] {.inline.} =
## The primitive append operation.
assert not s.isNil
assert v >= s.value, "out of order append"
result = s
if s.down.isNil:
s.over = SkipList[T](over: s.over, value: v)
else:
s.over = SkipList[T](over: s.over, value: v,
down: append(s.down, v))
assert s <> s.down == Equal
assert s.over <> s.over.down == Equal
proc insert[T](s: var SkipList[T]; v: T): SkipList[T] {.inline.} =
## The primitive insert operation.
assert not s.isNil
assert v <= s.value, "out of order insert"
if s.down.isNil:
result = SkipList[T](over: s, value: v)
else:
result = SkipList[T](over: s, value: v,
down: insert(s.down, v))
assert result <> result.down == Equal
assert result.over <> result.over.down == Equal
proc remove*[T](s: var SkipList[T]; n: SkipList[T]): bool =
## Remove SkipList `n` from SkipList `s`; returns `true` if `s` changed.
##
## :s: The source SkipList
## :n: The SkipList to remove
var p, parent: SkipList[T]
case constrain(s, n, p, parent, comp = {Less})
of Undefined, More:
discard
of Less:
var q = p.bottom
if q.over <> n in {Equal}:
# dupe exists; only remove the dupe
q.over = q.over.over
result = true
else:
# remove the entire file
if p.over <> n in {Equal}:
result = true
while not p.isNil:
p.over = p.over.over
p = p.down
of Equal:
# we need to mutate s
var q = s.bottom
result = true
if q.over <> q in {Equal}:
# it's a dupe; simple to handle
q.over = q.over.over
else:
# just omit the entire file
s = s.over
proc remove*[T](s: var SkipList[T]; value: T): bool {.discardable.} =
## Remove `value` from SkipList `s`; returns `true` if `s` changed.
result = remove(s, newSkipList value)
checkList s
proc grow*[T](s: var SkipList[T]; n: SkipList[T]): bool =
## `true` if we grew.
var p, parent: SkipList[T]
var c = constrain(s, n, p, parent, comp = {Less})
result = c in {Equal, Less}
case c
of Undefined, More:
discard
of Equal:
assert s.rank == p.rank
assert s <> n == Equal
# add a rank; we're already as tall as possible
s = SkipList[T](value: n.value, down: s)
of Less:
assert p.over <> n in {Equal}
# if s and p aren't the same skiplist but they have the same rank,
if s =!= p and s.rank == p.rank:
# add a rank with s and p nodes
s = SkipList[T](value: s.value, down: s,
over: SkipList[T](value: n.value, down: p.over))
elif s.rank != p.rank:
# confirm that grow received input that was "close"
raise newException(SkipListDefect, "s.rank != p.rank")
elif parent.isNil:
# essentially, add a rank with s and p values
s = SkipList[T](value: s.value, down: s,
over: SkipList[T](value: n.value, down: p.over))
# this is a non-recursive append, basically
else:
parent.over = SkipList[T](value: n.value, over: parent.over)
proc add[T](s: var SkipList[T]; n: SkipList[T]; pred: SkipListPred[T]) =
## Add SkipList `n` into SkipList `s`.
if s.isNil:
s = n
else:
var p, parent: SkipList[T]
case constrain(s, n, p, parent, comp = {Less})
of Undefined:
discard
of More:
# create a new file for this value
s = insert(s, n.value)
of Equal:
# the head is equal to the new value
# just append it at the bottom; dupes don't make good indices
p = s.bottom
discard append(p, n.value)
of Less:
# go ahead and append it
discard append(p, n.value)
if parent.isNil:
parent = s
while pred(parent, p, n):
discard grow(parent, n)
proc add*[T](s: var SkipList[T]; v: T; pred: SkipListPred[T] = defaultPred) =
## Add a value `v` into SkipList `s`.
add(s, SkipList[T](value: v), pred = pred)
checkList s, "add()"
proc toSkipList*[T](values: openArray[T] = @[]): SkipList[T] =
## Create a SkipList from an openArray `values`.
for item in items(values):
if result.isNil:
result = newSkipList(item)
else:
add(result, item)
checkList result, "toSkipList()"
proc clear*(s: var SkipList) =
## Empty SkipList `s` of all entries.
s = nil
template append*[T](s: var SkipList[T]; value: T) =
## Alias for `add(s, value)`.
add(s, value)