;; The first three lines of this file were inserted by DrScheme. 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 |27.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
;Once the interval size reaches TOLERANCE, simply approximate the area under the curve as the corresponding rectangle or trapezoid.

;TOLERANCE1 is for integrate-dc
(define TOLERANCE1 0.0001)

;TOLERANCE2 is for integrate-adaptive
(define TOLERANCE2 0.0000001)

;integrate-dc  : (number -> number) number number -> number
;(integrate-divide and conquer)
;Given f, left, and right, use the divide-and-conquer generative recursion strategy to find the area under the curve.  Given an interval, if the interval is small enough (compared to TOLERANCE1), we simply find the area of the interval (using a rectangle or trapezoid).  Otherwise, we divide the interval into two pieces and sum the area under the curves of the resulting two integrals.
;ASSUMPTION : (> right left)
;Termination argument: Since each recursion involves an interval with half the width of the original interval, integrate-dc will eventually be applied to an interval less than the TOLERANCE1 and so terminate.

(define (integrate-dc f left right)
  (local ((define midpoint (+ left
                              (/ (- right left) 2))))
    (cond
      [(not (> right left))
       (error 'integrate-dc "right endpoint must be greater than left endpoint")]
      [(<= (- right left) TOLERANCE1) (area-of-trapezoid f left right)]
      [else (+ (integrate-dc f left midpoint)
               (integrate-dc f midpoint right))])))

;area-of-rectangle : number number number -> number
;Given the left and right endpoints as well as the height, compute the area of the rectangle.

(define (area-of-rectangle left right height)
  (* (- right left) height))

;area-of-trapezoid : (number -> number) number number -> number
;Given the function f, the left and right endpoints, compute the area of the trapezoid.
(define (area-of-trapezoid f left right)
  (* (/ (+ (f left) (f right)) 2)
     (- right left)))

;integrate-adaptive : 
;Given f, left, and right, integrate-adaptive uses the same strategy as integrate-dc except that it prematurely ends recursions if it notices that the difference between the trapezoid approximation of an interval versus the trapezoid approximation of the interval split in two is about the same.

(define (integrate-adaptive f left right)
  (local ((define midpoint (+ left
                              (/ (- right left) 2)))
          (define current-approx (area-of-trapezoid f left right)))
    (cond
      [(not (> right left))
       (error 'integrate-adaptive "right endpoint must be greater than left endpoint")]
      [(< (- current-approx 
             (+ (area-of-trapezoid f left midpoint)
                (area-of-trapezoid f midpoint right)))
          (* TOLERANCE2 (- right left)))
       current-approx]
      [(<= (- right left) TOLERANCE2) current-approx]
      [else (+ (integrate-adaptive f left midpoint)
               (integrate-adaptive f midpoint right))])))

(time (integrate-adaptive (lambda (x) (sqr x)) -4 9))
(time (integrate-dc (lambda (x) (sqr x)) -4 9))