HyperLogLog.

export type Step =
	/** raise or keep: an item's hash picked a register and a rank; the register keeps the larger. */
	| { kind: 'raise' | 'keep'; index: number; rank: number; before: number; after: number }
	/** merge: another sketch's register was larger, so this one takes it. */
	| { kind: 'merge'; index: number; before: number; after: number }
	/** sketch: the next sketch merged into a total. */
	| { kind: 'sketch'; station: string; day: string };

const encoder = new TextEncoder();

// FNV-1a over the UTF-8 bytes, then a final mix, so Go computes the same 32-bit hash.
function hash(text: string): number {
	let h = 0x811c9dc5;
	for (const byte of encoder.encode(text)) {
		h ^= byte;
		h = Math.imul(h, 0x01000193) >>> 0;
	}
	h ^= h >>> 16;
	h = Math.imul(h, 0x85ebca6b) >>> 0;
	h ^= h >>> 13;
	h = Math.imul(h, 0xc2b2ae35) >>> 0;
	h ^= h >>> 16;
	return h >>> 0;
}

// HyperLogLog estimates how many different items it has seen, in a fixed array of small
// registers. Each item's hash picks a register with its first bits, and the rest of the hash
// gives a rank: one more than its run of leading zeros. A run of k zeros turns up about once
// in 2^k different items, so the largest rank each register has seen says roughly how many
// items reached it. Seeing an item again changes nothing.
export class HyperLogLog {
	/** Bits of the hash that pick a register: 2^precision registers. */
	readonly precision: number;
	#registers: Uint8Array;

	constructor(precision = 12) {
		if (!Number.isInteger(precision) || precision < 4 || precision > 16)
			throw new RangeError('precision must be a whole number from 4 to 16');
		this.precision = precision;
		this.#registers = new Uint8Array(1 << precision);
	}

	/** Returns true when a register rose, which means the estimate may have changed. */
	add(item: string, steps?: Step[]): boolean {
		const h = hash(item);
		const index = h >>> (32 - this.precision);
		const rest = (h << this.precision) >>> 0;
		const rank = Math.min(Math.clz32(rest), 32 - this.precision) + 1;
		const before = this.#registers[index];
		const after = Math.max(before, rank);
		this.#registers[index] = after;
		steps?.push({ kind: after > before ? 'raise' : 'keep', index, rank, before, after });
		return after > before;
	}

	// Taking the larger register everywhere gives exactly the sketch of both sets together:
	// a union, without knowing a single item. Returns how many registers rose.
	merge(other: HyperLogLog, steps?: Step[]): number {
		if (other.precision !== this.precision)
			throw new RangeError('only sketches with the same precision can merge');
		let raised = 0;
		other.#registers.forEach((value, index) => {
			const before = this.#registers[index];
			if (value <= before) return;
			this.#registers[index] = value;
			steps?.push({ kind: 'merge', index, before, after: value });
			raised++;
		});
		return raised;
	}

	/** The estimated number of different items, with a standard error of about 1.04 ÷ √registers. */
	count(): number {
		const m = this.#registers.length;
		let sum = 0;
		let zeros = 0;
		for (const register of this.#registers) {
			sum += 1 / 2 ** register;
			if (register === 0) zeros++;
		}
		const alpha = m === 16 ? 0.673 : m === 32 ? 0.697 : m === 64 ? 0.709 : 0.7213 / (1 + 1.079 / m);
		let estimate = (alpha * m * m) / sum;
		// Few items leave empty registers, and counting those is more accurate than the harmonic mean.
		if (estimate <= 2.5 * m && zeros > 0) estimate = m * Math.log(m / zeros);
		// Near 2^32, different items start sharing whole 32-bit hashes; correct for that.
		else if (estimate > 2 ** 32 / 30)
			estimate = -(2 ** 32) * Math.log(1 - Math.min(estimate, 2 ** 32 - 1) / 2 ** 32);
		return Math.floor(estimate + 0.5);
	}

	registers(): number[] {
		return Array.from(this.#registers);
	}
}

