author | Tony Garnock-Jones <tonyg@kcbbs.gen.nz> |
Thu, 31 Mar 2005 01:25:02 +1200 | |
changeset 0 | ea4e1a00864c |
permissions | -rw-r--r-- |
0
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
1 |
;; Splay trees, partly from Chris Okasaki's "Purely Functional Data |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
2 |
;; Structures" but mostly from Tom Lord's "Hackerlab" C library |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
3 |
;; implementation. |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
4 |
;; |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
5 |
;; The Hackerlab implementation is a bit buggy (eg. the implementation |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
6 |
;; of delete-root and raise) so its been useful mainly as an |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
7 |
;; implementation template - I've had to reverify the actual |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
8 |
;; algorithms from scratch to make sure they're correct here. |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
9 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
10 |
;; Algebraic data type; we use '() as the empty tree. |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
11 |
(define-record-type bst-node |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
12 |
(make-bst-node element left right) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
13 |
bst-node? |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
14 |
(element bst-node-element) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
15 |
(left bst-node-left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
16 |
(right bst-node-right)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
17 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
18 |
(define (bst? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
19 |
(or (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
20 |
(bst-node? t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
21 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
22 |
(define (binary-curry f a) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
23 |
(lambda (b) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
24 |
(f a b))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
25 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
26 |
;; Suggested API, from Tom Lord's Hackerlab splay trees: |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
27 |
;; |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
28 |
;; (splay-tree-singleton x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
29 |
;; (splay-tree-find-raw predcmp tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
30 |
;; (splay-tree-find-min tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
31 |
;; (splay-tree-find-max tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
32 |
;; (splay-tree-raise predcmp tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
33 |
;; (splay-tree-raise-min tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
34 |
;; (splay-tree-raise-max tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
35 |
;; (splay-tree-insert-after tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
36 |
;; (splay-tree-insert-before tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
37 |
;; (splay-tree-delete-root tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
38 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
39 |
(define (splay-tree-singleton x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
40 |
(make-bst-node x '() '())) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
41 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
42 |
;; Non-splaying search: returns a bst node, or #f |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
43 |
(define (splay-tree-find-raw predcmp tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
44 |
(let walk ((tree tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
45 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
46 |
#f |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
47 |
(let ((order (predcmp (bst-node-element tree)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
48 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
49 |
((negative? order) (walk (bst-node-left tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
50 |
((positive? order) (walk (bst-node-right tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
51 |
(else tree)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
52 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
53 |
(define (splay-tree-find-min tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
54 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
55 |
#f |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
56 |
(let walk ((tree tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
57 |
(let ((left (bst-node-left tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
58 |
(if (null? left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
59 |
tree |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
60 |
(walk left)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
61 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
62 |
(define (splay-tree-find-max tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
63 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
64 |
#f |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
65 |
(let walk ((tree tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
66 |
(let ((right (bst-node-right tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
67 |
(if (null? right) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
68 |
tree |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
69 |
(walk right)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
70 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
71 |
(define (splay-tree-raise cmp-pivot tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
72 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
73 |
tree |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
74 |
(let walk ((tree tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
75 |
(let* ((element (bst-node-element tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
76 |
(left (bst-node-left tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
77 |
(right (bst-node-right tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
78 |
(order (cmp-pivot element))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
79 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
80 |
((negative? order) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
81 |
(if (null? left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
82 |
tree |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
83 |
(let* ((element2 (bst-node-element left)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
84 |
(left2 (bst-node-left left)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
85 |
(right2 (bst-node-right left)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
86 |
(order2 (cmp-pivot element2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
87 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
88 |
((and (negative? order2) (bst-node? left2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
89 |
(let ((new2 (walk left2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
90 |
(make-bst-node (bst-node-element new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
91 |
(bst-node-left new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
92 |
(make-bst-node element2 |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
93 |
(bst-node-right new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
94 |
(make-bst-node element right2 right))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
95 |
((and (positive? order2) (bst-node? right2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
96 |
(let ((new2 (walk right2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
97 |
(make-bst-node (bst-node-element new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
98 |
(make-bst-node element2 left2 (bst-node-left new2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
99 |
(make-bst-node element (bst-node-right new2) right)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
100 |
(else (make-bst-node element2 left2 (make-bst-node element right2 right))))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
101 |
((positive? order) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
102 |
(if (null? right) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
103 |
tree |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
104 |
(let* ((element2 (bst-node-element right)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
105 |
(left2 (bst-node-left right)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
106 |
(right2 (bst-node-right right)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
107 |
(order2 (cmp-pivot element2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
108 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
109 |
((and (negative? order2) (bst-node? left2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
110 |
(let ((new2 (walk left2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
111 |
(make-bst-node (bst-node-element new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
112 |
(make-bst-node element left (bst-node-left new2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
113 |
(make-bst-node element2 (bst-node-right new2) right2)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
114 |
((and (positive? order2) (bst-node? right2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
115 |
(let ((new2 (walk right2))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
116 |
(make-bst-node (bst-node-element new2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
117 |
(make-bst-node element2 |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
118 |
(make-bst-node element left left2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
119 |
(bst-node-left new2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
120 |
(bst-node-right new2)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
121 |
(else (make-bst-node element2 (make-bst-node element left left2) right2)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
122 |
(else tree)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
123 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
124 |
(define (splay-tree-raise-min tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
125 |
(splay-tree-raise (lambda (v) -1) tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
126 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
127 |
(define (splay-tree-raise-max tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
128 |
(splay-tree-raise (lambda (v) 1) tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
129 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
130 |
(define (splay-tree-insert-after tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
131 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
132 |
((null? tree) (splay-tree-singleton x)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
133 |
(else (make-bst-node x |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
134 |
(make-bst-node (bst-node-element tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
135 |
(bst-node-left tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
136 |
'()) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
137 |
(bst-node-right tree))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
138 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
139 |
(define (splay-tree-insert-before tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
140 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
141 |
((null? tree) (splay-tree-singleton x)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
142 |
(else (make-bst-node x |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
143 |
(bst-node-left tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
144 |
(make-bst-node (bst-node-element tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
145 |
'() |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
146 |
(bst-node-right tree)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
147 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
148 |
;; Well, I invented this algorithm. Chances are it's inefficient, or |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
149 |
;; it doesn't work, or both. |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
150 |
(define (splay-tree-delete-root tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
151 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
152 |
(error "Cannot delete root of empty splay tree") |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
153 |
(let* ((left (bst-node-left tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
154 |
(right (bst-node-right tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
155 |
(new-left (splay-tree-raise-max left))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
156 |
(if (null? new-left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
157 |
right |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
158 |
(if (null? (bst-node-right new-left)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
159 |
(let ((new-tree (make-bst-node (bst-node-element new-left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
160 |
(bst-node-left new-left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
161 |
right))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
162 |
;;(pretty-print (list 'DEL |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
163 |
;;(bst->alist tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
164 |
;;(bst->alist new-tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
165 |
new-tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
166 |
(error "Invariant violation: need null right on max-raised splay tree" |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
167 |
(list (bst->alist left) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
168 |
(bst->alist new-left)))))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
169 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
170 |
(define (splay-tree-insert cmp-pivot tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
171 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
172 |
(splay-tree-singleton x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
173 |
(let ((new-tree (splay-tree-raise cmp-pivot tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
174 |
(if (positive? (cmp-pivot (bst-node-element new-tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
175 |
(splay-tree-insert-after new-tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
176 |
(splay-tree-insert-before new-tree x))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
177 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
178 |
(define (splay-tree-insert/replace cmp-pivot tree x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
179 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
180 |
(splay-tree-singleton x) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
181 |
(let* ((new-tree (splay-tree-raise cmp-pivot tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
182 |
(order (cmp-pivot (bst-node-element new-tree)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
183 |
(cond |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
184 |
((negative? order) (splay-tree-insert-before new-tree x)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
185 |
((positive? order) (splay-tree-insert-after new-tree x)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
186 |
(else (make-bst-node x (bst-node-left new-tree) (bst-node-right new-tree))))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
187 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
188 |
(define (splay-tree-find predcmp tree k-found k-notfound) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
189 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
190 |
(k-notfound tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
191 |
(let ((new-tree (splay-tree-raise predcmp tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
192 |
(if (zero? (predcmp (bst-node-element new-tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
193 |
(k-found new-tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
194 |
(k-notfound new-tree))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
195 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
196 |
(define (splay-tree-delete predcmp tree k-found . opt-k-notfound) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
197 |
(let ((k-notfound (if (null? opt-k-notfound) k-found (car opt-k-notfound)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
198 |
(if (null? tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
199 |
(k-notfound tree) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
200 |
(let ((new-tree (splay-tree-raise predcmp tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
201 |
(if (zero? (predcmp (bst-node-element new-tree))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
202 |
(k-found (splay-tree-delete-root new-tree)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
203 |
(k-notfound new-tree)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
204 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
205 |
(define (bst->list t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
206 |
(let walk ((t t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
207 |
(acc '())) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
208 |
(if (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
209 |
acc |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
210 |
(walk (bst-node-left t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
211 |
(cons (bst-node-element t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
212 |
(walk (bst-node-right t) acc)))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
213 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
214 |
(define (bst->alist t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
215 |
(let ((v (let walk ((t t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
216 |
(if (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
217 |
(cons 0 t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
218 |
(let ((l (walk (bst-node-left t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
219 |
(r (walk (bst-node-right t)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
220 |
(list (+ (max (car l) (car r)) 1) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
221 |
(bst-node-element t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
222 |
(cdr l) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
223 |
(cdr r))))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
224 |
`((height ,(car v)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
225 |
(tree ,(cdr v))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
226 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
227 |
(define (bst-height t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
228 |
(if (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
229 |
0 |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
230 |
(+ (max (bst-height (bst-node-left t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
231 |
(bst-height (bst-node-right t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
232 |
1))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
233 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
234 |
(define (bst-size t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
235 |
(if (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
236 |
0 |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
237 |
(+ (bst-size (bst-node-left t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
238 |
(bst-size (bst-node-right t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
239 |
1))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
240 |
|
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
241 |
(define (splay-tree-tests) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
242 |
(define (test) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
243 |
(let ((remove (lambda (i t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
244 |
(splay-tree-delete (binary-curry - i) t |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
245 |
(lambda (t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
246 |
(pretty-print (list 'FOUND i (bst->alist t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
247 |
t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
248 |
(lambda (t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
249 |
(pretty-print (list 'NOTFOUND i (bst->alist t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
250 |
t))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
251 |
(let* ((t '()) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
252 |
(t (do ((i 0 (+ i 1)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
253 |
(t t (splay-tree-insert (lambda (b) (- (- 50 i) b)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
254 |
(splay-tree-insert - t i) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
255 |
(- 50 i)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
256 |
((= i 10) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
257 |
(pretty-print (list 'FINALINS (bst->alist t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
258 |
t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
259 |
(pretty-print (list 'INTERIM i (bst->alist t))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
260 |
(t (do ((i 0 (+ i 2)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
261 |
(t t (remove i (remove (- 50 i 1) t)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
262 |
((> i 50) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
263 |
(pretty-print (list 'FINALDEL (bst->alist t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
264 |
t)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
265 |
'done))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
266 |
(require 'srfi-1) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
267 |
(define (test2) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
268 |
(let ((t (time (do ((i 0 (+ i 1)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
269 |
(t '() (let ((v (random 10000))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
270 |
(splay-tree-insert (lambda (b) (- v b)) t v)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
271 |
((= i 10000) t))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
272 |
(pretty-print (bst-height t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
273 |
(let* ((oldt t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
274 |
(t (time (do ((i 0 (+ i 1)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
275 |
(t t (splay-tree-find (binary-curry - (random 10000)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
276 |
t |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
277 |
(lambda (t) t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
278 |
(lambda (t) t)))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
279 |
((= i 50000) t))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
280 |
(pretty-print (bst-height t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
281 |
(pretty-print (eq? t oldt)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
282 |
(time |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
283 |
(let loop ((t t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
284 |
(if (null? t) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
285 |
(pretty-print (bst-height t)) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
286 |
(let ((new-t (splay-tree-raise-min t))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
287 |
(loop (splay-tree-delete-root new-t))))))))) |
ea4e1a00864c
Initial version, from TLA arch@eighty-twenty.org--2004/smalltalk-tng--main--0--version-0
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff
changeset
|
288 |
(test2)) |