+1 (315) 557-6473 

Program To Solve Data Structures and Algorithms in C++ Language Assignment Solution.


Instructions

Objective
Write a program to solve data structures and algorithms in C++ language.

Requirements and Specifications

Implement
  • 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);

    }

}