Update key/value mapping from changes on another key/value mapping.

mapping.ts

import {Multimap, ReadonlyMultimap} from "./multimap";

export type NoInfer<T> = T & { [K in keyof T]: T[K] };

function identityProjection<T>(value: any, primary: T) { return primary }

/**
 * Project some sequence of values onto a Map using keys generated by
 * {@link surrogate}. Values with the same surrogate key will overwrite, with
 * the later insertion order overwriting the earlier.
 * @param values Sequence of values to project.
 * @param surrogate A callback that generates a surrogate key for projection.
 * @param bare When true, {@link values} is treated as a bare object.
 * @param onto Project onto a specific Map, rather than constructing new.
 * @returns A map of surrogate keys pointing to an associated value.
 */
export function project<K, V, L>(values: ReadonlyMap<L, V> | ReadonlyMultimap<L, V>, surrogate?: (value: NoInfer<V>, primary: NoInfer<L>) => K, bare?: false, onto?: Map<K, V>): Map<K, V>;
export function project<K, V>(values: Iterable<V>, surrogate: (value: NoInfer<V>) => K, bare?: false, onto?: Map<K, V>): Map<K, V>;
export function project<K, V>(values: readonly V[], surrogate?: (value: NoInfer<V>, primary: number, bare?: false, onto?: Map<K, V>) => K): Map<K, V>;
export function project<K, V, L extends PropertyKey>(values: { [key in L]: V }, surrogate: undefined | ((value: NoInfer<V>, primary: NoInfer<L>) => K), bare: true, onto?: Map<K, V>): Map<K, V>;
export function project(values: object, surrogate: (value: any, primary?: any) => any = identityProjection, bare?: boolean, onto?: Map<unknown, unknown>): Map<unknown, unknown> {
	const projection = new Map<unknown, unknown>();
	const mark = onto ? new Set(onto.keys()) : null;
	if(bare) {
		for(const [primary, value] of Object.entries(values)) {
			const key = surrogate(value, primary)
			projection.set(key, value);
			if(mark) mark.delete(key);
		}
	}
	else if(values instanceof Map || values instanceof Multimap) {
		for(const [primary, value] of values) {
			const key = surrogate(value, primary)
			projection.set(key, value);
			if(mark) mark.delete(key);
		}
	}
	else if(values instanceof Set) {
		for(const value of values) {
			const key = surrogate(value)
			projection.set(key, value);
			if(mark) mark.delete(key);
		}
	}
	else if(Array.isArray(values)) {
		for(let i = 0, len = values.length; i !== len; i++) {
			const key = surrogate(values[i], i)
			projection.set(key, values[i]);
			if(mark) mark.delete(key);
		}
	}
	else if(Symbol.iterator in values) {
		for(const value of values as any) {
			const key = surrogate(value)
			projection.set(key, value);
			if(mark) mark.delete(key);
		}
	}
	else {
		throw new Error("Unknown object type");
	}

	if(mark) for(const key of mark) projection.delete(key);

	return projection;
}

/**
 * Project some sequence of values onto a Multimap using keys generated from
 * {@link surrogate}.
 * @param values Sequence of values to project
 * @param surrogate A callback that generates a surrogate key for projection.
 * @param bare When true, {@link values} is treated as a bare object.
 * @param onto Project onto a specific Multimap, rather than constructing new.
 * @returns A multimap of surrogate keys pointing to Sets of their associated
 * values.
 */
