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 Sun, 05 Oct 2003 19:08:01 GMT
I originally had TestBidiMap extending TestMap (which is now 
AbstractTestMap), but the tests were failing for other reasons.  It 
seems there is a test which adds a certain number of entries and then 
tests that it matches the total number of entries in the Map, which 
isn't necessarily true with BidiMaps, in the case that different keys 
are entered with the same value.

My point is, it may take more than a conversion to a decorator to make 
BidiMaps pass all of the tests in AbstractMap. However, I do think that 
a conversion to a decorator may be a good idea, since it can be viewed 
as simply a different way of viewing a Map.




Stephen Colebourne wrote:
> I spotted a problem in the HashBidiMap implementation when I made the test
> extend AbstractTestMap. equals and hashCode weren't working. So I
> implemented them to delegate to the first map.
> 
> Then I realised that that was a broader problem with the implementation. I
> think that the whole class becomes much simpler if it is viewed as a
> decorator, so I'm working on that now.
> 
> Stephen
> 
> 
> ----- Original Message -----
> From: "__matthewHawthorne" <matth@phreaker.net>
> To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
> Sent: Tuesday, September 30, 2003 12:32 AM
> Subject: Re: [collections] BidiMap / DoubleOrderedMap
> 
> 
> 
>>If anyone else is interested in working TreeBidiMap, the SortedBidiMap
>>implementation, the gates are open.  I've started some initial work on
>>it and it has my head spinning.  These bidirectional maps are tough!
>>
>>I'm trying to code a little each day, but I'm extremely busy at work,
>>and I don't want to hold up the 3.0 release.  If anyone is interested,
>>let me know, and I can check in what I've done so far... in the
>>meanwhile, I'll persist.
>>
>>
>>
>>
>>__matthewHawthorne wrote:
>>
>>
>>>OK, I'll be sure to add some tests for these cases and update the
>>>functionality to accomodate them.  Thanks.
>>>
>>>
>>>
>>>
>>>Stephen Colebourne wrote:
>>>
>>>
>>>>The current HashBidiMap implementation will fail in a couple of places
> 
> I
> 
>>>>think.
>>>>
>>>>map.iterator().next()
>>>>returns a Map.Entry. If you call setValue() on the entry it only
>>>>updates one
>>>>map, not the inverse.
>>>>
>>>>map.inverseBidiMap().iterator().next()
>>>>returns a DefaultMapEntry. This should be a real map entry which allows
>>>>setValue().
>>>>
>>>>Presumably, tests would be needed for these too.
>>>>
>>>>Stephen
>>>>
>>>>
>>>>----- Original Message -----
>>>>From: "Stephen Colebourne" <scolebourne@btopenworld.com>
>>>>To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
>>>>Sent: Wednesday, September 24, 2003 11:57 PM
>>>>Subject: Re: [collections] BidiMap / DoubleOrderedMap
>>>>
>>>>
>>>>
>>>>
>>>>>My expectation is that
>>>>>
>>>>>
>>>>>>map.put("a", "c");
>>>>>>map.put("b", "c");
>>>>>
>>>>>
>>>>>will result in a size 1 map (both ways).
>>>>>
>>>>>Thus a put(key,value) needs to
>>>>>- inverse.put(value, key) returns oldMapping
>>>>>- forward.remove(oldMapping)
>>>>>- forward.put(key, value)
>>>>>(or some such code...)
>>>>>
>>>>>An alternative implementation might throw IllegalArgumentException
> 
> when
> 
>>>>
>>>>the
>>>>
>>>>
>>>>>second method is called. (but we don't need to write this
> 
> implementation
> 
>>>>
>>>>in
>>>>
>>>>
>>>>>[collections])
>>>>>
>>>>>Stephen
>>>>>
>>>>>----- Original Message -----
>>>>>From: "Phil Steitz" <phil@steitz.com>
>>>>>To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
>>>>>Sent: Wednesday, September 24, 2003 4:17 PM
>>>>>Subject: Re: [collections] BidiMap / DoubleOrderedMap
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>>__matthewHawthorne wrote:
>>>>>>
>>>>>>
>>>>>>>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!
>>>>>>>
>>>>>>
>>>>>>I like the approach.  I am still a bit concerned about the contract
> 
> vis
> 
>>>>>>a vis duplicates (not necessarily that it is wrong, but really that
I
>>>>>>don't know exactly what it is). Right now, HashBidiMap will happily
>>>>>
>>>>>
>>>>>accept:
>>>>>
>>>>>
>>>>>>map.put("a", "c");
>>>>>>map.put("b", "c");
>>>>>>
>>>>>>The size() methods on both the map and inverse will return 2, but
the
>>>>>>inverse really has only one entry <c, b>.  Both map.get("a")
and
>>>>>>map.get("b") return "c"; but map.getKey("c") returns "b".
>>>>>>
>>>>>>The question is, is this a happy state?  This is what I was trying
to
>>>>>>express in the garbled stuff above. This really comes down to
>>>>>>specifying
>>>>>>exactly what the contract of a BidiMap is. The simplest contract
> 
> (IMHO)
> 
>>>>>>would require that the map be 1-1, in which case it would probably
be
>>>>>>most natural to have the second assignment above overwrite *both*
> 
> maps.
> 
>>>>>>If we don't add that requirement and insertion test, it seems to me
>>>>>>that
>>>>>>the contract is going to have to refer to *two* maps and the
>>>>>>relationship between them is not necessarily what would (at least
in
>>>>>>the
>>>>>>mathematical sense) be described as "inverse", since the range of
the
>>>>>>inverse map may end up being a subset of the domain of the original
> 
> (as
> 
>>>>>>in case above).  We would also have to find a way to get size()
>>>>>>correctly overloaded to give the actual size of the inverse map (now
> 
> it
> 
>>>>>>returns the size of the "forward" map).
>>>>>>
>>>>>>Phil
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>---------------------------------------------------------------------
>>>>>>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>>>>>>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>>>>>>
>>>>>
>>>>>
>>>>>---------------------------------------------------------------------
>>>>>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>>>>>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>>>>>
>>
>>
>>
>>---------------------------------------------------------------------
>>To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
>>For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>>



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message