1. John Chandler
  2. metaljoe_codekata

Source

metaljoe_codekata / kata2 / code_kata_2c.clj

; http://codekata.pragprog.com/2007/01/kata_two_karate.html

(ns code-kata)

(defn evaluate-list
  " Returns offset if list contains only item, otherwise -1 "
  [ item list offset ]
  (if (= item (first list))
	offset
	-1))

(defn get-left-half
  " Returns the left half of the list "
  [ list mid ]
  (first (split-at mid list)))

(defn get-right-half
  " Returns the right half of the list "
  [ list mid ]
  (first (rest (split-at mid list))))

(defn bsearch
  " Returns index of item if in list, otherwise -1 "
  [ dummy item list offset ]
  (if (empty? list)
	-1
    (if (= 1 (count list))
	  (evaluate-list item list offset)
	  (let [ mid        (quot (count list) 2)
			 left-half  (bsearch dummy item (get-left-half list mid)  offset )
			 right-half (bsearch dummy item (get-right-half list mid) (+ mid offset)) ]
		(if (= -1 left-half)
		  right-half
		  left-half)))))
  
(defn
  #^{:test (fn []
			 (assert (= -1 (chop 3 []) ))
			 (assert (= -1 (chop 3 [1]) ))
			 (assert (=  0 (chop 1 [1]) ))

			 (assert (=  0 (chop 1 [1 3 5]) ))
			 (assert (=  1 (chop 3 [1 3 5]) ))
			 (assert (=  2 (chop 5 [1 3 5]) ))
			 (assert (= -1 (chop 0 [1 3 5]) ))
			 (assert (= -1 (chop 2 [1 3 5]) ))
			 (assert (= -1 (chop 4 [1 3 5]) ))
			 (assert (= -1 (chop 6 [1 3 5]) ))

			 (assert (=  0 (chop 1 [1 3 5 7]) ))
			 (assert (=  1 (chop 3 [1 3 5 7]) ))
			 (assert (=  2 (chop 5 [1 3 5 7]) ))
			 (assert (=  3 (chop 7 [1 3 5 7]) ))
			 (assert (= -1 (chop 0 [1 3 5 7]) ))
			 (assert (= -1 (chop 2 [1 3 5 7]) ))
			 (assert (= -1 (chop 4 [1 3 5 7]) ))
			 (assert (= -1 (chop 6 [1 3 5 7]) ))
			 (assert (= -1 (chop 8 [1 3 5 7]) )) ) }
  chop
  [item list]
  (let [ mid         (quot (count list) 2)
		 left-agent  (agent -1)
		 right-agent (agent -1) ]
	(send left-agent  bsearch item (get-left-half list mid)  0)
	(send right-agent bsearch item (get-right-half list mid) mid)
	(await left-agent right-agent)
	(if (= -1 @left-agent)
	  @right-agent
	  @left-agent)))

(test #'chop)

(shutdown-agents)