For this assignment you need to do a JAVA program to implement queue data structure using linked list for this assignment.

Summary

Your job is to implement a FriendshipQueue, using linked nodes. A friendship queue is like a normal queue, except that when a new object joins a queue, it looks to see if it has any friends in the queue. If it has friends in the queue, it jumps in the queue with its friends, instead of joining the tail of the queue. There is a limit though, a person in line can only have two friends join them. When a set of friends gets to the front of the queue, they are processed one at a time, in the order they joined the line.

Instructions

Part 1: Create a TernaryNode class. This should look very much like the double-linked LinearNode class that you already have, except that in addition to next and prev references, there is also a child reference:

Test your TernaryNode by writing Junit tests.

Part 2: Create a FriendshipQueue class that implements the FriendshipQueueADT and makes use of the TernaryNode class you have created. The UML diagram for this class is below:

Note that while you must implement the methods above, you are welcome to add as many private helper methods to the FriendshipQueue class as you need. While this looks similar to a regular queue, a few things are different:

In the enqueue() method, you must search the queue to see if the element has any friends (the compareTo method will return 0 if the items are friends). If a friend element is found in the queue, you must check to make sure it hasnt already got two other friends in line with it. If not, you add this element so that it stands in queue with its friend. If the friend already has two friends in line with it, continue searching until youve got to the front of the queue. If you search the queue and cant find any friends to join, enqueue as usual.

In the dequeue() method, if the element you are dequeing has friends standing in line with it, you must move the friends up towards the queue. Watch how you maintain your state variables here.

The size() method counts the length of the queue, ignoring friends. The totalSize() method returns the length of the queue, including the friends.

Here are diagrams that show how the friendship queue should operate:

after dequeue() operation (size is 5, totalSize is 7):

after a queue() operation adding a dark blue element:

after enqueuing another dark blue element:

Requirements

You must fulfill the following:

- Implementation: you need to implement the TernaryNode class and the FriendshipQueue class. These two classes will be graded by web-cat.

- Write Junit tests for your TernaryNode and your FriendshipQueue classes. These will be graded by the TA.

Files needed

ClubLineUp:

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package ds_assignment2;

import java.util.logging.Level; import java.util.logging.Logger;

