commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From __matthewHawthorne <ma...@phreaker.net>
Subject Re: [collections] BidiMap / DoubleOrderedMap
Date Tue, 23 Sep 2003 20:32:16 GMT
I just committed an initial version of HashBidiMap, the unordered 
BidiMap implementation.

I wrote a fair amount of tests, and everything seems OK, but I would 
appreciate it if somebody could take a look and let me know what they 
think, before I start on the ordered version, TreeBidiMap.

It was sort of confusing to write and I'm paranoid that I missed 
something.  Thanks!




Phil Steitz wrote:

> 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