This is the final programming assignment for the semester. It will involve creating both a front end and back end.
Similar to previous assignments, there will also be a lab which will act as a starting point towards completing this assignment.
The final project is due at midnight on the last day of classes, 12/9/2022.
- But, I will accept submissions, for full credit, until midnight, on 12/16/2022.
Start by creating a file, your_last_name_in_lower_case_p8.java
. It should reside within the src
directory.
Before you move on with the reset of Program Assignment 8, you will need to finish lab12. For lab12, please do all the details specified here, then push up your changes to github. The commit hash on brightspace should correspond to what you finish by the end of lab12:
git add -A
git commit -m "finished lab 12, rest of program assignment 8 will come later."
git push
git rev-parse HEAD
To be clear here, lab12 will be completely captured and graded here, in the program assignment 08 repository. There is no separate lab12 repository. Your grade for program assignment 08 will also be based upon this repository, just for another commit hash that you will submit later on, when you finish it in its entirety.
If you finish lab12 early in lab, you may continue on to implement the rest of programming assignment 08. See below.
- For program assignment 8, we will be reading two files of integer values.
- The first file is the "sort" file
- The second file is the "search" file
- When the files are read, the values are added to two
int
arrays.- In my code, I read the values into an
ArrayList<Integer>
, and once the entire file was read, my code copies the values into the appropriateint[]
.
- In my code, I read the values into an
- For programming assignment 1, we implemented selection sort to sort a
String[]
. - We will be re-using that method, except we will be updating it to sort an
int[]
. - This update should be easy.
- Replace
String[]
withint[]
- Assuming the
String[]
is namedvalues
:- Replace
if(values[j].compareTo(values[min]) < 0)
withif(values[j] < values[min])
- Replace
- Replace
- That should be pretty much it.
The first part of the remainder of the program is to evaluate various performances of sorting an array int[] values
and also copying values into different data structures.
-
Sort an
int[]
using the selection sort that we implemented in program one.O(n^2)
. -
Add the values as keys into a binary search tree
O(n log n)
-
Add the values to a TreeSet
O(n log n)
-
Add the values to a PriorityQueue
O(n log n)
-
Add the values to a HashSet
O(n)
-
Add the values to an ArrayList
(unsorted, O(n))
-
Add the values to an ArrayList and use the
java.util.Collections.sort
to sort the values.O(n log n)
-
Add the values to an
int[]
(unsorted, O(n))
-
Note: Other than the
HashSet
, theArrayList
(unsorted), andint[]
(unsorted), each of the above data structures will have sorted the data either while adding it or after adding it -
Our Goal: Keep track of the time spent performing each of the above.
The second part of the remainder of the program is to evaluate various performances of searching for elements within difference data structures.
- Search for a value in a
int[]
smartly.O(log n) for each search
- Implement a binary search
- Search for a value in a Binary Search Tree
O(log n) for each search
- This is fast and easy, use the
getNode()
method
- Search for a value in a TreeSet
O(log n) for each search
- This is fast and easy, use the
contains()
method
- Search for a value in a PriorityQueue
O(n) for each search.
- This is slow, even though the PriorityQueue uses a heap to store the values, and the polling is quick, using the
contains()
method is very slow (and documented as such). - Note: Keep in mind, heaps are primarily used to quickly grab the next value from the priority queue, and was not optimized for searches.
- Search for a value in a HashSet
O(log n)
garaunteed for each search, this might beO(1)
- This is fast and easy, use the
contains()
method.
- This is fast and easy, use the
- Search for a value in an
ArrayList
in a naive wayO(n)
for each search- This is slow, use the
contains()
method.
- Search for a value in an
ArrayList
in a smarter way.O(log n)
for each search.- This is fast, use the
java.util.Collections.binarySearch
- Search for a value in a
int[]
naively.O(n)
for each search.- This is slow, use a for loop to search.
As you already saw from lab12, the program has a GUI component (our front end) and a non-GUI component (our backend).
Focusing on the non-GUI component, we will:
- Read the two files
- Create various data structures
- Populate the data structures
- Search for values in the data structures
- Track the time to do the various tasks.
- Report the number of search elements found in the various data structures
Please refer to these slides showcasing what is happening in the front end for our GUI.
Generally, when you create a GUI, if any of the work behind the GUI is going to take time, the GUI and the back end computations are done in separate threads.
-
This stops the GUI from freezing while waiting for the back end computations to complete.
-
Generally speaking, anything that takes more than 10 - 20 ms is long enough that the delay might be noticable to a typical user.
-
Note: We are NOT going to deal with this issue for our program.
-
When you select the
sort ints
,search arraylist
,search priority queue
, andsearch array
for the larger test files, you will definitely notice that the GUI will temporarily freeze while waiting for the computations to complete. -
Sorting the 100,000 value file with selection sort takes around 3.5 seconds on my laptop, and the
250,000
value file takes around 23 seconds.
- This is fairly complex.
- Here is what my code looks like for the
leftButtonPanel
:- Instantiate the panel
- Instantiate the
GridBagLayout
- Set the layout of the panel
- Instantiate the left buttons and panels.
Here is whay my code looks like for the first couple of buttons and labels being added to the leftButtonPanel:
- For my
JButtons
andJLabels
, I declare them asstatic
fields in the class, and when initially instantiated, theJButtons
are disabled. - When the input files are read, I enable the appropriate
JButtons
.- Refer back to the front end slides for more details, but it should be intuitive.
- The search buttons are enabled when both the search file is read and the correspnding "sort/add" button is selected.
- Your code needs to handle both cases where the search file is read BEFORE and AFTER the corresponding "sort/add" button is selected.
- Each of the
JButtons
need to have anActionListener
defined for it.- See
example2a.java
- See
- All of my code is in a single file. This is not required, but it does work.
- Except for the binary search tree code, which I re-used from program 5.
private static void selectionSort()
private static int searchInts()
private static void addToBinarySearchTree()
private static int searchBinarySearchTree()
private static void addToTreeSet()
private static int searchTreeSet()
private static void addToHashSet()
private static int searchHashSet()
private static void addToPriorityQueue()
private static int searchPriorityQueue()
private static void addToArrayList()
private static int searchArrayList()
private static void addToSortedArrayList()
private static int searchSortedArrayList()
private static void addToArray()
private static int searchArray()
private static void readData(String filename, boolean readSortValues)
static class MenuItemActionListener implements java.awt.event.ActionListener
static class ButtonActionListener implements java.awt.event.ActionListener
Button | Function |
---|---|
sort ints | private static void selectionSort() |
add to bst | private static void addToBinarySearchTree() |
add to treeset | private static void addToTreeSet() |
add to priority queue | private static void addToPriorityQueue() |
add to hashset | private static void addToHashSet() |
add to arraylist | private static void addToArrayList() |
add to sorted arraylist | private static void addToSortedArrayList() |
add to array | private static void addToArray() |
------------------------- | ---------------------------------- |
search sorted ints | private static int searchInts() |
search bst | private static int searchBinarySearchTree() |
search treeset | private static int searchTreeSet() |
search priority queue | private static int searchPriorityQueue() |
search hashset | private static int searchHashSet() |
search arraylist | private static int searchArrayList() |
search sorted arraylist | private static int searchSortedArrayList() |
search array | private static int searchArray() |
- And the two menu items both use
private static void readData(String filename, boolean readSortValues)
- Since they are fields of the class, they can be accessed directly by the methods in the class.
- This will be useful when needing to enable buttons as the state changes.
- They can't be access directly by the inner classes of the main class, but they can be accessed if we pass them as a paramter of the inner class constructor.
- See example2a.java
- You don't need to use my variable names, they are just to show you an example of what I did.
Field | Description |
---|---|
int[] sortValues |
contains the list of values read from the “sort file” |
int[] searchValues |
contains the list of values read from the “search file” |
int[] sortedValues |
is the array that is sorted in selectionSort() |
TreeSet<Integer> treeSetValues |
is the tree set used for adding to and searching |
HashSet<Integer> hashSetValues> |
is the hash set used for adding to and searching |
PriorityQueue<Integer> priorityQueueValues |
is the priority queue used for adding to and searching |
ArrayList<Integer> arrayListValues |
is the unsorted ArrayList used for adding to and searching |
ArrayList<Integer> sortedArrayListValues |
is the sorted ArrayList used for adding to and searching |
int[] unsortValues |
is the unsorted int[] used for adding to and searching |
BinarySearchTree bst |
is the binary search tree used for adding to and searching |
To get the time estimates, simply capture the time just before and just adter calling the various methods:
long t0 = System.currentTimeMillis();
long t1 = System.currentTimeMillis();
The set the text to (t1 - t0) + "ms"
for the appropriate label.
-
For the two
ActionListeners
, in theiractionPerformed()
methods, I have a collection ofif
statements to determine which button or menu item was selected, and then call the appropriate method to perform the required action.- See example2a.java
-
The vast majority of my code is related to the GUI.
-
The other code, reading the input files, and adding/sorting/searching for values is quite small in comparison.
- For the TreeSet, HashSet, unsorted ArrayList, and PriorityQueue, we are just using the
add()
andcontains()
methods. - For the binary search tree, we are just doing the
insertNode()
andgetNode()
methods.
- For the TreeSet, HashSet, unsorted ArrayList, and PriorityQueue, we are just using the
- The search methods return the number of values found
- The label associated with the “search” buttons are updated with the number of search values found and the time spent searching for them.
- Note: The labels should have
X / Yms
after performing the search - Where
X
is the number of values found in the search andY
is the number of milliseconds to perform the search
- Note: The labels should have
The following code assumes that you are dealing with an already sorted array:
If you made it to the end, congratulations! Developing front end and back end is no small feat, especially for an intro course.
If you wish, you can try to do a merge sort for 10 extra points of extra credit.
Submit your finished program to github and post the latest commit hash on BrightSpace.
git add -A
git commit -m "finshed program assignmnent 08"
git push
git rev-parse HEAD
=======
Java Front-End Project
origin/main