search

cgswords / racket-rrb

Racket RRB Tree Implementation
MIT License
10 stars 1 forks source link

General persistance #15

Closed sizur closed 10 years ago

sizur commented 10 years ago

Docs say rrb-set is persistent. Are concat and push persistent as well? If not, maybe we need a rrb-clone?

rrb-split-at and rrb-insert-at also need to have persistence if possible.

cgswords commented 10 years ago

IIRC, the entire data structure is persistent. Push uses vector-append to make new vectors, and concat duplicates nodes as it changes the tree, but I am not certain they are perfectly persistent.

I should write a test case or six to verify this.

I can provide rrb-clone fairly easily, and will do it soon.

sizur commented 10 years ago

If everything is persistent, then clone will only confuse people. Let's wait for tests to show us the light :)

cgswords commented 10 years ago

I pushed two tests that seem to suggest push and concat are persistent:

(check-equal?
  (let* ((tree (rrb-set-pairs (for/list ([i (in-range 0 375)]) (cons i 0)) tree1234a))
         (tree1 (rrb-push 50 tree))
         (tree2 (rrb-push 50 tree)))
    (eq? tree1 tree2))
  #f
  "Persistance check 1")

(check-equal?
  (let ((tree1 (rrb-concat tree1234a tree1234a))
        (tree2 (rrb-concat tree1234a tree1234a)))
    (eq? tree1 tree2))
  #f
  "Persistance check 2")

If this proves to be false in another way in the future, I will reopen this issue.