2023年11月25日

数据库代写 | COMP3760/6760: Enterprise Systems Integration

本次Java代写是实现一个混合数据结构
DSC 30 Final Project  
General Requirements  
1
. Office hours through Autograder and Zoom: You are only allowed to submit at most 2  
tickets for debugging questions on the final project (autograder errors will not count).  
We will count your opportunity as used if you asked any questions about the final  
project in a session.  
2
. Piazza: You can submit unlimited amounts of clarification questions in public posts  
only. Private posts about the final project will not be answered. You are not allowed to  
post your final project code in a piazza post unless being told to do so by an instructor.  
Since all clarification questions are public posts, you are encouraged to search your  
potential questions first before you make a new post.  
3
. Others: You are not allowed to request help on the final project through other  
approaches, including sending email to the instructors, or reaching the instructors  
through social networks.  
Note that these policies will only apply to the final project related questions. If you need help  
from us for other reasons, feel free to contact us in the usual approach you prefer.  
START EARLY!  
Style Requirements  
You will be graded on your code’s style according to the Style Guide.  
IntelliJ has a great plugin to check your style automatically. Use it!  
There are style considerations beyond indentation and such.

●
Choose names for test methods and for variables that are descriptive and useful when  
you see them in the test output.  
●
●
Consider writing helper methods if you repeatedly use the same set of statements.  
Use Javadoc comments for descriptions of your methods and classes and inline  
comments if the logic of your program is not captured by your variable names and the  
natural flow of code.  
Testing Requirements  
For the final project, you are not required to submit any test cases, including JUnit test files  
and main methods. However, we strongly recommend you to test your code thoroughly.  
Think about the butterfly effect: a small mistake in one method will lead to a major failure of  
the project.  
Part 0: Setup  
Starter Code  
Our starter code will be distributed from the course GitHub repository.  
Please follow the same procedures as before to get your starter code and set up IntelliJ.  
Project Quiz  
The final project quiz is a part of PA 10, thus its grade will be a part of PA 10 grade. Please  
read the write-up of PA 10 for more details.

Part 1: Project Overview  
In this project, you will implement a hybrid data structure (called FADAF, Part 4) that stores  
key-data pairs with support of duplicate keys.  
The goal of creating this new data structure is to achieve optimal time complexity for every  
operation it supports by sacrificing space complexity. To achieve this goal, we will use a  
combination of data structures we learned from this class as the backed structures. This new  
data structure will be primarily backed by (thus you must use) a hash table (Chaining, Part 2),  
and a binary search tree that supports duplicates (DAFTree, Part 3). If you want to use other  
data structures for optimization, feel free to use the built-in ones (import from java.util.*  
package), but you must implement Part 2 and 3, and use these two structures to implement  
Part 4. This is an open-ended project, meaning that there are multiple valid implementations  
for many methods. You should enhance the time complexity of all methods as best as you  
can.  
Note that the backed data structures in Part 2 and Part 3 are considered as helper classes.  
Therefore, you will find that many methods will give access to the raw implementation details  
(
such as tree nodes) publicly. With the same reasoning, you are allowed to add helper  
methods with ANY access modifier (not confined to private anymore) in these two data  
structures. However, the hybrid data structure in Part 4 will still NOT allow any public  
exposure of implementation details, just like the usual data structures you have implemented  
before.  
You may reuse the codes from your previous PAs, readings, lectures, and exams to  
save you some time. Make sure you have done the necessary modifications to fit  
these codes in this assignment.

Part 2: Hash Table (Chaining)  
Introduction  
In PA 8, you have implemented a hash table that applies cuckoo hashing as the strategy to  
address collisions. In this section, you will implement a hash table that applies the chaining  
to resolve collisions. You may refer to the course materials for the specific algorithms of  
chaining. For this implementation, we will use the LinkedList API from Java.util to express the  
chain, and an array of LinkedList to express the table.  
Another key difference between this hash table and the hash table in PA 8 is that our hash  
table now supports Generics (<T>). In order to calculate the hash value for an unknown  
generic type, we will use the hashCode() method in our hash function. The hashCode()  
method is declared in the Java.lang.Object (parent class of ALL class by default), and  
implemented in all common concrete classes (such as Integer, String, etc.). This method  
returns the hash value of the given object that Java’s built-in hash tables can use. If you want  
to use Java’s built-in hash tables for your self-defined classes or the instructed hash table  
described below, these classes must overwrite the hashCode() method. You may read the  
method descriptions below for how you should apply this method to this implementation.  
Debugging Tip: Create a HashTable that stores Integer to test, since the hashCode of an  
integer is just the integer itself which is easy to keep track of.  
Implementation  
All implementations of this part should be done in HashTable.java, and you must  
complete all the following constructor and methods.  
public HashTable(int capacity)  
A constructor that initializes a hash table with specified capacity.  
@
throws IllegalArgumentException if capacityis less than the minimum threshold (10)  
public boolean insert(T value)  
A method that inserts the value in the hash table. This method returns true if the value  
is inserted, and false if the value is already present in the hash table. Before insertion,  
this method checks if the load factor is greater than ⅔, and invokes rehash() if the  
condition satisfies.