// Step is one register touched. Kind is "raise" or "keep" (an item's hash picked register
// Index and a Rank; the register keeps the larger), "merge" (another sketch's register was
// larger, so this one takes it), or "sketch" (the next sketch merged into a total, from
// Station on Day).
type Step struct {
	Kind    string `json:"kind"`
	Index   int    `json:"index"`
	Rank    int    `json:"rank,omitempty"`
	Before  int    `json:"before"`
	After   int    `json:"after"`
	Station string `json:"station,omitempty"`
	Day     string `json:"day,omitempty"`
}

// hash is FNV-1a over the UTF-8 bytes, then a final mix, so TypeScript computes the same
// 32-bit hash.
func hash(text string) uint32 {
	h := uint32(0x811c9dc5)
	for i := 0; i < len(text); i++ {
		h ^= uint32(text[i])
		h *= 0x01000193
	}
	h ^= h >> 16
	h *= 0x85ebca6b
	h ^= h >> 13
	h *= 0xc2b2ae35
	h ^= h >> 16
	return h
}

func record(steps *[]Step, step Step) {
	if steps != nil {
		*steps = append(*steps, step)
	}
}

// HyperLogLog estimates how many different items it has seen, in a fixed array of small
// registers. Each item's hash picks a register with its first bits, and the rest of the hash
// gives a rank: one more than its run of leading zeros. A run of k zeros turns up about once
// in 2^k different items, so the largest rank each register has seen says roughly how many
// items reached it. Seeing an item again changes nothing.
type HyperLogLog struct {
	precision int
	registers []uint8
}

func NewHyperLogLog(precision int) (*HyperLogLog, error) {
	if precision < 4 || precision > 16 {
		return nil, errors.New("precision must be a whole number from 4 to 16")
	}
	return &HyperLogLog{precision, make([]uint8, 1<<precision)}, nil
}

// Add returns true when a register rose, which means the estimate may have changed.
func (s *HyperLogLog) Add(item string, steps *[]Step) bool {
	h := hash(item)
	index := int(h >> (32 - s.precision))
	rank := min(bits.LeadingZeros32(h<<s.precision), 32-s.precision) + 1
	before := int(s.registers[index])
	after := max(before, rank)
	s.registers[index] = uint8(after)
	kind := "keep"
	if after > before {
		kind = "raise"
	}
	record(steps, Step{Kind: kind, Index: index, Rank: rank, Before: before, After: after})
	return after > before
}

// Merge takes the larger register everywhere, which gives exactly the sketch of both sets
// together: a union, without knowing a single item. It returns how many registers rose.
func (s *HyperLogLog) Merge(other *HyperLogLog, steps *[]Step) (int, error) {
	if other.precision != s.precision {
		return 0, errors.New("only sketches with the same precision can merge")
	}
	raised := 0
	for index, value := range other.registers {
		before := s.registers[index]
		if value <= before {
			continue
		}
		s.registers[index] = value
		record(steps, Step{Kind: "merge", Index: index, Before: int(before), After: int(value)})
		raised++
	}
	return raised, nil
}

// Count estimates the number of different items, with a standard error of about 1.04 ÷
// √registers.
func (s *HyperLogLog) Count() int {
	m := float64(len(s.registers))
	sum, zeros := 0.0, 0
	for _, register := range s.registers {
		sum += 1 / float64(uint64(1)<<register)
		if register == 0 {
			zeros++
		}
	}
	var alpha float64
	switch len(s.registers) {
	case 16:
		alpha = 0.673
	case 32:
		alpha = 0.697
	case 64:
		alpha = 0.709
	default:
		alpha = 0.7213 / (1 + 1.079/m)
	}
	estimate := alpha * m * m / sum
	two32 := float64(uint64(1) << 32)
	if estimate <= 2.5*m && zeros > 0 {
		// Few items leave empty registers, and counting those is more accurate than the harmonic mean.
		estimate = m * math.Log(m/float64(zeros))
	} else if estimate > two32/30 {
		// Near 2^32, different items start sharing whole 32-bit hashes; correct for that.
		estimate = -two32 * math.Log(1-min(estimate, two32-1)/two32)
	}
	return int(math.Floor(estimate + 0.5))
}

func (s *HyperLogLog) Registers() []int {
	out := make([]int, len(s.registers))
	for i, r := range s.registers {
		out[i] = int(r)
	}
	return out
}

func (s *HyperLogLog) Precision() int { return s.precision }