Part 1: An Implementation of DefaultMap (18 points)

You, provide a fast implementation of an interface called DefaultMap in BST.java.

You will implement all the methods defined in the DefaultMap interface. You must ensure that each has the specified big-O bound in the worst case, and argue why based on the documentation of any libraries you use, or based on your implementation. Note that these are big-O bounds, so doing better (like O(1) where O(log(n)) is required) is acceptable. In each, n represents the number of entries in the map.

put, required O(n)

replace, required O(n)

remove, required O(n)

set, required O(n)

get, required O(n)

size, required O(1)

isEmpty, required O(1)

containsKey, required O(n)

keys, required O(n)

• In BST, you will need come up with the proper instance variables to achieve the above runtime requirements.

The specifications for the other methods are defined in header comments in the DefaultMap.java file, which you should follow.

• Important: for keys(), the returned result need to be in ascending order

Note: You are not allowed to use the java SortedMap interface or Collections.sort, or any other implementations of BSTs or sorting!!!

Your implementation of DefaultMap will be graded automatically by tests that we provide. We, provide a very minimal sanity check in the grader. DO NOT rely on it for testing!

• Part 2: File System Filtering (16 points)

FileData

In our file system, a file is represented as a FileData object which contains the information of its name, directory, and last modified date. This is the same FileData from PA6 so feel free to reuse your code!

• Instance Variables

name

The name of the given file in string format.

• dir

The directory of where the file is stored, represented in a string format.

lastModifiedDate

• The date of when the file is last modified, represented in a string format. Format: yyyy/mm/dd

Methods

In FileData.java, you will implement and thoroughly test the following methods:

• public FileData(String name, String directory, String modifiedDate)

public String toString()

public FileData(String name, String directory, String modifiedDate)

• A constructor that creates an instance of FileData object by intializing its instance variables with the given parameters. You may assume that the parameters passed in to the constructor will be non-null.

public String toString()

A method that returns the string representation of FileData by displaying the file information. It should strictly follow the format of {Name: file_name, Directory: dir_name, Modified Date: date}.

• FileSystem

The FileSystem class will be used to represent the entire structure of the file system. You should store the file information in the instance variables provided to ensure that the lookup times are as efficient as possible. You are NOT ALLOWED to add any additional instance variables or include any additional imports in FileSystem.java.

Instance Variables

nameTree

A BST that uses the file name as the key and the FileData as the value.

dateTree

A BST that uses the file date in a different format (format: yyyy/mm/dd) as the key and a list of FileData as the value. This list should keep track of the files in the order that they arrive in.

FileSystem Methods

In FileSystem.java, you will implement and thoroughly test the following methods:

public FileSystem()

public FileSystem(String inputFile)

public void add(String name, String dir, String date)

public ArrayList<String> findFileNamesByDate(String date)

public FileSystem filter(String startDate, String endDate)

public FileSystem filter(String wildCard)

public List<String> outputNameTree()

public List<String> outputDateTree()

public FileSystem()

Default constructor that creates a new FileSystem object and initializes its instance variable.

public FileSystem(String inputFile)

Constructor that creates a new FileSystem object with the given inputFile that contains the file system information. We have provided some skeleton code for reading the contents of the text file. You will need to initailizes FileSystemænbsp;instance variables and populate FileSystem with each fileænbsp;information.
Each file information is represented by a line formatted as filename, directory, date within the content of inputFile. For example, it could be mySample.txt, /home, 2021/02/01. (Note that since it is a unix type file system, forward slashes are used to represent directory hierarchy).
We have also provided a sample file, input.txt, to show how each file information is represented within the inputFile. Feel free to add more data to the file to test your FileSystem implementation thoroughly.
You may assume that inputFile parameter is properly formatted and is non-null.

public void add(String name, String dir, String date)

This method should create a FileData object with the given file information and add it to the instance variables of FileSystem. If there is a duplicate file name, then the FileData with the most recent date should be used. For example, if the first FileData stored in the trees is test.txt, /home, 2021/01/01 and the next FileData is test.txt, /home, 2021/02/01, the second FileData should replace the first FileData stored in the trees.

Here is another example: Let File1 be mySample1.txt, /root, 2021/02/01 and File2 be mySample1.txt, /root, 2023/02/01. Before we add File2, assume that we already have File1 in the FileSystem. In this situation, check which file is the most recent. If the original file was more recent, keep it and do not change the trees. If the new file is more recent, update nameTree and dateTree. Note that dateTree now has a new key and needs to be removed from the original list. In this example, before we add File2, dateTree should have °21/02/01®bsp;as the key and File1 in the value. Since File2 has the same name as File1 but a more recent date, File1 should be removed from the ArrayList associated with the date °21/02/01®bsp;and File2 should be added to the ArrayList associated with the date °23/02/01¼/p>

Note that since we are using yyyy/mm/dd as our date format now, you can use Javaænbsp;compareTo() method to compare two dates and determine which one is more recent. To read more on the usage of compareTo(), see this documentation.

If the name, dir, or date is null, then do not add anything to the FileSystem.

Follow this table for further clarification on when to add or update the trees 

public ArrayList<String> findFileNamesByDate(String date)

Given a date (format: yyyy/mm/dd), return an ArrayList of file names that correspond to this date. This list should have the file names in the order that they were added.

If the date given is null, return null.

public FileSystem filter(String startDate, String endDate)

Given a startDate and an endDate (format: yyyy/mm/dd), return a new FileSystem that contains only the files that are within the range (startDate is inclusive, endDate is exclusive). Assume the given parameters are valid and non-null.

Example: Letænbsp;call filter("2021/01/20", "2021/02/02") on a FileSystem with the following dateTree:

