Data Structures

ArrayList

// please don't use it! It's just a draft that contains defects and is not fully implemented!

class ArrayList {
    constructor (initialSize = 16) {
        this._initialSize = initialSize
        this._threshold = initialSize
        this._size = 0
        this._bucket = new Array(initialSize)
    }

    add(v) {
        if (this._size >= this._threshold) {
            this._threshold = this._bucket.length * 2
            let newBucket = new Array(this._threshold)
            this._bucket.forEach(x => newBucket.add(x))
            this._bucket = newBucket
        }

        this._bucket.push(v)
        this._size += 1
    }

    get(idx) {
        if (idx > this._size) {
            return console.log('out of bound')
        }
        return this._bucket[idx]
    }

    remove(idx) {
        if (idx > this._size) {
            return console.log('out of bound')
        }

        this._bucket = [...this._bucket.slice(0, idx), ...this._bucket(idx + 1)]
    }

    size() {
        return this._size
    }
}

binarySearch

// todo handle negative cases ([], less than start, bigger than end)
// O(log n)
function binarySearch(arr, x, start = 0, end = arr.length - 1) {
  while (start <= end) {
    it++
    const mid = Math.floor((start + end) / 2)
    const val = arr[mid]

      if (x > val) {
        start = mid + 1
      } else if (x < val) {
        end = mid - 1
      } else {
        console.log(val, x)
        return true
      }
  }
  return false
}
// xx = 33
// binarySearch([1,3,5,7,9], 3)

BinaryTree

var { BinaryTree, BinaryTreeNode } = (() => {
    const ROOT = Symbol('root')
    const LEFT = Symbol('left')
    const RIGHT = Symbol('right')
    
    const checkType = (node) => {
        if (node instanceof BinaryTreeNode === false) {
            throw new Error('Tree node should be instance of BinaryTreeNode class')
        }
    }

    class BinaryTreeNode {
        constructor(data) {
            this.data = data
            this[LEFT] = null
            this[RIGHT] = null
        }
        get left() { return this[LEFT] }
        get right() { return this[RIGHT] }
        set left(node) {
            checkType(node)
            this[LEFT] = node
        }
        set right(node) {
            checkType(node)
            this[RIGHT] = node
        }
        
    }

    class BinaryTree {
        constructor(node) {
            checkType(node)
            this[ROOT] = node
        }
        get root() { return this[ROOT] }
    }

    return { BinaryTree, BinaryTreeNode }
})();

gistfile1.txt

function bubbleSort(unsortedArr) {
    function sort(arr) {
        for (let i = 1, i0 = 0; i < arr.length; i++, i0++) {
            if (arr[i0] > arr[i]) { swap(arr, i0, i) }
            for (let j = i0, j0 = j - 1; j > 0; j--, j0--) {
                if (arr[j0] > arr[j]) { swap(arr, j0, j) }
            }
        }
        return arr
    }

    function swap(arr, i, j) {
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        return arr
    }

    const result = sort(unsortedArr)
    return result
}
bubbleSort([4,2,3,1,5,0])

HashMap

// please don't use it! It's just a draft that contains defects and is not fully implemented!
// https://adrianmejia.com/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#HashMapWithRehash

// TODO flattern map when size is increased

class DecentHashMap {

  constructor(initialCapacity = 2) {
    this.buckets = new Array(initialCapacity);
    this.collisions = 0;
  }

  set(key, value) {
    const bucketIndex = this.getIndex(key);
    if(this.buckets[bucketIndex]) {
console.log('set existing arr')
      this.buckets[bucketIndex].push({key, value});
      if(this.buckets[bucketIndex].length > 1) { 
console.log('collision', this.buckets[bucketIndex])
        this.collisions++;
      }
    } else {
console.log('set new arr')
      this.buckets[bucketIndex] = [{key, value}];
    }
    return this;
  }

