辅导Data Structures: Assignment 2

日期：2023-11-18 07:31

Data Structures: Assignment 2
My PlayStation Friends
SP2, 2018
James Baumeister
March 2018
1 Introduction
Needing a way to manage all your PlayStation friends, you decide to build a backend system for adding, removing and maintaining them. The idea is to organise
your friends so you can search for individuals, search for players who have the
same games as you, determine rankings, and view player information and
trophies. At the same time, you’d like your search queries to be fast, ruling out
basic structures like arrays and linked lists. Deciding that the most important
factor for ordering your friends is level, you build a binary search tree (BST)
structure, using the level (actually a function on level, see section 4) as the key.
In this assignment we will build a BST structure, with each node representing
a PlayStation friend. Each friend node contains information about that player,
including their username, level and date of birth, along with attached data
structures for their games (single linked-list) and trophies (ArrayList). In
accordance with the rules of BSTs, each friend has a parent node and two child
nodes, left and right. From any one node, all nodes to the left are less (lower level)
and all nodes to the right are greater (higher level). Due to this, searching for
higher or lower-levelled players is, on average, a O(logn) process.
This assignment consists of a number of parts. In part A you will setup the
basic class structure, ensuring that the test suite is able to run without error. In
part B you will implement the basic structures needed by User to hold multiple
Trophy and Game objects. In part C you will create your BST-based friend database.
Finally, in part D you will improve the efficiency of your tree by implementing AVL
balancing. You are free to add your own methods and fields to any of the classes
in the Database package, but do not change any existing method prototypes or
field definitions. A testing suite has been provided for you to test the functionality
of your classes. These tests will be used to mark your assignment, but with altered
values. This means that you cannot hard-code answers to pass the tests. It is
suggested that you complete the assignment in the order outlined in the following
sections. Many of the later-stage classes rely on the correct implementation of
their dependencies.
2
1.1 Importing into eclipse
The Assignment has been provided as an eclipse project. You just need to import
the project into an existing workspace. See Figure 1 for a visual guide. Make sure
that your Java JDK has been set, as well as the two jar files that you need for junit
to function. This can be found in Project → Properties → Java Build Path →
Libraries. The jar files have been provided within the project; there is no need to
download any other version and doing so may impact the testing environment.
Figure 1: Importing the project through File → Import
2 Part A
If you run the testing suite, you will be lovingly presented with many errors.
Your first task is to complete the class implementations that the tests expect
(including instance variables and basic methods) to remove all errors from the
testing classes.
3
2.1 Game
The Game class represents one PlayStation game and includes general
information, namely the title, release date, and total number of available trophies.
In addition, it holds a reference to another Game object. This will be important in
section 3 where you will make a single-linked list of games. The Game class
requires the following instance variables:
private String name; private
Calendar released; private Game
next; private int totalTrophies;
The toString method should output a string in the following format (quotation
marks included):
"Assassin's Creed IV: Black Flag", released on: Nov 29, 2013
Hint: A printed Calendar object may not look as you might expect. Take a look at
APIs for java date formatters.
You should also generate the appropriate accessor and mutator methods.
GameTester will assign marks as shown in Table 1:
Table 1: GameTester mark allocation
Test Marks
testConstructor 2
toStringTest 3
Total: 5
2.2 Trophy
The Trophy class represents one PlayStation trophy and includes information
about its name, date obtained and the game from which it was earnt. Additionally,
its rank and rarity values are set from finite options available through enumerator
variables. The Trophy class requires the following instance variables:
public enum Rank {
BRONZE, SILVER, GOLD, PLATINUM
} public enum Rarity {
COMMON, UNCOMMON, RARE, VERY_RARE, ULTRA_RARE
}
4
private String name; private Rank
rank; private Rarity rarity; private
Calendar obtained; private Game
game;
The toString method should output a string in the following format (quotation
marks included):
"What Did You Call Me?", rank: BRONZE, rarity: RARE, obtained on: May 04, 2014
You should also generate the appropriate accessor and mutator methods.
GameTester will assign marks as shown in Table 2:
Table 2: TrophyTester mark allocation
Test Marks
testConstructor 2
toStringTest 3
Total: 5
2.3 User
The User class represents a PlayStation user and, more generally, a tree node. Most
importantly when using as a tree node, the class must have a key on which the
tree can be ordered. In our case, it is a double named key. This key is a simple
function based on the combination of a user’s username and level. As levels are
whole numbers and likely not unique, a simple method (see calculateKey snippet
below) is used to combine the two values into one key whilst preserving the level.
For example, imagine that the hashcode for username “abc” is 1234 and the user’s
level is 3. We do not want to simply add the hash to the level as that would not
preserve the level and would lead to incorrect rankings. Instead, we calculate
1234/10000 to get 0.1234. This can then be added to the level. As the usernames
must be unique, our node keys are now also unique 1 and the user level is
preserved.
private double calculateKey() { int hash =
Math.abs(username.hashCode()); // Calculate
number of zeros we need int length =
(int)(Math.log10(hash) + 1);

1 A string’s hash value can never be guaranteed to be unique, but for the purposes of this assignment we
will assume them to be.
5
// Make a divisor 10^length double divisor =
Math.pow(10, length);
// Return level.hash return level +
hash / divisor;
}
The User class requires the following instance variables:
private String username; private int level;
private double key; private
ArrayList