commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@btopenworld.com>
Subject Re: [collections] BidiMap / DoubleOrderedMap
Date Sun, 05 Oct 2003 12:35:04 GMT
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