(require "apf.scm")
(require (lib "list.ss"))

;; Test using BSTs... Tests the path based "update", traversal control, and
;;   general "combine"s

;; Produces a list of strings representing the paths to each
;;   "data" element in the tree
(define (bst-paths t)
  (traverse-ba t
               (union-id [(number string) (n p) (string-append (number->string n) ":" p)]
                         [(leaf) (l) '()]
                         [(node string list list) (n d l r) (cons d (append l r))])
               (union-idA [(bst node.left string) (t f p) (string-append p ".left")]
                          [(bst node.right string) (t f p) (string-append p ".right")])
               "root"))

;; Produces a string representation of the tree
(define (bst->string t)
  (traverse-b t (union-id 
                 [(number) (n) (number->string n)]
                 [(bst string string string) (n d l r) (string-append "(" d " " l " " r ")")]
                 [(bst) (l) ""])))

;; Increments each data element and rebuilds the resulting tree
(define (bst-incr t)
  (traverse-b t (union-Bc [(number) (n) (add1 n)])))

;; Find the minimum data element in the BST... keep going left
(define (bst-min t)
  (traverse-bc t (union-id [(leaf) (l) l]
                           [(node number leaf) (n d l) d]
                           [(node number number) (n d mn) mn])
               (make-bypass (node right))))

;; Main function
(define (Main)
  (let ((tree (list->bst '(4 6 2 3 1 7 5))))
    (println " Tree: " (bst->string tree))
    (println " Paths:\n" (pretty (bst-paths tree)))
    (println " Incr: " (bst->string (bst-incr tree)))
    (println " Min: " (bst-min tree))))

;; The usual functional BSTs, defined with apf-lib...
(def-sum  bst [node leaf])
(def-prod node ["(" (data number)
                    (left bst)
                    (right bst) ")"])
(def-prod leaf ["*"])

;; Insert a single element into the given BST
(define (bst-insert t i)
  (traverse-bc t (union-id 
                  [(leaf) (l) (node i l l)]
                  [(node number bst bst) (n d l r) (if (< i d)
                                                       (node d (bst-insert l i) r)
                                                       (node d l (bst-insert r i)))])
               one-step))

;; Convert a list-of-numbers into a BST
(define (list->bst l)
  (traverse-b (reverse l)
              (union-id [(empty) (e) (leaf)]
                        [(cons number bst) (c n t) (bst-insert t n)])))

;; Print a line from a list of strings
(define (println . los)
  (map display los) (newline))

;; Pretty-ify a list of strings (Paths)
(define (pretty lop)
  (foldr (lambda (s r) (string-append "   " s "\n" r)) "" lop))

;; Finally, call the Main function
;; *******************************
(Main)