Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!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 12:01:00 -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: Sun, 3 Apr 2011 19:31:57 +0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="+XOGlUMTIWGTtEFUy3CYUQ"; logging-data="861"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19bXgHqB19KH1ykP+gK1o2rCbF0YarELFY=" 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:z2FWXxrGw4IlvKGuRISzccrRcY0= X-Priority: 3 X-MSMail-Priority: Normal Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:2811 "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.