dexie-dsync: a dexie addon for distributed sync using file storage like dropbox or google drive.

client.ts

import { toVersion, Ordering } from 'version-vector';
import { mergeJoin, stringComparator, innerJoin, maybe, assert } from 'rr/util';

export interface Versioned {
	version: string;
}

export interface Version extends Versioned {
	readonly uid: string;
	readonly band: string;
	readonly table: string;
	readonly timestamp: number;
	readonly version: string;
	readonly deleted: boolean;
}

export interface Record<T> extends Version {
	readonly payload: T;
}

export interface Band extends Versioned {
	prefix: string;
	version: string;
}

export interface ClientSummary extends Versioned {
	key: 'manifest';
	name: string;
	version: string;
	clientID: string;
	lastSyncTime: number | null;
	lastSyncClientID: string | null;
	lastUpdateTime: number;
	schemaVersion: number;
}

export interface Manifest extends ClientSummary {
	// known clients must be sorted by clientID
	knownClients: ClientSummary[];
	// bands must be sorted by prefix
	bands: Band[];
}

export interface MergeFunc<T> {
	(local: Record<T>, remote: Record<T>): T | null;
}

export function cmp(local: Versioned, remote: Versioned): Ordering {
	return toVersion(local.version)
		.cmp(toVersion(remote.version));
}

export function mergeVersions(local: Versioned | null, remote: Versioned | null): string {
	return toVersion(maybe(local).version)
		.merge(toVersion(maybe(remote).version))
		.toString();
}

export abstract class Client {

	abstract name: string;
	abstract getManifest(): Promise<Manifest>;
	// SycRecords must be sorted by id
	abstract getRecords(band: Band): Promise<Array<Record<any>>>;
	abstract saveRecord(record: Record<any>): Promise<void>;
	abstract saveManifest(manifest: Manifest): Promise<string>;
	abstract resolveConflict<T>(local: Record<T>, remote: Record<T>): T;
	abstract saveBand(band: Band): Promise<void>;
	abstract supportsReciprocalSync(): boolean;

	async mergeRecord<T>(local: Record<T> | null, remote: Record<T> | null): Promise<void> {
		let record;
		let payload;
		let timestamp;
		if (local == null) {
			record = remote!;
			payload = remote!.payload;
			timestamp = remote!.timestamp;
		} else if (remote == null) {
			// Nothing to do.
			return;
		} else if (cmp(local, remote) === Ordering.Equal) {
			// Nothing to do.
			return;
		} else if (cmp(local, remote) === Ordering.Less) {
			record = remote;
			payload = remote.payload;
			timestamp = remote.timestamp;
		} else if (cmp(local, remote) === Ordering.Greater) {
			// Nothing to do.
			return;
		} else if (cmp(local, remote) === Ordering.Concurrent) {
			record = local;
			payload = this.resolveConflict(local, remote);
			timestamp = local.timestamp;
		}
		const version = mergeVersions(local, remote);
		const merged: Record<any> = {
			...record,
			timestamp,
			version,
			payload
		};
		console.log(`saving ${record.uid} to ${this.name}`);
		await this.saveRecord(merged);
	}

	async mergeManifest(local: Manifest, remote: Manifest): Promise<void> {
		const { key, name, clientID, schemaVersion } = local;
		const version = mergeVersions(local, remote);
		const bands = innerJoin(
			local.bands,
			remote.bands,
			'prefix',
			'prefix',
			(localBand, remoteBand): Band => ({
				...localBand,
				version: mergeVersions(localBand, remoteBand)
			})
		);
		const now = +(new Date());
		const localSummary: ClientSummary = {
			key,
			name,
			version,
			clientID,
			lastUpdateTime: now,
			lastSyncTime: now,
			lastSyncClientID: remote.clientID,
			schemaVersion,
		};
		const knownClients = mergeJoin(
			local.knownClients,
			remote.knownClients,
			(l, r) => stringComparator(l.clientID, r.clientID),
			(l, r): ClientSummary => {
				if (l == null) {
					return r!;
				} else if (r == null) {
					return l;
				}
				if (l.clientID === localSummary.clientID) {
					return localSummary;
				}
				let newer;
				if (l.lastSyncTime == null) {
					newer = r;
				} else if (r.lastSyncTime == null) {
					newer = l;
				} else {
					newer = l.lastSyncTime > r.lastSyncTime ? l : r;
				}
				return {
					...l,
					version: mergeVersions(l, r),
					lastSyncTime: newer.lastSyncTime,
					lastSyncClientID: newer.lastSyncClientID,
					schemaVersion: newer.schemaVersion
				};
			}
		).sort((a, b) => stringComparator(a.clientID, b.clientID));
		const manifest = {
			...localSummary,
			bands,
			knownClients
		};
		await this.saveManifest(manifest);
	}

