Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Guava: Set<K> + Function<K,V> = Map<K,V>?

Is there an idiomatic way to take a Set<K> and a Function<K,V>, and get a Map<K,V> live view? (i.e. the Map is backed by the Set and Function combo, and if e.g. an element is added to the Set, then the corresponding entry also exists in the Map).

(see e.g. Collections2.filter for more discussion on live views)


What if a live view is not needed? Is there something better than this:

public static <K,V> Map<K,V> newMapFrom(Set<K> keys, Function<? super K,V> f) {     Map<K,V> map = Maps.newHashMap();     for (K k : keys) {         map.put(k, f.apply(k));     }     return map; } 
like image 946
polygenelubricants Avatar asked Oct 06 '10 03:10

polygenelubricants


1 Answers

Creating a Map from a Set and a Function

Here are two classes that should each do the job. The first just shows a map view of the set, while the second can write values back to the set through a special interface.

Call Syntax:

Map<K,V> immutable = new SetBackedMap<K,V>(Set<K> keys, Function<K,V> func); Map<K,V> mutable = new MutableSetBackedMap<K,V>(Set<K> keys, Function<K,V> func); 

Where to put this code?

Side note: If guava were my library, I'd make them accessible through the Maps class:

Map<K,V> immutable = Maps.immutableComputingMap(Set<K> keys, Function<K,V> func); Map<K,V> mutable = Maps.mutableComputingMap(Set<K> keys, Function<K,V> func); 

Immutable version:

I have implemented this as a one-way view:

  • Changes to the set are reflected in the map, but not vice-versa (and you can't change the map anyway, the put(key, value) method isn't implemented).
  • The entrySet() iterator uses the set iterator internally, so it will also inherit the internal iterator's handling of ConcurrentModificationException.
  • Both put(k,v) and entrySet().iterator().remove() will throw UnsupportedOperationException.
  • Values are cached in a WeakHashMap, with no special concurrency handling, i.e. there is no synchronization at any level. This will do for most cases, but if your function is expensive, you might want to add some locking.

Code:

public class SetBackedMap<K, V> extends AbstractMap<K, V>{      private class MapEntry implements Entry<K, V>{         private final K key;         public MapEntry(final K key){             this.key = key;         }         @Override         public K getKey(){             return this.key;         }         @Override         public V getValue(){             V value = SetBackedMap.this.cache.get(this.key);             if(value == null){                 value = SetBackedMap.this.funk.apply(this.key);                 SetBackedMap.this.cache.put(this.key, value);             }             return value;         }         @Override         public V setValue(final V value){             throw new UnsupportedOperationException();         }     }      private class EntrySet extends AbstractSet<Entry<K, V>>{          public class EntryIterator implements Iterator<Entry<K, V>>{             private final Iterator<K> inner;             public EntryIterator(){                 this.inner = EntrySet.this.keys.iterator();             }             @Override             public boolean hasNext(){                 return this.inner.hasNext();             }             @Override             public Map.Entry<K, V> next(){                 final K key = this.inner.next();                 return new MapEntry(key);             }             @Override             public void remove(){                 throw new UnsupportedOperationException();             }         }          private final Set<K> keys;          public EntrySet(final Set<K> keys){             this.keys = keys;         }          @Override         public Iterator<Map.Entry<K, V>> iterator(){             return new EntryIterator();         }          @Override         public int size(){             return this.keys.size();         }      }      private final WeakHashMap<K, V> cache;     private final Set<Entry<K, V>> entries;     private final Function<? super K, ? extends V> funk;      public SetBackedMap(         final Set<K> keys, Function<? super K, ? extends V> funk){         this.funk = funk;         this.cache = new WeakHashMap<K, V>();         this.entries = new EntrySet(keys);     }      @Override     public Set<Map.Entry<K, V>> entrySet(){         return this.entries;     }  } 

Test:

final Map<Integer, String> map =     new SetBackedMap<Integer, String>(         new TreeSet<Integer>(Arrays.asList(             1, 2, 4, 8, 16, 32, 64, 128, 256)),         new Function<Integer, String>(){              @Override             public String apply(final Integer from){                 return Integer.toBinaryString(from.intValue());             }         }); for(final Map.Entry<Integer, String> entry : map.entrySet()){     System.out.println(         "Key: " + entry.getKey()         + ", value: " + entry.getValue()); } 

Output:

Key: 1, value: 1 Key: 2, value: 10 Key: 4, value: 100 Key: 8, value: 1000 Key: 16, value: 10000 Key: 32, value: 100000 Key: 64, value: 1000000 Key: 128, value: 10000000 Key: 256, value: 100000000 

Mutable Version:

While I think it's a good idea to make this one-way, here's a version for Emil that provides a two-way view (it's a variation of Emil's variation of my solution :-)). It requires an extended map interface that I'll call ComputingMap to make clear that this is a map where it doesn't make sense to call put(key, value).

Map interface:

public interface ComputingMap<K, V> extends Map<K, V>{     boolean removeKey(final K key);     boolean addKey(final K key); } 

Map implementation:

public class MutableSetBackedMap<K, V> extends AbstractMap<K, V> implements     ComputingMap<K, V>{      public class MapEntry implements Entry<K, V>{          private final K key;          public MapEntry(final K key){             this.key = key;         }          @Override         public K getKey(){             return this.key;         }          @Override         public V getValue(){             V value = MutableSetBackedMap.this.cache.get(this.key);             if(value == null){                 value = MutableSetBackedMap.this.funk.apply(this.key);                 MutableSetBackedMap.this.cache.put(this.key, value);             }             return value;         }          @Override         public V setValue(final V value){             throw new UnsupportedOperationException();         }      }      public class EntrySet extends AbstractSet<Entry<K, V>>{          public class EntryIterator implements Iterator<Entry<K, V>>{              private final Iterator<K> inner;              public EntryIterator(){                 this.inner = MutableSetBackedMap.this.keys.iterator();             }              @Override             public boolean hasNext(){                 return this.inner.hasNext();             }              @Override             public Map.Entry<K, V> next(){                 final K key = this.inner.next();                 return new MapEntry(key);             }              @Override             public void remove(){                 throw new UnsupportedOperationException();             }          }          public EntrySet(){         }          @Override         public Iterator<Map.Entry<K, V>> iterator(){             return new EntryIterator();         }          @Override         public int size(){             return MutableSetBackedMap.this.keys.size();         }      }      private final WeakHashMap<K, V> cache;     private final Set<Entry<K, V>> entries;     private final Function<? super K, ? extends V> funk;     private final Set<K> keys;      public MutableSetBackedMap(final Set<K> keys,         final Function<? super K, ? extends V> funk){         this.keys = keys;         this.funk = funk;         this.cache = new WeakHashMap<K, V>();         this.entries = new EntrySet();     }      @Override     public boolean addKey(final K key){         return this.keys.add(key);     }      @Override     public boolean removeKey(final K key){         return this.keys.remove(key);     }      @Override     public Set<Map.Entry<K, V>> entrySet(){         return this.entries;     }  } 

Test:

public static void main(final String[] args){     final ComputingMap<Integer, String> map =         new MutableSetBackedMap<Integer, String>(             new TreeSet<Integer>(Arrays.asList(                 1, 2, 4, 8, 16, 32, 64, 128, 256)),             new Function<Integer, String>(){                  @Override                 public String apply(final Integer from){                     return Integer.toBinaryString(from.intValue());                 }             });     System.out.println(map);     map.addKey(3);     map.addKey(217);     map.removeKey(8);     System.out.println(map); } 

Output:

{1=1, 2=10, 4=100, 8=1000, 16=10000, 32=100000, 64=1000000, 128=10000000, 256=100000000} {1=1, 2=10, 3=11, 4=100, 16=10000, 32=100000, 64=1000000, 128=10000000, 217=11011001, 256=100000000} 
like image 63
Sean Patrick Floyd Avatar answered Oct 17 '22 12:10

Sean Patrick Floyd