In Part I we used a Singly Linked List, where each node knows the next node in the list, but not the previous. With a doubly linked list, nodes will now know both the previous and next nodes. This provides some efficiencies for certain types of operations, like for reversing a list. For this part, you should find three source files. Note that ColorListApp is a JavaFX app that you can run and will demonstrate use of GenericDoublyLinkedList, which is where you will write your code. Look through all three classes and be sure to carefully read the documentation.

With a doubly linked list, you must always be careful to properly update the next & prev node variables after each operation on the list.

In addition to being a doubly linked list, in this part you will be manipulating a generic list, just as we discussed in lecture. Your list will be able to store any type of objects. The ColorListApp class provides one example, demonstrating the use of your class for storing and manipulating Color objects. When you feel that your methods are properly defined, try playing around with the ColorListApp application.

NOTE: you should write your own little driver class (a class with a main method) for testing your methods independently of ColorListApp, which has lots of stuff that may confuse you. Create a main method and build your list and print the contents to verify if your method are working properly.

YOUR FOUR METHODS, ALL FOR THE GenericDoublyLinkedList CLASS

Define the clear method such that it when called it completely empties the list of all nodes.

Define the moveFrontToLast method such that it takes the first node in the list and moves it to the end of the list, leaving the rest of the list as it was.

Define the moveLastToFront method such that it takes the last node in the list and moves it to the front of the list, leaving the rest of the list as it was.

Define the reverse method such that it simply reverses the order of the nodes in the list. So, what was first is now last, what was last is now first, etc. A list that was originally ABCDE would be EDCBA after being reversed.

Here is a code.

package part_two_color_animation;

import java.util.Iterator; import javafx.beans.property.BooleanProperty; import javafx.beans.property.IntegerProperty; import javafx.scene.canvas.Canvas; import javafx.scene.canvas.GraphicsContext; import javafx.scene.paint.Color; import javafx.scene.text.Font; import javafx.scene.text.FontPosture; import javafx.scene.text.FontWeight;