	async syncRemoteClient(remoteClient: Client, reciprocal: boolean): Promise<void> {
		console.log(`syncing ${this.name} with ${remoteClient.name}`);
		const remoteManifest = await remoteClient.getManifest();
		const localManifest = await this.getManifest();
		assert(localManifest.clientID !== remoteManifest.clientID);
		if (cmp(localManifest, remoteManifest) === Ordering.Equal) {
			console.log('Nothing to sync, already up-to-date.');
			// No changes, nothing to do.
			return;
		}
		if (cmp(localManifest, remoteManifest) === Ordering.Greater) {
			// We shouldn't get into this situation.
			// This means we synced both ways and still have unsynced changes!
			assert(reciprocal === false, 'reciprocal sync failed');
			// We've got the latest data, tell the other client to sync from us.
			if (remoteClient.supportsReciprocalSync()) {
				await remoteClient.syncRemoteClient(this, true);
			}
			return;
		}
		const joined = innerJoin(localManifest.bands, remoteManifest.bands, 'prefix', 'prefix',
			(localBand, remoteBand) => ({ localBand, remoteBand })
		);
		for (const { localBand, remoteBand } of joined) {
			if (cmp(localBand, remoteBand) === Ordering.Equal
				|| cmp(localBand, remoteBand) === Ordering.Greater
			) {
				// Skip this band, we have all the data already.
				continue;
			}
			const joinedRecords = mergeJoin(
				localBand ? await this.getRecords(localBand) : [],
				remoteBand ? await remoteClient.getRecords(remoteBand) : [],
				(localRecord, remoteRecord) => stringComparator(localRecord.uid, remoteRecord.uid),
				(localRecord, remoteRecord) => ({ localRecord, remoteRecord })
			);
			for (const { localRecord, remoteRecord } of joinedRecords) {
				await this.mergeRecord(localRecord, remoteRecord);
			}
			await this.saveBand(localBand);
		}
		await this.mergeManifest(localManifest, remoteManifest);
		if (remoteClient.supportsReciprocalSync()) {
			await remoteClient.syncRemoteClient(this, true);
		}
	}

}

crudMonitor.ts

import Dexie from 'dexie';
import { initCreatingHook } from './hooks/creating';
import { initUpdatingHook } from './hooks/updating';
import { initDeletingHook } from './hooks/deleting';

export function initCrudMonitor(db: Dexie) {
	return function crudMonitor(table: Dexie.Table<any, string>) {
		if (table.hook._dsyncObserving) {
			return;
		}
		table.hook._dsyncObserving = true;
		const tableName = table.name;
		table.hook('creating').subscribe(initCreatingHook(db, tableName));
		table.hook('updating').subscribe(initUpdatingHook(db, tableName));
		table.hook('deleting').subscribe(initDeletingHook(db, tableName));
	};
}

db.ts

// Example usage, setting up the database and enabling sync

import 'dexie-dsync';
import Dexie from 'dexie';
import { toVersion } from 'version-vector';
import { DropboxClient } from 'dexie-dsync/dropboxClient';
import { SettingKeyValue } from 'rr/state/settings';
import { WorkoutEntry } from 'rr/state/workouts';
import { BodyMeasurements } from 'rr/state/body-measurements';

export class RepsDB extends Dexie {
	settings: Dexie.Table<SettingKeyValue, string>;
	workoutLog: Dexie.Table<WorkoutEntry, string>;
	bodyMeasurements: Dexie.Table<BodyMeasurements, string>;

	constructor() {
		super('RepsDB');
		this.version(1).stores({
			settings: 'uid,&key',
			workoutLog: 'uid,date',
			bodyMeasurements: 'uid,date',
		});
	}
}

const db = new RepsDB();

db.dsync.setSyncTables([
	db.settings,
	db.workoutLog,
	db.bodyMeasurements
]);

db.dsync.syncRecordFilter = (record) => {
	// Don't sync records that came from `origin`
	if (toVersion(record.version).has('origin')) {
		return false;
	}
	// Don't sync records that are sensitive or non-user-facing settings.
	if (record.table === 'settings') {
		return !(record.payload as SettingKeyValue).isPrivate;
	}
	return true;
};

export const enableDropboxSync = (token: string) =>
	db.dsync.addRemoteClient(new DropboxClient(token));

export const sync = () => db.dsync.sync();

setInterval(() => db.dsync.sync(), 30000);

export { db };

dropboxClient.ts

import Dropbox = require('dropbox');
import * as Dsync from '.';
import { request } from 'd3-request';
import { FileBand, FileManifest } from './file';

const MANIFEST_PATH = '/manifest.json';

const defaultManifest: FileManifest = {
	key: 'manifest',
	name: 'Dropbox',
	version: 'dropbox.0',
	clientID: 'dropbox',
	lastSyncTime: null,
	lastSyncClientID: null,
	lastUpdateTime: 0,
	schemaVersion: 1,
	knownClients: [],
	bands: [
		{ prefix: '0', version: 'dropbox.0', href: '/band-0.json' },
		{ prefix: '1', version: 'dropbox.0', href: '/band-1.json' },
		{ prefix: '2', version: 'dropbox.0', href: '/band-2.json' },
		{ prefix: '3', version: 'dropbox.0', href: '/band-3.json' },
		{ prefix: '4', version: 'dropbox.0', href: '/band-4.json' },
		{ prefix: '5', version: 'dropbox.0', href: '/band-5.json' },
		{ prefix: '6', version: 'dropbox.0', href: '/band-6.json' },
		{ prefix: '7', version: 'dropbox.0', href: '/band-7.json' },
		{ prefix: '8', version: 'dropbox.0', href: '/band-8.json' },
		{ prefix: '9', version: 'dropbox.0', href: '/band-9.json' },
		{ prefix: 'a', version: 'dropbox.0', href: '/band-a.json' },
		{ prefix: 'b', version: 'dropbox.0', href: '/band-b.json' },
		{ prefix: 'c', version: 'dropbox.0', href: '/band-c.json' },
		{ prefix: 'd', version: 'dropbox.0', href: '/band-d.json' },
		{ prefix: 'e', version: 'dropbox.0', href: '/band-e.json' },
		{ prefix: 'f', version: 'dropbox.0', href: '/band-f.json' }
	]
};

// https://stackoverflow.com/questions/14488745
function dateParser(key: any, value: any) {
	const reISO = /^(\d{4})-(\d{2})-(\d{2})T(\d{2}):(\d{2}):(\d{2}(?:\.\d*))(?:Z|(\+|-)([\d|:]*))?$/;
	if (typeof value === 'string') {
		if (reISO.exec(value)) {
			return new Date(value);
		}
	}
	return value;
}

async function getJSON(url: string): Promise<any> {
	return new Promise((resolve, reject) => {
		request(url)
			.mimeType('application/json')
			.response(function (xhr: XMLHttpRequest) { return JSON.parse(xhr.responseText, dateParser); })
			.get((error, data) => {
				if (error) {
					reject(error);
				} else {
					resolve(data);
				}
			});
	});
}

export class DropboxClient extends Dsync.Client {

	dbx: Dropbox;
	bands: Map<string, FileBand>;
	bandRecords: Map<string, Map<string, Dsync.Record<any>>>;
	name: string;

	constructor(accessToken: string) {
		super();
		this.dbx = new Dropbox({ accessToken });
		this.bands = new Map();
		this.bandRecords = new Map();
		this.name = 'dropbox';
	}

	supportsReciprocalSync(): boolean {
		return true;
	}

	async getManifest(): Promise<Dsync.Manifest> {
		let manifest;
		try {
			const { link } = await this.dbx.filesGetTemporaryLink({ path: MANIFEST_PATH });
			manifest = await getJSON(link);
		} catch (e) {
			const contents = JSON.stringify(defaultManifest, null, 4);
			await this.dbx.filesUpload({path: MANIFEST_PATH, mode: { '.tag': 'overwrite' }, contents });
			manifest = defaultManifest;
		}
		for (const band of manifest.bands) {
			this.bands.set(band.prefix, band);
		}
		return manifest;
	}