export function projectMulti<K, V, L>(values: ReadonlyMap<L, V> | ReadonlyMultimap<L, V>, surrogate?: (value: NoInfer<V>, primary: NoInfer<L>) => K, bare?: false, onto?: Multimap<K, V>): Multimap<K, V>;
export function projectMulti<K, V>(values: Iterable<V>, surrogate: (value: NoInfer<V>) => K, bare?: false, onto?: Multimap<K, V>): Multimap<K, V>;
export function projectMulti<K, V>(values: readonly V[], surrogate?: (value: NoInfer<V>, primary: number) => K, bare?: false, onto?: Multimap<K, V>): Multimap<K, V>;
export function projectMulti<K, V, L extends PropertyKey>(values: { [key in L]: V }, surrogate: undefined | ((value: NoInfer<V>, primary: NoInfer<L>) => K), bare: true, onto?: Multimap<K, V>): Multimap<K, V>;
export function projectMulti(values: object, surrogate: (value: any, primary?: any) => any = identityProjection, bare?: boolean, onto?: Multimap<unknown, unknown>): Multimap<unknown, unknown> {
	const projection = onto || new Multimap<unknown, unknown>();
	const mark = onto ? new Multimap(onto) : null;
	if(bare) {
		for(const [primary, value] of Object.entries(values)) {
			const key = surrogate(value, primary)
			projection.set(key, value);
			if(mark) mark.delete(key, value);
		}
	}
	else if(values instanceof Map || values instanceof Multimap) {
		for(const [primary, value] of values) {
			const key = surrogate(value, primary)
			projection.set(key, value);
			if(mark) mark.delete(key, value);
		}
	}
	else if(values instanceof Set) {
		for(const value of values) {
			const key = surrogate(value)
			projection.set(key, value);
			if(mark) mark.delete(key, value);
		}
	}
	else if(Array.isArray(values)) {
		for(let i = 0, len = values.length; i !== len; i++) {
			const key = surrogate(values[i], i)
			projection.set(key, values[i]);
			if(mark) mark.delete(key, values[i]);
		}
	}
	else if(Symbol.iterator in values) {
		for(const value of values as any) {
			const key = surrogate(value)
			projection.set(key, value);
			if(mark) mark.delete(key, value);
		}
	}
	else {
		throw new Error("Unknown object type");
	}

	if(mark) for(const [key, value] of mark) projection.delete(key, value);

	return projection;
}

/**
 * Project some sequence of values onto a dict using keys generated by
 * {@link surrogate}. Values with the same surrogate key will overwrite, with
 * the later insertion order overwriting the earlier.
 * @param values Sequence of values to project.
 * @param surrogate A callback that generates a surrogate key for projection.
 * @param bare When true, {@link values} is treated as a bare object.
 * @param onto Project onto a specific dict, rather than constructing new.
 * @returns A map of surrogate keys pointing to an associated value.
 */
export function projectDict<K extends PropertyKey, V, L>(values: ReadonlyMap<L, V> | ReadonlyMultimap<L, V>, surrogate?: (value: NoInfer<V>, primary: NoInfer<L>) => K, bare?: false, onto?: { [P in K]: V }): { [P in K]: V }
export function projectDict<K extends PropertyKey, V>(values: Iterable<V>, surrogate: (value: NoInfer<V>) => K, bare?: false, onto?: { [P in K]: V }): { [P in K]: V };
export function projectDict<K extends PropertyKey, V>(values: readonly V[], surrogate?: (value: NoInfer<V>, primary: number) => K, bare?: false, onto?: { [P in K]: V }): { [P in K]: V };
export function projectDict<K extends PropertyKey, V, L extends PropertyKey>(values: { [key in L]: V }, surrogate: undefined | ((value: NoInfer<V>, primary: NoInfer<L>) => K), bare: true, onto?: { [P in K]: V }): { [P in K]: V };
export function projectDict(values: object, surrogate: (value: any, primary?: any) => any = identityProjection, bare?: boolean, onto?: { [P in PropertyKey]: unknown }): { [P in PropertyKey]: unknown } {
	const projection = {} as { [P in PropertyKey]: unknown };
	const mark = onto ? new Set(Object.keys(onto)) : null
	if(bare) {
		for(const [primary, value] of Object.entries(values)) {
			const key = surrogate(value, primary);
			projection[key] = value;
			if(mark) mark.delete(key);
		}
	}
	else if(values instanceof Map || values instanceof Multimap) {
		for(const [primary, value] of values) {
			const key = surrogate(value, primary);
			projection[key] = value;
			if(mark) mark.delete(key);
		}
	}
	else if(values instanceof Set) {
		for(const value of values) {
			const key = surrogate(value);
			projection[key] = value;
			if(mark) mark.delete(key);
		}
	}
	else if(Array.isArray(values)) {
		for(let i = 0, len = values.length; i !== len; i++) {
			const key = surrogate(values[i], i);
			projection[key] = values[i];
			if(mark) mark.delete(key);
		}
	}
	else if(Symbol.iterator in values) {
		for(const value of values as any) {
			const key = surrogate(value);
			projection[key] = value;
			if(mark) mark.delete(key);
		}
	}
	else {
		throw new Error("Unknown object type");
	}

	if(mark) for(const [key, value] of mark) delete projection[key];

	return projection;
}

