Function upperBound [src]

Returns the index of the first element in items that is greater than context, as determined by compareFn. If no such element exists, returns items.len. items must be sorted in ascending order with respect to compareFn: [0] [len] ┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐ │.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│ └───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘ ├─────────────────┼─────────────────┼─────────────────┤ ↳ zero or more ↳ zero or more ↳ zero or more ├───┤ ↳ returned index O(log n) time complexity. See also: binarySearch, lowerBound, partitionPoint, equalRange.

Prototype

 pub fn upperBound( comptime T: type, items: []const T, context: anytype, comptime compareFn: fn (@TypeOf(context), T) std.math.Order, ) usize

Parameters

T: typeitems: []const TcompareFn: fn (@TypeOf(context), T) std.math.Order

Example

 test upperBound {
    const S = struct {
        fn compareU32(context: u32, item: u32) std.math.Order {
            return std.math.order(context, item);
        }
        fn compareI32(context: i32, item: i32) std.math.Order {
            return std.math.order(context, item);
        }
        fn compareF32(context: f32, item: f32) std.math.Order {
            return std.math.order(context, item);
        }
    };
    const R = struct {
        val: i32,

        fn r(val: i32) @This() {
            return .{ .val = val };
        }

        fn compareFn(context: i32, item: @This()) std.math.Order {
            return std.math.order(context, item.val);
        }
    };

    try std.testing.expectEqual(0, upperBound(u32, &[_]u32{}, @as(u32, 0), S.compareU32));
    try std.testing.expectEqual(0, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 0), S.compareU32));
    try std.testing.expectEqual(1, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 2), S.compareU32));
    try std.testing.expectEqual(2, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 5), S.compareU32));
    try std.testing.expectEqual(6, upperBound(u32, &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, @as(u32, 8), S.compareU32));
    try std.testing.expectEqual(6, upperBound(u32, &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, @as(u32, 8), S.compareU32));
    try std.testing.expectEqual(3, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 8), S.compareU32));
    try std.testing.expectEqual(6, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 64), S.compareU32));
    try std.testing.expectEqual(6, upperBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 100), S.compareU32));
    try std.testing.expectEqual(2, upperBound(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 5), S.compareI32));
    try std.testing.expectEqual(1, upperBound(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, @as(f32, -33.4), S.compareF32));
    try std.testing.expectEqual(2, upperBound(R, &[_]R{ R.r(-100), R.r(-40), R.r(-10), R.r(30) }, @as(i32, -20), R.compareFn));
}

Source

  pub fn upperBound(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) usize {
    const S = struct {
        fn predicate(ctx: @TypeOf(context), item: T) bool {
            return compareFn(ctx, item).invert() != .gt;
        }
    };
    return partitionPoint(T, items, context, S.predicate);
}  