项目

/// Demo: Using std.PriorityQueue to dispatch tasks by priority.
/// Lower urgency values mean higher priority; ties are broken by earlier submission time.
/// This example prints the order in which tasks would be processed.
///
/// Notes:
/// - The comparator returns `.lt` when `a` should be dispatched before `b`.
/// - We also order by `submitted_at_ms` to ensure deterministic order among equal urgencies.
/// 演示：使用 std.PriorityQueue 按优先级分发任务。
/// 紧急程度值越低意味着优先级越高；平局时以较早提交时间打破。
/// 此示例打印任务将被处理的顺序。
///
/// 注意：
/// - 当 `a` 应该在 `b` 之前分发时，比较器返回 `.lt`。
/// - 我们还按 `submitted_at_ms` 排序，以确保在同等紧急程度下的确定性顺序。
const std = @import("std");
const Order = std.math.Order;

/// A single work item to schedule.
/// 要调度的单个工作项。
const Task = struct {
    /// Display name for the task.
    /// 任务的显示名称。
    name: []const u8,
    /// Priority indicator: lower value = more urgent.
    /// 优先级指示器：值越低越紧急。
    urgency: u8,
    /// Monotonic timestamp in milliseconds used to break ties (earlier wins).
    /// 用于打破平局的单调时间戳（毫秒），较早者胜出。
    submitted_at_ms: u64,
};

/// Comparator for the priority queue:
/// - Primary key: urgency (lower is dispatched first)
/// - Secondary key: submitted_at_ms (earlier is dispatched first)
/// 优先级队列的比较器：
/// - 主键：紧急程度（较低者先分发）
/// - 次要键：submitted_at_ms（较早者先分发）
fn taskOrder(_: void, a: Task, b: Task) Order {
    // Compare by urgency first.
    /// 首先按紧急程度比较。
    if (a.urgency < b.urgency) return .lt;
    if (a.urgency > b.urgency) return .gt;

    // Tie-breaker: earlier submission is higher priority.
    /// 平局打破器：较早提交者优先级更高。
    return std.math.order(a.submitted_at_ms, b.submitted_at_ms);
}

/// Program entry: builds a priority queue and prints dispatch order.
/// 程序入口：构建优先级队列并打印分发顺序。
pub fn main() !void {
    // Use the General Purpose Allocator (GPA) for simplicity in examples.
    /// 为了示例简便，使用通用分配器（GPA）。
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Instantiate a priority queue of Task:
    // - Context type is `void` (no extra state needed by the comparator)
    // - `taskOrder` defines the ordering.
    /// 实例化一个任务优先级队列：
    /// - 上下文类型是 `void`（比较器不需要额外状态）
    /// - `taskOrder` 定义排序规则。
    var queue = std.PriorityQueue(Task, void, taskOrder).init(allocator, {});
    defer queue.deinit();

    // Enqueue tasks with varying urgency and submission times.
    // Expectation (by our ordering): lower urgency processed first;
    // within same urgency, earlier submitted_at_ms processed first.
    /// 将具有不同紧急程度和提交时间的任务入队。
    /// 期望（按我们的排序）：较低紧急程度优先处理；
    /// 在相同紧急程度内，submitted_at_ms 较早者优先处理。
    try queue.add(.{ .name = "compile pointer.zig", .urgency = 0, .submitted_at_ms = 1 });
    try queue.add(.{ .name = "run tests", .urgency = 1, .submitted_at_ms = 2 });
    try queue.add(.{ .name = "deploy preview", .urgency = 2, .submitted_at_ms = 3 });
    try queue.add(.{ .name = "prepare changelog", .urgency = 1, .submitted_at_ms = 4 });

    std.debug.print("Dispatch order:\n", .{});

    // Remove tasks in priority order until the queue is empty.
    // removeOrNull() yields the next Task or null when empty.
    /// 按优先级顺序移除任务直到队列为空。
    /// removeOrNull() 返回下一个任务或空时返回 null。
    while (queue.removeOrNull()) |task| {
        std.debug.print("  - {s} (urgency {d})\n", .{ task.name, task.urgency });
    }
}