/**
 * Returns a projection that will propagate changes back to {@link values}. If
 * {@link projection} is a Map, the map's `set` and `get` methods are modified.
 * If {@link projection} is a dict, a `Proxy` object is returned.
 * @param projection A projection of {@link values} by either {@link project} or
 * {@link projectDict}.
 * @param values The originating `Set` that was projected.
 */
export function proxySet<T>(projection: Map<unknown, T> | Multimap<unknown, T>, values: Set<T>): Map<unknown, T>;
export function proxySet<T>(projection: Record<any, T>, values: Set<T>): Record<any, T>;
export function proxySet<T>(projection: Map<unknown, T> | Multimap<unknown, T> | Record<any, T>, values: Set<T>): Map<unknown, T> | Record<any, T> {
	if(projection instanceof Map || projection instanceof Multimap) {
		const set = projection.set;
		const del = projection.delete;
		projection.set = function (this: typeof projection, key: unknown, value: T) {
			if(this.has(key, value)) values.delete(this.get(key, value)!);
			values.add(value);
			return set.call(this, key, value);
		};

		projection.delete = function (this: typeof projection, key: unknown, value?: T) {
			if(this.has(key, value)) values.delete(this.get(key, value)!);
			return (del as Function).call(this, key, value);
		};

		return projection;
	}
	else {
		return new Proxy(projection, {
			set(obj, prop, value) {
				if(prop in obj) values.delete(obj[prop as any]);
				values.add(value);
				obj[prop as any] = value;
				return true;
			},
			deleteProperty(obj, prop) {
				if(prop in obj) values.delete(obj[prop as any]);
				delete obj[prop as any];
				return true;
			},
		})
	}
}

const PLACEHOLDER: any = Symbol("Placeholder for recycled sinks, preserving map insertion order");
const DEFAULT_MAP: ReadonlyMap<any, any> = new Map();
const DEFAULT_DICT = Object.freeze({});

/**
 * Remap transforms the {@link output} Map by synchronizing its keyset with that
 * of the {@link input} Map. For keys belonging to only input, new values are
 * constructed by the {@link create} callback and are assigned to corresponding
 * keys on the output. For keys belonging to both input and output, updated
 * values are constructed or updated in place by the {@link update} callback and
 * are assigned to corresponding keys on the output. For keys belonging only to
 * output, the values are cleaned up by the {@link destroy} callback before
 * being removed from output.
 *
 * It is intended that, over the lifetime of the application, remap will be
 * called multiple times on the same input and output, synchronizing the state
 * of the two maps.
 *
 * Remap optionally supports recycling values that are to be removed from output
 * if {@link shouldRecycleRemoved} is true. If enabled, instead of calling
 * {@link create} to construct a new value, a removed value is selected and
 * passed to {@link recycle} and the value is assigned to the associated key on
 * output. Later, {@link update} will be called on the recycled value, as if it
 * belonged to a key on both input and output.
 *
 * Regardless of the state of {@link shouldRecycleRemoved}, the optional map
 * {@link recycleMap} may be used to force the use of specific values in
 * recycling specific keys. Values in {@link recycleMap} are only used if there
 * is a corresponding key on input. {@link recycle} will be called on any values
 * that are used from the map with `key === origin`, unless the key already
 * exists on output and the corresponding value is strictly equivalent to the
 * value in {@link recycleMap}, in which case the mapping is simply ignored.
 *
 * {@link recycleMap} may specify values that presently exist on output,
 * allowing the user to manually specify moved values.
 *
 * Output values are removed in output insertion order. Removed output values
 * are recycled in output insertion order. Output values are added/updated in
 * input insertion order.
 *
 * Remap performs actions in stages: First all calls to {@link recycle} are
 * made, with explicit {@link recycleMap} values being recycled first, and
 * removed values being recycled thereafter. Second all calls to {@link destroy}
 * are made. Third, and finally, all calls to {@link create} and {@link update}
 * are made, with no definite ordering between either kind of call.
 *
 * @param input A readonly map of keys and values.
 * @param output A mutable map that will be transformed to match input.
 * @param create A callback that constructs a new value for output.
 * @param update A callback that updates or reconstructs a value for output.
 * @param destroy A callback that cleans up an output value that has been
 * removed and will not be reused.
 * @param shouldRecycleRemoved True when values should be preferentially
 * recycled instead of being removed.
 * @param recycle A callback that cleans up and prepares a value for reuse. When
 * undefined, and {@link destroy} is defined, destroy will be used instead.
 * Disable by assigning null.
 * @param recycleMap A Map of keys to values, requiring that for the indicated
 * keys, the associated value must be used inplace of a new value or any other
 * recycled value.
 * @returns True if the set of output keys changed.
 * @see project
 * @see remapDict
 */
