PA7: BSTs and Range QueriesPart I: Ordered Queries in OrderedDefaultMap Part II: A New Kind of QueryAs a Console Interface As MethodsrangeSearch topN generateDatabaseComparator for Instantiating BSTMap (and more!)Te sting Limitations READMEAsking for Help Rubric ExtensionsOther Query OutputsIn this assignment youŇll finish an implementation of a a Map interface that makes use of ordering, and use its special properties to perform new kinds of queries.This PA is closed to collaboration. You can get the starter code here:https://github.com/ucsd-cse12-w19/pa7-starterPart I: Ordered Queries inOrderedDefaultMapWeŇve provided an incomplete implementations of OrderedDefaultMap for you, implemented with a binary search tree, in BSTMap.java. It already supports several methods, which we have or will discuss in lecture. You will fill in the methods listed below.keys, entries, and values, which are specified to return elements according to the order of the keys. You must implement these in O(n) time, where n is the number of elements in the tree.floor and ceiling, which query keys based onordering. You must implement these in O(h) time, where h is the height of the tree.range, which selects a subset of the keys in the map inan ordered range. You must implement this in O(m + h) time, where h is the height of the tree, and m is the number of elements in the tree between low (inclusive) and high (exclusive). The important thing to note here is that you should not visit all the elements in the tree in order to implement this method.These are all based on methods provided by JavaŇs TreeMap class. More information and references are provided in the Javadoc for OrderedDefaultMap. You should implement and test these thoroughly.You can also refer to the slides from discussion for some examples of range queries.Part II: A New Kind of QueryIn PA6, you implemented comparison queries where you could provide two n-grams and visualize a graph comparing them. In this PA, you will build a query that takes two strings, and finds all the n-grams between the strings. This is particularly useful because it lets us query for all the n-grams that start with some string. For example, we could search for all the strings from “has a ” to “has a!” to get all the 3- grams that start with has a. This is broken out in detail below.As a Console InterfaceYou will use this method to implement a new kind of query at the console. This query, instead of producing a graph, simply prints out a list of the top 10 n-grams that are in range of the query:Enter query: is a –is a! is a good: 41is a very: 40 is a lot: 16is a prosperous: 15 is a great: 14is a big: 11is a little: 11 is a new: 10is a major: 9 is a matter: 8The — is a separator that distinguishes the low andhigh parts of the query.The space after is a is intentional and meaningful. It makes sure the string is a (with no space) is not included in the range.! is the first character after the space character in ASCII, so this range includes all strings that start with is a (with a space after the a).The console interface should print only the top 10 results, as ordered by the total sum of times the n-gram appears across all years in the dataset. This should be implemented in the main method of Loader.java.You are free to re-use code and ideas from your PA6 submission for this. ItŇs interesting (though not required) to keep the other query interface with graph drawing working at the same time as this one. For PA7 youŇre only required to make this interface work.As MethodsYou will implement several methods to help build out this interface.rangeSearchOrderedDefaultMap
rder People by name, and other times by age. We could define a Comparator for each of those cases:class AgeComparator implements Comparator
undergraduate English: 1 undergraduate English major: 1 undergraduate I: 1 undergraduate I spent: 1 undergraduate a: 1