quark-dsa

quark-dsa

The Quark-dsa is a JavaScript utility library for data structures and operations on it. It is built using TypeScript and includes data structures Stack, Queue, Tree, Graph and many more.

All documentation for this library can be found here.

Install

npm install quark-dsa

Usage

There are several utility functions in quark-dsa, those you can use for performing data structures and operations.

• String:

  Reverse the string

  import { reverseString } from "quark-dsa";
  
  let str = "quark";
  reverseString(str); // returns 'krauq'
  

  Check a string is palindrome

  import { isStringPalindrome } from "quark-dsa";
  
  let str = "racecar";
  isStringPalindrome(str); // returns true;
  

  Sort the string

  import { sortString } from "quark-dsa";
  
  let str = "mississippi";
  sortString(str); //returns iiiimppssss
  

  Words list in the sentence

  import { getWords } from "quark-dsa";
  
  let str = "Lorem ipsum dolor sit amet, consectetur adipiscing elit";
  getWords(str); //returns ["Lorem", "ipsum", "dolor", "sit", "amet", "consectetur", "adipiscing", "elit"]
  

• Number:

  Reverse the number

  import { reverseNumber } from "quark-dsa";
  
  let num = 5698;
  reverseNumber(num); // returns 8965
  

  Check a number is prime number

  import { isPrime } from "quark-dsa";
  
  let num = 37019;
  isPrime(num); // returns true;
  

  Check a number is palindrome

  import { isNumberPalindrome } from "quark-dsa";
  
  let num = 1562651;
  isNumberPalindrome(num); // returns true;
  

  Factorial of a number

  import { factorial } from "quark-dsa";
  
  factorial(5); // returns 120;
  factorial(15); // returns 1307674368000
  

  Permutations of the list

  You can get number of possibilities of selecting k entities out of set of n entities. It will give you the result of nPk.

  import { permutations } from "quark-dsa";
  
  permutations(5, 2); //returns 20
  permutations(12, 2); // returns 132
  

  Combinations of the list

  You can get number of arrangements of k entities out of set of n entities. It will give you the result of nCk

  import { combinations } from "quark-dsa";
  
  combinations(5, 2); //returns 10
  combinations(12, 2); // returns 66
  

• Array:

  Mean (Average Calculation)

  You can calculate the mean of a list. Supported mean types are arithmetic, geometric, harmonic and rms (root mean square). By default arithmetic is selected.

  import { mean } from "quark-dsa";
  
  let list = [2, 6, 4, 5, 8];
  mean(list); // returns 5
  mean(list, "geometric"); // returns 4.54
  mean(list, "harmonic"); // returns 4.03
  mean(list, "rms"); // returns 5.39
  

  Median

  You can calculate middle value of the list, which is median. If list has even number of items, it will return average of middle two values, otherwise it will return middle value. List will get sorted in ascending order before median calculation.

  import { median } from "quark-dsa";
  
  let list = [4, 12, 14, 17, 22, 23, 23, 24, 25, 29, 40, 67, 77, 82, 92];
  median(list); // returns 24
  let list2 = [142, 140, 130, 150, 160, 135, 158, 132];
  median(list2); // returns 141
  

  Mode

  You can also get the element having highest frequency in the list, which is mode. If the list has only one mode, then it will return as a number. If the list has more than one modes, then it will return all mode values in an array.

  import { mode } from "quark-dsa";
  
  let list = [3, 3, 6, 9, 16, 16, 16, 27, 27, 37, 48];
  mode(list); // returns 16
  let list2 = [3, 3, 3, 9, 16, 16, 16, 27, 37, 48];
  mode(list2); // returns [3, 16]
  

  Variance and Standard Variation

  You can also calculate Variance and Standard Variation of the list.

  import { variance, standardDeviation } from "quark-dsa";
  
  let list = [46, 69, 32, 60, 52, 41];
  variance(list); // returns 177.2
  standardDeviation(list); // returns 13.31
  let list2 = [4, 2, 5, 8, 6];
  variance(list2); // returns 5
  standardDeviation(list2); // returns 2.24
  

  Remove duplicates

  You can remove duplicates from a list and returns the same list. Here, in place operation is performed on the list. Only numbers and strings are supported in the list.

  import { removeDuplicates } from "quark-dsa";
  
  let list = [1, 2, 3, 3, 2, 1, 4, 5, 1, 5, 8, 3];
  removeDuplicates(list); // returns [1, 2, 3, 4, 5, 8];
  let list2 = [
    "John",
    "George",
    "Paul",
    "Ringo",
    "George",
    "Bob",
    "Elvis",
    "Freddie",
    "Paul",
  ];
  removeDuplicates(list2); // returns ["John", "George", "Paul", "Ringo", "Bob","Elvis", "Freddie"]
  

  Histogram

  You can get the object of occurence of all items in the list.

  import { histogram } from "quark-dsa";
  
  let list = [3, 3, 3, 9, 16, 16, 16, 27, 37, 48];
  histogram(list); // returns {"3": 3, "9": 1, "16": 3, "27": 1, "37": 1, "48": 1}
  

  Greatest Common Divisor (GCD) and Least Common Multiples (LCM) of an array

  You can calculate GCD and LCM of an array.

  import { gcd, lcm } from "quark-dsa";
  
  let list = [8, 12, 16];
  gcd(list); // returns 4
  let list2 = [12, 18, 24];
  lcm(list2); // returns 72
  

  Matrix Operations

  You can also perform matrix operations like addition, subtraction and multiplication on the n*n arrays.

  import {
    matrixAddition,
    matrixSubtraction,
    matrixMultiplication,
    matrixDeterminant,
  } from "quark-dsa";
  
  let list = [
    [2, 4, 3],
    [5, 7, 8],
    [9, 6, 7],
  ];
  let list2 = [
    [3, 5, 7],
    [8, 3, 4],
    [5, 7, 8],
  ];
  matrixAddition(list, list2); // returns [[5, 9, 10], [13, 10, 12], [14, 13, 15]]
  matrixSubtraction(list, list2); // returns [[-1, -1, -4], [-3, 4, 4], [4, -1, -1]]
  matrixMultiplication(list, list2); // returns [[53, 43, 54], [111, 102, 127], [110, 112, 143]]
  matrixDeterminant(list); // returns 51
  

