1. A generic binary tree interface

The first step is to design a very simple interface called BinaryTree. This must be a generic interface declaring the following methods:

(a) add, which takes a generic element as its only argument, and has the return type void.

(b) remove, which takes a generic element as its only argument, and has the return type void.

(c) find, which takes a single generic element as its argument and returns a generic BinaryTreeNode instance.

(d) A print() method that takes no argument, and has return type void.

2. A generic class for ordered pairs

Next, write a generic class called OrderedPair which should have two final instance fields of the generic type. In addition to the corresponding getter methods, override Javas default equality checking with your own method. Your equality checking method should return true if and only if both fields of one object are identical to the corresponding fields of the other object.

3. A class for time intervals

Next, write a class called TimeInterval which should be a subclass of the ordered pair of doubles. For this, use the class you wrote in step 2. This class is meant to contains pairs of numbers that denote the start time and end time of some event, measured in seconds. Plus, this class should implement the Comparable interface for time intervals. This class should have the following additional methods:

(a) A method called interval(), which returns the interval between the start and end time as a double.

(b) A static method called fromString(String s) which takes a string representing two numbers separated by a comma, and returns a TimeInterval object.

(c) Override the equality check for this class with your own method. Think of when two time intervals should be considered the same when you implement this. Keep in mind that if two objects are considered equal, then your implementation of the comparable interface should consider these two objects as equal.

(d) Override the toString() method to pretty-print a time interval as a human-readable pair of numbers in the format (t_start, t_end).

(e) The constructor for this class should throw an IllegalArgumentException if the arguments cannot form a valid time interval.

4. A class for binary search trees

Write a binary search tree class with the following class declaration: public class BinarySearchTree> implements BinaryTree

(a) The add, find and remove methods should implement the insert, search and delete algorithms we have studied in class.

(b) The print method should use the print method in BinaryTreeNode class.

5. The tree builder

The last step of this assignment is the class that actually builds a tree from user input. This class contains the main method. A partial implementation of this class is already given to you as below:

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class BinarySearchTreeBuilder { public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

Set timeIntervals = new HashSet<>();

for (String line = ""; !line.equals("done");

line = scanner.nextLine()) {

if (line.startsWith("Tree: ")) {

Matcher matcher = Pattern.compile("([0-9.]+,[0-9.]+)").matcher(line);

while (matcher.find()) timeIntervals.add(TimeInterval.fromString(matcher.group()));

}

}

BinarySearchTree intervalTree = new BinarySearchTree<>();

timeIntervals.forEach(intervalTree::add);

intervalTree.print();

}

}

Currently, it allows the user to provide intervals to create a tree. The user then types done, and the program prints the tree and quits. Your task is to modify this method so that

(a) After getting the initial input to form the tree, it asks the user what to do. The valid options are (i) add, (ii) remove, (iii) search, and (iv) print.

(b) For add, remove and search, the accepted user input should be in a single line, for example, add 3.2,4.9. This should add the interval (3.2, 4.9) to the binary search tree intervalTree.

(c) After each step, the program should again ask the user what to do. If the user types done, then the program should print the whole tree and exit.