function addUpToSimple(n: number) {let total = 0;for (let i = 0; i < n; i++) {
        total += i;}return total;}

function addUpComplex(n: number) {return (n * (n + 1)) / 2;}

function printUpAndDown(n: number) {
    console.log('Going up');for (let i = 0; i < n; i++) {
        console.log(i);}
    console.log('Going down');for (let j = n - 1; j > 0; j--) {
        console.log(j);}}

function printAllPairs(n: number) {for (let i = 0; i < n; i++) {
        console.log(i);for (let j = 0; j < n; j++) {
            console.log(j);}}}

function logAtLeastFive(n: number) {for (let i = 0; i <= Math.max(5, n); i++) {
        console.log(i);}}

function logAtMostFive(n: number) {for (let i = 0; i <= Math.min(5, n); i++) {
        console.log(i);}}

function sum(arr: number[]) {let total = 0;for (let i = 0; i < arr.length; i++) {
        total += arr[i];}}

function double(arr: number[]) {const newArr = [];for (let i = 0; i < arr.length; i++) {
        array.push(arr[i] * 2);}return newArr;}

const person = { name: 'John', age: 22, hobbies: ['reading', 'sleeping'] };

Object.keys(person); // ["name", "age", "hobbies"] --->              O(n)
Object.values(person); // ["John", 22, Array(2)]--->                 O(n)
Object.entries(person); // [Array(2), Array(2), Array(2)]--->        O(n)
person.hasOwnProperty('name'); // true --->                          O(1)

function binarySearch(sortedArr: number[], value: number): number {let min = 0;let max = sortedArr.length - 1;while (min <= max) {let middle = Math.floor((min + max) / 2);if (sortedArr[middle] < value) {
            min = middle + 1;} else if (sortedArr[middle] > value) {
            max = middle - 1;} else {return middle;}}return -1;}

function wakeUp() {// callStack [wakeUp]takeShower();eatBreakfast();
    console.log('Ready to go ... ');} // callStack []function takeShower() {// callStack [takeShower, wakeUp]
    console.log('taking shower');} // callStack[wakeUp]function eatBreakfast() {// callStack [eatBreakfast, wakeUp]const meal = cookBreakFast();
    console.log(`eating ${meal}`);} // callStack [wakeUp]function cookBreakFast() {// callStack [cookBreakFast, eatBreakfast, wakeUp]const meals = ['Cheese', 'Protein Shake', 'Coffee'];return meals[Math.floor(Math.random() * meals.length)]; // callStack [eatBreakFast, wakeUp]}wakeUp();

function sumRange(num: number) {if (num === 1) return 1;return num + sumRange(num - 1);}function factorial(num: number) {if (num === 1) return 1;return num * factorial(num - 1);}

// helper method recursion approachfunction collectOdd(arr: number[]) {const result = [];function helper(helperArr: number[]) {if (!helperArr.length) {return;}if (helperArr[0] % 2 !== 0) {
            result.push(helperArr[0]);}helper(helperArr.slice(1));}helper(arr);return result;}// pure recursion approachfunction collectOdd(arr: number[]): number[] {let result = [];if (!arr.length) {return result;}if (arr[0] % 2 !== 0) {
        result.push(arr[0]);}

    result = collectOdd(result.concat(arr.slice(1)));return result;}

function linearSearch(arr: number[], value: number): number {for (let i = 0; i < arr.length; i++) {if (arr[i] === value) {return i;}return -1;}}

function binarySearch(sortedArr: number[], value: number): number {let left = 0;let right = sortedArr.length - 1;while (left <= right) {const middle = Math.round((right + left) / 2);if (sortedArr[middle] > value) {
            right = middle - 1;} else if (sortedArr[middle] < value) {
            left = middle + 1;} else {return middle;}}return -1;}

['a', 'c', 'b', 'f', 'd'].sort(); // (5) ["a", "b", "c", "d", "f"][1, 10, 6, 8, 2, 3, 5].sort(); //(7) [1, 10, 2, 3, 5, 6, 8]/* 
also receive callback function by two arguments:
    a: previous number 
    b: next number 

*/// if callback return NEGATIVE number a will placed before b[1, 10, 6, 8, 2, 3, 5].sort((a, b) => a - b); // (7) [1, 2, 3, 5, 6, 8, 10]// if callback return POSITIVE number a will placed after b(7)[(1, 2, 3, 5, 6, 8, 10)].sort((a, b) => b - a); // (7) [10, 8, 6, 5, 3, 2, 1]// if callback return ZERO a and b will placed at the same position

function bubbleSort(arr: number[]): number[] {for (let i = 0; i < arr.length; i++) {let noSwap = true;for (let j = 0; j < arr.length - i; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                noSwap = false;}}if (noSwap) break;}return arr;}// orfunction bubbleSort(arr: number[]): number[] {for (let i = arr.length; i > 0; i--) {let noSwap = true;for (let j = 0; j < i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                noSwap = false;}}if (noSwap) break;}return arr;}

function selectionSort(arr: number[]) {for (let i = 0; i < arr.length; i++) {let min = i;for (let j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) {
                min = j;}}if (min !== i) {[arr[i], arr[min]] = [arr[min], arr[i]];}}return arr;}

function insertionSort(arr) {var currentVal;for (let i = 1; i < arr.length; i++) {
        currentVal = arr[i];for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
            arr[j + 1] = arr[j];}
        arr[j + 1] = currentVal;}return arr;}

// merge two sorted arrayfunction merge(arr1: number[], arr2: number[]): number[] {let result = [];let i = 0;let j = 0;while (i < arr1.length && j < arr2.length) {if (arr1[i] < arr2[j]) {
            result.push(arr1[i]);
            i++;} else {
            result.push(arr2[j]);
            j++;}}while (i < arr1.length) {
        result.push(arr1[i]);
        i++;}while (j < arr2.length) {
        result.push(arr2[j]);
        j++;}return result;}function mergeSort(arr: number[]): number[] {if (arr.length <= 1) return arr;const middle = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, middle));const right = mergeSort(arr.slice(middle));return merge(left, right);}

// place pivot in the right index and return pivot indexfunction pivot(arr: number[], start = 0, end = arr.length - 1) {const pivot = arr[start];let pivotIndex = start;for (let i = start + 1; i < end; i++) {if (arr[i] < pivot) {
            pivotIndex++;[arr[pivotIndex], arr[i]] = [arr[i], arr[pivotIndex]];}}[arr[start], arr[pivotIndex]] = [arr[pivotIndex], arr[start]];}function quickSort(arr: number[], start = 0, end = arr.length - 1) {if (left < right) {const pivot = pivot(arr, start, end);// leftquickSort(arr, start, pivotIndex - 1);// rightquickSort(arr, pivotIndex + 1, end);}return arr;}

// get the actual number at the given indexfunction getDigit(num: number, i: number): number {return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;}// get number lengthfunction digitCount(num: number): number {if (num === 0) return 1;return Math.floor(Math.log10(Math.abs(num))) + 1;}// return number by most lengthfunction mostDigits(arr: number[]): number {let maxDigits = 0;for (let i = 0; i < arr.length; i++) {
        maxDigits = Math.max(maxDigits, digitCount(arr[i]));}return maxDigits;}function radixSort(arr: number[]): number[] {let maxDigitCount = mostDigits(arr);for (let k = 0; k < maxDigitCount; k++) {let digitBuckets = Array.from({ length: 10 }, () => []);for (let j = 0; j < arr.length; j++) {
            digitBuckets[getDigit(arr[j], k)].push(arr[j]);}

        arr = [].concat(...digitBuckets);}return arr;}

class _Node {constructor(public value: any) {}public next: _Node | null = null;}class SinglyLinkedList {private _length: number = 0;private head: _Node | null = null;private tail: _Node | null = null;get length() {return this._length;}get print(): null | _Node[] {if (!this._length) return null;const arr = [];let currentNode = this.head;while (currentNode) {
            arr.push(currentNode.value);
            currentNode = currentNode.next;}return arr;}public push(value: any): SinglyLinkedList {const node = new _Node(value);if (!this.head || !this.tail) {this.head = node;this.tail = this.head;} else {this.tail.next = node;this.tail = node;}this._length += 1;return this;}public pop(): _Node | null {if (!this.head) return null;let currentNode = this.head;if (!currentNode.next) {this.head = null;this.tail = null;this._length -= 1;return currentNode;}while (currentNode.next && currentNode.next.next) {
            currentNode = currentNode.next;}this.tail = currentNode;this.tail.next = null;this._length -= 1;return currentNode.next as _Node;}public unShift(value: any): SinglyLinkedList {const currentHead = this.head;this.head = new _Node(value);if (currentHead) {this.head.next = currentHead;} else {this.tail = this.head;}this._length += 1;return this;}public shift(): _Node | null {if (!this.head) return null;const currentHead = this.head;this.head = currentHead.next;this._length -= 1;if (currentHead === this.tail) this.tail = null;return currentHead;}public get(index: number): _Node | null {if (index < 0 || index >= this._length) return null;let currentNode = this.head;for (let j = 0; j < index; j++) {if (currentNode && currentNode.next) {
                currentNode = currentNode.next;}}return currentNode;}public set(index: number, value: any): _Node | null {const node = this.get(index);if (node) {
            node.value = value;}return node;}public insert(index: number, value: any): SinglyLinkedList | null {if (index < 0 || index >= this._length) {return null;} else if (index === 0) {return this.unShift(value);} else if (index === this._length) {return this.push(value);} else {const prevNode = this.get(index - 1);if (prevNode) {const newNode = new _Node(value);
                newNode.next = prevNode.next;
                prevNode.next = newNode;this._length += 1;return this;}return prevNode;}}public remove(index: number): _Node | null {if (index === 0) {return this.shift();} else if (index === this._length - 1) {return this.pop();} else {const prevNode = this.get(index - 1);const currentNode = this.get(index);if (prevNode && currentNode) {
                prevNode.next = currentNode.next;this._length -= 1;}return currentNode;}}public reverse(): SinglyLinkedList | false {if (this._length <= 1) return false;let node = this.head;this.head = this.tail;this.tail = node;let next: _Node | null;let prev: _Node | null = null;for (let i = 0; i < this._length; i++) {if (node) {
                next = node.next;
                node.next = prev;
                prev = node;
                node = next;}}return this;}}

class _Node {public next: _Node | null = null;public prev: _Node | null = null;constructor(public value: any) {}}class DoublyLinkedList {private head: _Node | null = null;private tail: _Node | null = null;private _length = 0;get length() {return this._length;}get print(): null | _Node[] {if (!this._length) return null;const arr = [];let currentNode = this.head;while (currentNode) {
            arr.push(currentNode.value);
            currentNode = currentNode.next;}return arr;}public push(value: any): DoublyLinkedList {const node = new _Node(value);if (!this.tail) {this.head = node;} else {this.tail.next = node;
            node.prev = this.tail;}this._length += 1;this.tail = node;return this;}public pop(): _Node | null {if (!this.tail) {return null;}const currentTail = this.tail;if (currentTail.prev) {this.tail = currentTail.prev;this.tail.next = null;
            currentTail.prev = null;} else {this.head = null;this.tail = null;}this._length -= 1;return currentTail;}public shift(): null | _Node {if (!this.head) {return null;}const currentHead = this.head;if (currentHead.next) {this.head = currentHead.next;this.head.prev = null;
            currentHead.next = null;} else {return this.pop();}this._length -= 1;return currentHead;}public unshift(value: any): DoublyLinkedList {if (!this.head) {return this.push(value);}const node = new _Node(value);const currentHead = this.head;this.head = node;this.head.next = currentHead;
        currentHead.prev = this.head;this._length += 1;return this;}public get(index: number): null | _Node {if (index < 0 || index >= this._length) return null;let currentNode: _Node | null = null;if (index < Math.floor(this._length / 2)) {// iterate from head to tail

            currentNode = this.head;for (let i = 0; i < index; i++) {if (currentNode && currentNode.next) {
                    currentNode = currentNode.next;}}} else {// iterate from tail to head

            currentNode = this.tail;for (let i = this._length - 1; i > index; i--) {if (currentNode && currentNode.prev) {
                    currentNode = currentNode.prev;}return currentNode;}}return currentNode;}public set(index: number, value: any): _Node | null {const node = this.get(index);if (node) {
            node.value = value;}return node;}public insert(index: number, value: any): DoublyLinkedList | null {if (index < 0 || index > this._length) {return null;} else if (index === 0) {return this.unshift(value);} else if (index === this._length) {return this.push(value);} else {const prevNode = this.get(index - 1);const nextNode = this.get(index);if (prevNode && nextNode) {const newNode = new _Node(value);

                prevNode.next = newNode;(newNode.prev = prevNode), (newNode.next = nextNode);
                nextNode.prev = newNode;}}this._length += 1;return this;}public remove(index: number): DoublyLinkedList | null {if (index < 0 || index > this._length) {return null;} else if (index === 0) {this.shift();} else if (index === this._length - 1) {this.pop();} else {const node = this.get(index);if (node && node.prev && node.next) {(node.prev.next = node.next), (node.next.prev = node.prev);(node.next = null), (node.prev = null);}this._length -= 1;}return this;}}

// implement stack using arrayconst stack = [1, 2, 3];
stack.push(4); // [1,2,3,4]
stack.pop(); // [1,2,3]// stacks just have push and pop
stack.unshift(0); // [0,1,2,3]
stack.shift(); // [1,2,3]

// implementing stack using singly linked listclass _Node {public next: _Node | null = null;constructor(public value: any) {}}class Stack {private first: _Node | null = null;private last: _Node | null = null;private _length = 0;get length(): number {return this._length;}push(value: any): Stack {const node = new _Node(value);const currentFirst = this.first;(this.first = node), (this.first.next = currentFirst);if (!currentFirst) {this.last = node;}this._length += 1;return this;}pop(): _Node | null {const currentFirst = this.first;if (currentFirst) {if (this.first === this.last) this.last = currentFirst.next;this.first = currentFirst.next;this._length -= 1;}return currentFirst;}}

// implementing queue using arrayconst q = [];
q.push(1);
q.push(2);
q.shift(1); // out first items first// or
q.shift(1);
q.shift(2);
q.pop(); // out first items first

// implementing queue using singly linked listclass _Node {public next: _Node | null = null;constructor(public value: any) {}}class Queue {private first: _Node | null = null;private last: _Node | null = null;private _length = 0;get length(): number {return this._length;}enqueue(value: any): Queue {const node = new _Node(value);if (!this.last) {(this.first = node), (this.last = node);} else {this.last.next = node;this.last = node;}this._length += 1;return this;}dequeue(): _Node | null {const currentFirst = this.first;if (currentFirst) {if (this.first === this.last) this.last = null;this.first = currentFirst.next;this._length -= 1;}return currentFirst;}}

class _Node {constructor(public value: number) {}public left: _Node | null = null;public right: _Node | null = null;}class BinarySearchTree {public root: _Node | null = null;public insert(value: number): BinarySearchTree | null {const node = new _Node(value);if (!this.root) {this.root = node;} else {let currentNode: _Node = this.root;do {if (value === currentNode.value) return null;if (value < currentNode.value) {if (currentNode.left) {
                        currentNode = currentNode.left;} else {
                        currentNode.left = node;break;}} else {if (currentNode.right) {
                        currentNode = currentNode.right;} else {
                        currentNode.right = node;break;}}} while (currentNode);}return this;}public have(value: number): boolean {let currentNode = this.root;while (currentNode) {if (value === currentNode.value) {return true;} else {if (value < currentNode.value) {if (currentNode.left) {
                        currentNode = currentNode.left;continue;}break;} else {if (currentNode.right) {
                        currentNode = currentNode.right;continue;}break;}}}return false;}}

class _Node {constructor(public value: number) {}public left: _Node | null = null;public right: _Node | null = null;}class BinarySearchTree {public root: _Node | null = null;public insert(value: number): BinarySearchTree | null {const node = new _Node(value);if (!this.root) {this.root = node;} else {let currentNode: _Node = this.root;do {if (value === currentNode.value) return null;if (value < currentNode.value) {if (currentNode.left) {
                        currentNode = currentNode.left;} else {
                        currentNode.left = node;break;}} else {if (currentNode.right) {
                        currentNode = currentNode.right;} else {
                        currentNode.right = node;break;}}} while (currentNode);}return this;}public have(value: number): boolean {let currentNode = this.root;while (currentNode) {if (value === currentNode.value) {return true;} else {if (value < currentNode.value) {if (currentNode.left) {
                        currentNode = currentNode.left;}break;} else {if (currentNode.right) {
                        currentNode = currentNode.right;continue;}break;}}}return false;}/*
    breadth first search (bfs) : traverse tree horizontally
*/public bfs(): _Node[] {const visited: _Node[] = [];if (this.root) {const q: _Node[] = [this.root];while (q.length) {if (q[0].left) q.push(q[0].left);if (q[0].right) q.push(q[0].right);

                visited.push(q[0]), q.shift();}}return visited;}/*
    depth first search (dfs) : traverse tree vertically
    following contains three dfs searching methods:
    1. preOrder : add node => going to left and add left => going to right and add right
    2. postOrder : going to left and add left => going to right and add right => going to node and add node
    3. inOrder : going to the left and add left => add node => going to the right and add right
     */public dfsPreOrder(): _Node[] {const visited: _Node[] = [];if (this.root) {(function traverse(node: _Node): void {
                visited.push(node);if (node.left) {traverse(node.left);}if (node.right) {traverse(node.right);}})(this.root);}return visited;}public dfsPostOrder(): _Node[] {const visited: _Node[] = [];if (this.root) {(function traverse(node: _Node): void {if (node.left) {traverse(node.left);}if (node.right) {traverse(node.right);}

                visited.push(node);})(this.root);}return visited;}dfsInOrder(): _Node[] {const visited: _Node[] = [];if (this.root) {(function traverse(node: _Node) {if (node.left) {traverse(node.left);}

                visited.push(node);
                f;if (node.right) {traverse(node.right);}})(this.root);}return visited;}}