const std = @import("std");
const Order = std.math.Order;

/// Represents an incoming support request with SLA constraints.
/// 表示带有 SLA 约束的传入支持请求。
const Request = struct {
    ticket: []const u8,
    submitted_at_ms: u64,
    sla_ms: u32,
    work_estimate_ms: u32,
    vip: bool,
};

/// Scheduling policy parameters that influence prioritization.
/// 影响优先级调度的策略参数。
const Policy = struct {
    now_ms: u64,             // Current time reference for slack calculation
    /// 用于计算宽松时间的当前时间参考点
    vip_boost: i64,          // Score reduction (boost) for VIP requests
    /// VIP 请求的分数减少（提升）
    overdue_multiplier: i64, // Penalty multiplier for overdue requests
    /// 超期请求的惩罚乘数
};

/// Computes the time slack for a request: positive means time remaining, negative means overdue.
/// Overdue requests are amplified by the policy's overdue_multiplier to increase urgency.
/// 计算请求的时间宽松度：正值表示剩余时间，负值表示已超期。
/// 超期请求会根据策略的 overdue_multiplier 进行放大以增加紧急程度。
fn slack(policy: Policy, request: Request) i64 {
    // Calculate absolute deadline from submission time + SLA window
    /// 从提交时间 + SLA 时间窗口计算绝对截止时间
    const deadline = request.submitted_at_ms + request.sla_ms;

    // Compute slack as deadline - now; use i128 to prevent overflow on subtraction
    /// 计算宽松度为 deadline - now；使用 i128 防止减法溢出
    const slack_signed = @as(i64, @intCast(@as(i128, deadline) - @as(i128, policy.now_ms)));

    if (slack_signed >= 0) {
        // Positive slack: request is still within SLA
        /// 正宽松度：请求仍在 SLA 内
        return slack_signed;
    }

    // Negative slack: request is overdue; amplify urgency by multiplying
    /// 负宽松度：请求已超期；通过乘法放大紧急程度
    return slack_signed * policy.overdue_multiplier;
}

/// Computes a weighted score for prioritization.
/// Lower scores = higher priority (processed first by min-heap).
/// 计算用于优先级的加权分数。
/// 分数越低 = 优先级越高（由最小堆优先处理）。
fn weightedScore(policy: Policy, request: Request) i64 {
    // Start with slack: negative (overdue) or positive (time remaining)
    /// 从宽松度开始：负值（已超期）或正值（剩余时间）
    var score = slack(policy, request);

    // Add work estimate: longer tasks get slightly lower priority (higher score)
    /// 添加工作估计：较长的任务获得稍低的优先级（更高分数）
    score += @as(i64, @intCast(request.work_estimate_ms));

    // VIP boost: reduce score to increase priority
    /// VIP 提升：减少分数以增加优先级
    if (request.vip) score -= policy.vip_boost;

    return score;
}

/// Comparison function for the priority queue.
/// Returns Order.lt if 'a' should be processed before 'b' (lower score = higher priority).
/// 优先级队列的比较函数。
/// 如果 'a' 应该在 'b' 之前处理，则返回 Order.lt（分数越低 = 优先级越高）。
fn requestOrder(policy: Policy, a: Request, b: Request) Order {
    const score_a = weightedScore(policy, a);
    const score_b = weightedScore(policy, b);
    return std.math.order(score_a, score_b);
}

