Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!weretis.net!feeder4.news.weretis.net!newsfeed.straub-nv.de!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: "Mike Schilling" Newsgroups: comp.lang.java.programmer Subject: Re: Binary Search Date: Sun, 3 Apr 2011 16:37:22 -0700 Organization: A noiseless patient Spider Lines: 3 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: Sun, 3 Apr 2011 23:37:17 +0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="+XOGlUMTIWGTtEFUy3CYUQ"; logging-data="17303"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/fnMp2oSBlL1qwEgj8cUgqXS8EzTCXrSE=" 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:taa27eCrV79QPbEYPNrbhZlkE+o= X-Priority: 3 X-MSMail-Priority: Normal Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:2818 "Tom Anderson" wrote in message news:alpine.DEB.2.00.1104032234030.11872@urchin.earth.li... > On Sun, 3 Apr 2011, Mike Schilling wrote: > >> "Tom Anderson" wrote in message >> news:alpine.DEB.2.00.1104031840110.11872@urchin.earth.li... >>> On Sat, 2 Apr 2011, Mike Schilling wrote: >>> >>>> "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? >>>>> >>>>> 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. >>> >>> Yes, and i tried not to think about it, because it's smelly. How do you >>> obtain these objects? >> >> Simple use case that I've done several times: >> >> I'm going to parse a file. For each keyword, I create an object that >> describes how it should be processed; one of its fields is the string >> representation of the keyword. I put it in a map using that field as >> the key (map.put (kw.getName(), kw). Where do I get the String I'll use >> to look it up? From reading the file. > > Okay, crossed wires. If some type T has an embedded key K (ie there's some > method m such that you can say T t; K k = t.m();), then you have two > options. One, you can do what you describe there, and what i was also > talking about in my last post (with all the curly brackets), where you > have a Map. Two, you can do what you described in your original > reply to Lawrence, and have a Map, with a Comparator that says > compare(T a, T b) {return a.m().compareTo(b.m());}. Option two involves > using instances of T as keys. It's those instances which i was asking how > you obtain. > > But perhaps the answer is that we use option one. Fair point. This was simpler before generics, when the Comparator could accept either K's or T's :-)