;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-reader.ss" "lang")((modname 20make2d) (read-case-sensitive #t) (teachpacks ((lib "universe.rkt" "teachpack" "2htdp") (lib "image.rkt" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "universe.rkt" "teachpack" "2htdp") (lib "image.rkt" "teachpack" "2htdp")))))
;; DEMO: Trying to make a 2D tree using recursion
#|
DATA DEFINTION

(h2dtree X) is one of

   - (2dpoint X)
   - (make-h-boundary above y below)
      where y coordinates are good

(v2dtree X) is one of

   - (2dpoint X)
   - (make-v-boundary left  x right)
     where all points in `left` have x coordinates at most `x`
            and similarly `right` have x coordinates at least `x`
(2dtree X) is one of:
   - (v2dtree X)
   - (h2dtree X)
|#

(define-struct point (x y value))
(define-struct h-boundary (above y below))
(define-struct v-boundary (left  x right))

;; make-h2dtree : (1listof (2dpoint X)) -> (h2dtree X)
;; to make a h2dtree containing the given points
(define (make-h2dtree points)
  (cond [(empty? (rest points)) (first points)]
        [(cons? (rest points))
         (local [(define boundary-y (point-y (argmin point-y points)))
                 (define above-line (filter (lambda (p) (<= (point-y p) boundary-y)) points))
                 (define below-line (filter (lambda (p) (>  (point-y p) boundary-y)) points))]
           ;; tragically this does not terminate because `above-line` might contain all the points
           (make-h-boundary (make-v2dtree above-line)
                            boundary-y
                            (make-v2dtree below-line)))]))
 
(check-expect (make-h2dtree (list (make-point 10 12 "A")
                                  (make-point 5 6 "B")
                                  (make-point 33 99 "C")))
              (make-h-boundary (make-v2dtree (list (make-point 10 12 "A")
                                                   (make-point 5 2 "B"))
                                             12
                                             (make-point 33 99 "C"))))

;; make-v2dtree : (1listof (2dpoint X)) -> (v2dtree X)
;; to make a v2dtree containing the given points
(define (make-v2dtree points)
   ...)