Highlights

quark-dsa provides following data startuctures and common operations (more work is going on...):

• Stack: Basic push, pop, peek, length and serach operations are supported.
• Queue: Basic enqueue, dequeue, length and search operations are supported.
• Linked List: Construct, add node, update node, delete node, reverse, concat, get middle node, rotate operations are supported.
• Binary Tree: Construct, insert/update/delete node of the tree. Traversal paths of the tree (preorder, inorder, postorder, level order traversal), inverting the tree.

quark-dsa also provides commonly used algorithms as utility functions.

• Searching: Linear and Binary search algorithms are added to give position of key in the list.

quark-dsa provides sorting algorithms as utility functions.

• Sorting: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Radix Sort.

Stack

Initialize the stack

You can create a stack with the given size. Size is optional argument with the default value 65535.

import { Stack } from "quark-dsa";

const stack = new Stack(200); // Creates stack with size 200.

Supported methods

Usage

import { Stack } from "quark-dsa";

const stack = new Stack(); // new stack is created.
stack.push(23); // pushes 23 to the top of the stack.
stack.push(36); // pushes 36 to the top of the stack.
stack.length(); // returns 2;
stack.search(36); // returns 1;
stack.search(98); // returns -1;
stack.pop(); // removes top element from the stack and returns it.
stack.peek(); // returns the top element of the stack, 23.
stack.length(); // returns 1;
stack.pop(); // removes top element from the stack and returns it.
stack.isEmpty(); // returns true as stack is empty now.

Queue

Initialize the queue

You can create a queue with the given size. Size is optional argument with the default value 65535.

import { Queue } from "quark-dsa";

const queue = new Queue(200); // Creates queue with size 200.

Supported methods

Usage

import { Queue } from "quark-dsa";

const queue = new Queue(); // new queue is created.
queue.enqueue(3); // inserts 3 to the rear of the queue.
queue.enqueue(8); // inserts 8 to the rear of the queue.
queue.length(); // returns 2;
queue.search(8); // returns 1;
queue.search(98); // returns -1;
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.getFront(); // returns the front item of the queue, 8.
queue.enqueue(10); // inserts 10 to the rear of the queue.
queue.getRear(); // returns the rear item of the queue, 10.
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.dequeue(); // removes the front item of the queue and then returns it.
queue.length(); // returns 0;
queue.isEmpty(); // returns true as queue is empty now.

Linked List

Initialize the linked list

You can create an empty linked list or you can pass an array which will convert an array to an linked list.

import { LinkedList } from "quark-dsa";

const list = new LinkedList(); // returns an empty linked list.

or;

const list = new LinkedList([17, 2, 96, 55, 40]); // returns a linked list with array elements inserted sequentially.

Supported methods

Usage

import { LinkedList } from "quark-dsa";

const list = new LinkedList([17, 2, 96, 55, 40]); // returns a linked list with array elements inserted sequentially.
list.print(); // returns the value in the console log "17 -> 2 -> 96 -> 55 -> 40".
list.add(3); // inserts 3 at last of the linked list.
list.update(45, 3); // updates node of index 3 with value 45.
list.remove(5); // removes node at index 5;
list.reverse(); // reverse the list.
list.getMiddleValue(); // returns the middle value of the list, 96.
list.rotateRight(4); // rotates the list to 4 positions towards right.
list.rotateLeft(5); // rotates the list to 5 positions towards left.

const list2 = new LinkedList([89, 21, 63, 45]); // returns a linked list with array elements inserted sequentially.
list.concat(list2); // returns list with concatenated values of list2.

Binary Tree

Initialize the binary tree

You can create a tree with the root value. If the root value is not given, an empty node is created and set as a root of the tree.

import { BinaryTree } from "quark-dsa";

const tree = new BinaryTree(5); // The binary tree with root value as 5 is created.
const tree2 = new BinaryTree(); // The binary tree is created with root value set as null.