/// Simulates a scheduling scenario by inserting all tasks into a priority queue,
/// then dequeuing and printing them in priority order.
/// 通过将所有任务插入优先级队列来模拟调度场景，
/// 然后按优先级顺序出队并打印。
fn simulateScenario(allocator: std.mem.Allocator, policy: Policy, label: []const u8) !void {
    // Define a set of incoming requests with varying SLA constraints and characteristics
    /// 定义一组具有不同 SLA 约束和特征的传入请求
    const tasks = [_]Request{
        .{ .ticket = "INC-482", .submitted_at_ms = 0, .sla_ms = 500, .work_estimate_ms = 120, .vip = false },
        .{ .ticket = "INC-993", .submitted_at_ms = 120, .sla_ms = 400, .work_estimate_ms = 60, .vip = true },
        .{ .ticket = "INC-511", .submitted_at_ms = 200, .sla_ms = 200, .work_estimate_ms = 45, .vip = false },
        .{ .ticket = "INC-742", .submitted_at_ms = 340, .sla_ms = 120, .work_estimate_ms = 30, .vip = false },
    };

    // Initialize priority queue with the given policy as context for comparison
    /// 使用给定策略作为比较上下文初始化优先级队列
    var queue = std.PriorityQueue(Request, Policy, requestOrder).init(allocator, policy);
    defer queue.deinit();

    // Add all tasks to the queue; they will be heap-ordered automatically
    /// 将所有任务添加到队列中；它们将自动按堆排序
    try queue.addSlice(&tasks);

    // Print scenario header
    /// 打印场景标题
    std.debug.print("{s} (now={d}ms)\n", .{ label, policy.now_ms });

    // Dequeue and print requests in priority order (lowest score first)
    /// 按优先级顺序出队并打印请求（分数最低的先出队）
    while (queue.removeOrNull()) |request| {
        // Recalculate score and deadline for display
        /// 重新计算分数和截止时间以供显示
        const score = weightedScore(policy, request);
        const deadline = request.submitted_at_ms + request.sla_ms;

        std.debug.print(
            "  -> {s} score={d} deadline={d} vip={}\n",
            .{ request.ticket, score, deadline, request.vip },
        );
    }
    std.debug.print("\n", .{});
}

pub fn main() !void {
    // Set up general-purpose allocator with leak detection
    /// 设置带有泄漏检测的通用分配器
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Scenario 1: Mid-shift with moderate VIP boost and overdue penalty
    /// 场景 1：班中时段，适度 VIP 提升和超期惩罚
    try simulateScenario(
        allocator,
        .{ .now_ms = 350, .vip_boost = 250, .overdue_multiplier = 2 },
        "Mid-shift triage"
    );

    // Scenario 2: Escalation window with reduced VIP boost but higher overdue penalty
    /// 场景 2：升级窗口，减弱 VIP 提升但更高超期惩罚
    try simulateScenario(
        allocator,
        .{ .now_ms = 520, .vip_boost = 100, .overdue_multiplier = 4 },
        "Escalation window"
    );
}

// Import the Zig standard library for allocator, sorting, debugging, etc.
/// 导入 Zig 标准库用于分配器、排序、调试等。
const std = @import("std");

const Order = std.math.Order;

// A single latency measurement for an endpoint.
// Fields:
//  - endpoint: UTF-8 byte slice identifying the endpoint.
//  - duration_ms: observed latency in milliseconds.
//  - payload_bytes: size of the request/response payload in bytes.
/// 端点的单个延迟测量。
/// 字段：
///  - endpoint：标识端点的 UTF-8 字节切片。
///  - duration_ms：以毫秒为单位的观察延迟。
///  - payload_bytes：请求/响应有效负载的大小（字节）。
const LatencySample = struct {
    endpoint: []const u8,
    duration_ms: u32,
    payload_bytes: u32,
};

// Compute a score for a latency sample.
// Higher scores represent more severe (worse) samples. The formula favors
// larger durations and applies a small penalty for larger payloads to reduce
// noisy high-latency large-payload samples.
//
// Returns an f64 so scores can be compared with fractional penalties.
/// 计算延迟样本的分数。
/// 更高的分数表示更严重（更差）的样本。公式偏向较大的持续时间，
/// 并对较大的有效负载应用小幅惩罚，以减少噪声高延迟大有效负载样本。
///
/// 返回 f64 以便分数可以与分数惩罚进行比较。
fn score(sample: LatencySample) f64 {
    // Convert integers to floating point explicitly to avoid implicit casts.
    // The penalty factor 0.005 was chosen empirically to be small.
    /// 显式将整数转换为浮点数以避免隐式转换。
    /// 惩罚因子 0.005 是凭经验选择的较小值。
    return @as(f64, @floatFromInt(sample.duration_ms)) - (@as(f64, @floatFromInt(sample.payload_bytes)) * 0.005);
}

