Created
October 28, 2020 16:46
-
-
Save nickx720/9f607a3cdeaf28165f15257881ad792b to your computer and use it in GitHub Desktop.
Ord Basis For Coord as per Tom Hardings Fantas Guide
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const daggy = require('daggy'); | |
const { merge } = require('ramda'); | |
function fantasyLandDaggy() { | |
const Coord = daggy.tagged('Coord', ['x', 'y', 'z']); | |
const Line = daggy.tagged('Coord', ['from', 'to']) | |
Coord.prototype.equals = function coordEquals(that) { | |
return this.x == that.x | |
&& this.y == that.y | |
&& this.z == that.z | |
} | |
Coord.prototype.lte = function coordLte(that) { | |
return (this.x < that.x) | |
|| (this.x == that.x && this.y < that.y) | |
|| (this.x == that.x && this.y == that.y && this.z < that.z) | |
|| (this.equals(that)) | |
} | |
Line.prototype.equals = function lineEquals(that) { | |
return this.from.equals(that.from) | |
&& this.to.equals(that.to) | |
} | |
Line.prototype.lte = function lineLte(that) { | |
return (lt(this.from, that.from)) || (this.from.equals(that.from) && lt(this.to, that.to)) || (this.equals(that)) | |
} | |
const gt = function (x, y) { | |
return !lte(x, y) | |
} | |
// Greater than or equal. | |
// gte :: Ord a => a -> a -> Boolean | |
const gte = function (x, y) { | |
return gt(x, y) || x.equals(y) | |
} | |
// Less than. The OPPOSITE of gte! | |
// lt :: Ord a => a -> a -> Boolean | |
const lt = function (x, y) { | |
return !gte(x, y) | |
} | |
// And we already have lte! | |
// lte :: Ord a => a -> a -> Boolean | |
const lte = function (x, y) { | |
return x.lte(y) | |
} | |
const copy = xs => [...xs] | |
//- Sort a list of Ords using bubble sort algorithm | |
// bubbleSort :: Ord a => [a] -> [a] | |
const bubbleSort = xs_ => { | |
const xs = copy(xs_) | |
let n = xs.length - 1 | |
let swapped = true | |
while (swapped) { | |
swapped = false | |
for (let i = 1; i <= n; i++) { | |
const curr = xs[i] | |
const prev = xs[i - 1] | |
if (gt(prev, curr)) { | |
xs[i - 1] = curr | |
xs[i] = prev | |
swapped = true | |
} | |
} | |
} | |
return xs | |
} | |
const merge = (arr1, arr2) => { | |
let finalArray = []; | |
let i = 0; | |
let j = 0; | |
while (i < arr1.length && j < arr2.length) { | |
if (lt(arr1[i], arr2[j])) { | |
finalArray.push(arr1[i]); | |
i++; | |
} else { | |
finalArray.push(arr2[i]); | |
j++; | |
} | |
} | |
let newArray = []; | |
if (i !== arr1.length) { | |
newArray.push(...arr1.slice(i, arr1.length)) | |
} else if (j !== arr2.length) { | |
newArray.push(...arr2.slice(j, arr2.length)) | |
} | |
return finalArray.concat(...newArray); | |
} | |
const mergeSort = (xs) => { | |
if (xs.length <= 1) return xs; | |
let mid = Math.floor(xs.length / 2); | |
let left = mergeSort(xs.slice(0, mid)); | |
let right = mergeSort(xs.slice(mid)); | |
return merge(left, right); | |
} | |
const quickSort = (arr, low, high) => { | |
if (low < high) { | |
let pi = partition(arr, low, high); | |
quickSort(arr, low, pi - 1); | |
quickSort(arr, pi + 1, high); | |
return arr | |
} | |
} | |
const partition = (arr, low, high) => { | |
let pivot = arr[high]; | |
let i = low - 1; | |
for (let j = low; j <= high - 1; j++) { | |
if (lt(arr[j], pivot)) { | |
i++; | |
swap(arr, i, j); | |
} | |
} | |
swap(arr, i + 1, high); | |
return (i + 1); | |
} | |
const swap = (arr, i, j) => { | |
let temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
const coord_list = [ | |
Coord(1, 8, 3), | |
Coord(1, 2, 1), | |
Coord(1, 1, 2) | |
] | |
let origin = Coord(0, 0, 0) | |
const line_list = [ | |
Line( | |
origin, | |
Coord(1, 2, 3) | |
), | |
Line( | |
Coord(1, 2, 1), | |
Coord(1, 2, 2), | |
), | |
Line( | |
origin, | |
Coord(1, 1, 2) | |
) | |
] | |
console.log(quickSort(line_list, 0, line_list.length - 1)) | |
} | |
exports.fantasyLandDaggy = fantasyLandDaggy; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment