Ported from Redux Toolkit's createEntityAdapter.

NormalizedState.ts

type EntityKey = string | number;

type EntityMap<T> = Record<EntityKey, T>;

type UpdatePayload<T> = { key: EntityKey; changes: Partial<T> };

type KeySelector<T> = (item: T) => EntityKey;

type EntitySorter<T> = (a: T, b: T) => number;

export function normalize<T>(items: T[], selectKey: KeySelector<T>) {
  const keys: EntityKey[] = [];
  const entities: EntityMap<T> = {};

  items.forEach((item) => {
    const key = selectKey(item);
    keys.push(key);
    entities[key] = item;
  });

  return [keys, entities] as const;
}

export function denormalize<T>(keys: EntityKey[], entities: EntityMap<T>) {
  return keys.map((key) => entities[key]);
}

function isArrayEqual(a: unknown[], b: unknown[]) {
  if (a.length !== b.length) return false;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }

  return true;
}

export type NormalizedStateOptions<T> = {
  keySelector: KeySelector<T>;
  entitySorter?: EntitySorter<T>;
};

export class NormalizedState<T> {
  keys: EntityKey[] = [];

  entities: EntityMap<T> = {};

  #keySelector: KeySelector<T>;

  #entitySorter: EntitySorter<T> | undefined;

  constructor(options: NormalizedStateOptions<T>) {
    this.#keySelector = options.keySelector;
    this.#entitySorter = options.entitySorter;
  }

  get list() {
    console.log('list');
    return denormalize(this.keys, this.entities);
  }

  get length() {
    return this.keys.length;
  }

  get(key: EntityKey) {
    return this.entities[key];
  }

  #merge(items: T[]) {
    items.forEach((item) => {
      this.entities[this.#keySelector(item)] = item;
    });

    const entities = Object.values(this.entities);
    if (this.#entitySorter) entities.sort(this.#entitySorter);

    const keys = entities.map(this.#keySelector);
    if (!isArrayEqual(keys, this.keys)) this.keys = keys;
  }

  #splitUpsertEntities(items: T[]) {
    const added: T[] = [];
    const updated: UpdatePayload<T>[] = [];

    items.forEach((item) => {
      const key = this.#keySelector(item);
      if (key in this.entities) {
        updated.push({ key, changes: item });
      } else {
        added.push(item);
      }
    });

    return [added, updated] as const;
  }

  setAll(list: T[]) {
    this.keys = [];
    this.entities = {};
    this.#merge(list);
  }

  addOne(item: T) {
    this.addMany([item]);
  }

  addMany(items: T[]) {
    items = items.filter((item) => !(this.#keySelector(item) in this.entities));
    if (items.length) this.#merge(items);
  }

  removeOne(key: EntityKey) {
    this.removeMany([key]);
  }

  removeMany(keys: EntityKey[]) {
    let count = 0;

    keys.forEach((key) => {
      if (key in this.entities) {
        delete this.entities[key];
        count++;
      }
    });

    if (count) {
      this.keys = this.keys.filter((key) => key in this.entities);
    }
  }

  removeAll() {
    this.keys = [];
    this.entities = {};
  }

  updateOne(payload: UpdatePayload<T>) {
    this.updateMany([payload]);
  }

  updateMany(payloads: UpdatePayload<T>[]) {
    const updated = payloads.reduce((items, { key, changes }) => {
      if (key in this.entities) {
        const original = this.entities[key];
        items.push(Object.assign({}, original, changes));
      }

      return items;
    }, [] as T[]);

    this.#merge(updated);
  }

  upsertOne(item: T) {
    this.upsertMany([item]);
  }

  upsertMany(items: T[]) {
    const [added, updated] = this.#splitUpsertEntities(items);
    this.updateMany(updated);
    this.addMany(added);
  }
}