export function remap<U, V, K>(
	input: ReadonlyMap<K, U>,
	output: Map<K, V>,
	create: (source: U, key: K) => V,
	update?: (sink: V, source: U, key: K) => V,
	destroy?: (sink: V, origin: K) => unknown,
	shouldRecycleRemoved: boolean = true,
	recycle: undefined | null | ((sink: V, origin: K, source: U, key: K) => unknown) = destroy,
	recycleMap: ReadonlyMap<K, V> = DEFAULT_MAP,
) {
	const inverseRecycleMap: ReadonlyMap<V, K> = new Map(swap(recycleMap));
	const removed = new Map<K, V>();
	let keysChanged = false;

	// First pass: Remove deleted keys from output.
	for(const [key, sink] of output) {
		if(!input.has(key)) {
			// If the key isn't present in the input we need to remove the
			// corresponding key and sink from the output.
			output.delete(key);
			keysChanged = true;

			if(!inverseRecycleMap.has(sink)) {
				// If the user hasn't requeste that this sink be recycled, add
				// it into the general removed pool.
				removed.set(key, sink);
			}
		}
		else if(inverseRecycleMap.has(sink)) {
			// If the user has requested that this sink be recycled onto a
			// different key, we must treat the corresponding output key as if
			// it were deleted.
			output.set(key, PLACEHOLDER as any);
		}
		else if(recycleMap.has(key)) {
			// If the user has requested that this key be recycled from another
			// sink, we need to check that the replacement sink is actually
			// different than the current sink. This is because we only want to
			// call recycle() on sinks that have changed keys.
			const replacement = recycleMap.get(key)!;
			if(replacement !== sink) {
				output.set(key, replacement);
				if(recycle) recycle(replacement, key, input.get(key)!, key);

				// We've already checked that the sink isn't being recycled onto
				// another key.
				if(sink !== PLACEHOLDER) removed.set(key, sink);
			}

			// Otherwise, we leave the key alone, so it can be updated just as
			// if it were never recycled.
		}

		// Otherwise, this particular key on the output will be updated.
	}

	// Second pass: Fill in new keys with recycled sinks where possible
	const it = removed.entries();
	if(shouldRecycleRemoved) {
		for(const [key, source] of input) {
			if(output.has(key)) {
				// If the output has a matching key and the corresponding sink
				// isn't a PLACEHOLDER, we don't need to recycle anything,
				if(output.get(key) !== PLACEHOLDER) continue;
			}
			else {
				// If the output doesn't have a matching key, this is a new
				// key that's being given a recycled sink.
				keysChanged = true;
			}

			const { value, done } = it.next();
			if(done) break;

			const [origin, sink] = value;
			if(recycle) recycle(sink, origin, source, key);
			output.set(key, sink);
		}
	}

	// Clean up removed sinks that didn't get recycled.
	if(destroy) for(const [origin, sink] of it) destroy(sink, origin);

	// Third pass: Update matching keys, and create new sinks where necessary.
	for(const [key, source] of input) {
		if(!output.has(key) || output.get(key) === PLACEHOLDER) {
			// If we ran out of removed nodes to recycle (or recycling was disabled),
			// we need to be sure to fill in the PLACEHOLDER values.
			output.set(key, create(source, key));
			keysChanged = true;
		}
		else {
			const sink = output.get(key)!;
			output.set(key, update ? update(sink, source, key) : sink);
		}
	}

	return keysChanged;
}

