;; 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 21make2d) (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: Successfully making a 2D tree using recursion
#|
DATA DEFINTION

(h2dtree X) is one of
   - (2dpoint X)
   - (make-h-boundary above y below)
      where above and below are (v2dtree X)
      where y coordinates in above are at most y
            y coordinates in below are at least y

(v2dtree X) is one of
   - (2dpoint X)
   - (make-v-boundary left  x right)
     where left and right are (h2dtree X)
     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 tiebreaker (first points))
                 (define boundary-y (point-y tiebreaker))
                 (define others (rest points))
                 (define above-line (filter (lambda (p) (<= (point-y p) boundary-y)) others))
                 (define below-line (filter (lambda (p) (>  (point-y p) boundary-y)) others))]
           (cond [(empty? above-line)
                  (make-h-boundary (make-v2dtree (cons tiebreaker above-line))
                                   boundary-y 
                                   (make-v2dtree below-line))]
                 [(cons? above-line)
                  (make-h-boundary (make-v2dtree above-line) 
                                   boundary-y 
                                   (make-v2dtree (cons tiebreaker 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-point 10 12 "A")
                               12
                               (make-v2dtree (list (make-point 5 2 "B")
                                             (make-point 33 99 "C")))))

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