Zig 0.17.0-dev (Split by item)

?

× Shortcut keys

?: Show these tips

S: Focus search field

Esc: Clear focus & close tips

U: Jump to source code

↑: Move up in search results

↓: Move down in search results

↵: Go to active search result

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 standard library. Public Function

partitionPoint

Doc Source

Public Function

std.sort.partitionPoint

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

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.

Params

T: type
items: []const T
context
predicate: fn (@TypeOf(context), T) bool

File

sort.zig:675

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;
}