Question

1/3

This programming assignment involves adding functionality to the SearchTreeset implementation found in the SetMap project. Specifically you will edit the file util.SearchTreeSet and write Java-correct implementations of these methods * first pollFirst headset e lower The goal is to make these methods behave exactly like they would for a Java Treeset. Additional programming requirements the first, pollFirst, and lower methods should just take one or two passes down the tree. For a "well-balanced" tree, the time should be O(log(n)) the headset method, although O(n), should be done as efficiently as possible One thing to ignore in the description of the headSet method is that it returns a view of the portion of this set. Look at JavaDoc Documentation For the Java operations, select its usage, right-click and run Show JavaDoc to see what Java says about the behavior. For example, to see the JavaDoc of pollFirst, work with the selection java tree.pollFirst)i Skeleton Program Add the following starter code at the end of the class, fix the imports (for SortedSet), and set YOUR NAME util.Search TreeSet public class SearchTreeset<E> extends NavsetAdapter<E /Please add the following starter code AT THE END of this class // and fix imports 1 of 3 added by YOUR NAME (please set this) @Override public E first)t return null; @Override public E pollFirst) roturn null;

2/3

3/3

Answer 1

Please let me know if you have any doubts or you want me to modify the code. And if you find this code useful then don't forget to rate my answer as thumps up. Thank you! :)

import java.util.*;

public class Driver {
    @SuppressWarnings("rawtypes")
    public static void main(String[] args) {
//       NavigableSet<Integer> set = new TreeSet<Integer>();
        NavigableSet<Integer> set = (NavigableSet<Integer>) new SearchTreeSet<Integer>();

        final int RANGE = 20; // random number range
        final int NUM = 12; // make this 0 to create an empty set

        Set<String> todo = new HashSet<String>();
        todo.add("first-last");
        todo.add("pollFirst");
        todo.add("headSet");
        todo.add("floor");

        Random rand = new Random();
        for (int i = 0; i < NUM; ++i) {
            int n = rand.nextInt(RANGE);
            set.add(n);
        }

        System.out.println("\n");
        System.out.println("set = " + set);
        System.out.println("set.size() = " + set.size());

        if (set instanceof SearchTreeSet) {
            System.out.println("\n");
            ((SearchTreeSet) set).reverseInorderOutput();
        }

        if (todo.contains("first-last")) {
            System.out.println("\n");
            System.out.println("set.first() = " + set.first());
            System.out.println("set.last() = " + set.last());
        }

        if (todo.contains("pollFirst")) {
            System.out.println("\n");
            System.out.println("set.pollFirst() = " + set.pollFirst());
            System.out.println("set = " + set);
            System.out.println("set.size() = " + set.size());
        }

        int elt = rand.nextInt(RANGE); // try specific values of this as well

        if (todo.contains("headSet")) {
            System.out.println("\n");
            System.out
                    .println("set.headSet(" + elt + ") = " + set.headSet(elt));
        }

        if (todo.contains("floor")) {
            System.out.println("\n");
            System.out.println("set.floor(" + elt + ") = " + set.floor(elt));
        }
    }
}
-------------------------------------------------------------------------------------------
import java.util.*;

@SuppressWarnings("serial")
public class NavSetAdapter<E> extends SetAdapter<E> implements NavigableSet<E> {
    // SortedSet interface

    @Override
    public Comparator<? super E> comparator() {
        throw new UnsupportedOperationException("comparator");
    }

    @Override
    public E first() {
        throw new UnsupportedOperationException("first");
    }

    @Override
    public E last() {
        throw new UnsupportedOperationException("last");
    }

    @Override
    public SortedSet<E> headSet(E toElement) {
        throw new UnsupportedOperationException("headSet(E)");
    }

