Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Content-Class: urn:content-classes:message
Message-ID: <3F6F9A45.8000601@steitz.com>
Date: Mon, 22 Sep 2003 17:56:37 -0700
From: "Phil Steitz" <phil@steitz.com>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.1) Gecko/20020830
MIME-Version: 1.0
To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Subject: Re: [collections] BidiMap / DoubleOrderedMap
References: <007d01c37f74$9ca811a0$b7768051@oemcomputer>
 <3F6F6BD7.60305@phreaker.net> <005401c3815f$27dbd360$7a7c8051@oemcomputer>
 <3F6F87C2.4030706@phreaker.net>
Content-Type: text/plain;
	format=flowed;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit

__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" <matth@phreaker.net>
>> To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
>> Sent: Monday, September 22, 2003 10:38 PM
>> Subject: Re: [collections] BidiMap / DoubleOrderedMap
>>
>>
>>
>>> I've started some work on converting DoubleOrderedMap to TreeBidiMap.
>>>
>>> What is the suggested name for the basic BidiMap implementation which is
>>> n't sorted?  DefaultBidiMap?
>>>
>>>
>>>
>>>
>>> Stephen Colebourne wrote:
>>>
>>>
>>>> I have been prompted to take a look at DoubleOrderedMap by bugzilla and
>>>
>>
>> been
>>
>>>> a little surprised by what I found. Given the history of collections,
>>>
>>
>> what
>>
>>>> we have is a single implementation brought in from an external project.
>>>> [collections] should do better :-)
>>>>
>>>> A bidirectional map is a relatively standard concept in computing. 
>>>> It is
>>>
>>
>> a
>>
>>>> map where you can use a key to find a value, or a value to find a key
>>>
>>
>> with
>>
>>>> equal ease. This deserves its own interface in [collections] - BidiMap.
>>>>
>>>> The DoubleOrderedMap class goes beyond this by being Sorted, 
>>>> effectively
>>>> holding all entries in a Compared order always. This effectively 
>>>> equates
>>>
>>
>> to
>>
>>>> a second interface in [collections] - SortedBidiMap.
>>>>
>>>> BidiMap
>>>> ----------
>>>> Map methods +
>>>> BidiMap inverseBidiMap()
>>>> Object getKeyForValue(Object value)
>>>> Object removeValue(Object value)
>>>> Set entrySetByValue()
>>>> Set keySetByValue()
>>>> Collection valuesByValue()
>>>> (these method names are from DoubleOrderedMap, and seem OKish)
>>>>
>>>> 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