metaljoe_codekata / kata2 / code_kata_2a.clj

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

(ns code-kata)

(defn is-single-item? [ list ]
  (= 1 (count list)))

(defn mid-index [ list ]
  (quot (count list) 2))

(defn bsearch [ list value slice-start slice-end ]
  (if (empty? list)
	-1
	(let [ slice (subvec list slice-start slice-end)]
	  (if (is-single-item? slice)
		(if (= value (first slice) )
		  slice-start
		  -1)
		(let [ mid (mid-index slice) ]
		  (let [ mid-value (get slice mid) ]
			(if (= value mid-value)
			  (+ slice-start mid)
			  (if (< value mid-value)
				(bsearch list value slice-start (- slice-end mid))
				(bsearch list value (+ slice-start mid) slice-end)))))))))

(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]
  (bsearch list item 0 (count list))
)

(test #'chop)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.