;; classify
;;
;; This function takes in a set of examples and then group them
;; accoriding to the classes.
;; so:
;;
;; We defined a concept class of 0 or 1
;; here we make a list of three EXAMPLES: example 1 is classified as 1
;; example 2 is classified as 0
;; example 3 is classified as 1
;;
;; >(defun classes () '(0 1))
;; >(classify (list (make-EXAMPLE 1 '((a 1) (b 0) (c 1)) 1)
;;		(make-EXAMPLE 2 '((a 0) (b 1) (c 1)) 0)
;;		(make-EXAMPLE 3 '((a 1) (b 0) (c 0)) 1)))
;; ( ( (2 ((A 0) (B 1) (C 1)) 0) )          ;; 0
;;   ( (3 ((A 1) (B 0) (C 0)) 1)            ;; 1 
;;     (1 ((A 1) (B 0) (C 1)) 1)) )         ;; 1
;;
;; As expected, classify put all the 0 examples in the first list
;; and the 1 examples in the second list
;;

(defun classify (examples)
  (mapcar #'(lambda (class)
	      (findall examples #'(lambda (s) 
				    (eq class (EXAMPLE-class s)))))
	  (classes)))

;;
;; findall
;;
;; findall returns all the elements that matches the test requirement
;; so:
;;
;; >(findall '(1 b 2 c 3 5 f g ) #'(lambda (x) (numberp x)))
;; (5 3 2 1)
;;
;; This tells it to find all the numbers from the list, then findall
;; goes through the list and then return the list of all the
;; numbers

(defun findall (list test)
  (do ((items list (cdr items))
       (results nil))
      ((null items) results)
      (if (funcall test (car items)) 
	  (setq results (adjoin (car items) results
				:test #'equal)))))


;;
;; partition
;;
;; This takes in a set of examples and then group them according to
;; the value of the given dimension.
;; So
;;
;; We use the same example as above:
;; then we partition the examples according to the dimension (a (0 1))
;; partition then group the examples by looking at the value of the
;; "a" dimension of each example
;;
;; >(partition (list (make-EXAMPLE 1 '((a 1) (b 0) (c 1)) 1)
;;		     (make-EXAMPLE 2 '((a 0) (b 1) (c 1)) 0)
;;		     (make-EXAMPLE 3 '((a 1) (b 0) (c 0)) 1))
;;	       (make-DIMENSION 'a '(0 1)))
;;
;;( ( (2 ((A 0) (B 1) (C 1)) 0) )
;;  ( (3 ((A 1) (B 0) (C 0)) 1)
;;    (1 ((A 1) (B 0) (C 1)) 1) ) )
;;

(defun partition (examples dimension)
  (let ((attribute (DIMENSION-attribute dimension)))
    (mapcar #'(lambda (value) 
		(findall examples
			 #'(lambda (example)
			     (member (list attribute value)
				     (EXAMPLE-features example)
				     :test #'equal))))
	    (DIMENSION-values dimension))))

;;
;; splitter
;;
;; splitter finds the attribute that minimizes a particular evaluation
;; function implemented by evaluate and then return that attribute
;;
;;(setq foo (list (make-EXAMPLE 1 '((a 1) (b 0) (c 1)) 1)
;;			(make-EXAMPLE 2 '((a 1) (b 1) (c 0)) 1)
;;			(make-EXAMPLE 3 '((a 1) (b 1) (c 1)) 0)
;;			(make-EXAMPLE 4 '((a 0) (b 0) (c 0)) 0)
;;			(make-EXAMPLE 5 '((a 1) (b 1) (c 0)) 1)
;;			(make-EXAMPLE 6 '((a 1) (b 0) (c 0)) 0)))
;;> (splitter (make-node foo))
;;(A (0 1))
;;

(defun splitter (node) 
  (do* ((dims (cdr (dimensions)) (cdr dims))
	(value (evaluate node (car (dimensions))))
	(splitter (car (dimensions))) (min value))
       ((null dims) splitter)
       (setq value (evaluate node (car dims)))
       (if (< value min)
	   (setq splitter (car dims) min value))))

;;
;; evaluate
;;

(defun evaluate (node dimension)
  (let ((total (length (NODE-examples node))))
    (apply #'+
	   (mapcar #'(lambda (subset)
		       (* (/ (length subset) total)
			  (disorder (classify subset))))
		   (partition (NODE-examples node) dimension)))))
  
;;
;; disorder
;;

(defun disorder (partition)
  (let* ((sizes (mapcar #'length partition))
	 (total (apply #'+ sizes)))
    (if (= total 0) 0
      (- (log total 2)
	 (apply #'+ (mapcar #'(lambda (s) 
				(if (= s 0) 0 
				  (* (/ s total) (log s 2))))
			    sizes))))))