class MaxBinaryHeap {private _values: number[] = [];get values(): number[] {return this._values;}private sinkingUp(value: number): void {let valueIndex = this._values.length - 1;while (valueIndex > 0) {const parentIndex = Math.floor((valueIndex - 1) / 2);const parent = this._values[parentIndex];if (value <= parent) break;this._values[parentIndex] = value;this._values[valueIndex] = parent;

            valueIndex = parentIndex;}}private sinkingDown(): void {let targetIndex = 0;while (true) {let leftChildIndex = targetIndex * 2 + 1,
                rightChildIndex = targetIndex * 2 + 2;let target = this._values[targetIndex],
                leftChild = this._values[leftChildIndex],
                rightChild = this._values[rightChildIndex];if (target < leftChild && target < rightChild) {if (rightChild > leftChild) {[this._values[targetIndex],this._values[rightChildIndex]] = [this._values[rightChildIndex],this._values[targetIndex]];

                    targetIndex = rightChildIndex;} else {[this._values[targetIndex],this._values[leftChildIndex]] = [this._values[leftChildIndex],this._values[targetIndex]];

                    targetIndex = leftChildIndex;}continue;} else if (rightChild >= target) {[this._values[targetIndex], this._values[rightChildIndex]] = [this._values[rightChildIndex],this._values[targetIndex]];

                targetIndex = leftChildIndex;continue;} else if (leftChild >= target) {[this._values[targetIndex], this._values[leftChildIndex]] = [this._values[leftChildIndex],this._values[targetIndex]];

                targetIndex = leftChildIndex;continue;}break;}}public insert(value: number): number[] {this._values.push(value);this.sinkingUp(value);return this._values;}public extractMax(): number | null {if (!this._values.length) {return null;}const root = this._values[0];this._values[0] = this._values[this._values.length - 1];this._values.pop();this.sinkingDown();return root;}}

interface INode {value: any;priority: number;}class _Node implements INode {constructor(public value: any, public priority: number = 0) {}}class PriorityQueue {private _values: INode[] = [];get values(): INode[] {return this._values;}private sinkingUp(node: INode): void {let valueIndex = this._values.length - 1;while (valueIndex > 0) {const parentIndex = Math.floor((valueIndex - 1) / 2);const parent = this._values[parentIndex];if (node.priority >= parent.priority) break;this._values[parentIndex] = node;this._values[valueIndex] = parent;

            valueIndex = parentIndex;}}private sinkingDown(): void {let targetIndex = 0;while (true) {let leftChildIndex = targetIndex * 2 + 1,
                rightChildIndex = targetIndex * 2 + 2;let target = this._values[targetIndex],
                leftChild = this._values[leftChildIndex],
                rightChild = this._values[rightChildIndex];if (
                leftChild &&
                rightChild &&
                target.priority > leftChild.priority &&
                target.priority > rightChild.priority
            ) {if (rightChild.priority < leftChild.priority) {[this._values[targetIndex],this._values[rightChildIndex]] = [this._values[rightChildIndex],this._values[targetIndex]];

                    targetIndex = rightChildIndex;} else {[this._values[targetIndex],this._values[leftChildIndex]] = [this._values[leftChildIndex],this._values[targetIndex]];

                    targetIndex = leftChildIndex;}continue;} else if (rightChild && rightChild.priority <= target.priority) {[this._values[targetIndex], this._values[rightChildIndex]] = [this._values[rightChildIndex],this._values[targetIndex]];

                targetIndex = leftChildIndex;continue;} else if (leftChild && leftChild.priority <= target.priority) {[this._values[targetIndex], this._values[leftChildIndex]] = [this._values[leftChildIndex],this._values[targetIndex]];

                targetIndex = leftChildIndex;continue;}break;}}public enqueue({ value, priority }: INode): _Node[] {const node = new _Node(value, priority);this._values.push(node);this.sinkingUp(node);return this._values;}public dequeue(): _Node | null {if (!this._values.length) {return null;}const root = this._values[0];this._values[0] = this._values[this._values.length - 1];this._values.pop();this.sinkingDown();return root;}}

