PageRank.

export const MAX_PAGES = 64;
export const MAX_LINKS = 256;
export const MAX_ITERATIONS = 100;

export type Link = { from: string; to: string };
export type Wiki = { pages: string[]; links: Link[] };
export type RankOptions = { damping?: number; tolerance?: number; maxIterations?: number };
export type RankSnapshot = {
	iteration: number;
	scores: Record<string, number>;
	delta: number;
	dangling: number;
};
export type PageScore = { page: string; score: number };
export type RankResult = {
	scores: Record<string, number>;
	ordered: PageScore[];
	iterations: number;
	converged: boolean;
	trace: RankSnapshot[];
};

export type RankErrorCode =
	'too-big' | 'bad-page' | 'unknown-page' | 'duplicate-link' | 'bad-options';

export class RankError extends Error {
	readonly code: RankErrorCode;
	constructor(code: RankErrorCode, message: string) {
		super(message);
		this.name = 'RankError';
		this.code = code;
	}
}

function validate(wiki: Wiki, options: Required<RankOptions>): void {
	if (wiki.pages.length > MAX_PAGES || wiki.links.length > MAX_LINKS)
		throw new RankError('too-big', `up to ${MAX_PAGES} pages and ${MAX_LINKS} links`);
	const known = new Set<string>();
	for (const page of wiki.pages) {
		if (!/^[a-z][a-z0-9-]{0,23}$/.test(page) || known.has(page))
			throw new RankError('bad-page', `page ids are unique lowercase slugs: ${page}`);
		known.add(page);
	}
	const links = new Set<string>();
	for (const link of wiki.links) {
		if (!known.has(link.from) || !known.has(link.to))
			throw new RankError(
				'unknown-page',
				`a link names a page that does not exist: ${link.from}, ${link.to}`
			);
		const key = `${link.from}\0${link.to}`;
		if (links.has(key))
			throw new RankError('duplicate-link', `link appears twice: ${link.from} -> ${link.to}`);
		links.add(key);
	}
	if (
		!Number.isFinite(options.damping) ||
		options.damping <= 0 ||
		options.damping >= 1 ||
		!Number.isFinite(options.tolerance) ||
		options.tolerance <= 0 ||
		!Number.isInteger(options.maxIterations) ||
		options.maxIterations < 1 ||
		options.maxIterations > MAX_ITERATIONS
	)
		throw new RankError(
			'bad-options',
			`damping is between 0 and 1, tolerance is positive, and maxIterations is 1 to ${MAX_ITERATIONS}`
		);
}

function optionsOf(options: RankOptions = {}): Required<RankOptions> {
	return {
		damping: options.damping ?? 0.85,
		tolerance: options.tolerance ?? 1e-8,
		maxIterations: options.maxIterations ?? MAX_ITERATIONS
	};
}

function ordered(scores: Map<string, number>): PageScore[] {
	return [...scores.entries()]
		.map(([page, score]) => ({ page, score }))
		.sort((a, b) => b.score - a.score || a.page.localeCompare(b.page));
}

// Each iteration redistributes linked rank, spreads dangling rank, and adds teleportation.
export function traceRank(wiki: Wiki, options: RankOptions = {}): RankSnapshot[] {
	const resolved = optionsOf(options);
	validate(wiki, resolved);
	if (wiki.pages.length === 0) return [];
	const count = wiki.pages.length;
	const outgoing = new Map<string, string[]>(wiki.pages.map((page) => [page, []]));
	for (const link of wiki.links) outgoing.get(link.from)!.push(link.to);
	// Turn the links around once, so each page can gather its votes in O(indegree).
	const incoming = new Map<string, string[]>(wiki.pages.map((page) => [page, []]));
	for (const [from, destinations] of outgoing)
		for (const to of destinations) incoming.get(to)!.push(from);
	let scores = new Map(wiki.pages.map((page) => [page, 1 / count]));
	const trace: RankSnapshot[] = [];
	for (let iteration = 1; iteration <= resolved.maxIterations; iteration++) {
		const dangling = [...scores]
			.filter(([page]) => outgoing.get(page)!.length === 0)
			.reduce((sum, [, score]) => sum + score, 0);
		const next = new Map<string, number>();
		for (const page of wiki.pages) {
			let linked = 0;
			for (const from of incoming.get(page)!)
				linked += scores.get(from)! / outgoing.get(from)!.length;
			next.set(
				page,
				(1 - resolved.damping) / count + resolved.damping * (linked + dangling / count)
			);
		}
		const delta = Math.max(
			...wiki.pages.map((page) => Math.abs(next.get(page)! - scores.get(page)!))
		);
		const snapshot = Object.fromEntries(wiki.pages.map((page) => [page, next.get(page)!]));
		trace.push({ iteration, scores: snapshot, delta, dangling });
		scores = next;
		if (delta < resolved.tolerance) break;
	}
	return trace;
}

export function rankPages(wiki: Wiki, options: RankOptions = {}): RankResult {
	const trace = traceRank(wiki, options);
	const resolved = optionsOf(options);
	validate(wiki, resolved);
	const scores =
		trace.at(-1)?.scores ??
		Object.fromEntries(wiki.pages.map((page) => [page, 1 / wiki.pages.length]));
	const scoreMap = new Map(Object.entries(scores));
	return {
		scores,
		ordered: ordered(scoreMap),
		iterations: trace.length,
		converged: trace.length > 0 && trace.at(-1)!.delta < resolved.tolerance,
		trace
	};
}

const (
	MaxPages      = 64
	MaxLinks      = 256
	MaxIterations = 100
)

type Link struct {
	From string
	To   string
}

