Assignment 2

Due Date : 2/6 @ 11:59pm

Instructions

Each of you should have a repository in CCIS’s GitHub with the name assignment2-ccisLogin. Use this repository and add all your work there. In order to clone the repositories from CCIS GitHub to your machine (or watch this video video instructions):

  1. Sign in to GitHub.

  2. On your CCIS GitHub home page your Github Handle should appear on the left as a button/drop down menu. Click that button and from the drop down menu select cs8674sp15-seattle. The CCIS GitHub page will then navigate to the class' web page and to the contents that is available to you.

  3. On the right you should be able to see all repositories to which you have been given access. Find the repository whose name matches the pattern assignment2-ccisLogin, where ccisLogin is your CCIS login name, e.g,assignment2-john123, and click on it.

  4. On the repositories home page look at the bottom right hand corner for a button with the text Clone in Desktop. By clicking on this button your browser will launch the GitHub client that we installed in Lab1 and ask for a location on your drive to store the repository.

    If you are not using the GitHub client the clone URL is located above the Clone in Desktop button. Copy the URL and issue the following command on your shell git clone URL.

  5. Create a file and save it under the folder on your drive that you selected in the preceding step.

Remember to push your changes to the CCIS GitHub repository often.

Rules

  1. You are not allowed to use any JDK APIs other than java.lang.
  2. You are not allowed to use Java arrays.
  3. You are not allowed to use Java lists of any kind.
  4. For any Java class that contains methods you are expected to provide tests using JUnit.
  5. For any Java class you are expected to provide valid Javadoc documentation. This means that running Javadoc on your your source code should successfully compile and generate documentation in HTML.
  6. For any images, e.g., for Class Diagrams, you are expected to provide a PDF version of the image.

Problem 1

All Java source code that is part of your solution to this problem must reside inside a java package with the name edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem1

You are asked to provide the design and implementation in Java for a Set, as in the mathematical notion of a set. Here is the specification given to you describing all the operations on Set. The specification uses

Operation Specification Comments

EmptySet(): Set
EmptySet() = {} 
                

Creates an empty set.

isEmpty() : boolean
{}.isEmpty()          = true

{1,2,...}.isEmpty() = false 
  • Calling isEmpty() on an empty set must return true.
  • Calling isEmpty() on a non empty set must return false.

add(Integer n) : Set
{}.add(n)   = {n}

aSet.add(n) = aSet,        
    if aSet.contains(n) = true 

aSet.add(n) = {n} ∪ aSet,  
    if aSet.contains(n) = false 
                
  • Calling add(n) on the empty set adds the new element n to the empty set.
  • alling add(n) on a non-empty set aSet returns the same set aSet if n is already a member of aSet.
  • Calling add(n) on a non-empty set aSet returns the union of aSet with the set {n}.

contains(Integer n) : boolean
{}.contains(n)   = false

aSet.contains(n) = true,
    if n ∈ aSet 

aSet.add(n)      = false,
    if m ∉ aSet 
                
  • Calling contains(n) on the empty set returns false.
  • Calling contains(n) on a non-empty set aSet returns true if n is a in the set aSet.
  • Calling contains(n) on a non-empty set aSet returns false if n is not in aSet

size() : Integer
{}.size()   = 0
aSet.size() = n,  where |aSet| = n 
                
  • Calling size() on the empty set returns 0.
  • Calling size() on a non-empty set aSet returns the number of elements in aSet

You are also required to provide the following methods for Sets

  1. equals(Object o) should return true if and only if the two sets have the same number of elements and for each element in this the same element exists in o and for each element in o also exists in this.
  2. hashCode() ensure that your implementation of hashCode() and equals() satisfies the contracts for both methods.

Problem 2

All Java source code that is part of your solution to this problem must reside inside a java package with the name edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem2

You are asked to provide the design and implementation in Java of a Bag. A Bag is a container for a group of data, in our case a Bag can hold Strings. A Bag can contain duplicates. The elements of a Bag have no order. Here is the specification given to you describing all operations on Bags. The specification uses

Operation Specification Comments

EmptyBag() : Bag
EmptyBag() = []
                

Creates an empty bag.

isEmpty() : boolean
[].isEmpty()   = true 

aBag.isEmpty() = false, 
    if aBag ≠ []
                
  • Calling isEmpty() on the empty bag returns true.
  • Calling isEmpty() on a non-empty bag aBag returns false.

size() : Integer
[].size()   = 0 

aBag.size() = n,
    where |aBag| = n
                
  • Calling size() on the empty bag returns 0.
  • Calling size() on a non-empty bag aBag returns the number of elements in aBag.

add(String s) : Bag
[].add(s)   = [s] 

aBag.add(s) = anotherBag,  
    where anotherBag = s ++ aBag
                
  • Calling add(s) on the empty bag returns a new bag that holds only one element s.
  • Calling add(s) on a non-empty bag aBag returns a new bag anotherBag that contains all the elements of aBag plus the newly added element s.

contains(String s) : boolean
[].contains(s) = false 

aBag.contains(s) = true,  
   if aBag = s ++ anotherBag                