/** * ColorCanvas.java * * DO NOT CHANGE THIS FILE * * This class does the rendering of the list of Colors in a list. * */ public class ColorCanvas extends Canvas {

// THIS IS THE LIST WE'LL BE DRAWING GenericDoublyLinkedList colorList; // THIS APP WILL MONITOR THESE FOR RENDERING // THE FRAME RATE BooleanProperty keepAnimatingProperty; IntegerProperty fpsProperty;

// THESE ARE ALL THE DRAWING CONSTANTS FOR // SIZING AND LOCATING THINGS final int TEXT_X_OFFSET = 20; final int TEXT_Y_OFFSET = 5; final int RECT_WIDTH = 40; final int RECT_HEIGHT = 40; final int RECT_X_OFFSET = 0; final int RECT_Y_OFFSET = 0; final int NODES_PER_ROW = 32; final int MAX_NODES = 720; final int FPS_X = 20; final int FPS_Y = 20; final int NODES_PER_COLUMN = MAX_NODES / NODES_PER_ROW; Font nodeFont = Font.font("Helvetica", FontWeight.NORMAL, FontPosture.REGULAR, 16);

/** * Constructor, it initializes everything this canvas * needs to draw the list of colors. */ public ColorCanvas( BooleanProperty initKeepAnimatingProperty, IntegerProperty initFpsProperty, GenericDoublyLinkedList initColorList) { keepAnimatingProperty = initKeepAnimatingProperty; fpsProperty = initFpsProperty; colorList = initColorList; }

/** * This function clears the canvas and then does * the rendering, this is to be called each time * the list is changed. */ public void repaint() { // THIS DOES THE ACTUAL RENDERING GraphicsContext gC = getGraphicsContext2D(); gC.setFont(nodeFont);

// WHAT ARE THE PANEL DIMENSIONS int canvasWidth = (int) getWidth(); int canvasHeight = (int) getHeight();

// CLEAR OUT WHAT WE DREW PREVIOUSLY gC.clearRect(0, 0, canvasWidth, canvasHeight);

// CALCULATE THE SIZE OF EVERYTHING WE NEED TO DRAW int totalWidth = (NODES_PER_ROW * RECT_WIDTH) + ((NODES_PER_ROW - 1) * RECT_X_OFFSET); int totalHeight = ((NODES_PER_COLUMN + 2) * RECT_HEIGHT) + ((NODES_PER_COLUMN + 1) * RECT_Y_OFFSET);

// FIRST DRAW THE FRAME RATE gC.strokeText("Frames Per Second: " + fpsProperty.getValue(), FPS_X, FPS_Y); // CALCULATE THE CANVAS LOCATION OF THE FIRST NODE int rectX = (canvasWidth / 2) - (totalWidth / 2); int rectY = (canvasHeight / 2) - (totalHeight / 2) + RECT_HEIGHT;

// WE'LL USE THESE TO CALCULATE COLOR LOCATIONS int row; boolean drawingComplete = false; int counter = 0; // GO THROUGH ALL THE COLORS IN THE LIST ONCE Iterator it = colorList.listIterator(); while (!drawingComplete) { // CALCULATE THE ROW row = counter / NODES_PER_ROW;

if (!it.hasNext()) { // WE JUST PASSED THE LAST NODE IN THE LIST, // TIME TO END THE RENDERING drawingComplete = true; } else { // MORE NODES TO RENDER Color color = (Color) it.next(); // FILL A RECTANGLE WITH THIS COLOR gC.setFill(color); gC.fillRect(rectX, rectY, RECT_WIDTH, RECT_HEIGHT); counter++;

// LAST NODE IN ROW if ((counter % NODES_PER_ROW) == 0) { rectY += RECT_HEIGHT + RECT_Y_OFFSET; } // FIRST NODE IN ROW, PREV POINTS UP else if ((counter % NODES_PER_ROW) == 1) { // NEXT IS TO THE RIGHT if ((row % 2) == 0) { rectX += RECT_WIDTH + RECT_X_OFFSET; } // NEXT IS TO THE LEFT else { rectX -= RECT_WIDTH + RECT_X_OFFSET; } } // NEXT IS TO THE RIGHT else if (row % 2 == 0) { rectX += RECT_WIDTH + RECT_X_OFFSET; } // NEXT IS TO THE LEFT else { rectX -= RECT_WIDTH + RECT_X_OFFSET; } } } } }

package part_two_color_animation;

import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; import java.util.concurrent.locks.ReentrantLock; import javafx.application.Application; import javafx.application.Platform; import javafx.beans.property.BooleanProperty; import javafx.beans.property.IntegerProperty; import javafx.beans.property.SimpleBooleanProperty; import javafx.beans.property.SimpleIntegerProperty; import javafx.geometry.Rectangle2D; import javafx.scene.Scene; import javafx.scene.control.Alert; import javafx.scene.control.Alert.AlertType; import javafx.scene.layout.BorderPane; import javafx.scene.layout.HBox; import javafx.stage.Stage; import javafx.scene.control.Button; import javafx.scene.control.CheckBox; import javafx.scene.layout.StackPane; import javafx.scene.paint.Color; import javafx.stage.Screen;

/** * ColorListApp.java * * DO NOT CHANGE THIS FILE * * This class plays around with a GenericDoublyLinkedList of Color objects. It * uses methods in that list class to manipulate the list and then provides a * timed animation mechanism to see these manipulations in action. * */ public class ColorListApp extends Application {

// HERE'S OUR LIST GenericDoublyLinkedList colorList = new GenericDoublyLinkedList(); // WE'LL NEED THESE TO ANIMATE AnimationTimer animationThread = new AnimationTimer(); IntegerProperty fps = new SimpleIntegerProperty(10); boolean restartAnimation = false; final int MAX_FPS = 100; final int MIN_FPS = 5;

// THIS WILL MAKE SURE ONLY ONE THREAD WILL BE ACCESSING // SHARED DATA AT A TIME. NOTE WE WILL HAVE A THREAD // FOR ANIMATION AND THE GUI ITSELF MANAGES THREADS SO // THAT IT CAN DRAW THE GUI WHILE ALSO LISTENING FOR USER INPUT ReentrantLock animationLock = new ReentrantLock();

// THIS IS THE WINDOW AND IT'S TOP LEVEL PANE Stage primaryStage; BorderPane primaryPane = new BorderPane(); Scene primaryScene = new Scene(primaryPane);

// TOP TOOLBAR HBox topPane = new HBox(); Button addColorButton = makeButton("Add Color"); Button addAllRedsButton = makeButton("Add All Reds"); Button addYellowMagentaCyanButton = makeButton("Add Yellow-Magenta-Cyan"); Button addRGBButton = makeButton("Add Red-Green-Blue"); Button moveFrontToLastButton = makeButton("Move Front to Last"); Button moveLastToFrontButton = makeButton("Move Last to Front"); Button reverseListButton = makeButton("Reverse List"); Button removeColorsButton = makeButton("Remove All Colors");

// THIS WILL RENDER OUR LIST StackPane centerPane = new StackPane(); ColorCanvas colorCanvas = new ColorCanvas(animationThread.getKeepAnimatingProperty(), fps, colorList);

// BOTTOM TOOLBAR HBox bottomPane = new HBox(); CheckBox reverseCheckBox = new CheckBox("Reverse"); Button startAnimationButton = makeButton("Start Animation"); Button stopAnimationButton = makeButton("Stop Animation"); Button incAnimationSpeedButton = makeButton("Inc FPS"); Button decAnimationSpeedButton = makeButton("Dec FPS");

/** * Default Constructor, sets up our GUI */ public void start(Stage initPrimaryStage) { // SETUP THE WINDOW primaryStage = initPrimaryStage; primaryStage.setScene(primaryScene); primaryStage.setTitle("Color List App");

// INIT THE GUI layoutGUI();

// OPEN THE WINDOW primaryStage.show(); // AND START OUR ANIMATION THREAD animationThread.start(); }

/** * Puts all of our GUI components in their proper places. It also connects * the buttons to the button handler, which is actually this object. */ public void layoutGUI() { // ARRANGE THE TOP TOOLBAR topPane.getChildren().add(addColorButton); topPane.getChildren().add(addAllRedsButton); topPane.getChildren().add(addYellowMagentaCyanButton); topPane.getChildren().add(addRGBButton); topPane.getChildren().add(moveFrontToLastButton); topPane.getChildren().add(moveLastToFrontButton); topPane.getChildren().add(reverseListButton); topPane.getChildren().add(removeColorsButton);

// THE CENTER ONLY HAS THE CANVAS centerPane.getChildren().add(colorCanvas); colorCanvas.widthProperty().bind(centerPane.widthProperty()); colorCanvas.heightProperty().bind(centerPane.heightProperty());

// AND THE BOTTOM TOOLBAR reverseCheckBox.setStyle("-fx-font-size:14pt; -fx-padding:10px;"); bottomPane.getChildren().add(reverseCheckBox); bottomPane.getChildren().add(startAnimationButton); bottomPane.getChildren().add(stopAnimationButton); bottomPane.getChildren().add(incAnimationSpeedButton); bottomPane.getChildren().add(decAnimationSpeedButton);

// MAKE THE WINDOW FIT OUR SCREEN Screen screen = Screen.getPrimary(); Rectangle2D bounds = screen.getVisualBounds(); primaryStage.setX(bounds.getMinX()); primaryStage.setY(bounds.getMinY()); primaryStage.setWidth(bounds.getWidth()); primaryStage.setHeight(bounds.getHeight());

// PUT EVERYTHING IN THE STAGE primaryPane.setTop(topPane); primaryPane.setCenter(centerPane); primaryPane.setBottom(bottomPane);

// ROUTE THE EVENT SOURCES TO THEIR HANDLERS addColorButton.setOnAction(e -> { respondToButtonPress("respondToAddColor"); }); addAllRedsButton.setOnAction(e -> { respondToButtonPress("respondToAddAllReds"); }); addYellowMagentaCyanButton.setOnAction(e->{ respondToButtonPress("respondToAddYellowToMagentaToCyan"); }); addRGBButton.setOnAction(e -> { respondToButtonPress("respondToAddRGB"); }); moveFrontToLastButton.setOnAction(e -> { respondToButtonPress("respondToMoveFrontToLast"); }); moveLastToFrontButton.setOnAction(e -> { respondToButtonPress("respondToMoveLastToFront"); }); reverseListButton.setOnAction(e -> { respondToButtonPress("respondToReverseList"); }); removeColorsButton.setOnAction(e -> { respondToButtonPress("respondToRemoveColors"); }); startAnimationButton.setOnAction(e -> { respondToButtonPress("respondToStartAnimation"); }); stopAnimationButton.setOnAction(e -> { respondToButtonPress("respondToStopAnimation"); }); incAnimationSpeedButton.setOnAction(e -> { respondToButtonPress("respondToIncAnimationSpeed"); }); decAnimationSpeedButton.setOnAction(e -> { respondToButtonPress("respondToDecAnimationSpeed"); }); // WHEN THE WINDOW CLOSES, KILL THE ANIMATION THREAD primaryStage.setOnCloseRequest(e->{ if (animationThread != null) { animationThread.closeApp(); } });

// OPEN THE WINDOW primaryStage.show(); }

/** * Helper method for making a simple textual button. */ private Button makeButton(String text) { javafx.scene.control.Button b = new javafx.scene.control.Button(text); b.setStyle("-fx-font-size:14pt; -fx-padding:10px;"); return b; }

/** * This method employs reflection to process button clicks * such that it can lock access to the animation variables * first and then unlock access after. */ private void respondToButtonPress(String handlerMethodName) { try { // MAKE SURE NO OTHER CODE TRIES TO CHANGE THINGS // BEFORE WE'RE DONE WITH HANDLING THIS RESPONSE animationLock.lock(); // PAUSE THE ANIMATION WHILE WE'RE FIGURING OUT // WHAT THE RESPONSE SHOULD BE restartAnimation = animationThread.getKeepAnimatingProperty().getValue(); animationThread.setKeepAnimating(false); // HERE IS WHERE REFLECTION CALLS THE NAMED EVENT HANDLING METHOD Class colorListAppClass = this.getClass(); Method handlerMethod = colorListAppClass.getMethod(handlerMethodName); handlerMethod.invoke(this); // RESTART THE ANIMATION IF NECESSARY if (restartAnimation) { // NOTE THAT THIS WILL FORCE A REPAINT respondToStartAnimation(); } else { // REPAINT WITH WHATEVER THE UPDATE MAY BE. NOTE THAT // Platform.runLaber IS JavaFX's WAY OF MAKING SURE // MULTIPLE THREADS AREN'T TRYING TO DO THINGS SIMULTANEOUSLY, // LIKE DRAW TO THE CANVAS. Platform.runLater(()->{ colorCanvas.repaint(); }); } } catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException exc) { // ALWAYS UNLOCK TO AVOID DEADLOCK animationLock.unlock(); exc.printStackTrace(); } finally { // ALWAYS UNLOCK TO AVOID DEADLOCK animationLock.unlock(); } }

/** * Helper method for displaying a simple message dialog. */ private void showMessageDialog(Alert.AlertType alertType, String title, String message) { Alert dialog = new Alert(alertType); dialog.setTitle(title); dialog.setHeaderText(null); dialog.setContentText(message); dialog.showAndWait(); }

// HANDLES PRESSING THE ADD COLOR, IT ADDS ONE COLOR TO THE LIST public void respondToAddColor() { if (colorList.size() < colorCanvas.MAX_NODES) { Color randomColor = Color.color((float) Math.random(), (float) Math.random(), (float) Math.random()); colorList.addLast(randomColor); } else { showMessageDialog(AlertType.WARNING, "No More Colors", "That's enough Colors for now"); } }

// HANDLES PRESSING ADD ALL REDS, IT ADDS 512 REDS TO THE LIST public void respondToAddAllReds() { colorList.clear(); for (int i = 0; i < 256; i += 1) { double r = i / 255.0; Color newRed = Color.color(r, 0, 0); colorList.addLast(newRed); } for (int i = 255; i > -1; i -= 1) { double r = i / 255.0; Color newRed = Color.color(r, 0, 0); colorList.addLast(newRed); } }

// HANDLES ADDING YELLOW, MAGENTA, AND CYAN public void respondToAddYellowToMagentaToCyan() { colorList.clear(); int r = 255, g = 255, b = 0; // YELLOW TO MAGENTA for (int i = 0; i < 256; i++) { Color colorToAdd = Color.color(r/255.0, g/255.0, b/255.0); colorList.addLast(colorToAdd); if (i < 255) { g--; b++; } } // MAGENTA TO CYAN for (int i = 0; i < 256; i++) { Color colorToAdd = Color.color(r/255.0, g/255.0, b/255.0); colorList.addLast(colorToAdd); if (i < 255) { r--; g++; } } // CYAN BACK TO YELLOW for (int i = 0; i < 256; i++) { Color colorToAdd = Color.color(r/255.0, g/255.0, b/255.0); colorList.addLast(colorToAdd); if (i < 255) { r++; b--; } } }

// HANLES ADDING RED, GREEN, AND, BLUE TO LIST public void respondToAddRGB() { colorList.clear(); for (int i = 0; i < 256; i += 1) { Color redToAdd = Color.color(i / 255.0, 0, 0); colorList.addLast(redToAdd); } for (int i = 0; i < 256; i += 1) { Color greenToAdd = Color.color(0, i / 255.0, 0); colorList.addLast(greenToAdd); } for (int i = 0; i < 256; i += 1) { Color blueToAdd = Color.color(0, 0, i / 255.0); colorList.addLast(blueToAdd); } }

// HANDLES MOVING THE FRONT ELEMENT TO THE END public void respondToMoveFrontToLast() { colorList.moveFrontToLast(); }

// HANDLES MOVING THE LAST ELEMENT TO THE FRONT public void respondToMoveLastToFront() { colorList.moveLastToFront(); }

// HANDLES REVERSING THE LIST public void respondToReverseList() { colorList.reverse(); }

// HANDLES REMOVING ALL COLORS FROM THE LIST public void respondToRemoveColors() { colorList.clear(); }

// HANDLES STARTING THE ANIMATOR public void respondToStartAnimation() { animationThread.setKeepAnimating(true); }

// HANDLES STOPPING THE ANIMATOR public void respondToStopAnimation() { animationThread.setKeepAnimating(false); restartAnimation = false; }

// HANDLES INCREMENTING THE ANIMATION SPEED public void respondToIncAnimationSpeed() { incFps(5); }

// HANDLES DECREMENTING THE ANIMATION SPEED public void respondToDecAnimationSpeed() { incFps(-5); }

/** * Accessor method for getting the animation speed. It is * synchronized because there may be multiple threads in this * application that need to use this information simultaneously. */ public IntegerProperty getFpsProperty() { return fps; }

/** * Mutator method for setting the animation speed. It is * synchronized because there may be multiple threads in this * application that need to use this information simultaneously. */ public void incFps(int deltaFps) { // ADD THE DELTA VALUE fps.setValue(fps.getValue() + deltaFps); // AND CLAMP THE FRAMES PER SECOND. if (fps.getValue() < MIN_FPS) { fps.setValue(MIN_FPS); } else if (fps.getValue() > MAX_FPS) { fps.setValue(MAX_FPS); } }

/** * The AnimationTimer class provides our animation timing for us. */ class AnimationTimer extends Thread { // TURNING THIS TO true WILL KILL THE ANIMATOR boolean appClosed = false; // TURNING THIS TO FALSE WILL PAUSE ANIMATION BooleanProperty keepAnimating = new SimpleBooleanProperty(true);

// FOR KILLING THE ANIMATOR public void closeApp() { appClosed = true; } // ACCESSOR FOR GETTING IF THE ANIMATOR IS PAUSED OR NOT public BooleanProperty getKeepAnimatingProperty() { return keepAnimating; }

// FOR PAUSING/UNPAUSING THE ANIMATOR public void setKeepAnimating(boolean initKeepAnimating) { keepAnimating.setValue(initKeepAnimating); }

/** * When this animationThread is started, the run method is called. * It performs timed rendering of the list. */ public void run() { // WHEN THE APP CLOSES EXIT THIS METHOD while (!appClosed) { // IF WE'RE NOT PAUSED if (keepAnimating.getValue()) { try { // LOCK ACCESS TO AVOID RACE CONDITIONS animationLock.lock();

// WHICH LIST METHOD SHOULD BE USED EACH // FRAME OF ANIMATION? if (reverseCheckBox.isSelected()) { // REVERSE colorList.moveFrontToLast(); } else { // FORWARD colorList.moveLastToFront(); } // RENDER THE LIST Platform.runLater(()->{ colorCanvas.repaint(); }); } finally { // RELASE THE LOCK animationLock.unlock(); } } try { // REST BRIEFLY TO ENSURE PROPER TIMING // AND TO ALLOW THE GUI TO GET SOME OPERATIONS // EXECUTED if (keepAnimating.getValue()) { // ENSURES A CONSISTENT FRAME RATE Thread.sleep(1000 / fps.getValue()); } else { // DON'T BE A RESOURCE HOG Thread.sleep(100); } } catch (InterruptedException ie) { ie.printStackTrace(); } } } }

/** * This method launches the ColorListApp JavaFX app, which * constructs it and then forces a call to start. */ public static void main(String[] args) { launch(); } }

package part_two_color_animation;

import java.util.Iterator;

/** * GenericDoublyLinkedList.java * * YOU MUST FILL IN THE CODE FOR THE FOLLOWING FOUR METHODS: * -clear * -moveFrontToLast * -moveLastToFront * -reverse * */ public class GenericDoublyLinkedList {

// YOU'LL NEED TO CAREFULLY MAINTAIN THE head & tail private GenericNode head = null; private GenericNode tail = null; private int size = 0;

// DEFAULT CONSTRUCTOR public GenericDoublyLinkedList() { }

/** * This method simply adds a new node to the end of the list. * Do not need to change this method, it works properly. */ public void addLast(E dataToAdd) { size++; GenericNode newNode = new GenericNode(dataToAdd, tail, null); if (head == null) { head = newNode; tail = head; } else { tail.next = newNode; tail = newNode; } }

/** * You need to define this one. It simply empties the list * of all data (all nodes). */ public void clear() { // ADD YOUR CODE HERE }

/** * You need to define this one. It should take the first node * in the list and move it to the end. */ public void moveFrontToLast() { // ADD YOUR CODE HERE }

/** * You need to define this one. It should take the last node * in the list and move it to the front. */ public void moveLastToFront() { // ADD YOUR CODE HERE }

/** * You need to define this one. It reverses the order of the * nodes in the list. */ public void reverse() { // ADD YOUR CODE HERE }

/** * Accessor method for getting the size of the list. You do * not have to change this method. */ public int size() { return size; }

/** * This method provides an Iterator for iterating through the * list. You should not change this method or the custom * Iterator class, SortedGenericListIterator. */ public Iterator listIterator() { return new SortedGenericListIterator(); }

/** * This is just a basic Iterator, don't change it. */ class SortedGenericListIterator implements Iterator { // THE ITERATOR'S TRAVELLER STARTS AT THE HEAD private GenericNode traveller = head;

public SortedGenericListIterator() { }

// HAVE WE REACHED THE END OF THE LIST? public boolean hasNext() { if (traveller == null) { return false; } else { return true; } }

// GET THE NEXT ELEMENT IN THE LIST public Object next() { if (traveller == null) { return null; }

Object dataToReturn = traveller.data; traveller = traveller.next; return dataToReturn; }

// WE WON'T USE THIS METHOD public void remove() {} }

/** * Node for a generic doubly linked list. It can store any * type of object. */ class GenericNode { // DOUBLY LINKED LIST NODE E data; protected GenericNode prev; protected GenericNode next;

public GenericNode(E dataToAdd, GenericNode initPrev, GenericNode initNext) { data = dataToAdd; prev = initPrev; next = initNext; } } }

Thank you for reading, and help

Have a nice day.