Alias method.

export type AliasErrorCode =
	| 'empty-table'
	| 'too-big'
	| 'bad-id'
	| 'duplicate-id'
	| 'bad-weight'
	| 'zero-total'
	| 'bad-draw-count'
	| 'bad-seed'
	| 'bad-bound';

export class AliasError extends Error {
	readonly code: AliasErrorCode;

	constructor(code: AliasErrorCode, message: string) {
		super(message);
		this.name = 'AliasError';
		this.code = code;
	}
}

export interface LootWeight {
	id: string;
	weight: number;
}

export interface AliasEntry {
	probability: number;
	alias: number;
}

export interface AliasTable {
	items: LootWeight[];
	totalWeight: number;
	entries: AliasEntry[];
}

function validate(weights: LootWeight[]): number {
	if (weights.length === 0)
		throw new AliasError('empty-table', 'Alias table needs at least one outcome.');
	if (weights.length > MAX_OUTCOMES) {
		throw new AliasError('too-big', `Alias table is limited to ${MAX_OUTCOMES} outcomes.`);
	}
	const seen = new Set<string>();
	let total = 0;
	for (const item of weights) {
		if (item.id.length > MAX_ID_LENGTH || !ID.test(item.id)) {
			throw new AliasError('bad-id', 'Outcome ids must be lowercase slugs.');
		}
		if (seen.has(item.id)) throw new AliasError('duplicate-id', 'Outcome ids must be unique.');
		seen.add(item.id);
		if (!Number.isInteger(item.weight) || item.weight < 0 || item.weight > MAX_WEIGHT) {
			throw new AliasError('bad-weight', `Weights must be whole numbers from 0 to ${MAX_WEIGHT}.`);
		}
		total += item.weight;
	}
	if (total <= 0)
		throw new AliasError('zero-total', 'At least one outcome must have a positive weight.');
	return total;
}

/** One pairing: a short column keeps its own height and borrows the rest from a tall one. */
export interface AliasStep {
	small: number;
	large: number;
	threshold: number;
	borrowed: number;
	largeBefore: number;
	largeAfter: number;
	largeBecomes: 'small' | 'large';
}

export interface AliasTrace {
	scaled: number[];
	small: number[];
	large: number[];
	steps: AliasStep[];
}

export function traceAliasTable(weights: LootWeight[]): { table: AliasTable; trace: AliasTrace } {
	const totalWeight = validate(weights);
	const items = weights.map((item) => ({ ...item }));
	const scaled = items.map((item) => item.weight * items.length);
	const small: number[] = [];
	const large: number[] = [];
	for (const [index, value] of scaled.entries()) (value < totalWeight ? small : large).push(index);
	const trace: AliasTrace = {
		scaled: [...scaled],
		small: [...small],
		large: [...large],
		steps: []
	};
	const entries = items.map(() => ({ probability: totalWeight, alias: -1 }));
	while (small.length > 0 && large.length > 0) {
		const smallIndex = small.pop()!;
		const largeIndex = large.pop()!;
		const borrowed = totalWeight - scaled[smallIndex];
		entries[smallIndex] = { probability: scaled[smallIndex], alias: largeIndex };
		const largeBefore = scaled[largeIndex];
		scaled[largeIndex] -= borrowed;
		const largeBecomes = scaled[largeIndex] < totalWeight ? 'small' : 'large';
		(largeBecomes === 'small' ? small : large).push(largeIndex);
		trace.steps.push({
			small: smallIndex,
			large: largeIndex,
			threshold: scaled[smallIndex],
			borrowed,
			largeBefore,
			largeAfter: scaled[largeIndex],
			largeBecomes
		});
	}
	// Anything left in either list is already exactly one column tall.
	return { table: { items, totalWeight, entries }, trace };
}

export function buildAliasTable(weights: LootWeight[]): AliasTable {
	return traceAliasTable(weights).table;
}

type LootWeight struct {
	ID     string
	Weight int
}

type AliasEntry struct {
	Probability int
	Alias       int
}

type AliasTable struct {
	Items       []LootWeight
	TotalWeight int
	Entries     []AliasEntry
}

