1. Write the following custom method, getCluster, described below for the given Dictionary implementation. Assume the normal fields/methods are present for our generic KeyValuePair class (i.e. from the Dictionary programming assignment) as well as for our generic Dictionary class. [20pts] The method getCluster takes in a bucketIndex and grabs all KeyValuePair objects that are in the cluster surrounding that index (BOTH before and after the given bucketIndex). Note that for the programming assignment, techniques such as Sequential Search was forbidden. However, you might find such techniques are actually quite useful for this method. The following image showing an example should make this clearer: Given bucketindex of 4 , the cluster List object should contain: cluster={k4:v4,k1:v1,k2:v2,k6:v6}NotethatanyDELETEDbucketsarenotaddedandtheactualorderofkey:valuepairsintheclusterListobjectisirrelevant.Anequallyvalidsolutioncouldbe:cluster={k1:v1,k4:v4,k2:v2,k6:v6} The above image is just an example. The empty buckets shown indicate there is null in those buckets (i.e. they do NOT contain a KeyValuePair object). Reaching an empty bucket above and below the given bucketIndex is how you know where to stop collecting KeyValuePair objects and furthermore is how you know the boundaries of the cluster (DELETED buckets should be passed over). The getCluster function returns a List of KeyValuePair objects. Assume the List class is the same generic one from your past assignment and has an "append" method that takes in the KeyValuePair object you want to append. This append method is the only List method you will need. Simply append the contents of each bucket before and after the bucketIndex (skipping any DELETED buckets) and stop when you hit a null bucket. Make sure to append the contents of the bucketindex itself unless it is DELETED or null. About edge cases: - The table itself may be null. If it is, you should return null - The table may be empty. If it is, you should return an empty cluster - There is no assumption on the size of the table, so you will need to grab its size when needed - The given bucketindex may be invalid, that is, it may refer to a bucket that doesn't exist in the table. If it does, you should return an empty cluster - If it is valid, the bucket at bucketindex may be either: null, in which case you should return an empty cluster, DELETED, in which case you should check above and below to grab the other buckets in the cluster, or a valid KeyValuePair object, in which case the contents of the bucketindex should be appended to the cluster along with the other buckets in the cluster You must account for all 3 of these cases. - You are not to wrap around the table when searching for a null bucket i.e. you should check for array bounds in both directions and stop after examining the ends of the table if a null bucket is not found beforehand lic class Dictionary K,v> \{ rivate KeyValuePair [] table; rivate final KeyValuePair K,V> DELETED = new KeyValuePair rKK,V>( null, null); ublic Dictionary (),} public ListK,V>> getCluster(int bucketIndex) \{ // use this List object below to append all the KeyvaluePair objects in the 1/ cluster. Initially it is empty. Don't forget to return this object ListK,V>> cluster = new ListK,V>>(); I/ continue implementation below