commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Phil Steitz" <p...@steitz.com>
Subject Re: [collections] BidiMap / DoubleOrderedMap
Date Tue, 23 Sep 2003 01:09:20 GMT
Phil Steitz wrote:
> __matthewHawthorne wrote:
> 
>> HashBidiMap is fine with me.  My best thought seems to match yours, 
>> I'm keeping two HashMaps in sync (one the inverse of the other).  I'm 
>> trying to think of a better way, but I'm drawing a blank.
>>
>> For now, I'm just concentrating on writing solid tests to make sure 
>> the interface works... low level improvements can come whenever a 
>> better idea occurs.
>>
> +1 -- test first!
> 
> Am I correct in assuming that the BidiMap interface contract *requires* 
> that the mapping be 1-to-1 wrt identity, but not necessarily wrt equals 
> -- i.e., will a BidiMap allow for example
> 
> x = new Integer(0);
> y = new Integer(0);

DOH!  Thinking backwards, I meant

map.put("foo", x);
map.out("bar", y);

though now I am thinking that it really amount to the same thing, so 
this should probably be disallowed (or cause overwrite as it does for Map)

> map.put(x, "foo");
> map.out(y, "bar");
> ??
> 
> Clearly,
> 
> map.put("foo", x);
> map.put("bar", x);
> 
> has to be illegal, but the first example is not so clear.
> 
> The "Sorted" version will obviously require that the mapping be strictly 
> 1-1 (as the DoubleOrderedMap does), but for the unsorted version this is 
> not a logical necessity (though I suspect that it is a practical one).
> 
> Could be I am missing something obvious here.  I am looking forward to 
> seeing the tests and maybe some clarification of exactly what is allowed 
> in the interface docs :-)
> 
> Phil
> 
> 
> 
>>
>>
>>
>> Stephen Colebourne wrote:
>>
>>> I was thinking of HashBidiMap as I assumed it would involve hashing. (My
>>> current best thought is two tied HashMaps, but thats not very nice
>>> really...)
>>>
>>> The main thing with TreeBidiMap is to retain the speed of the specialist
>>> implementation while adding the new interface ;-)
>>>
>>> Stephen
>>>
>>> ----- Original Message -----
>>> From: "__matthewHawthorne" <matth@phreaker.net>
>>> To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
>>> Sent: Monday, September 22, 2003 10:38 PM
>>> Subject: Re: [collections] BidiMap / DoubleOrderedMap
>>>
>>>
>>>
>>>> I've started some work on converting DoubleOrderedMap to TreeBidiMap.
>>>>
>>>> What is the suggested name for the basic BidiMap implementation 
>>>> which is
>>>> n't sorted?  DefaultBidiMap?
>>>>
>>>>
>>>>
>>>>
>>>> Stephen Colebourne wrote:
>>>>
>>>>
>>>>> I have been prompted to take a look at DoubleOrderedMap by bugzilla 
>>>>> and
>>>>
>>>>
>>>
>>> been
>>>
>>>>> a little surprised by what I found. Given the history of collections,
>>>>
>>>>
>>>
>>> what
>>>
>>>>> we have is a single implementation brought in from an external 
>>>>> project.
>>>>> [collections] should do better :-)
>>>>>
>>>>> A bidirectional map is a relatively standard concept in computing. 
>>>>> It is
>>>>
>>>>
>>>
>>> a
>>>
>>>>> map where you can use a key to find a value, or a value to find a key
>>>>
>>>>
>>>
>>> with
>>>
>>>>> equal ease. This deserves its own interface in [collections] - 
>>>>> BidiMap.
>>>>>
>>>>> The DoubleOrderedMap class goes beyond this by being Sorted, 
>>>>> effectively
>>>>> holding all entries in a Compared order always. This effectively 
>>>>> equates
>>>>
>>>>
>>>
>>> to
>>>
>>>>> a second interface in [collections] - SortedBidiMap.
>>>>>
>>>>> BidiMap
>>>>> ----------
>>>>> Map methods +
>>>>> BidiMap inverseBidiMap()
>>>>> Object getKeyForValue(Object value)
>>>>> Object removeValue(Object value)
>>>>> Set entrySetByValue()
>>>>> Set keySetByValue()
>>>>> Collection valuesByValue()
>>>>> (these method names are from DoubleOrderedMap, and seem OKish)
>>>>>



Mime
View raw message