Source

metaljoe_codekata / code_kata_2e.clj

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

; ------------------------------------------------------------
;  Algorithm taken from Programming Pearls, 2nd Edition, p.36
;   written by Jon Bentley, published by Addison Wesley
; ------------------------------------------------------------

(ns code-kata)


(defmacro mid []
  (list 'quot '(+ lower upper) 2) )

(defmacro get-mid []
  (list 'get 'list '(mid)))

(defmacro get-upper []
  (list '- '(count list) 1 ))

(defmacro look-left []
  (list 'recur 'lower '(- (mid) 1)))

(defmacro look-right []
  (list 'recur '(+ (mid) 1) 'upper ))

(defmacro search-exhausted []
  (list '> 'lower 'upper))

(defmacro do-search [ & body ]
  ; NOT WORKING - "Can only recur from tail position"
  `(loop [ ~'lower 0
		   ~'upper (get-upper) ] ~@body
     {:lower ~'lower :upper ~'upper }))

(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]
  (do-search
	(if (search-exhausted)
	  -1
	  (if (< (get-mid) item)
		(look-right)
		(if (= (get-mid) item)
		  (mid)
		  (look-left))))))

(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.