{{ message }}

Instantly share code, notes, and snippets.

# BKcore/ More Tests.carbide.md

Last active Oct 3, 2016
More Tests

# More Tests

This Gist was automatically created by Carbide, a free online programming environment.

 export function mergeSort(array) { let scratch = new Array(array.length); _mergeSortImpl(array, 0, array.length-1, scratch); return array; } function _mergeSortImpl(array, start, end, scratch) { if(start >= end) { return; } let middle = Math.floor((start + end) / 2); _mergeSortImpl(array, start, middle, scratch); _mergeSortImpl(array, middle+1, end, scratch); _merge(array, start, middle, end, scratch); } function _merge(array, start, middle, end, scratch) { for(let i = start; i <= end; ++i) { scratch[i] = array[i]; } let leftIdx = start; let rightIdx = middle + 1; let destIdx = start; while(leftIdx <= middle && rightIdx <= end) { if(scratch[leftIdx] < scratch[rightIdx]) { array[destIdx] = scratch[leftIdx]; ++leftIdx; } else { array[destIdx] = scratch[rightIdx]; ++rightIdx; } ++destIdx; } while(leftIdx <= middle) { array[destIdx] = scratch[leftIdx]; ++leftIdx; ++destIdx; } }
 class Graph { static Node = class Node { constructor(weight, neighbors) { this.weight = weight; this.neighbors = neighbors; } } // nodes is a map from node to a list of neighboring nodes. constructor(nodes) { this.nodes = nodes; } } class PriorityQueue { queue = []; static Entry = class Entry { constructor(item, priority) { this.item = item; this.priority = priority; } } insert(item, priority) { let i = 0; while(this.queue[i] != null && this.queue[i].priority >= priority) { ++i; } this.queue.splice(i, 0, new PriorityQueue.Entry(item, priority)); return this.queue; } pop() { return this.queue.pop(); } toString() { return `[\${this.queue.map((x) => `(\${x.priority}, \${x.item})`).join(', ')}]`; } } let queue = new PriorityQueue(); queue.insert('A', 1); queue.insert('B', 0); queue.insert('C', 2); queue.insert('D', 1); queue.toString(); class PathFinder { static walkBack(start, destination, visitedMap) { let path = []; let current = destination; while (current != start) { path.push(current); current = visitedMap[current]; } path.push(start); return path.reverse(); } static findPathBreadthFirst(graph, start, destination) { let visitedToParent = {}; let frontier = [start]; let current; while(frontier.length) { current = frontier.shift(); if(current === destination) { break; } for(let neighbor of graph.nodes[current].neighbors) { if(visitedToParent[neighbor] == null) { frontier.push(neighbor); visitedToParent[neighbor] = current; } } } if(current != destination) { return []; } else { return PathFinder.walkBack(start, destination, visitedToParent); } } } let graph = new Graph({ 'A': new Graph.Node(1, ['B']), 'B': new Graph.Node(2, ['A', 'C', 'D']), 'C': new Graph.Node(3, ['A']), 'D': new Graph.Node(1, ['E', 'A']), 'E': new Graph.Node(2, ['B']) }); let path = PathFinder.findPathBreadthFirst(graph, 'A', 'E');
 import {mergeSort} from './algorithm.js' console.log('-- START'); const SIZE = 10; let array = new Array(SIZE); for(let i = 0; i < SIZE; ++i) { array[i] = Math.floor(Math.random() * 10); } array.slice(0) mergeSort(array);