Skip to content

Instantly share code, notes, and snippets.

@jesseschalken
Created July 17, 2020 18:57
Show Gist options
  • Save jesseschalken/858b720516a3514b53a19910aecc5aff to your computer and use it in GitHub Desktop.
Save jesseschalken/858b720516a3514b53a19910aecc5aff to your computer and use it in GitHub Desktop.
export interface HashImpl<T> {
hash?(value: T): unknown;
equals(a: T, b: T): boolean;
}
export class AssociationList<K, V> implements Map<K, V> {
private inner: {readonly key: K; value: V}[] = [];
constructor(
private readonly impl: HashImpl<K>,
entries: Iterable<[K, V]> = [],
) {
for (const [k, v] of entries) {
this.set(k, v);
}
}
get [Symbol.toStringTag]() {
return "AssociationList";
}
get size(): number {
return this.inner.length;
}
[Symbol.iterator](): IterableIterator<[K, V]> {
return this.entries();
}
clear(): void {
this.inner = [];
}
delete(key: K): boolean {
for (let i = 0; i < this.inner.length; i++) {
const obj = this.inner[i];
if (this.impl.equals(obj.key, key)) {
this.inner.splice(i, 1);
return true;
}
}
return false;
}
*entries(): IterableIterator<[K, V]> {
for (const obj of this.inner) {
yield [obj.key, obj.value];
}
}
forEach(
callbackfn: (value: V, key: K, map: Map<K, V>) => void,
thisArg?: any,
): void {
for (const obj of this.inner) {
callbackfn.call(thisArg, obj.value, obj.key, this);
}
}
get(key: K): V | undefined {
for (const obj of this.inner) {
if (this.impl.equals(obj.key, key)) {
return obj.value;
}
}
return undefined;
}
has(key: K): boolean {
for (const obj of this.inner) {
if (this.impl.equals(obj.key, key)) {
return true;
}
}
return false;
}
*keys(): IterableIterator<K> {
for (const obj of this.inner) {
yield obj.key;
}
}
set(key: K, value: V): this {
for (const obj of this.inner) {
if (this.impl.equals(obj.key, key)) {
obj.value = value;
return this;
}
}
this.inner.push({key, value});
return this;
}
*values(): IterableIterator<V> {
for (const obj of this.inner) {
yield obj.value;
}
}
}
export class HashMap<K, V> implements Map<K, V> {
private readonly lists = new Map<unknown, AssociationList<K, V>>();
constructor(
private readonly impl: HashImpl<K>,
entries: Iterable<[K, V]> = [],
) {
for (const [k, v] of entries) {
this.set(k, v);
}
}
get [Symbol.toStringTag]() {
return "HashMap";
}
get size() {
let ret = 0;
for (const lists of this.lists.values()) {
ret += lists.size;
}
return ret;
}
*[Symbol.iterator](): IterableIterator<[K, V]> {
for (const list of this.lists.values()) {
yield* list;
}
}
clear(): void {
this.lists.clear();
}
delete(key: K): boolean {
const list = this.lists.get(this.impl.hash?.(key));
return list ? list.delete(key) : false;
}
entries(): IterableIterator<[K, V]> {
return this[Symbol.iterator]();
}
forEach(
callbackfn: (value: V, key: K, map: Map<K, V>) => void,
thisArg?: any,
): void {
for (const list of this.lists.values()) {
for (const [key, value] of list) {
callbackfn.call(thisArg, value, key, this);
}
}
}
get(key: K): V | undefined {
const list = this.lists.get(this.impl.hash?.(key));
return list ? list.get(key) : undefined;
}
has(key: K): boolean {
const list = this.lists.get(this.impl.hash?.(key));
return list ? list.has(key) : false;
}
*keys(): IterableIterator<K> {
for (const list of this.lists.values()) {
yield* list.keys();
}
}
set(key: K, value: V): this {
const hash = this.impl.hash?.(key);
let list = this.lists.get(hash);
if (!list) {
list = new AssociationList(this.impl);
this.lists.set(hash, list);
}
list.set(key, value);
return this;
}
*values(): IterableIterator<V> {
for (const list of this.lists.values()) {
yield* list.values();
}
}
}
export class MultiMap<K, V> implements Map<K, V> {
private readonly map: Map<K, V[]>;
constructor(
makeMap: <T>() => Map<K, T> = <T>() => new Map(),
entries: Iterable<[K, V]> = [],
) {
this.map = makeMap();
for (const [k, v] of entries) {
this.set(k, v);
}
}
set(key: K, value: V): this {
this.map.set(key, [value]);
return this;
}
add(key: K, value: V): this {
let list = this.map.get(key);
if (!list) {
list = [];
this.map.set(key, list);
}
list.push(value);
return this;
}
get size() {
let ret = 0;
for (const v of this.map.values()) {
ret += v.length;
}
return ret;
}
readonly [Symbol.toStringTag]: string;
[Symbol.iterator](): IterableIterator<[K, V]> {
return this.entries();
}
clear(): void {
this.map.clear();
}
delete(key: K): boolean {
const list = this.map.get(key);
if (list) {
this.map.delete(key);
if (list.length > 0) {
return true;
}
}
return false;
}
*entries(): IterableIterator<[K, V]> {
for (const [k, list] of this.map) {
for (const value of list) {
yield [k, value];
}
}
}
forEach(
callbackfn: (value: V, key: K, map: Map<K, V>) => void,
thisArg?: any,
): void {
for (const [key, list] of this.map) {
for (const value of list) {
callbackfn.call(thisArg, value, key, this);
}
}
}
get(key: K): V | undefined {
const list = this.map.get(key);
return list && list.length > 0 ? list[0] : undefined;
}
getAll(key: K): V[] {
return this.map.get(key) || [];
}
has(key: K): boolean {
const list = this.map.get(key);
return list ? list.length > 0 : false;
}
*keys(): IterableIterator<K> {
for (const [key, list] of this.map) {
if (list.length > 0) {
yield key;
}
}
}
*values(): IterableIterator<V> {
for (const list of this.map.values()) {
yield* list;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment