Lab 1: Singly-Linked List (120 pts) Due Monday, January 13 at 11:59pm on Canvas Before you begin!
Pair Programming Required!
Part 1: Project Set Up & Pre and Post Conditions
* Defines a singly-linked list class * @author * @author */ import java.util.NoSuchElementException; public class List<T> { private class Node { private T data; private Node next; public Node(T data) { this.data = data; this.next = null; } } private int length; private Node first; private Node last; /****CONSTRUCTOR****/ /** * Instantiates a new List with default values * @postcondition */ public List() { } /****ACCESSORS****/ /** * Returns the value stored in the first node * @precondition * @return the value stored at node first * @throws NoSuchElementException when precondition is violated */ public T getFirst() throws NoSuchElementException{ return null; } /** * Returns the value stored in the last node * @precondition * @return the value stored in the node last * @throws NoSuchElementException when precondition is violated */ public T getLast() throws NoSuchElementException{ return null; } /** * Returns the current length of the list * @return the length of the list from 0 to n */ public int getLength() { return -1; } /** * Returns whether the list is currently empty * @return whether the list is empty */ public boolean isEmpty() { return false; } /****MUTATORS****/ /** * Creates a new first element * @param data the data to insert at the * front of the list * @postcondition */ public void addFirst(T data) { return; } /** * Creates a new last element * @param data the data to insert at the * end of the list * @postcondition */ public void addLast(T data) { return; } /** * removes the element at the front of the list * @precondition * @postcondition * @throws NoSuchElementException when precondition is violated */ public void removeFirst() throws NoSuchElementException{ return; } /** * removes the element at the end of the list * @precondition * @postcondition * @throws NoSuchElementException when precondition is violated */ public void removeLast() throws NoSuchElementException{ return; } /****ADDITIONAL OPERATIONS****/ /** * List with each value on its own line * At the end of the List a new line * @return the List as a String for display */ @Override public String toString() { return ""; } }
Part 2: Method Implementation
Testing Your List Using ListTest.java
Constructor
/** * Instantiates a new List with default values * @postcondition <--fill in here */ public List() { first = null; last = //you fill in here length = //you fill in here }
/** * Class to test List.java * @author * @author */ public class ListTest { public static void main(String[] args) { List<Integer> L = new List<>(); } } Additional List Operations - toString()
/** * List with each value on its own line * At the end of the List a new line * @return the List as a String for display */ @Override public String toString() { String result = ""; Node temp = first; while(temp != null) { result += fill in here //fill in here } return result; }
/** * Class to test List.java * @author * @author */ public class ListTest { public static void main(String[] args) { List<Integer> L = new List<>(); System.out.println("Should print nothing (an empty list): " + L); } } Mutator: addFirst
* Creates a new first element * @param data the data to insert at the * front of the list * @postcondition */ public void addFirst(T data) { if (first == null) { first = last = new Node(data); } else { Node N = new Node(data); N.next = first; first = N; } length++; }
/** * Class to test List.java * @author * @author */ public class ListTest { public static void main(String[] args) { List<Integer> L = new List<>(); System.out.println("Should print nothing (an empty list): " + L); System.out.println("**Testing addFirst**"); L.addFirst(2); //Testing Edge case: length == 0 System.out.println("Should print 2: " + L); L.addFirst(1); //Testing General case: length >= 1 System.out.println("Should print 1 2: " + L); } } Mutator: addLast
Mutator: removeFirst
* removes the element at the front of the list * @precondition <--fill in here * @postcondition <-- fill in here * @throws NoSuchElementException when precondition is violated */ public void removeFirst() throws NoSuchElementException{ if (length == 0) { throw new NoSuchElementException("removeFirst(): Cannot remove from an empty List!"); } else if (length == 1) { first = last = null; } else { first = first.next; } length--; }
* Class to test List.java * @author * @author */ public class ListTest { public static void main(String[] args) { List<Integer> L = new List<>(); System.out.println("Should print nothing (an empty list): " + L); System.out.println("**Testing addFirst**"); L.addFirst(2); System.out.println("Should print 2: " + L); L.addFirst(1); System.out.println("Should print 1 2: " + L); //Code to test addLast goes here! System.out.println("**Testing removeFirst**"); L.removeFirst(); //Testing General case: length >1 System.out.println("Should print 2: " + L); L.removeFirst(); //Testing Edge case: length == 1 System.out.println("Should print an empty List: " + L); System.out.println("Should an error message for an empty List: "); try { //place in a try-catch so program does not end when exception thrown L.removeFirst(); //Testing Precondition: length == 0 } catch(NoSuchElementException e) { System.out.println(e.getMessage()); } } Mutator: removeLast
* removes the element at the end of the list * @precondition <--fill in here * @postcondition <--fill in here * @throws NoSuchElementException when precondition is violated */ public void removeLast throws NoSuchElementException { //add your if statement here else if (length == 1) { //add a line of code here } else { Node temp = first; while (temp.next != last) { temp = temp.next; } last = temp; last.next = null; } length--; } Writing the List Access Methods
Accessor: isEmpty
/**
/** Accessor: getLength()
Accessor: getFirst()
* Returns the value stored in the first node * @precondition * @return the value stored at node first * @throws NoSuchElementException when the precondition is violated */ public T getFirst() throws NoSuchElementException{ if (length == 0) { throw new NoSuchElementException("getFirst: List is Empty. No data to access!"); } return first.data; }
Accessor: getLast()
Part 3: Testing Your List Using JUnit
JUnit Tests for addLast(): import static org.junit.Assert.*; import org.junit.Test; public class AddLastTest { @Test public void test() { List<Integer> L = new List<>(); L.addLast(1); assertEquals(1, L.getLength()); L.addLast(2); assertEquals(2, L.getLast());//note that you may need to create a new Integer(2) to compare L.addLast(3); assertEquals(3, L.getLast()); } } JUnit Tests for getLength(): import static org.junit.Assert.*; import org.junit.Test; public class GetLengthTest { @Test public void test() { List<Integer> L = new List<>(); assertEquals(0, L.getLength()); L.addLast(3); assertEquals(1, L.getLength()); L.addFirst(2); assertEquals(2, L.getLength()); } } Part 4:BlockChain Application
Transaction.java Interface
/** * Transaction.java * @author FILL IN HERE * @author FILL IN HERE * CIS 22C Lab 1 */ public interface Transaction { /** * Returns the transaction id * @return the id of the transaction */ int getTransactionId(); /** * Returns the customer's first name * @return the first name */ String getFirstName(); /** * Returns the customer's last name * @return the last name */ String getLastName(); /** * Returns the transaction description * @return the description */ String getDescription(); /** * Calculates the hash for the next * block * @param id the next block's id * @param firstName the customer first * name for the next block * @param lastName the customer last * name of the next block */ void computeHash(int id, String firstName, String lastName);
} Block.java Class
/** * Block.java * @author * @author * CIS 22C Lab 1 */ public class Block implements Transaction{ private int transactionId; private String firstName; private String lastName; private String description; private long timeStampMillis; private long hashNextBlock; private static int numBlocks = 0;
/** * Constructor for a Block * @param id the transaction id * @param first the customer first name * @param last the customer last name * @param description the transaction description * Calls System's currentTimeMillis() method * to assign the timeStampMillis * Increases the numBlocks */ public Block(int id, String first, String last, String description) {
}
/** * Returns the current number of blocks * @return the number of blocks */ public static int getNumBlocks() { return numBlocks; }
/** * Calculates the hash for the next * block * @param id the next block's id * @param firstName the customer first * name for the next block * @param lastName the customer last * name of the next block */ public void computeHash(int id, String firstName, String lastName) { String name = firstName + lastName; int sum = 0; for (int i = 0; i < name.length(); i++) { sum += name.charAt(i); } hashNextBlock = sum * 10000 + id; }
/** * toString for the Block class * @return a String of Block object * */ @Override public String toString() { return "\n" }
} transactions.txt file:
987684 Jiming Wu 5 heads romaine lettuce 987685 James Brown 2 pints strawberries 987686 Leanna Perez 1 dozen oranges 987687 Xing Li 2 bunches kale 987688 Stacey Cahill 3 boxes cherry tomatoes 945544 Mohammed Abbas 1 pint blueberries 945575 Kumari Chakrabarti 1 loaf whole wheat bread 945576 Shakil Smith 1 red cabbage 945682 Jung Ahrin 4 honey crisp apples 945683 Pedro Martinez 10 Persian cucumbers 945873 Ally Gu 2 pounds dry farm tomatoes 945874 Tamara White 2 bunches cilantro 956689 Alvin Ngo 5 limes 956690 Abir Fadel 12 red onions 942211 Brad Feinman 3 avocado 942212 Xiaohang Yue 5 carrots BlockChain.java Class
Sample Output of BlockChain.java: Welcome to Block Chain! Total Number of Blocks: 16 Would you like to add another transaction (y/n)?: y Enter the transaction id: 748474 Enter the customer first and last name: Gabriel Ramos Enter the transaction description: 1 bunch collard greens Total Number of Blocks: 17 Would you like to add another transaction (y/n)?: y Enter the transaction id: 832839 Enter the customer first and last name: Tao Nguyen Enter the transaction description: 6 purple potatoes Total Number of Blocks: 18 Would you like to add another transaction (y/n)?: n Total Number of Blocks: 18 Enter the name of the output file: blocks.txt Goodbye! Corresponding output file for above example output: Id: 987684 Name: Jiming Wu Description: 5 heads romaine lettuce Time Stamp: 1554434883163 Hash of Next Block: 11147685 Id: 987685 Name: James Brown Description: 2 pints strawberries Time Stamp: 1554434883163 Hash of Next Block: 12077686 Id: 987686 Name: Leanna Perez Description: 1 dozen oranges Time Stamp: 1554434883163 Hash of Next Block: 6857687 Id: 987687 Name: Xing Li Description: 2 bunches kale Time Stamp: 1554434883163 Hash of Next Block: 13047688 Id: 987688 Name: Stacey Cahill Description: 3 boxes cherry tomatoes Time Stamp: 1554434883164 Hash of Next Block: 13755544 Id: 945544 Name: Mohammed Abbas Description: 1 pint blueberries Time Stamp: 1554434883164 Hash of Next Block: 18275575 Id: 945575 Name: Kumari Chakrabarti Description: 1 loaf whole wheat bread Time Stamp: 1554434883164 Hash of Next Block: 12155576 Id: 945576 Name: Shakil Smith Description: 1 red cabbage Time Stamp: 1554434883164 Hash of Next Block: 9965682 Id: 945682 Name: Jung Ahrin Description: 4 honey crisp apples Time Stamp: 1554434883164 Hash of Next Block: 14425683 Id: 945683 Name: Pedro Martinez Description: 10 Persian cucumbers Time Stamp: 1554434883165 Hash of Next Block: 6845873 Id: 945873 Name: Ally Gu Description: 2 pounds dry farm tomatoes Time Stamp: 1554434883165 Hash of Next Block: 12055874 Id: 945874 Name: Tamara White Description: 2 bunches cilantro Time Stamp: 1554434883165 Hash of Next Block: 8936689 Id: 956689 Name: Alvin Ngo Description: 5 limes Time Stamp: 1554434883165 Hash of Next Block: 9536690 Id: 956690 Name: Abir Fadel Description: 12 red onions Time Stamp: 1554434883165 Hash of Next Block: 11732211 Id: 942211 Name: Brad Feinman Description: 3 avocado Time Stamp: 1554434883165 Hash of Next Block: 12162212 Id: 942212 Name: Xiaohang Yue Description: 5 carrots Time Stamp: 1554434883166 Hash of Next Block: 12828474 Id: 748474 Name: Gabriel Ramos Description: 1 bunch collard greens Time Stamp: 1554434920850 Hash of Next Block: 10052839 Id: 832839 Name: Tao Nguyen Description: 6 purple potatoes Time Stamp: 1554434944322 Hash of Next Block: 0
Specifications for Submission
|