aBag.contains(s) = anotherBag.contains(s),  
   if aBag = x ++ anotherBag, and, 
   x ≠ s
                
  • Calling contains(s) on an empty bag returns false
  • Calling contains(s) on a non-empty bag returns true if the element is in the bag
  • Calling contains(s) on a non-empty bag returns false if the element is not in the bag

You are also required to provide the following methods for Bags

  1. equals(Object o) that returns true if the two bags have the same exact elements; exactly the same String and exactly the same number of times in the bag (if there are duplicates). Remember that the order of elements in the bag does not matter.
  2. hashCode() ensure that your implementation of hashCode() and equals() satisfies the contracts for both methods.

Now that you have completed your implementation of Bag, your users would like you to provide the design and Java implementation of a Bounded Bag. A Bounded Bag is very similar to a normal Bag but a Bounded Bag has a maximum number of elements that it can hold. We call this maximum the Bag's capacity. Here is the specification of Bounded Bag

Operation Specification Comments

EmptyBoundedBag(Integer max) : BoundedBag
EmptyBoundedBag(n) = []
                

Creates an empty bounded bag that can hold at most n elements.

isEmpty() : boolean
Same as Bag's specification for this method. 
                

Same as Bag's comments for this method.

size() : Integer
Same as Bag's specification for this method. 
                
Same as Bag's comments for this method.

add(String s) : Bag
aBBag.add(s) = anotherBBag,   
    if aBBag.size() < max 
    and anotherBBag = s ++ aBBag


aBBag.add(s) = error,   
    if aBBag.size() ≥ max 
                
  • Calling add(s) on a bounded bag aBBag that has not yet reached its capacity returns a new bounded bag anotherBBag that contains all the elements of aBBag plus the newly added element s.
  • Calling add(s) on a bounded bag aBBag that has reached its capacity throws an error.

contains(String s) : boolean
Same as Bag's specification for this method. 
                
Same as Bag's comments for this method.

isFull() : boolean
aBBag.isFull() = true, 
    if aBBag.size() = capacity                    

aBBag.isFull() = false, 
    if aBBag.size() < capacity                    
                
  • Calling isFull() on a bounded bag that has reached capacity returns true.
  • Calling isFull() on a bounded bag that has not reached capacity returns false

You are also required to provide implementations for the methods equals(Object o) and hashCode(). The requirements for these two methods are the same as those for Bag.

Problem 3

All Java source code that is part of your solution to this problem must reside inside a java package with the name edu.neu.ccs.cs8674.sp15.seattle.assignment2.problem3

One of your team mates would like your help with one of his projects. He was given the following specification for a Queue and is asking you to provide a design and Java implementation. This Queue holds data in a first in first out (FIFO) order, thus the order by which the elements are added into the Queue matters. The specification uses

Operation Specification Comments

EmptyQueue() : Queue
EmptyQueue() = [| |]
                

Creates an empty queue.

isEmpty() : boolean
[| |].isEmpty()  = true 

aQueue.isEmpty() = false 
    if aQueue ≠ [| |]
                
  • Calling isEmpty() on the empty queue returns true.
  • Calling isEmpty() on a non empty queue returns false.

size() : Integer
[| |].size()  = 0

aQueue.size() = n 
    where |aQueue| = n 
                
  • Calling size() on an empty queue returns 0
  • Calling size() on a non empty queue returns the number of elements in the queue.

add(Integer s) : Queue
[| |].add(n)       = [| n |]

[|x,y,...|].add(n) = [|n,x,y,...|]
                
  • Calling add(n) on an empty queue returns a new queue that has only one element n.
  • Calling add(n) on a non empty queue returns a new queue with n as the first element followed by all the elements of the original queue in their original order.

contains(Integer x) : boolean
[| |].contains(x)  = false 

aQueue.contains(x) = true 
    if aQueue = [| x,a,b,... |]


aQueue.contains(x) = [|a,b,...|].contains(x)
    if aQueue = [| s,a,b,... |]
    and s ≠ x
                
  • Calling contains(x) on the empty queue returns false.
  • Calling contains(x) on a non-empty queue that contains x returns true.
  • Calling contains(x) on a non-empty queue that does not contain x returns false.

pop() : Queue

[| |].pop()             = error 

[| x |].pop()           = [| |]

[| x,y,...,w,z |].pop() = [| x,y,...,w |]
                
  • Calling pop() on an empty queue throws an error.
  • Calling pop() on a one element queue return the empty queue.
  • Calling pop() on a non-empty queue with more than one element, returns a new queue that has all the elements of the original queue except the last element.

peek(): Integer
[| |].peek()          = error

[| x,y,...,w |].peek() = w
                
  • Calling peek() on an empty queue throws an error.
  • Calling peek() on a non empty queue returns the queue's last element.

You are also required to provide implementations for the methods equals(Object o) and hashCode(). For equals() two queues are equal if and only if they have the same exact elements and in the same order (identical), i.e., [| 1,2,3,1,2,3 |] is not equal with [| 1,2,3,1,2, |] or [| 2,1,3,1,2,3 |].