Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!feeder.news-service.com!feeder.news-service.com!85.214.198.2.MISMATCH!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: "Mike Schilling" Newsgroups: comp.lang.java.programmer Subject: Re: Binary Search Date: Sat, 2 Apr 2011 16:52:58 -0700 Organization: A noiseless patient Spider Lines: 1 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; format=flowed; charset="UTF-8"; reply-type=original Content-Transfer-Encoding: 8bit Injection-Date: Sat, 2 Apr 2011 23:52:20 +0000 (UTC) Injection-Info: mx01.eternal-september.org; posting-host="igtKpzRBOz6+ZjfkpittKQ"; logging-data="25090"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19PEM0D4L2y7n7clfq79jmvV99Bb+G7BjQ=" X-MimeOLE: Produced By Microsoft MimeOLE V14.0.8117.416 In-Reply-To: X-Newsreader: Microsoft Windows Live Mail 14.0.8117.416 Importance: Normal Cancel-Lock: sha1:loTFgXNR/Iw/4HhaQVP7mn5sETc= X-Priority: 3 X-MSMail-Priority: Normal Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:2782 "Tom Anderson" wrote in message news:alpine.DEB.2.00.1104030007560.28036@urchin.earth.li... > 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. I was thinking that you'd iterate through the sorted set to get a sorted List or array, but that wasn't the use we were discussing, was it. > > Mind you, with an embedded key, i'm not sure how you'd do lookups even > with a map. To retrieve some object, wouldn't you need to have it to hand > in the first place, to be able to pass in its embedded key? Or would you > also support lookup by freestanding key? You can look it up with an object that's equal to (as opposed to identical to) the one embedded in the value. But you knew that.