Projects

1 - Project 1 - SitRite3K

classDiagram
class Social
<<utility>> Social
Social: +distance(s int[], t int[])$ double

For this assignment, you must implement three classes, a class named Student that encapsulates information about individual students, a class named Posse that manages an individual Student object’s friends, and a utility class named Social that contains methods for performing calculations involving social networks.

At a high level of abstraction, the relationships between these classes can be modeled using the following UML class diagram.

classDiagram
class Student
<<mutable>> Student
class Posse
<<mutable>> Posse
class Social
<<utility>> Social
Student --o Posse : Each Student has exactly one Posse object as an attribute<br/> (containing their friends).<br /><br />A Posse contains zero or more Student objects<br/> (i.e., a Student object can have zero or more friends).<br /><br />Each Student can be a<br/> member of zero or more Posse objects<br/> (i.e., each Student object can be a friend of zero other Student objects).
Student -- Social : calculatesUnhappinessWith

The details of each class in this diagram are provided below.

The Social class

The Social class must conform to the following detailed class diagram.

Detailed Specification

distance

The distance() method must calculate the Euclidean distance between two seats, s and t, as follows:

$$ \tag*{(1)} d(s,t) = \sqrt {\left( {s_0 - t_0 } \right)^2 + \left( {s_1 - t_1 } \right)^2 } $$

The Student class

The Student class must conform to the following detailed class diagram.

You are free to add additional private helper methods, but the public methods must match the UML specification exactly.

Detailed Specifications

Attributes

The role of the name attribute and Posse attributes should be apparent from the UML diagrams. The seat attribute must have a length of 2 and must contain the row and column (in that order) of the Student object’s seat.

Parameter Validation

All methods that change the row and/or column must (directly or indirectly) validate the parameters they are passed. Specifically, if the parameter is less than 0 then the corresponding instance variable must be set to 0.

Constructors

As usual, the constructors must appropriately initialize each of the instance variables. The single-argument constructor must initialize both the row and the column values to 0. (Note: As always, you must avoid code duplication. In this case, one constructor should probably call the other, which itself should call setRow() and setColumn()).

Accessors and Mutators

Getters and setters must perform the appropriate operations (accounting for parameter validation as discussed above).

addFriend()

This method must add the provided Student object to the Posse named friends. However, it must not add a Student object to her/his own Posse.

equals()

This method must return true if and only if the name of the owning Student object is the same as the name of the given Student object. (Note that, this product assumes that names are unique.)

unhappiness()

A student’s unhappiness is defined to be the summed Euclidean distance from the student to each of the student’s friends. More formally, the unhappiness of student g is defined to be:

$$ \tag*{(2)} \sum_{f \in F} d(\hat{g},\hat{f}) $$

where \(F\) denotes the set of friends of student \(g\), \(\hat{g}\) denotes the seat of student \(g\), \(\hat{f}\) denotes the seat of student \(f\), and \(d\) denotes the Euclidean distance function.

If the student has no friends then this method must return 0.0.

The Posse class

The Posse class must conform to the following UML diagram:

You are free to add additional private helper methods, but the public methods must match the UML specification exactly.

Detailed Specifications

Constructors

As usual, the constructors must appropriately initialize each of the instance variables. The default constructor must initialize the Posse to have a maxSize of DEFAULT_SIZE. (Note: As always, you must avoid code duplication.)

The get() Methods

Both get() methods must return either (a reference to) a Student that is in the owning object’s Posse or null.

The version that is passed an int must return the Student at the given index of the members array if the index is valid and must return null otherwise.

The version that is passed a String must return the Student with the given name if that Student is in the members array and must return null otherwise (including when the parameter is null). You may assume that the parameter name is unique.

The get() methods must not contain duplicate code and must not duplicate code in any other methods.

contains()

The contains() method must return true if the given Student is in the owning Posse and must return false otherwise (including when the parameter is null). It must not duplicate code that is in the get() methods (i.e., it should call one of the get() methods and/or call a private helper method.)

add()

The add() method must add the given Student to the end of the owning Posse if and only if it is not already in the Posse and the Posse is not full.

It must return false if the Posse was full and true if either the Student was added or if it was already in the Posse.

getSize()

The getSize() method must return the number of Student objects that are currently in the Posse (not the maximum size of the Posse).

getMaxSize()

The getMaxSize() method must return the maximum size of the Posse (not the number of Student objects that are currently in it).

Implementation Advice

Start with stubs

1. Begin by creating each of the classes for the assignment (in this case, Social, Student, and Posse).
2. In each of those classes, add a “stub” for every method required in the spec:
   1. This stub should have the same signature (visibility, return type, and parameter quantity and types)
   2. If the method is not void, return some (incorrect) value of the correct type.
3. After doing all of the above correctly, your project should compile successfully.

By working with stubs, you can quickly turn the compiler from the grouchy, nit-picking taskmaster into your ally and helper.

Continue with small iterations

You should work on one class at a time and, within each class, one method at a time. After you complete each method you should test it. You may use a test harness (e.g., JUnit) if you are familiar with one, or you may write simple drivers. (Note: You must not submit your tests.)

Working on one method at a time, starting with stubs that already compile, the amount of time that your project can compile successfully should dramatically outweigh the amount it doesn’t.

You should consider implementing the classes/methods in the following order:

1. The distance() method in ths Social class.
2. The constructors, setters, and simple getters in the Student class.
3. The equals() method in the Student class.
4. The constructors in the Posse class.
5. The add() method in the Posse class.
6. The getSize() method in the Posse class.
7. The getMaxSize() method in the Posse class.
8. The get() methods in the Posse class.
9. The contains() methods in the Posse class.
10. The add() method in the Student class.
11. The unhappiness() method in the Student class.

Don’t delete the tests when you finish a method! You may be able to reuse them if you need to modify the method later. They also provide a useful reference if you need to get help.

Submission and Grading

You should never start design or construction until you completely understand the project.

You should start by carefully reading the project specifications. (In general it is a good idea to print a paper copy so that you can take notes and perform calculations as you read.)

Implement all of the classes (in accordance with the specifications, perhaps informed by the Implementation Advice above) and submit them to gradescope .

You are not required to submit tests for these classes.

Grading

The code quality grade will be based on such things as:

• Comment clarity
• Code clarity (including variable names)
• Code duplication
• Elegance
• Acknowledgements (as appropriate)

You may submit to Gradescope an unlimited number of times.

2 - Project 2 - Seam Carving

Overview

Seam carving is a content-aware image resizing technique for changing the size of an image by one pixel of width or height at a time. It is a core feature in Adobe Photoshop and other graphics applications. The underlying algorithm is simple and elegant, but the technique was not discovered until 2007 by Shai Avidan and Ariel Shamir. Here is their original video presentation from SIGGRAPH 2007, the premier conference for computer graphics research:

Objectives

• Manipulate 2D arrays of objects and integers.
• Validate arguments by throwing exceptions.

Provided Files

• 3x4.png – small example image
• 6x5.png – another small example image

