Zig 0.17.0-dev (Split by item)

This is an example of documentation generated by ZigDoc, an alternative to Zig's built-in Auto Doc feature. See also examples in other modes/formats. The project being documented here (as the example) is the Zig library itself.

partitionPoint

Returns the index of the partition point of items in relation to the given predicate.

If all elements of items satisfy the predicate the returned value is items.len.

items must contain a prefix for which all elements satisfy the predicate, and beyond which none of the elements satisfy the predicate:

[0]                                          [len]
┌────┬────┬─/ /─┬────┬─────┬─────┬─/ /─┬─────┐
│true│true│ \ \ │true│false│false│ \ \ │false│
└────┴────┴─/ /─┴────┴─────┴─────┴─/ /─┴─────┘
├────────────────────┼───────────────────────┤
 ↳ zero or more       ↳ zero or more
                     ├─────┤
                      ↳ returned index

O(log n) time complexity.

See also: binarySearch, lowerBound, upperBound, equalRange.

sort.partitionPoint

pub fn partitionPoint(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime predicate: fn (@TypeOf(context), T) bool,
) usize

File

lib/std/sort.zig:675

Code

pub fn partitionPoint(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime predicate: fn (@TypeOf(context), T) bool,
) usize {
    var it: usize = 0;
    var len: usize = items.len;

    while (len > 1) {
        const half: usize = len / 2;
        len -= half;
        if (predicate(context, items[it + half - 1])) {
            @branchHint(.unpredictable);
            it += half;
        }
    }

    if (it < items.len) {
        it += @intFromBool(predicate(context, items[it]));
    }

    return it;
}