For performing operations on a node in the tree, we need to provide the path of the node. Path of the node should be in the format of L and R. For example, path LRRL means node of having path Left -> Right -> Right -> Left from the root node. Any characters other than L and R with throw an error.

Supported methods

Usage

import { BinaryTree } from "quark-dsa";

const tree = new BinaryTree(5); // Constructs a tree with 5 as a root node value.
tree.insertNode(3, "L"); // Inserts a node with value 3 on left of root.
tree.insertNode(9, "R"); // Inserts a node with value 9 on right of root.
tree.insertNode(5, "LR"); // Inserts a node with value 5 on right of 3.
tree.insertNode(7, "RL"); // Inserts a node with value 7 on left of 9.
tree.insertNode(6, "RLL"); // Inserts a node with value 6 on left on 7.
tree.insertNode(8, "RLR"); // Inserts a node with value 8 on right on 7.
tree.insertNode(12, "RR"); // Inserts a node with value 12 on right on 9.
tree.insertNode(20, "RRR"); // Inserts a node with value 20 on right on 12.
tree.inorder(); // Should return [3, 5, 5, 6, 7, 8, 9, 12, 20].
tree.preorder(); // Should return [5, 3, 5, 9, 7, 6, 8, 12, 20].
tree.postorder(); // Should return [5, 3, 6, 8, 7, 20, 12, 9, 5].
tree.levelOrder(); // Should return [5, 3, 9, 5, 7, 12, 6, 8, 20].
tree.height(); // Should return 4.
tree.updateNode(13, ""); // Should update root node with value 13.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 8, 12, 20].
tree.updateNode(31, "RLR"); // Updates the node with value 8 with 31.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 31, 12, 20].
tree.deleteNode("RR"); // Should delete the node 12.
tree.inorder(); // Should return [3, 5, 13, 6, 7, 31, 9].
tree.deleteNode("RLL"); // Should delete the node 6.
tree.inorder(); // Should return [3, 5, 13, 7, 31, 9].
tree.invert(); // Construct the invert (mirror) of the tree.
tree.inorder(); // Shoud return [9, 31, 7, 13, 5, 3].

Binary Search Tree

Initialize the binary search tree

You can create a binary search tree with the list of node values or insert each node at a time.

import { BinarySearchTree } from "quark-dsa";

const tree = new BinarySearchTree([8, 3, 10, 6, 1, 4, 14, 7]); // This will create a binary search tree with node 8 as a root.
const root = tree.getRoot(); // It will return the root of the tree.
tree.insert(15); // It will insert node with value 15 in the tree.

Supported methods

Usage

import { BinarySearchTree } from "quark-dsa";

const tree = new BinarySearchTree([8, 3, 10, 6, 1, 4, 14, 7]); // Constructs a tree with 8 as a root node value.
tree.inorder(); // Should return [1, 3, 4, 6, 7, 8, 10, 14].
tree.preorder(); // Should return [8, 3, 1, 6, 4, 7, 10, 14].
tree.postorder(); // Should return [1, 4, 7, 6, 3, 14, 10, 8].
tree.insert(13); // Insert 13 in the tree.
tree.inorder(); // Should return [1, 3, 4, 6, 7, 8, 10, 13, 14].
tree.preorder(); // Should return [8, 3, 1, 6, 4, 7, 10, 14, 13].
tree.postorder(); // Should return [1, 4, 7, 6, 3, 13, 14, 10, 8].
tree.levelOrder(); // Should return [8, 3, 10, 1, 6, 14, 4, 7, 13].
tree.height(); // Should return 4.

Search

Quark-dsa supports Linear Search and Binary Search operations. You can pass the list and search key, it will return the position of the search key in the list.

Linear Search

Linear Search iterates over the list and returns the position of the search key in the list. If the search key is not present in the list, it will return -1.

import { LinearSearch } from "quark-dsa";

const list = [20, 12, 10, 15, 2];
LinearSearch(list, 15); // returns 3;
LinearSearch(list, 58); // returns -1;

Binary Search

Binary Search compares the search key with the middle value of the list and then partitions the list depending on the search key will be in the left or right partition. The important pre-requisite for the Binary Search is that the list should be in ascending order, otherwise it will throw an error. If the search key is not present in the list, it will return -1.

import { BinarySearch } from "quark-dsa";

const list = [2, 10, 12, 15, 20];
BinarySearch(list, 15); // returns 3;
BinarySearch(list, 58); // returns -1;

Sort

Quark-dsa supports different sorting algorithms including the bubble sort, insertion sort, selection sort, mergesort, quicksort and radix sort.

import {
  BubbleSort,
  InsertionSort,
  SelectionSort,
  MergeSort,
  QuickSort,
  RadixSort,
} from "quark-dsa";

const list = [-2, 45, 0, 11, -9];
BubbleSort(list); // returns [-9, -2, 0, 11, 45]
InsertionSort(list); // returns [-9, -2, 0, 11, 45]
SelectionSort(list); // returns [-9, -2, 0, 11, 45]
MergeSort(list); // returns [-9, -2, 0, 11, 45]
QuickSort(list); // returns [-9, -2, 0, 11, 45]
RadixSort(list); // returns [-9, -2, 0, 11, 45]