1. List ADT

A classmate found the following ADT for lists

Operation Description

CreateEmpty() : List

Creates an empty list

add(String element) : void

Adds the given element to the start of the list (index 1)

add(String element, Integer index) : void

Adds the given element at index index. The index provided must be a positive integer greater than 0 and less than the size of the list. It the value passed for indes does not meet these criteria we should signal an error

size() : Integer

Returns the number of elements in the list

isEmpty() : Boolean

Returns true if the list has no elements, false otherwise

get(Integer index) : String

Returns the element at index index. The index provided must be a positive integer greater than 0 and less than the size of the list. It the value passed for indes does not meet these criteria we should signal an error

remove(Integer index) : void

Removes the element at index index. The index provided must be a positive integer greater than 0 and less than the size of the list. It the value passed for indes does not meet these criteria we should signal an error

Your classmate wants to implement the above ADT using a singly linked list and started writing some code but he is now stuck. Here is his code thus far.

package edu.neu.ccs.cs5004.sp16.lab5.list;

/**
 * The List ADT
 */
public interface List {

	public static List CreateEmpty() {

		return null; // TODO
	}

	void add(String element);

	void add(String element, Integer index);

	Integer size();

	Boolean isEmpty();

	String get(Integer index);

	void remove(Integer index);

}
package edu.neu.ccs.cs5004.sp16.lab5.list;


public class Tuple implements List {

	private String value;
	private List next;

	public Tuple(String value, List next) {
		super();
		this.value = value;
		this.next = next;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void add(String element) {
		// TODO Auto-generated method stub

	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void add(String element, Integer index) {
		// TODO Auto-generated method stub

	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public Integer size() {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public Boolean isEmpty() {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public String get(Integer index) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public void remove(Integer index) {
		// TODO Auto-generated method stub

	}

}
Practise Exercises

  1. Finish the implementation of Tuple. Add method bodies and tests as appropriate.

  2. Make sure you provide implementations for toString(), equals() and hashCode()

  3. Your friend claims that it is not possible to alter your code to make your list implementation accept any type of element, like Integers, Booleans or even nested lists. Prove them wrong.

Your roomate took your code and is using it for their projects. They are confused however because they are using your generic list implementation to store Players but they want to loop over the list and perform an action to each element but they cannot figure out how to do it. Here is their code.

package edu.neu.ccs.cs5004.sp16.lab5.game;

/**
 * Represents a player in the zombie game
 */
public class Player {
	private String name;
	private Integer strength;

	/**
	 * @param name
	 * @param strength
	 */
	public Player(String name, Integer strength) {
		super();
		this.name = name;
		this.strength = strength;
	}

	/**
	 * @return this Player's name
	 */
	public String getName() {
		return this.name;
	}

	/**
	 * @param name
	 *            the name to set
	 */
	public void setName(String name) {
		this.name = name;
	}

	/**
	 * @return this Player's strength
	 */
	public Integer getStrength() {
		return this.strength;
	}

	/**
	 * @param strength
	 *            the strength to set
	 */
	public void setStrength(Integer strength) {
		this.strength = strength;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = (prime * result) + ((this.name == null) ? 0 : this.name.hashCode());
		result = (prime * result) + ((this.strength == null) ? 0 : this.strength.hashCode());
		return result;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (getClass() != obj.getClass()) {
			return false;
		}
		Player other = (Player) obj;
		if (this.name == null) {
			if (other.name != null) {
				return false;
			}
		} else if (!this.name.equals(other.name)) {
			return false;
		}
		if (this.strength == null) {
			if (other.strength != null) {
				return false;
			}
		} else if (!this.strength.equals(other.strength)) {
			return false;
		}
		return true;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public String toString() {
		return "Player [name=" + this.name + ", strength=" + this.strength + "]";
	}

}
package edu.neu.ccs.cs5004.sp16.lab5.game;

import edu.neu.ccs.cs5004.sp16.lab5.list.List;

/**
 * Represents a team of players in the game
 */
public class Team {
	private List<Player> members;

	/**
	 * @param members
	 */
	public Team(List<Player> members) {
		super();
		this.members = members;
	}

	/**
	 * @return this Platoon's members
	 */
	public List<Player> getMembers() {
		return this.members;
	}

	/**
	 * @param members
	 *            the members to set
	 */
	public void setMembers(List<Player> members) {
		this.members = members;
	}

	public void takeHit(Integer damage) {
		// loop over members and decrease their
		// strength by damage.
		// Also if any player gets strength 0 or
		// less than 0 remove them from the list
	}

	public void takeBoost(Integer boost) {
		// loop over members and increase their
		// strength by boost.
	}

}
Practise Exercises

  1. Help them fill in the implementaiton of takeHit and takeBoost. Your roomate feels strongly about using a while loop here but he cannot get it to work.

  2. Write tests for any code that you add to Team and/or Player.

2. Queue

Here is another ADT for a simple generic Queue<E>

Operation Description Empty() : Queue

  • Creates an empty Queue

isEmpty: Boolean

  • returns true if the Queue is empty

  • returns false if the Queue is non-empty

size() : Integer

  • returns 0 if the Queue is empty

  • returns the number of elements in the Queue

push(x): void

  • adds the element x to the start of the queue

pop() : void * removes the first element in the Queue

peek() : E

  • if the Queue is empty peek throws an error

  • if the Queue is not empty then return the first element. The queue remains unchanged.
Practise Exercises

  1. Provide an implementaiton for Queue<E>.

We would like to now implement a bounded queue BQ. A bounded queue works in the same way as your Queue but it has a maximum number of elements that it can hold.

We will need

  1. The ability to pass the maximum number of elements that the queue can hold when we create a BQ

  2. The push operation must now throw an error when we try to add an element to a full BQ. A full BQ is a queue whose size is equal to its maximum number of elements

  3. A method to check how many more elements we can add to the BQ before it reaches maximum capacity.

Practise Exercises

  1. Provide an implementation for BQ.

  2. Add the method push2 to BQ that allows us to push 2 elements, i.e., it is equivalent in effect to calling push twice.

  3. Add the method pop2 to BQ that allows us to pop 2 elements, i.e., it is equivalent in effect to calling pop twice.

3. Circular Queue

A circular queue CQ works similarly to a bounded queue BQ but when the queue reaches capacity instead of throwing an error we remove the last element in the queue to make room and then add the new element to the start of the queue. The remaining original elements should stay in the same order. For example, given a CQ with capacity 5 with the elements a, b, c, d, e, the queue will look like

  [| a, b, c, d, e |]

If we add the element x then we get

  [| x, a, b, c, d |]

Adding y will then give us

  [| y, x, a, b, c |]