• HJoceanSmall.png – real image
• Main.java – example application
• Picture.java – for loading images (originally found at https://introcs.cs.princeton.edu/java/stdlib/Picture.java )
• ProvidedCode.java (find this in your Canvas course) – partial solution
• SeamCarver.java – stubs

Acknowledgements

This assignment is based on materials by Josh Hug, Maia Ginsburg, and Kevin Wayne.

Example Use

Given an image, it is sometimes desirable to resize it in only one dimension. Consider the 507 pixel wide by 285 pixel tall image below. Suppose that we’d like to resize it to 357 x 285 pixels (i.e., making it narrower without changing the height).

Example 1

The easiest approaches are to rescale the image or to crop the image. However rescaling ruins the aspect ratio, making everything look squashed, whereas cropping removes image content (like the people on the right).

Example 2

Example 3

By contrast, seam carving resizes images in a content-aware manner, resulting in much better results for some types of images. Unimportant pixels (like the ocean separating the two people in the middle) are thrown away, while interesting pixels (like the people and the island) are preserved.

Example 4

Example 5

How It Works

Despite its power and modernity, the seam carving algorithm is elegant and easy to describe. We start by converting an image to an “energy matrix” using a very simple function that gives higher (brighter) energy values to important pixels and lower (darker) energy to unimportant ones.

Example 6

We then find the path from the top to the bottom such that the total energy of the path is minimized. This can be done using a dynamic programming approach or by casting it as a shortest paths problem on a directed graph. (You’ll learn about these more advanced techniques in CS 327 and CS 412.)

Example 7

We then “shrink” the image by creating a copy of the original image, but excluding all of the seam pixels (highlighted in image above). Since the seam is exactly one pixel per row, the resulting image is one pixel narrower.

To shrink the image further, we repeat the entire process as many times as we’d like, reducing the width by one each time. Finding and removing horizontal seams is analogous.

Image Library

To read, write, and display images, we will use the Picture class from Sedgewick’s and Wayne’s standard libraries . Within an image, the pixel (x, y) refers column x and row y. Pixel (0, 0) is at the upper-left corner, and pixel (W-1, H-1) is at the bottom right corner.

Warning: this “column-major” order is the opposite from the mathematical notation used in linear algebra, where (i, j) refers to row i and column j. It’s also different from Cartesian coordinates, where (0, 0) is at the lower-left corner.

Colors

Each pixel is represented by a java.awt.Color object. Colors are based on three integers (ranging from 0 to 255) that represent the amounts of Red, Green, and Blue (also known as RGB values).

You can look for color charts on the web to see your favorite colors represented in values specific enough for computers. There are different systems for representing colors, but the 3-channel R.G.B. representation with values ranging from 0-255 (inclusive) is quite popular. Marketing departments often publish “Branding” guidelines to help standardize an organizations presentation on the web, in print, and etc. See for example JMU’s Branding Identity Colors page, just one component of our overall Brand Guide .

SeamCarver

In this assignment, you will implement the seam-carving technique. The main algorithm involves three steps: (1) compute the energy of each pixel, (2) find the seam with the least amount of energy, and (3) remove all the pixels along the seam. Step 2 has already been implemented for you in the ProvidedCode class. Your task is to implement the SeamCarver class in the UML diagram below.

classDiagram
class SeamCarver
SeamCarver: -Picture picture
SeamCarver: -int width
SeamCarver: -int height
SeamCarver: +SeamCarver(picture Picture)
SeamCarver: +getPicture() Picture
SeamCarver: +getWidth() int
SeamCarver: +getHeight() int
SeamCarver: +energy(x int, y int) int
SeamCarver: +energyMatrix() int[][]
SeamCarver: +removeHorizontalSeam(seam int[]])
SeamCarver: +removeVerticalSeam(seam int[])

energy

For this assignment, we will use the “dual-gradient” energy function:

• The energy of a pixel at (x, y) is Δ_x² + Δ_y².
• The square of the x-gradient Δ_x² = R_x² + G_x² + B_x². The square of the y-gradient Δ_y² = R_y² + G_y² + B_y²
• R_x, G_x, and B_x are the differences of red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y).
• R_y, G_y, and B_y are the differences of red, green, and blue components between pixel (x, y + 1) and pixel (x, y − 1).

By convention, the indices x and y are integers between 0 and W − 1 and between 0 and H − 1 respectively, where W is the width of the current image and H is the height. Your method should throw an IndexOutOfBoundsException if either x or y is outside its range. When x is out of bounds, the error message of the exception should be “x = %d, width = %d” (with the specific values). When y is out of bounds, the error message of the exception should be “y = %d, height = %d” (with the specific values).

To handle pixels on the borders of the image, we will define the leftmost and rightmost columns as adjacent and the topmost and bottommost rows as adjacent. For example, to compute the energy of a pixel (0, y) in the leftmost column, we use its right neighbor (1, y) and its left neighbor (W − 1, y).

Consider the 3-by-4 image with RGB values shown in the table below:

• Non-border pixel example

  The energy of pixel (1, 2) is calculated from pixels (0, 2) and (2, 2) for the x-gradient:

  R_x = 255 − 255 = 0,
  G_x = 205 − 203 = 2,
  B_x = 255 − 51 = 204,
  

  yielding Δ_x² = 0² + 2² + 204² = 41620.

  The energy of pixel (1, 2) is calculated from pixels (1, 1) and (1, 3) for the y-gradient:

  R_y = 255 − 255 = 0,
  G_y = 255 − 153 = 102,
  B_y = 153 − 153 = 0,
  

  yielding Δ_y² = 0² + 102² + 0² = 10404.

  Thus, the energy of pixel (1, 2) is 41620 + 10404 = 52024.

• Border pixel example

  The energy of the border pixel (1, 0) is calculated by using pixels (0, 0) and (2, 0) for the x-gradient:

  R_x = 255 − 255 = 0,
  G_x = 101 − 101 = 0,
  B_x = 255 − 51 = 204,
  

  yielding Δ_x² = 0² + 0² + 204² = 41616.

  The energy of the border pixel (1, 0) is calculated by using pixels (1, 3) and (1, 1) for the y-gradient:

  R_y = 255 − 255 = 0,
  G_y = 255 − 153 = 102,
  B_y = 153 − 153 = 0,
  

  yielding Δ_y² = 0² + 102² + 0² = 10404.

  Thus, the energy of borderpixel (1, 0) is 41616 + 10404 = 52020.

energyMatrix

The energy matrix is constructed by getting the energy at each pixel (x, y). For example, using the 3-by-4 image from the previous section, the energy matrix would be:

findVerticalSeam

The findVerticalSeam() method returns an array of length H such that entry i is the column number of the pixel to be removed from row i the image. For example, consider the 6-by-5 image below:

The corresponding pixel energies are shown below, with a minimum energy vertical seam highlighted in pink. In this case, findVerticalSeam() returns the array { 3, 4, 3, 2, 2 }.

Remember that seams cannot wrap around the image. When there are multiple vertical seams with minimal total energy, your method should return the leftmost seam (based on its starting position on the top row).

The behavior of findHorizontalSeam() is analogous to that of findVerticalSeam() except that it returns an array of length W such that entry j is the row number of the pixel to be removed from column j of the image.

removeVerticalSeam

This removeVerticalSeam method replaces this.picture with a new Picture object and decreases this.width by 1. The new picture is a copy of the old picture with the seam pixels removed. The removeHorizontalSeam method is analogous, except that it decreases this.height by 1.

Notice that copying the picture is necessary, because you cannot change the picture’s width or height. And there is no method to copy the image; you will need to copy each pixel one at a time in this method.

removeHoriztonalSeam

See mention above

Validating Seams

Both of the seam removal methods need to handle edge conditions. They should throw an exception when called with invalid arguments:

1. Throw a NullPointerException if either removeVerticalSeam() or removeHorizontalSeam() is called with a null argument.
2. Throw an IllegalArgumentException if either removeVerticalSeam() or removeHorizontalSeam() is called with an array of the wrong length or if the array is not a valid seam (either an entry is outside the height/width bounds or two adjacent entries differ by more than 1).
3. Throw an IllegalArgumentException if either removeVerticalSeam() or removeHorizontalSeam() is called when the width or height of the current picture is 1, respectively.

Grading

Note: Your code must pass checkstyle before you can get any points for it on this assignment.

To help prepare you for implementing this project, please review the specifications and ask questions. Prior to writing the code for this project, check your understanding of the specifications via the P2 Readiness Quiz in gradescope .

3 - Project 3 - RGBFileFormat

Objectives

• Read and write text files representing 2D arrays.
• Throw exceptions with specific error messages.

Introduction

For this project you will implement saving and loading images in a format that supports debugging graphics algorithms by being more human-readable.

When testing applications like SeamCarver, creating small images can be helpful. The “RGB File Format” is a simple way to create your own images in plain text files.

See the .txt files below for examples of the RGB file format. Each line of the file is a tab-delimited sequence of pixels in the format (r, g, b) where r, g, and b are integers in the range 0 to 255. Space characters before/after the parentheses and commas are optional (all spaces should be ignored).

Provided Image Files

• 3x4.png – 3-by-4 image from P2

• 3x4.txt – 3x4.png in RGB format

• 3x4.bad – 3x4.txt missing a comma

• 6x5.png – 6-by-5 image from P2

• 6x5.txt – 6x5.png in RGB format

• 6x5.bad – 6x5.txt missing a parenthesis

Provided Source Files

