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/09/20 14:42:11 UTC
[collections] BidiMap / DoubleOrderedMap
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)
SortedBidiMap
----------------
BidiMap + SortedMap +
inverseSortedBidiMap()
subMapByValue()
headMapByValue()
tailMapByValue()
The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
I would like to rename it to TreeBidiMap.
An alternative implementation of BidiMap would then be needed, which would
be useful as it would not require objects to be comparable.
With these new interfaces, decorators could then be written as required.
Anything obvious I've missed? Any volunteers?
Stephen
---------------------------------------------------------------------
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>.
in SortedBidiMap
I made a mistake.... in SortedBidiMap, my suggested valueMap() would at
least have to return a java.util.SortedMap, since java.util.Map doesn't
have the headMap, tailMap, and subMap methods.
__matthewHawthorne wrote:
> In BidiMap, instead of:
>
> > Object getKeyForValue(Object value)
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> What about just providing a single method which would return a Map with
> the keys/values reversed, such as:
>
> Map valueMap()
>
> It would remove the duplication of having to write all these XXXbyValue
> methods.
>
>
> Similarly, in SortedBidiMap, instead of:
>
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
>
> what about (I'm not exactly sure what the return type should be):
>
> Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>
>
> I haven't looked at the existing code, but I suspect that this way would
> be easier to write, less lines of code, and more OO.
>
> What do you think?
>
>
>
>
> 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)
>>
>> SortedBidiMap
>> ----------------
>> BidiMap + SortedMap +
>> inverseSortedBidiMap()
>> subMapByValue()
>> headMapByValue()
>> tailMapByValue()
>>
>> The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>> However
>> I would like to rename it to TreeBidiMap.
>>
>> An alternative implementation of BidiMap would then be needed, which
>> would
>> be useful as it would not require objects to be comparable.
>>
>> With these new interfaces, decorators could then be written as required.
>>
>> Anything obvious I've missed? Any volunteers?
>>
>> Stephen
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
in SortedBidiMap
I made a mistake.... in SortedBidiMap, my suggested valueMap() would at
least have to return a java.util.SortedMap, since java.util.Map doesn't
have the headMap, tailMap, and subMap methods.
__matthewHawthorne wrote:
> In BidiMap, instead of:
>
> > Object getKeyForValue(Object value)
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> What about just providing a single method which would return a Map with
> the keys/values reversed, such as:
>
> Map valueMap()
>
> It would remove the duplication of having to write all these XXXbyValue
> methods.
>
>
> Similarly, in SortedBidiMap, instead of:
>
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
>
> what about (I'm not exactly sure what the return type should be):
>
> Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>
>
> I haven't looked at the existing code, but I suspect that this way would
> be easier to write, less lines of code, and more OO.
>
> What do you think?
>
>
>
>
> 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)
>>
>> SortedBidiMap
>> ----------------
>> BidiMap + SortedMap +
>> inverseSortedBidiMap()
>> subMapByValue()
>> headMapByValue()
>> tailMapByValue()
>>
>> The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>> However
>> I would like to rename it to TreeBidiMap.
>>
>> An alternative implementation of BidiMap would then be needed, which
>> would
>> be useful as it would not require objects to be comparable.
>>
>> With these new interfaces, decorators could then be written as required.
>>
>> Anything obvious I've missed? Any volunteers?
>>
>> Stephen
---------------------------------------------------------------------
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 Stephen Colebourne <sc...@btopenworld.com>.
----- Original Message -----
From: "__matthewHawthorne" <ma...@phreaker.net>
> I was thinking that the inverseBidiMap() would just return a reference
> to an inner class which is held inside of the BidiMap implementation.
This is still another object. Sure it can be cached and the same one
returned each time (as per other collections views) but its still annoying
> It all depends on whether we want to be able to call the shortcuts:
> get(value)
> remove(value)
They have to be:
> > getKey(value)
> > removeKey(value)
as BidiMap extends Map
> instead of:
> inverseBidiMap().get(value)
> inverseBidiMap().remove(value)
>
> Since BidiMap is an interface, I would suggest against creating the
> shortcut methods, since it forces all implementations to write them. If
> we have an abstract implemenation which takes care of it then it's not
> such a hassle.
I reckon that these two shortcut methods cover 80% of the functionality
required (80:20 rule :-0). The rest can go via inverseBidiMap().
> I'd be happy to help out either way.
Grins :-)) I'll checkin a BidiMap interface tonight and we can take it from
there.
Stephen
> Stephen Colebourne wrote:
> > I had an inverseBidiMap() to cover the valueMap() case. However I reckon
> > that since the whole reason for the class is to allow the reverse
lookup,
> > its not unreasonable to be able to access it directly. Having to go via
an
> > inverseBidiMap() method means creating another object, which is quite a
> > large overhead for these operations (well the get at least).
> >
> > Maybe we should have just
> > inverseBidiMap()
> > getKey(value)
> > removeKey(value)
> >
> > The rest could go via the inverse. Maybe.
> > Stephen
> >
> > ----- Original Message -----
> > From: "__matthewHawthorne" <ma...@phreaker.net>
> > To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> > Sent: Saturday, September 20, 2003 6:57 PM
> > Subject: Re: [collections] BidiMap / DoubleOrderedMap
> >
> >
> >
> >>In BidiMap, instead of:
> >>
> >>
> >>>Object getKeyForValue(Object value)
> >>>Object removeValue(Object value)
> >>>Set entrySetByValue()
> >>>Set keySetByValue()
> >>>Collection valuesByValue()
> >>
> >>What about just providing a single method which would return a Map with
> >>the keys/values reversed, such as:
> >>
> >>Map valueMap()
> >>
> >>It would remove the duplication of having to write all these XXXbyValue
> >>methods.
> >>
> >>
> >>Similarly, in SortedBidiMap, instead of:
> >>
> >>
> >>>subMapByValue()
> >>>headMapByValue()
> >>>tailMapByValue()
> >>
> >>what about (I'm not exactly sure what the return type should be):
> >>
> >>Map/SortedMap/BidiMap/SortedBidiMap valueMap()
> >>
> >>
> >>I haven't looked at the existing code, but I suspect that this way would
> >>be easier to write, less lines of code, and more OO.
> >>
> >>What do you think?
> >>
> >>
> >>
> >>
> >>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)
> >>>
> >>>SortedBidiMap
> >>>----------------
> >>>BidiMap + SortedMap +
> >>>inverseSortedBidiMap()
> >>>subMapByValue()
> >>>headMapByValue()
> >>>tailMapByValue()
> >>>
> >>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
> >
> > However
> >
> >>>I would like to rename it to TreeBidiMap.
> >>>
> >>>An alternative implementation of BidiMap would then be needed, which
> >
> > would
> >
> >>>be useful as it would not require objects to be comparable.
> >>>
> >>>With these new interfaces, decorators could then be written as
required.
> >>>
> >>>Anything obvious I've missed? Any volunteers?
> >>>
> >>>Stephen
> >>
> >>
> >>
> >>---------------------------------------------------------------------
> >>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 Stephen Colebourne <sc...@btopenworld.com>.
----- Original Message -----
From: "__matthewHawthorne" <ma...@phreaker.net>
> I was thinking that the inverseBidiMap() would just return a reference
> to an inner class which is held inside of the BidiMap implementation.
This is still another object. Sure it can be cached and the same one
returned each time (as per other collections views) but its still annoying
> It all depends on whether we want to be able to call the shortcuts:
> get(value)
> remove(value)
They have to be:
> > getKey(value)
> > removeKey(value)
as BidiMap extends Map
> instead of:
> inverseBidiMap().get(value)
> inverseBidiMap().remove(value)
>
> Since BidiMap is an interface, I would suggest against creating the
> shortcut methods, since it forces all implementations to write them. If
> we have an abstract implemenation which takes care of it then it's not
> such a hassle.
I reckon that these two shortcut methods cover 80% of the functionality
required (80:20 rule :-0). The rest can go via inverseBidiMap().
> I'd be happy to help out either way.
Grins :-)) I'll checkin a BidiMap interface tonight and we can take it from
there.
Stephen
> Stephen Colebourne wrote:
> > I had an inverseBidiMap() to cover the valueMap() case. However I reckon
> > that since the whole reason for the class is to allow the reverse
lookup,
> > its not unreasonable to be able to access it directly. Having to go via
an
> > inverseBidiMap() method means creating another object, which is quite a
> > large overhead for these operations (well the get at least).
> >
> > Maybe we should have just
> > inverseBidiMap()
> > getKey(value)
> > removeKey(value)
> >
> > The rest could go via the inverse. Maybe.
> > Stephen
> >
> > ----- Original Message -----
> > From: "__matthewHawthorne" <ma...@phreaker.net>
> > To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> > Sent: Saturday, September 20, 2003 6:57 PM
> > Subject: Re: [collections] BidiMap / DoubleOrderedMap
> >
> >
> >
> >>In BidiMap, instead of:
> >>
> >>
> >>>Object getKeyForValue(Object value)
> >>>Object removeValue(Object value)
> >>>Set entrySetByValue()
> >>>Set keySetByValue()
> >>>Collection valuesByValue()
> >>
> >>What about just providing a single method which would return a Map with
> >>the keys/values reversed, such as:
> >>
> >>Map valueMap()
> >>
> >>It would remove the duplication of having to write all these XXXbyValue
> >>methods.
> >>
> >>
> >>Similarly, in SortedBidiMap, instead of:
> >>
> >>
> >>>subMapByValue()
> >>>headMapByValue()
> >>>tailMapByValue()
> >>
> >>what about (I'm not exactly sure what the return type should be):
> >>
> >>Map/SortedMap/BidiMap/SortedBidiMap valueMap()
> >>
> >>
> >>I haven't looked at the existing code, but I suspect that this way would
> >>be easier to write, less lines of code, and more OO.
> >>
> >>What do you think?
> >>
> >>
> >>
> >>
> >>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)
> >>>
> >>>SortedBidiMap
> >>>----------------
> >>>BidiMap + SortedMap +
> >>>inverseSortedBidiMap()
> >>>subMapByValue()
> >>>headMapByValue()
> >>>tailMapByValue()
> >>>
> >>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
> >
> > However
> >
> >>>I would like to rename it to TreeBidiMap.
> >>>
> >>>An alternative implementation of BidiMap would then be needed, which
> >
> > would
> >
> >>>be useful as it would not require objects to be comparable.
> >>>
> >>>With these new interfaces, decorators could then be written as
required.
> >>>
> >>>Anything obvious I've missed? Any volunteers?
> >>>
> >>>Stephen
> >>
> >>
> >>
> >>---------------------------------------------------------------------
> >>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 was thinking that the inverseBidiMap() would just return a reference
to an inner class which is held inside of the BidiMap implementation.
That way there may not have to be another object created. I'm not sure
if this is practical or not.
It all depends on whether we want to be able to call the shortcuts:
get(value)
remove(value)
instead of:
inverseBidiMap().get(value)
inverseBidiMap().remove(value)
Since BidiMap is an interface, I would suggest against creating the
shortcut methods, since it forces all implementations to write them. If
we have an abstract implemenation which takes care of it then it's not
such a hassle.
I think the shortcuts are convenient, but not necessary, it just depends
on where you want to draw the line. I'd be happy to help out either way.
Stephen Colebourne wrote:
> I had an inverseBidiMap() to cover the valueMap() case. However I reckon
> that since the whole reason for the class is to allow the reverse lookup,
> its not unreasonable to be able to access it directly. Having to go via an
> inverseBidiMap() method means creating another object, which is quite a
> large overhead for these operations (well the get at least).
>
> Maybe we should have just
> inverseBidiMap()
> getKey(value)
> removeKey(value)
>
> The rest could go via the inverse. Maybe.
> Stephen
>
> ----- Original Message -----
> From: "__matthewHawthorne" <ma...@phreaker.net>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Saturday, September 20, 2003 6:57 PM
> Subject: Re: [collections] BidiMap / DoubleOrderedMap
>
>
>
>>In BidiMap, instead of:
>>
>>
>>>Object getKeyForValue(Object value)
>>>Object removeValue(Object value)
>>>Set entrySetByValue()
>>>Set keySetByValue()
>>>Collection valuesByValue()
>>
>>What about just providing a single method which would return a Map with
>>the keys/values reversed, such as:
>>
>>Map valueMap()
>>
>>It would remove the duplication of having to write all these XXXbyValue
>>methods.
>>
>>
>>Similarly, in SortedBidiMap, instead of:
>>
>>
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>
>>what about (I'm not exactly sure what the return type should be):
>>
>>Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>>
>>
>>I haven't looked at the existing code, but I suspect that this way would
>>be easier to write, less lines of code, and more OO.
>>
>>What do you think?
>>
>>
>>
>>
>>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)
>>>
>>>SortedBidiMap
>>>----------------
>>>BidiMap + SortedMap +
>>>inverseSortedBidiMap()
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>>
>>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>
> However
>
>>>I would like to rename it to TreeBidiMap.
>>>
>>>An alternative implementation of BidiMap would then be needed, which
>
> would
>
>>>be useful as it would not require objects to be comparable.
>>>
>>>With these new interfaces, decorators could then be written as required.
>>>
>>>Anything obvious I've missed? Any volunteers?
>>>
>>>Stephen
>>
>>
>>
>>---------------------------------------------------------------------
>>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 was thinking that the inverseBidiMap() would just return a reference
to an inner class which is held inside of the BidiMap implementation.
That way there may not have to be another object created. I'm not sure
if this is practical or not.
It all depends on whether we want to be able to call the shortcuts:
get(value)
remove(value)
instead of:
inverseBidiMap().get(value)
inverseBidiMap().remove(value)
Since BidiMap is an interface, I would suggest against creating the
shortcut methods, since it forces all implementations to write them. If
we have an abstract implemenation which takes care of it then it's not
such a hassle.
I think the shortcuts are convenient, but not necessary, it just depends
on where you want to draw the line. I'd be happy to help out either way.
Stephen Colebourne wrote:
> I had an inverseBidiMap() to cover the valueMap() case. However I reckon
> that since the whole reason for the class is to allow the reverse lookup,
> its not unreasonable to be able to access it directly. Having to go via an
> inverseBidiMap() method means creating another object, which is quite a
> large overhead for these operations (well the get at least).
>
> Maybe we should have just
> inverseBidiMap()
> getKey(value)
> removeKey(value)
>
> The rest could go via the inverse. Maybe.
> Stephen
>
> ----- Original Message -----
> From: "__matthewHawthorne" <ma...@phreaker.net>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Saturday, September 20, 2003 6:57 PM
> Subject: Re: [collections] BidiMap / DoubleOrderedMap
>
>
>
>>In BidiMap, instead of:
>>
>>
>>>Object getKeyForValue(Object value)
>>>Object removeValue(Object value)
>>>Set entrySetByValue()
>>>Set keySetByValue()
>>>Collection valuesByValue()
>>
>>What about just providing a single method which would return a Map with
>>the keys/values reversed, such as:
>>
>>Map valueMap()
>>
>>It would remove the duplication of having to write all these XXXbyValue
>>methods.
>>
>>
>>Similarly, in SortedBidiMap, instead of:
>>
>>
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>
>>what about (I'm not exactly sure what the return type should be):
>>
>>Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>>
>>
>>I haven't looked at the existing code, but I suspect that this way would
>>be easier to write, less lines of code, and more OO.
>>
>>What do you think?
>>
>>
>>
>>
>>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)
>>>
>>>SortedBidiMap
>>>----------------
>>>BidiMap + SortedMap +
>>>inverseSortedBidiMap()
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>>
>>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>
> However
>
>>>I would like to rename it to TreeBidiMap.
>>>
>>>An alternative implementation of BidiMap would then be needed, which
>
> would
>
>>>be useful as it would not require objects to be comparable.
>>>
>>>With these new interfaces, decorators could then be written as required.
>>>
>>>Anything obvious I've missed? Any volunteers?
>>>
>>>Stephen
>>
>>
>>
>>---------------------------------------------------------------------
>>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 Stephen Colebourne <sc...@btopenworld.com>.
I had an inverseBidiMap() to cover the valueMap() case. However I reckon
that since the whole reason for the class is to allow the reverse lookup,
its not unreasonable to be able to access it directly. Having to go via an
inverseBidiMap() method means creating another object, which is quite a
large overhead for these operations (well the get at least).
Maybe we should have just
inverseBidiMap()
getKey(value)
removeKey(value)
The rest could go via the inverse. Maybe.
Stephen
----- Original Message -----
From: "__matthewHawthorne" <ma...@phreaker.net>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Saturday, September 20, 2003 6:57 PM
Subject: Re: [collections] BidiMap / DoubleOrderedMap
> In BidiMap, instead of:
>
> > Object getKeyForValue(Object value)
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> What about just providing a single method which would return a Map with
> the keys/values reversed, such as:
>
> Map valueMap()
>
> It would remove the duplication of having to write all these XXXbyValue
> methods.
>
>
> Similarly, in SortedBidiMap, instead of:
>
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
>
> what about (I'm not exactly sure what the return type should be):
>
> Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>
>
> I haven't looked at the existing code, but I suspect that this way would
> be easier to write, less lines of code, and more OO.
>
> What do you think?
>
>
>
>
> 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)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > I would like to rename it to TreeBidiMap.
> >
> > An alternative implementation of BidiMap would then be needed, which
would
> > be useful as it would not require objects to be comparable.
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
>
>
>
> ---------------------------------------------------------------------
> 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 Stephen Colebourne <sc...@btopenworld.com>.
I had an inverseBidiMap() to cover the valueMap() case. However I reckon
that since the whole reason for the class is to allow the reverse lookup,
its not unreasonable to be able to access it directly. Having to go via an
inverseBidiMap() method means creating another object, which is quite a
large overhead for these operations (well the get at least).
Maybe we should have just
inverseBidiMap()
getKey(value)
removeKey(value)
The rest could go via the inverse. Maybe.
Stephen
----- Original Message -----
From: "__matthewHawthorne" <ma...@phreaker.net>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Saturday, September 20, 2003 6:57 PM
Subject: Re: [collections] BidiMap / DoubleOrderedMap
> In BidiMap, instead of:
>
> > Object getKeyForValue(Object value)
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> What about just providing a single method which would return a Map with
> the keys/values reversed, such as:
>
> Map valueMap()
>
> It would remove the duplication of having to write all these XXXbyValue
> methods.
>
>
> Similarly, in SortedBidiMap, instead of:
>
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
>
> what about (I'm not exactly sure what the return type should be):
>
> Map/SortedMap/BidiMap/SortedBidiMap valueMap()
>
>
> I haven't looked at the existing code, but I suspect that this way would
> be easier to write, less lines of code, and more OO.
>
> What do you think?
>
>
>
>
> 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)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > I would like to rename it to TreeBidiMap.
> >
> > An alternative implementation of BidiMap would then be needed, which
would
> > be useful as it would not require objects to be comparable.
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
>
>
>
> ---------------------------------------------------------------------
> 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>.
In BidiMap, instead of:
> Object getKeyForValue(Object value)
> Object removeValue(Object value)
> Set entrySetByValue()
> Set keySetByValue()
> Collection valuesByValue()
What about just providing a single method which would return a Map with
the keys/values reversed, such as:
Map valueMap()
It would remove the duplication of having to write all these XXXbyValue
methods.
Similarly, in SortedBidiMap, instead of:
> subMapByValue()
> headMapByValue()
> tailMapByValue()
what about (I'm not exactly sure what the return type should be):
Map/SortedMap/BidiMap/SortedBidiMap valueMap()
I haven't looked at the existing code, but I suspect that this way would
be easier to write, less lines of code, and more OO.
What do you think?
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)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
In BidiMap, instead of:
> Object getKeyForValue(Object value)
> Object removeValue(Object value)
> Set entrySetByValue()
> Set keySetByValue()
> Collection valuesByValue()
What about just providing a single method which would return a Map with
the keys/values reversed, such as:
Map valueMap()
It would remove the duplication of having to write all these XXXbyValue
methods.
Similarly, in SortedBidiMap, instead of:
> subMapByValue()
> headMapByValue()
> tailMapByValue()
what about (I'm not exactly sure what the return type should be):
Map/SortedMap/BidiMap/SortedBidiMap valueMap()
I haven't looked at the existing code, but I suspect that this way would
be easier to write, less lines of code, and more OO.
What do you think?
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)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
---------------------------------------------------------------------
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 see your point, and I think I agree... the purpose of BidiMap isn't to
maintain a relationship between 2 maps, it's to maintain a bidirectional
link between all key value pairs.
So, I'll have to detect cases like your example:
map.put("a", "c");
map.put("b", "c");
And be sure to remove the pair with key "a". I'll have to take a look
and see how hard this will be, but overall I think it's the best way,
because it is the simplest and most consistent way.
Phil Steitz wrote:
> __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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
I see your point, and I think I agree... the purpose of BidiMap isn't to
maintain a relationship between 2 maps, it's to maintain a bidirectional
link between all key value pairs.
So, I'll have to detect cases like your example:
map.put("a", "c");
map.put("b", "c");
And be sure to remove the pair with key "a". I'll have to take a look
and see how hard this will be, but overall I think it's the best way,
because it is the simplest and most consistent way.
Phil Steitz wrote:
> __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
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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>.
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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
>>>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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
>>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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
>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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
>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
__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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
__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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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" <ma...@phreaker.net>
>>>> To: "Jakarta Commons Developers List" <co...@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)
>>>>>>
---------------------------------------------------------------------
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 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" <ma...@phreaker.net>
>>>> To: "Jakarta Commons Developers List" <co...@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)
>>>>>>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
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" <ma...@phreaker.net>
>>> To: "Jakarta Commons Developers List" <co...@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)
>>>>>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
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" <ma...@phreaker.net>
>>> To: "Jakarta Commons Developers List" <co...@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)
>>>>>
---------------------------------------------------------------------
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 Phil Steitz <ph...@steitz.com>.
__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);
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" <ma...@phreaker.net>
>> To: "Jakarta Commons Developers List" <co...@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)
>>>>
>>>> SortedBidiMap
>>>> ----------------
>>>> BidiMap + SortedMap +
>>>> inverseSortedBidiMap()
>>>> subMapByValue()
>>>> headMapByValue()
>>>> tailMapByValue()
>>>>
>>>> The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>>>
>>
>> However
>>
>>>> I would like to rename it to TreeBidiMap.
>>>>
>>>> An alternative implementation of BidiMap would then be needed, which
>>>
>>
>> would
>>
>>>> be useful as it would not require objects to be comparable.
>>>>
>>>> With these new interfaces, decorators could then be written as
>>>> required.
>>>>
>>>> Anything obvious I've missed? Any volunteers?
>>>>
>>>> Stephen
>>>
>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> 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 Phil Steitz <ph...@steitz.com>.
__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);
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" <ma...@phreaker.net>
>> To: "Jakarta Commons Developers List" <co...@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)
>>>>
>>>> SortedBidiMap
>>>> ----------------
>>>> BidiMap + SortedMap +
>>>> inverseSortedBidiMap()
>>>> subMapByValue()
>>>> headMapByValue()
>>>> tailMapByValue()
>>>>
>>>> The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>>>
>>
>> However
>>
>>>> I would like to rename it to TreeBidiMap.
>>>>
>>>> An alternative implementation of BidiMap would then be needed, which
>>>
>>
>> would
>>
>>>> be useful as it would not require objects to be comparable.
>>>>
>>>> With these new interfaces, decorators could then be written as
>>>> required.
>>>>
>>>> Anything obvious I've missed? Any volunteers?
>>>>
>>>> Stephen
>>>
>>>
>>>
>>>
>>> ---------------------------------------------------------------------
>>> 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>.
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.
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" <ma...@phreaker.net>
> To: "Jakarta Commons Developers List" <co...@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)
>>>
>>>SortedBidiMap
>>>----------------
>>>BidiMap + SortedMap +
>>>inverseSortedBidiMap()
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>>
>>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>
> However
>
>>>I would like to rename it to TreeBidiMap.
>>>
>>>An alternative implementation of BidiMap would then be needed, which
>
> would
>
>>>be useful as it would not require objects to be comparable.
>>>
>>>With these new interfaces, decorators could then be written as required.
>>>
>>>Anything obvious I've missed? Any volunteers?
>>>
>>>Stephen
>>
>>
>>
>>---------------------------------------------------------------------
>>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>.
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.
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" <ma...@phreaker.net>
> To: "Jakarta Commons Developers List" <co...@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)
>>>
>>>SortedBidiMap
>>>----------------
>>>BidiMap + SortedMap +
>>>inverseSortedBidiMap()
>>>subMapByValue()
>>>headMapByValue()
>>>tailMapByValue()
>>>
>>>The existing DoubleOrderedMap is an implementation of SortedBidiMap.
>
> However
>
>>>I would like to rename it to TreeBidiMap.
>>>
>>>An alternative implementation of BidiMap would then be needed, which
>
> would
>
>>>be useful as it would not require objects to be comparable.
>>>
>>>With these new interfaces, decorators could then be written as required.
>>>
>>>Anything obvious I've missed? Any volunteers?
>>>
>>>Stephen
>>
>>
>>
>>---------------------------------------------------------------------
>>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 Stephen Colebourne <sc...@btopenworld.com>.
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" <ma...@phreaker.net>
To: "Jakarta Commons Developers List" <co...@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)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > I would like to rename it to TreeBidiMap.
> >
> > An alternative implementation of BidiMap would then be needed, which
would
> > be useful as it would not require objects to be comparable.
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
>
>
>
> ---------------------------------------------------------------------
> 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 Stephen Colebourne <sc...@btopenworld.com>.
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" <ma...@phreaker.net>
To: "Jakarta Commons Developers List" <co...@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)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > I would like to rename it to TreeBidiMap.
> >
> > An alternative implementation of BidiMap would then be needed, which
would
> > be useful as it would not require objects to be comparable.
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
>
>
>
> ---------------------------------------------------------------------
> 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'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)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
> A BidiMap interface has just been checked in as a starter. It has
> - getKey(Object value)
> - removeKey(Object value)
> - inverseBidiMap()
>
> I personally prefer Bidi, because its easier to manage simply from length. I
> think the name needs to be one word, otherwise implementation names get
> confusing. And Invertable doesn't work for me.
OK. I guess "Bijective" won't work for you either ;-) No big deal.
>
> The implementation names are formed by
> <internalOfImpl><interfaceName>
> dropping 'Sorted' from the interface name if it is present.
>
> 'TreeBidiMap' thus results from the RedBlack Tree implementation +
> SortedBidiMap name.
Thanks for clarifying. This makes sense.
Regarding the current impl, the inverseBidiMap() requirement might push
things to the point where a dual-tree implementation makes sense,
allowing us to dispense with the custom RedBlack implementation and just
use JDK TreeMaps. Something to think about.
Phil
>
> Stephen
>
>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
> A BidiMap interface has just been checked in as a starter. It has
> - getKey(Object value)
> - removeKey(Object value)
> - inverseBidiMap()
>
> I personally prefer Bidi, because its easier to manage simply from length. I
> think the name needs to be one word, otherwise implementation names get
> confusing. And Invertable doesn't work for me.
OK. I guess "Bijective" won't work for you either ;-) No big deal.
>
> The implementation names are formed by
> <internalOfImpl><interfaceName>
> dropping 'Sorted' from the interface name if it is present.
>
> 'TreeBidiMap' thus results from the RedBlack Tree implementation +
> SortedBidiMap name.
Thanks for clarifying. This makes sense.
Regarding the current impl, the inverseBidiMap() requirement might push
things to the point where a dual-tree implementation makes sense,
allowing us to dispense with the custom RedBlack implementation and just
use JDK TreeMaps. Something to think about.
Phil
>
> Stephen
>
>
---------------------------------------------------------------------
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 Stephen Colebourne <sc...@btopenworld.com>.
A BidiMap interface has just been checked in as a starter. It has
- getKey(Object value)
- removeKey(Object value)
- inverseBidiMap()
I personally prefer Bidi, because its easier to manage simply from length. I
think the name needs to be one word, otherwise implementation names get
confusing. And Invertable doesn't work for me.
The implementation names are formed by
<internalOfImpl><interfaceName>
dropping 'Sorted' from the interface name if it is present.
'TreeBidiMap' thus results from the RedBlack Tree implementation +
SortedBidiMap name.
Stephen
----- Original Message -----
From: "Michael Heuer" <he...@acm.org>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Cc: <Da...@JungleMoss.com>; <Da...@workplace-systems.plc.uk>
Sent: Saturday, September 20, 2003 9:05 PM
Subject: Re: [collections] BidiMap / DoubleOrderedMap
>
> On Sat, 20 Sep 2003, Phil Steitz wrote:
>
> > See comments inline.
> >
> > 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.
> >
> > I agree, though I would favor either spelling out "Bidirectional" or
> > using "Invertible" or "OneToOne" as the prefix. Unless the term
> > "BidiMap" is a "familiar" term, I would suggest picking a full word for
> > the prefix.
>
> For what it's worth, I would also prefer "Bidirectional" for the prefix.
>
> michael
>
> >
> > >
> > > 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.
> >
> > Yes, and it is important to distinguish between what is required by the
> > interface and how the implementation happens to work. The current class
> > header comments are a bit confusing/nonsensical on this. How things are
> > "stored" is irrelevant to the interface.
> >
> > >
> > > BidiMap
> > > ----------
> > > Map methods +
> > > BidiMap inverseBidiMap()
> >
> > > Object getKeyForValue(Object value)
> >
> > Could drop "ForValue" here.
> >
> > > Object removeValue(Object value)
> > > Set entrySetByValue()
> > > Set keySetByValue()
> > > Collection valuesByValue()
> >
> > > (these method names are from DoubleOrderedMap, and seem OKish)
> > >
> > > SortedBidiMap
> > > ----------------
> > > BidiMap + SortedMap +
> > > inverseSortedBidiMap()
> > > subMapByValue()
> > > headMapByValue()
> > > tailMapByValue()
> > >
> > > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > > I would like to rename it to TreeBidiMap.
> >
> > InvertibleTreeMap or BidirectionalTreeMap might be better.
> >
> > >
> > > An alternative implementation of BidiMap would then be needed, which
would
> > > be useful as it would not require objects to be comparable.
> >
> > +1
> >
> > >
> > > With these new interfaces, decorators could then be written as
required.
> > >
> > > Anything obvious I've missed? Any volunteers?
> > >
> > > Stephen
> > >
> > >
> > >
> >
> > 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
>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
A BidiMap interface has just been checked in as a starter. It has
- getKey(Object value)
- removeKey(Object value)
- inverseBidiMap()
I personally prefer Bidi, because its easier to manage simply from length. I
think the name needs to be one word, otherwise implementation names get
confusing. And Invertable doesn't work for me.
The implementation names are formed by
<internalOfImpl><interfaceName>
dropping 'Sorted' from the interface name if it is present.
'TreeBidiMap' thus results from the RedBlack Tree implementation +
SortedBidiMap name.
Stephen
----- Original Message -----
From: "Michael Heuer" <he...@acm.org>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Cc: <Da...@JungleMoss.com>; <Da...@workplace-systems.plc.uk>
Sent: Saturday, September 20, 2003 9:05 PM
Subject: Re: [collections] BidiMap / DoubleOrderedMap
>
> On Sat, 20 Sep 2003, Phil Steitz wrote:
>
> > See comments inline.
> >
> > 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.
> >
> > I agree, though I would favor either spelling out "Bidirectional" or
> > using "Invertible" or "OneToOne" as the prefix. Unless the term
> > "BidiMap" is a "familiar" term, I would suggest picking a full word for
> > the prefix.
>
> For what it's worth, I would also prefer "Bidirectional" for the prefix.
>
> michael
>
> >
> > >
> > > 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.
> >
> > Yes, and it is important to distinguish between what is required by the
> > interface and how the implementation happens to work. The current class
> > header comments are a bit confusing/nonsensical on this. How things are
> > "stored" is irrelevant to the interface.
> >
> > >
> > > BidiMap
> > > ----------
> > > Map methods +
> > > BidiMap inverseBidiMap()
> >
> > > Object getKeyForValue(Object value)
> >
> > Could drop "ForValue" here.
> >
> > > Object removeValue(Object value)
> > > Set entrySetByValue()
> > > Set keySetByValue()
> > > Collection valuesByValue()
> >
> > > (these method names are from DoubleOrderedMap, and seem OKish)
> > >
> > > SortedBidiMap
> > > ----------------
> > > BidiMap + SortedMap +
> > > inverseSortedBidiMap()
> > > subMapByValue()
> > > headMapByValue()
> > > tailMapByValue()
> > >
> > > The existing DoubleOrderedMap is an implementation of SortedBidiMap.
However
> > > I would like to rename it to TreeBidiMap.
> >
> > InvertibleTreeMap or BidirectionalTreeMap might be better.
> >
> > >
> > > An alternative implementation of BidiMap would then be needed, which
would
> > > be useful as it would not require objects to be comparable.
> >
> > +1
> >
> > >
> > > With these new interfaces, decorators could then be written as
required.
> > >
> > > Anything obvious I've missed? Any volunteers?
> > >
> > > Stephen
> > >
> > >
> > >
> >
> > 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 Michael Heuer <he...@acm.org>.
On Sat, 20 Sep 2003, Phil Steitz wrote:
> See comments inline.
>
> 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.
>
> I agree, though I would favor either spelling out "Bidirectional" or
> using "Invertible" or "OneToOne" as the prefix. Unless the term
> "BidiMap" is a "familiar" term, I would suggest picking a full word for
> the prefix.
For what it's worth, I would also prefer "Bidirectional" for the prefix.
michael
>
> >
> > 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.
>
> Yes, and it is important to distinguish between what is required by the
> interface and how the implementation happens to work. The current class
> header comments are a bit confusing/nonsensical on this. How things are
> "stored" is irrelevant to the interface.
>
> >
> > BidiMap
> > ----------
> > Map methods +
> > BidiMap inverseBidiMap()
>
> > Object getKeyForValue(Object value)
>
> Could drop "ForValue" here.
>
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> > (these method names are from DoubleOrderedMap, and seem OKish)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> > I would like to rename it to TreeBidiMap.
>
> InvertibleTreeMap or BidirectionalTreeMap might be better.
>
> >
> > An alternative implementation of BidiMap would then be needed, which would
> > be useful as it would not require objects to be comparable.
>
> +1
>
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
> >
> >
> >
>
> 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
>
>
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Michael Heuer <he...@acm.org>.
On Sat, 20 Sep 2003, Phil Steitz wrote:
> See comments inline.
>
> 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.
>
> I agree, though I would favor either spelling out "Bidirectional" or
> using "Invertible" or "OneToOne" as the prefix. Unless the term
> "BidiMap" is a "familiar" term, I would suggest picking a full word for
> the prefix.
For what it's worth, I would also prefer "Bidirectional" for the prefix.
michael
>
> >
> > 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.
>
> Yes, and it is important to distinguish between what is required by the
> interface and how the implementation happens to work. The current class
> header comments are a bit confusing/nonsensical on this. How things are
> "stored" is irrelevant to the interface.
>
> >
> > BidiMap
> > ----------
> > Map methods +
> > BidiMap inverseBidiMap()
>
> > Object getKeyForValue(Object value)
>
> Could drop "ForValue" here.
>
> > Object removeValue(Object value)
> > Set entrySetByValue()
> > Set keySetByValue()
> > Collection valuesByValue()
>
> > (these method names are from DoubleOrderedMap, and seem OKish)
> >
> > SortedBidiMap
> > ----------------
> > BidiMap + SortedMap +
> > inverseSortedBidiMap()
> > subMapByValue()
> > headMapByValue()
> > tailMapByValue()
> >
> > The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> > I would like to rename it to TreeBidiMap.
>
> InvertibleTreeMap or BidirectionalTreeMap might be better.
>
> >
> > An alternative implementation of BidiMap would then be needed, which would
> > be useful as it would not require objects to be comparable.
>
> +1
>
> >
> > With these new interfaces, decorators could then be written as required.
> >
> > Anything obvious I've missed? Any volunteers?
> >
> > Stephen
> >
> >
> >
>
> 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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by Phil Steitz <ph...@steitz.com>.
See comments inline.
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.
I agree, though I would favor either spelling out "Bidirectional" or
using "Invertible" or "OneToOne" as the prefix. Unless the term
"BidiMap" is a "familiar" term, I would suggest picking a full word for
the prefix.
>
> 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.
Yes, and it is important to distinguish between what is required by the
interface and how the implementation happens to work. The current class
header comments are a bit confusing/nonsensical on this. How things are
"stored" is irrelevant to the interface.
>
> BidiMap
> ----------
> Map methods +
> BidiMap inverseBidiMap()
> Object getKeyForValue(Object value)
Could drop "ForValue" here.
> Object removeValue(Object value)
> Set entrySetByValue()
> Set keySetByValue()
> Collection valuesByValue()
> (these method names are from DoubleOrderedMap, and seem OKish)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
InvertibleTreeMap or BidirectionalTreeMap might be better.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
+1
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
>
>
>
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
Re: [collections] BidiMap / DoubleOrderedMap
Posted by __matthewHawthorne <ma...@phreaker.net>.
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)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
---------------------------------------------------------------------
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 Phil Steitz <ph...@steitz.com>.
See comments inline.
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.
I agree, though I would favor either spelling out "Bidirectional" or
using "Invertible" or "OneToOne" as the prefix. Unless the term
"BidiMap" is a "familiar" term, I would suggest picking a full word for
the prefix.
>
> 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.
Yes, and it is important to distinguish between what is required by the
interface and how the implementation happens to work. The current class
header comments are a bit confusing/nonsensical on this. How things are
"stored" is irrelevant to the interface.
>
> BidiMap
> ----------
> Map methods +
> BidiMap inverseBidiMap()
> Object getKeyForValue(Object value)
Could drop "ForValue" here.
> Object removeValue(Object value)
> Set entrySetByValue()
> Set keySetByValue()
> Collection valuesByValue()
> (these method names are from DoubleOrderedMap, and seem OKish)
>
> SortedBidiMap
> ----------------
> BidiMap + SortedMap +
> inverseSortedBidiMap()
> subMapByValue()
> headMapByValue()
> tailMapByValue()
>
> The existing DoubleOrderedMap is an implementation of SortedBidiMap. However
> I would like to rename it to TreeBidiMap.
InvertibleTreeMap or BidirectionalTreeMap might be better.
>
> An alternative implementation of BidiMap would then be needed, which would
> be useful as it would not require objects to be comparable.
+1
>
> With these new interfaces, decorators could then be written as required.
>
> Anything obvious I've missed? Any volunteers?
>
> Stephen
>
>
>
Phil
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>