/** * Club lineup simulation for ITIS 2214 Assignment 2 * Version 1 * @date Feb 20, 2017 * @author clatulip */ public class ClubLineup { private FriendshipQueue lineup; private String[] dorms; private String[] names; private int id; private int clubEntries; private final int MAX_SIM_STEPS = 40; private final int MAX_NAMES = 20; private final int MAX_DORMS = 5;

public ClubLineup() { setupNames(); }

public void runSimulation() { lineup = new FriendshipQueue(); id = 0; clubEntries = 0; for (int i = 0; i < MAX_SIM_STEPS; i++ ) { // at each step, either add someone to the queue // or dequeue someone double ran = Math.random(); if (ran < 0.7) { // create new friend and enqueue Friend f = createNewFriend(); try { lineup.enqueue(f); } catch (NonComparableElementException ex) { Logger.getLogger(ClubLineup.class.getName()).log(Level.SEVERE, null, ex); } System.out.println(" Adding " + f.getName() + " from " + f.getDormName() + "(ID# " + Integer.toString(f.getId()) + ") to club lineup."); } else { // dequeue, if queue isn't empty if (!lineup.isEmpty()) { try { Friend f = (Friend)lineup.dequeue(); clubEntries++; System.out.println("**** " + f.getName() + "(ID# " + Integer.toString(f.getId()) + ") just got into the club!"); } catch (EmptyCollectionException ex) { Logger.getLogger(ClubLineup.class.getName()).log(Level.SEVERE, null, ex); } } else { System.out.println("... The club lineup is empty."); } } } System.out.println(clubEntries + " people got into the club. "); System.out.println("There are still " + lineup.totalSize() + " people in line."); }

private void setupNames() { names = new String[MAX_NAMES]; names[0] = "Abdul"; names[1] = "Jen"; names[2] = "Chris"; names[3] = "Myron"; names[4] = "Rutuja"; names[5] = "Harrison"; names[6] = "Carlos"; names[7] = "Elizabeth"; names[8] = "Jean-Paul"; names[9] = "Richard"; names[10] = "Sofia"; names[11] = "Kyle"; names[12] = "Tyler"; names[13] = "Mohammed"; names[14] = "Avery"; names[15] = "Miriam"; names[16] = "Mariah"; names[17] = "Tristan"; names[18] = "Jacob"; names[19] = "Brandon"; // setup dorms dorms = new String[MAX_DORMS]; dorms[0] = "Levine Hall"; dorms[1] = "Belk Hall"; dorms[2] = "Laurel Hall"; dorms[3] = "Pine Hall"; dorms[4] = "Oak Hall"; }

private Friend createNewFriend() { int dNum = (int)(Math.random()*(MAX_DORMS-1)); int nNum = (int)(Math.random()*(MAX_NAMES-1)); Friend f = new Friend(names[nNum], dorms[dNum], id); id++; return f; } }

DS_Assignment2:

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package ds_assignment2;

/** * * @author clatulip */ public class DS_Assignment2 {

/** * @param args the command line arguments */ public static void main(String[] args) { ClubLineup cl = new ClubLineup(); cl.runSimulation(); } }

EmptyCollectionException:

package ds_assignment2;

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */

/** * An Empty Collection Exception class * Prints out what type of collection is empty * For use in ITCS 2214 Data Structures & Algorithms * UNC Charlotte, 2016 * @author clatulip */ public class EmptyCollectionException extends Exception {

public EmptyCollectionException(String collection) { super("The " + collection + " is empty."); } }

Friend:

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package ds_assignment2;

/** * Friend class for use in Data Structures Assignment 2 * @author clatulip */ public class Friend implements Comparable { private String name; private String dormName; private int id;

public Friend(String name, String dormName, int id) { this.name = name; this.dormName = dormName; this.id = id; }

public String getName() { return name; }

public void setName(String name) { this.name = name; }

public String getDormName() { return dormName; }

public void setDormName(String dormName) { this.dormName = dormName; }

public int getId() { return id; }

public void setId(int id) { this.id = id; }

@Override public int compareTo(Object o) { // string comparison based on dormName field Friend f = (Friend)o; return f.getDormName().compareTo(this.getDormName()); }

@Override public String toString() { return "Friend{" + "name=" + name + ", dormName=" + dormName + ", id=" + id + '}'; }

}

FriendshipQueueADT:

package ds_assignment2;

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */

/** * An interface for a friendship queue * For use in ITCS 2214 Data Structures & Algorithms * UNC Charlotte, 2016 * @author clatulip */ public interface FriendshipQueueADT { /** * Adds the specified element to the end of the queue, but... * If the element has friends in the queue that it can queue with * Note that friend groups can't be larger than 3, if an element can't * join friends b/c the groups all have 3, this element has to join the * end of the queue * @param element element to be added to the queue */ public void enqueue(T element) throws NonComparableElementException; /** * Removes and returns the element that is at the front of the queue * If there is a friend group at the front, the first friend is dequeued * and then friends move up in the queue * @return the element removed from the queue * @throws EmptyCollectionException */ public T dequeue() throws EmptyCollectionException; /** * Returns (without removing) the element that is at the front of the queue * @return the element at the front of the queue * @throws EmptyCollectionException */ public T first()throws EmptyCollectionException; /** * Returns true if the collection contains no elements * @return true if the collection is empty */ public boolean isEmpty(); /** * Returns the length of the queue, ignoring friends * @return the number of elements as an int */ public int size(); /** * Returns the length of the queue, including friends * @return the number of elements as an int */ public int totalSize(); /** * Returns a string representation of the collection * @return a string representation of the collection */ @Override public String toString(); }

NonComparableElementException:

package ds_assignment2;

/** * Exception class for when trying to compare collection elements that * haven't implemented Comparable (and don't have a compareTo(..) method) * @author clatulip */ public class NonComparableElementException extends Exception {

public NonComparableElementException(String collection) { super("The element passed in to " + collection + " does not implement Comparable."); } }