    @Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
        throw new UnsupportedOperationException("subSet(E,E)");
    }

    @Override
    public SortedSet<E> tailSet(E fromElement) {
        throw new UnsupportedOperationException("tailSet(E)");
    }

    // NavigableSet interface

    @Override
    public E higher(E e) {
        throw new UnsupportedOperationException("higher");
    }

    @Override
    public E lower(E e) {
        throw new UnsupportedOperationException("lower");
    }

    @Override
    public E pollFirst() {
        throw new UnsupportedOperationException("pollFirst");
    }

    @Override
    public E pollLast() {
        throw new UnsupportedOperationException("pollLast");
    }

    @Override
    public E ceiling(E e) {
        throw new UnsupportedOperationException("ceiling");
    }

    @Override
    public E floor(E e) {
        throw new UnsupportedOperationException("floor");
    }

    @Override
    public Iterator<E> descendingIterator() {
        throw new UnsupportedOperationException("descendingIterator");
    }

    @Override
    public NavigableSet<E> descendingSet() {
        throw new UnsupportedOperationException("descendingSet");
    }

    @Override
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        throw new UnsupportedOperationException("headSet(E,boolean)");
    }

    @Override
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement, boolean toInclusive) {
        throw new UnsupportedOperationException("subSet(E,boolean,E,boolean)");
    }

    @Override
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        throw new UnsupportedOperationException("tailSet");
    }
}
---------------------------------------------------------------------------------------------------
import java.util.*;

public class SearchTreeSet<E> extends NavSetAdapter<E> {
    private class Node {
        E data;
        Node left, right;

