Deques Design Document

1. Classes and Data Structures

ArrayDeque

This class stores the elements and other information in the array based deque.

Fields

1. T[] items; // Generic array of elements, holds all elements inserted into deque
2. int size; //maintains current size of deque, where size is the number of elements
3. int nextFirst; //maintains pointer to current “start” of array
4. int nextLast; //maintains pointer to current “end” of array.
5. final int START_SIZE = 8; //default (starting) size of deque

LinkedListDeque

This class stores the elements and other information in the linked list based deque.

Fields

1. Node sentinel; // generic linked list node sentinel, points to linked list of all elements
2. int size; // maintains current size of deque, where size is the number of elements

Inner Class Node

Fields

1. T item; // generic item, holds value of specific element
2. Node next; // pointer to next element
3. Node prev; // pointer to previous element

2. Algorithms

ArrayDeque

1. public ArrayDeque(); // no args constructor to initialize empty deque

a. Creates an empty deque by initializing the array based on START_SIZE, size, nextFirst, and nextLast. ```java 2. public addFirst(T element); // inserts element to the start of the deque based on nextFirst ```
a. First we will check if items.length == size(). If it is that means that we have to resize, we will geometrically increase the length of items by a factor of 2 and copy over our items (this will be done by calling the private helper function resize(2 * items.length). After the check to resize / possible resize, we will set items[nextLast] = element, increment size, and set nextLast = (nextLast + 1) % items.length.
b. *We will not provide further explanations for all algorithms, but for your Gitlet project you should record in detail what each method / algorithm will do.* ```java 3. public addLast(T element); // inserts element to end of the deque based on nextLast 4. public size(); // returns current size 5. public printDeque(); // prints visual representation of current state of deque 6. public removeFirst(); // removes and returns first element in deque based on nextFirst 7. public removeLast(); // removes and returns last element in deque based on nextLast 8. public get(int index); // returns element at provided index 9. private wrapIndex(int index); // returns index translated into range [0, size - 1] 10. private resize(int newLen); // resizes underlying array to size newLen. Copies all elements and retains relative ordering. ```

LinkedListDeque

1. public LinkedListDeque(); // no args constructor to initialize empty deque
2. public addFirst(T element); // inserts element to the start of the deque
3. public addLast(T element); // inserts element to end of the deque
4. public size(); // returns current size
5. public printDeque(); // prints visual representation of current state of deque
6. public removeFirst(); // removes and returns first element in deque
7. public removeLast(); // removes and returns last element in deque
8. public get(int index); // returns element at provided index
9. public getRecursive(int index); // returns element at provided index using the recursive helper function
10. private getItemRecursive(Node node, int index); // overloaded private helper function to recursively find element at index provided

Node

1. public Node(T element); // instantiates new element

3. Persistence

Note: This section was not required for Project 1, but is necessary for Project 2. For the purposes of demonstrating how you might fill this section in your own design document, imagine that Project 1 also required keeping track of the state of the Deque after leaving the program that defines it. That is, imagine we execute:

java -ea deques.Main [configuration file] [input] [output]

This would create a LinkedListDeque or ArrayDeque based on the configuration file (imagine this configuration file could specify what type of Deque to use) and populate it based on the input. We will be saving a representation of the object created to file. Thus, the settings provided in the first run should persist across multiple executions of the program, as we will be able to reload the object.

In order to persist the state of the deque, we must save the necessary data elements. That is: write the ArrayDeque or LinkedListDeque to disk. We can serialize them into bytes that we can eventually write to a file on disk, named based on a set naming convention. This can be done with the writeObject() method from the Utils class.

In order to retrieve our state, before executing any code, we need to search for the saved files in the working directory (folder in which our program exists) and load the objects that we saved in them. Since we set on a file naming convention (“myLinkedListDeque1”, etc.) our program always knows which files it should look for. We can use the readObject() method from the Utils class to read the data of files and deserialize the associated objects we previously wrote to these files.