/**
 * remapDict transforms the {@link output} dict by synchronizing its keyset with
 * that of the {@link input} dict. For keys belonging to only input, new values
 * are constructed by the {@link create} callback and are assigned to
 * corresponding keys on the output. For keys belonging to both input and
 * output, updated values are constructed or updated in place by the
 * {@link update} callback and are assigned to corresponding keys on the output.
 * For keys belonging only to output, the values are cleaned up by the
 * {@link destroy} callback before being removed from output.
 *
 * It is intended that, over the lifetime of the application, remapDict will be
 * called multiple times on the same input and output, synchronizing the state
 * of the two dicts.
 *
 * remapDict optionally supports recycling values that are to be removed from
 * output if {@link shouldRecycleRemoved} is true. If enabled, instead of
 * calling {@link create} to construct a new value, a removed value is selected
 * and passed to {@link recycle} and the value is assigned to the associated key
 * on output. Later, {@link update} will be called on the recycled value, as if
 * it belonged to a key on both input and output.
 *
 * Regardless of the state of {@link shouldRecycleRemoved}, the optional dict
 * {@link recycleDict} may be used to force the use of specific values in
 * recycling specific keys. Values in {@link recycleDict} are only used if there
 * is a corresponding key on input. {@link recycle} will be called on any values
 * that are used from the dict with `key === origin`, unless the key already
 * exists on output and the corresponding value is strictly equivalent to the
 * value in {@link recycleDict}, in which case the mapping is simply ignored.
 *
 * {@link recycleDict} may specify values that presently exist on output,
 * allowing the user to manually specify moved values.
 *
 * Output values are removed in output insertion order. Removed output values
 * are recycled in output insertion order. Output values are added/updated in
 * input insertion order.
 *
 * remapDict performs actions in stages: First all calls to {@link recycle} are
 * made, with explicit {@link recycleDict} values being recycled first, and
 * removed values being recycled thereafter. Second all calls to {@link destroy}
 * are made. Third, and finally, all calls to {@link create} and {@link update}
 * are made, with no definite ordering between either kind of call.
 *
 * @param input A readonly dict of keys and values. Map
 * @param output A mutable dict that will be transformed to match input.
 * @param create A callback that constructs a new value for output.
 * @param update A callback that updates or reconstructs a value for output.
 * @param destroy A callback that cleans up an output value that has been
 * removed and will not be reused.
 * @param shouldRecycleRemoved True when values should be preferentially
 * recycled instead of being removed.
 * @param recycle A callback that cleans up and prepares a value for reuse. When
 * undefined, and {@link destroy} is defined, destroy will be used instead.
 * Disable by assigning null.
 * @param recycleDict A dict of keys to values, requiring that for the indicated
 * keys, the associated value must be used inplace of a new value or any other
 * recycled value.
 * @returns True if the set of output keys changed.
 *
 * @see projectDict
 * @see remap
 */
