simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

StackedMap.js (3453B)

      1 /*
      2 	MIT License http://www.opensource.org/licenses/mit-license.php
      3 	Author Tobias Koppers @sokra
      4 */
      5 
      6 "use strict";
      7 
      8 const TOMBSTONE = Symbol("tombstone");
      9 const UNDEFINED_MARKER = Symbol("undefined");
     10 
     11 /**
     12  * @template T
     13  * @typedef {T | undefined} Cell<T>
     14  */
     15 
     16 /**
     17  * @template T
     18  * @typedef {T | typeof TOMBSTONE | typeof UNDEFINED_MARKER} InternalCell<T>
     19  */
     20 
     21 /**
     22  * @template K
     23  * @template V
     24  * @param {[K, InternalCell<V>]} pair the internal cell
     25  * @returns {[K, Cell<V>]} its “safe” representation
     26  */
     27 const extractPair = pair => {
     28 	const key = pair[0];
     29 	const val = pair[1];
     30 	if (val === UNDEFINED_MARKER || val === TOMBSTONE) {
     31 		return [key, undefined];
     32 	} else {
     33 		return /** @type {[K, Cell<V>]} */ (pair);
     34 	}
     35 };
     36 
     37 /**
     38  * @template K
     39  * @template V
     40  */
     41 class StackedMap {
     42 	/**
     43 	 * @param {Map<K, InternalCell<V>>[]=} parentStack an optional parent
     44 	 */
     45 	constructor(parentStack) {
     46 		/** @type {Map<K, InternalCell<V>>} */
     47 		this.map = new Map();
     48 		/** @type {Map<K, InternalCell<V>>[]} */
     49 		this.stack = parentStack === undefined ? [] : parentStack.slice();
     50 		this.stack.push(this.map);
     51 	}
     52 
     53 	/**
     54 	 * @param {K} item the key of the element to add
     55 	 * @param {V} value the value of the element to add
     56 	 * @returns {void}
     57 	 */
     58 	set(item, value) {
     59 		this.map.set(item, value === undefined ? UNDEFINED_MARKER : value);
     60 	}
     61 
     62 	/**
     63 	 * @param {K} item the item to delete
     64 	 * @returns {void}
     65 	 */
     66 	delete(item) {
     67 		if (this.stack.length > 1) {
     68 			this.map.set(item, TOMBSTONE);
     69 		} else {
     70 			this.map.delete(item);
     71 		}
     72 	}
     73 
     74 	/**
     75 	 * @param {K} item the item to test
     76 	 * @returns {boolean} true if the item exists in this set
     77 	 */
     78 	has(item) {
     79 		const topValue = this.map.get(item);
     80 		if (topValue !== undefined) {
     81 			return topValue !== TOMBSTONE;
     82 		}
     83 		if (this.stack.length > 1) {
     84 			for (let i = this.stack.length - 2; i >= 0; i--) {
     85 				const value = this.stack[i].get(item);
     86 				if (value !== undefined) {
     87 					this.map.set(item, value);
     88 					return value !== TOMBSTONE;
     89 				}
     90 			}
     91 			this.map.set(item, TOMBSTONE);
     92 		}
     93 		return false;
     94 	}
     95 
     96 	/**
     97 	 * @param {K} item the key of the element to return
     98 	 * @returns {Cell<V>} the value of the element
     99 	 */
    100 	get(item) {
    101 		const topValue = this.map.get(item);
    102 		if (topValue !== undefined) {
    103 			return topValue === TOMBSTONE || topValue === UNDEFINED_MARKER
    104 				? undefined
    105 				: topValue;
    106 		}
    107 		if (this.stack.length > 1) {
    108 			for (let i = this.stack.length - 2; i >= 0; i--) {
    109 				const value = this.stack[i].get(item);
    110 				if (value !== undefined) {
    111 					this.map.set(item, value);
    112 					return value === TOMBSTONE || value === UNDEFINED_MARKER
    113 						? undefined
    114 						: value;
    115 				}
    116 			}
    117 			this.map.set(item, TOMBSTONE);
    118 		}
    119 		return undefined;
    120 	}
    121 
    122 	_compress() {
    123 		if (this.stack.length === 1) return;
    124 		this.map = new Map();
    125 		for (const data of this.stack) {
    126 			for (const pair of data) {
    127 				if (pair[1] === TOMBSTONE) {
    128 					this.map.delete(pair[0]);
    129 				} else {
    130 					this.map.set(pair[0], pair[1]);
    131 				}
    132 			}
    133 		}
    134 		this.stack = [this.map];
    135 	}
    136 
    137 	asArray() {
    138 		this._compress();
    139 		return Array.from(this.map.keys());
    140 	}
    141 
    142 	asSet() {
    143 		this._compress();
    144 		return new Set(this.map.keys());
    145 	}
    146 
    147 	asPairArray() {
    148 		this._compress();
    149 		return Array.from(this.map.entries(), extractPair);
    150 	}
    151 
    152 	asMap() {
    153 		return new Map(this.asPairArray());
    154 	}
    155 
    156 	get size() {
    157 		this._compress();
    158 		return this.map.size;
    159 	}
    160 
    161 	createChild() {
    162 		return new StackedMap(this.stack);
    163 	}
    164 }
    165 
    166 module.exports = StackedMap;