;;chet tobrey
;; feb 10 2007

(defvar *ls* '((1 2 4 3 4) (2 3 4 5 0) (1 4 5 6 4 )))
;;;; ENTROPY FUNCTIONS ;;;;

(defun entropy-sort (data)
  "uses functions below to take a list of list,
   sort by highest entropy columns and return in reordered form"
  (transpose (sort-cols data)))

(defun bits-required (d)
 (let ((b 0))
    (dolist (p d (- b))
      (unless (= 0 p)
        (incf b (* p (log p 2)))))))

(defun remove-zeros (column)
  (remove '0 column))

(defun how-many (item column)
  (count item column))

(defun height (column)
  "height of column w/o pesky zeros"
  (length (remove-zeros column)))

(defun elt-probability (item column)
  "returns the probability  -- zeroes are accounted for in the height function"
  (/ 1 (height column)))

(defun list-prob (column)
  "takes a list of numbers and returns a hashtable with key val being number - probability "
  (let ((table  (make-hash-table)))
    (dolist (item (remove-zeros column) table)
      (if (eq (gethash item table) nil)
        (setf (gethash item table) (elt-probability item column))
        (setf (gethash item table)
              (+ (gethash item table)(elt-probability item column)))))))
; (gethash key table detault)
; (incf (gethash item table 0) (elt-probability item column))

(defun pull-vals (table)
  "pulls the values for a hash table, used here to get the probabilities"
  (let (values)
    (maphash #'(lambda(key val)(setf values (cons val values)))table)
    values))
; (push val values)

(defun score-column(column)
  "calls a host of small functions to get the entropy of a column"
  (bits-required (pull-vals (list-prob column))))


;;;; ROW AND COLUMN MANIPULATION ;;;;
(defun count-rows (group)
  "counts the rows in a list of lists"
  (length group))

 (defun count-cols (rows)
   "counts the columns by counting the items in the first row"
   (length (first rows)))

(defun transpose (x)
  "transpose a matrix"
  (apply #'mapcar (cons #'list x)))


(defun sort-cols (group)
  "sort cols takes a list of lists, turns it into columns,
   and sorts using score-column -which calculates the entropy of each"
   (stable-sort (transpose group) #'< :key #'score-column))

;;;;SORT by ZEROS better than entropy for sample.lisp;;
(defun zero-sort (group)
 (transpose (sort (transpose group) #'> :key #'count-zeros)))
(defun count-zeros(col)
  (count 0 col))
  
;;;;remove zeros                                        
(defun ent-sort-no-zeros (data)
  "Does an entropy sort with all zeros removed"
  (transpose (sort-cols (remove-zeros data))))

;(defun result-state (column &optional(where )
 ; "looks at the result for each column

;(defun info-gain (cols)