  get(key) {
    const bucketIndex = this.getIndex(key);
    for (let arrayIndex = 0; arrayIndex < this.buckets[bucketIndex].length; arrayIndex++) {
      const entry = this.buckets[bucketIndex][arrayIndex];
      if(entry.key === key) {
        return entry.value
      }
    }
  }

  hash(key) {
    let hashValue = 0;
    const stringTypeKey = `${key}${typeof key}`;

    for (let index = 0; index < stringTypeKey.length; index++) {
      const charCode = stringTypeKey.charCodeAt(index);
      hashValue += charCode << (index * 8);
    }
console.log('hash', key, hashValue)
    return hashValue;
  }

  getIndex(key) {
    const indexHash = this.hash(key);
    const index = indexHash % this.buckets.length;
console.log('index', index, 'l', this.buckets.length)
    return index;
  }
}

LinkedList

// https://humanwhocodes.com/blog/2019/01/computer-science-in-javascript-linked-list/
// TODO: handle negative cases
// TODO: implement map, filter, some, etc...

LinkedList = (() => {
    const head = Symbol('head')
    const size = Symbol('size')
    const last = Symbol('last')
    const next = Symbol('next')
    const prev = Symbol('prev')

    class ListNode {
        constructor (data) {
            this.data = data
            this[next] = null
            this[prev] = null
        }

        get next() { return this[next] }
        get prev() { return this[prev] }
    }

    class LinkedList {
        constructor (dataArray = []) {
            this[head] = null
            this[last] = null
            this[size] = 0
            this.addAll(dataArray)
        }

        [Symbol.iterator]() { return this.values() }
        get size() { return this[size] }
        get first() { return this[head] }
        get last() { return this[last] }

        add(data) {
            if (data === undefined) {
                return // should throw?
            }

            const newNode = new ListNode(data)

            if (this[head] === null) {
                this[head] = newNode
            } else {
                this[last][next] = newNode
                newNode[prev] = this[last]
            }
            this[size] += 1
            this[last] = newNode
        }

        addAll(dataArray) {
            dataArray.forEach(data => this.add(data))
        }

        getNode(idx) {
            if (idx < 0 || idx >= this.size || this.size === 0) {
                return // should throw?
            }

            let current, i, direction, step
            // iterate in reverse order if idx is closer to the last node
            if (idx >= this.size / 2) {
                current = this[last]
                i = this.size - 1
                direction = prev
                step = -1
            } else { // iterate from head
                current = this[head]
                i = 0
                direction = next
                step = 1
            }

            while (i !== idx && current !== null) {
                current = current[direction]
                i = i + step
            }
            return current
        }

        get(idx) {
            return this.getNode(idx).data
        }

        indexOf(value) {
            let i = 0
            for (let data of this) {
                if (data === value) {
                    return i
                }
                i += 1
            }
            return -1
        }

        lastIndexOf(value) {
            let i = this.size - 1
            for (let data of this.reverse) {
                if (data === value) {
                    return i
                }
                i -= 1
            }
            return -1
        }

        includes(value) {
            return this.indexOf(value) > -1
        }

        removeIndex(idx) {
            if (idx < 0 || idx >= this.size || this.size === 0) {
                return // should throw?
            }
            let current

            if (idx === 0) { // first
                current = this[head]
                this[head] = this[head][next]
                if (this[head] === null) { // deleting the last list item
                    this[last] = null
                } else {
                    this[head][prev] = null
                }
            } else if (idx === this.size - 1) { // last
                current = this[last]
                this[last] = this[last][prev]
                this[last][next] = null
            } else {
                current = this.getNode(idx)
                if (!current) {
                    return // should throw?
                }
                current[prev][next] = current[next]
                current[next][prev] = current[prev][next]
            }
            this[size] -= 1
            delete current[next]
            delete current[prev]
            return current.data
        }

        // remove last
        pop() {
            return this.removeIndex(this.size - 1)
        }

        // remove first
        shift() {
            return this.removeIndex(0)
        }

        get reverse() {
            const linkedList = this
            return {
                [Symbol.iterator]() { return this.values() },
                *values() {
                    let current = linkedList[last]

                    while (current !== null) {
                        yield current.data;
                        current = current.prev
                    }
                },
            }
        }

        *values() {
            let current = this[head]

            while (current !== null) {
                yield current.data;
                current = current.next
            }
        }
    }

    return LinkedList
})();

