Saturday 8 October 2016

Implement Bijective Map

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