We extend, and finalize, our memory model for Java programs, and discuss garbage collection. We use our memory model to introduce Java programs that use mutation and circular data structures. We discuss the effects of mutation and circular data structure to our programs covering stack overflow exceptions and equality between objects.

We introduce class invariants and use pre-conditions and post-conditions along with invariants to reason about Java programs that use mutation.

  1. Write the names of the two types of memory used by the JVM.
  2. Given a Java class with a main method, draw a diagram to show the state of the JVM's memory.
  3. Write a Java program that can cause a stack overflow exception.
  4. Given a diagram that shows the memory state of the JVM, mark the elements that will be removed by a garbage collection cycle.
  5. Given a specification for cyclic data, write a Java class that implements the specification.
  6. Given a set of Java classes, verify object state by writing JUnit tests.
  7. Given a Java class with mutable state, write pre-conditions for each method.
  8. Given a Java class with mutable state, write post-conditions for each method.
  9. Given a Java class with mutable state, write a class invariant.
  10. Given two Java classes, show if one class is a behavioral subtype of the other.

  • DUE DATE: June 23rd @ 12:00pm (NOON)

Submission Criteria

Repository Contents

Your repositories must contain only the following

  1. pom.xml file and
  2. src folder with appropriate sub-folders with your code and test code only.

Code Criteria

  1. Your solution for each problem should be in its own package. The package names should follow this naming convention edu.neu.ccs.cs5004.assignmentN.problemM where you replace N with the assignment number and M with the problem number, e.g., all your code for problem 1 for this assignment must be in a package named edu.neu.ccs.cs5004.assignment6.problem1.
  2. Your project should successfully build using maven generating all the default reports.
  3. Your Javadoc generation should complete with no errors or warnings.
  4. Your Checkstyle report must have no violations.
  5. Your JaCoCo report must indicate 75% code coverage per package for "Branches" and "Instructions" or more.
  6. Your FindBugs report must have no violations (except for violations categorized as PERFORMANCE or SECURITY, you can ignore those).
  7. Your PMD report should have no violations.

Binary Search Trees with mutation

You asked to design a program in Java to implement the following Binary Search Tree (BST) data type.

  • create() : BST - creates an empty BST
  • add(Integer n) : void - adds the element n into the BST. If the element we are trying to add is already in the BST, the BST remains unchanged.
  • remove(Integer n) : void - removes the element n from the BST. If the element is not present in the BST then the BST remains unchanged.
  • contains(Integer n) : Boolean - returns true if the element n is in the BST and false otherwise.
  • size() : Integer - returns the total number of elements in the BST

Queue with mutation

You are asked to design a program in Java to implement the following first in, first out (FIFO) Queue data type.

  • create() : Queue - creates an empty Queue
  • isEmpty() : Boolean - returns true of the Queue is the empty one and false otherwise
  • enqueue(String n) : void - adds the element n into the Queue.
  • dequeue() : String - removes the oldest element from the Queue and returns it to the caller.
  • remove(String n) : void - removes the element n from the Queue. If the element is not in the Queue the Queue remains unchanged. After the removal of an element, the remaining elements should maintain their order, e.g., given a queue ("a","b","c","d") after removing "c" the Queue's behavior should be identical to the Queue ("a","b","d")
  • contains(String n) : Boolean - returns true if the element n is in the Queue and false otherwise.
  • size() : Integer - returns the total number of elements in the Queue

Bounded Queue

A bounded queue is similar to a normal queue in that it has the same operations. A bounded queue however has a maximum capacity of elements that it can hold. Design the bounded queue data type with the following operations

  • create(Integer capacity) : BoundedQueue - creates an empty BoundedQueue with the given capacity
  • isEmpty() : Boolean - returns true of the BoundedQueue is the empty one and false otherwise
  • enqueue(String n) : void - adds the element n into the BoundedQueue. In the case that your BoundedQueue has reached capacity and enqueue is called the new element should replace the oldest element in the BoundedQueue.
  • dequeue() : String - removes the oldest element from the BoundedQueue and returns it to the caller.
  • remove(String n) : void - removes the element n from the BoundedQueue. If the element is not in the BoundedQueue the BoundedQueue remains unchanged. After the removal of an element, the remaining elements should maintain their order, e.g., given a queue ("a","b","c","d") after removing "c" the BoundedQueue's behavior should be identical to the BoundedQueue ("a","b","d")
  • contains(String n) : Boolean - returns true if the element n is in the BoundedQueue and false otherwise.
  • size() : Integer - returns the total number of elements in the BoundedQueue
  • available() : Integer - returns the total number of available slots (empty positions in our bounded queue).