import java.lang.reflect.Array; public class ArrayList extends List { private int size; private int capacity; private Object[] ls; // TODO: default: should create an arraylist that is capable of holding 10 element public ArrayList(){ } // TODO: second constructor - should create an arraylist that is capable of holding x element public ArrayList(int capacity){ } public int size(){ return this.size; } public E get(int index) throws IndexOutOfBoundsException{ if(index >= this.size){ throw new IndexOutOfBoundsException(); } return (E) this.ls[index]; } // TODO: insert --> takes some element and inserts it at the end of the arraylist, resizes to double capacity if no space public void add(E value){ } // TODO: delete - deletes an element at said index; moves elements such that there are no gaps in between them public void delete(int index) throws IndexOutOfBoundsException{ } // TODO: searches one by one to find the element, if it doesn't exist then return -1 public int search(E value){ return -1; } // TODO: given some other arraylist, compare it to see if it has the same contents public boolean equals(Object o){ return false; } // to help you public String toString(){ String ret = ""; for(int i = 0; i  
 
 
abstract class List{ abstract void add(E value); abstract void delete(int index) throws IndexOutOfBoundsException; abstract E get(int index) throws IndexOutOfBoundsException; abstract int search(E value); public abstract boolean equals(Object o); public abstract int size(); } 
  Building your own small scale Search Engine A th this assignment you will be building a small-scale search engine with different data structures to see how efficient they are. In the first phase, we will use a build a custom ArrayList and a SortedArrayList for our search engine. In phase 2, we will use our data structures to implement our search engine. Eventually, you will be using a Linked List, BST, AVL tree, and Hash Table as well to implement the search engine. Phase 1 You need to implement your own custom Array List for this assignment and You will build 2 data structures to be used in the search engine: Array List, and Sorted Array List. You cannot use the in-built ArrayList. Both of these should be able to support different data types and not limited to just Integer, or String, etc. This can be done using Generics. Here is an example of a generic class in Java: public class Box T} private T t; public void add ( T t) \{ this. t=t; \} public T get () \{ return t; \} \} This class, called "Box", can be used to hold any type of object, as specified by the type parameter "T". To use this class, you would specify the type of object that the "Box" should hold when you create an instance of it, like this: Box  Integer> integerBox = new Box BInteger> (); integerBox.add(new Integer (10)); Integer someInteger = integerBox.get(); We use generics such that we can use the same class/Object to declare instances of different types i.e ArrayList  String  \& ArrayListInteger . The details of the data structures are listed below: 1. Array List You need to implement the following: Your class should have 2 constructors: - The default constructor should initialize an array to store 10 elements (we call this capacity). What this means is that we can initially store 10 elements and that there are no elements currently in the list. - The second constructor should take in a number and initialize an array of this length. Furthermore, each constructor should also initialize the size of the list to be 0 (this is the total number of elements in the list). Add: Should take in the value to be inserted. It'll automatically add it to the end (for this assignment). You may need to resize the original array in order to complete this operation. Please double the capacity of the array if needed. For instance, lets assume that the capacity is 10 and there are already 10 elements in the list, and you are trying to insert another. The method should double the size of the array and copy all elements before inserting. Delete: Should take in an index that is to be deleted. If the index is negative, or equal or greater than the size (not the capacity), it should generate an IndexoutofBoundsException Otherwise, it should delete that item at provided index. You must ensure there are no holes in your list. Search: Should take in a value to search for and return the index of this item. If the item is not found, it should return 1. Get: Should take in an index. If the index is negative, or equal or greater than the size, it should generate an IndexoutofBoundsException Otherwise, it should return the item at the provided index. 2. Sorted Array List You need to implement the following: Your class should have 2 constructors: - The default constructor should initialize an array to store 10 elements (we call this capacity). What this means is that we can initially store 10 elements and that there are no elements currently in the list. - The second constructor should take in a number and initialize an array of this length. Furthermore, each constructor should also initialize the size of the list to be 0 (this is the total number of elements in the list). Add: Should take in the value to be inserted. It needs to insert this item, so that the list remains sorted. You may need to resize the original array in order to complete this operation. Please double the capacity of the array if needed. For instance, lets assume that the capacity is 10 and there are already 10 elements in the list, and you are trying to insert another. The method should double the size of the array and copy all elements before inserting. Delete: Should take in an index that is to be deleted. If the index is negative, or equal or greater than the size (not the capacity), it should generate an IndexOutofBoundsException Otherwise, it should delete that item at provided index. You must ensure there are no holes in your list. Search: Should take in a value to search for and return the index of this item. If the item is not found, it should return -1. Since the list is sorted, you can use binary search to do this. Get: Should take in an index. If the index is negative, or equal or greater than the size, it should generate an IndexoutofBoundsException Otherwise, it should return the item at the provided index. Test Cases Using Junit, please provide test cases that test the accuracy of your methods. You should test add, delete, get, and search. Remember, your Phase 2 You have a dataset (dataset.t  ) containing a list of URLs, You have to read the contents of each webpage, and add the keyword with the associated URL so that if someone searches for the keyword, the results include that keyword. Dataset The text file contains a list of URLs which you need to read. Your main program should look like the following: import j ava. util. Scanner; public class SearchEngine f private String directory; private int mode; public SearchEngine(String directory, int mode) \{ this. directory = directory; this.mode = mode; \} public void search (String term) \& System. out.println("Searching for " + term + " using data structure mode " + mode +""); // Search logic goes here // // Example code for displaying results System. out.println("Displaying results for " + term + ":"); System. out.println(" 1. Document 1"); System. out.println(" 2. Document 2"); System. out.println(" 3. Document 3"); \} public static void main(String [] args) \& Scanner input = new Scanner (System.in); System. out.print("Please enter the name of a directory: "); String directory = input . nextLine () ; System. out.println("Enter mode as in what data structure to use:"); System. out.println(" 1. Array List "); System. out.println(" 2. Sorted Array List"); int mode = input.nextInt 0 ; System. out.println("Building Search Engine..."); SearchEngine engine = new SearchEngine (directory, mode); String answer = " y "; while (answer. equals ("y ")) \& input.nextLine(); // constme the remaining newline character System.out.print("Search (enter a term to query): "); String term = input. nextLine (); engine.search (term); System. out.print ("Would you like to search another term (y)?"); answer = input. nextLine (); input.close (); \}o read a HTML webpage, you can uSe JSoup: Document doc = Jsoup.connect('https://en.wikipedia. org/wiki/Engineering_informatics') . get(); String text = doc.body(0.text(): System.out.println(text): The following page shows you how to add a dependency: https://www jetbrains, com/help/idea/working-with-module- dependencies,html\#add-a-new-dependency The mode tells the search engine which data structure to use detailed below. 1. Array List You decide to use an Array List so that each element/Node would store 2 things: - Keyword - List of URLs the keyword appears in (another instance of ArrayList). You need to implement the add, and search operations for the Array List. Assume that the initial capacity of the ArrayList is 10 and every time you run out of space, you double the capacity. 2. Sorted Array List Same as 1 but in addition, you want to keep the array sorted. So when you add, you want to ensure that the keywords remain sorted. Assume that the initial capacity of the ArrayList is 10 and every time you run out of space, you double the capacity. Unlike 1, you can now use binary search to find a keyword. Explanation: 1. Array List You decide to use an Array List so that each element/Node would store 2 things: - Keyword - List of URLs the keyword appears in (another instance of ArrayList). You need to implement the add, and search operations for the Array List. Assume that the initial capacity of the ArrayList is 10 and every time you run out of space, you double the capacity. 2. Sorted Array List Same as 1 but in addition, you want to keep the array sorted. So when you add, you want to ensure that the keywords remain sorted. Assume that the initial capacity of the ArrayList is 10 and every time you run out of space, you double the capacity. Unlike 1, you can now use binary search to find a keyword. Explanation: Assume you are reading https://en, wikipedia, org/wiki/Google_Drive. For each keyword, you need to store that keyword in the SearchEngine's arraylist as well as the fact that it appears in this web URL (the Node's list of references). There should be no repetitions of keywords. Lets say you read "storage" so you store it in your arraylist with the fact that it appears in httpsi//en, wikipedia,org/wiki/Google_Drive. Later, you read https://en, wikipedia,org/wiki/File_hosting_service and encounter the same word again, for instance, you encounter "storage" so you add this URL as well to the list of URLs. Ultimately, when all data is loaded, the user searches for "storage" and you find the keyword (which should have the list of URLs) and display all the URLs for this keyword, which should be: https://en, wikipedia,org/wiki/Google_Drive. https://en, wikipedia,org/wiki/File_hosting_service You need to output how long it took to load the data as how long it took to search a term. Dataset Files loaded successfully. 47 URLs loaded from the folder in 3 seconds and 548 microseconds. Please enter a word to search: storage 2 result(s) found in 1 seconds and 431 microseconds. https://en, wikipedia, org/wiki/Google_Drive. https://en, wikipedia,org/wiki/File_hosting_service *Bonus: Can you improve the search engine by looking at how many himes a keyword appears in a documentand using that information to sort the results? Submit Autograder: - ArrayList.java - SortedArrayList.java - Node.java - SearchEngine/java Canvas: - Arraylist.java - SortedArraylist.java - Node.java - SearchEngine/java - ArraylistTest.java - SortedArrayListTest.java - NodeTest.java - SearchEngineTest.java