Мне поручено реализовать метод remove () для моего Sorted Binary Tree.Мне нужно пройти набор тестов, которые были назначены нашим учителем, и я изо всех сил стараюсь это сделать.Это код, который у меня есть в настоящее время, который был заимствован из нашего учебника.
@Override
@SuppressWarnings("unchecked")
public V remove(Object key) throws NoSuchElementException {
if(!containsKey((K) key)){
throw new NoSuchElementException();
}
ReturnObject oldEntry = new ReturnObject(null);
SortedTreeMap<K, V> newRoot = removeEntry(getRoot(this), (K) key, oldEntry);
if(newRoot != null){
setRoot(newRoot.data);
setLeftChild(newRoot.leftChild);
setRightChild(newRoot.rightChild);
} else{
this.data = null;
}
if(oldEntry.get() != null){
size--;
}
return oldEntry.get();
}
/*
* Removes the entry in a given root node of a subtree.
* rootNode is the root node of the subtree.
* Returns the root node of the revised subtree.
*
* */
private SortedTreeMap<K,V> removeFromRoot(SortedTreeMap<K, V> rootNode){
if(rootNode.hasLeftChild() && rootNode.hasRightChild()){
SortedTreeMap<K,V> leftSubtreeRoot = rootNode.getLeftChild();
SortedTreeMap<K,V> largestNode = findLargest(leftSubtreeRoot);
rootNode.setRoot(largestNode.getRoot());
rootNode.setLeftChild(removeLargest(leftSubtreeRoot));
} else if(rootNode.hasRightChild()) {
rootNode = rootNode.getRightChild();
} else{
rootNode = rootNode.getLeftChild();
}
return rootNode;
}
/*
* Finds the node containing the largest entry in a given tree.
* rootNode is the root node of the tree.
* Returns the node containing the largest entry in the tree.
*
* */
private SortedTreeMap<K,V> findLargest(SortedTreeMap<K, V> rootNode){
if(rootNode.hasRightChild()){
rootNode = findLargest(rootNode.getRightChild());
}
return rootNode;
}
/*
* Removes the node containing the largest entry in a given tree.
* rootNode is the root node of the tree.
* Returns the root node of the revised tree.
*
* */
private SortedTreeMap<K,V> removeLargest(SortedTreeMap<K, V> rootNode){
if(rootNode.hasRightChild()){
SortedTreeMap<K,V> rightEntry = rootNode.getRightChild();
rightEntry = removeLargest(rightEntry);
rootNode.setRightChild(rightEntry);
} else{
rootNode = rootNode.getLeftChild();
}
return rootNode;
}
/*
* Removes an entry from the tree rooted at a given node.
* rootNode is a reference to the root of a tree.
* entry is the object to be removed.
* oldEntry is an object whose data field is null
* Returns the root node of the resulting tree; if entry matches
* an entry in the tree, oldEntry's data field is the entry
* that was removed from the tree; otherwise it is null.
* */
private SortedTreeMap<K,V> removeEntry(SortedTreeMap<K,V> rootNode, K entry, ReturnObject oldEntry){
if(rootNode != null){
K rootData = rootNode.data.key;
int comparison = entry.compareTo(rootData);
if(comparison == 0){
oldEntry.set(rootNode.data.value);
rootNode = removeFromRoot(rootNode);
} else if(comparison < 0){
SortedTreeMap<K,V> leftEntry = rootNode.getLeftChild();
SortedTreeMap<K,V> subtreeRoot = removeEntry(leftEntry, entry, oldEntry);
rootNode.setLeftChild(subtreeRoot);
} else{
SortedTreeMap<K,V> rightEntry = rootNode.getRightChild();
rootNode.setRightChild(removeEntry(rightEntry, entry, oldEntry));
}
}
return rootNode;
}
И вот этот тест, который я пытаюсь пройти:
/**
* Check that entry is no longer in map after remove
*/
public Property remove_removes_entry() {
return property(isKVList,
kvs -> implies(kvs.length() > 0,
() -> property(choose(0, kvs.length()-1),
i -> {
P2<Integer, String> entry = kvs.index(i);
SortedTreeMap<Integer, String> tm = new SortedTreeMap<>(intOrd.toComparator());
kvs.foreachDoEffect(kv -> tm.add(kv._1(), kv._2()));
tm.remove(entry._1());
List<Integer> keys = fromIterator(tm.keys().iterator());
return prop(!keys.exists(key -> key.equals(entry._1())));
})
)
);
}
Сообщение об ошибке Iя получаю это:
java.lang.Error: Falsified after 2 passed tests with arguments: List(List((0,gzprxt),(4,lntpqj),(-5,caki),(-6,jzf)),2)
Я могу получить от 0 до 60 проходов, и я не понимаю, в каком сценарии не удается удалить метод. Я пытался сделать тест Junit, но не сделалне удастся
Вот еще немного контекста для моего класса:
public class Entry<K, V> {
public final K key;
public final V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public boolean equals(Object o) {
if (o instanceof Entry) {
Entry other = (Entry)o;
return this.key.equals(other.key) && this.value.equals(other.value);
}
return false;
}
}
public class SortedTreeMap<K extends Comparable<? super K>, V> implements ISortedTreeMap<K, V> {
private int size;
private Entry<K,V> data;
private SortedTreeMap<K,V> leftChild, rightChild, parent;
private Comparator<K> keyComparator;
private SortedTreeMap(K key, V value, Comparator<K> keyComparator, SortedTreeMap<K, V> parent){
data = new Entry<>(key, value);
this.parent = parent;
this.keyComparator = keyComparator;
}
public SortedTreeMap(Comparator<K> kComparator) {
keyComparator = kComparator;
}
private Entry<K,V> getRoot(){
return this.data;
}
private SortedTreeMap<K,V> getLeftChild(){
return this.leftChild;
}
private SortedTreeMap<K,V> getRightChild(){
return this.rightChild;
}
private void setLeftChild(SortedTreeMap<K, V> newLeftChild){
leftChild = newLeftChild;
}
private void setRightChild(SortedTreeMap<K, V> newRightChild){
rightChild = newRightChild;
}
private void setRoot(Entry<K, V> newRoot){
data = newRoot;
}
private boolean hasLeftChild(){
return leftChild != null;
}
private boolean hasRightChild(){
return rightChild != null;
}
@Override
public V add(K key, V value) {
V result = null;
if(isEmpty()) {
data = new Entry<>(key, value);
} else{
int comparison = keyComparator.compare(key, data.key);
SortedTreeMap<K,V> newChild = new SortedTreeMap<>(key, value, keyComparator, this);
if(comparison < 0){
if (hasLeftChild()) {
result = leftChild.add(key, value);
} else{
setLeftChild(newChild);
}
} else if(comparison > 0){
if (hasRightChild()) {
result = rightChild.add(key, value);
} else{
setRightChild(newChild);
}
} else{
result = data.value;
this.data = new Entry<>(key, value);
}
}
if (result == null){
size++;
}
return result;
}
@Override
public Iterable<K> keys() {
return new KeyIterator(this);
}
public class KeyIterator implements Iterable<K>, Iterator<K>{
private SortedTreeMap<K,V> next;
KeyIterator(SortedTreeMap<K, V> root){
next = root;
while(next.leftChild != null){
next = next.leftChild;
}
}
@Override
public Iterator<K> iterator() {
return this;
}
public boolean hasNext(){
return next != null && !next.isEmpty();
}
public K next(){
if(!hasNext()){
throw new NoSuchElementException();
}
SortedTreeMap<K,V> r = next;
if(next.rightChild != null){
next = next.rightChild;
while(next.leftChild != null){
next = next.leftChild;
}
return r.data.key;
}
while(true){
if(next.parent == null){
next = null;
return r.data.key;
}
if(next.parent.leftChild == next){
next = next.parent;
return r.data.key;
}
next = next.parent;
}
}
}