	// SyncRecords must be sorted by id
	async getRecords(band: Dsync.Band): Promise<Array<Dsync.Record<any>>> {
		let recordsMap = this.bandRecords.get(band.prefix);
		if (recordsMap == null) {
			try {
				recordsMap = new Map();
				const { href } = this.bands.get(band.prefix)!;
				const { link } = await this.dbx.filesGetTemporaryLink({ path: href });
				const records = await getJSON(link) as Dsync.Record<any>[];
				for (const record of records) {
					recordsMap.set(record.uid, record);
				}
				this.bandRecords.set(band.prefix, recordsMap);
			} catch (e) {
				recordsMap = new Map();
			}
		}
		return Array.from(recordsMap.values());
	}

	async saveRecord(record: Dsync.Record<any>): Promise<void> {
		let recordsMap = this.bandRecords.get(record.band);
		if (recordsMap == null) {
			recordsMap = new Map();
			this.bandRecords.set(record.band, recordsMap);
		}
		recordsMap.set(record.uid, record);
	}

	async saveManifest(manifest: Dsync.Manifest): Promise<string> {
		const contents = JSON.stringify(manifest, null, 4);
		await this.dbx.filesUpload({path: MANIFEST_PATH, mode: { '.tag': 'overwrite' }, contents });
		return 'manifest';
	}

	async saveBand(band: Dsync.Band): Promise<void> {
		const recordsMap = this.bandRecords.get(band.prefix);
		if (recordsMap == null) {
			return;
		}
		const records = Array.from(recordsMap.values());
		const contents = JSON.stringify(records, null, 4);
		const { href } = this.bands.get(band.prefix)!;
		await this.dbx.filesUpload({path: href, mode: { '.tag': 'overwrite' }, contents });
	}

	resolveConflict<T>(local: Dsync.Record<T>, remote: Dsync.Record<T>): T {
		throw new Error('Unexpected conflict.');
	}

}

dsyncClient.ts

import Dexie from 'dexie';
import throttle = require('lodash/throttle');
import { Client, Manifest, Record, Band } from './client';
import { initCrudMonitor } from './crudMonitor';

export class Dsync extends Client {

	db: Dexie;
	syncInprogress: boolean;
	tables: Map<string, Dexie.Table<any, string>>;
	syncRecordFilter: (r: Record<any>) => boolean;
	name: string;
	syncStarted: () => void;
	syncEnded: (hasNewData: boolean) => void;
	sync: () => Promise<void>;
	private _hasNewData: boolean;
	private _remoteClients: Map<string, Client>;

	constructor(db: Dexie) {
		super();
		this.db = db;
		this.tables = new Map();
		this.syncRecordFilter = (r: Record<any>) => true;
		this.name = 'local';
		this.syncStarted = () => null;
		this.syncEnded = () => null;
		this.sync = throttle(this._sync, 15000);
		this._hasNewData = false;
		this._remoteClients = new Map();
	}

	supportsReciprocalSync(): boolean {
		// This is the local client that always initiates sync, reciprocal is unnecessary.
		return false;
	}

	setSyncTables(tables: Dexie.Table<any, string>[]) {
		const crudMonitor = initCrudMonitor(this.db);
		for (const table of tables) {
			this.tables.set(table.name, table);
			table.syncEnabled = true;
			crudMonitor(table);
		}
	}

	addRemoteClient(client: Client) {
		this._remoteClients.set(client.name, client);
	}

	async getRemoteClients(): Promise<Array<Client>> {
		return Array.from(this._remoteClients.values());
	}

	async getManifest(): Promise<Manifest> {
		return this.db._dsync.get('manifest') as Promise<Manifest>;
	}

	// SyncRecords must be sorted by id
	async getRecords(band: Band): Promise<Array<Record<any>>> {
		const tableSet = new Set(this.tables.keys());
		const versions = await this.db._versions
			.where('band')
			.equals(band.prefix)
			.filter(v => tableSet.has(v.table))
			.toArray();
		const records: Record<any>[] = [];
		for (const version of versions) {
			const record = {
				...version,
				payload: await this.db.table(version.table).get(version.uid)
			};
			if (this.syncRecordFilter(record)) {
				records.push(record);
			}
		}
		return records;
	}

	async saveRecord(record: Record<any>): Promise<void> {
		if (record.deleted) {
			await this.db.table(record.table).where('id').equals(record.uid).delete();
		}
		const { payload, ...version } = record;
		await this.db.table(record.table).put(payload);
		await this.db._versions.put(version);
		this._hasNewData = true;
	}

