Toolbox of software design pattern, algorithms and typical problems
Toolbox of software data structures, design patterns, algorithms and typical problems. Repo includes swift and typescript examples (add other languages if you feel so). Part of Develepor’s toolbox series: link.
swift
func bubbleSort(numbers: [Int]) -> [Int] {
var sortedNumbers = numbers
for i in 0..<sortedNumbers.count {
for j in 1..<sortedNumbers.count-i {
if sortedNumbers[j - 1] > sortedNumbers[j] {
sortedNumbers.swapAt(j - 1, j)
}
}
}
return sortedNumbers
}
let numbers = [5, 15, 14, 1, 26, 0, 99]
print(bubbleSort(numbers: numbers))
[0, 1, 5, 14, 15, 26, 99]
typescript
function bubbleSort(numbers: number[]): number[] {
let sortedNumbers = numbers;
for (let i = 0; i < sortedNumbers.length; i++) {
for (let j = 1; j < sortedNumbers.length; j++) {
if (sortedNumbers[j - 1] > sortedNumbers[j]) {
const temp = sortedNumbers[j - 1];
sortedNumbers[j - 1] = sortedNumbers[j];
sortedNumbers[j] = temp;
}
}
}
return sortedNumbers;
}
const numbers = [5, 15, 14, 1, 26, 0, 99];
console.log(bubbleSort(numbers));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
func insertionSort(numbers: [Int]) -> [Int] {
var sortedNumbers = numbers
for i in 0..<sortedNumbers.count {
let val = sortedNumbers[i]
for j in 0..<i {
if sortedNumbers[j] > sortedNumbers[i] {
sortedNumbers.remove(at: i)
sortedNumbers.insert(val, at: j)
}
}
}
return sortedNumbers
}
let numbers = [5, 15, 14, 1, 26, 0, 99]
print(insertionSort(numbers: numbers))
[0, 1, 5, 14, 15, 26, 99]
typescript
function insertionSort(numbers: number[]): number[] {
let sortedNumbers = numbers;
for (let i = 1; i < sortedNumbers.length; i++) {
let value = sortedNumbers[i];
let position = i;
while (position > 0 && sortedNumbers[position - 1] > value) {
numbers[position] = numbers[position - 1];
position -= 1;
}
numbers[position] = value;
}
return sortedNumbers;
}
function insertionSort2(arr: number[]): number[] {
for (let i = 1; i < arr.length; i++) {
for (let sortedJ = 0; sortedJ <= i; sortedJ++) {
if (arr[i] < arr[sortedJ]) {
const t = arr[i];
arr.splice(i, 1);
arr.splice(sortedJ, 0, t);
}
}
}
return arr;
}
const unsortedArray = [5, 15, 14, 1, 26, 0, 99];
console.log(insertionSort(unsortedArray));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
func selectionSort(numbers: [Int]) -> [Int] {
var sortedNumbers = numbers
for i in 0..<sortedNumbers.count-1 {
var minIndex = i
for j in i..<sortedNumbers.count {
if sortedNumbers[j] < sortedNumbers[minIndex] {
minIndex = j
}
}
let temp = sortedNumbers[minIndex]
sortedNumbers[minIndex] = sortedNumbers[i]
sortedNumbers[i] = temp
}
return sortedNumbers
}
let numbers = [5, 15, 14, 1, 26, 0, 99]
print(selectionSort(numbers: numbers))
[0, 1, 5, 14, 15, 26, 99]
typescript
function selectionSort(numbers: number[]): number[] {
let sortedNumbers = numbers;
for (let i = 0; i < sortedNumbers.length - 1; i++) {
let minValueIndex = i;
for (let j = i + 1; j < sortedNumbers.length; j++) {
if (sortedNumbers[j] < sortedNumbers[minValueIndex]) {
minValueIndex = j;
}
}
const temp = sortedNumbers[minValueIndex];
sortedNumbers[minValueIndex] = sortedNumbers[i];
sortedNumbers[i] = temp;
}
return sortedNumbers;
}
const unsortedArray = [5, 15, 14, 1, 26, 0, 99];
console.log(selectionSort(unsortedArray));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
func mergeSort(numbers: [Int]) -> [Int] {
// If only one element - already sorted.
if numbers.count == 1 {
return numbers
}
// First, divide the list into equal-sized sublists
// consisting of the first half and second half of the list.
let iMiddle = numbers.count/2
let left = mergeSort(numbers: Array(numbers[0..<iMiddle]))
let right = mergeSort(numbers: Array(numbers[iMiddle..<numbers.count]))
// Recursively sort both sublists.
return compareAndMerge(left: left, right: right)
}
func compareAndMerge(left: [Int], right:[Int]) -> [Int] {
var leftIndex = 0
var rightIndex = 0
var ordered: [Int] = []
while leftIndex < left.count && rightIndex < right.count {
if left[leftIndex] < right[rightIndex] {
ordered.append(left[leftIndex])
leftIndex += 1
} else {
ordered.append(right[rightIndex])
rightIndex += 1
}
}
// Going through leftovers
ordered += Array(left[leftIndex..<left.count])
ordered += Array(right[rightIndex..<right.count])
return ordered
}
var numbers = [5, 15, 14, 1, 26, 0, 99]
print(mergeSort(numbers: numbers))
[0, 1, 5, 14, 15, 26, 99]
typescript
function mergeSort(numbers: number[]): number[] {
// If only one element - already sorted.
if (numbers.length === 1) {
return numbers;
}
// First, divide the list into equal-sized sublists
// consisting of the first half and second half of the list.
const iMiddle = Math.floor(numbers.length / 2);
const leftArray = [];
numbers.forEach((el, index) => {
if (0 <= index && index < iMiddle) {
leftArray.push(el);
}
});
const rightArray = [];
numbers.forEach((el, index) => {
if (iMiddle <= index && index <= numbers.length) {
rightArray.push(el);
}
});
const left = mergeSort(leftArray);
const right = mergeSort(rightArray);
// Recursively sort both sublists.
return compareAndMerge(left, right);
}
function compareAndMerge(left: number[], right: number[]): number[] {
let ordered = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
ordered.push(left[leftIndex]);
leftIndex++;
} else {
ordered.push(right[rightIndex]);
rightIndex++;
}
}
// Going through leftovers
left.forEach((el, index) => {
if (leftIndex <= index && index <= left.length) {
ordered.push(el);
}
});
right.forEach((el, index) => {
if (rightIndex <= index && index <= right.length) {
ordered.push(el);
}
});
return ordered;
}
const unsortedArrayOfNumbers = [5, 15, 14, 1, 26, 0, 99];
console.log(mergeSort(unsortedArrayOfNumbers));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
func quickSortLomuto(_ numbers: inout [Int], left: Int, right: Int) -> [Int] {
// Recursive, in-place version that uses Lomuto's scheme.
if left < right {
let p = lomutoPartion(&numbers, left: left, right: right)
quickSortLomuto(&numbers, left: left, right: p - 1)
quickSortLomuto(&numbers, left: p + 1, right: right)
}
return numbers
}
func lomutoPartion(_ numbers: inout [Int], left: Int, right: Int) -> Int {
// We use the biggest item as the pivot.
let pivotValue = numbers[right]
// And begin from the smallest left value.
var storeIndex = left
// Partitioning array into four regions:
// [low..i] where values are <= than pivot
// [i+1..j-1] where values are > than pivot
// [j..high-1] values that we haven't looked at yet
// [high] is the pivot.
for i in left..<right {
if numbers[i] < pivotValue {
(numbers[i], numbers[storeIndex]) = (numbers[storeIndex], numbers[i])
storeIndex += 1
}
}
(numbers[storeIndex], numbers[right]) = (numbers[right], numbers[storeIndex])
return storeIndex
}
var numbers = [5, 15, 14, 1, 26, 0, 99]
print(quickSortLomuto(&numbers, left: 0, right: numbers.count-1))
[0, 1, 5, 14, 15, 26, 99]
typescript
function quickSortLomuto(numbers: number[], left: number, right: number): number[] {
// Recursive, in-place version that uses Lomuto's scheme.
if (left < right) {
let p = lomutoParition(numbers, left, right);
quickSortLomuto(numbers, left, p - 1);
quickSortLomuto(numbers, p + 1, right);
}
return numbers;
}
function lomutoParition(numbers: number[], left: number, right: number): number {
// We use the biggest item as the pivot.
const pivotValue = numbers[right];
// And begin from the smallest left value.
let storeIndex = left;
// Partitioning array into four regions:
// [low..i] where values are <= than pivot
// [i+1..j-1] where values are > than pivot
// [j..high-1] values that we haven't looked at yet
// [high] is the pivot.
for (let i = left; i < right; i++) {
if (numbers[i] < pivotValue) {
[numbers[i], numbers[storeIndex]] = [numbers[storeIndex], numbers[i]];
storeIndex++;
}
}
[numbers[storeIndex], numbers[right]] = [numbers[right], numbers[storeIndex]];
return storeIndex;
}
const arrayToSort = [5, 15, 14, 1, 26, 0, 99];
console.log(quickSortLomuto(arrayToSort, 0, arrayToSort.length - 1));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
func selectionSort(numbers: [Int]) -> [Int] {
var sortedNumbers = numbers
for i in 0..<sortedNumbers.count-1 {
var minIndex = i
for j in i..<sortedNumbers.count {
if sortedNumbers[j] < sortedNumbers[minIndex] {
minIndex = j
}
}
let temp = sortedNumbers[minIndex]
sortedNumbers[minIndex] = sortedNumbers[i]
sortedNumbers[i] = temp
}
return sortedNumbers
}
let numbers = [5, 15, 14, 1, 26, 0, 99]
print(selectionSort(numbers: numbers))
[0, 1, 5, 14, 15, 26, 99]
typescript
function selectionSort(numbers: number[]): number[] {
let sortedNumbers = numbers;
for (let i = 0; i < sortedNumbers.length - 1; i++) {
let minValueIndex = i;
for (let j = i + 1; j < sortedNumbers.length; j++) {
if (sortedNumbers[j] < sortedNumbers[minValueIndex]) {
minValueIndex = j;
}
}
const temp = sortedNumbers[minValueIndex];
sortedNumbers[minValueIndex] = sortedNumbers[i];
sortedNumbers[i] = temp;
}
return sortedNumbers;
}
const unsortedArray = [5, 15, 14, 1, 26, 0, 99];
console.log(selectionSort(unsortedArray));
[ 0, 1, 5, 14, 15, 26, 99 ]
swift
class Node {
var value: Int?
var next: Node?
}
class LinkedList {
var head: Node?
func insert(value: Int) {
print("Inserting: \(value)")
if var iteratingHead = self.head {
while(iteratingHead.next != nil) {
iteratingHead = iteratingHead.next!
}
iteratingHead.next = Node()
iteratingHead.next?.value = value
}
else {
self.head = Node()
self.head?.value = value
}
}
func remove(value: Int) {
print("Removing: \(value)")
if var iteratingHead = self.head {
var lastNode = self.head!
while(iteratingHead.value != value && iteratingHead.next != nil) {
lastNode = iteratingHead
iteratingHead = iteratingHead.next!
}
if iteratingHead.value == value {
if iteratingHead.next != nil {
lastNode.value = nil
lastNode.next = iteratingHead.next
}
else {
lastNode.next = nil
}
}
}
else {
print("It looks like list is not initilezed yet.")
}
}
func printAll() {
print("Printing values:")
if var iteratingHead = head {
while(iteratingHead.next != nil) {
print(iteratingHead.value ?? 0)
iteratingHead = iteratingHead.next!
}
print(iteratingHead.value ?? 0)
} else {
print("List is empty.")
}
print("---")
}
}
var list = LinkedList()
list.printAll()
list.insert(value: 22)
list.insert(value: 33)
list.insert(value: 44)
list.insert(value: 55)
list.insert(value: 66)
list.printAll()
list.remove(value: 33)
list.remove(value: 66)
list.printAll()
list.remove(value: 22)
list.remove(value: 44)
list.remove(value: 55)
list.remove(value: 66)
list.printAll()
Printing values:
List is empty.
---
Inserting: 22
Inserting: 33
Inserting: 44
Inserting: 55
Inserting: 66
Printing values:
22
33
44
55
66
---
Removing: 33
Removing: 66
Printing values:
44
55
66
---
Removing: 22
Removing: 44
Removing: 55
Removing: 66
Printing values:
---
typescript
class LinkedListNode {
public value: number;
public next: LinkedListNode;
}
class LinkedList {
public head: LinkedListNode;
public insert(value: number): void {
console.log(`Inserting: ${value}`);
let iteratingHead = this.head;
if (iteratingHead != null) {
while (iteratingHead.next != null) {
iteratingHead = iteratingHead.next;
}
iteratingHead.next = new LinkedListNode();
iteratingHead.next.value = value;
} else {
this.head = new LinkedListNode();
this.head.value = value;
}
}
public remove(value: number): void {
console.log(`Removing: ${value}`);
let iteratingHead = this.head;
if (iteratingHead != null) {
let lastNode = iteratingHead;
while (iteratingHead.next != null && iteratingHead.next.value === value) {
lastNode = iteratingHead;
iteratingHead = iteratingHead.next;
}
if (iteratingHead.value === value) {
if (iteratingHead.next != null) {
lastNode.value = null;
lastNode.next = iteratingHead.next;
} else {
lastNode.next = null;
}
}
} else {
console.log("It looks like list is not initilezed yet.");
}
}
public printAll(): void {
console.log("Printing values:");
let iteratingHead = this.head;
if (iteratingHead != null) {
while (iteratingHead.next != null) {
if (iteratingHead.value != null) {
console.log(iteratingHead.value);
}
iteratingHead = iteratingHead.next;
}
if (iteratingHead.value != null) {
console.log(iteratingHead.value);
}
} else {
console.log("List is empty.");
}
console.log("---");
}
}
const list = new LinkedList();
list.printAll();
list.insert(22);
list.insert(33);
list.insert(44);
list.insert(55);
list.insert(66);
list.printAll();
list.remove(33);
list.remove(66);
list.printAll();
list.remove(22);
list.remove(44);
list.remove(55);
list.remove(66);
list.printAll();
Printing values:
List is empty.
---
Inserting: 22
Inserting: 33
Inserting: 44
Inserting: 55
Inserting: 66
Printing values:
22
33
44
55
66
---
Removing: 33
Removing: 66
Printing values:
44
55
66
---
Removing: 22
Removing: 44
Removing: 55
Removing: 66
Printing values:
---
swift
import Foundation
class QNode {
var value: Int?
var next: QNode?
}
class Queue {
var head: QNode?
var tail: QNode?
func enqueue(value: Int) {
print("Enqueing: \(value)")
let node = QNode()
node.value = value
if tail == nil && head == nil {
head = node
tail = node
} else {
tail?.next = node
tail = node
}
// OR
// if tail == nil {
// tail = node
//
// if head == nil {
// head = tail
// }
// }
// else {
// tail?.next = node
// tail = node
// }
}
func dequeue() -> Int? {
print("Dequeing")
if let iteratingHead = head {
head = iteratingHead.next
if iteratingHead.next == nil {
tail = nil
}
return iteratingHead.value
}
else {
print("It looks like queue is not initilezed yet.")
return nil
}
}
func printAll() {
print("Printing values:")
if var iteratingHead = self.head {
while iteratingHead.next != nil {
print(iteratingHead.value ?? 0)
iteratingHead = iteratingHead.next!
}
print(iteratingHead.value ?? 0)
} else {
print("Queue is empty.")
}
print("---")
}
}
let q = Queue()
q.enqueue(value: 11)
q.enqueue(value: 22)
q.enqueue(value: 33)
q.enqueue(value: 44)
q.enqueue(value: 55)
q.printAll()
q.dequeue()
q.dequeue()
q.printAll()
q.dequeue()
q.dequeue()
q.dequeue()
q.dequeue()
q.printAll()
Enqueing: 11
Enqueing: 22
Enqueing: 33
Enqueing: 44
Enqueing: 55
Printing values:
11
22
33
44
55
---
Dequeing
Dequeing
Printing values:
33
44
55
---
Dequeing
Dequeing
Dequeing
Dequeing
It looks like queue is not initilezed yet.
Printing values:
Queue is empty.
---
typescript
class QNode {
public value: number;
public next: QNode;
}
class Queue {
public head: QNode;
public tail: QNode;
public enqueue(value: number): void {
console.log(`Enqueing: ${value}`);
const node = new QNode();
node.value = value;
if (this.tail == null && this.head == null) {
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
}
public dequeue(): number {
console.log("Dequeing");
let iteratingHead = this.head;
if (iteratingHead != null) {
this.head = iteratingHead.next;
if (iteratingHead.next == null) {
this.tail = null;
}
return iteratingHead.value;
} else {
console.log("It looks like queue is not initilezed yet.");
return 0;
}
}
public printAll(): void {
console.log("Printing values:");
let iteratingHead = this.head;
if (iteratingHead != null) {
while (iteratingHead.next != null) {
if (iteratingHead.value != null) {
console.log(iteratingHead.value);
}
iteratingHead = iteratingHead.next;
}
if (iteratingHead.value != null) {
console.log(iteratingHead.value);
}
} else {
console.log("Queue is empty.");
}
console.log("---");
}
}
let q = new Queue();
q.enqueue(11);
q.enqueue(22);
q.enqueue(33);
q.enqueue(44);
q.enqueue(55);
q.printAll();
q.dequeue();
q.dequeue();
q.printAll();
q.dequeue();
q.dequeue();
q.dequeue();
q.dequeue();
q.printAll();
Enqueing: 11
Enqueing: 22
Enqueing: 33
Enqueing: 44
Enqueing: 55
Printing values:
11
22
33
44
55
---
Dequeing
Dequeing
Printing values:
33
44
55
---
Dequeing
Dequeing
Dequeing
Dequeing
It looks like queue is not initilezed yet.
Printing values:
Queue is empty.
---
swift
class Stack {
var stackArray = [String]()
func push(val: String) {
self.stackArray.append(val)
}
func pop() -> String? {
if self.stackArray.last != nil {
return self.stackArray.removeLast()
}
else{
return "Stack is empty."
}
}
func printValues() {
print(stackArray)
}
}
let stack = Stack()
stack.push(val: "1")
stack.push(val: "2")
stack.push(val: "2")
stack.push(val: "2")
stack.push(val: "3")
stack.push(val: "2")
stack.push(val: "1")
stack.printValues()
print(stack.pop() as Any)
print(stack.pop() as Any)
stack.printValues()
print(stack.pop() as Any)
print(stack.pop() as Any)
print(stack.pop() as Any)
print(stack.pop() as Any)
print(stack.pop() as Any)
print(stack.pop() as Any)
["1", "2", "2", "2", "3", "2", "1"]
Optional("1")
Optional("2")
["1", "2", "2", "2", "3"]
Optional("3")
Optional("2")
Optional("2")
Optional("2")
Optional("1")
Optional("Stack is empty.")
typescript
class Stack {
private stackArray: string[] = [];
public push(val: string): void {
this.stackArray.push(val);
}
public pop(): string {
if (this.stackArray.length !== 0) {
return this.stackArray.splice(this.stackArray.length - 1, 1)[0];
} else {
return "Stack is empty";
}
}
public printValues(): void {
console.log(this.stackArray);
}
}
let stack = new Stack();
stack.push("1");
stack.push("2");
stack.push("2");
stack.push("2");
stack.push("3");
stack.push("2");
stack.push("1");
stack.printValues();
console.log(stack.pop());
console.log(stack.pop());
stack.printValues();
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());
[ '1', '2', '2', '2', '3', '2', '1' ]
1
2
[ '1', '2', '2', '2', '3' ]
3
2
2
2
1
Stack is empty
swift
class TreeNode<T> {
public var value: T
public var parent: TreeNode?
public var children = [TreeNode<T>]()
init(value: T) {
self.value = value
}
public func addChild(node: TreeNode<T>) {
children.append(node)
node.parent = self
}
public func printAll() {
print(value)
children.forEach { node in
node.printAll()
}
}
}
let tree = TreeNode(value: "root")
let black = TreeNode(value: "black")
let red = TreeNode(value: "red")
let blue = TreeNode(value: "blue")
let yellow = TreeNode(value: "yellow")
let white = TreeNode(value: "white")
let pink = TreeNode(value: "pink")
tree.addChild(node: black)
tree.addChild(node: blue)
tree.addChild(node: pink)
black.addChild(node: red)
black.addChild(node: yellow)
red.addChild(node: white)
tree.printAll()
root
black
red
white
yellow
blue
pink
typescript
class TreeNode<T> {
public value: T;
public parent: TreeNode<T>;
public children: TreeNode<T>[] = [];
constructor(value: T) {
this.value = value;
}
public addChild(node: TreeNode<T>): void {
this.children.push(node);
node.parent = this;
}
public printAll(): void {
console.log(this.value);
for (let i in this.children) {
this.children[i].printAll();
}
}
}
const tree = new TreeNode("root");
const black = new TreeNode("black");
const red = new TreeNode("red");
const blue = new TreeNode("blue");
const yellow = new TreeNode("yellow");
const white = new TreeNode("white");
const pink = new TreeNode("pink");
tree.addChild(black);
tree.addChild(blue);
tree.addChild(pink);
black.addChild(red);
black.addChild(yellow);
red.addChild(white);
tree.printAll();
root
black
red
white
yellow
blue
pink
typescript
class TNode {
public val: number;
public left: TNode;
public right: TNode;
}
class BinarySearchTree {
public root: TNode = null;
public addChild(val: number): void {
const newNode = new TNode();
newNode.val = val;
if (this.root == null) {
this.root = newNode;
} else {
let currentNode = this.root;
let traversing = true;
while (traversing) {
if (currentNode.val < newNode.val) {
if (currentNode.left == null) {
currentNode.left = newNode;
traversing = false;
} else {
currentNode = currentNode.left;
}
} else if (currentNode.val > newNode.val) {
if (currentNode.right == null) {
currentNode.right = newNode;
traversing = false;
} else {
currentNode = currentNode.right;
}
}
}
}
}
public preOrder(): void {
console.log("preOrder");
if (this.root != null) {
let numbers: number[] = [];
let currentNode = this.root;
const traverse = (currentNode: TNode) => {
if (currentNode != null) {
numbers.push(currentNode.val);
traverse(currentNode.left);
traverse(currentNode.right);
}
};
traverse(this.root);
console.log(numbers);
} else {
console.log("Tree is empty");
}
}
public inOrder(): void {
console.log("inOrder");
if (this.root != null) {
let numbers: number[] = [];
let currentNode = this.root;
const traverse = (currentNode: TNode) => {
if (currentNode != null) {
traverse(currentNode.left);
numbers.push(currentNode.val);
traverse(currentNode.right);
}
};
traverse(this.root);
console.log(numbers);
} else {
console.log("Tree is empty");
}
}
public postOrder(): void {
console.log("postOrder");
if (this.root != null) {
let numbers: number[] = [];
let currentNode = this.root;
const traverse = (currentNode: TNode) => {
if (currentNode != null) {
traverse(currentNode.left);
traverse(currentNode.right);
numbers.push(currentNode.val);
}
};
traverse(this.root);
console.log(numbers);
} else {
console.log("Tree is empty");
}
}
public breadthFirstSearchTraversal(): void {
console.log("breadthFirstSearchTraversal");
if (this.root != null) {
let numbers: number[] = [];
let qOfNextItems = [this.root];
while (qOfNextItems.length !== 0) {
const currentNode = qOfNextItems[0];
numbers.push(currentNode.val);
if (currentNode.left != null) {
qOfNextItems.push(currentNode.left);
}
if (currentNode.right != null) {
qOfNextItems.push(currentNode.right);
}
qOfNextItems.splice(0, 1);
}
console.log(numbers);
} else {
console.log("Tree is empty");
}
}
}
const bst = new BinarySearchTree();
bst.addChild(10);
bst.addChild(3);
bst.addChild(0);
bst.addChild(8);
bst.addChild(6);
bst.addChild(15);
bst.addChild(11);
bst.addChild(20);
bst.preOrder();
bst.inOrder();
bst.postOrder();
bst.breadthFirstSearchTraversal();
"preOrder"
[10, 15, 20, 11, 3, 8, 6, 0]
"inOrder"
[20, 15, 11, 10, 8, 6, 3, 0]
"postOrder"
[20, 11, 15, 6, 8, 0, 3, 10]
"breadthFirstSearchTraversal"
[10, 15, 3, 20, 11, 8, 0, 6]
typescript
class BinaryMinHeap {
public values: number[] = [];
public insert(val: number): void {
if (this.values.length === 0) {
this.values[0] = val;
} else {
this.values.push(val);
this.bubbleUp();
}
}
private bubbleUp(): void {
let index = this.values.length - 1;
let parentIndex = Math.floor((index - 1) / 2);
let temp;
// Keep looping until the parent node is less than the child node
while (parentIndex >= 0 && this.values[parentIndex] > this.values[index]) {
temp = this.values[index];
this.values[index] = this.values[parentIndex];
this.values[parentIndex] = temp;
index = parentIndex;
parentIndex = Math.floor((index - 1) / 2);
}
}
public extractMin(): number {
if (this.values.length != 0) {
const min = this.values[0];
const end = this.values[this.values.length - 1];
this.values.splice(this.values.length - 1, 1);
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return min;
} else {
return 0;
}
}
private sinkDown(): void {
let parentIdx = 0;
let leftChildIdx = 0;
let rightChildIdx = 0;
let heapLength = this.values.length;
let nodeToSink = this.values[parentIdx];
let idxToSwap = 0;
let swap = false;
// Keep looping through the nodes util you find the right spot
while (true) {
leftChildIdx = 2 * parentIdx + 1;
rightChildIdx = 2 * parentIdx + 2;
swap = false;
let leftChild = null;
let rightChild = null;
// Check with the left child only if it is a valid index
if (leftChildIdx < heapLength) {
leftChild = this.values[leftChildIdx];
// Compare with the node to sink down
if (nodeToSink > leftChild) {
idxToSwap = leftChildIdx;
swap = true;
}
}
// Check with the right child only if it is a valid index
if (rightChildIdx < heapLength) {
rightChild = this.values[rightChildIdx];
if ((swap && leftChild > rightChild) || (!swap && nodeToSink > rightChild)) {
idxToSwap = rightChildIdx;
swap = true;
}
}
if (!swap) {
// If there is no swap required, we found the correct spot for the element
return;
} else {
// Swap the elements
this.values[parentIdx] = this.values[idxToSwap];
this.values[idxToSwap] = nodeToSink;
// Set the reference to index to its new value
parentIdx = idxToSwap;
}
}
}
public printAll(): void {
console.log(this.values);
}
}
const mbh = new BinaryMinHeap();
mbh.insert(2);
mbh.insert(7);
mbh.insert(1);
mbh.insert(0);
mbh.insert(12);
mbh.insert(20);
mbh.insert(25);
mbh.insert(5);
mbh.insert(4);
mbh.printAll();
console.log(mbh.extractMin());
console.log(mbh.extractMin());
console.log(mbh.extractMin());
mbh.printAll();
[0, 1, 2, 4, 12, 20, 25, 7, 5]
0
1
2
[4, 5, 7, 25, 12, 20]
It lets you change the behavior of a class when the state changes.
swift
final class Context {
private var state: State = UnauthorizedState()
var isAuthorized: Bool {
get {
return state.isAuthorized(context: self)
}
}
var userId: String? {
get {
return state.userId(context: self)
}
}
func changeStateToAuthorized(userId: String) {
state = AuthorizedState(userId: userId)
}
func changeStateToUnauthorized() {
state = UnauthorizedState()
}
func printAuthorizationStatus() {
print("Is user authorized: \(userContext.isAuthorized). User id is: \(String(describing: userContext.userId)).")
}
}
protocol State {
func isAuthorized(context: Context) -> Bool
func userId(context: Context) -> String?
}
class UnauthorizedState: State {
func isAuthorized(context: Context) -> Bool {
return false
}
func userId(context: Context) -> String? {
return nil
}
}
class AuthorizedState: State {
let userId: String
init(userId: String) {
self.userId = userId
}
func isAuthorized(context: Context) -> Bool {
return true
}
func userId(context: Context) -> String? {
return userId
}
}
let userContext = Context()
// initial state
userContext.printAuthorizationStatus()
// authorizing as admin
userContext.changeStateToAuthorized(userId: "admin")
// now logged in as "admin"
userContext.printAuthorizationStatus()
// unauthorizing
userContext.changeStateToUnauthorized()
// now logged out
userContext.printAuthorizationStatus()
Is user authorized: false. User id is: nil.
Is user authorized: true. User id is: Optional("admin").
Is user authorized: false. User id is: nil.
typescript
class Context {
private state: State = new UnauthorizedState();
private _isAuthorized: boolean;
get isAuthorized(): boolean {
return this.state.isAuthorized(this);
}
private _userId: string;
get userId(): string {
return this.state.getUserId(this);
}
public changeStateToAuthorized(userId: string) {
this.state = new AuthorizedState(userId);
}
public changeStateToUnauthorized() {
this.state = new UnauthorizedState();
}
public printAuthorizationStatus() {
console.log(`Is user authorized: ${this.isAuthorized}. User id is: ${this.userId}.`);
}
}
interface State {
isAuthorized(context: Context): boolean;
getUserId(context: Context): string;
}
class UnauthorizedState implements State {
public isAuthorized(context: Context): boolean {
return false;
}
public getUserId(context: Context): string {
return `nil`;
}
}
class AuthorizedState implements State {
private userId: string;
constructor(userId: string) {
this.userId = userId;
}
public isAuthorized(context: Context): boolean {
return true;
}
public getUserId(context: Context): string {
return this.userId;
}
}
let userContext = new Context();
// initial state
userContext.printAuthorizationStatus();
// authorizing as admin
userContext.changeStateToAuthorized("admin");
// now logged in as "admin"
userContext.printAuthorizationStatus();
// unauthorizing
userContext.changeStateToUnauthorized();
// now logged out
userContext.printAuthorizationStatus();
Is user authorized: false. User id is: nil.
Is user authorized: true. User id is: admin.
Is user authorized: false. User id is: nil.
Define the basic steps of an algorithm and allow the implementation of the individual steps to be changed.
swift
// Define a template method that contains a skeleton of some algorithm, composed of calls to (usually) primitive operations.
protocol TreeColorFlag {
// The template method defines the skeleton of an algorithm.
func draw()
// These operations have to be implemented in subclasses.
func drawFirstPart()
func drawSecondPart()
func drawThirdPart()
}
extension TreeColorFlag {
func draw() {
log(message: "Starting drawing")
drawFirstPart();
log(message: "First part is done.")
drawSecondPart();
log(message: "Second part is done.")
drawThirdPart();
log(message: "Third part is done.")
}
func log(message: String) {
print(message)
}
func drawFirstPart() {
fatalError("Subclass must implement drawFirstPart")
}
func drawSecondPart() {
fatalError("Subclass must implement drawSecondPart")
}
func drawThirdPart() {
fatalError("Subclass must implement drawThirdPart")
}
}
// Concrete classes have to implement all needed operations of the base
// class. They can also override some operations with a default implementation.
class FrenchFlag: TreeColorFlag {
func drawFirstPart() {
print("FrenchFlag says: Implemented Operation1")
}
func drawSecondPart() {
print("FrenchFlag says: Implemented drawSecondPart")
}
func drawThirdPart() {
print("FrenchFlag says: Implemented drawThirdPart")
}
}
class GermanFlag: TreeColorFlag {
func drawFirstPart() {
print("FrenchFlag says: Implemented Operation1")
}
func drawSecondPart() {
print("FrenchFlag says: Implemented drawSecondPart")
}
func drawThirdPart() {
print("FrenchFlag says: Implemented drawThirdPart")
}
}
print("Drawing French 🇫🇷 flag")
FrenchFlag().draw()
print("Drawing German 🇩🇪 flag")
GermanFlag().draw()
Drawing French 🇫🇷 flag
Starting drawing
FrenchFlag says: Implemented Operation1
First part is done.
FrenchFlag says: Implemented drawSecondPart
Second part is done.
FrenchFlag says: Implemented drawThirdPart
Third part is done.
Drawing German 🇩🇪 flag
Starting drawing
FrenchFlag says: Implemented Operation1
First part is done.
FrenchFlag says: Implemented drawSecondPart
Second part is done.
FrenchFlag says: Implemented drawThirdPart
Third part is done.
typescript
// Define a template method that contains a skeleton of some algorithm, composed of calls to (usually) primitive operations.
class TreeColorFlag {
// The template method defines the skeleton of an algorithm.
draw(): void {
this.log("Starting drawing");
this.drawFirstPart();
this.log("First part is done.");
this.drawSecondPart();
this.log("Second part is done.");
this.drawThirdPart();
this.log("Third part is done.");
}
log(message: String): void {
console.log(message);
}
// These operations have to be implemented in subclasses.
drawFirstPart(): void {
throw new Error("Subclass must implement drawFirstPart");
}
drawSecondPart(): void {
throw new Error("Subclass must implement drawSecondPart");
}
drawThirdPart(): void {
throw new Error("Subclass must implement drawThirdPart");
}
}
// Concrete classes have to implement all needed operations of the base
// class. They can also override some operations with a default implementation.
class FrenchFlag extends TreeColorFlag {
drawFirstPart(): void {
console.log("FrenchFlag says: Implemented Operation1");
}
drawSecondPart(): void {
console.log("FrenchFlag says: Implemented drawSecondPart");
}
drawThirdPart(): void {
console.log("FrenchFlag says: Implemented drawThirdPart");
}
}
class GermanFlag extends TreeColorFlag {
drawFirstPart(): void {
console.log("FrenchFlag says: Implemented Operation1");
}
drawSecondPart(): void {
console.log("FrenchFlag says: Implemented drawSecondPart");
}
drawThirdPart(): void {
console.log("FrenchFlag says: Implemented drawThirdPart");
}
}
console.log("Drawing French 🇫🇷 flag");
new FrenchFlag().draw();
console.log("Drawing German 🇩🇪 flag");
new GermanFlag().draw();
Drawing French 🇫🇷 flag
Starting drawing
FrenchFlag says: Implemented Operation1
First part is done.
FrenchFlag says: Implemented drawSecondPart
Second part is done.
FrenchFlag says: Implemented drawThirdPart
Third part is done.
Drawing German 🇩🇪 flag
Starting drawing
FrenchFlag says: Implemented Operation1
First part is done.
FrenchFlag says: Implemented drawSecondPart
Second part is done.
FrenchFlag says: Implemented drawThirdPart
Third part is done.
Adapter pattern lets you wrap an otherwise incompatible object in an adapter to make it compatible with another class.
swift
// Adaptee: SocketDenmark contains some useful behavior, but it is incompatible
// with the existing LaptopUS. The SocketDenmark needs some adaptation before the
// LaptopUS can use it.
// 🇩🇰 socket
class SocketDenmark {
public func forbinde() { //connect in Danish
print("Adapee: Forbundet.") // connected in Danish
}
}
// Target: SocketUS defines the domain-specific implementation.
class SocketUS {
func connect() {
print("Target: Connected.")
}
}
/// Adapter: makes SocketDenmark compatible with the SocketUS.
// 🇺🇸 plug to 🇩🇰 socket adapter.
class Adapter: SocketUS {
private var SocketDenmark: SocketDenmark
init(_ SocketDenmark: SocketDenmark) {
self.SocketDenmark = SocketDenmark
}
override func connect() {
print("Adapter: Connecting...")
SocketDenmark.forbinde()
print("Adapter: Connected.")
}
}
// Client: uses Adapter.
// Laptop with 🇺🇸 plug
class LaptopUS {
static func connectUSPlugToElectricity(socket: SocketUS) {
print(socket.connect())
}
}
LaptopUS.connectUSPlugToElectricity(socket: SocketUS())
LaptopUS.connectUSPlugToElectricity(socket: Adapter(SocketDenmark()))
Target: Connected.
Adapter: Connecting...
Adapee: Forbundet.
Adapter: Connected.
typescript
// Adaptee: SocketDenmark contains some useful behavior, but it is incompatible
// with the existing LaptopUS. The SocketDenmark needs some adaptation before the
// LaptopUS can use it.
// 🇩🇰 socket
class SocketDenmark {
public forbinde(): void {
//connect in Danish
console.log("Adapee: Forbundet."); // connected in Danish
}
}
// Target: SocketUS defines the domain-specific implementation.
class SocketUS {
public connect(): void {
console.log("Target: Connected.");
}
}
/// Adapter: makes SocketDenmark compatible with the SocketUS.
// 🇺🇸 plug to 🇩🇰 socket adapter.
class Adapter extends SocketUS {
private adaptee: SocketDenmark;
constructor(adaptee: SocketDenmark) {
super();
this.adaptee = adaptee;
}
public connect(): void {
console.log("Adapter: Connecting...");
this.adaptee.forbinde();
console.log("Adapter: Connected.");
}
}
// Client: uses Adapter.
// Laptop with 🇺🇸 plug
class LaptopUS {
static connectUSPlugToElectricity(socket: SocketUS): void {
console.log(socket.connect());
}
}
LaptopUS.connectUSPlugToElectricity(new SocketUS());
LaptopUS.connectUSPlugToElectricity(new Adapter(new SocketDenmark()));
Target: Connected.
Adapter: Connecting...
Adapee: Forbundet.
Adapter: Connected.
Delegation is a design pattern that enables a class to hand off (or “delegate”) some of its responsibilities to an instance of another class.
swift
struct Cookie {
var size = 5
var hasChocolateChips = false
}
// Setup delegate protocol
protocol BakeryDelegate {
func bakeCookies(cookie: Cookie)
}
// Implementation of the delegation
class Bakery: BakeryDelegate {
func bakeCookies(cookie: Cookie) {
print("Yay! A new cookie was baked, with size \(cookie.size).")
}
}
class CookieShop {
var delegate: BakeryDelegate
init(delegate: BakeryDelegate) {
self.delegate = delegate
}
func buy(cookies: Int) {
var cookie = Cookie()
cookie.size = cookies
cookie.hasChocolateChips = true
delegate.bakeCookies(cookie: cookie)
}
}
let bakery = Bakery()
let shop = CookieShop(delegate: bakery)
shop.buy(cookies: 6)
Yay! A new cookie was baked, with size 6.
typescript
class Cookie {
public size = 5;
public hasChocolateChips = false;
}
// Setup delegate interface
interface BakeryDelegate {
bakeCookies(cookie: Cookie): void;
}
// Implementation of the delegation
class Bakery implements BakeryDelegate {
bakeCookies(cookie: Cookie): void {
console.log(`Yay! A new cookie was baked, with size ${cookie.size}.`);
}
}
class CookieShop {
constructor(private delegate: BakeryDelegate) {}
buy(cookies: number): void {
const cookie = new Cookie();
cookie.size = cookies;
cookie.hasChocolateChips = true;
this.delegate.bakeCookies(cookie);
}
}
const bakery = new Bakery();
const shop = new CookieShop(bakery);
shop.buy(6);
Yay! A new cookie was baked, with size 6.
The facade pattern is used to define a simplified interface to a more complex subsystem.
swift
final class SystemA {
public func veryBigMethod() {
print("veryBigMethod of SystemA");
}
}
final class SystemB {
public func veryImportantMethod() {
print("veryImportantMethod of SystemB");
}
}
final class SystemC {
public func veryDifficultMethod() {
print("veryDifficultMethod of SystemC");
}
}
class Facade {
private let a = SystemA()
private let b = SystemB()
private let c = SystemC()
public func runBigAndImportantStuff() {
print("-- runBigAndImportantStuff started --")
self.a.veryBigMethod()
self.b.veryImportantMethod()
print("-- runBigAndImportantStuff is done --")
}
public func runBigAndDifficultStuff() {
print("-- runBigAndDifficultStuff started --")
self.a.veryBigMethod()
self.c.veryDifficultMethod()
print("-- runBigAndDifficultStuff is done --")
}
}
let facade = Facade()
facade.runBigAndImportantStuff()
facade.runBigAndDifficultStuff()
-- runBigAndImportantStuff started --
veryBigMethod of SystemA
veryImportantMethod of SystemB
-- runBigAndImportantStuff is done --
-- runBigAndDifficultStuff started --
veryBigMethod of SystemA
veryDifficultMethod of SystemC
-- runBigAndDifficultStuff is done --
typescript
namespace FacadePattern {
export class SystemA {
public veryBigMethod(): void {
console.log("veryBigMethod of SystemA");
}
}
export class SystemB {
public veryImportantMethod(): void {
console.log("veryImportantMethod of SystemB");
}
}
export class SystemC {
public veryDifficultMethod(): void {
console.log("veryDifficultMethod of SystemC");
}
}
export class Facade {
private a = new SystemA();
private b = new SystemB();
private c = new SystemC();
public runBigAndImportantStuff(): void {
console.log(`-- runBigAndImportantStuff started --`);
this.a.veryBigMethod();
this.b.veryImportantMethod();
console.log(`-- runBigAndImportantStuff is done --`);
}
public runBigAndDifficultStuff(): void {
console.log(`-- runBigAndDifficultStuff started --`);
this.a.veryBigMethod();
this.c.veryDifficultMethod();
console.log(`-- runBigAndDifficultStuff is done --`);
}
}
}
const facade = new FacadePattern.Facade();
facade.runBigAndImportantStuff();
facade.runBigAndDifficultStuff();
-- runBigAndImportantStuff started --
veryBigMethod of SystemA
veryImportantMethod of SystemB
-- runBigAndImportantStuff is done --
-- runBigAndDifficultStuff started --
veryBigMethod of SystemA
veryDifficultMethod of SystemC
-- runBigAndDifficultStuff is done --
Instead of creating the dependency internally an object can receive it from the outside.
swift
protocol Propulsion {
func move()
}
class Vehicle {
private let engine: Propulsion
init(engine: Propulsion) {
self.engine = engine
}
func forward() {
engine.move()
}
}
class RaceCarEngine: Propulsion {
func move() {
print("Vrrrooooommm!!")
}
}
class RocketEngine: Propulsion {
func move() {
print("3-2-1... LIFT OFF!!!")
}
}
let raceCarEngine = RaceCarEngine()
let car = Vehicle(engine: raceCarEngine)
car.forward()
let rocketEngine = RocketEngine()
let car2 = Vehicle(engine: rocketEngine)
car2.forward()
Vrrrooooommm!!
3-2-1... LIFT OFF!!!
typescript
interface Propulsion {
move(): void;
}
class Vehicle {
constructor(private engine: Propulsion) {}
forward(): void {
this.engine.move();
}
}
class RaceCarEngine implements Propulsion {
move(): void {
console.log("Vrrrooooommm!!");
}
}
class RocketEngine implements Propulsion {
move(): void {
console.log("3-2-1... LIFT OFF!!!");
}
}
const raceCarEngine = new RaceCarEngine();
const car = new Vehicle(raceCarEngine);
car.forward();
const rocketEngine = new RocketEngine();
const car2 = new Vehicle(rocketEngine);
car2.forward();
Vrrrooooommm!!
3-2-1... LIFT OFF!!!
The factory pattern is used to replace class constructors, abstracting the process of object generation so that the type of the object instantiated can be determined at run-time.
swift
enum Country {
case italy, spain, denmark, ukraine, usa
}
protocol Currency {
func getFlag() -> String
func getSymbol() -> String
}
// Defining currencies based on protocol
class Euro: Currency {
func getFlag() -> String {
return "🇪🇺"
}
func getSymbol() -> String {
return "€"
}
}
class Krona: Currency {
func getFlag() -> String {
return "🇩🇰"
}
func getSymbol() -> String {
return "DKK"
}
}
class Hryvnia: Currency {
func getFlag() -> String {
return "🇺🇦"
}
func getSymbol() -> String {
return "₴"
}
}
class Dollar: Currency {
func getFlag() -> String {
return "🇺🇸"
}
func getSymbol() -> String {
return "$"
}
}
// Defining factory itself
class CurrencyFactory {
static func make(currencyFor country: Country) -> Currency {
switch country {
case .spain, .italy:
return Euro()
case .denmark:
return Krona()
case .ukraine:
return Hryvnia()
case .usa:
return Dollar()
}
}
}
let currency1 = CurrencyFactory.make(currencyFor: .ukraine)
print("\(currency1.getFlag()) \(currency1.getSymbol())")
let currency2 = CurrencyFactory.make(currencyFor: .spain)
print("\(currency2.getFlag()) \(currency2.getSymbol())")
🇺🇦 ₴
🇪🇺 €
typescript
enum Country {
italy = 0,
spain,
denmark,
ukraine,
usa
}
interface Currency {
getFlag(): String;
getSymbol(): String;
}
// Defining currencies based on protocol
class Euro implements Currency {
public getFlag(): String {
return "🇪🇺";
}
public getSymbol(): String {
return "€";
}
}
class Krona implements Currency {
getFlag(): String {
return "🇩🇰";
}
public getSymbol(): String {
return "DKK";
}
}
class Hryvnia implements Currency {
getFlag(): String {
return "🇺🇦";
}
public getSymbol(): String {
return "₴";
}
}
class Dolar implements Currency {
getFlag(): String {
return "🇺🇸";
}
public getSymbol(): String {
return "$";
}
}
// Defining factory itself
class CurrencyFactory {
public static make(currencyForCountry: Country): Currency {
switch (currencyForCountry) {
case (Country.spain, Country.italy):
return new Euro();
case Country.denmark:
return new Krona();
case Country.ukraine:
return new Hryvnia();
case Country.usa:
return new Dolar();
}
}
}
let currency1 = CurrencyFactory.make(Country.ukraine);
console.log(`${currency1.getFlag()} ${currency1.getSymbol()}`);
let currency2 = CurrencyFactory.make(Country.denmark);
console.log(`${currency2.getFlag()} ${currency2.getSymbol()}`);
🇺🇦 ₴
🇩🇰 DKK
Ensures a class has only one instance and provides a global point of access to it.
swift
// final prevents class to be subclassed.
final class Singleton {
// A variable which stores the singleton object.
// On initialization This is how we create a singleton object.
static let sharedInstance = Singleton()
// Private initialization to ensure just one instance is created.
private init() {
print("Initialized.")
}
func sayHi() {
print("Hi!")
}
}
let instance = Singleton.sharedInstance
instance.sayHi()
Initialized.
Hi!
// Next line will fail
Singleton()
error: Singleton.playground:21:1: error: 'Singleton' initializer is inaccessible due to 'private' protection level
Singleton()
^
Singleton.playground:8:13: note: 'init()' declared here
private init() {
^
typescript
namespace SingletonPattern {
export class Singleton {
// A variable which stores the singleton object.
// Initially, the variable acts like a placeholder
private static sharedInstance: Singleton;
public id: number;
// Private initialization to ensure just one instance is created.
private constructor() {
console.log("Initialized.");
this.id = Math.random();
}
// This is how we create a singleton object
public static getInstance(): Singleton {
// Check if an instance of the class is already created.
if (!Singleton.sharedInstance) {
// If not created create an instance of the class, and store the instance in the variable
Singleton.sharedInstance = new Singleton();
}
// return the singleton object
return Singleton.sharedInstance;
}
public sayHi(): void {
console.log("Hi!");
}
}
}
const instance1 = SingletonPattern.Singleton.getInstance();
instance1.sayHi();
console.log(instance1.id);
const instance2 = SingletonPattern.Singleton.getInstance();
console.log(instance2.id);
Initialized.
Hi!
0.32110868008151106
0.32110868008151106
//However, js gives you ability to do next:
console.log("🤔")
const test1 = new SingletonPattern.Singleton();
console.log(test1.id);
test1.sayHi();
const test2 = new SingletonPattern.Singleton();
console.log(test2.id);
test1.sayHi();
🤔
Initialized.
0.9238042630755623
Hi!
Initialized.
0.8771180249127926
Hi!
Hit run from debug toolbar.
In order to run/debug typescript examples run tsc -w
from root of the project. And then run node filesname.js
to see output in console. Or user jsfiddle link to run in a browser.
Open playground in Xcode and run it there.
Made with ❤️ by Dots and Spaces.