PS2 · Multi-Startup Set

多起点集合：抽象数据类型

IntervalSet 的两种 rep 实现、泛型 MultiIntervalSet、similarity 函数——深入抽象数据类型、AF/RI 与表示暴露防护。

基本信息

PS2ADTAF/RIbigint泛型

官方讲义：web.mit.edu/6.102/ps2 ↗

作业要求

为 IntervalSet<string> 设计合法客户测试套件
用要求的两 map 表示实现 RepMapIntervalSet
泛化为按 === 比较的任意标签
用要求的并行数组表示实现 RepArrayIntervalSet
在 makeIntervalSet 中选择一种实现
测试/实现 MultiIntervalSet，其 rep 必须使用 IntervalSet
测试/规格化/实现 similarity，包括自行设计的 helper ADT

对每个实现类，显式记录 AF、RI、checkRep，以及表示暴露安全性。

规格说明

Interval

不可变半开区间 [start, end)，end > start，只读 bigint 端点。

IntervalSet<Label>

可变映射：唯一标签 → 不重叠的半开区间。标签按 === 比较，不得为 null、undefined 或 NaN。

interface IntervalSet<Label> {
  add(start: bigint, end: bigint, label: Label): void;
  interval(label: Label): Interval | undefined;
  labels(): Set<Label>;
}

add 在已存在相同标签区间时幂等。同一标签映射到不同区间，或不同标签占用重叠区间时抛出 IntervalConflictError。相邻合法（半开区间）。

MultiIntervalSet<Label>

一个标签可拥有多个区间，但全局不允许重叠。rep 必须以 IntervalSet 为构建块。

add(start,end,label): void
clear(): boolean
intervals(label): IntervalSet<number>
labels(): Set<Label>

similarity

type LabelSimilarity = [string,string,number];
similarity(defs, setA, setB): number

客户为选定的字符串标签对提供 [0,1] 对称相似度。未列出的相同标签相似度为 1；未列出的不同标签为 0。对两个非空多区间集合，在每个区间边界处划分整体跨度，累加每个子跨度长度 × 覆盖它的标签对的相似度，再除以总跨度。两个空集合的相似度为 0。

完成清单

IntervalSet 分区/测试
map 表示 + AF/RI/checkRep
泛型标签测试
array 表示 + AF/RI/checkRep
makeIntervalSet
MultiIntervalSet
similarity 测试
helper ADT
similarity

源码骨架

interval.ts — 不可变区间

export class Interval {
  public constructor(public readonly start: bigint, public readonly end: bigint) {
    if (end <= start) throw new Error('end must be greater than start');
  }
  public toString(): string { return `[${this.start},${this.end})`; }
}

intervalset.ts — 接口与工厂

import { Interval } from './interval.js';

export class IntervalConflictError extends Error {}
export interface IntervalSet<Label> {
  add(start: bigint, end: bigint, label: Label): void;
  interval(label: Label): Interval | undefined;
  labels(): Set<Label>;
}

export function makeIntervalSet<Label>(): IntervalSet<Label> {
  throw new Error('TODO: select one completed IntervalSet implementation');
}

intervalset-impls.ts — 两种 rep 实现

const todo = (name:string): never => { throw new Error(`TODO: ${name}`); };

export class RepMapIntervalSet<Label> implements IntervalSet<Label> {
  private readonly startMap: Map<Label, bigint> = new Map();
  private readonly endMap: Map<bigint, bigint> = new Map();
  private checkRep(): void { /* TODO */ }
  public add(start: bigint, end: bigint, label: Label): void { todo('RepMapIntervalSet.add'); }
  public interval(label: Label): Interval | undefined { return todo('RepMapIntervalSet.interval'); }
  public labels(): Set<Label> { return todo('RepMapIntervalSet.labels'); }
}

export class RepArrayIntervalSet<Label> implements IntervalSet<Label> {
  private readonly labelList: Array<Label> = [];
  private readonly valueList: Array<bigint> = [];
  // ... 同上，需决定 valueList 如何编码区间端点
}

export function implementationsForTesting() { return [RepMapIntervalSet, RepArrayIntervalSet]; }

multiintervalset.ts — 多区间集合

const todo = (name:string): never => { throw new Error(`TODO: ${name}`); };

export class MultiIntervalSet<Label> {
  // TODO: 官方作业要求 IntervalSet 出现在此 rep 中
  public constructor(initial?: IntervalSet<Label>) { void initial; }
  public add(start:bigint,end:bigint,label:Label):void { todo('MultiIntervalSet.add'); }
  public clear():boolean { return todo('MultiIntervalSet.clear'); }
  public intervals(label:Label):IntervalSet<number> { return todo('MultiIntervalSet.intervals'); }
  public labels():Set<Label> { return todo('MultiIntervalSet.labels'); }
}

similarity.ts — 相似度与 helper ADT

export type LabelSimilarity = [string,string,number];
export function similarity(similarities:LabelSimilarity[], setA:MultiIntervalSet<string>, setB:MultiIntervalSet<string>):number {
  throw new Error('TODO: design helper ADT, test, then implement similarity');
}
// TODO: PS2 explicitly requires you to design one helper ADT here before implementing similarity.