	async saveManifest(manifest: Manifest): Promise<string> {
		return this.db._dsync.put(manifest);
	}

	async saveBand(band: Band): Promise<void> {
		// Do nothing
	}

	resolveConflict<T>(local: Record<T>, remote: Record<T>): T {
		return this.db.dsync.tables.get(local.table)!.conflictHandler(local, remote);
	}

	async _sync(): Promise<void> {
		const clients = await this.getRemoteClients();
		if (clients.length === 0) {
			return;
		}
		this.syncInprogress = true;
		this.syncStarted();
		for (const client of clients) {
			await this.syncRemoteClient(client, false);
			console.log(`finished syncing ${this.name} with ${client.name}`);
		}
		this.syncInprogress = false;
		this.syncEnded(this._hasNewData);
		this._hasNewData = false;
	}
}

file.ts

import { Band, Manifest } from '.';

export interface FileBand extends Band {
	href: string;
}

export interface FileManifest extends Manifest {
	bands: FileBand[];
}

httpClient.ts

import * as Dsync from '.';
import { json } from 'd3-request';
import { FileBand, FileManifest } from './file';

async function getJSON(url: string): Promise<any> {
	return new Promise((resolve, reject) => {
		json(url, (error, data) => {
			if (error) {
				reject(error);
			} else {
				resolve(data);
			}
		});
	});
}

export class HttpClient extends Dsync.Client {

	manifestURL: string;
	bands: Map<string, FileBand>;
	bandRecords: Map<string, Map<string, Dsync.Record<any>>>;
	name: string;

	constructor(name: string, manifestURL: string) {
		super();
		this.name = name;
		this.manifestURL = manifestURL;
		this.bands = new Map();
		this.bandRecords = new Map();
	}

	supportsReciprocalSync(): boolean {
		return false;
	}

	async getManifest(): Promise<FileManifest> {
		const manifest = await getJSON(this.manifestURL);
		for (const band of manifest.bands) {
			this.bands.set(band.prefix, band);
		}
		return manifest;
	}

	// SyncRecords must be sorted by id
	async getRecords(band: Dsync.Band): Promise<Array<Dsync.Record<any>>> {
		let recordsMap = this.bandRecords.get(band.prefix);
		if (recordsMap == null) {
			recordsMap = new Map();
			const { href } = this.bands.get(band.prefix)!;
			const records = await getJSON(href) as Dsync.Record<any>[];
			for (const record of records) {
				recordsMap.set(record.uid, record);
			}
			this.bandRecords.set(band.prefix, recordsMap);
		}
		return Array.from(recordsMap.values());
	}

	async saveRecord(record: Dsync.Record<any>): Promise<void> {
		let recordsMap = this.bandRecords.get(record.band);
		if (recordsMap == null) {
			recordsMap = new Map();
			this.bandRecords.set(record.band, recordsMap);
		}
		recordsMap.set(record.uid, record);
	}

	async saveManifest(manifest: Dsync.Manifest): Promise<string> {
		// Do nothing
		return 'manifest';
	}

	async saveBand(band: Dsync.Band): Promise<void> {
		// Do nothing
	}

	resolveConflict<T>(local: Dsync.Record<T>, remote: Dsync.Record<T>): T {
		throw new Error('Unexpected conflict.');
	}

	async sync(): Promise<void> {
		// Do nothing
	}

}

index.ts

import Dexie from 'dexie';
import * as shortid from 'shortid';
import { Manifest, ClientSummary, Version, MergeFunc, Record } from './client';
import { Dsync } from './dsyncClient';
import { toVersion } from 'version-vector';
import { initOverrideCreateTransaction } from './overrideCreateTransaction';
import { overrideParseStoresSpec } from './overrideParseStoresSpec';
export { Client, Manifest, ClientSummary, Version, MergeFunc, Record, Band } from './client';
export { Dsync } from './dsyncClient';

const override = Dexie.override;

declare module 'dexie' {
	interface Dexie {
		dsync: Dsync;
		_dsync: Dexie.Table<Manifest, string>;
		_versions: Dexie.Table<Version, string>;
		_createTransaction: any;
	}

