Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #3753

Re: Concurrent bidirectional one-to-many map?

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-06 22:07 +0200
  Re: Concurrent bidirectional one-to-many map? markspace <-@.> - 2011-05-06 13:45 -0700
    Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-07 11:43 +0200
      Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-07 07:59 -0400
        Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-07 12:49 -0400
          Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-07 21:34 +0200
      Re: Concurrent bidirectional one-to-many map? Patricia Shanahan <pats@acm.org> - 2011-05-07 06:40 -0700
        Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-08 04:51 +0100
          Re: Concurrent bidirectional one-to-many map? Robert Klemme <shortcutter@googlemail.com> - 2011-05-09 06:43 -0700
            Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-09 18:28 +0100
              Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-09 22:57 +0200
                Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-09 18:36 -0400
                Re: Concurrent bidirectional one-to-many map? Tom Anderson <twic@urchin.earth.li> - 2011-05-10 08:34 +0100
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 10:09 +0200
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 10:51 +0200
                Re: Concurrent bidirectional one-to-many map? Robert Klemme <shortcutter@googlemail.com> - 2011-05-11 04:55 -0700
                Re: Concurrent bidirectional one-to-many map? Lew <noone@lewscanon.com> - 2011-05-11 09:00 -0400
                Re: Concurrent bidirectional one-to-many map? Sebastian <sebastian@undisclosed.invalid> - 2011-05-11 20:47 +0200
      Re: Concurrent bidirectional one-to-many map? markspace <-@.> - 2011-05-07 09:35 -0700
      Re: Concurrent bidirectional one-to-many map? Michal Kleczek <kleku75@gmail.com> - 2011-05-09 16:42 +0200
  Re: Concurrent bidirectional one-to-many map? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-07 03:46 -0700

csiph-web