MapReduce

// simple single thread MapReduce

function mapReduce(data, mapFn, reduceFn) {
    return data
        .map(myMapFn) // MAP
        .flat().reduce((acc, [key, value]) => {
            acc[key] = acc[key] === undefined ? value : reduceFn(acc[key], value) // REDUCE
            return acc
        }, {})
}

// USAGE

function myMapFn(doc, index) {
    const words = {}
    doc.split(' ').forEach(word => {
        if (words[word] === undefined) {
            words[word] = 0
        }
        words[word]++
    })
    return Object.entries(words)
}

function myReduceFn (accumulator, currentValue) { return accumulator + currentValue }


mapReduce(['foo bar', 'bla bar', 'bar foo'], myMapFn, myReduceFn)

mergeSort

// O(n log n)

function mergeSort(arr) {
  function sortChunk(chunk) {
    if (chunk.length < 2) { return chunk }
    if (chunk.length === 2) {
      if (chunk[1] < chunk[0]) {
        const chunk0 = chunk[0]
        chunk[0] = chunk[1]
        chunk[1] = chunk0
      }
      return chunk
    }
    const mid = Math.floor(chunk.length / 2)
    return merge(
        sortChunk(chunk.slice(0, mid)),
        sortChunk(chunk.slice(mid))
    )
  }

  function merge(arr1, arr2) {
    const result = []
    let i1 = 0
    let i2 = 0
    while (i1 < arr1.length && i2 < arr2.length) {
      if (arr1[i1] < arr2[i2]) {
        result.push(arr1[i1])
        i1 += 1
      } else {
        result.push(arr2[i2])
        i2 += 1
      }
    }

    while (i1 < arr1.length) { result.push(arr1[i1]); i1++ }
    while (i2 < arr2.length) { result.push(arr2[i2]); i2++ }

    return result
  }

  return sortChunk(arr)
}

// mergeSort([7, -1, 2, 0, 0, 2, 44.56, 13, 3])

mergeSort - no slice

function mergeSortN(unsortedArray) {
  function sortChunk(arr, lo = 0, hi = arr.length - 1) {
    const length = 1 + hi - lo

    if (length < 2) { return arr }

    if (length === 2) {
      if (arr[hi] < arr[lo]) {
        const chunkLo = arr[lo]
        arr[lo] = arr[hi]
        arr[hi] = chunkLo
      }
      return arr
    }

    const mid = lo + Math.floor(length / 2)
    sortChunk(arr, lo, mid)
    sortChunk(arr, mid, hi)

    return merge(arr, lo, mid, mid, hi + 1)
  }

  function merge(arr, lo1, hi1, lo2, hi2) {
    const result = []
    let i1 = lo1
    let i2 = lo2
    while (i1 < hi1 && i2 < hi2) {
      if (arr[i1] < arr[i2]) {
        result.push(arr[i1])
        i1 += 1
      } else {
        result.push(arr[i2])
        i2 += 1
      }
    }

    while (i1 < hi1) { result.push(arr[i1]); i1++ }
    while (i2 < hi2) { result.push(arr[i2]); i2++ }

    let ri = 0
    for (let i = lo1; i < hi2; i++) {
        arr[i] = result[ri]; ri++
    }

    return arr
  }

  return sortChunk(unsortedArray)
}
mergeSortN([7, -1, 2, 0, 0, 2, 44.56, 13, 3])

Queue

