From: Ken Wesson Subject: Re: Binary Search Newsgroups: comp.lang.java.programmer References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit NNTP-Posting-Host: $$-gwckl$tgnwr6.news.x-privat.org Message-ID: <4d9b20cb@news.x-privat.org> Date: 5 Apr 2011 16:01:47 +0100 Organization: X-Privat.Org NNTP Server - http://www.x-privat.org Lines: 70 X-Authenticated-User: $$o-16a0wpsuhxkoyemw X-Complaints-To: abuse@x-privat.org Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!gegeweb.org!newsfeed.x-privat.org!x-privat.org!not-for-mail Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:2886 On Sun, 03 Apr 2011 00:11:01 +0100, Tom Anderson wrote: > On Sat, 2 Apr 2011, Mike Schilling wrote: > >> "Lawrence D'Oliveiro" wrote in >> message news:in6oj8$5b5$3@lust.ihug.co.nz... >>> In message , Mike Schilling wrote: >>> >>>> "Lawrence D'Oliveiro" wrote in >>>> message news:imouja$56s$2@lust.ihug.co.nz... >>>> >>>>> In message , Roedy Green >>>>> wrote: >>>>> >>>>>> The problem is, Map and SortedMap don't "map" well onto binary >>>>>> search. binary search to work properly requires embedded keys. Maps >>>>>> require them separate. >>>>> >>>>> Sounds like the Java Map classes are not well designed. >>>> >>>> Or that someone doesn't understand them. Embedded keys can be made >>>> to work perfectly well with SortedMaps simply by making both >>>> arguments to put() the same, and providing a comparator that can >>>> locate the key in the object. >>> >>> So why isn’t there a single-argument overload of the put method to >>> save you the trouble? >> >> There is, if you use a Set instead of a Map. > > Except there's no way to retrieve the value from the Set later! We've > been round this one before - the idea that sets might support some sort > of 'get' or 'canonicalize' method to do just that. Clojure is a JVM language that fixes this. Its sets can be called as functions, and return the matching item in the set: user=> (def q (Integer. 253)) #'user/q user=> (def r (Integer. 253)) #'user/r user=> (def s #{q 17 42}) #'user/s user=> (def t (s r)) #'user/t user=> (identical? t r) false user=> (identical? t q) true The identical? function is Java's == operator "in disguise". The set's return value was the object q put into it rather than the .equals but not == object r used to retrieve q. The Clojure set classes can of course be invoked from Java. user=> (identical? q (.get s r)) true That's actually a Java method invocation. In Java, someSet.get(keyholder) would return the corresponding object in the set, given that someSet was a clojure.lang.IPersistentSet, say a clojure.lang.HashSet, rather than one of the stock java.util set classes (which don't have this get method). So, you can use these set classes even if you for some odd reason can't stomach Lisp syntax, while somehow nonetheless tolerating Java's baroque verbosity. :)