4855
CS143 – Lab 1
Sorted Set
Introduction
A set is an unordered collection of data that contains no duplicates. A sorted list is an ordered collection
of data that is always sorted using the elements’ natural order. A sorted set is a combination of the
above two ADTs having the following attributes:
• The collection is ordered, meaning it maintains the relative order of the elements, and
elements can be accessed by position.
• The collection is sorted, meaning that the order in which the elements are placed is based on a
comparison of the relative value of adjacent elements.
• The elements of the collection are all unique, meaning that no duplicates can be added.
A sorted set contains the following functions:
• add(value) – adds the value to the properly sorted place in the collection and returns the index
where it was added, or returns -1 if not added.
• remove(value) – deletes the value from the collection and returns true if successful, false if not.
• find(value) – reports the current index of a value in the collection, or -1 if not found.
• get(index) – returns the value at the given index
• size() – returns the number of elements currently stored in the collection.
Lab Overview
In the Lab 1 module you are given a NetBeans project that contains the following classes:
• A domain class called Player that represents a single player of an online game and their
personal high score. The class implements Comparable in order to help sort players from
highest score to lowest. It also contains an equals method based on player names to help
prevent duplicate players from being added.
• A data-management class called SortedSet that models the sorted set ADT described above.
(This class currently contains only stubs of methods.)
• A main class called Lab1 used to test the SortedSet.
Your job is to complete the SortedSet class. The following requirements and limitations apply:
• You must use a partially-filled array of Player objects as your underlying data storage.
• You must double the size of the array whenever it becomes too full to add another player, but
not before then.
• You may not use any methods in the Array, Arrays, or System classes to aid in array handling or
convert the array to another type of collection. Instead, write the necessary code based on
simple selection and repetition structures and good computer science logic.
• You must implement the variation of the insertion sort described in the lectures when adding a
value, as this is a very efficient algorithm when adding a single value to an already sorted list.
Attachments:
Lab1Requireme….pdf
Lab1.zip