Queue = (() => { // FIFO
    const SIZE = Symbol('size')
    const NEXT = Symbol('next')
    const FIRST = Symbol('first')
    const LAST = Symbol('last')

    class QueueNode {
        constructor(data) {
            this.data = data
            this[NEXT] = null
        }

        get next() { return this[NEXT] }
    }

    class Queue {
        constructor() {
            this[SIZE] = 0
            this[FIRST] = null
            this[LAST] = null
        }

        get size() { return this[SIZE] }

        remove() {
            if (this.isEmpty()) { return } // throw?
            
            const item = this[TOP].data
            this[FIRST] = this[FIRST].next

            if (this[FIRST] === null) {
                this[LAST] = null
            }

            this[SIZE] -= 1

            return item
        }

        add(data) {
            const qn = new QueueNode(data)
            if (this[LAST] !== null) {
                this[LAST][NEXT] = qn
            }
            this[LAST] = qn
            if (this[FIRST] === null) {
                this[FIRST] = this[LAST]
            }

            this[SIZE] += 1
        }

        get peek() {
            return this.peekNode.data
        }

        get peekNode() { return this[FIRST] }

        isEmpty() {
            return this[SIZE] === 0
        }
    }

    return Queue
})();

quickSort - iterative

function quickSort(unsortedArr) {
    if (unsortedArr.length < 2) { return unsortedArr }

    const tasks = [0, unsortedArr.length - 1]

    function partition(arr) {
        while (tasks.length > 0) {
            const hi = tasks.pop()
            const lo = tasks.pop()

            const pivot = choosePivot(arr, lo, hi)

            let p = lo
            for (let i = lo; i < hi; i++) {
                if (arr[i] < pivot) { swap(arr, i, p); p++ }
            }
            swap(arr, p, hi)

            addTask(lo, p - 1)
            addTask(p + 1, hi)
        }

        return arr
    }

    function choosePivot(arr, lo, hi) {
        const mid = Math.floor((lo + hi) / 2)
        
        if (arr[mid] < arr[lo]) {
            swap(arr, lo, mid)
        }
        if (arr[hi] < arr[lo]) {
            swap(arr, lo, hi)
        }
        if (arr[mid] < arr[hi]) {
            swap(arr, hi, mid)
        }
        // arr[mid] is now the biggest one
        return arr[hi] // last is median

    }

    function swap(arr, i, j) {
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        return arr
    }

    function addTask(lo, hi) {
        if (lo < hi) {
            tasks.push(lo, hi)
        }
    }
    
    const res = partition(unsortedArr)
    return res
}

quickSort([7, -1, 2, 0, 0, 2, 44.56, 13, 99, -2])

quickSort - recursive

function quickSort(unsortedArr) {
    let it = 0
    if (unsortedArr.length < 2) { return unsortedArr }

    function partition(arr, lo = 0, hi = arr.length - 1) {
        if (lo >= hi) { return arr }
        it++
        const pivot = choosePivot(arr, lo, hi)

        let p = lo
        for (let i = lo; i <= hi; i++) {
            if (arr[i] < pivot) { swap(arr, i, p); p++ }
        }
        swap(arr, p, hi)
        partition(arr, lo, p - 1)
        partition(arr, p + 1, hi)
        return arr
    }

    function choosePivot(arr, lo, hi) {
        const mid = Math.floor((lo + hi) / 2)
        
        if (arr[mid] < arr[lo]) {
            swap(arr, lo, mid)
        }
        if (arr[hi] < arr[lo]) {
            swap(arr, lo, hi)
        }
        if (arr[mid] < arr[hi]) {
            swap(arr, hi, mid)
        }
        // arr[mid] is now the biggest one
        return arr[hi] // last is median

    }

    function swap(arr, i, j) {
        let tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        return arr
    }
    
    const res = partition(unsortedArr)
    console.log('it', it)
    return res
}
quickSort([7, -1, 2, 0, 0, 2, 44.56, 13, 3])

RotatableList