	module Dexie {
		interface Table<T, Key> {
			conflictHandler: MergeFunc<T>;
			syncEnabled: boolean;
		}

		interface TableHooks<T, Key> {
			_dsyncObserving: boolean;
		}
	}
}

export function DsyncAddon(db: Dexie) {
	db.Version.prototype._parseStoresSpec = override(db.Version.prototype._parseStoresSpec, overrideParseStoresSpec);
	db.Table.prototype.conflictHandler = <T> (local: Record<T>, remote: Record<T>): T | null => {
		return local.timestamp > remote.timestamp
			? local.payload
			: remote.payload;
	};
	db.Table.prototype.syncEnabled = false;
	const overrideCreateTransaction = initOverrideCreateTransaction(db);
	db._createTransaction = override(db._createTransaction, overrideCreateTransaction);
	db.dsync = new Dsync(db);
	db.on.populate.subscribe(() => {
		const clientID = shortid.generate();
		const version = toVersion().add(clientID).toString();
		const now = +(new Date());
		const client: ClientSummary = {
			key: 'manifest',
			name: window.navigator.userAgent,
			version,
			clientID,
			lastSyncTime: null,
			lastSyncClientID: null,
			lastUpdateTime: now,
			schemaVersion: db.verno,
		};
		db._dsync.put({
			...client,
			knownClients: [
				client
			],
			bands: [
				{ prefix: '0', version },
				{ prefix: '1', version },
				{ prefix: '2', version },
				{ prefix: '3', version },
				{ prefix: '4', version },
				{ prefix: '5', version },
				{ prefix: '6', version },
				{ prefix: '7', version },
				{ prefix: '8', version },
				{ prefix: '9', version },
				{ prefix: 'a', version },
				{ prefix: 'b', version },
				{ prefix: 'c', version },
				{ prefix: 'd', version },
				{ prefix: 'e', version },
				{ prefix: 'f', version }
			],
		});
	});
}

Dexie.addons.push(DsyncAddon);

overrideCreateTransaction.ts

import Dexie from 'dexie';

export function initOverrideCreateTransaction(db: Dexie) {
	return function overrideCreateTransaction(origFunc: any) {
		return function (this: any, mode: any, storenames: any, dbschema: any, parent: any) {
			if (db.dynamicallyOpened()) {
				return origFunc.apply(this, arguments); // Don't observe dynamically opened databases.
			}
			if (mode === 'readwrite'
				&& storenames.some((storeName: any) => dbschema[storeName] && db.dsync.tables.get(storeName) != null)) {
					// At least one included store is a dsync store. Make sure to also include the _versions & _dsync stores.
					storenames = storenames.slice(0); // Clone
					if (storenames.indexOf('_versions') === -1) {
						storenames.push('_versions');
					}
					if (storenames.indexOf('_dsync') === -1) {
						storenames.push('_dsync');
					}
			}
			// Call original db._createTransaction()
			const trans = origFunc.call(this, mode, storenames, dbschema, parent);
			return trans;
		};
	};
}

overrideParseStoresSpec.ts

export function overrideParseStoresSpec(origFunc: (fn: any) => any): any {
	return function (this: any, stores: any, dbSchema: any): any {
		stores._versions = 'uid,band,table,deleted';
		stores._dsync = 'key,type';
		origFunc.call(this, stores, dbSchema);
	};
}

util.ts

// http://ideasintosoftware.com/typescript-advanced-tricks/
export type Diff<T extends string, U extends string> = ({[P in T]: P } & {[P in U]: never } & { [x: string]: never })[T];
export type Omit<T, K extends keyof T> = {[P in Diff<keyof T, K>]: T[P]};

export function isEmptyObject(obj: Object) {
	for (const _ of Object.keys(obj)) {
		return false;
	}
	return true;
}

export function assert(condition: boolean, message: string = 'Assertion failed') {
	if (!condition) {
		throw new Error(message);
	}
}

export function prunedObject<T>(obj: Readonly<T>): T {
	const res = Object.assign({}, obj) as T;
	const keys = Object.keys(obj) as [keyof T];
	for (const prop of keys) {
		if (res[prop] == null) {
			delete res[prop];
		}
	}
	return res;
}

export function createUUID() {
	// Decent solution from http://stackoverflow.com/questions/105034
	let d = Date.now();
	const uuid = 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, (c: string) => {
		const r = (d + Math.random() * 16) % 16 | 0;
		d = Math.floor(d / 16);
		return (c === 'x' ? r : (r & 0x7 | 0x8)).toString(16);
	});
	return uuid;
}

