Project

/// 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.
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)
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.
    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.
    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.
    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.
    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.
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
    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.
fn slack(policy: Policy, request: Request) i64 {
    // Calculate absolute deadline from submission time + SLA window
    const deadline = request.submitted_at_ms + request.sla_ms;
    
    // Compute slack as deadline - now; use i128 to prevent overflow on subtraction
    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
        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
    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).
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
    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
    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
    try simulateScenario(
        allocator,
        .{ .now_ms = 520, .vip_boost = 100, .overdue_multiplier = 4 },
        "Escalation window"
    );
}

// Import the Zig standard library for allocator, sorting, debugging, etc.
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.
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.
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.
    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.
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.
    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.
        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).
        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.
        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.
        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.
        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).
                _ = self.heap.remove();
            }
        }

        // Add multiple values from a slice into the tracker.
        // This simply forwards each element to `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.
        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.
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.
    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.
    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 },
        );
    }
}