RotatableList = (() => {
    const head = Symbol('head')
    const size = Symbol('size')
    const last = Symbol('last')
    const next = Symbol('next')
    const prev = Symbol('prev')

    class ListNode {
        constructor (data) {
            this.data = data
            this[next] = null
            this[prev] = null
        }

        get next() { return this[next] }
        get prev() { return this[prev] }
    }

    class LinkedList {
        constructor (dataArray = []) {
            this[head] = null
            this[last] = null
            this[size] = 0
            this.addAll(dataArray)
        }

        [Symbol.iterator]() { return this.values() }
        get size() { return this[size] }
        get first() { return this[head] }
        get last() { return this[last] }

        add(data) {
            if (data === undefined) {
                return // should throw?
            }

            const newNode = new ListNode(data)

            if (this[head] === null) {
                this[head] = newNode
            } else {
                this[last][next] = newNode
                newNode[prev] = this[last]
            }
            newNode[next] = this[head]
            this[head][prev] = newNode
            this[size] += 1
            this[last] = newNode
        }

        addAll(dataArray) {
            dataArray.forEach(data => this.add(data))
        }

        getNode(idx) {
            if (idx < 0 || idx >= this.size || this.size === 0) {
                return // should throw?
            }

            let current, i, direction, step
            // iterate in reverse order if idx is closer to the last node
            if (idx >= this.size / 2) {
                current = this[last]
                i = this.size - 1
                direction = prev
                step = -1
            } else { // iterate from head
                current = this[head]
                i = 0
                direction = next
                step = 1
            }

            while (i !== idx && current !== null) {
                current = current[direction]
                i = i + step
            }
            return current
        }

        get(idx) {
            return this.getNode(idx).data
        }

        indexOf(value) {
            let i = 0
            for (let data of this) {
                if (data === value) {
                    return i
                }
                i += 1
            }
            return -1
        }

        lastIndexOf(value) {
            let i = this.size - 1
            for (let data of this.reverse) {
                if (data === value) {
                    return i
                }
                i -= 1
            }
            return -1
        }

        includes(value) {
            return this.indexOf(value) > -1
        }

        removeIndex(idx) {
            if (idx < 0 || idx >= this.size || this.size === 0) {
                return // should throw?
            }
            let current

            if (idx === 0) { // first
                current = this[head]
                this[head] = this[head][next]
                if (this[head] === null) { // deleting the last list item
                    this[last] = null
                } else {
                    this[head][prev] = null
                }
            } else if (idx === this.size - 1) { // last
                current = this[last]
                this[last] = this[last][prev]
                this[last][next] = null
            } else {
                current = this.getNode(idx)
                if (!current) {
                    return // should throw?
                }
                current[prev][next] = current[next]
                current[next][prev] = current[prev][next]
            }
            this[size] -= 1
            delete current[next]
            delete current[prev]
            return current.data
        }

        // remove last
        pop() {
            return this.removeIndex(this.size - 1)
        }

        // remove first
        shift() {
            return this.removeIndex(0)
        }

        get reverse() {
            const linkedList = this
            return {
                [Symbol.iterator]() { return this.values() },
                *values() {
                    let current = linkedList[last]

                    while (current !== null) {
                        yield current.data;
                        current = current.prev
                    }
                },
            }
        }

        *values() {
            let current = this[head]

            while (current !== null) {
                yield current.data;
                current = this[last] === current ? null : current.next
            }
        }
    }

    return LinkedList
})();

Stack

Stack = (() => { // LIFO
    const SIZE = Symbol('size')
    const NEXT = Symbol('next')
    const TOP = Symbol('top')

    class StackNode {
        constructor(data) {
            this.data = data
            this[NEXT] = null
        }

        get next() { return this[NEXT] }
    }

    class Stack {
        constructor() {
            this[SIZE] = 0
            this[TOP] = null
        }

        get size() { return this[SIZE] }

        pop() {
            if (this.isEmpty()) { return } // throw?
            
            const item = this[TOP].data
            this[TOP] = this[TOP].next

            this[SIZE] -= 1

            return item
        }

        push(data) {
            const sn = new StackNode(data)
            sn[NEXT] = this[TOP]
            this[TOP] = sn

            this[SIZE] += 1
        }

        get peek() {
            return this.peekNode.data
        }

        get peekNode() { return this[TOP] }

        isEmpty() {
            return this[TOP] === null
        }
    }

    return Stack
})();

Tree

var { Tree,TreeNode } = (() => {
    const ROOT = Symbol('root')
    const CHILDREN = Symbol('children')

    class TreeNode {
        constructor(data) {
            this.data = data
            this[CHILDREN] = new TreeNodeArray()
        }
        get children() { return this[CHILDREN] }
    }

    class TreeNodeArray extends Array {
        push(...items) {
            if (items.some(item => item instanceof TreeNode !== true)) {
                throw new Error('Tree node should be instance of TreeNode class')
            }
            return super.push(...items)
        }
    }

    class Tree {
        constructor(node) {
            if (node instanceof TreeNode === false) {
                throw new Error('Tree node should be instance of TreeNode class')
            }
            this[ROOT] = node
        }
        get root() { return this[ROOT] }
    }

    return { Tree, TreeNode }
})();

Trie

var { Trie, TrieNode } = (() => {
    const ROOT = Symbol('root')
    const CHILDREN = Symbol('children')
    const TERMINATES = Symbol('terminates')

    class TrieNode {
        constructor(data) {
            if (typeof data !== 'string' || data.length !== 1) {
                throw new Error('Unable to create TrieNode with data ' + data)
            }
            this.data = data
            this[ROOT] = null
            this[TERMINATES] = false
            this[CHILDREN] = new TrieMap(this)
        }
        get root() { return this[ROOT] }
        get children() { return this[CHILDREN] }
        get terminates() { return this[TERMINATES] }
        set terminates(value) {
            if (typeof value !== 'boolean') {
                throw new Error('Only boolean true or false are allowed')
            }
            this[TERMINATES] = value
        }
    }

    function TrieMap (root) {
        return new Proxy(Object.create({}, {
            'size': {
                get() { return Object.keys(this).length }
            }
        }), {
            set(obj, prop, value) {
                // allow only chars
                if (prop.length !== 1) {
                    throw new Error('Not allowed to set prop: ' + prop)
                }

                const current = obj[prop]

                if (value instanceof TrieNode === true) {
                    obj[prop] = value
                } else if (typeof value === 'string' && value.length === 1) {
                    obj[prop] = new TrieNode(value)
                } else {
                    throw new Error('Unable to add children ' + value)
                }

                if (current instanceof TrieNode) {
                    current[ROOT] = null
                }

                obj[prop][ROOT] = root
            },
            deleteProperty(obj, prop) {
                if (obj[prop] instanceof TrieNode) {
                    obj[prop][ROOT] = null
                }
                delete obj[prop]
            }
        })
    }

    class Trie {
        constructor(node) {
            if (node instanceof TrieNode === true) {
                this[ROOT] = node
            } else if (typeof node === 'string' && node.length === 1) {
                this[ROOT] = new TrieNode(node)
            } else {
                throw new Error('Trie node should be instance of TreeNode class or a char')
            }
        }
        get root() { return this[ROOT] }

        getParents(node) {
            const cache = []
            let tmpNode = node
            while (tmpNode) {
                cache.push(tmpNode.data)
                tmpNode = tmpNode.root
            }
            cache.reverse()
            return cache
        }

        printWords(node, cache = this.getParents(node)) {
            if (node.terminates) {
                console.log(cache)
            }

            Object.values(node.children).forEach(child => {
                this.printWords(child, [...cache, child.data])
            })
        }
    }

    return { Trie, TrieNode }
})();