        Node(E data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    private Node root = null;
    private int size = 0;
    private Comparator<? super E> cmp = null;

    public SearchTreeSet(Comparator<? super E> cmp) {
        this.cmp = cmp;
    }

    public SearchTreeSet() {
    }

    private int myCompare(E lhs, E rhs) {
        if (cmp == null) {
            return ((Comparable) lhs).compareTo(rhs);
        } else {
            return cmp.compare(lhs, rhs);
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
        root = null;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public java.util.Comparator<? super E> comparator() {
        return cmp;
    }

    private boolean contains(Node n, E elt) {
        if (n == null) {
            return false;
        }
        int comp = myCompare(elt, n.data);
        if (comp < 0) {
            return contains(n.left, elt);
        } else if (comp > 0) {
            return contains(n.right, elt);
        } else {
            return true;
        }
    }

    @Override
    public boolean contains(Object obj) {
        E elt = (E) obj;
        return contains(root, elt);
    }

    private Node add(Node n, E elt, Mutable<Boolean> found) {
        if (n == null) {
            found.set(false);
            return new Node(elt, null, null);
        }
        int comp = myCompare(elt, n.data);
        if (comp < 0) {
            n.left = add(n.left, elt, found);
            return n;
        } else if (comp > 0) {
            n.right = add(n.right, elt, found);
            return n;
        } else {
            found.set(true);
            return n;
        }
    }

    @Override
    public boolean add(E elt) {
        Mutable<Boolean> found = new Mutable<Boolean>();
        root = add(root, elt, found);
        if (!found.get()) {
            ++size;
        }
        return !found.get();
    }

    private Node removeMin(Node n, Mutable<E> save) {
        if (n.left == null) {
            save.set(n.data);
            return n.right;
        } else {
            n.left = removeMin(n.left, save);
            return n;
        }
    }

    private Node removeMax(Node n, Mutable<E> save) {
        if (n.right == null) {
            save.set(n.data);
            return n.left;
        } else {
            n.right = removeMax(n.right, save);
            return n;
        }
    }

    // used to randomly choose findMin/findMax in remove operations
    private Random flipACoin = new Random();

    private Node remove(Node n, E elt, Mutable<Boolean> found) {
        if (n == null) {
            found.set(false);
            return null;
        }
        int comp = myCompare(elt, n.data);
        if (comp < 0) {
            n.left = remove(n.left, elt, found);
            return n;
        }
        if (comp > 0) {
            n.right = remove(n.right, elt, found);
            return n;
        }
        found.set(true);
        if (n.left == null) {
            return n.right;
        }
        if (n.right == null) {
            return n.left;
        }
        Mutable<E> save = new Mutable<E>();
        boolean choose_min = (flipACoin.nextInt(2) == 1);
        if (choose_min) {
            n.right = removeMin(n.right, save);
        } else {
            n.left = removeMax(n.left, save);
        }
        n.data = save.get();
        return n;
    }

    @Override
    public boolean remove(Object obj) {
        if (isEmpty()) {
            return false;
        }
        E elt = (E) obj;
        Mutable<Boolean> found = new Mutable<Boolean>();
        root = remove(root, elt, found);
        if (found.get()) {
            --size;
        }
        return found.get();
    }

    // structure-revealing operations
    private String indentString = "   ";

    public void setIndentString(String indentString) {
        this.indentString = indentString;
    }

    public void inorderOutput() {
        inorderOutput(root, 0);
    }

    public void reverseInorderOutput() {
        reverseInorderOutput(root, 0);
    }

    public void preorderOutput() {
        preorderOutput(root, 0);
    }

    public void postorderOutput() {
        postorderOutput(root, 0);
    }

    private String repeat(String s, int times) {
        String output = "";
        for (int i = 0; i < times; ++i) {
            output += s;
        }
        return output;
    }

    private void inorderOutput(Node n, int level) {
        if (n != null) {
            inorderOutput(n.left, level + 1);
            System.out.println(repeat(indentString, level) + n.data);
            inorderOutput(n.right, level + 1);
        }
    }

    private void reverseInorderOutput(Node n, int level) {
        if (n != null) {
            reverseInorderOutput(n.right, level + 1);
            System.out.println(repeat(indentString, level) + n.data);
            reverseInorderOutput(n.left, level + 1);
        }
    }

    private void preorderOutput(Node n, int level) {
        if (n != null) {
            System.out.println(repeat(indentString, level) + n.data);
            preorderOutput(n.left, level + 1);
            preorderOutput(n.right, level + 1);
        }
    }

    private void postorderOutput(Node n, int level) {
        if (n != null) {
            postorderOutput(n.left, level + 1);
            postorderOutput(n.right, level + 1);
            System.out.println(repeat(indentString, level) + n.data);
        }
    }

    // toArray is basically an inorder traversal.
    private int toArray(Object[] arr, int index, Node n) {
        if (n == null) {
            return index;
        } else {
            index = toArray(arr, index, n.left);
            arr[index++] = n.data;
            return toArray(arr, index, n.right);
        }
    }

    @Override
    public Object[] toArray() {
        Object[] arr = new Comparable[size]; // new Object[size] causes problems!
        toArray(arr, 0, root);
        return arr;
    }

    @Override
    public String toString() {
        return java.util.Arrays.toString(toArray());
    }

    @Override
    public Iterator<E> iterator() {
        return Arrays.asList((E[]) toArray()).listIterator();
    }

    // added by Marshall Bowers

    @Override
    public E first() {
        // Return null if the set is empty
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        // Set the current node to root
        Node currNode = root;

        // While the left hand side of the current node is not null
        while (currNode.left != null) {
            // Set the current node equal to the left node
            currNode = currNode.left;
        }

        // Return the value of the current node
        return currNode.data;
    }

    @Override
    public E last() {
        // Return null if the set is empty
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        // Set the current node to root
        Node currNode = root;

        // While the right hand side of the current node is not null
        while (currNode.right != null) {
            // Set the current node equal to the right node
            currNode = currNode.right;
        }

        // Return the value of the current node
        return currNode.data;
    }

    @Override
    public E pollFirst() {
        // Return null if the set is empty
        if (isEmpty()) {
            throw new NoSuchElementException();
        }

        // Set the current node to root
        Node currNode = root;

        // While the left hand side of the current node is not null
        while (currNode.left != null) {
            // Set the current node equal to the left node
            currNode = currNode.left;
        }

        // Remove the current node from the set
        remove(currNode.data);

        // Return the value of the current node
        return currNode.data;
    }

    @Override
    public SortedSet<E> headSet(E before) {
        // Create a new SortedSet
        SortedSet<E> set = new SearchTreeSet<E>();

        // Return the empty set if the tree is empty
        if (isEmpty()) {
            return set;
        }

        // Compare the argument with the first node in the tree
        int cmp = myCompare(before, first());

        // If the first node is smaller than the argument
        if (cmp > 0) {
            // Call the helper function
            headSet(root, before, set);
        }

        // Else: no nodes smaller than the argument
        return set;
    }

    // headSet helper function
    private void headSet(Node n, E before, SortedSet<E> set) {
        // Compare the argument with the current node
        int cmp = myCompare(before, n.data);

        // If the current node is smaller than the argument
        if (cmp > 0) {
            // Add the current node to the set
            set.add(n.data);

            // Check if the right hand side exists
            if (n.right != null) {
                // Recall the helper function on the right node
                headSet(n.right, before, set);
            }
        }

        // Check if the left hand side exists
        if (n.left != null) {
            // Recall the helper function on the left node
            headSet(n.left, before, set);
        }
    }

    @Override
    public E floor(E elt) {
        // Create a new node equal to the result of floor
        Node n = floor(root, elt);

        // If the result was null, return null
        if (n == null) {
            return null;
        } else {
            // Otherwise, return the data value of the current node
            return n.data;
        }
    }

    // floor helper function
    private Node floor(Node n, E elt) {
        // Return null if the current node is null
        if (n == null) {
            return null;
        }

        // Compare argument and the value of the node
        int cmp = myCompare(elt, n.data);

        // If the current node is less than the argument
        if (cmp < 0) {
            // Recall floor on the left hand side
            return floor(n.left, elt);
        } else if (cmp == 0) {
            return n;
        }

        // Create a new node equal to the largest element on the right
        Node r = floor(n.right, elt);

        // Return this node if it is not null
        if (r != null) {
            return r;
        } else {
            // Return the current node
            return n;
        }
    }
}
----------------------------------------------------------------------------------------
import java.util.*;
import java.io.Serializable;

@SuppressWarnings("serial")
public class SetAdapter<E> implements Cloneable, Set<E>, Serializable {

    // Iterable
    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException("iterator");
    }

    // Collection
    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException("remove");
    }

    @Override
    public boolean add(E e) {
        throw new UnsupportedOperationException("add");
    }

    @Override
    public int size() {
        throw new UnsupportedOperationException("size");
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException("addAll");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException("removeAll");
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("retainAll");
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException("containsAll");
    }

    @Override
    public boolean contains(Object o) {
        throw new UnsupportedOperationException("contains");
    }

    @Override
    public boolean isEmpty() {
        throw new UnsupportedOperationException("isEmpty");
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException("clear");
    }

    @Override
    public <E> E[] toArray(E[] a) {
        throw new UnsupportedOperationException("toArray(E[])");
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException("toArray()");
    }
}
---------------------------------------------------------------------------------------
public final class Mutable<E> {
    private E value = null;