// TopK is a compile-time generic producer that returns a fixed-capacity,
// score-driven top-K tracker for items of type T.
//
// Parameters:
//  - T: the element type stored in the tracker.
//  - scoreFn: a compile-time function that maps T -> f64 used to rank elements.
/// TopK 是一个编译时泛型生成器，返回一个固定容量的、
/// 基于分数的 T 类型项目顶级 K 跟踪器。
///
/// 参数：
///  - T：跟踪器中存储的元素类型。
///  - scoreFn：编译时函数，映射 T -> f64 用于排名元素。
fn TopK(comptime T: type, comptime scoreFn: fn (T) f64) type {
    const Error = error{InvalidLimit};

    // Comparator helpers used by the PriorityQueue and for sorting snapshots.
    /// PriorityQueue 和排序快照使用的比较器辅助函数。
    const Comparators = struct {
        // Comparator used by the PriorityQueue. The first parameter is the
        // user-provided context (unused here), hence the underscore name.
        // Returns an Order (Less/Equal/Greater) based on the score function.
        /// PriorityQueue 使用的比较器。第一个参数是用户提供的上下文（此处未使用），
        /// 因此使用下划线名称。基于分数函数返回 Order（Less/Equal/Greater）。
        fn heap(_: void, a: T, b: T) Order {
            return std.math.order(scoreFn(a), scoreFn(b));
        }

        // Boolean comparator used by the heap sort to produce descending order.
        // Returns true when `a` should come before `b` (i.e., a has higher score).
        /// 堆排序使用的布尔比较器以产生降序。
        /// 当 `a` 应该在 `b` 之前时返回 true（即 a 有更高的分数）。
        fn desc(_: void, a: T, b: T) bool {
            return scoreFn(a) > scoreFn(b);
        }
    };

    return struct {
        // A priority queue specialized for T using our heap comparator.
        /// 使用我们的堆比较器为 T 专门化的优先级队列。
        const Heap = std.PriorityQueue(T, void, Comparators.heap);
        const Self = @This();

        heap: Heap,
        limit: usize,

        // Initialize a TopK tracker with the provided allocator and positive limit.
        // Returns Error.InvalidLimit when limit == 0.
        /// 使用提供的分配器和正限制初始化 TopK 跟踪器。
        /// 当 limit == 0 时返回 Error.InvalidLimit。
        pub fn init(allocator: std.mem.Allocator, limit: usize) Error!Self {
            if (limit == 0) return Error.InvalidLimit;
            return .{ .heap = Heap.init(allocator, {}), .limit = limit };
        }

        // Deinitialize the underlying heap and free its resources.
        /// 释放底层堆并释放其资源。
        pub fn deinit(self: *Self) void {
            self.heap.deinit();
        }

        // Add a single value into the tracker. If adding causes the internal
        // count to exceed `limit`, the priority queue will evict the item it
        // considers lowest priority according to our comparator, keeping the
        // top-K scored items.
        /// 将单个值添加到跟踪器中。如果添加导致内部计数超过 `limit`，
        /// 优先级队列将根据我们的比较器逐出它认为优先级最低的项目，
        /// 保持顶级 K 分数项目。
        pub fn add(self: *Self, value: T) !void {
            try self.heap.add(value);
            if (self.heap.count() > self.limit) {
                // Evict the lowest-priority element (as defined by Comparators.heap).
                /// 逐出最低优先级元素（如 Comparators.heap 所定义）。
                _ = self.heap.remove();
            }
        }

        // Add multiple values from a slice into the tracker.
        // This simply forwards each element to `add`.
        /// 从切片将多个值添加到跟踪器中。
        /// 这只是将每个元素转发给 `add`。
        pub fn addSlice(self: *Self, values: []const T) !void {
            for (values) |value| try self.add(value);
        }

        // Produce a snapshot of the current tracked items in descending score order.
        //
        // The snapshot allocates a new array via `allocator` and copies the
        // internal heap's item storage into it. The result is then sorted
        // descending (highest score first) using Comparators.desc.
        //
        // Caller is responsible for freeing the returned slice.
        /// 按降序分数顺序生成当前跟踪项目的快照。
        ///
        /// 快照通过 `allocator` 分配一个新数组，并将内部堆的项目存储复制到其中。
        /// 然后使用 Comparators.desc 按降序（最高分数优先）排序结果。
        ///
        /// 调用者负责释放返回的切片。
        pub fn snapshotDescending(self: *Self, allocator: std.mem.Allocator) ![]T {
            const count = self.heap.count();
            const out = try allocator.alloc(T, count);
            // Copy the underlying items buffer into the newly allocated array.
            // This creates an independent snapshot so we can sort without mutating the heap.
            /// 将底层项目缓冲区复制到新分配的数组中。
            /// 这创建了一个独立的快照，因此我们可以在不改变堆的情况下排序。
            @memcpy(out, self.heap.items[0..count]);
            // Sort in-place so the highest-scored items appear first.
            /// 原地排序，以便最高分项目出现在前面。
            std.sort.heap(T, out, @as(void, {}), Comparators.desc);
            return out;
        }
    };
}

