Hash set.

// FNV-1a over the value's UTF-8 bytes. Simple and identical in every language,
// so a value lands in the same slot in TypeScript and Go.
export function hashKey(value: string): number {
	let hash = 2166136261;
	for (const byte of new TextEncoder().encode(value)) {
		hash ^= byte;
		hash = Math.imul(hash, 16777619) >>> 0;
	}
	return hash;
}

export type Step = {
	kind: 'hash' | 'skip' | 'compare' | 'match' | 'empty' | 'insert' | 'delete' | 'rebuild' | 'move';
	value: string;
	/** The slot looked at; the old capacity for rebuild; the old slot for move. */
	slot: number;
	/** The full hash for hash; the new capacity for rebuild; the new slot for move;
	 * 1 when insert reused a tombstone, 0 when it took an empty slot; otherwise -1. */
	detail: number;
};
export type Slot = { state: 'empty' } | { state: 'tombstone' } | { state: 'live'; value: string };

const TOMBSTONE = Symbol('tombstone');
type Cell = string | typeof TOMBSTONE | undefined;
type Found = { found: number; tombstone: number; empty: number };

// Open addressing: every value lives in the slots array itself. A value starts at
// its hash's slot and walks forward until it finds itself or an empty slot.
// Deleting leaves a tombstone, so walks that pass through that slot keep going.
// Live values plus tombstones never fill more than half the slots.
export class StringSet {
	#cells: Cell[] = new Array(8).fill(undefined);
	#size = 0;
	#tombstones = 0;
	#probes = 0;
	#steps: Step[] = [];
	#capture: boolean;

	constructor(capture = false) {
		this.#capture = capture;
	}
	get size(): number {
		return this.#size;
	}
	get capacity(): number {
		return this.#cells.length;
	}
	get tombstones(): number {
		return this.#tombstones;
	}
	/** Slots looked at by every has, add, and delete so far. */
	get probes(): number {
		return this.#probes;
	}

	has(value: string): boolean {
		this.#steps = [];
		return this.#find(value).found >= 0;
	}

	add(value: string): 'added' | 'present' {
		this.#steps = [];
		let place = this.#find(value);
		if (place.found >= 0) return 'present';
		// Reusing a tombstone takes no new room. Taking an empty slot might.
		if (place.tombstone < 0 && (this.#size + this.#tombstones + 1) * 2 > this.capacity) {
			this.#rebuild();
			place = this.#find(value);
		}
		const reused = place.tombstone >= 0;
		const slot = reused ? place.tombstone : place.empty;
		this.#cells[slot] = value;
		this.#size++;
		if (reused) this.#tombstones--;
		this.#record('insert', value, slot, reused ? 1 : 0);
		return 'added';
	}

	delete(value: string): 'deleted' | 'missing' {
		this.#steps = [];
		const { found } = this.#find(value);
		if (found < 0) return 'missing';
		this.#cells[found] = TOMBSTONE;
		this.#size--;
		this.#tombstones++;
		this.#record('delete', value, found, -1);
		return 'deleted';
	}

	// Slot order: neither insertion order nor sorted.
	values(): string[] {
		return this.#cells.filter((cell): cell is string => typeof cell === 'string');
	}

	slots(): Slot[] {
		return this.#cells.map((cell) =>
			cell === undefined
				? { state: 'empty' }
				: cell === TOMBSTONE
					? { state: 'tombstone' }
					: { state: 'live', value: cell }
		);
	}

	trace(): Step[] {
		return this.#steps.map((step) => ({ ...step }));
	}

	#find(value: string): Found {
		const hash = hashKey(value);
		const mask = this.capacity - 1;
		const start = hash & mask;
		this.#record('hash', value, start, hash);
		let tombstone = -1;
		for (let i = 0; i < this.capacity; i++) {
			const slot = (start + i) & mask;
			const cell = this.#cells[slot];
			this.#probes++;
			if (cell === undefined) {
				this.#record('empty', value, slot, -1);
				return { found: -1, tombstone, empty: slot };
			}
			if (cell === TOMBSTONE) {
				this.#record('skip', value, slot, -1);
				if (tombstone < 0) tombstone = slot;
				continue;
			}
			if (cell === value) {
				this.#record('match', value, slot, -1);
				return { found: slot, tombstone, empty: -1 };
			}
			this.#record('compare', value, slot, -1);
		}
		throw new Error('No empty slot: the table is never more than half full.');
	}

	// Double if the live values alone would pass half; otherwise just clear the tombstones.
	#rebuild(): void {
		const old = this.#cells;
		const capacity = (this.#size + 1) * 2 > old.length ? old.length * 2 : old.length;
		this.#record('rebuild', '', old.length, capacity);
		this.#cells = new Array(capacity).fill(undefined);
		this.#tombstones = 0;
		const mask = capacity - 1;
		old.forEach((cell, from) => {
			if (typeof cell !== 'string') return;
			let to = hashKey(cell) & mask;
			while (this.#cells[to] !== undefined) to = (to + 1) & mask;
			this.#cells[to] = cell;
			this.#record('move', cell, from, to);
		});
	}

	#record(kind: Step['kind'], value: string, slot: number, detail: number): void {
		if (this.#capture) this.#steps.push({ kind, value, slot, detail });
	}
}

