Hello, I need assistance with checking the invariant in the wellFormed method. T
ID: 3776513 • Letter: H
Question
Hello, I need assistance with checking the invariant in the wellFormed method. The cases are in the comments within the code.
public class TreeMap<K,V> extends AbstractMap<K,V> {
// Here is the data structure to use.
private static class Node<K,V> extends AbstractEntry<K,V> {
Node<K,V> left, right;
Node<K,V> parent;
Node(K k, V v) {
super(k,v);
parent = left = right = null;
}
}
private Comparator<K> comparator;
private Node<K,V> dummy;
private int numItems = 0;
private int version = 0;
private boolean wellFormed() {
// 1. check that comparator is not null
// 2. check that dummy is not null
// 3. check that dummy's right subtree and parent are null
// 4. check that all (non-dummy) nodes are in range
// 5. check that each (non-dummy) node's parent reference is correct
// 6. check that number of items matches number of (non-dummy) nodes
return true;
}
Explanation / Answer
package com.tree;
import java.util.Comparator;
import java.util.TreeMap;
public class MyTreeMapComparator {
private static class Node<K,V> extends AbstractEntry<K,V> implements Comparator<String>{
Node<K,V> left, right;
Node<K,V> parent;
Node(K k, V v) {
super(k,v);
parent = left = right = null;
}
@Override
public int compare(String str1, String str2) {
return str1.compareTo(str2);
}
}
public static void main(String a[]){
//the treemap sorts by key
Node <String, String> node0= new Node<String, String>("java","language");
Node <String, String> node1= new Node<String, String>("computer","machine");
Node <String, String> node2= new Node<String, String>("india","country");
Node <String, String> node22= new Node<String, String>("USA","country");
node2.left=node22;
node0.left=node1;
node0.right=node2;
if(node0!=null)
System.out.println(node0);
}
}
class MyComp implements Comparator<String>{
@Override
public int compare(String str1, String str2) {
return str1.compareTo(str2);
}
}
Program2:
package com.tree;
public class AbstractEntry<T1, T2> {
public AbstractEntry() {
}
public AbstractEntry(T1 k, T2 v) {
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.