Purpose

• To learn how to use the JCF classes (HashSet, HashMap,TreeSet, TreeMap).
  • You do not need to implement these classes.
• To practice using the StringBuilder class to reduce runtimewhen working with Strings.

Time Estimate

4-5 hours to complete.

Background

You have been given the following:

Code

• setAndMaps.java

Input files

• imdb.txt
• sight_and_sound.txt
• 3_lists.txt

Sample output

• output_intersection.txt
• output_frequent.txt
• output_groupByNumChars.txt

The sample output is produced for the provided main function;mainly, the following cases:

// intersectionSystem.out.println(setAndMaps.intersection(list1, list2));// frequentSystem.out.println(setAndMaps.frequent(list3, 3));// groupByNumCharsSystem.out.println(setAndMaps.groupByNumChars(list2));

Problem Statement

Three of the methods in setAndMaps.java are incomplete. Writethe code so it works correctly. You should only code in one file,setAndMaps.java.

Do not change the method signatures. Each method should returnthe output as a String.

Code Structure

public static List getList(String filename){};

• This method has been done for you.
  • It takes a filename as a parameter and returns a List ofmovies.
• Each file contains one movie per line.
  • 3_lists.txt has duplicates because it contains 3 lists
  • the other files do not have duplicates

public static String intersection(List list1, List list2){};

• Return all movies that occur in both lists as a String.
  • Your output MUST be ordered alphanumerically (from a-z,0-9).
• The expected runtime must be O(nlogn) where n is the totalnumber of movies in the lists.
• Use a HashSet to store one of the lists, so you can search theHashSet efficiently.
  • You may assume that the expected runtime of searching orinserting into a hash table is O(1).
• Do not call the list's contains method, because it is tooslow.
• Return all entries (do not deduplicate your result).

public static String frequent(List list, int k){};

• Return all movies in the list that occur at least ktimes as a String.
  • Your output MUST be ordered alphanumerically (from a-z,0-9).
• The output String will contain the movie followed by the numberof occurrences in parentheses, as in the sample output.
• The expected runtime must be O(nlogn) where n is the totalnumber of movies in the list.
• Use a HashMap to count occurrences
  • the key is the movie
  • the value is the number of occurrences
• For each movie, check if it's a key in the map.
  • If it is, update its value.
  • Otherwise add a new entry to the map.
• Then iterate through the map and print the frequent movies.
  • See UsingSetsMaps for an example of how use a for-each loopwith a map.

public static String groupByNumChars(List list){};

• Return all movies in the list, grouped by number of characters,as a String.
  • All movies with the same number of characters should be printedon the same line
  • Movies with fewer characters should be printed first.
  • Your output MUST be ordered alphanumerically (from a-z,0-9).

Advice

• There is more than one way to solve this problem, but one wayis to use a map.
  • The key is the number of characters, and the value is a list ofmovies with that number of characters.
  • You can declare it like this:

Map> map = new ... // Choose the appropriate map class

• For each movie, you can use the String class's length functionto get the number of characters.

  • If the map doesn't already have an entry for this length,create a new entry
    • use the map's put method
  • If the map already has an entry for this length:
    • first call the map's get method (which returns a reference to alist)
    • then add the movie to the list

• Do not use a single String to store more than one movie, becauseit will slow down the runtime

  • a StringBuilder is fine.

Requirements

• The program takes in text files that are then converted tolists. Your solutions will operate on the parameterized lists.

• The code must properly complete the setAndMaps.java class andwork with the provided Main.java class.

• All functions in the setAndMaps.java class MUSTbe implemented.

• All code you write should exist solely in the specified methodsand additional helper functions. NO CODE SHOULD BE ADDED TOTHE MAIN FUNCTION

• Base your code on the given template. Any code not adhering tothe given template may work, but may not pass all tests uponsubmission.

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main {
   // Returns a List of all movies in the specified file(assume there is one movie per line).
   public static ArrayList getList(String filename){
   ArrayList list = new ArrayList<>();
   try (Scanner in = new Scanner(newFileReader(filename))) {
   while (in.hasNextLine()) {
   String line = in.nextLine();
   list.add(line);
   }
   } catch (FileNotFoundException e) {
   e.printStackTrace();
   }
   return list;
   }
   public static void main(String[] args) {
       ArrayList list1 =getList(\"imdb.txt\");
       ArrayList list2 =getList(\"sight_and_sound.txt\");
       ArrayList list3 =getList(\"3_lists.txt\");

//Sort lists
Collections.sort(list1);
Collections.sort(list2);
Collections.sort(list3);
  
      System.out.println(\"***\nintersection\n***\");
      System.out.println(setAndMaps.intersection(list1, list2));

      System.out.println(\"***\nfrequent\n***\");
      System.out.println(setAndMaps.frequent(list3, 3));

      System.out.println(\"***\ngroupByNumChars\n***\");
      System.out.println(setAndMaps.groupByNumChars(list2));
   }
}

import java.util.*;

BELOW IS WHERE WE DO THE CODE

public class setAndMaps {

// Prints all movies that occur in both lists.
public static String intersection(List list1,List list2) {
//Add code below
return \"\";
}

// Prints all movies in the list that occur at least ktimes
// (print the movie followed by the number of occurrences inparentheses).
public static String frequent(List list, int k){
//Add code below
return \"\";
}

// Prints all movies in the list, grouped by number ofcharacters.
// All movies with the same number of characters are printed on thesame line.
// Movies with fewer characters are listed first.
public static String groupByNumChars(List list){
//Add code below
return \"\";
}
}