@
throws NullPointerException if the value is null  
public boolean delete(T value)  
A method that deletes the value from the hash table. This method returns true if the  
value was in the hash table before deletion, and false if the value was not found.  
@
throws NullPointerException if the value is null  
public boolean lookup(T value)  
A method that checks if the value is stored in the hash table. This method returns true  
if the value is in the hash table, and false otherwise.  
@
throws NullPointerException if the value is null  
public int size()  
A method that returns the total number of elements stored in the hash table.  
public int capacity()  
A method that returns the total capacity of the hash table.  
private int hashValue(T value)  
A method that calculates the hash value (expected index) of the value in the hash  
table. This method calls the hashCode() of the value and mod by the capacity of the  
hash table.  
private void rehash()  
A method that performs rehash when the condition is met. This method doubles the  
capacity of the original table, and re-insert all values (not the chained list) present in  
the old table by iterating through the old table.  
You can add more helper methods with ANY access modifiers if you think they are  
necessary for your implementation.

Part 3: DAF Tree  
Introduction  
In PA 6, you have implemented a traditional binary search tree. In this section, you will  
implement a modified version of the Binary Search Tree that supports storing duplicates. This  
tree is called Duplicates-Are-Fine tree, and you should have already seen it in the second  
midterm. You may refer to the second midterm and other course materials for specific  
definitions and examples of DAF trees.  
Note that compared with the declarations in the midterm 2, we have added a par reference in  
DAFNode that points to the parent node. This reference might be helpful to optimize certain  
operations. In addition, since we consider this tree as a helper class for our hybrid structure,  
you will find many methods are returning the node directly. This is intended and might be  
useful for your Part 4 implementation.  
A key feature of this tree is that it supports two generic parameters (<K extends  
Comparable<? super K>, D>). Parameter K is used to denote the type of key, and the type K  
must be Comparable so that you can use compareTo() for comparison. Parameter D is used  
to denote the type of data, and you can use any concrete class to fit in this type. The  
declaration of DAFTree with concrete classes will look like DAFTree<String, Integer>.  
Since the DAF tree is a normal BST with dup sequences, you should be able to finish the  
majority of implementations by modifying your BST implementation. However, you should  
always keep the dup sequences in mind when modifying your old code, and sometimes  
accommodating the dup sequences will be trickier than you would expect. We will have more  
explanations of methods in the implementation section.  
Debugging Tip: Make use of the debugger to keep  
track of the state of the tree, especially the fields of  
each DAFNode. You may also find the object ID  
field (which is unique to each object) helpful to keep  
track of the node objects. This image shows how  
the Variables window in the debugger displays the  
object ID (the numbers following @).

Implementation  
All implementations of this part should be done in DAFTree.java, and you must complete  
all the following constructors and methods (unless specified optional).  
Complete this constructor in the DAFNode class.  
public DAFNode(K key, D data)  
A constructor that initializes a DAFNode with specified keyand data.  
@
throws NullPointerException if keyor data is null  
(
Optional) If you plan to directly use DAFNode to populate your hash table in your  
implementation of Part 4, you should implement the following methods in the DAFNode  
class. If this is not your plan, you may ignore these methods.  
@
Override  
public boolean equals(Object obj)  
A method that checks if obj is equal to this DAFNode object. This method returns true  
if two objects are equal, and false otherwise. The implementation here overrides the  
default implementation in java.util.Object.  
Note:  
There is no right answer for this implementation, the definition of equality between two  
nodes is completely up to you. However, notice that the argument is of Object type.  
This means that the obj is not necessarily a DAFNode, or its keyor value might have  
different data types. Make sure to handle these cases.  
As equals() is an overridden method, it is used by many built-in functions such as  
contains() method in java.util.LinkedList. You want to think about how equals() would  
be called, and implement it in a way that satisfies how you would use the DAFNodes.  
@
Override  
public int hashCode()  
A method that returns a hash value for this DAFNode object. The implementation here  
overrides the default implementation in java.util.Object.  
Note:  
You may choose any hash functions you prefer, but make sure the keyand data of  
this node are taken into account (you can use their hashCode()).

Complete these constructors and methods in the DAFTree class.  
public DAFTree()  
A constructor that initializes an empty DAFTree.  
public int size()  
A method that returns the total number of elements stored in the tree.  
public int nUniqueKeys()  
A method that returns the total number of unique keys stored in the tree.  
public DAFNode<K, D> insert(K key, D data)  
A method that inserts a new node that has given keyand data to the tree. This  
method returns the inserted DAFNode if the insertion is successful, and returns null if  
the tree already has a node with the same keyand data.  
Implementation tips:  
You may start from the algorithm in the midterm 2. Make sure you revised the  
algorithm so it matches this implementation (par reference updates, duplicate  
detection, etc.).  
@
throws NullPointerException if keyor data is null  
public boolean lookupAny(K key)  
A method that checks if any nodes with the given keyare stored in the tree. This  
method returns true if at least one node is found, and false otherwise.  
@
throws NullPointerException if the keyis null  
public boolean lookup(K key, D data)  
A method that checks if a node with the given keyand value is stored in the tree. This  
method returns true if such a node is found, and false otherwise.  
@
throws NullPointerException if keyor data is null  
public LinkedList<D> getAllData(K key)  
A method that returns a LinkedList that contains all data associated under the given  
key. The order of all data within the list does not matter. This method returns an empty  
list if the keyis not found, and a list with all data fetched if nodes with this keyare  
present.  

