Implement map, where following operations are
performed in constant time.
a. Get
the value by Key
b. Get
the key be value
c. Remove
<key, value> pair by key
d. Remove
<key, value> pair by value.
e. Check
for the existence of key
f. Check
for the existence of value
g. Get
the size of the map
Assume there is one-to-one mapping between
<key, value> pairs. By using two maps (one to keep track of <key,
value> mappings and other to keep track of <value, key> mappings), we
can implements Bijective map easily. Following is the complete working
application.
import java.util.HashMap; import java.util.Map; public class BijectiveMap<K, V> { private Map<K, V> map = new HashMap<K, V>(); private Map<V, K> inverseMap = new HashMap<V, K>(); public void put(K key, V value) { map.put(key, value); inverseMap.put(value, key); } public V getValue(K key) { return map.get(key); } public K getKey(V value) { return inverseMap.get(value); } @SuppressWarnings("unchecked") public RemovedKey<K, V> removeKeyValuePairByKey(K key) { if (key == null || !map.containsKey(key)) { return RemovedKey.EMPTY_ENTRY; } V value = map.remove(key); inverseMap.remove(value); RemovedKey<K, V> removedKey = new RemovedKey<>(key, value); return removedKey; } @SuppressWarnings("unchecked") public RemovedKey<K, V> removeKeyValuePairByValue(V value) { if (value == null || !inverseMap.containsKey(value)) { return RemovedKey.EMPTY_ENTRY; } K key = inverseMap.remove(value); map.remove(key); RemovedKey<K, V> removedKey = new RemovedKey<>(key, value); return removedKey; } public boolean containsKey(Object key) { return map.containsKey(key); } public boolean containsValue(Object value) { return inverseMap.containsKey(value); } public boolean isEmpty() { return map.isEmpty(); } public int size() { return map.size(); } public static class RemovedKey<K, V> { K key; V value; @SuppressWarnings("rawtypes") public static final RemovedKey EMPTY_ENTRY = new RemovedKey(); private RemovedKey() { key = null; value = null; } public RemovedKey(K key, V value) { this.key = key; this.value = value; } @SuppressWarnings("rawtypes") public static RemovedKey getEmptyEntry() { return EMPTY_ENTRY; } } }
public class BijectiveMapTest { public static void main(String args[]) { BijectiveMap<Integer, String> bijMap = new BijectiveMap<>(); bijMap.put(1, "Hari krishna"); bijMap.put(2, "Sudhir"); System.out.println("Value associated with key 1 is : " + bijMap.getValue(1)); System.out.println("Value associated with key 2 is : " + bijMap.getValue(2)); System.out.println("Key associated with value \"Hari krishna\" is : " + bijMap.getKey("Hari krishna")); System.out.println("Key associated with value \"Sudhir\" is : " + bijMap.getKey("Sudhir")); } }
Output
Value associated with key 1 is : Hari krishna Value associated with key 2 is : Sudhir Key associated with value "Hari krishna" is : 1 Key associated with value "Sudhir" is : 2
You
may like
No comments:
Post a Comment