type El = [string, any];class HashTable {private keyMap: El[][];constructor(size: number = 53) {this.keyMap = new Array(size);}public _hash(key: string): number {let total = 0;const WEIRD_PRIME = 31;for (let i = 0; i < key.length; i++) {const characterCode = key.charCodeAt(i) - 96;
            total = (total + characterCode * WEIRD_PRIME) % this.keyMap.length;}return total;}set(key: string, value: any): El[][] {const index = this._hash(key);if (!this.keyMap[index]) {this.keyMap[index] = [];}this.keyMap[index].push([key, value]);return this.keyMap;}get(key: string): El | undefined {const index = this._hash(key);const elements = this.keyMap[index];if (elements) {for (let value of elements) {if (value[0] === key) return value[1];}}return undefined;}get keys(): string[] {const keys: string[] = [];for (let value of this.keyMap) {if (value) {for (let _value of value) {
                    keys.push(_value[0]);}}}return keys;}get values(): any[] {const values = new Set<any>();for (let value of this.keyMap) {if (value) {for (let _value of value) {
                    values.add(value[1]);}}}return [...values];}}

interface AdjacencyList {[vertex: string]: string[];}class Graph {private _adjacencyList: AdjacencyList = {};public get adjacencyList(): AdjacencyList {return this._adjacencyList;}public set adjacencyList(value: AdjacencyList) {this._adjacencyList = value;}public addVertex(vertex: string): AdjacencyList {this._adjacencyList[vertex] = [];return this._adjacencyList;}public addEdge(vertex1: string, vertex2: string): boolean {if (this._adjacencyList[vertex1] && this._adjacencyList[vertex2]) {this._adjacencyList[vertex1].push(vertex2),this._adjacencyList[vertex2].push(vertex1);return true;}return false;}public removeEdge(vertex1: string, vertex2: string): boolean {if (this._adjacencyList[vertex1] && this._adjacencyList[vertex2]) {(this._adjacencyList[vertex1] = this._adjacencyList[vertex1].filter((value: string) => value !== vertex2
            )),(this._adjacencyList[vertex2] = this._adjacencyList[
                    vertex2
                ].filter((value: string) => value !== vertex1));return true;}return false;}public removeVertex(vertex: string): string | undefined {if (this._adjacencyList[vertex]) {for (let key in this._adjacencyList) {this.removeEdge(key, vertex);}delete this._adjacencyList[vertex];return vertex;}return undefined;}}

