we have a completed binary search tree implementation. Make all necessary changes to the file so that it's Iterator is a fail-fast Iterator.

I do rate the answer so please do it seriously don't just copy and paste some code which is totally NOT RELEATED to this question.

package edu.buffalo.cse116; import java.util.AbstractSet; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException; public class BinarySearchTree> extends AbstractSet { /** * Data version count which can be used to help our fail-fast implementation of the iterator. */ protected int modCount; protected Entry root; protected int size; /** * Initializes this BinarySearchTree object to be empty, to contain only elements of type E, to be ordered by the * Comparable interface, and to contain no duplicate elements. */ public BinarySearchTree() { root = null; size = 0; modCount = 0; } @SuppressWarnings("unchecked") @Override public boolean equals(Object obj) { if (!(obj instanceof BinarySearchTree)) { return false; } return equals(root, ((BinarySearchTree) obj).root); } // method 1-parameter equals public boolean equals(Entry p, Entry q) { if ((p == null) || (q == null)) { return p == q; } if (!p.element.equals(q.element)) { return false; } if (equals(p.left, q.left) && equals(p.right, q.right)) { return true; } return false; } /** * Returns the size of this BinarySearchTree object. * * @return the size of this BinarySearchTree object. */ @Override public int size() { return size; } /** * Iterator method that has, at last, been implemented. * * @return an iterator positioned at the smallest element in this BinarySearchTree object. */ @Override public Iterator iterator() { return new TreeIterator(); } /** * Determines if there is at least one element in this BinarySearchTree object that equals a specified element. The * worstTime(n) is O(n) and averageTime(n) is O(log n). * * @param obj - the element sought in this BinarySearchTree object. * @return true - if there is an element in this BinarySearchTree object that equals obj; otherwise, return false. * @throws ClassCastException - if obj cannot be compared to the elements in this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @Override public boolean contains(Object obj) { return getEntry(obj) != null; } /** * Ensures that this BinarySearchTree object contains a specified element. The worstTime(n) is O(n) and averageTime(n) * is O(log n). * * @param element - the element whose presence is ensured in this BinarySearchTree object. * @return true - if this BinarySearchTree object changed as a result of this method call (that is, if element was * actually inserted); otherwise, return false. * @throws ClassCastException - if element cannot be compared to the elements already in this BinarySearchTree object. * @throws NullPointerException - if element is null. */ @Override public boolean add(E element) { if (root == null) { if (element == null) { throw new NullPointerException(); } root = new Entry<>(element, null); size++ ; return true; } else { Entry temp = root; int comp; while (true) { comp = element.compareTo(temp.element); if (comp == 0) { return false; } if (comp < 0) { if (temp.left != null) { temp = temp.left; } else { temp.left = new Entry<>(element, temp); size++ ; return true; } // temp.left == null } else if (temp.right != null) { temp = temp.right; } else { temp.right = new Entry<>(element, temp); size++ ; return true; } // temp.right == null } // while } // root not null } // method add /** * Ensures that this BinarySearchTree object does not contain a specified element. The worstTime(n) is O(n) and * averageTime(n) is O(log n). * * @param obj - the object whose absence is ensured in this BinarySearchTree object. * @return true - if this BinarySearchTree object changed as a result of this method call (that is, if obj was * actually removed); otherwise, return false. * @throws ClassCastException - if obj cannot be compared to the elements already in this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @Override public boolean remove(Object obj) { Entry e = getEntry(obj); if (e == null) { return false; } deleteEntry(e); return true; } /** * Finds the Entry object that houses a specified element, if there is such an Entry. The worstTime(n) is O(n), and * averageTime(n) is O(log n). * * @param obj - the element whose Entry is sought. * @return the Entry object that houses obj - if there is such an Entry; otherwise, return null. * @throws ClassCastException - if obj is not comparable to the elements already in this BinarySearchTree object. * @throws NullPointerException - if obj is null. */ @SuppressWarnings("unchecked") protected Entry getEntry(Object obj) { int comp; if (obj == null) { throw new NullPointerException(); } if (!(obj instanceof Comparable)) { return null; } Comparable compObj = (Comparable) obj; Entry e = root; while (e != null) { comp = compObj.compareTo(e.element); if (comp == 0) { return e; } else if (comp < 0) { e = e.left; } else { e = e.right; } } // while return null; } /** * Deletes the element in a specified Entry object from this BinarySearchTree. * * @param p  the Entry object whose element is to be deleted from this BinarySearchTree object. * @return the Entry object that was actually deleted from this BinarySearchTree object. */ protected Entry deleteEntry(Entry p) { size-- ; // If p has two children, replace p's element with p's successor's // element, then make p reference that successor. if ((p.left != null) && (p.right != null)) { Entry s = successor(p); p.element = s.element; p = s; } // p had two children // At this point, p has either no children or one child. Entry replacement; if (p.left != null) { replacement = p.left; } else { replacement = p.right; } // If p has at least one child, link replacement to p.parent. if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) { root = replacement; } else if (p == p.parent.left) { p.parent.left = replacement; } else { p.parent.right = replacement; } } // p has at least one child else if (p.parent == null) { root = null; } else { if (p == p.parent.left) { p.parent.left = null; } else { p.parent.right = null; } } // p has a parent but no children return p; } // method deleteEntry /** * Finds the successor of a specified Entry object in this BinarySearchTree. The worstTime(n) is O(n) and * averageTime(n) is constant. * * @param e - the Entry object whose successor is to be found. * @return the successor of e, if e has a successor; otherwise, return null. */ protected Entry successor(Entry e) { if (e == null) { return null; } else if (e.right != null) { // successor is leftmost Entry in right subtree of e Entry p = e.right; while (p.left != null) { p = p.left; } return p; } // e has a right child else { // go up the tree to the left as far as possible, then go up // to the right. Entry p = e.parent; Entry ch = e; while ((p != null) && (ch == p.right)) { ch = p; p = p.parent; } // while return p; } // e has no right child } // method successor protected class TreeIterator implements Iterator { protected int expectedModCount; protected Entry lastReturned = null, next; /** * Positions this TreeIterator to the smallest element, according to the Comparable interface, in the * BinarySearchTree object. The worstTime(n) is O(n) and averageTime(n) is O(log n). */ protected TreeIterator() { next = root; if (next != null) { while (next.left != null) { next = next.left; } } } /** * Determines if there are still some elements, in the BinarySearchTree object this TreeIterator object is iterating * over, that have not been accessed by this TreeIterator object. * * @return true - if there are still some elements that have not been accessed by this TreeIterator object; * otherwise, return false. */ @Override public boolean hasNext() { return next != null; } // method hasNext /** * Returns the element in the Entry this TreeIterator object was positioned at before this call, and advances this * TreeIterator object. The worstTime(n) is O(n) and averageTime(n) is constant. * * @return the element this TreeIterator object was positioned at before this call. * @throws NoSuchElementException - if this TreeIterator object was not positioned at an Entry before this call. */ @Override public E next() { if (!hasNext()) { throw new NoSuchElementException(); } lastReturned = next; next = successor(next); return lastReturned.element; } // method next /** * Removes the element returned by the most recent call to this TreeIterator object's next() method. The * worstTime(n) is O(n) and averageTime(n) is constant. * * @throws IllegalStateException - if this TreeIterator's next() method was not called before this call, or if * this TreeIterator's remove() method was called between the call to the next() method and this call. */ @Override public void remove() { if (lastReturned == null) { throw new IllegalStateException(); } if (expectedModCount != modCount) { throw new ConcurrentModificationException(); } if ((lastReturned.left != null) && (lastReturned.right != null)) { next = lastReturned; } deleteEntry(lastReturned); expectedModCount = modCount; lastReturned = null; } // method remove } // class TreeIterator protected static class Entry { protected E element; protected Entry left = null, right = null, parent; /** * Initializes this Entry object. This default constructor is defined for the sake of subclasses of the * BinarySearchTree class. */ public Entry() {} /** * Initializes this Entry object from element and parent. */ public Entry(E element, Entry parent) { this.element = element; this.parent = parent; } // constructor } // class Entry } // class BinarySearchTree 

And here is the test code

package edu.buffalo.cse116;

import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail;

import java.lang.reflect.Field; import java.util.Arrays; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.NoSuchElementException;

import org.junit.Before; import org.junit.Test;

import edu.buffalo.cse116.BinarySearchTree.Entry;

public class BinarySearchTreeIteratorTest { private Field rootField; private Field sizeField;

private BinarySearchTree instance;

private Entry[] nodes; private final Character[] values = new Character[] { '0', 'd', '9', 'g', 't', 'j', 'e', 'v', 'w', 'z', 'o' };

@SuppressWarnings("unchecked") @Before public void setUp() { nodes = new Entry[11]; for (int i = 0; i < nodes.length; i++ ) { nodes[i] = new Entry(values[i], null); }

// Setup the left and right children in the tree nodes[5].left = nodes[3]; nodes[5].right = nodes[4];

nodes[4].left = nodes[10];

nodes[2].left = nodes[0]; nodes[2].right = nodes[1];

nodes[6].left = nodes[2]; nodes[6].right = nodes[5];

nodes[8].right = nodes[9];

nodes[7].left = nodes[6]; nodes[7].right = nodes[8];

// Setup the parents in the tree nodes[6].parent = nodes[7]; nodes[8].parent = nodes[7]; nodes[9].parent = nodes[8]; nodes[5].parent = nodes[6]; nodes[2].parent = nodes[6]; nodes[0].parent = nodes[2]; nodes[1].parent = nodes[2]; nodes[10].parent = nodes[4]; nodes[3].parent = nodes[5]; nodes[4].parent = nodes[5];

instance = new BinarySearchTree();

Class binarySearchTreeKlass = BinarySearchTree.class;

try { rootField = binarySearchTreeKlass.getDeclaredField("root"); assertTrue("BinarySearchTree class needs to still have a field named \"root\" in which the root of the tree is stored!", rootField.getType() == Entry.class); rootField.setAccessible(true); } catch (Exception e) { fail("BinarySearchTree class needs to still have a field named \"root\" in which the root of the tree is stored!"); } try { sizeField = binarySearchTreeKlass.getDeclaredField("size"); sizeField.setAccessible(true); assertTrue("BinarySearchTree class needs to still have a field named \"size\" in which the number of elements in the binary tree are recorded!", sizeField.getType() == Integer.TYPE); } catch (Exception e) { fail("BinarySearchTree class needs to still have a field named \"size\" in which the number of elements in the binary tree are recorded!"); }

}

@Test public void testIteratorStillWorks() throws IllegalArgumentException, IllegalAccessException { Iterator it = instance.iterator(); assertFalse("Should not have changed basic working of the iterator! hasNext() returned true once past the end of the Collection!", it.hasNext()); boolean exceptionThrown = false; try { it.next(); } catch (NoSuchElementException nse) { exceptionThrown = true; } assertTrue("Should not have changed basic working of the iterator! next() did not throw a NoSuchElementException when past the end of the Collection!", exceptionThrown);

rootField.set(instance, nodes[7]); sizeField.set(instance, 11); Arrays.sort(values); it = instance.iterator(); for (int i = 0; i < values.length; i++ ) { assertTrue("Should not have changed basic working of the iterator! hasNext() returned false while the Collection had more elements!", it.hasNext()); assertEquals("Should not have changed basic working of the iterator! next() did not return the next element in the Collection!", values[i], it.next()); } }

@Test public void testIteratorWorksWithContains() throws IllegalArgumentException, IllegalAccessException { rootField.set(instance, nodes[7]); sizeField.set(instance, 11); Arrays.sort(values); Iterator it = instance.iterator(); for (int i = 0; i < values.length; i++ ) { instance.contains(values[i]); assertTrue("Calls to contains() should not affect the iterator. hasNext() returned false while the Collection had more elements!", it.hasNext()); assertEquals("Calls to contains() should not affect the iterator. next() did not return the next element in the Collection!", values[i], it.next()); instance.contains((char) (values[i] + 1)); } }

@Test public void testIteratorWorksWhenAddCalledBeforeIterating() throws IllegalArgumentException, IllegalAccessException { rootField.set(instance, nodes[7]); sizeField.set(instance, 11); instance.add('2'); Character[] newValues = Arrays.copyOf(values, values.length + 1); newValues[values.length] = '2'; Arrays.sort(newValues); Iterator it = instance.iterator(); for (int i = 0; i < newValues.length; i++ ) { assertTrue("Calls to add() before we create the iterator should not have an impact. hasNext() returned false while the Collection had more elements!", it.hasNext()); assertEquals("Calls to add() before we create the iterator should not have an impact. next() did not return the next element in the Collection!", newValues[i], it.next()); } }

@Test public void testIteratorWorksWhenElementAddedCalledDuringIteration() throws IllegalArgumentException { @SuppressWarnings("unused") Iterator unusedIterator = instance.iterator(); for (int i = 0; i < values.length; i++ ) { instance.add(values[i]); } Arrays.sort(values); Iterator it = instance.iterator(); for (int i = 0; i < 6; i++ ) { assertTrue("Calls to add() before we create the iterator should not have an impact. hasNext() returned false while the Collection had more elements!", it.hasNext()); assertEquals("Calls to add() before we create the iterator should not have an impact. next() did not return the next element in the Collection!", values[i], it.next()); } instance.add('F'); try { it.next(); fail("Calls to add() while the Iterator is active should cause it to throw a ConcurrentModificationException!"); } catch (ConcurrentModificationException cme) { // Do not do anything, this is expected but also makes certain it only occurs here. } }

@Test public void testIteratorWorksWhenAddFailsDuringIteration() throws IllegalArgumentException { @SuppressWarnings("unused") Iterator unusedIterator = instance.iterator(); for (int i = 0; i < values.length; i++ ) { instance.add(values[i]); } Arrays.sort(values); Iterator it = instance.iterator(); for (int i = 0; i < 6; i++ ) { assertTrue("Calls to add() before we create the iterator should not have an impact. hasNext() returned false while the Collection had more elements!", it.hasNext()); assertEquals("Calls to add() before we create the iterator should not have an impact. next() did not return the next element in the Collection!", values[i], it.next()); } instance.add(values[0]); try { assertEquals("Calls to add() that do not make changes should not have an impact. next() did not return the next element in the Collection!", values[6], it.next()); } catch (ConcurrentModificationException cme) { fail("Calls to add() that do no add anything (e.g., because the element was already in the tree) should NOT cause it to throw a ConcurrentModificationException!"); } }

}