• Picture.java – for loading images (originally found at https://introcs.cs.princeton.edu/java/stdlib/Picture.java )
• RGBException.java – custom exception class
• RGBFileFormatTest.java – example JUnit tests
• RGBFileFormat.java – stubs for Part A
• Convert.java – stubs for Part B

Part A: RGBFileFormat.java

Your first task is to implement the RGBFileFormat class in the UML diagram below. Each of its methods throws a FileNotFoundException when applicable. In addition, the load() method throws RGBException (with a specific error message and location) if the file format is incorrect.

classDiagram
class RGBFileFormat
RGBFileFormat: +load(path String)$ Picture
RGBFileFormat: +save(path String, picture Picture)$

load()

This method reads an RGB file and returns a corresponding Picture object. You will need to determine the width and height of the picture based on the file contents. Read the file line by line, construct a Color object for each pixel, and set the corresponding (x, y) of the picture.

Your load method should be robust enough to read a “sloppier” version of a picture file than your own very clean save method would produce. Specifically, (as mentioned in the introduction) your load method should ignore space characters . Therefore, you should be able to load files when the numbers have not been padded to a width of 3 characters (which is required of your own save method).

You may assume that the number of tab characters (\t) between pixels on the same line is exactly 1 and that the line will not have any other tab characters.

Your code must be able to handle the following error conditions:

• If the file is empty, throw an RGBException with the message "empty file".
• If any line is blank, throw an RGBException with the message "blank line".
• If the file has an inconsistent number of columns, throw an RGBException with the message "ragged".
• If a pixel does not begin with '(' or end with ')', throw an RGBException with the message "parens".
• If a pixel does not have exactly two commas, throw an RGBException with the message "commas".
• If a number does not parse as an integer, throw an RGBException with the message "number".
• If a number is not in the range 0 to 255, throw an RGBException with the message "range".

When throwing an RGBException, the x and y values should correspond to the location of the corresponding pixel. In the case of empty file, blank line, and ragged, the x value should be 0 and the y value should be the relevant location. In the case of an empty file, y should be 0.

save()

This method writes a Picture object to an RGB file. Each line of the file represents a row of the picture. Pixels on the same line should be separated by tab characters and use the format (r, g, b) with exactly one space after each comma. As shown in 3x4.txt and 6.5.txt, each integer should be 3 characters wide (with leading spaces), so that all pixels are 15 characters wide. Each line of the file should end with a newline character.

Unit Testing

RGBFileFormatTest is provided as a starting point to test your load and save methods. You should create additional .bad files of your own to test the other error conditions. These files and other test code will not be submitted; feel free to make any changes you like.

What unit tests should you write? Consider:

1. What is the simplest example you can think of where you expect a certain outcome for some part of the code (a method or a small number of methods)?
   • Write a unit test that asserts your expectation is the result of calling those methods.
2. What is an example where the same code should perhaps behave differently?
   • Maybe different “branch” or condition has been satisfied and so the behavior should be different according to the specs?
   • Maybe it’s an erroneous situation and the expectation is that a certain exception is thrown?
3. Might there be unexpected interactions between different methods?

Part B: Convert.java

Implement an application that uses your RGBFileFormat class to convert images to/from other formats. This application will be run from the command line as follows:

• To convert a png/jpg file to RGB format:

java Convert filename.png filename.txt

• To convert an RGB file to png/jpg format:

java Convert filename.txt filename.png

As shown above, the main method must have exactly two arguments: the source filename and the destination filename. If the application is not run with two arguments, main should print the following message to System.err and exit with status code 1:

Usage: java Convert SRC DST

Exactly one of the command-line arguments must end with ".txt"; this argument is the file in RGB format. If neither argument ends with ".txt", main should print the following message to System.err and exit with status code 1:

One of the images must end with .txt

The other argument must end with either ".jpg" or ".png"; this argument is the image to convert to/from. If any other extension is found, main should print the following message to System.err and exit with status code 1:

Unsupported file format: FILENAME

where FILENAME is the invalid argument.

After validating the command-line arguments, the main method should perform the requested conversion. For example, use RGBFileFormat to load the image and Picture to save the image, or vice versa.

Submission and Grading

For this project, you will submit each part separately on Gradescope:

• For Part A, submit only RGBFileFormat.java. It will be autograded with a longer version of RGBFileFormatTest that is more comprehensive than the provided code.
• For Part B, submit only Convert.java. It will be autograded with the solution for RGBFileFormat. That way, you can get full credit for Part B even if you don’t finish Part A.

You may submit up to 10 times without penalty. Additional submissions (if any) will receive a penalty of 3 points each. You are strongly encouraged to test your code offline before submitting.

As in previous assignments, your code must pass Checkstyle to receive any points. Submissions that don’t pass Checkstyle count toward the limit of 10 submissions. You are strongly encouraged to run Checkstyle offline before submitting.

4 - Project 4 - MovieTix

Introduction

PayTex is a (fictitious) company that develops technologies for electronic payment and crypto-currency systems. You have been hired by them to develop several components of a system called MovieTix.

MovieTix is, essentially, a hybrid debit/credit card for purchasing movie tickets. A MovieTix card can be pre-loaded with a particular number of tickets, can be used as a credit card, or can be used like a combination of the two. The prototype MovieTix system is being developed for university students and supports types of plans with the following “default” properties (though the system must support other properties, as described below).

• Movie Plan - a plan with both pre-paid tickets and the ability to purchase tickets on credit. Any pre-paid tickets that are not used during the semester are lost (and the purchase price is not refunded).
• Tiered Plan - a plan with both pre-paid tickets and the ability to purchase tickets on credit. It differs from a Movie Plan in that the first group of "purchases" is at a different price from the subsequent "purchases".
• Limited Plan - a plan with both pre-paid tickets and the ability to purchase a limited dollar amount of tickets on credit.

Existing Applications

Another PayTex employee has written two applications that will make use of your code when you complete it, and provided you with the source code.

• UsageSummarizer.java
• Planalyzer.java

The UsageSummarizer can be used to print a table of costs-per-movie for different amounts of usage (i.e., movies seen) for different common plans. The Planalyzer can be used to print a table that contains the best plan (of the same common plans) for different amounts of usage.

System Design

The relationships between the components that encapsulate plans can be modeled using the following UML class diagram.

classDiagram
class MoviePlan:::whitebg
MoviePlan: -double movieCost {readOnly}
MoviePlan: -double planCost {readOnly}
MoviePlan: -int prepaid {readOnly}
MoviePlan: -String name {readOnly}
MoviePlan: -double spent
MoviePlan: -int numberPurchased
MoviePlan: -int punches
MoviePlan: #Interval APPROVED_MOVIE_COSTS {readOnly}$
MoviePlan: #Interval APPROVED_PLAN_COSTS {readOnly}$
MoviePlan: +MoviePlan()
MoviePlan: +MoviePlan(name String, prepaid int, planCost double, movieCost double)
MoviePlan: #costOfPurchasedMovie() double
MoviePlan: #costToDate() double
MoviePlan: +getCategory() Category {exceptions=IllegalStateException}
MoviePlan: +getCostOfNextMovie() String
MoviePlan: +getCostPerMovie() double {exceptions=IllegalStateException}
MoviePlan: +getName() String
MoviePlan: +getPlanCost() double
MoviePlan: #numberPurchased() int
MoviePlan: #numberSeen() int
MoviePlan: #remainingPrepaid() int
MoviePlan: #spent() double
MoviePlan: +toString() String
MoviePlan: +use() boolean
class TieredPlan:::whitebg
TieredPlan: -double tierCost {readOnly}
TieredPlan: -int tierLimit {readOnly}
TieredPlan: +TieredPlan()
TieredPlan: +TieredPlan(name String, prepaid int, planCost double, movieCost double, tierLimit int, tierCost double)
TieredPlan: #costOfPurchasedMovie() double
MoviePlan<|--TieredPlan
class LimitedPlan:::whitebg
LimitedPlan: -double creditLimit {readOnly}
LimitedPlan: +LimitedPlan()
LimitedPlan: +LimitedPlan(name String, int prepaid, planCost double)
LimitedPlan: +LimitedPlan(name String, prepaid int, planCost double, movieCost double, creditLimit double)
LimitedPlan: +getCostOfNextMovie() String
LimitedPlan: +use() boolean
MoviePlan<|--LimitedPlan

The supporting components can be modeled using the following UML class diagram.

classDiagram
class Interval:::whitebg
<<immutable>> Interval
Interval: -double left {readOnly}
Interval: -double right {readOnly}
Interval: -boolean leftClosed {readOnly}
Interval: -boolean rightClosed {readOnly}
Interval: +Interval(original Interval)
Interval: +Interval(leftSymbol char, left double, right double, rightSymbol char) {exceptions = IllegalArgumentException}
Interval: +contains(value double) boolean
Interval: +closestTo(value double) double
Interval: +toString() String
Interval: +toString(formatString String) String
class Category:::whitebg
<<enumeration>> Category
Category: -Interval interval {readOnly}
Category: -String description {readOnly}
Category: -String symbol {readOnly}
Category: -Category(description String, symbol String, interval Interval)
Category: +getCategoryFor(price double)$ Category
Category: +getDescription() String
Category: +getSymbol() String
Category: +toString() String
Category: BARGAIN
Category: INEXPENSIVE
Category: MODERATE
Category: EXPENSIVE
Category: OUTRAGEOUS
class PlanUtilities:::whitebg
<<utility>> PlanUtilities
PlanUtilities: +findBestPlan(plans MoviePlan...)$ MoviePlan

The details of each class in this diagram are provided below. You may add methods but you must not override any existing methods that are not explicitly overridden in the UML diagram and you must not shadow any attributes.

Note that, in Java, the UML property modifier {readOnly} indicates that an attribute must be declared final.

The Interval Class

The Interval class is an encapsulation of an interval on the real line. Interval objects are used in several places.

In addition to the other specifications included in the UML diagram, the Interval class must comply with the following specifications.

Attributes

The double attributes left and right contain the left and right bounds of the interval.

The boolean attribute leftClosed indicates whether left is in the interval (when true) or not (when false). Similarly, the boolean attribute rightClosed indicates whether right is in the interval or not.

Interval(Interval)

The one-parameter constructor is a copy constructor. You need not validate the parameter.

Interval(char, double, double, char)

The four-parameter constructor is passed a char to indicate whether the interval is closed on the left (i.e., left is in the interval), the left and right bounds, and a char to indicate whether the interval is closed on the right. A leftSymbol of '[' indicates that the interval must be closed on the left and a rightSymbol of ']' indicates that the interval must be closed on the right. Any other char indicates that the interval is open on that side (though the traditional characters are '(' and ')'.

This constructor must throw an IllegalArgumentException if left is greater than right.

contains(double)

Must return true if the given value is contained in the interval and false otherwise. Note that this method does not use tolerances. Hence, it is not appropriate for some kinds of calculations.

closestTo(double)

Must return the value in the closure of the interval (i.e., the interval and its bounds, whether or not it is closed) that is closest to the given number. Note that this method can, if the value is in the interval, return the value itself. (This operation is sometimes described as projecting the value onto the closure of the interval.)

For example, the closure of the open interval (3.00, 8.00) is [3.00, 8.00]. So, the point in the closure of the interval (3.00, 8.00) that is closest to 5.30 is 5.30, and the point in the closure of the same interval that is closest to 100.50 is 8.00.

toString()

Must return a String representation of the interval. The result must contain a '[' or '(' as appropriate, followed by the left bound (in a field of width 6 with 2 digits to the right of the decimal point), followed by a ',', followed by a space, followed by the right bound (in a field of width 6 with 2 digits to the right of the decimal point), followed by a ']' or ')' as appropriate.

toString(String)

Like the version with no parameters, this method must return a String representation of the interval. However, the left and right bounds must be formatted using the String parameter as the format specifier (instead of being in a field of width 6 with 2 digits to the fight of the decimal point). In other words, if this method is passed a parameter of "%3.0f" it must format each bound in a field of width 3 with no digits to the right of the decimal point.

This method need not validate the String parameter. In other words, it may assume that the format specifier is valid.

The Category Enum

The Category enum encapsulates a predefined set of price categories.

In addition to the other specifications included in the UML diagram, the Category enum must comply with the following specifications.

Constructor

By default, enum constructors are private , which is conveniently aligned with this specification (see the UML). So, you should not explicitly mark the Category constructor as private in your source code or Checkstyle will complain about the redundancy.

Elements

The Category enum must contain five elements:

1. BARGAIN with a description of Bargain, a symbol of $, and an interval of [0.00, 5.00];
2. INEXPENSIVE with attributes Inexpensive, $$, and (5.00, 11.00];
3. MODERATE, with attributes Moderate, $$$, and (11.00, 15.00];
4. EXPENSIVE, with attributes Expensive, $$$$, and (15.00, 25.00]; and
5. OUTRAGEOUS with attributes Outrageous, $$$$$, and (25.00, ∞].

getCategoryFor(double)

Must return the Category object that contains the given price (or null if there is no corresponding Category).

toString()

Must return a String containing the description, a single space, and the symbol (in parentheses). For example, BARGAIN.toString() must return the String literal Bargain ($).

The MoviePlan Class

The MoviePlan class encapsulates pre-paid movie plans with a fixed up-front cost and number of tickets, and the ability to purchase “extra” tickets on credit at a pre-determined cost.

In addition to the other specifications included in the UML diagram, the MoviePlan class must comply with the following specifications.

Attributes

APPROVED_PLAN_COSTS contains the range of allowable plan costs (as determined by the company PayTex). Valid plan costs must be in the interval [0.00, 200.00]. Similarly, APPROVED_MOVIE_COSTS contains the range of allowable ticket costs (which, though not relevant for MoviePlan objects is relevant for other plans). Valid ticket costs must be in the interval [0.00, 25.00].

The attributes prepaid and punches contain the number of prepaid tickets in the plan and the number of pre-paid tickets used to-date (which must be 0 initially).

The attribute numberPurchased contains the number of “extra” movies that have been purchased to-date (which must be 0 initially) and the attribute spent contains the amount spent to-date on “extra” movies (which must be 0.00 initially).

Constructors

The default constructor must initialize the attributes to the default values as follows: the name must be Movie Plan, the number of pre-paid tickets must be 5, the plan cost must be $50.00, and the cost per “extra” movie must be $15.00.

The explicit value constructor must initialize the attributes in the obvious way, with a few exceptions. The plan cost attribute must be assigned the value in APPROVED_PLAN_COSTS that is closest to the parameter planCost and the movie cost attribute must be assigned the value in APPROVED_MOVIE_COSTS that is closest to the parameter movieCost.

costOfPurchasedMovie()

Must return the cost of a purchased (i.e., not pre-paid) movie.

Note: The use of the term “purchased” in the name of this method is not intended to convey the past tense (i.e., it does not imply that the movie was purchased in the past). This method could just as easily have been named costOfPurchasingAMovie().

costToDate()

Must return the cost-to-date of the plan (i.e., the sum of the plan cost and the amount spent to-date on purchased/“extra” movies). So, for example, if the plan cost $100.00, all of the pre-paid movies have been used, and one “extra” movie has been purchased at a price of $12.50 then this method must return 112.50.

getCategory()

Must return the current Category for the plan based on the cost per movie (to-date). For example, if the cost per movie is currently $7.00 then this method must return the INEXPENSIVE Category.

If the cost per movie is undefined then this method must throw an IllegalStateException.

getCostOfNextMovie()

Must return a String representation of the cost of the next movie. If the plan still has punches then this method must return “Free”. Otherwise, it must return the cost of a purchased movie (preceded by a dollar sign, in a field of width 6, with 2 digits to the right of the decimal point).

getCostPerMovie()

If the number of movies seen to-date is 0 it must throw an IllegalStateException (since the cost per movie is undefined when no movies have been seen). Otherwise, it must return the cost-to-date divided by the number of movies seen to-date.

numberPurchased()

Must return the number of movies that have been purchased to-date (which does not include the number of pre-paid movies that have been seen).

numberSeen()

Must return the number of movies that have been seen (whether pre-paid or purchased) to-date.

remainingPrepaid()

Must return the number of unused pre-paid tickets.

spent()

Must return the amount of money that has been spent on purchased movies (which does not include the plan cost).

toString()

Must return a String representation of the plan. The String must be tab-delimited and include four items (in order): the name, the cost per movie (preceded by a dollar sign in a field of width 6, with 2 digits to the right of the decimal point), the String representation of the current Category, and the cost of the next movie (formatted as described above).

If the cost per movie is undefined, then this method must return: the name, followed by two tabs, followed by the String literal “Unused”, followed by the cost of the next movie (formatted as described above)

use()

The use() method is called when a user wants to “see” a movie. It must adjust the number of punches, the amount spent, and/or the number purchased (as appropriate, depending on whether there are or aren’t unused punches).

Since it is always possible to “see” a movie under this plan, it must always return true.

An Example

A MoviePlan with the attributes (“A”, 2, 20.00, 12.50) would have the following costs per movie.

The LimitedPlan Class

The LimitedPlan class is a specialization of the MoviePlan class in which there is a limit on the amount of money that can be spent on credit.

In addition to the other specifications included in the UML diagram, the LimitedPlan class must comply with the following specifications.

Attributes

The creditLimit attribute must contain the limit on the amount of money that can be spent on credit.

Constructors

The default constructor must initialize the name to “Limited Plan”, the number of pre-paid tickets to 5, the plan cost to $50.00, the cost of purchased tickets to $15.00, and the credit limit to $100.00

The 3-parameter constructor is used to construct “pre-paid only” plans. To that end, it must initialize the cost of purchased tickets to the maximum possible value, and the credit limit to $0.00.

getCostOfNextMovie()

Must return a String representation of the cost of the next movie. If the plan is unusable (i.e., has no available punches and insufficient credit to purchase a ticket) then it must return “N/A”. Otherwise, it must exhibit the same behavior as a MoviePlan.

use()

The use() method is called when a user wants to “see” a movie. It must return false if the plan is unusable (as described above). Otherwise, it must exhibit the same behavior as a MoviePlan.

An Example

A LimitedPlan with the attributes (“B”, 2, 25.00, 15.00, 30.00) would have the following costs per movie.

The TieredPlan Class

The TieredPlan class is a specialization of a MoviePlan in which there is a special initial tier of purchases (at a different price from ordinary purchases).

In addition to the other specifications included in the UML diagram, the TieredPlan class must comply with the following specifications.

Attributes

The tierLimit is the number of tickets in the initial group of tickets. The tierCost attribute must contain the cost (per movie) of the initial group of purchased tickets.

Constructors

The default constructor must initialize the name to “Tiered Plan”, the number of pre-paid tickets to 5, the plan cost to $100.00, the normal purchase price to $10.00, the number of tickets in the initial group to 5, and the price of the initial purchases to $5.50.

The explicit value constructor must initialize the attributes in the obvious way, with a few exceptions. The plan cost attribute must be assigned the value in APPROVED_PLAN_COSTS that is closest to the parameter planCost, and the movie cost and tier cost attributes must be assigned the value in APPROVED_MOVIE_COSTS that are closest to the parameters movieCost and tierCost, respectively.

costOfPurchasedMovie()

Must return the cost of a purchased (i.e., not pre-paid) movie. Note that the value returned by this method will depend on the number of movies that have been purchased (because of the two price tiers).

An Example

A TieredPlan with the attributes (“C”, 2, 30.00, 12.50, 2, 7.50) would have the following costs per movie.

The PlanUtilities Class

The PlanUtilities class is a utility class that can be used to perform operations on MoviePlan objects.

In addition to the other specifications included in the UML diagram, the PlanUtilities class must comply with the following specifications.

findBestPlan()

Must return the least expensive MoviePlan (among those passed to it) based on each plan’s current cost-per-movie.

This method must account for several special situations:

1. In the event of a tie, it must return the MoviePlan that appears earliest in the argument list.
2. Any null parameters must be ignored.
3. It must return null if all of the parameters are null.
4. It must return null if there are 0 parameters.
5. It must ignore parameters that have an undefined cost-per-movie.
6. It must return null if all of the parameters have an undefined cost-per-movie.

Submission and Grading

You must submit complete implementations of all classes/enums, as well as JUnit tests for each class/enum.

For full credit your submission must satisfy three conditions:

• The classes/enums must pass all of the student-provided JUnit tests.
• The student-provided unit tests must achieve 100% method, statement, and branch coverage of the classes/enums.
• The classes/enums must pass all of the instructor-provided correctness tests.

Grading

For all three parts, you may submit up to 10 times without penalty. Additional submissions (if any) will receive a penalty of 1 point each. Be sure to use all the development tools offline: Checkstyle, JUnit, coverage analysis, and the debugger.

The code reviews are worth 0 additional points this time. However, points may be deducted if your code is difficult to understand. For example: confusing variable names, too few or too many comments, etc.

Hints and Suggestions

In addition to the information above, you might find the following information helpful.

Recommended Process

You are strongly encouraged to use test-driven development (TDD) (i.e., to develop the tests for a class/method before developing the class/method itself). To facilitate that process, stubbed-out versions of all of the classes/enums are available in p4-stubs.zip .

Whether or not you use TDD, you should work on the classes/enums one at a time, in the following order:

1. The Interval class and associated JUnit tests.
2. The Category class and associated JUnit tests.
3. The MoviePlan class and associated JUnit tests.
4. The LimitedPlan class and associated JUnit tests.
5. The TieredPlan class and associated JUnit tests.
6. The PlanUtilities class and associated JUnit tests.

After that, you should perform system testing using the UsageSummarizer and Planalyzer classes.

Getting 100% Coverage

To get 100% coverage of enums and utility classes, you need to use some “tricks”. For more information, see the following EclEmma help page (which also explains how to run an entire test suite).

Questions to Think About

The following question will help you understand the material from this assignment (and from earlier in the semester). You do not have to submit your answers, but you should make sure that you can answer them.

1. The findBestPlan() method in the PlanUtilities can be passed a variable number of parameters. From the invoker's standpoint, what is the advantage of using a formal parameter of MoviePlan... rather than a formal parameter of MoviePlan[]?
2. Each plan in the Planalyzer application is declared to be a MoviePlan object but some are instantiated as other objects. Why does the code compile?
3. Given the signature of the findBestPlan() method, would the following fragment compile?

   LimitedPlan limited;
   TieredPlan  tiered;
   MoviePlan   best;
   
   limited = new LimitedPlan();
   tiered  = new TieredPlan();
   
   best = PlanUtilities.findBestPlan(tiered, limited);
   

4. Suppose the following methods were added to the PlanUtilities class:

   public static void printPlanInfo(MoviePlan plan)
   {
     System.out.println("Movie Plan");
     System.out.println(plan.toString());
   }
   
   public static void printPlanInfo(LimitedPlan plan)
   {
     System.out.println("Tiered Plan");
     System.out.println(plan.toString());
   }
   
   public static void printPlanInfo(TieredPlan plan)
   {
     System.out.println("Tiered Plan");
     System.out.println(plan.toString());
   }
   

   What would be printed by the following fragment?

   MoviePlan    a, b, c;
   LimitedPlan  d;
   TieredPlan   e;
   
   
   a = new MoviePlan();
   a.use();
   
   b = new LimitedPlan("Limited Plan", 1, 15.00);
   b.use();
   
   c = new TieredPlan();
   c.use();
   
   d = new LimitedPlan("Limited Plan", 1, 15.00);
   d.use();
   
   e = new TieredPlan();
   e.use();
   
   PlanUtilities.printPlanInfo(a);
   PlanUtilities.printPlanInfo(b);
   PlanUtilities.printPlanInfo(c);
   PlanUtilities.printPlanInfo(d);
   PlanUtilities.printPlanInfo(e);
   

4.1 - Plans

Plans

classDiagram
class MoviePlan:::whitebg
MoviePlan: -double movieCost {readOnly}
MoviePlan: -double planCost {readOnly}
MoviePlan: -int prepaid {readOnly}
MoviePlan: -String name {readOnly}
MoviePlan: -double spent
MoviePlan: -int numberPurchased
MoviePlan: -int punches
MoviePlan: #Interval APPROVED_MOVIE_COSTS {readOnly}$
MoviePlan: #Interval APPROVED_PLAN_COSTS {readOnly}$
MoviePlan: +MoviePlan()
MoviePlan: +MoviePlan(name String, prepaid int, planCost double, movieCost double)
MoviePlan: #costOfPurchasedMovie() double
MoviePlan: #costToDate() double
MoviePlan: +getCategory() Category {exceptions=IllegalStateException}
MoviePlan: +getCostOfNextMovie() String
MoviePlan: +getCostPerMovie() double {exceptions=IllegalStateException}
MoviePlan: +getName() String
MoviePlan: +getPlanCost() double
MoviePlan: #numberPurchased() int
MoviePlan: #numberSeen() int
MoviePlan: #remainingPrepaid() int
MoviePlan: #spent() double
MoviePlan: +toString() String
MoviePlan: +use() boolean
class TieredPlan:::whitebg
TieredPlan: -double tierCost {readOnly}
TieredPlan: -int tierLimit {readOnly}
TieredPlan: +TieredPlan()
TieredPlan: +TieredPlan(name String, prepaid int, planCost double, movieCost double, tierLimit int, tierCost double)
TieredPlan: #costOfPurchasedMovie() double
MoviePlan<|--TieredPlan
class LimitedPlan:::whitebg
LimitedPlan: -double creditLimit {readOnly}
LimitedPlan: +LimitedPlan()
LimitedPlan: +LimitedPlan(name String, int prepaid, planCost double)
LimitedPlan: +LimitedPlan(name String, prepaid int, planCost double, movieCost double, creditLimit double)
LimitedPlan: +getCostOfNextMovie() String
LimitedPlan: +use() boolean
MoviePlan<|--LimitedPlan

4.2 - Support

Support

classDiagram
class Interval:::whitebg
<<immutable>> Interval
Interval: -double left {readOnly}
Interval: -double right {readOnly}
Interval: -boolean leftClosed {readOnly}
Interval: -boolean rightClosed {readOnly}
Interval: +Interval(original Interval)
Interval: +Interval(leftSymbol char, left double, right double, rightSymbol char) {exceptions = IllegalArgumentException}
Interval: +contains(value double) boolean
Interval: +closestTo(value double) double
Interval: +toString() String
Interval: +toString(formatString String) String
class Category:::whitebg
<<enumeration>> Category
Category: -Interval interval {readOnly}
Category: -String description {readOnly}
Category: -String symbol {readOnly}
Category: -Category(description String, symbol String, interval Interval)
Category: +getCategoryFor(price double)$ Category
Category: +getDescription() String
Category: +getSymbol() String
Category: +toString() String
Category: BARGAIN
Category: INEXPENSIVE
Category: MODERATE
Category: EXPENSIVE
Category: OUTRAGEOUS
class PlanUtilities:::whitebg
<<utility>> PlanUtilities
PlanUtilities: +findBestPlan(plans MoviePlan...)$ MoviePlan

5 - Project 5 - Swarm!

Introduction

SwarmWORKS is a fictitious video game company that is developing an insect-themed game for distribution on multiple platforms. The game will involve dodging swarming insects while collecting flowers on a 2D playing field. As part of the design process, the company has decided to develop a swarm simulator that can be used to experiment with models of insect behavior. Portions of the simulator code may be incorporated into the final product, but the main objective is to develop a platform for testing design ideas.

The completed application will read a user-editable text file specifying the contents of the simulation then execute the simulation until the user exits.

Provided Code

It should not be necessary to modify any of these classes. Please do not make any changes, because your code will be graded using the original files.

StdDraw, SwarmDriver, and SwarmConstants

All of the graphics for this application will be handled by the StdDraw library developed by Robert Sedgewick and Kevin Wayne at Princeton University. This library is not particularly powerful or full-featured, but it makes it easier to develop simple graphical applications in Java.

SwarmDriver.java has been developed to load the simulation data, initialize the drawing window, and handle the main simulation loop.

It is your responsibility to develop a Simulation class that is able to read the configuration file passed to the Simulation constructor. This class must also provide an “update” method that will be responsible for updating the state of all simulation elements at each time step, and a “draw” method that will be responsible for re-drawing simulation elements after they have been updated. Your code will be tested using the driver above.

SwarmConstants.java contains a set of constant values such as the window size, the simulation update rate, etc.

Point, Pose, and PoseUtils

It will be necessary to store and update the positions and headings of simulated insects in order to model their behavior. This is complicated by the requirement that the simulation environment wraps at the edges. In other words, when an object disappears off one edge of the window, it should reappear in the corresponding location at the opposite edge.

The following classes will be helpful for maintaining and updating insect locations:

1. Point.java - The Point class is an encapsulation of a two-dimensional location.
2. Pose.java - The Pose class is a subclass of Point that includes heading information.
3. PoseUtils.java - This class contains utility methods for updating Poses so that the edges of the window are handled correctly.

Simulation Specification

A list of simulation elements will be provided to the application in a text file. The first line of the file will contain a single integer describing the total number of elements encoded in the file. The second line will be blank. The remainder of the file will consist of entries describing the simulation elements.

The first line of each entry will contain an element type identifier. Subsequent lines will contain information appropriate to that element type. Where there are multiple values on a single line, each value will be separated by a single space. There will be a single blank line after each entry, including the last. You may assume that the file will be free of defects.

The remainder of this section will describe each simulation element along with the associated file entry formats.

Bees

Within the simulation, bees are represented as small isosceles triangles that move forward at a fixed speed while making random heading changes.

Bee File Format

File entries for bees have the following format:

bee
RED GREEN BLUE SPEED ANGLE_STD

The RED, GREEN and BLUE values will be integers in the range 0-255 indicating the values of the indicated color channels.

The SPEED value is a double indicating the bee’s forward speed. The speed is provided in units of pixels/time step.

The value of ANGLE_STD specifies the amount of randomness in the bee’s heading. A value of 0 indicates that the bee’s path will be perfectly straight. Larger values will lead to more random trajectories. Specifically, the bee’s heading should be updated with values drawn from a Gaussian (i.e., normal) distribution with a mean of zero and a standard deviation determined by the value of ANGLE_STD.

Bee Appearance

Bees should be drawn as isosceles triangles with a base width of 5.0 pixels and a height of 10.0 pixels. The PoseUtils.drawPoseAsTriangle method provides the necessary functionality for drawing bees. Bees (and all other simulation elements) should be drawn using the default StdDraw pen radius of .002.

Bee Behavior

The poses of all bees should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the interval [0, 2π).

The following pseudocode describes the behavior that a bee must exhibit on each time step:

Randomly update the heading:
       x <- A random number drawn from the appropriate Gaussian distribution.
       heading <- heading + x
Move forward SPEED units.

where the leftward pointing arrows <- indicate assignment.

Bee Example

Here is a sample configuration file specifying two bees: a red bee that moves slowly and erratically, and a black bee that moves more quickly with no random changes to its heading.

2

bee
255 0 0 1.0 0.3

bee
0 0 0 3.0 0.0

This video shows a possible simulation run that might result from processing this file:

Note that this video was created after modifying SwarmConstants.java to specify a smaller window size. Using the default settings, you should expect your bees to appear somewhat smaller relative to the window.

Bee examples

We have captured several examples of the result of drawing a Bee to help support your understanding of the Point and Pose coordinate system. Take a look at the Bee Gallery.

Swarms

A swarm is a collection of bees with a single queen and an arbitrary number of drones. The queen moves randomly and the drones follow the queen.

Swarm File Format

File entries for swarms have the following format:

swarm
NUM_DRONES
RED GREEN BLUE SPEED ANGLE_STD
RED GREEN BLUE SPEED ANGLE_STD MAX_TURN_RATE

The NUM_DRONES value will be an integer indicating the number of drones in the swarm.

The next line specifies the characteristics of the queen. The format here is the same as the bee format described above.

The final line specifies the characteristics of the individual drones. In addition to the four entries required to specify a bee, drones have an additional attribute, MAX_TURN_RATE, that governs how quickly they are able to turn in order to track the movements of the queen. This will be a double specified in radians per time step.

Swarm Behavior

The poses of all bees in the swarm should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the range [0, 2π).

The following pseudocode describes the behavior that a swarm must exhibit on each time step:

 Randomly update the heading of the queen.
 Move the queen forward according to her speed.
 For each drone in the swarm:
     Turn toward the queen at the maximum rate.
     Perform a random update to the heading.
     Move forward according to the drone's speed.

Swarm Example

Here is a sample configuration file specifying a single swarm composed of a red queen and three black drones:

1

swarm
3
255 0 0 2.0 0.2
0 0 0 2.0 0.2 0.07

This video shows a possible simulation run that might result from processing this file:

For the sake of simplicity, this example only includes one swarm. It should be possible to simulate multiple swarms simultaneously.

Beetles

Beetles differ from bees in both their appearance and their motion pattern. On most updates beetles move straight ahead without changing their heading. They occasionally select a new random heading.

Beetle File Format

File entries for beetles have the following format:

beetle
RED GREEN BLUE SPEED TURN_PROBABILITY

The values for RED, GREEN, BLUE and SPEED have the same meaning for beetles as they do for bees. TURN_PROBABILITY will be a double between 0.0 and 1.0 indicating the probability that the beetle will change its heading on a given time step. If the value is 0, then the beetle never turns. If the value is 1, the beetle selects a new random heading on each update.

Beetle Appearance

Beetles should be drawn as filled circles with a radius of 6.0 pixels.

Beetle Behavior

The pose of all beetles should be generated randomly at the start of the simulation. Positions should be selected uniformly from the entire simulation window. Orientations should be drawn uniformly from the range [0, 2π).

The following pseudocode describes the behavior that a beetle must exhibit on each time step:

 With probability TURN_PROBABILITY:
     Update the heading to a randomly selected value in the interval [0, 2π).
 Move forward SPEED units.

Beetle Example

The following file describes two beetles: one blue beetle that changes direction with probability .01, and a yellow beetle that changes direction with probability .1.

2

beetle
0 0 255 1.0 .01

beetle
255 255 0 1.0 .1

This video shows a possible simulation run that might result from processing this file:

Flowers

For the purpose of this application, a “flower” is just a stationary filled polygon. This will make it possible to experiment with different flower shapes without making changes to the simulation source code.

Flower File Format

File entries for flowers have the following format:

flower
RED GREEN BLUE
NUM_POINTS
X_1 X_2 ... X_N
Y_1 Y_2 ... Y_N

The second line specifies the color of the polygon. The third line consists of a single number specifying the number of points on the boundary of the polygon. The fourth and fifth lines provide the x and y coordinates of the boundary points. The number of values in these lines will match the NUM_POINTS value.

Flower Behavior

Flowers do not change their state during updates.

Flower Example

The following file describes two flowers: one black square with its lower-left corner at (20.0, 20.0) and one blue polygon with its lower left corner at (120.0, 120.0).

2

flower
0 0 0
4
20.0 40.0 40.0 20.0
20.0 20.0 40.0 40.0

flower
0 0 255
5
120.0 140.0 140.0 130.0 120.0
120.0 120.0 140.0 150.0 140.0

This video shows the expected result of processing this file:

Part A: UML

By the first deadline you must submit a UML diagram illustrating your design. For full credit, your design must make appropriate use of the object oriented features that we have been covering in class: specialization, abstract classes, interfaces, etc. Your UML should be as complete as possible. It should show the attributes of each class as well as the signatures of all public and protected methods. It should also show the relationships between your classes.

Part of your grade for this portion of the assignment will be based on using correct UML syntax . Your UML diagram may be prepared electronically or very neatly hand-drawn and scanned.

In addition to the practice you’ve had with earlier labs, the reading in chapters 8 and 12 (esp. the CRC Card Method), find a few tips on this page associated with the Objected-Oriented Design Lab .

Your UML diagram must be submitted through Gradescope as a one-page PDF file.

Part B: Code

You must submit your finished project through Gradescope by the second deadline. The submission tests will not be able to verify that your swarm elements are updated or drawn correctly. Passing the autograder tests will only mean that your code is formatted correctly and doesn’t crash when it is executed. This makes it particularly important that you carefully test your code before submitting.

Here are some additional configuration files that you can use for testing:

• all_examples.txt - This contains all of the examples above in a single file.
• interesting.txt - A larger example.

Design and Implementation Suggestions

Working with Random Numbers

• The class java.util.Random should be used to generate pseudo-random numbers for this application. The nextDouble method returns a double selected uniformly from the interval [0, 1). This method can be used to generate initial poses by multiplying the generated values by the desired upper bound for each component of the pose.

• In order to create a block that occurs with a particular probability, you can compare the output of nextDouble to the desired probability. For example:

  if (generator.nextDouble() < 0.75) {
      // This block will execute with probability 75%
  }
  

• The java.util.Random class provides a nextGaussian method that can be used for generating pseudo-random numbers from a Gaussian distribution with mean 0.0 and standard deviation 1.0. If a different standard deviation is required, you can simply multiply the generated value by the desired standard deviation:

  // Here 10.0 is the desired standard deviation.
  double x = generator.nextGaussian() * 10.0;
  

Miscellaneous Advice

1. Make sure you understand the provided code. Take some time to look over the StdDraw library documentation as well as the other provided classes.
2. Develop with testing in mind. For example, it might be a good idea create your swarm elements with explicit value constructors first so that you can test them in isolation before worrying about file I/O.
3. Many steps in this project require the use of a random number generator. Programs with a random component can be challenging to debug because errors may occur at unpredictable intervals. This problem can be alleviated by using a single shared random number generator and setting an explicit seed value during testing.
4. Look for opportunities to use polymorphism to avoid code duplication. As always, if you find yourself copying and pasting code, there is a good chance you are doing something wrong.
5. Don’t wait until after the UML deadline to start working on your code. You can experiment with developing and testing classes even if you haven’t completely solidified your design. It will probably be easier to refactor functional code to match an improved design than it would be to start coding from scratch.

Acknowledgement: This assignment was originally designed by Prof. Nathan Sprague.

5.1 - BEES!🐝🐝😱

Bee at origin…

Missing Bee?

is missing?

Found it! 🔬

Bee at origin - ZOOMED

Annotated 🖊

Bee at origin - ZOOMED, annotated

Bee at center…

Zoomed

6 - Project 6 - TournaKit

Introduction

perspecTV is a (fictitious company) that designs, creates and markets products that provide a new perspective on television. Their products make television both more interactive and more informative. They have found that viewers of televised competitions of various kinds (including traditional sporting events, eSports, dance competitions, singing competitions, cooking competitions, poker competitions, spelling bees, etc.) are very interested in historical statistics and they are developing various software products to help satisfy that demand.

“TournaKit” is a suite of products that can be used to analyze the results of completed tournaments.

Definitions

perspecTV uses the following definitions (listed in logical, not alphabetical, order) in relation to TournaKit.

Participant

A competitor in a competition of some kind.

Matchup

A competition involving exactly two participants.

Visitor/Home

Designations for the two participants in a matchup. The visiting participant is listed first and the home participant is listed second.

Score

The number of points/runs/goals/etc. awarded to a single participant.

Point Differential

The absolute value of the difference between the visiting participant’s points and the home participant’s points.

Win/Loss/Tie

The three possible outcomes of a matchup for a particular participant. Note that, in some matchups, the participant with the higher score wins (e.g., lacrosse) while in other matchups, the participant with the lower score wins (e.g., golf).

Round

A set of matchups in which none of the participants appears more than once.

Tournament

A set of rounds.

Round Robin Tournament

A tournament in which each competitor plays multiple other competitors, regardless of whether they win, lose, or tie. A round robin tournament is said to be regular if the number of competitors (n) is even, each competitor competes in each round, and each competitor competes against each other competitor exactly once (and, hence, there are n−1 rounds).

Single Elimination Tournament

A tournament in which ties are not possible and only the winning teams in a round advance to the next round (i.e., if a team loses it is eliminated). A single elimination tournament is said to be regular if the number of competitors (n) is a power of 2 (and, hence, the number of rounds is \(log_2(n)+1\) ). Many single elimination tournaments are regular but many, especially those that involve “play-in” competitions, are not. For example, the NCAA Division I Basketball Tournament used to be regular (involving 64 competitors and 7 rounds) but now includes a “play-in” round (involving 8 competitors reduced to 4 that are added to the 60 teams that skip the “play-in” round).

Assumptions

1. You should assume that round robin tournaments are regular.
2. You must not assume that single elimination tournaments are regular.
3. You must not make any assumptions about other tournaments.

Data Files

perspecTV has provided three tournament files that you can use when running your code. They contain the results of the:

1. 2017 NCAA Division III Women’s Lacrosse Championship (Single Elimination)
   • lacrosse-women_d3_2017.set
2. 2016 Fantasy Division I Quidditch World Cup (Regular Round Robin)
   • quidditch_d1_2016.rrt
3. 2018 Disney Division Golf Championship (Regular Round Robin followed by Single Elimination)
   • golf_dd_2018.tmt

Single elimination tournaments have a file type of .set, regular round robin tournaments have a file type of .rrt, and other tournaments have a file type of .tmt. None of these files are “human readable”.

To help you test your code, they have also provided the following files:

• Lacrosse:
  • Spreadsheet
  • Visualization
• Quidditch:
  • Spreadsheet
• Golf:
  • Spreadsheet
  • Visualization of the Single Elimination Portion

Design

The design of the initial components has already been completed, and is illustrated in the following UML class diagram. Existing classes (i.e., classes that are being provided to you) are shown in (perspecTV’s trademarked) green and new classes (i.e, classes that you must write) are shown in black.

Provided Code

New Code

Existing Components

• Analyst.java
  • Stubs (including Javadoc comments) are provided for the Analyst class.
• AnalystTest.java
  • This small set of tests are sufficient to cover 100 % of a reference solution.
• tournakit.jar
  • The Participant enum, Matchup class, and Tournament, RoundRobinTournament, and SingleEliminationTournament classes have already been implemented and are provided in a .jar file:

The Matchup class

classDiagram
class Matchup
Matchup: +Matchup(visitor String, home String, visitorScore int, homeScore int)
Matchup: +getName(who Participant) String
Matchup: +getScore(who Participant) int
Matchup: +toString() String

In addition to the other specifications included in the UML diagram, this class has the following explicit values constructor that may help you write early unit tests (i.e. before you feel ready to read in a whole Tournament for testing).

• Matchup(String team1Name, String team2Name, int team1Score, int team2Score)

The Tournament Class

The getFinalMatchups() method returns an array of all of the “final” Matchup objects, regardless of the round in which they occur. This means that the the array that is returned will include every competitor in at least one Matchup (and, in some cases, in more than one Matchup). For example, consider a Tournament that has six competitors; all six play a round robin portion and then the top four competitors in the round robin portion play a single elimination portion. The getFinalMatchups() method will return an array containing the one Matchup from the final round of the single elimination portion and the Matchup objects from the last round of the round robin portion for the two teams that did not participate in the single elimination portion.

The iterator() method returns an Iterator containing all of the Matchup objects involving the given team, ending with the given Matchup. The Iterator is in “round order” (i.e., the first call to next() will return the earliest Matchup).

The previous() method returns the Matchup from the previous round (relative to the round of the given Matchup) for the given team. If there is no such Matchup then this method returns null.

The RoundRobinTournament Class

The getFinalMatchups() method of a RoundRobinTournament object returns all of the Matchup objects from the final round.

The SingleEliminationTournament Class

The getFinalMatchups() method of a SingleEliminationTournament object return an array containing one Matchup, the Matchup for the final round of the tournament.

The getFinalMatchup() method (note the lack of an “s”) is a convenience method that returns the final round of the tournament. In other words, it returns getFinalMatchups()[0].

The Judge Interface

The Judge interface describes the capabilities of classes that can be used to determine the result of a Matchup.

Detailed Specifications

In addition to the other specifications included in the UML diagram, concrete implementations of this method must comply with the following specifications.

The result(Matchup, Participant) Method

The result(Matchup, Participant) method must return 1 if the given Participant won the given Matchup, must return -1 if the given Participant lost the given Matchup, and must return 0 if the given Matchup was a tie.

The HighWins and LowWins Classes

The HighWins class is a realization of the Judge interface that awards the win to the participant with the highest score. Both lacrosse and quidditch are examples of competitions that use this kind of Judge.

The LowWins class is a realization of the Judge interface that awards the win to the participant with the lowest score. Golf is an example of a competition that uses this kind of Judge.

The Record Class

The Record class is an encapsulation of a competitor’s performance in a tournament.

Detailed Specifications

In addition to the other specifications included in the UML diagram, this class must comply with the following specifications.

Default Constructor

The default constructor must initialize all attributes to 0.

Methods

The increaseLosses(), increaseWins(), and increaseTies() methods must increase the associated attribute by 1.

The toString() method must return a String representation of the record including the wins, losses, and ties (in that order), delimited by " - " (i.e., a dash with a space on each side). Each value must be right-justified in a field of width three.

The Analyst Class

The Analyst class is a utility class for performing calculations on tournaments.

Detailed Specifications

In addition to the other specifications included in the UML diagram, this class must comply with the following specifications. Note that when a specification says that a method must be recursive, it must be recursive in a meaningful/non-trivial way (i.e., it must use recursion to solve the problem).

The buildSchedule(RoundRobinTournament) Method

The buildSchedule(RoundRobinTournament) method is the publicly visible method that builds a schedule containing each competitor in a RoundRobinTournament (the key of the Map) and a List of all of its opponents (the value of the Map). The opponents must be included in the List in the order in which the competitions occurred (i.e., with the earliest round first).

It must call a private method that does most of the work. This private method need not be recursive, though it can be. In other words, because of the structure of RoundRobinTournament objects, the schedule can be built iteratively, without recursion. Keep in mind that a RoundRobinTournament has multiple matchups in each round, including the final round.

The buildSchedule(SingleEliminationTournament) Method

The buildSchedule(SingleEliminationTournament) method is the publicly visible method that builds a schedule containing each competitor in a SingleEliminationTournament (the key of the Map) and an ordered List of all of its opponents (the value of the Map). It must call a private method that does most of the work. This private method must be recursive.

The calculateRecords(Tournament, Judge) Method

The calculateRecords(Tournament, Judge) method is the publicly visible method for calculating the records of all competitors in a Tournament. It must call a private method that does most of the work. This private method must be recursive.

The totalPointDifferential(Tournament, Matchup, String) Method

The totalPointDifferential(Tournament, Matchup, String) method is the publicly visible method for calculating the total point differential in all games involving the given team, ending with the given Matchup. This method need not be recursive. In other words, it is possible (indeed relatively easy) to calculate the point differential for a particular team iteratively, without recursion.

The totalPointDifferential(SingleEliminationTournament) Method

The totalPointDifferential(SingleEliminationTournament) method is the publicly visible method for calculating the total point differential of all matchups in a SingleEliminationTournament. It must call a private method that does most of the work. This private method must be recursive.

Submission and Grading

You must submit all of the classes/interfaces you implement. You must not submit JUnit test suites.

For Part A, submit only Judge.java, HighWins.java, LowWins.java, and Record.java. We recommend you complete this part at least one week before the deadline.

For Part B, submit only Analyst.java. Gradescope will compile your Analyst with the reference solutions for Judge, HighWins, LowWins, and Record.

At this point in the semester, you should be able to both implement and test your code. Hence, it is your responsibility to submit correct code. Hence, though you do not need to submit any tests, you will almost certainly need to write tests.

One way to think about this is that perspecTV does not have testers (either in-house alpha testers or external beta testers). The code you submit will be given to clients to use in a production environment. If the code contains defects, the clients will not provide details, they will just stop using the product (which will cost perspecTV revenue). If you find yourself in a situation in which your code passes all of your tests but the client (i.e., Gradescope) says it didn’t work properly, you will need to re-think your tests.

Your grade will be based on the “official” tests your code passes/fails (though, as in the past, your code must not contain any style defects). Specifically:

You may submit up to 10 times without penalty. Additional submissions (if any) will receive a penalty of 1 point each. Be sure to use all the development tools offline: Checkstyle, JUnit, coverage analysis, and the debugger.

The code reviews are worth 0 additional points. However, points may be deducted if your code is difficult to understand. For example: confusing variable names, too few or too many comments, etc.

Hints and Suggestions

A Recommended Process

You should certainly start by implementing and testing the Judge interface, HighWins and LowWins classes, and Record. After that, you should probably work on the methods in the Analyst class in increasing level of difficulty.

The totalPointDifferential(Tournament, Matchup, String) method is the easiest in the Analyst class. It needn’t involve recursion.

The buildSchedule(RoundRobinTournament) method is the next-easiest (because you need only consider regular round robin tournaments). It also needn’t involve recursion, though you need to think carefully about how you can use iteration because the last round in such a tournament includes multiple Matchup objects.

The totalPointDifferential(SingleEliminationTournament) method does involve recursion (i.e., the private method it calls must use recursion), but the recursion is fairly straightforward (i.e., similar to many examples that you’ve seen).

The buildSchedule(SingleEliminationTournament) method must work backwards from the last Matchup to construct a complete schedule. The base case should be fairly obvious, and you should also be able to figure out how to refine the other cases fairly quickly. What may take some time is figuring out how to keep track of the results.

The calculateRecords(Tournament, Judge) method is pretty challenging because it must work on any Tournament. Hence, though the base case is pretty obvious, you will need to spend time thinking about how to refine the other cases. Also, you will need to think carefully about how to avoid “double counting”.

Using Your Code

You should test your code using JUnit. However, you may also want to write a small application or two just because it is sometimes more satisfying than just writing components. For example, the following application can be used to print the records of each team in the lacrosse championship.

import java.util.*;

public class Results
{
  public static void main(String[] args) throws Exception
  {
    HashMap<String, Record>     records;
    SingleEliminationTournament lacrosse;

    lacrosse = SingleEliminationTournament.read("lacrosse-women_d3_2017.set");

    records = Analyst.calculateRecords(lacrosse, new HighWins());

    System.out.println(lacrosse.getDescription());
    for (String team: records.keySet())
    {
      Record record = records.get(team);
      System.out.printf("%25s:\t%s\n", team, record);
    }
  }
}

If you’re actually interested in these kinds of analyses, you might also want to write an application that compares the point differential for all of the matchups in the lacrosse tournament with the point differential for the winner in order to evaluate their “dominance” in the tournament.