racket / data

Other
16 stars 23 forks source link

Make splay-tree->list handle non-numeric keys. #29

Closed soegaard closed 1 year ago

soegaard commented 1 year ago

The current splay-tree->list doesn't handle non-numeric keys due to the expression (+ key k*). This PR simply removes the k* variable.

A test case that shows the bug:

#lang racket
(require data/order data/splay-tree)
(define string-order (order 'string-order string? string=? string<?))
(define S (make-splay-tree string-order))
(splay-tree-set! S "foo" 1)
(splay-tree-set! S "bar" 2)
(splay-tree->list S)
rmculpepper commented 1 year ago

That fix doesn't work for adjustable splay trees. Adjustable splay trees store each node's key (which must be numeric) as the difference from its parent's key.

(require data/splay-tree)
(define s (make-adjustable-splay-tree))
(splay-tree-set! s 1 'a)
(splay-tree-set! s 2 'b)
(splay-tree-set! s 3 'c)
(splay-tree->list s)
;; => '((1 . a) (2 . b) (3 . c))

I think the right fix is to change (+ key k*) to (if adjust? (+ key k*) key), but I haven't tested it.

soegaard commented 1 year ago

Yes, that works for both. I'll make a new PR.