You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Stephen Colebourne <sc...@btopenworld.com> on 2003/10/05 14:35:04 UTC
Re: [collections] BidiMap / DoubleOrderedMap
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" <ma...@phreaker.net>
To: "Jakarta Commons Developers List" <co...@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" <sc...@btopenworld.com>
> >> To: "Jakarta Commons Developers List" <co...@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" <ph...@steitz.com>
> >>> To: "Jakarta Commons Developers List" <co...@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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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" <ma...@phreaker.net>
> To: "Jakarta Commons Developers List" <co...@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" <sc...@btopenworld.com>
>>>>To: "Jakarta Commons Developers List" <co...@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" <ph...@steitz.com>
>>>>>To: "Jakarta Commons Developers List" <co...@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