    public E get() {
        return value;
    }

    public void set(E value) {
        this.value = value;
    }

    public Mutable() {
    }

    public Mutable(E value) {
        set(value);
    }
}

SearchTreeSet [fldeaProjects/SearchTreeSet - .src/SearchTreeSet.java [SearchTreeSet] IsearchTreeSet-src Θ searchTreeSet *-G Driver.java " 勺Mutablejava TreeSet Project ▼ e NavSetAdapterjava K e SetAdapterjava Θ SearchTreeSet.java import java.util.* ▼『SearchTreeSet idea out public class SearchTreeSetcE> extends NavSetAdapter<E>f private class Node f E data; Node left, right; Driver Mutable Node(E data, Node left, Node right) this.data data; this.left-left this.right right SearchTreeSet . SearchTreeSet.iml ot 1DEA 2918 Run:Main x /Library/Java/JavavirtualMachines/jdk-9.9 4 dk/Contents/Home/bin/java javaagent /Applications/IntelliJ IDEA 2018.3 EAP app/contents/lib/ideart ar 52395: /Applications/Intell幻 set = [0, 1, 3, 4, 9, 12, 13, 18] pset.size)8 18 13 12 set.first) set. last)18 set.pollFirst) set [1, 3, 4, 9, 12, 13, 181 set.size)7 set.headSet (19) (1, 3, 4, 9, 12, 13, 181 set.floor(19) 18 Process finished with exit code 0 Event Log TerminaO: Messages 4 Run 6: TODO Compilation completed successfully in 2 s 513 ms (moments ago)