;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This file is part of "NOVA":  NOVA = search + COCOMO tools
; Copyright, 2008, Tim Menzies tim@menzies.us
;
; NOVA is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; NOVA is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
; You should have received a copy of the GNU General Public License
; a long with NOVA.  If not, see <http://www.gnu.org/licenses/>.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(in-package :wvu-lib.tricks)

(defstruct line
  "A line runs from (x1, y1) to (x2, y2) with slope m and y-intercept b.  Some
   lines are verticalp (i.e., vertical lines with no defined slope)."
  x1 y1 x2 y2 m b verticalp)

(defun point-to-line (x1 y1 x2 y2)
  "Creates a line from two points."
  (if (> x1 x2)
      (point-to-line x2 y2 x1 y1)
      (let* ((rise      (- y2 y1))
	     (run       (- x2 x1))
	     (verticalp (zerop run))
	     m
	     b)
	(unless verticalp
	  (setf m (/ rise run)
		b (- y2 (* m x2))))
	(make-line :x1 x1 :y1 y1 :x2 x2 :y2 y2
		   :m m :b b :verticalp verticalp))))

(defun line-y (x line)
  "Returns the y value for the given x value on the line."
  (if (line-verticalp line)
      (error "unable to calculate y from x because line is vertical")
      (+ (* (line-m line) x)
	 (line-b line))))

(defun interpolate (x x1 y1 x2 y2 &optional too-big)
  "Calculates the y value for the given x value using linear interpolation
   between the given points.  Returns too-big if x > x2, y1 if x < x1."
  (cond ((<   x x1) y1)
	((eql x x1) y1)
	((eql x x2) y2)
	((>   x x2) too-big)
	(t          (line-y x (point-to-line x1 y1 x2 y2)))))

(defun interpolates (x points)
  "Calculates the y value for the given x value using linear interpolation
   between the (x . y) pairs in points."
  (let ((one (pop points))
	(two (car points)))
    (or (if (null points) (cdr one))
	(interpolate x (car one) (cdr one) (car two) (cdr two))
	(interpolates x points))))