export function unique<T>(arr: T[]): T[] {
	return Array.from(new Set(arr));
}

export function maybeF<T, V>(f: (t: T) => V, t: T): V | undefined {
	if (t == null) {
		return undefined;
	}
	return f(t);
}

export function maybe<T>(obj: T | undefined | null): Partial<T> {
	if (obj == null) {
		return {};
	}
	return obj;
}

export namespace format {
	export function duration(n: number): string {
		const hours = Math.floor(n / 3600);
		const minutes = Math.floor((n - (hours * 3600)) / 60);
		const seconds = n - (hours * 3600) - (minutes * 60);
		let formatted = '';
		if (hours > 0) {
			formatted += hours + 'h ';
		}
		if (minutes > 0) {
			formatted += minutes + 'm ';
		}
		if (seconds > 0) {
			formatted += seconds.toFixed(0) + 's ';
		}
		return formatted.trim();
	}
}

// https://stackoverflow.com/questions/2901102
export function formatCommas(x: number) {
	const parts = x.toString().split('.');
	parts[0] = parts[0].replace(/\B(?=(\d{3})+(?!\d))/g, ',');
	return parts.join('.');
}

export function stringComparator(a: string, b: string): number {
	if (a < b) {
		return -1;
	}
	if (a > b) {
		return 1;
	}
	return 0;
}

export function copyString(str: string): string {
	return (' ' + str).slice(1);
}

export function innerJoin<L, R, LK extends keyof L, RK extends keyof R, C>(
		left: L[],
		right: R[],
		leftKey: LK,
		rightKey: RK,
		select: (l: L, r: R) => C): C[] {
	const m = left.length;
	const n = right.length;
	const index = new Map<any, L>();
	const c: C[] = [];
	for (let i = 0; i < m; i++) {
		const row = left[i];
		index.set(row[leftKey], row);
	}
	for (let j = 0; j < n; j++) {
		const y = right[j];
		const x = index.get(y[rightKey])!;
		c.push(select(x, y));
	}
	return c;
}

export function mergeJoin<L, R, C>(
		left: L[],
		right: R[],
		comparisonFunction: (l: L, r: R) => number,
		joinFunction: (l: L | null, r: R | null) => C): C[] {
	const newArray: C[] = [];
	let i = 0;
	let j = 0;
	let e1;
	let e2;
	let comparison;
	while (i < left.length || j < right.length) {
		if (i === left.length) {
			newArray.push(joinFunction(null, right[j]));
			j += 1;
			continue;
		}
		if (j === right.length) {
			newArray.push(joinFunction(left[i], null));
			i += 1;
			continue;
		}
		e1 = left[i];
		e2 = right[j];
		comparison = comparisonFunction(e1, e2);
		if (comparison > 0) {
			newArray.push(joinFunction(null, e2));
			j += 1;
			continue;
		}
		if (comparison < 0) {
			newArray.push(joinFunction(e1, null));
			i += 1;
			continue;
		}
		if (comparison === 0) {
			newArray.push(joinFunction(e1, e2));
			i += 1;
			j += 1;
			continue;
		}
		break;
	}
	return newArray;
}
                       
                       interface Array<T> {
	flatMap<E>(f: (t: T) => Array<E>): Array<E>;
	concatMap<E> (this: Array<T>, fn: (t: T) => Array<E>): Array<E>;
	intersperse<E> (this: Array<T>, el: E);
}

Object.defineProperty(Array.prototype, 'flatMap', {
	value: function<T, E> (this: Array<T>, f: (t: T) => Array<E>): Array<E> {
		return this.reduce((ys: Array<E>, x: T) => {
			return ys.concat(f.call(this, x));
		}, []);
	},
	enumerable: false,
});

Object.defineProperty(Array.prototype, 'concatMap', {
	value: function<T, E> (this: Array<T>, fn: (t: T) => Array<E>): Array<E> {
		return [].concat.apply([], this.map(fn));
	},
	enumerable: false,
});

Object.defineProperty(Array.prototype, 'intersperse', {
	value: function<T, E> (this: Array<T>, el: E): Array<T | E> {
		return this.concatMap(x => [el, x]).slice(1);
	},
	enumerable: false,
});