Implement the TODO methods in JAVA. (Task : Implement map using a sorted List) C
ID: 3710024 • Letter: I
Question
Implement the TODO methods in JAVA. (Task : Implement map using a sorted List)
CODE:
import java.util.List;
import java.util.ArrayList;
public class SortedListMap<K extends Comparable<K>, V> implements Map<K, V> {
/*
* This nested class contains a completed implementation of Entry
* which you should use within SortedListMap.
*
* You do not need to edit this class.
*/
private class Entry<K extends Comparable<K>, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {return key;}
public V getValue() {return value;}
public void setKey(K key) {this.key = key;}
public void setValue(V value) {this.value = value;}
}
// The entry list
private final List<Entry<K, V>> entries = new ArrayList<>();
@Override
public int size() {
return entries.size();
}
@Override
public boolean isEmpty() {
return entries.isEmpty();
}
// TODO: implement the remaining methods!
/**
* Tests whether the map contains the given key.
*
* @param k
* a key
* @return true if the map contains the given key, false otherwise
*/
@Override
public boolean containsKey(K key) {
// TODO
return false;
}
/**
* Returns the value associated with the given key if any.
*
* @param k
* a key
* @return the value associated with the given key (or null if none present)
*/
@Override
public V get(K key) {
//TODO
return null;
}
/**
* Inserts an entry into the map with the given key and value.
*
* @param k
* a key
* @param v
* a value
*/
@Override
public void put(K key, V value) {
//TODO
}
/**
* Removes the value associated with the given key if any, and returns it.
*
* @param k
* a key
* @return the removed value (or null if none present)
*/
@Override
public V remove(K key) {
//TODO
return null;
}
// Returns index of entry with key, or -1 if not found
private int binarySearch(K key) {
int min = 0;
int max = entries.size();
while (min < max) {
int mid = (max + min)/2;
K midKey = entries.get(mid).key;
if (midKey.equals(key)) {
return mid;
} else if (midKey.compareTo(key) < 0) {
// key after midKey
min = mid + 1;
} else {
// key before midKey
max = mid;
}
}
// not found
return -1;
}
public static void main(String[] args) {
System.out.println("Running the main method in SortedListMap");
}
}
Explanation / Answer
Given below is the completed code for the question. Please use any test driver code to test the SortedListMap implementation.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you
import java.util.List;
import java.util.ArrayList;
public class SortedListMap<K extends Comparable<K>, V> implements Map<K, V> {
/*
* This nested class contains a completed implementation of Entry
* which you should use within SortedListMap.
*
* You do not need to edit this class.
*/
private class Entry<K extends Comparable<K>, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {return key;}
public V getValue() {return value;}
public void setKey(K key) {this.key = key;}
public void setValue(V value) {this.value = value;}
}
// The entry list
private final List<Entry<K, V>> entries = new ArrayList<>();
@Override
public int size() {
return entries.size();
}
@Override
public boolean isEmpty() {
return entries.isEmpty();
}
// TODO: implement the remaining methods!
/**
* Tests whether the map contains the given key.
*
* @param k
* a key
* @return true if the map contains the given key, false otherwise
*/
@Override
public boolean containsKey(K key) {
int index = binarySearch(key);
if(index == -1)
return false;
else
return true;
}
/**
* Returns the value associated with the given key if any.
*
* @param k
* a key
* @return the value associated with the given key (or null if none present)
*/
@Override
public V get(K key) {
int index = binarySearch(key);
if(index == -1)
return null;
else
return entries.get(index).value;
}
/**
* Inserts an entry into the map with the given key and value.
*
* @param k
* a key
* @param v
* a value
*/
@Override
public void put(K key, V value) {
int i;
Entry<K, V> e = new Entry<K, V> (key, value);
if(entries.isEmpty())
{
entries.add(e);
return;
}
for(i = 0; i < entries.size(); i++)
{
Entry<K,V> e2 = entries.get(i);
if(e2.key.compareTo(key) >= 0) //found a key which is higher than the current key to be inserted
break;
}
entries.add(i, e); //insert at the index found
}
/**
* Removes the value associated with the given key if any, and returns it.
*
* @param k
* a key
* @return the removed value (or null if none present)
*/
@Override
public V remove(K key) {
int index = binarySearch(key);
if(index == -1)
return null;
else
return entries.remove(index).value;
}
// Returns index of entry with key, or -1 if not found
private int binarySearch(K key) {
int min = 0;
int max = entries.size();
while (min < max) {
int mid = (max + min)/2;
K midKey = entries.get(mid).key;
if (midKey.equals(key)) {
return mid;
} else if (midKey.compareTo(key) < 0) {
// key after midKey
min = mid + 1;
} else {
// key before midKey
max = mid;
}
}
// not found
return -1;
}
public static void main(String[] args) {
System.out.println("Running the main method in SortedListMap");
}
}