type Wiki struct {
	Pages []string
	Links []Link
}

type RankOptions struct {
	Damping       float64
	Tolerance     float64
	MaxIterations int
}

type RankSnapshot struct {
	Iteration int
	Scores    map[string]float64
	Delta     float64
	Dangling  float64
}

type PageScore struct {
	Page  string
	Score float64
}

type RankResult struct {
	Scores     map[string]float64
	Ordered    []PageScore
	Iterations int
	Converged  bool
	Trace      []RankSnapshot
}

type RankError struct {
	Code    string
	Message string
}

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

var pagePattern = regexp.MustCompile(`^[a-z][a-z0-9-]{0,23}$`)

func validate(wiki Wiki, options RankOptions) error {
	if len(wiki.Pages) > MaxPages || len(wiki.Links) > MaxLinks {
		return &RankError{"too-big", fmt.Sprintf("up to %d pages and %d links", MaxPages, MaxLinks)}
	}
	known := map[string]bool{}
	for _, page := range wiki.Pages {
		if !pagePattern.MatchString(page) || known[page] {
			return &RankError{"bad-page", "page ids are unique lowercase slugs: " + page}
		}
		known[page] = true
	}
	links := map[string]bool{}
	for _, link := range wiki.Links {
		if !known[link.From] || !known[link.To] {
			return &RankError{"unknown-page", fmt.Sprintf("a link names a page that does not exist: %s, %s", link.From, link.To)}
		}
		key := link.From + "\x00" + link.To
		if links[key] {
			return &RankError{"duplicate-link", fmt.Sprintf("link appears twice: %s -> %s", link.From, link.To)}
		}
		links[key] = true
	}
	if math.IsNaN(options.Damping) || math.IsInf(options.Damping, 0) ||
		options.Damping <= 0 || options.Damping >= 1 ||
		math.IsNaN(options.Tolerance) || math.IsInf(options.Tolerance, 0) || options.Tolerance <= 0 ||
		options.MaxIterations < 1 || options.MaxIterations > MaxIterations {
		return &RankError{"bad-options", fmt.Sprintf("damping is between 0 and 1, tolerance is positive, and maxIterations is 1 to %d", MaxIterations)}
	}
	return nil
}

// DefaultRankOptions is the TypeScript default: damping 0.85, tolerance 1e-8, 100 iterations.
// A zero field is refused, as in TypeScript, rather than quietly replaced by a default.
func DefaultRankOptions() RankOptions {
	return RankOptions{Damping: 0.85, Tolerance: 1e-8, MaxIterations: MaxIterations}
}

func ordered(scores map[string]float64) []PageScore {
	result := []PageScore{}
	for page, score := range scores {
		result = append(result, PageScore{page, score})
	}
	sort.Slice(result, func(i, j int) bool {
		if result[i].Score == result[j].Score {
			return result[i].Page < result[j].Page
		}
		return result[i].Score > result[j].Score
	})
	return result
}

// Each iteration redistributes linked rank, spreads dangling rank, and adds teleportation.
func TraceRank(wiki Wiki, options RankOptions) ([]RankSnapshot, error) {
	if err := validate(wiki, options); err != nil {
		return nil, err
	}
	if len(wiki.Pages) == 0 {
		return []RankSnapshot{}, nil
	}
	outgoing := map[string][]string{}
	for _, page := range wiki.Pages {
		outgoing[page] = []string{}
	}
	for _, link := range wiki.Links {
		outgoing[link.From] = append(outgoing[link.From], link.To)
	}
	// Turn the links around once, so each page can gather its votes in O(indegree).
	incoming := map[string][]string{}
	for _, from := range wiki.Pages {
		for _, to := range outgoing[from] {
			incoming[to] = append(incoming[to], from)
		}
	}
	count := float64(len(wiki.Pages))
	scores := map[string]float64{}
	for _, page := range wiki.Pages {
		scores[page] = 1 / count
	}
	trace := []RankSnapshot{}
	for iteration := 1; iteration <= options.MaxIterations; iteration++ {
		dangling := 0.0
		for _, page := range wiki.Pages {
			if len(outgoing[page]) == 0 {
				dangling += scores[page]
			}
		}
		next := map[string]float64{}
		for _, page := range wiki.Pages {
			linked := 0.0
			for _, from := range incoming[page] {
				linked += scores[from] / float64(len(outgoing[from]))
			}
			next[page] = (1-options.Damping)/count + options.Damping*(linked+dangling/count)
		}
		delta := 0.0
		for _, page := range wiki.Pages {
			if difference := math.Abs(next[page] - scores[page]); difference > delta {
				delta = difference
			}
		}
		snapshot := map[string]float64{}
		for _, page := range wiki.Pages {
			snapshot[page] = next[page]
		}
		trace = append(trace, RankSnapshot{iteration, snapshot, delta, dangling})
		scores = next
		if delta < options.Tolerance {
			break
		}
	}
	return trace, nil
}

func RankPages(wiki Wiki, options RankOptions) (RankResult, error) {
	trace, err := TraceRank(wiki, options)
	if err != nil {
		return RankResult{}, err
	}
	scores := map[string]float64{}
	if len(trace) > 0 {
		for page, score := range trace[len(trace)-1].Scores {
			scores[page] = score
		}
	} else if len(wiki.Pages) > 0 {
		for _, page := range wiki.Pages {
			scores[page] = 1 / float64(len(wiki.Pages))
		}
	}
	return RankResult{scores, ordered(scores), len(trace), len(trace) > 0 && trace[len(trace)-1].Delta < options.Tolerance, trace}, nil
}