Only need to write the iterator functions. WIll only give points to person who w
ID: 3547728 • Letter: O
Question
Only need to write the iterator functions. WIll only give points to person who write the function relating to the function I have written below not some generic copy and paste stuff. The Key Iterator should return an Iterator of the keys in the dictionary, in ascending
sorted order. The iterator must be fail-fast. The Value Iterator should return return an Iterator of the values in the dictionary. The order of the values must match the order of the keys. The iterator must be fail-fast. The functions are highlighted in the code.
package data_structures;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import data_structures.Hashtable.IteratorHelper;
public class BinarySearchTree<K,V> implements DictionaryADT<K,V> {
private Node<K,V> root;
private int currentSize, mod;
class Node<K,V> { //creates Node and has nested constructor
private K key;
private V value;
private Node left, right;
public Node (K k, V v) {
key = k;
value = v;
left = right = null;
}
}
public BinarySearchTree() {
root = null;
currentSize = 0;
mod = 0;
}
public boolean contains(K key) {
return getValue(key) != null;
}
public boolean insert(K key, V value) {
if (contains(key))
return false;
if (root == null)
root = new Node<K,V>(key,value);
else
add(key,value,root,null,false);
currentSize++;
mod++;
return true;
}
private void add(K key,V value,Node<K,V> n,Node<K,V> parent, boolean wasLeft) {
if (n == null) {
if (wasLeft)
parent.left = new Node<K,V>(key,value);
else
parent.right = new Node<K,V>(key,value);
}
else if (((Comparable<K>)key).compareTo((K)n.key) < 0 )
add(key,value,n.left,n,true);
else
add(key,value,n.right,n,false);
}
public boolean remove(K key) {
if (key == null)
return false;
if (((Comparable<K>)key).compareTo((K)root.key) == 0 ) {
clear();
return true;
}
root = delete(root, key);
currentSize--;
mod++;
return true;
}
private Node delete(Node x, K key) {
if (x == null) return null;
if (((Comparable<K>)key).compareTo((K)x.key) < 0)
x.left = delete(x.left, key);
else if (((Comparable<K>)key).compareTo((K)x.key) > 0)
x.right = delete(x.right, key);
else {
if (x.right == null)
return x.left;
if (x.left == null)
return x.right;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
return x;
}
private Node deleteMin(Node x) {
if (x.left == null)
return x.right;
x.left = deleteMin(x.left);
return x;
}
protected K min() {
if (isEmpty())
return null;
return (K) min(root).key;
}
private Node min(Node x) {
if (x.left == null)
return x;
else
return min(x.left);
}
public V getValue(K key) {
if (root == null)
return null;
Node<K,V> current = root;
while (((Comparable<K>)current.key).compareTo((K)key) != 0) {
if (((Comparable<K>)key).compareTo((K)current.key) < 0)
current = current.left;
else
current = current.right;
if (current == null)
return null;
}
return current.value;
}
public K getKey(V value) {
if (root == null)
return null;
Node<K,V> current = root;
while (((Comparable<V>)current.value).compareTo((V)value) != 0) {
if (((Comparable<V>)value).compareTo((V)current.value) < 0)
current = current.left;
else
current = current.right;
if (current == null)
return null;
}
return current.key;
}
public int size() {
return currentSize;
}
private int size(Node x) {
if (x == null)
return 0;
else
return currentSize;
}
public boolean isFull() {
return false;
}
public boolean isEmpty() {
return size() == 0;
}
public void clear() {
root = null;
}
public Iterator<K> keys() {
}
public Iterator<V> values() {
}
}
Explanation / Answer
http://stackoverflow.com/questions/5849154/can-we-write-our-own-iterator-in-java can you please go through this link and get a good idea about what you require thanks :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.