// HashKey is FNV-1a over the value's UTF-8 bytes. Simple and identical in every
// language, so a value lands in the same slot in Go and TypeScript.
func HashKey(value string) uint32 {
	hash := uint32(2166136261)
	for i := 0; i < len(value); i++ {
		hash ^= uint32(value[i])
		hash *= 16777619
	}
	return hash
}

type Step struct {
	Kind  string `json:"kind"`
	Value string `json:"value"`
	// The slot looked at; the old capacity for rebuild; the old slot for move.
	Slot int `json:"slot"`
	// The full hash for hash; the new capacity for rebuild; the new slot for move;
	// 1 when insert reused a tombstone, 0 when it took an empty slot; otherwise -1.
	Detail int64 `json:"detail"`
}

type cellState uint8

const (
	empty cellState = iota
	tombstone
	live
)

type cell struct {
	state cellState
	value string
}

// Slot is an inspection copy of one cell: State is "empty", "tombstone", or "live".
type Slot struct {
	State string
	Value string
}

// StringSet uses open addressing: every value lives in the cells slice itself. A
// value starts at its hash's slot and walks forward until it finds itself or an
// empty slot. Deleting leaves a tombstone, so walks through that slot keep going.
// Live values plus tombstones never fill more than half the cells.
type StringSet struct {
	cells      []cell
	size       int
	tombstones int
	probes     int
	steps      []Step
	capture    bool
}

func NewStringSet(capture bool) *StringSet {
	return &StringSet{cells: make([]cell, 8), capture: capture}
}

func (s *StringSet) Len() int        { return s.size }
func (s *StringSet) Capacity() int   { return len(s.cells) }
func (s *StringSet) Tombstones() int { return s.tombstones }

// Probes counts slots looked at by every Has, Add, and Delete so far.
func (s *StringSet) Probes() int { return s.probes }

func (s *StringSet) Has(value string) bool {
	s.steps = nil
	found, _, _ := s.find(value)
	return found >= 0
}

// Add returns "added" or "present".
func (s *StringSet) Add(value string) string {
	s.steps = nil
	found, grave, open := s.find(value)
	if found >= 0 {
		return "present"
	}
	// Reusing a tombstone takes no new room. Taking an empty slot might.
	if grave < 0 && (s.size+s.tombstones+1)*2 > len(s.cells) {
		s.rebuild()
		found, grave, open = s.find(value)
	}
	slot, reused := open, int64(0)
	if grave >= 0 {
		slot, reused = grave, 1
		s.tombstones--
	}
	s.cells[slot] = cell{live, value}
	s.size++
	s.record("insert", value, slot, reused)
	return "added"
}

// Delete returns "deleted" or "missing".
func (s *StringSet) Delete(value string) string {
	s.steps = nil
	found, _, _ := s.find(value)
	if found < 0 {
		return "missing"
	}
	s.cells[found] = cell{state: tombstone}
	s.size--
	s.tombstones++
	s.record("delete", value, found, -1)
	return "deleted"
}

// Values returns the live values in slot order: neither insertion order nor sorted.
func (s *StringSet) Values() []string {
	values := make([]string, 0, s.size)
	for _, c := range s.cells {
		if c.state == live {
			values = append(values, c.value)
		}
	}
	return values
}

func (s *StringSet) Slots() []Slot {
	slots := make([]Slot, len(s.cells))
	for i, c := range s.cells {
		slots[i] = Slot{[...]string{"empty", "tombstone", "live"}[c.state], c.value}
	}
	return slots
}

func (s *StringSet) Trace() []Step { return append([]Step{}, s.steps...) }

// find returns the value's slot or -1, the first tombstone passed or -1, and the
// empty slot that ended the walk or -1.
func (s *StringSet) find(value string) (found, grave, open int) {
	hash := HashKey(value)
	mask := len(s.cells) - 1
	start := int(hash) & mask
	s.record("hash", value, start, int64(hash))
	grave = -1
	for i := 0; i < len(s.cells); i++ {
		slot := (start + i) & mask
		s.probes++
		switch c := s.cells[slot]; {
		case c.state == empty:
			s.record("empty", value, slot, -1)
			return -1, grave, slot
		case c.state == tombstone:
			s.record("skip", value, slot, -1)
			if grave < 0 {
				grave = slot
			}
		case c.value == value:
			s.record("match", value, slot, -1)
			return slot, grave, -1
		default:
			s.record("compare", value, slot, -1)
		}
	}
	panic("no empty slot: the table is never more than half full")
}

// rebuild doubles if the live values alone would pass half; otherwise it only
// clears the tombstones.
func (s *StringSet) rebuild() {
	old := s.cells
	capacity := len(old)
	if (s.size+1)*2 > capacity {
		capacity *= 2
	}
	s.record("rebuild", "", len(old), int64(capacity))
	s.cells = make([]cell, capacity)
	s.tombstones = 0
	mask := capacity - 1
	for from, c := range old {
		if c.state != live {
			continue
		}
		to := int(HashKey(c.value)) & mask
		for s.cells[to].state != empty {
			to = (to + 1) & mask
		}
		s.cells[to] = c
		s.record("move", c.value, from, int64(to))
	}
}

func (s *StringSet) record(kind, value string, slot int, detail int64) {
	if s.capture {
		s.steps = append(s.steps, Step{kind, value, slot, detail})
	}
}