Instructions
Requirements and Specifications
- Linked list
- GCD test
- Heap Sort
- Stack
Source Code
LINKED LIST
package com.gsd.algorithms.datastructures.linkedlist;
import org.junit.jupiter.api.*;
import static com.google.common.truth.Truth.assertThat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
@DisplayName("Vahid TestClass")
public class LinkedListTest {
private static final int LOOPS = 10000;
private static final int TEST_SZ = 40;
private static final int NUM_NULLS = TEST_SZ / 5;
private static final int MAX_RAND_NUM = 250;
DoublyLinkedList<Integer> list;
@BeforeEach
public void setup() {
list = new DoublyLinkedList<>();
}
@Test
@DisplayName("Ensure list is empty initially")
public void testEmptyList() {
assertThat(list.isEmpty()).isTrue();
assertThat(list.size()).isEqualTo(0);
}
// @Test(expected = Exception.class) //junit 4
@Test
@DisplayName("Exception removing 1st from empty list")
public void testRemoveFirstOfEmpty() {
Assertions.assertThrows(Exception.class, () -> {
list.removeFirst();
});
}
// @Test(expected = Exception.class)
@DisplayName("Exception removing last from empty list")
@Test public void testRemoveLastOfEmpty() {
Assertions.assertThrows(Exception.class, () -> {
list.removeLast();
});
}
// @Test(expected = Exception.class)
@DisplayName("Exception peek 1st from empty list")
@Test public void testPeekFirstOfEmpty() {
Assertions.assertThrows(Exception.class, () -> {
list.peekFirst();
});
}
@DisplayName("Exception peek last from empty list")
@Test public void testPeekLastOfEmpty() {
Assertions.assertThrows(Exception.class, () -> {
list.peekLast();
});
}
@Test
@DisplayName("Testing adding first")
public void testAddFirst() {
list.addFirst(3);
assertThat(list.size()).isEqualTo(1);
list.addFirst(5);
assertThat(list.size()).isEqualTo(2);
}
@Test
@DisplayName("Testing adding last")
public void testAddLast() {
list.addLast(3);
assertThat(list.size()).isEqualTo(1);
list.addLast(5);
assertThat(list.size()).isEqualTo(2);
}
@Test
@DisplayName("Testing adding at a specific index")
public void testAddAt() throws Exception {
list.addAt(0, 1);
assertThat(list.size()).isEqualTo(1);
list.addAt(1, 2);
assertThat(list.size()).isEqualTo(2);
list.addAt(1, 3);
assertThat(list.size()).isEqualTo(3);
list.addAt(2, 4);
assertThat(list.size()).isEqualTo(4);
list.addAt(1, 8);
assertThat(list.size()).isEqualTo(5);
}
@Test
@DisplayName("Testing removing first")
public void testRemoveFirst() {
list.addFirst(3);
assertThat(list.removeFirst()).isEqualTo(3);
assertThat(list.isEmpty());
}
@Test
@DisplayName("Testing removing last")
public void testRemoveLast() {
list.addLast(4);
assertThat(list.removeLast()).isEqualTo(4);
assertThat(list.isEmpty()).isTrue();
}
@Test
@DisplayName("Testing peeking first")
public void testPeekFirst() {
list.addFirst(4);
assertThat(list.peekFirst()).isEqualTo(4);
assertThat(list.size()).isEqualTo(1);
}
@Test
@DisplayName("Testing peeking last")
public void testPeekLast() {
list.addLast(4);
assertThat(list.peekLast()).isEqualTo(4);
assertThat(list.size()).isEqualTo(1);
}
@Test
@DisplayName("Testing peeking in a larger list")
public void testPeeking() {
// 5
list.addFirst(5);
assertThat(list.peekFirst()).isEqualTo(5);
assertThat(list.peekLast()).isEqualTo(5);
// 6 - 5
list.addFirst(6);
assertThat(list.peekFirst()).isEqualTo(6);
assertThat(list.peekLast()).isEqualTo(5);
// 7 - 6 - 5
list.addFirst(7);
assertThat(list.peekFirst()).isEqualTo(7);
assertThat(list.peekLast()).isEqualTo(5);
// 7 - 6 - 5 - 8
list.addLast(8);
assertThat(list.peekFirst()).isEqualTo(7);
assertThat(list.peekLast()).isEqualTo(8);
// 7 - 6 - 5
list.removeLast();
assertThat(list.peekFirst()).isEqualTo(7);
assertThat(list.peekLast()).isEqualTo(5);
// 7 - 6
list.removeLast();
assertThat(list.peekFirst()).isEqualTo(7);
assertThat(list.peekLast()).isEqualTo(6);
// 6
list.removeFirst();
assertThat(list.peekFirst()).isEqualTo(6);
assertThat(list.peekLast()).isEqualTo(6);
}
@Test
@DisplayName("Testing removing from a large list")
public void testRemoving() {
DoublyLinkedList<String> strs = new DoublyLinkedList<>();
strs.add("a");
strs.add("b");
strs.add("c");
strs.add("d");
strs.add("e");
strs.add("f");
strs.remove("b");
strs.remove("a");
strs.remove("d");
strs.remove("e");
strs.remove("c");
strs.remove("f");
assertThat(strs.size()).isEqualTo(0);
}
@Test
@DisplayName("Testing removing at index from a large list")
public void testRemoveAt() {
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.removeAt(0);
list.removeAt(2);
assertThat(list.peekFirst()).isEqualTo(2);
assertThat(list.peekLast()).isEqualTo(3);
list.removeAt(1);
list.removeAt(0);
assertThat(list.size()).isEqualTo(0);
}
@Test
@DisplayName("Testing clearing the list")
public void testClear() {
list.add(22);
list.add(33);
list.add(44);
assertThat(list.size()).isEqualTo(3);
list.clear();
assertThat(list.size()).isEqualTo(0);
list.add(22);
list.add(33);
list.add(44);
assertThat(list.size()).isEqualTo(3);
list.clear();
assertThat(list.size()).isEqualTo(0);
}
@Test
@DisplayName("Testing removing randomly")
public void testRandomizedRemoving() {
java.util.LinkedList<Integer> javaLinkedList = new java.util.LinkedList<>();
for (int loops = 0; loops < LOOPS; loops++) {
list.clear();
javaLinkedList.clear();
List<Integer> randNums = genRandList(TEST_SZ);
for (Integer value : randNums) {
javaLinkedList.add(value);
list.add(value);
}
Collections.shuffle(randNums);
for (int i = 0; i < randNums.size(); i++) {
Integer rm_val = randNums.get(i);
assertThat(javaLinkedList.remove(rm_val)).isEqualTo(list.remove(rm_val));
assertThat(javaLinkedList.size()).isEqualTo(list.size());
java.util.Iterator<Integer> iter1 = javaLinkedList.iterator();
java.util.Iterator<Integer> iter2 = list.iterator();
while (iter1.hasNext()) assertThat(iter1.next()).isEqualTo(iter2.next());
iter1 = javaLinkedList.iterator();
iter2 = list.iterator();
while (iter1.hasNext()) assertThat(iter1.next()).isEqualTo(iter2.next());
}
list.clear();
javaLinkedList.clear();
for (Integer value : randNums) {
javaLinkedList.add(value);
list.add(value);
}
// Try removing elements whether or not they exist
for (int i = 0; i < randNums.size(); i++) {
Integer rm_val = (int) (MAX_RAND_NUM * Math.random());
assertThat(javaLinkedList.remove(rm_val)).isEqualTo(list.remove(rm_val));
assertThat(javaLinkedList.size()).isEqualTo(list.size());
java.util.Iterator<Integer> iter1 = javaLinkedList.iterator();
java.util.Iterator<Integer> iter2 = list.iterator();
while (iter1.hasNext()) assertThat(iter1.next()).isEqualTo(iter2.next());
}
}
}
@Test
@DisplayName("Testing removing randomly at index")
public void testRandomizedRemoveAt() {
java.util.LinkedList<Integer> javaLinkedList = new java.util.LinkedList<>();
for (int loops = 0; loops < LOOPS; loops++) {
list.clear();
javaLinkedList.clear();
List<Integer> randNums = genRandList(TEST_SZ);
for (Integer value : randNums) {
javaLinkedList.add(value);
list.add(value);
}
for (int i = 0; i < randNums.size(); i++) {
int rm_index = (int) (list.size() * Math.random());
Integer num1 = javaLinkedList.remove(rm_index);
Integer num2 = list.removeAt(rm_index);
assertThat(num1).isEqualTo(num2);
assertThat(javaLinkedList.size()).isEqualTo(list.size());
java.util.Iterator<Integer> iter1 = javaLinkedList.iterator();
java.util.Iterator<Integer> iter2 = list.iterator();
while (iter1.hasNext()) assertThat(iter1.next()).isEqualTo(iter2.next());
}
}
}
@Test
@DisplayName("Testing random index at")
public void testRandomizedIndexOf() {
java.util.LinkedList<Integer> javaLinkedList = new java.util.LinkedList<>();
for (int loops = 0; loops < LOOPS; loops++) {
javaLinkedList.clear();
list.clear();
List<Integer> randNums = genUniqueRandList(TEST_SZ);
for (Integer value : randNums) {
javaLinkedList.add(value);
list.add(value);
}
Collections.shuffle(randNums);
for (int i = 0; i < randNums.size(); i++) {
Integer elem = randNums.get(i);
Integer index1 = javaLinkedList.indexOf(elem);
Integer index2 = list.indexOf(elem);
assertThat(index1).isEqualTo(index2);
assertThat(javaLinkedList.size()).isEqualTo(list.size());
java.util.Iterator<Integer> iter1 = javaLinkedList.iterator();
java.util.Iterator<Integer> iter2 = list.iterator();
while (iter1.hasNext()) assertThat(iter1.next()).isEqualTo(iter2.next());
}
}
}
@Test
@DisplayName("Testing toString")
public void testToString() {
DoublyLinkedList<String> strs = new DoublyLinkedList<>();
assertThat(strs.toString()).isEqualTo("[ ]");
strs.add("a");
assertThat(strs.toString()).isEqualTo("[ a ]");
strs.add("b");
assertThat(strs.toString()).isEqualTo("[ a, b ]");
strs.add("c");
strs.add("d");
strs.add("e");
strs.add("f");
assertThat(strs.toString()).isEqualTo("[ a, b, c, d, e, f ]");
}
// Generate a list of random numbers
static List<Integer> genRandList(int sz) {
List<Integer> lst = new ArrayList<>(sz);
for (int i = 0; i < sz; i++) lst.add((int) (Math.random() * MAX_RAND_NUM));
for (int i = 0; i < NUM_NULLS; i++) lst.add(null);
Collections.shuffle(lst);
return lst;
}
// Generate a list of unique random numbers
static List<Integer> genUniqueRandList(int sz) {
List<Integer> lst = new ArrayList<>(sz);
for (int i = 0; i < sz; i++) lst.add(i);
for (int i = 0; i < NUM_NULLS; i++) lst.add(null);
Collections.shuffle(lst);
return lst;
}
}
HEAP SORT
package com.gsd.algorithms.sorting;
import com.gsd.algorithms.datastructures.stack.IntStack;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import java.util.Random;
import static com.google.common.truth.Truth.assertThat;
@DisplayName("Vahid TestClass")
public class HeapsortTest {
private static final int TEST_SZ = 400;
Heapsort heapsort;
int[] array;
Random random = new Random(1);
@BeforeEach
public void setup() {
array = new int[TEST_SZ];
for(int i = 0; i<TEST_SZ; i++) {
array[i] = random.nextInt();
}
heapsort = new Heapsort();
}
@Test
@DisplayName("Testing heapSort")
public void testEmptyStack() {
heapsort.sort(array);
assertThat(isSorted(array)).isTrue();
}
private static boolean isSorted(int[] array) {
int prev = array[0];
for (int i = 1; i<array.length; i++) {
int curr = array[i];
if (prev > curr) {
return false;
}
prev = curr;
}
return true;
}
}
GCD TEST
package com.gsd.algorithms.math;
import com.gsd.algorithms.datastructures.stack.IntStack;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import static com.google.common.truth.Truth.assertThat;
@DisplayName("Vahid TestClass")
public class GCDTest {
@Test
@DisplayName("Testing both zero arguments")
public void testBothZeroGCD() {
assertThat(GCD.gcd(0,0)).isEqualTo(0);
}
@Test
@DisplayName("Testing on one zero argument")
public void testZeroGCD() {
assertThat(GCD.gcd(7,0)).isEqualTo(7);
assertThat(GCD.gcd(-7,0)).isEqualTo(7);
assertThat(GCD.gcd(0,7)).isEqualTo(7);
assertThat(GCD.gcd(0,-7)).isEqualTo(7);
assertThat(GCD.gcd(1,0)).isEqualTo(1);
assertThat(GCD.gcd(-1,0)).isEqualTo(1);
assertThat(GCD.gcd(0,-1)).isEqualTo(1);
assertThat(GCD.gcd(0,1)).isEqualTo(1);
}
@Test
@DisplayName("Testing on one argument")
public void testOneGCD() {
assertThat(GCD.gcd(1,1)).isEqualTo(1);
assertThat(GCD.gcd(1,-1)).isEqualTo(1);
assertThat(GCD.gcd(-1,1)).isEqualTo(1);
assertThat(GCD.gcd(-1,-1)).isEqualTo(1);
assertThat(GCD.gcd(1,7)).isEqualTo(1);
assertThat(GCD.gcd(1,-7)).isEqualTo(1);
assertThat(GCD.gcd(-1,7)).isEqualTo(1);
assertThat(GCD.gcd(-1,-7)).isEqualTo(1);
assertThat(GCD.gcd(7,1)).isEqualTo(1);
assertThat(GCD.gcd(7,-1)).isEqualTo(1);
assertThat(GCD.gcd(-7,1)).isEqualTo(1);
assertThat(GCD.gcd(-7,-1)).isEqualTo(1);
}
@Test
@DisplayName("Testing on co-prime arguments")
public void testCoPrimeGCD() {
assertThat(GCD.gcd(1000,49)).isEqualTo(1);
assertThat(GCD.gcd(1000,-49)).isEqualTo(1);
assertThat(GCD.gcd(-1000,49)).isEqualTo(1);
assertThat(GCD.gcd(-1000,-49)).isEqualTo(1);
assertThat(GCD.gcd(49,1000)).isEqualTo(1);
assertThat(GCD.gcd(49,-1000)).isEqualTo(1);
assertThat(GCD.gcd(-49,1000)).isEqualTo(1);
assertThat(GCD.gcd(-49,-1000)).isEqualTo(1);
}
@Test
@DisplayName("Testing on non co-prime arguments")
public void testNonCoPrimeGCD() {
assertThat(GCD.gcd(1000,490)).isEqualTo(10);
assertThat(GCD.gcd(1000,-490)).isEqualTo(10);
assertThat(GCD.gcd(-1000,490)).isEqualTo(10);
assertThat(GCD.gcd(-1000,-490)).isEqualTo(10);
assertThat(GCD.gcd(490,1000)).isEqualTo(10);
assertThat(GCD.gcd(490,-1000)).isEqualTo(10);
assertThat(GCD.gcd(-490,1000)).isEqualTo(10);
assertThat(GCD.gcd(-490,-1000)).isEqualTo(10);
}
}
STACK
package com.gsd.algorithms.datastructures.stack;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import static com.google.common.truth.Truth.assertThat;
@DisplayName("Vahid TestClass")
public class IntStackTest {
private static final int TEST_SZ = 40;
IntStack stack;
@BeforeEach
public void setup() {
stack = new IntStack(TEST_SZ);
}
@Test
@DisplayName("Testing isEmpty")
public void testEmptyStack() {
assertThat(stack.isEmpty()).isTrue();
stack.push(1);
assertThat(stack.isEmpty()).isFalse();
stack.push(2);
assertThat(stack.isEmpty()).isFalse();
stack.pop();
assertThat(stack.isEmpty()).isFalse();
stack.pop();
assertThat(stack.isEmpty()).isTrue();
}
@Test
@DisplayName("Testing peek on empty stack")
public void testPeekOnEmptyStack() {
Assertions.assertThrows(IndexOutOfBoundsException.class, () -> {
stack.peek();
});
}
@Test
@DisplayName("Testing peek on non-empty stack")
public void testPeek() {
int a = 1, b = 2;
stack.push(a);
assertThat(stack.peek()).isEqualTo(a);
stack.push(b);
assertThat(stack.peek()).isEqualTo(b);
stack.pop();
assertThat(stack.peek()).isEqualTo(a);
}
@Test
@DisplayName("Testing size")
public void testSizeStack() {
int expectedSize = 0;
assertThat(stack.size()).isEqualTo(expectedSize);
stack.push(1);
expectedSize++;
assertThat(stack.size()).isEqualTo(expectedSize);
stack.push(2);
expectedSize++;
assertThat(stack.size()).isEqualTo(expectedSize);
stack.pop();
expectedSize--;
assertThat(stack.size()).isEqualTo(expectedSize);
stack.pop();
expectedSize--;
assertThat(stack.size()).isEqualTo(expectedSize);
}
}