interface AdjacencyList {[vertex: string]: string[];}class Graph {private _adjacencyList: AdjacencyList = {};public get adjacencyList(): AdjacencyList {return this._adjacencyList;}public set adjacencyList(value: AdjacencyList) {this._adjacencyList = value;}public addVertex(vertex: string): AdjacencyList {this._adjacencyList[vertex] = [];return this._adjacencyList;}public addEdge(vertex1: string, vertex2: string): boolean {if (this._adjacencyList[vertex1] && this._adjacencyList[vertex2]) {this._adjacencyList[vertex1].push(vertex2),this._adjacencyList[vertex2].push(vertex1);return true;}return false;}public removeEdge(vertex1: string, vertex2: string): boolean {if (this._adjacencyList[vertex1] && this._adjacencyList[vertex2]) {(this._adjacencyList[vertex1] = this._adjacencyList[vertex1].filter((value: string) => value !== vertex2
            )),(this._adjacencyList[vertex2] = this._adjacencyList[
                    vertex2
                ].filter((value: string) => value !== vertex1));return true;}return false;}public removeVertex(vertex: string): string | undefined {if (this._adjacencyList[vertex]) {for (let key in this._adjacencyList) {this.removeEdge(key, vertex);}delete this._adjacencyList[vertex];return vertex;}return undefined;}public dfcRecursive(startingVertex: string): string[] {const results: string[] = [];const adjacencyList = this._adjacencyList;let currentVertex = this._adjacencyList[startingVertex];if (currentVertex) {const visitedVertex: { [vertex: string]: boolean } = {};(function traverse(vertex: string | undefined): void {if (!vertex) return;if (!visitedVertex[vertex]) {
                    visitedVertex[vertex] = true;
                    results.push(vertex);for (let neighbor of currentVertex) {if (!visitedVertex[neighbor]) {
                            currentVertex = adjacencyList[neighbor];traverse(neighbor);}}}})(startingVertex);}return results;}// orpublic dfsIterative(startingVertex: string): string[] {const results: string[] = [];if (this._adjacencyList[startingVertex]) {let stack: string[] = [startingVertex];const visitedVertex: { [vertex: string]: boolean } = {};while (stack.length) {debugger;const currentVertex = stack.pop();if (currentVertex && !visitedVertex[currentVertex]) {
                    visitedVertex[currentVertex] = true;
                    results.push(currentVertex);
                    stack = [...stack, ...this._adjacencyList[currentVertex]];}}}return results;}public breadthFirstSearch(startingVertex: string): string[] {const results: string[] = [];if (this._adjacencyList[startingVertex]) {let queue = [startingVertex];const visitedVertex: { [vertex: string]: boolean } = {};while (queue.length) {const currentVertex = queue.shift();if (currentVertex && !visitedVertex[currentVertex]) {
                    visitedVertex[currentVertex] = true;
                    results.push(currentVertex);
                    queue = [...queue, ...this._adjacencyList[currentVertex]];}}}return results;}}

interface Value {value: any;priority: number;}interface Neighbor {vertex: string;weight: number;}interface AdjacencyList {[vertex: string]: Neighbor[];}// naive priority queueclass PriorityQueue {private _values: Value[] = [];public get values(): Value[] {return this._values;}public enqueue(value: any, priority: number): Value[] {this._values.push({ value, priority });this.sort();return this._values;}public dequeue(): Value {const value = this._values.shift();return value as Value;}private sort() {this._values.sort((a: Value, b: Value) => a.priority - b.priority);}}class WeightedGraph {private _adjacencyList: AdjacencyList = {};public get adjacencyList(): AdjacencyList {return this._adjacencyList;}public set adjacencyList(value: AdjacencyList) {this._adjacencyList = value;}public addVertex(vertex: string): AdjacencyList {this._adjacencyList[vertex] = [];return this._adjacencyList;}public addEdge(vertex1: string, vertex2: string, weight: number): boolean {if (this._adjacencyList[vertex1]) {this._adjacencyList[vertex1].push({ vertex: vertex2, weight });this._adjacencyList[vertex2].push({ vertex: vertex1, weight });return true;}return false;}/*
    dijkstra shortest path first
    */dijkstraSPF(startingVertex: string, targetVertex: string): string[] {let path: string[] = [];if (this._adjacencyList[startingVertex] &&this._adjacencyList[targetVertex]) {const pq = new PriorityQueue();const previousVertex: { [vertex: string]: string | null } = {};const distances: { [vertex: string]: number } = {};// build initial statesfor (let key in this._adjacencyList) {if (key === startingVertex) {(distances[key] = 0), pq.enqueue(key, 0);} else {
                    distances[key] = Infinity;
                    pq.enqueue(key, Infinity);}
                previousVertex[key] = null;}while (pq.values.length) {let smallest = pq.dequeue().value;if (smallest) {if (smallest === targetVertex) {// done build pathwhile (
                            previousVertex[smallest] ||
                            smallest === startingVertex
                        ) {
                            path.push(smallest);
                            smallest = previousVertex[smallest];}break;}for (let neighbor of this._adjacencyList[smallest]) {const candidate = distances[smallest] + neighbor.weight;let nextNeighbor = neighbor.vertex;if (candidate < distances[nextNeighbor]) {
                            distances[nextNeighbor] = candidate;

                            previousVertex[nextNeighbor] = smallest;

                            pq.enqueue(nextNeighbor, candidate);}}}}}return path.reverse();}}