@
throws NullPointerException if the keyis null  
public boolean remove(K key, D data)  
A method that removes the node with the given keyand data from the tree. This  
method returns true if the node is removed from the tree, and returns false if this node  
is not present prior to this method call.  
Implementation tips:  
You are recommended, but not restricted, to use the provided helper methods, which  
is explained after the Implementation section. To use the provided helpers correctly,  
make sure you read through the description of the helpers and understand how they  
work.  
You would also want to update the number of unique keys, which requires extra  
carefulness.  
@
throws NullPointerException if keyor data is null  
public boolean removeAll(K key)  
A method that removes all nodes with the given keyfrom the tree. This method  
returns true if any nodes are removed from the tree, and returns false if no nodes with  
the given keyare present prior to this method call.  
Implementation tips:  
You would want to make use of the remove() method, after correctly removing all the  
duplicates. Recall that removing a node means no reference within the tree would  
point to that node anymore. Make sure you also correctly update the number of  
elements while removing the duplicates.  
@
throws NullPointerException if the keyis null  
public Iterator<DAFNode<K, D>> iterator()  
A method that returns a new DAFTree iterator instance.  
Complete these constructors and methods in the DAFTreeIterator class.  
public DAFTreeIterator()  
A constructor that initializes a DAFTree iterator that iterates through all keys in the  
tree (including duplicates).  
public boolean hasNext()  
A method that checks if the iterator has more elements to return. This method returns  

true if there are more elements, and false otherwise.  
public DAFNode<K, D> next()  
A method that returns the next node.  
Implementation tips:  
In BST, you have used a stack to perform an in-order traversal that the iterator will  
use, and for the DAF tree, you will do the same thing. However, note that for the  
in-order traversal of the DAF tree, the order becomes left -> root -> dup -> right, so  
your iterator implementation should take care of the dup sequence accordingly.  
@
throws NoSuchElementException if the iterator reaches the end of traversal  
Provided Helpers  
You are provided with several helper methods in DAFTree.java. You may or may not use it  
for your implementation. You may also make edits to them if you want to.  
The following helper methods are in the DAFNode class. These are used by the helper  
methods of DAFTree class, so you might not use the following two helpers.  
public void swapReferencesWith(DAFNode<K, D> other)  
A helper method that will swap the left, right, par references of this node with the given  
other node. When swapping the left and right references, the pointed child node’s par  
will be updated as well. When swapping the par references, the pointed parent node’s  
child reference will be updated using the below helper method.  
Note: This method is used by remove()  
public void changeParentTo(DAFNode<K, D> child, DAFNode<K, D>  
parent)  
A helper method that changes this node’s par reference to the given parent node. The  
given child is used to determine which child reference (left, right, dup) of the given  
parent should point to this node. Only the connection between this node and the given  
parent will be updated. Does nothing if the given child is not a child node of parent.  
Note: This method is designed to be specifically used by the above helper method, so  
it is very likely that you would not use this method.  
@
throws NullPointerException if child is null  
The following helper methods are in the DAFTree class.  

public boolean remove(DAFNode<K, D> cur)  
A public helper method that removes the given cur from the DAFTree. The method  
always returns true, since the method assumes the given cur exists in the  
DAFTree. This method calls the removeHelper method described below to perform  
the actual remove operation.  
private DAFNode<K, D> removeHelper(DAFNode<K, D> root, K key, D  
data)  
A helper method that removes the node with the given keyand data under the given  
subroot root, in a recursively manner. It is based on the BST style of node removal –  
replacement by in-order successor – with several modifications.  
Modifications:  
–
If the node is unique, it would remove the node in a BST-like manner; if the  
node has duplicates, it would remove the node by making its parent points to its  
dup child.  
–
–
It updates the par reference at the very end.  
While ordinary BSTs would replace the keys without directly changing the node  
objects, this implementation would directly swap the nodes by replacing their  
left, right, par references.  
Note: The reason we would swap the node instead of swapping the key and data is to  
allow the possibility of using a hash table to store DAFNode in Part 4. If we are going  
to keep track of the DAFNodes by a hash table, then directly changing a node’s key or  
data would change the node’s hash value, resulting in the node staying in the  
incorrect slot inside the hash table. This is why we would swap the whole node  
objects. Notice that we would not swap the dup references as the duplicates are  
coupled with the key values and hence with the node itself.  
private DAFNode<K, D> findMin(DAFNode<K, D> root)  
A helper that returns the smallest node from a subtree whose subroot is the given  
root. This method is used by the removeHelper method to find in-order successor.  
You can add more helper methods with ANY access modifiers if you think they are  
necessary for your implementation.