Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #2808

Re: Binary Search

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Sat, 2 Apr 2011, Mike Schilling wrote:

> "Tom Anderson" <twic@urchin.earth.li> wrote in message 
> news:alpine.DEB.2.00.1104030007560.28036@urchin.earth.li...
>> On Sat, 2 Apr 2011, Mike Schilling wrote:
>> 
>>> "Lawrence D'Oliveiro" <ldo@geek-central.gen.new_zealand> wrote in message
>>> news:in6oj8$5b5$3@lust.ihug.co.nz...
>>>> In message <imp8c9$nkf$1@dont-email.me>, Mike Schilling wrote:
>>>> 
>>>>> "Lawrence D'Oliveiro" <ldo@geek-central.gen.new_zealand> wrote in 
>>>>> message
>>>>> news:imouja$56s$2@lust.ihug.co.nz...
>>>>> 
>>>>>> In message <ohlno6t4rn1g9rd020immcdko7r448cjo1@4ax.com>, 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? Do you make them purely to use as key-holders? Does 
that mean you're going to have half-filled-out instances of your value 
class floating about the place? Does that mean you have to provide a 
constructor that allows such instances to be created, so abandoning the 
invariants that you could otherwise enforce through your constructors?

Or do you need to do something like:

public interface KeyHolder {
 	public String getKey();
}

public class Value implements KeyHolder {
 	private final String key;
 	// other fields
 	public String getKey() {
 		return key;
 	}
 	// other methods
}

public class Example implements KeyHolder { // so called for "query by example"
 	private final String key;
 	public Example(String key) {
 		this.key = key;
 	}
 	public String getKey() {
 		return key;
 	}
}

Map<KeyHolder, Value> objects = new TreeMap<KeyHolder, Value>(new Comparator<KeyHolder, KeyHolder>(){
 	public int compare(KeyHolder a, KeyHolder b) {
 		return a.getKey().compareTo(b.getKey());
 	}
});
Value v = ...;
String k = v.getKey();
objects.put(v, v);
Value u = objects.get(new Example(k));
assert u == v;

?

It can certainly be done, but all things considered, i lean towards 
extracting the key before hitting the map. The map could perhaps be 
wrapped in a simple wrapper:

public class ValueStore {
 	private Map<String, Value> map = new HashMap<String, Value>();
 	public void put(Value v) {
 		map.put(v.getKey(), v);
 	}
 	public Value get(String key) {
 		return map.get(key);
 	}
}

So that calling code is not troubled with the details.

tom

-- 
The Vikings' commitment to metal is absolute, and it is this unshakeable
resolve to bring their metal to the people that will possibly make
Vikings of Steel the most important band ever. -- Mr Gig

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Binary Search Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-04-02 22:00 +1300
  Re: Binary Search Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-02 05:07 -0500
    Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 07:59 -0700
      Re: Binary Search Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-02 10:37 -0500
        Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 08:57 -0700
          Re: Binary Search Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-04-03 12:40 +1200
  Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 07:58 -0700
    Re: Binary Search Lew <noone@lewscanon.com> - 2011-04-02 11:11 -0400
      Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 08:58 -0700
    Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 00:11 +0100
      Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-02 16:52 -0700
        Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 18:50 +0100
          Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-03 12:01 -0700
            Re: Binary Search Tom Anderson <twic@urchin.earth.li> - 2011-04-03 22:39 +0100
              Re: Binary Search "Mike Schilling" <mscottschilling@hotmail.com> - 2011-04-03 16:37 -0700
                Re: Binary Search Lew <noone@lewscanon.com> - 2011-04-06 15:24 -0400
                OT "sic"? (was Re: Binary Search) blmblm@myrealbox.com <blmblm@myrealbox.com> - 2011-04-11 13:53 +0000
                Re: OT "sic"? (was Re: Binary Search) Lew <lew@lewscanon.com> - 2011-04-11 11:45 -0700
                Re: OT "sic"? (was Re: Binary Search) Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-11 14:11 -0500
                Re: OT "sic"? (was Re: Binary Search) Lew <lew@lewscanon.com> - 2011-04-11 13:48 -0700
                Re: OT "sic"? (was Re: Binary Search) Tom Anderson <twic@urchin.earth.li> - 2011-04-11 22:16 +0100
                Re: OT "sic"? (was Re: Binary Search) Lew <noone@lewscanon.com> - 2011-04-11 17:54 -0400
                Re: OT "sic"? (was Re: Binary Search) Tom Anderson <twic@urchin.earth.li> - 2011-04-11 23:35 +0100
                Re: OT "sic"? (was Re: Binary Search) Leif Roar Moldskred <leifm@dimnakorr.com> - 2011-04-11 21:41 -0500
                Re: OT "sic"? (was Re: Binary Search) blmblm@myrealbox.com <blmblm@myrealbox.com> - 2011-04-14 10:11 +0000
                Re: OT "sic"? (was Re: Binary Search) Jerry Gerrone <scuzwalla@gmail.com> - 2011-04-14 20:12 -0700
                Re: OT "sic"? (was Re: Binary Search) Ken Wesson <kwesson@gmail.com> - 2011-04-26 22:53 +0100
      Re: Binary Search Ken Wesson <kwesson@gmail.com> - 2011-04-05 16:01 +0100

csiph-web