Я реализую мультикарту, используя linkedlist в Java.Но что-то не так с двумя методами удаления и методом замены.Я тестировал все три метода с помощью Junit, и они все прошли, но не смогли пройти грейдер.
В реализации используются два типа узлов:
MapNode: эти узлы будут использоваться для хранения ключей и ссылки на список значений, связанных с этим ключом.
ValueNode: эти узлы будут использоваться для хранения значений, связанных с ключом.
На диаграмме ниже показана структура LinkedList_Multimap.https://imgur.com/a/EUD4DeE
/* Replaces the entry for the specified key only if currently mapped to the
* specified value.
*
* Throws: NullPointerException - if the specified key or
* oldValue or newValue is null.
* IllegalStateException - if the key is not
* in the multimap, or oldValue is not already associated with key; or if
* oldValue and newValue are the same.
*
* @param key - key with which the specified value is associated
* @param oldValue - value expected to be associated with the specified key
* @param newValue - value to be associated with the specified key
* @return true if the value was replaced
*/
@Override
public boolean replace(K key, V oldValue, V newValue)
{
if(key==null || oldValue == null || newValue==null)
throw new NullPointerException("Something is null!");
if(oldValue.equals(newValue))
throw new IllegalStateException("Old and new values are the same!");
if(head == null || head.getValues() == null) return false;
MapNode<K, V> curr = head;
while(!curr.getKey().equals(key)){
if(curr.getNext()==null){ //no existing key
throw new IllegalStateException("The key is not in the multimap!");
}
curr = curr.getNext();
}
ValueNode<V> currV = curr.getValues();
if(currV.getValue().equals(oldValue)) {
ValueNode<V> newV = new ValueNode<>(newValue);
curr.setValues(newV);
newV.setNext(currV.getNext());
return true;
}
ValueNode<V> preV =null;
while(!currV.getValue().equals(oldValue)){
if(currV.getNext()==null){ //no existing old value
throw new IllegalStateException("The value is not associated with the key!");
}
if(curr.getNext()!= null && curr.getNext().getValues().equals(oldValue)) {
preV = new ValueNode<>(newValue);
}
currV = currV.getNext();
}
ValueNode<V> newV = new ValueNode<>(newValue);
if(preV==null) {
curr.setValues(newV);
}
else {
preV.setNext(newV);
}
newV.setNext(currV.getNext());
return true;
}
-> Я получил исключение NullPointerException при замене тестирования.
/*
* Removes the mapping for a key from this map if it is present. The key and
* its associated values are removed. Throws:
* NullPointerException - if the
* specified key is null.
* IllegalStateException - if key is not in the
* multimap
*
* @param key
* - key whose mapping is to be removed from the multimap
* @return the head of the list of values mapped to the key or null if the map contained
* no mapping for the key
*/
@Override
public ValueNode<V> remove(Object key)
{
if(key == null)
throw new NullPointerException("The key is null!");
if(head == null)
return null;
MapNode<K, V> curr = head;
if(curr.getKey().equals(key)) {
head = curr.getNext();
curr.setNext(null);
size --;
return curr.getValues();
}
MapNode<K, V> prev = null;
while(!curr.getKey().equals(key)){
if(curr.getNext()==null){ //no existing key
throw new IllegalStateException("The key is not in the multimap!");
}
if(curr.getNext()!= null && curr.getNext().getKey().equals(key)) {
prev = curr;
}
curr = curr.getNext();
}
prev.setNext(curr.getNext());
curr.setNext(null);
size--;
return curr.getValues();
}
-> Я получил сообщение «ожидается <2>, но было <3>» для проверки удаления ключа.
/*
* Removes the entry for the specified key only if it is currently mapped to
* the specified value. value is removed from the list of values. If value
* is the only value associated with key, then key is also removed.
* Throws:
* NullPointerException - if the specified key or value is null.
* IllegalStateException - if key is not in the multimap.
* key is not removed if it is not mapped with value
*
* @param key
* - key with which the specified value is associated
* @param value
* - value expected to be associated with the specified key
* @return true if the value was removed.
*/
@Override
public boolean remove(Object key, Object value)
{
if(key == null || value == null)
throw new NullPointerException("The key or the value is null!");
if(head == null)
return false;
MapNode<K, V> curr = head;
while(!curr.getKey().equals(key)){
if(curr.getNext()==null){ //no existing key
throw new IllegalStateException("The key is not in the multimap!");
}
curr = curr.getNext();
}
// if(curr.getValues()==null)
// return false;
ValueNode<V> currV = curr.getValues();
ValueNode<V> preV = null;
if(currV.getValue().equals(value)) {
if(currV.getNext()==null) {
remove(key);
return true;
}
curr.setValues(currV.getNext());
currV.setNext(null);
return true;
}
while (!currV.getValue().equals(value)) {
if(currV.getNext()==null)
return false;
if( currV.getNext()!= null && currV.getNext().getValue().equals(value))
preV = curr.getValues();
currV = currV.getNext();
}
preV.setNext(currV.getNext());
currV.setNext(null);
return true;
}
-> Я получил сообщение "ожидаемый <3>, но было <5>" для удаления ключа и проверки значения.