(module zip-test mzscheme
  (require "zip.ss")
  
  (print-struct #t)
  
  ; Test data type
  (define-struct tree () (make-inspector))
  (define-struct (tree:empty tree) () (make-inspector))
  (define-struct (tree:node tree) (left alpha right) (make-inspector))
  (define-struct (tree:leaf tree) (beta) (make-inspector))
  
  ; Test data value
  (define (test i)
    (cond
      [(>= 0 i)
       (make-tree:empty)]
      [(= 1 i)
       (make-tree:leaf (gensym))]
      [else
       (make-tree:node (test (sub1 i))
                       i
                       (test (sub1 i)))]))
  (define test-data (test 4))
  
  ; Test 1
  (define (test1)
    ; path(n) causes n+1 allocs
    ; this uses 4 allocs
    (change test-data
            ([tree:node right]
             [tree:node left]
             [tree:node right]
             (make-tree:empty))))
  (define (test2)
    ; m paths of length n_i causes E(m, (n_i+1)) allocs
    ; this uses 4 + 5 = 9, allocs
    (change
     (change test-data
             ([tree:node right]
              [tree:node left]
              [tree:node right]
              (make-tree:empty)))
     ([tree:node right]
      [tree:node left]
      [tree:node left]
      [tree:leaf beta]
      'got-em)))
  (define (test3)
    ; prefix(v) before m paths of length n_i causes (v+1) + E(m, (n_i+1)) allocs
    ; this uses (2 + 1) + (2 + 3) = 7, allocs (i.e., we hand optimize the prefix)
    (change test-data
            ([tree:node right]
             [tree:node left]
             (change
              (change (tree:node-left (tree:node-right test-data))
                      ([tree:node right]
                       (make-tree:empty)))
              ([tree:node left]
               [tree:leaf beta]
               'got-em)))))
  (define (test4)
    ; syntactic sugar for above
    (change test-data
            ([tree:node right]
             [tree:node left]
             [tree:node right]
             (make-tree:empty))
            ([tree:node right]
             [tree:node left]
             [tree:node left]
             [tree:leaf beta]
             'got-em)))  
  (define (test5)
    (change test-data
            ([tree:node right]
             [tree:node left]
             [tree:node right]
             (make-tree:empty))
            ([tree:node right]
             [tree:node left]
             [tree:node left]
             [tree:leaf beta]
             'got-em)
            ([tree:node left]
             (make-tree:empty))))
  (define (test6)
    (update test-data
            ([tree:node right]
             [tree:node left]
             [tree:node left]
             [tree:leaf beta]
             (lambda (old) (symbol->string old))))))