;;;;compiled under:
;;;;slime 1:20070927-3
;;;;SBCL  1:1.0.11.0-1
;;;;Peter Santiago, June 2nd, 2008
;;;;Program note: the input data array is assumed to be AxB, where each row represents the B dimensions of one point and there are A points 
(progn
(load "fastmap-kmeans-ancillary.lisp")
(load "utests.lisp"))

(defun fastmap (k datamatrix &optional
                (distancematrix (set-distance-matrix datamatrix))
                (x (make-array (list (array-dimension datamatrix 0) k) :initial-element nil))
                (pa (make-array (list 2 k) :initial-element nil))
                (cnum -1)) ;k is the desired number of dimensions, datamatrix if the data; all the rest are optional and generally computed by fastmap for subsequent passes
  "fastmap: does important things; generally awesome."
  (let ((templist 0) ;for storing the output of choose-distance-objects
        (dprimematrix 0) ;for storing the reduced distancematrix
        (o.a 0) ;stores object a
        (o.b 0) ;stores object b
        (x.i 0)) ;stores the calculated value of x.i (a bit extraneous, but I think it helps with readability)
    
    ;;1 base case conditional
    (if (<= k 0)
        (return-from fastmap x)) ;returns the new coordinates of objects
    (setf cnum (+ cnum 1)) ;This is here because that's how faloutsos and lin organized their algorithm    
    ;;2 choose pivot objects
    (setf templist (choose-distance-objects distancematrix))
    (setf o.a (first templist))
    (setf o.b (second templist))    
    ;;3 record the ids of the pivot objects
    (setf (aref pa 0 cnum) o.a)
    (setf (aref pa 1 cnum) o.b)    
    ;;4 distance something    
    (if (= (aref distancematrix o.a o.b) 0)
        (dotimes (i (array-dimension x 0))
          (setf (aref x i cnum) 0)))    
    ;;5 project the objects on the line(o.a,o.b)
    (dotimes (i (array-dimension datamatrix 0))
      (setf x.i (/ (- (+ (expt (aref distancematrix o.a i) 2)
                         (expt (aref distancematrix o.a o.b) 2))
                      (expt (aref distancematrix o.b i) 2))
                   (* 2 (aref distancematrix o.a o.b))))
      (setf (aref x i cnum) x.i))    
    ;;6 consider the projections of the objects on a hyper-plaine perpendicular to the line (o.a,o.b); find new distance function
    (setf dprimematrix (reduce-dist distancematrix x cnum))
    (fastmap (- k 1) datamatrix dprimematrix x pa cnum))) ;end fastmap

(deftest test-fastmap()
  "Note:the values are entirely different depending on which point is picked to be a and which is b"
  (check
    (let ((x (fastmap 1 (make-array '(4 2) :initial-contents '((0 0)
                                                              (5 3)
                                                              (10 24)
                                                              (60 70))))))
      ;;fastmap chooses o.a to be 3, and o.b to be 0
      (and (between 92 (aref x 0 0) 93)
           (between 86 (aref x 1 0) 87)
           (between 67 (aref x 2 0) 68)
           (between 0 (aref x 3 0) 0)))))