// Example program demonstrating TopK usage with LatencySample.
/// 演示 TopK 与 LatencySample 使用的示例程序。
pub fn main() !void {
    // Create a general-purpose allocator for example allocations.
    /// 为示例分配创建通用分配器。
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // Track the top 5 latency samples by computed score.
    /// 按计算分数跟踪前 5 个延迟样本。
    var tracker = try TopK(LatencySample, score).init(allocator, 5);
    defer tracker.deinit();

    // Example samples. These are small, stack-allocated literal records.
    /// 示例样本。这些是小的、栈分配的字面记录。
    const samples = [_]LatencySample{
        .{ .endpoint = "/v1/users", .duration_ms = 122, .payload_bytes = 850 },
        .{ .endpoint = "/v1/orders", .duration_ms = 210, .payload_bytes = 1200 },
        .{ .endpoint = "/v1/users", .duration_ms = 188, .payload_bytes = 640 },
        .{ .endpoint = "/v1/payments", .duration_ms = 305, .payload_bytes = 1500 },
        .{ .endpoint = "/v1/orders", .duration_ms = 154, .payload_bytes = 700 },
        .{ .endpoint = "/v1/ledger", .duration_ms = 420, .payload_bytes = 540 },
        .{ .endpoint = "/v1/users", .duration_ms = 275, .payload_bytes = 980 },
        .{ .endpoint = "/v1/health", .duration_ms = 34, .payload_bytes = 64 },
        .{ .endpoint = "/v1/ledger", .duration_ms = 362, .payload_bytes = 480 },
    };

    // Bulk-add the sample slice into the tracker.
    /// 批量将样本切片添加到跟踪器中。
    try tracker.addSlice(&samples);

    // Capture the current top-K samples in descending order and print them.
    /// 按降序捕获当前前 K 个样本并打印它们。
    const worst = try tracker.snapshotDescending(allocator);
    defer allocator.free(worst);

    std.debug.print("Top latency offenders (descending by score):\n", .{});
    for (worst, 0..) |sample, idx| {
        // Compute the score again for display purposes (identical to the ordering key).
        /// 出于显示目的重新计算分数（与排序键相同）。
        const computed_score = score(sample);
        std.debug.print(
            "  {d:>2}. {s: <12} latency={d}ms payload={d}B score={d:.2}\n",
            .{ idx + 1, sample.endpoint, sample.duration_ms, sample.payload_bytes, computed_score },
        );
    }
}