export function remapDict<U, V>(
	input: { readonly [key: string]: U },
	output: { [key: string]: V },
	create: (source: U, key: string) => NoInfer<V>,
	update?: (sink: V, source: U, key: string) => NoInfer<V>,
	destroy?: (sink: V, origin: string) => unknown,
	shouldRecycleRemoved: boolean = true,
	recycle: undefined | null | ((sink: V, origin: string, source: U, key: string) => unknown) = destroy,
	recycleDict: { readonly [key: string]: NoInfer<V> } = DEFAULT_DICT,
) {
	const inverseRecycleMap: ReadonlyMap<V, string> = new Map(swap(Object.entries(recycleDict)));
	const removed: { [key: string]: V } = {};
	let keysChanged = false;

	// First pass: Remove deleted keys from output.
	for(const key in output) {
		const sink = output[key];

		if(!(key in input)) {
			// If the key isn't present in the input we need to remove the
			// corresponding key and sink from the output.
			delete output[key];
			keysChanged = true;

			if(!inverseRecycleMap.has(sink)) {
				// If the user hasn't requeste that this sink be recycled, add
				// it into the general removed pool.
				removed[key] = sink;
			}
		}
		else if(inverseRecycleMap.has(sink)) {
			// If the user has requested that this sink be recycled onto a
			// different key, we must treat the corresponding output key as if
			// it were deleted.
			output[key] = PLACEHOLDER;
		}
		else if(key in recycleDict) {
			// If the user has requested that this key be recycled from another
			// sink, we need to check that the replacement sink is actually
			// different than the current sink. This is because we only want to
			// call recycle() on sinks that have changed keys.
			const replacement = recycleDict[key];
			if(replacement !== sink) {
				output[key] = replacement;
				if(recycle) recycle(replacement, key, input[key], key);

				// We've already checked that the sink isn't being recycled onto
				// another key.
				if(sink !== PLACEHOLDER) removed[key] = sink;
			}

			// Otherwise, we leave the key alone, so it can be updated just as
			// if it were never recycled.
		}

		// Otherwise, this particular key on the output will be updated.
	}

	// Second pass: Fill in new keys with recycled sinks where possible
	const it = Object.keys(removed).values();
	if(shouldRecycleRemoved) {
		for(const key in input) {
			if(key in output) {
				// If the output has a matching key and the corresponding sink
				// isn't a PLACEHOLDER, we don't need to recycle anything,
				if(output[key] !== PLACEHOLDER) continue;
			}
			else {
				// If the output doesn't have a matching key, this is a new
				// key that's being given a recycled sink.
				keysChanged = true;
			}

			const { value: origin, done } = it.next();
			if(done) break;

			const sink = removed[origin];
			if(recycle) recycle(sink, origin, input[key], key);
			output[key] = sink;
		}
	}

	// Clean up removed sinks that didn't get recycled.
	if(destroy) for(const origin of it) destroy(removed[origin], origin);

	// Third pass: Update matching keys, and create new sinks where necessary.
	for(const key in input) {
		const source = input[key];
		if(!(key in output) || output[key] === PLACEHOLDER) {
			// If we ran out of removed nodes to recycle (or recycling was disabled),
			// we need to be sure to fill in the PLACEHOLDER values.
			output[key] = create(source, key);
			keysChanged = true;
		}
		else {
			const sink = output[key]
			output[key] = update ? update(sink, source, key) : sink;
		}
	}

	return keysChanged;
}

export function remapMove<K,V>(output: Map<K, V>, value: V, from: K, to: K): [V] | [] {
	if(output.get(from)! === value) output.delete(from);
	let replaced: [V] | [] = output.has(to) ? [output.get(to)!] : [];
	output.set(to, value);
	return replaced;
}

export function remapDictMove<K extends PropertyKey, V>(output: { [P in K]: V }, value: V, from: K, to: K): [V] | [] {
	if(output[from] === value) delete output[from];
	let replaced: [V] | [] = to in output ? [ output[to] ] : [];
	output[to] = value;
	return replaced;
}

/**
 * Transform an iterable sequence of `[key, value]` tuples by reversing each
 * tuple in the sequence.
 * @param iterable Some iterable sequence of keys and values.
 */
function* swap<K, V>(iterable: Iterable<[K, V]>): Iterable<[V, K]> {
	for(const [key, value] of iterable) yield [value, key];
}