It should return a FileSystem with a dateTree that looks like the following (note: there should be a populated nameTree with the same entries):

public FileSystem filter(String wildCard)

Give a string wildCard, return a new FileSystem that contains only the files with names that contain the wildCard string. Note that this wildcard can be found anywhere in the file name (if the wild card is test, then test.txt, thistest.txt and thistest would all be files that should be selected in the filter)
Assume the given parameter is valid and non-null.

Example: Letænbsp;call filter("mySam") on a FileSystem with the following nameTree:

It should return a FileSystem with a nameTree that looks like the following (note: there should be a populated dateTree as well – it is not shown here):

public List<String> outputNameTree()

Return a List that contains the nameTreenameTree where each entry is formatted as: “: <FileData toString()>”

This list should be in alphabetical order. In the examples below, the quotations are there to indicate that the outputs are strings, thus ®bsp;should not show up in the actual output.

Input file:

mySample.txt, /home, 2021/02/01
mySample1.txt, /root, 2021/02/01
mySample2.txt, /user, 2021/02/06


Example Output:

["mySample.txt: {Name: mySample.txt, Directory: /home, Modified Date: 2021/02/01}", 
"mySample1.txt: {Name: mySample1.txt, Directory: /root, Modified Date: 2021/02/01}", 
"mySample2.txt: {Name: mySample2.txt, Directory: /user, Modified Date: 2021/02/06}"]

public List<String> outputDateTree()

Return a List that contains the dateTreedateTree where each entry is formatted as: “: <FileData toString()>”

The List should be in order from most recent to oldest. If there are multiple files associated with the same date, add them to the List in reverse order they were added into the ArrayList (see example below).

Input file:

mySample.txt, /home, 2021/02/01
mySample1.txt, /root, 2021/02/01
mySample2.txt, /user, 2021/02/06


Example Output:

["2021/02/06: {Name: mySample2.txt, Directory: /user, Modified Date: 2021/02/06}", 
"2021/02/01: {Name: mySample1.txt, Directory: /root, Modified Date: 2021/02/01}", 
"2021/02/01: {Name: mySample.txt, Directory: /home, Modified Date: 2021/02/01}"]


Testing

BSTTest.java and FileSystemTest.java

For this PA, your unit tests will be graded for completion only, however, we strongly encourage you to thoroughly test every public method in your class (helper methods you create should inherently be private). You are required to have at least two unique unit tests for each method written by yourself. You don need to write tests for any constructor that you choose to create in BST.java.

Part 3: Gradescope Assignment (9 points)

Respond to the following prompts in Programming Assignment 7 – questions:

What is the benefit of returning a FileSystem for the filter methods vs a List of the files that meet the filter requirements?

Describe what the best case would be for a non-empty BST, specifically, what does the tree look like? How is this the best case? What methods benefit from the best case scenario? Note that when we say ¥st case®bsp;or ïrst case we mean the best or worst case time complexity when n is very large.

Justify the runtime bounds (worst case) for the methods you wrote in BST.

Answers for FAQ

About creating your own constructors FileSystem should have constructor descriptions in the writeup and is included in the starter code. For BST, we will be using the default constructor when testing your code so account for this when creating your own instance variables. In other words, your methods should assume that only the default constructor is being used. As for Node, this is a private class only in BST so you are welcome to write whatever you see fit. We will not be testing it directly

The get() method should return null if the key is not found

If you are getting an exception on a gradescope sanity test, make sure that the structure of dateTree is correct. The key of the tree is a date in yyyy/mm/dd format

• About <? super K> The generic type K extends Comparable which is an interface. It means it can only be a type that has implemented the interface Comparable as these support comparisons. To see a list of types in Java that already do this and examples check out the table in this link: https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html. You can think of <? super K> as <K itself or one of K's superclasses>. For example, if I had <? super Integer>, this includes <Integer>, <Number>, and <Object>. I wouldn worry too much about understanding this as it is beyond the scope of the course but it is good Java knowledge.

Why is the Node class static? This is common for nested classes to make the implementation cleaner. We essentially don want Node to have access to BSTænbsp;instance variables. To learn more check out the documentation here: https://docs.oracle.com/javase/tutorial/java/javaO…

• In the output example, the  are there to emphasize that the elements in the list are Strings

You are allowed to use code provided in lecture or discussion

• About lphabetical®bsp;order It is derived from compareTo() result

Style (5 points)

• The following files will be graded on style:

BST.java

• BSTTest.java

FileData.java

• FileSystem.java

FileSystemTest.java

• To find the full style guideline, follow this link: https://docs.google.com/document/d/1XCwv_vHrp1X4vmlmNJIiXnxPuRLPZQkQEGNrJHJ0Ong/edit?usp=sharing

All guidelines that we will be following this quarter are marked in the Style Guidelines document. These are required and will be graded.

• On this PA, most guidelines must be followed, they are summarized below:

file headers

method headers (not required for test methods)

Lines cannot be longer than 100 characters

Inconsistent indentation

Lines must not be indented more than 6 times. If you have a need to indent more than 6 levels, build a helper method or otherwise reorganize your code

Test method must have meaningful names

Helper method must have meaningful names

magic numbers

Submitting

Part 1 & 2

On the Gradescope assignment Programming Assignment 7 – code please submit the following file structure:

BST.java

BSTTest.java

FileData.java

FileSystem.java

FileSystemTest.java

The easiest way to submit your files is to drag them individually into the submit box and upload that to Gradescope. You may submit as many times as you like till the deadline.

Part 3

Please submit your answers to the questions from part 3 on the Gradescope assignment Programming Assignment 7 – questions. You may submit as many times as you like till the deadline.