Path: csiph.com!x330-a1.tempe.blueboxinc.net!aioe.org!feeder.news-service.com!news.albasani.net!.POSTED!not-for-mail
From: Sebastian <sebastian@undisclosed.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Concurrent bidirectional one-to-many map?
Date: Sat, 07 May 2011 11:43:38 +0200
Organization: albasani.net
Lines: 86
Message-ID: <iq348b$iv1$1@news.albasani.net>
References: <iq1kf0$ee2$1@news.albasani.net> <iq1mmc$hbv$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net n3uwcWJ3zojrkeXBYpENFqG32BqCggzDHwBbE2mwFcWtx7h954vRPvZx0Tq7SCGEiZNW6WFUqrNyIb8aBtX0gA==
NNTP-Posting-Date: Sat, 7 May 2011 09:43:39 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="TxcHfNU9Z2rAX7xbLjcDlHSOuaugIM4wGggc+XkqPcebtXPiZwaakhCkn4fLX4VZrn/Sb8v1nFyjKSWNCAfkQyyAkHQjktUveqfIAFF2Dm9e3IaUmWzTimo/hqWkRYNA"; mail-complaints-to="abuse@albasani.net"
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9
In-Reply-To: <iq1mmc$hbv$1@dont-email.me>
Cancel-Lock: sha1:sToistF6o1Lqwb/jEAOFsSxiogk=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3753

Am 06.05.2011 22:45, schrieb markspace:
> On 5/6/2011 1:07 PM, Sebastian wrote:
>> Does anyone know of a concurrent bidirectional one-to-many
>> map implementation?
>>
>> By bidirectional I mean that I can lookup keys by values, by
>> one-to-many I mean that the value end of the map is a list or
>> set, and by concurrent I mean that I do not need to synchronize
>> externally and get performance comparable to that of
>> java.util.concurrent.ConcurrentHashMap in both directions.
>>
>> If this beast doesn't exist, how would I go about inventing it?
>> I must say that I am by no means any sort of concurrency guru...
>>
>> -- Sebastian
>>
>
>
> Can you just put both keys and values in as the key? Something like:
>
> Map<Key,Key> myMap = new ConcurrentHashMap();
> // add key k and value v
> Key holder = new Key( k, v, KEY );
> myMap.put( holder, holder );
> holder = new Key( v, k, VALUE )
> myMap.put( holder, holder );
> ...
>
> public class Key<K,V> {
> public enum KeyValue {KEY,VALUE};
> private k key;
> private V value;
> private KeyValue keyOrValue;
>
> public Key( K key, V value, KeyValue keyOrValue ) {
> this.key = key;
> this.value = value;
> this.keyOrValue = keyOrValue;
> }
> // must also override hashcode and equals...
> }
>
>
> This way when you add something, it gets added as both key and value.
> You might want to override "put" to do that automatically. When you look
> up either a key or a value, you'll find both.
>
> There may be better ways of doing this, it's just the first thing that I
> thought of. Also the code above is meant more as a sketch than a
> rigorous code example.
>

Thanks for the idea. I do not yet see how to deal with the
one-to-many aspect of my problem.

To give an example, I'm trying to solve a problem like this:
Associate tasks with workspaces, where a workspace may hold many
tasks,but a task may be associate with at most one workspace.

Idea:

    private ConcurrentMap<Item, Workspace> wsMap =
              new ConcurrentHashMap<Item, Workspace>();

     public boolean isAssigned( Item item ) {
         return wsMap.containsKey( item );
     }

     public void assign( Item item, Workspace ws ) {
         wsMap.putIfAbsent( item, ws );
         if( !ws.equals( wsMap.get( item) ) ) {
            throw new NotAssignableException();
         }
     }


Now I want to be able to close a workspace, releasing all tasks
to be assignable again to other workspaces.

     public void closeWorkspace( Workspace ws ) {
       // how do this efficiently? iterate over all
       // entries (holding a write lock) and remove it
       // when the value equals ws?
     }

-- Sebastian