type AliasError struct {
	Code    string
	Message string
}

func (e *AliasError) Error() string { return e.Message }

func validate(weights []LootWeight) (int, error) {
	if len(weights) == 0 {
		return 0, &AliasError{Code: "empty-table", Message: "Alias table needs at least one outcome."}
	}
	if len(weights) > 32 {
		return 0, &AliasError{Code: "too-big", Message: "Alias table is limited to 32 outcomes."}
	}
	seen := map[string]bool{}
	total := 0
	for _, item := range weights {
		if len(item.ID) == 0 || len(item.ID) > 24 || item.ID[0] < 'a' || item.ID[0] > 'z' {
			return 0, &AliasError{Code: "bad-id", Message: "Outcome ids must be lowercase slugs."}
		}
		for _, character := range item.ID[1:] {
			if !((character >= 'a' && character <= 'z') || (character >= '0' && character <= '9') || character == '-') {
				return 0, &AliasError{Code: "bad-id", Message: "Outcome ids must be lowercase slugs."}
			}
		}
		if seen[item.ID] {
			return 0, &AliasError{Code: "duplicate-id", Message: "Outcome ids must be unique."}
		}
		seen[item.ID] = true
		if item.Weight < 0 || item.Weight > 1_000_000 {
			return 0, &AliasError{Code: "bad-weight", Message: "Weights must be whole numbers from 0 to 1000000."}
		}
		total += item.Weight
	}
	if total <= 0 {
		return 0, &AliasError{Code: "zero-total", Message: "At least one outcome must have a positive weight."}
	}
	return total, nil
}

// AliasStep is one pairing: a short column keeps its own height and borrows the rest from a tall one.
type AliasStep struct {
	Small        int
	Large        int
	Threshold    int
	Borrowed     int
	LargeBefore  int
	LargeAfter   int
	LargeBecomes string
}

type AliasTrace struct {
	Scaled []int
	Small  []int
	Large  []int
	Steps  []AliasStep
}

func traceAliasTable(weights []LootWeight) (AliasTable, AliasTrace, error) {
	total, err := validate(weights)
	if err != nil {
		return AliasTable{}, AliasTrace{}, err
	}
	items := append([]LootWeight(nil), weights...)
	scaled := make([]int, len(items))
	small, large := []int{}, []int{}
	for index, item := range items {
		scaled[index] = item.Weight * len(items)
		if scaled[index] < total {
			small = append(small, index)
		} else {
			large = append(large, index)
		}
	}
	trace := AliasTrace{
		Scaled: append([]int(nil), scaled...),
		Small:  append([]int{}, small...),
		Large:  append([]int{}, large...),
		Steps:  []AliasStep{},
	}
	entries := make([]AliasEntry, len(items))
	for index := range entries {
		entries[index] = AliasEntry{Probability: total, Alias: -1}
	}
	for len(small) > 0 && len(large) > 0 {
		smallIndex := small[len(small)-1]
		small = small[:len(small)-1]
		largeIndex := large[len(large)-1]
		large = large[:len(large)-1]
		borrowed := total - scaled[smallIndex]
		entries[smallIndex] = AliasEntry{Probability: scaled[smallIndex], Alias: largeIndex}
		largeBefore := scaled[largeIndex]
		scaled[largeIndex] -= borrowed
		largeBecomes := "large"
		if scaled[largeIndex] < total {
			largeBecomes = "small"
			small = append(small, largeIndex)
		} else {
			large = append(large, largeIndex)
		}
		trace.Steps = append(trace.Steps, AliasStep{
			Small:        smallIndex,
			Large:        largeIndex,
			Threshold:    scaled[smallIndex],
			Borrowed:     borrowed,
			LargeBefore:  largeBefore,
			LargeAfter:   scaled[largeIndex],
			LargeBecomes: largeBecomes,
		})
	}
	// Anything left in either list is already exactly one column tall.
	return AliasTable{Items: items, TotalWeight: total, Entries: entries}, trace, nil
}

func buildAliasTable(weights []LootWeight) (AliasTable, error) {
	table, _, err := traceAliasTable(weights)
	return table, err
}