JS Data Structure

JS_data_structure.js

class Link {
    constructor(data) {
        this.next = null;
        this.data = data;
    }
}
class Stack {
    constructor(data) {
        this.top = new Link();
        data.forEach(this.push.bind(this));
    }

    push(data) {
        let item = new Link(data);
        item.next = this.top.next;
        this.top.next = item;
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error('Empty Stack!');
        }
        let topItem = this.top.next;
        if (topItem.next) {
            this.top.next = topItem.next;
        } else {
            this.top.next = null;
        }
        topItem.next = null;
        return topItem;
    }
    
    isEmpty() {
        return !this.top.next;  
    }
}

class Queue {
    constructor(data) {
        this.stack1 = new Stack([]);
        this.stack2 = new Stack([]);
        this.top = null;
        data = data || [];
        data.forEach(this.add.bind(this));
    }

    add(item) {
        if (this.stack1.isEmpty()) {
            this.stack1.push(item);
            this.top = this.stack1.top.next;
        } else {
            this.stack1.push(item);
        }
    }
    
    peek() {
        return this.top;   
    }

    remove() {
        while(!this.stack1.isEmpty()) {
            this.stack2.push(this.stack1.pop().data);
        }
        if (!this.stack2.isEmpty()) {
            let returnItem = this.stack2.pop();
            this.top = this.stack2.top.next;
            while(!this.stack2.isEmpty()) {
                this.stack1.push(this.stack2.pop().data);
            }
            return returnItem;
        }
    }
}

class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.graphs = {};
    }

    addEdge(sourceNode, targetNode) {
        if (!this.graphs[sourceNode]) {
            this.graphs[sourceNode] = [];
        }
        this.graphs[sourceNode].push(targetNode);
    }

    isReachable(sourceNode, targetNode) {
        let verticesVisited = Array(this.vertices).fill(false);
        let queue = new Queue();
        queue.add(sourceNode);
        verticesVisited[sourceNode] = true;
        while(queue.stack1.isEmpty()) {
            let item = queue.remove();
            if (item && item.data === targetNode) {
                return true;
            }
            this.graphs[item.data].filter(vertice => !verticesVisited[sourceNode]).forEach(vertice => {
                queue.add(vertice);
                verticesVisited[vertice] = true;
            })
        }
        return false;
    }
}

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    static traversalBinaryTreeLevelByBST(treeNode) {
        let queue = new Queue([]);
        let list = [];
        queue.add(treeNode);
        queue.add(null);
        let layer = [];
        while(queue.peek()) {
            let node = queue.remove();
            if (node && node.data) {
                layer.push(node.data.data);
                if (node.data.left) {
                    queue.add(node.data.left);
                }
                if (node.data.right) {
                   queue.add(node.data.right);
                }
            } else if (queue.peek()) {
                list.push(layer);
                layer = [];
                queue.add(null);
            } else {
                list.push(layer);
            }
        }
        return list;
    }

    static convertSortedListToBST(list) {
        function getRootIndex(list) {
            return Math.floor(list.length / 2);
        }
        
        let rootIndex = getRootIndex(list);
        let root = new Node(list[rootIndex]);
        if (rootIndex > 0) {
            root.left = Node.convertSortedListToBST(list.slice(0, rootIndex));
        }
        if (rootIndex < list.length - 1) {
            root.right = Node.convertSortedListToBST(list.slice(rootIndex + 1));
        }
        return root;
    }
    
    *[Symbol.iterator]() {
        yield statement;   
    }
}

function memories(fn) {
    const caches = {};
    return function(...args) {
        if (caches[args]) {
            return caches[args];   
        }
        let result = fn.apply(this, args);
        caches[args] = result;
        return result;
    };
}