;; 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-lambda-reader.ss" "lang")((modname 23make2d) (read-case-sensitive #t) (teachpacks ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "image.rkt" "teachpack" "2htdp") (lib "universe.rkt" "teachpack" "2htdp"))))) ;; DEMO: Making a *balanced* 2D tree #| DATA DEFINTION A (2dpoint X) is a structure: - (make x y value) where x and y are numbers and value is an X An (h2dtree X) is one of - (2dpoint X) - (make-h-boundary above y below) where above and below are (v2dtree X) and y is a number and all points in `above` have y coordinates at most y and all points in `below` have y coordinates at least y A (v2dtree X) is one of - (2dpoint X) - (make-v-boundary left x right) where `left` and `right` are (h2dtree X) and x is a number and all points in `left` have x coordinates at most `x` and all points in `right` have x coordinates at least `x` A (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 *balanced* h2dtree containing the given points (define (make-h2dtree points) (cond [(empty? (rest points)) (first points)] [(cons? (rest points)) (local [(define n (length points)) (define n-above (quotient n 2)) ;; (define n-below (- n n-above)) (define sorted-points (sort-by points point-y)) (define above (take n-above sorted-points)) ; list of points above line (define below (drop n-above sorted-points)) ; list of points below line (define boundary-y (point-y (first below)))] (make-h-boundary (make-v2dtree above) boundary-y (make-v2dtree below)))])) ;; sort-by : (listof X) (X -> number) -> (listof X) ;; to return the list xs sorted by increasing values of f (define (sort-by xs f) (sort xs (lambda (x1 x2) (< (f x1) (f x2))))) (check-expect (sort-by '("AAAA" "BB" "C" "DDD") string-length) '("C" "BB" "DDD" "AAAA")) ;; sort : (listof X) (X X -> boolean) -> (listof X) (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 5 6 "B") 12 (make-v-boundary (make-point 10 12 "A") 33 (make-point 33 99 "C")))) ;; make-v2dtree : (1listof (2dpoint X)) -> (v2dtree X) ;; to make a *balanced* v2dtree containing the given points (define (make-v2dtree points) (cond [(empty? (rest points)) (first points)] [(cons? (rest points)) (local [(define n (length points)) (define n-left (quotient n 2)) (define sorted-points (sort-by points point-x)) (define left (take n-left sorted-points)) ; points on the left side of the boundary (define right (drop n-left sorted-points)) (define boundary (point-x (first right)))] (make-v-boundary (make-h2dtree left) boundary (make-h2dtree right))) ; take : natural (listof X) -> (listof X) ; return the first n elements of xs, or if xs has fewer than n elements, all of them (define (take n xs) (cond [(or (zero? n) (empty? xs)) '()] [(and (positive? n) (cons? xs)) (cons (first xs) (take (sub1 n) (rest xs)))])) (check-expect (take 8 '(1 2 3)) '(1 2 3)) (check-expect (take 2 '(1 2 3)) '(1 2)) (check-expect (take 0 '(1 2 3)) '()) (check-expect (take 2 '()) '()) ;; drop : natural (listof X) -> (listof X) ;; return what's left after removing the first n elements of xs, ;; or if xs has fewer than n elements, all of them (define (drop n xs) (cond [(or (zero? n) (empty? xs)) xs] [(and (positive? n) (cons? xs)) (drop (sub1 n) (rest xs))])) (check-expect (drop 8 '(1 2 3)) '()) (check-expect (drop 2 '(1 2 3)) '(3)) (check-expect (drop 0 '(1 2 3)) '(1 2 3)) (check-expect (drop 2 '()) '())