I need help with the following Java code. Implement all missing methods of Sorte
ID: 3907384 • Letter: I
Question
I need help with the following Java code.
Implement all missing methods of SortedLinkedDictionary.java . You are allowed to throw UnsupportedOperationException from remove methods of both iterators.
/**
*An interface for a dictionary with distinct search keys.
*/
import java.util.Iterator;
public interface DictionaryInterface<K, V>
{
/**
* Adds a new entry to this dictionary. If the given search key already exists
* in the dictionary, replaces the corresponding value.
*
* @param key
* An object search key of the new entry.
* @param value
* An object associated with the search key.
* @return Either null if the new entry was added to the dictionary or the
* value that was associated with key if that value was replaced.
*/
public V add(K key, V value);
/**
* Removes a specific entry from this dictionary.
*
* @param key
* An object search key of the entry to be removed.
* @return Either the value that was associated with the search key or null if
* no such object exists.
*/
public V remove(K key);
/**
* Retrieves from this dictionary the value associated with a given search key.
*
* @param key
* An object search key of the entry to be retrieved.
* @return Either the value that is associated with the search key or null if
* no such object exists.
*/
public V getValue(K key);
/**
* Sees whether a specific entry is in this dictionary.
*
* @param key
* An object search key of the desired entry.
* @return True if key is associated with an entry in the dictionary.
*/
public boolean contains(K key);
/**
* Creates an iterator that traverses all search keys in this dictionary.
*
* @return An iterator that provides sequential access to the search keys in
* the dictionary.
*/
public Iterator<K> getKeyIterator();
/**
* Creates an iterator that traverses all values in this dictionary.
*
* @return An iterator that provides sequential access to the values in this
* dictionary.
*/
public Iterator<V> getValueIterator();
/**
* Sees whether this dictionary is empty.
*
* @return True if the dictionary is empty.
*/
public boolean isEmpty();
/**
* Gets the size of this dictionary.
*
* @return The number of entries (key-value pairs) currently in the dictionary.
*/
public int getSize();
/** Removes all entries from this dictionary. */
public void clear();
} // end DictionaryInterface
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* A class that implements a dictionary by using a sorted linked chain. The
* dictionary has distinct search keys.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class SortedLinkedDictionary<K extends Comparable<? super K>, V> implements DictionaryInterface<K, V>
{
private Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public SortedLinkedDictionary()
{
initializeDataFields();
} // end default constructor
public V add(K key, V value)
{
V result = null;
// Search chain until you either find a node containing key
// or locate where it should be
Node currentNode = firstNode;
Node nodeBefore = null;
while ((currentNode != null) && (key.compareTo(currentNode.getKey()) > 0))
{
nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
if ((currentNode != null) && key.equals(currentNode.getKey()))
{
// Key in dictionary; replace corresponding value
result = currentNode.getValue(); // Get old value
currentNode.setValue(value); // Replace value
} else // Key not in dictionary; add new node in proper order
{
// Assumes key and value are not null
Node newNode = new Node(key, value); // Create new node
if (nodeBefore == null)
{ // Add at beginning (includes empty dictionary)
newNode.setNextNode(firstNode);
firstNode = newNode;
} else // Add elsewhere in non-empty list
{
newNode.setNextNode(currentNode); // currentNode is after new node
nodeBefore.setNextNode(newNode); // nodeBefore is before new node
} // end if
numberOfEntries++; // Increase length for both cases
} // end if
return result;
} // end add
/*
* < Implementations of other methods in DictionaryInterface. > . . .
*/
private class Node
{
private K key;
private V value;
private Node next;
/*
* < Constructors and the methods getKey, getValue, setValue, getNextNode, and
* setNextNode are here. There is no setKey. > . . .
*/
} // end Node
//Since iterators implement Iterator, methods must be public
private class KeyIterator implements Iterator<K>
{
private Node nextNode;
private KeyIterator() { nextNode = firstNode; } // end default constructor
public boolean hasNext() { return nextNode != null; } // end hasNext
public K next()
{
K result;
if (hasNext())
{
result = nextNode.getKey();
nextNode = nextNode.getNextNode();
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end KeyIterator
} // end SortedLinkedDictionary
Explanation / Answer
Given below is the code for the question.
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.Iterator;
import java.util.NoSuchElementException;
/**
* A class that implements a dictionary by using a sorted linked chain. The
* dictionary has distinct search keys.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class SortedLinkedDictionary<K extends Comparable<? super K>, V> implements DictionaryInterface<K, V>
{
private Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public SortedLinkedDictionary()
{
initializeDataFields();
} // end default constructor
private void initializeDataFields() {
firstNode = null;
numberOfEntries = 0;
}
public V add(K key, V value)
{
V result = null;
// Search chain until you either find a node containing key
// or locate where it should be
Node currentNode = firstNode;
Node nodeBefore = null;
while ((currentNode != null) && (key.compareTo(currentNode.getKey()) > 0))
{
nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
if ((currentNode != null) && key.equals(currentNode.getKey()))
{
// Key in dictionary; replace corresponding value
result = currentNode.getValue(); // Get old value
currentNode.setValue(value); // Replace value
} else // Key not in dictionary; add new node in proper order
{
// Assumes key and value are not null
Node newNode = new Node(key, value); // Create new node
if (nodeBefore == null)
{ // Add at beginning (includes empty dictionary)
newNode.setNextNode(firstNode);
firstNode = newNode;
} else // Add elsewhere in non-empty list
{
newNode.setNextNode(currentNode); // currentNode is after new node
nodeBefore.setNextNode(newNode); // nodeBefore is before new node
} // end if
numberOfEntries++; // Increase length for both cases
} // end if
return result;
} // end add
/*
* < Implementations of other methods in DictionaryInterface. > . . .
*/
private class Node
{
private K key;
private V value;
private Node next;
/*
* < Constructors and the methods getKey, getValue, setValue, getNextNode, and
* setNextNode are here. There is no setKey. > . . .
*/
Node(K key, V value){
this.key = key;
this.value = value;
}
K getKey(){
return key;
}
V getValue(){
return value;
}
void setValue(V value){
this.value = value;
}
Node getNextNode(){
return next;
}
void setNextNode(Node next){
this.next = next;
}
} // end Node
//Since iterators implement Iterator, methods must be public
public class KeyIterator implements Iterator<K>
{
private Node nextNode;
private KeyIterator() { nextNode = firstNode; } // end default constructor
public boolean hasNext() { return nextNode != null; } // end hasNext
public K next()
{
K result;
if (hasNext())
{
result = nextNode.getKey();
nextNode = nextNode.getNextNode();
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end KeyIterator
public class ValueIterator implements Iterator<V>
{
private Node nextNode;
private ValueIterator() { nextNode = firstNode; } // end default constructor
public boolean hasNext() { return nextNode != null; } // end hasNext
public V next()
{
V result;
if (hasNext())
{
result = nextNode.getValue();
nextNode = nextNode.getNextNode();
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end ValueIterator
@Override
public V remove(K key) {
Node currentNode = firstNode;
Node nodeBefore = null;
while ((currentNode != null) && (key.compareTo(currentNode.getKey()) > 0))
{
nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
if(currentNode == null || key.compareTo(currentNode.getKey()) != 0) //not found
return null;
if(nodeBefore == null)
firstNode = currentNode.getNextNode();
else
nodeBefore.setNextNode(currentNode.getNextNode());
numberOfEntries--;
return currentNode.getValue();
}
@Override
public V getValue(K key) {
Node currentNode = firstNode;
while ((currentNode != null) && (key.compareTo(currentNode.getKey()) > 0))
{
currentNode = currentNode.getNextNode();
} // end while
if(currentNode == null || key.compareTo(currentNode.getKey()) != 0) //not found
return null;
return currentNode.getValue();
}
@Override
public boolean contains(K key) {
if(getValue(key) != null)
return true;
else
return false;
}
@Override
public Iterator getKeyIterator() {
return new KeyIterator();
}
@Override
public Iterator getValueIterator() {
return new ValueIterator();
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0;
}
@Override
public int getSize() {
return numberOfEntries;
}
@Override
public void clear() {
numberOfEntries = 0;
firstNode = null;
}
} // end SortedLinkedDictionary