Commit a655c15c40
Changed files (3)
lib
compiler
aro
std
debug
lib/compiler/aro/aro/Preprocessor.zig
@@ -265,14 +265,13 @@ fn clearBuffers(pp: *Preprocessor) void {
pub fn expansionSlice(pp: *Preprocessor, tok: Tree.TokenIndex) []Source.Location {
const S = struct {
- fn order_token_index(context: void, lhs: Tree.TokenIndex, rhs: Tree.TokenIndex) std.math.Order {
- _ = context;
- return std.math.order(lhs, rhs);
+ fn orderTokenIndex(context: Tree.TokenIndex, item: Tree.TokenIndex) std.math.Order {
+ return std.math.order(item, context);
}
};
const indices = pp.expansion_entries.items(.idx);
- const idx = std.sort.binarySearch(Tree.TokenIndex, tok, indices, {}, S.order_token_index) orelse return &.{};
+ const idx = std.sort.binarySearch(Tree.TokenIndex, indices, tok, S.orderTokenIndex) orelse return &.{};
const locs = pp.expansion_entries.items(.locs)[idx];
var i: usize = 0;
while (locs[i].id != .unused) : (i += 1) {}
lib/std/debug/SelfInfo.zig
@@ -1842,14 +1842,14 @@ pub fn unwindFrameDwarf(
&fde,
);
} else {
- const index = std.sort.binarySearch(Dwarf.FrameDescriptionEntry, context.pc, di.fde_list.items, {}, struct {
- pub fn compareFn(_: void, pc: usize, mid_item: Dwarf.FrameDescriptionEntry) std.math.Order {
- if (pc < mid_item.pc_begin) return .lt;
+ const index = std.sort.binarySearch(Dwarf.FrameDescriptionEntry, di.fde_list.items, context.pc, struct {
+ pub fn compareFn(pc: usize, item: Dwarf.FrameDescriptionEntry) std.math.Order {
+ if (pc < item.pc_begin) return .gt;
- const range_end = mid_item.pc_begin + mid_item.pc_range;
+ const range_end = item.pc_begin + item.pc_range;
if (pc < range_end) return .eq;
- return .gt;
+ return .lt;
}
}.compareFn);
lib/std/sort.zig
@@ -427,375 +427,388 @@ test "sort fuzz testing" {
}
}
-/// Returns the index of an element in `items` equal to `key`.
-/// If there are multiple such elements, returns the index of any one of them.
-/// If there are no such elements, returns `null`.
+/// Returns the index of an element in `items` returning `.eq` when given to `compareFn`.
+/// - If there are multiple such elements, returns the index of any one of them.
+/// - If there are no such elements, returns `null`.
///
-/// `items` must be sorted in ascending order with respect to `compareFn`.
+/// `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
+/// ├─────────────────┤
+/// ↳ if not null, returned
+/// index is in this range
+/// ```
///
-/// O(log n) complexity.
+/// `O(log n)` time complexity.
+///
+/// See also: `lowerBound, `upperBound`, `partitionPoint`, `equalRange`.
pub fn binarySearch(
comptime T: type,
- key: anytype,
items: []const T,
context: anytype,
- comptime compareFn: fn (context: @TypeOf(context), key: @TypeOf(key), mid_item: T) math.Order,
+ comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) ?usize {
- var left: usize = 0;
- var right: usize = items.len;
+ var low: usize = 0;
+ var high: usize = items.len;
- while (left < right) {
+ while (low < high) {
// Avoid overflowing in the midpoint calculation
- const mid = left + (right - left) / 2;
- // Compare the key with the midpoint element
- switch (compareFn(context, key, items[mid])) {
+ const mid = low + (high - low) / 2;
+ switch (compareFn(context, items[mid])) {
.eq => return mid,
- .gt => left = mid + 1,
- .lt => right = mid,
+ .lt => low = mid + 1, // item too small
+ .gt => high = mid, // item too big
}
}
-
return null;
}
test binarySearch {
const S = struct {
- fn order_u32(context: void, lhs: u32, rhs: u32) math.Order {
- _ = context;
- return math.order(lhs, rhs);
+ fn orderU32(context: u32, item: u32) std.math.Order {
+ return std.math.order(item, context);
+ }
+ fn orderI32(context: i32, item: i32) std.math.Order {
+ return std.math.order(item, context);
}
- fn order_i32(context: void, lhs: i32, rhs: i32) math.Order {
- _ = context;
- return math.order(lhs, rhs);
+ fn orderLength(context: usize, item: []const u8) std.math.Order {
+ return std.math.order(item.len, context);
}
};
- try testing.expectEqual(
- @as(?usize, null),
- binarySearch(u32, @as(u32, 1), &[_]u32{}, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, 0),
- binarySearch(u32, @as(u32, 1), &[_]u32{1}, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, null),
- binarySearch(u32, @as(u32, 1), &[_]u32{0}, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, null),
- binarySearch(u32, @as(u32, 0), &[_]u32{1}, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, 4),
- binarySearch(u32, @as(u32, 5), &[_]u32{ 1, 2, 3, 4, 5 }, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, 0),
- binarySearch(u32, @as(u32, 2), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.order_u32),
- );
- try testing.expectEqual(
- @as(?usize, 1),
- binarySearch(i32, @as(i32, -4), &[_]i32{ -7, -4, 0, 9, 10 }, {}, S.order_i32),
- );
- try testing.expectEqual(
- @as(?usize, 3),
- binarySearch(i32, @as(i32, 98), &[_]i32{ -100, -25, 2, 98, 99, 100 }, {}, S.order_i32),
- );
const R = struct {
b: i32,
e: i32,
fn r(b: i32, e: i32) @This() {
- return @This(){ .b = b, .e = e };
+ return .{ .b = b, .e = e };
}
- fn order(context: void, key: i32, mid_item: @This()) math.Order {
- _ = context;
-
- if (key < mid_item.b) {
+ fn order(context: i32, item: @This()) std.math.Order {
+ if (item.e < context) {
return .lt;
- }
-
- if (key > mid_item.e) {
+ } else if (item.b > context) {
return .gt;
+ } else {
+ return .eq;
}
-
- return .eq;
}
};
- try testing.expectEqual(
- @as(?usize, null),
- binarySearch(R, @as(i32, -45), &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, {}, R.order),
- );
- try testing.expectEqual(
- @as(?usize, 2),
- binarySearch(R, @as(i32, 10), &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, {}, R.order),
- );
- try testing.expectEqual(
- @as(?usize, 1),
- binarySearch(R, @as(i32, -20), &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, {}, R.order),
- );
-}
-
-/// Returns the index of the first element in `items` greater than or equal to `key`,
-/// or `items.len` if all elements are less than `key`.
+
+ try std.testing.expectEqual(null, binarySearch(u32, &[_]u32{}, @as(u32, 1), S.orderU32));
+ try std.testing.expectEqual(0, binarySearch(u32, &[_]u32{1}, @as(u32, 1), S.orderU32));
+ try std.testing.expectEqual(null, binarySearch(u32, &[_]u32{0}, @as(u32, 1), S.orderU32));
+ try std.testing.expectEqual(null, binarySearch(u32, &[_]u32{1}, @as(u32, 0), S.orderU32));
+ try std.testing.expectEqual(4, binarySearch(u32, &[_]u32{ 1, 2, 3, 4, 5 }, @as(u32, 5), S.orderU32));
+ try std.testing.expectEqual(0, binarySearch(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 2), S.orderU32));
+ try std.testing.expectEqual(1, binarySearch(i32, &[_]i32{ -7, -4, 0, 9, 10 }, @as(i32, -4), S.orderI32));
+ try std.testing.expectEqual(3, binarySearch(i32, &[_]i32{ -100, -25, 2, 98, 99, 100 }, @as(i32, 98), S.orderI32));
+ try std.testing.expectEqual(null, binarySearch(R, &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, @as(i32, -45), R.order));
+ try std.testing.expectEqual(2, binarySearch(R, &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, @as(i32, 10), R.order));
+ try std.testing.expectEqual(1, binarySearch(R, &[_]R{ R.r(-100, -50), R.r(-40, -20), R.r(-10, 20), R.r(30, 40) }, @as(i32, -20), R.order));
+ try std.testing.expectEqual(2, binarySearch([]const u8, &[_][]const u8{ "", "abc", "1234", "vwxyz" }, @as(usize, 4), S.orderLength));
+}
+
+/// Returns the index of the first element in `items` returning `.eq` or `.gt`
+/// when given to `compareFn`.
+/// - Returns `items.len` if all elements return `.lt`.
+///
+/// `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
+/// ```
///
-/// `items` must be sorted in ascending order with respect to `compareFn`.
+/// `O(log n)` time complexity.
///
-/// O(log n) complexity.
+/// See also: `binarySearch`, `upperBound`, `partitionPoint`, `equalRange`.
pub fn lowerBound(
comptime T: type,
- key: anytype,
items: []const T,
context: anytype,
- comptime lessThan: fn (context: @TypeOf(context), lhs: @TypeOf(key), rhs: T) bool,
+ comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) usize {
- var left: usize = 0;
- var right: usize = items.len;
-
- while (left < right) {
- const mid = left + (right - left) / 2;
- if (lessThan(context, items[mid], key)) {
- left = mid + 1;
- } else {
- right = mid;
+ const S = struct {
+ fn predicate(ctx: @TypeOf(context), item: T) bool {
+ return compareFn(ctx, item) == .lt;
}
- }
-
- return left;
+ };
+ return partitionPoint(T, items, context, S.predicate);
}
test lowerBound {
const S = struct {
- fn lower_u32(context: void, lhs: u32, rhs: u32) bool {
- _ = context;
- return lhs < rhs;
+ fn compareU32(context: u32, item: u32) std.math.Order {
+ return std.math.order(item, context);
}
- fn lower_i32(context: void, lhs: i32, rhs: i32) bool {
- _ = context;
- return lhs < rhs;
+ fn compareI32(context: i32, item: i32) std.math.Order {
+ return std.math.order(item, context);
}
- fn lower_f32(context: void, lhs: f32, rhs: f32) bool {
- _ = context;
- return lhs < rhs;
+ fn compareF32(context: f32, item: f32) std.math.Order {
+ return std.math.order(item, context);
}
};
+ const R = struct {
+ val: i32,
- try testing.expectEqual(
- @as(usize, 0),
- lowerBound(u32, @as(u32, 0), &[_]u32{}, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 0),
- lowerBound(u32, @as(u32, 0), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 0),
- lowerBound(u32, @as(u32, 2), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- lowerBound(u32, @as(u32, 5), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- lowerBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- lowerBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- lowerBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 5),
- lowerBound(u32, @as(u32, 64), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- lowerBound(u32, @as(u32, 100), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- lowerBound(i32, @as(i32, 5), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(usize, 1),
- lowerBound(f32, @as(f32, -33.4), &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, {}, S.lower_f32),
- );
-}
-
-/// Returns the index of the first element in `items` greater than `key`,
-/// or `items.len` if all elements are less than or equal to `key`.
+ fn r(val: i32) @This() {
+ return .{ .val = val };
+ }
+
+ fn compareFn(context: i32, item: @This()) std.math.Order {
+ return std.math.order(item.val, context);
+ }
+ };
+
+ try std.testing.expectEqual(0, lowerBound(u32, &[_]u32{}, @as(u32, 0), S.compareU32));
+ try std.testing.expectEqual(0, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 0), S.compareU32));
+ try std.testing.expectEqual(0, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 2), S.compareU32));
+ try std.testing.expectEqual(2, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 5), S.compareU32));
+ try std.testing.expectEqual(2, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 8), S.compareU32));
+ try std.testing.expectEqual(6, lowerBound(u32, &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, @as(u32, 8), S.compareU32));
+ try std.testing.expectEqual(2, lowerBound(u32, &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, @as(u32, 8), S.compareU32));
+ try std.testing.expectEqual(5, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 64), S.compareU32));
+ try std.testing.expectEqual(6, lowerBound(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 100), S.compareU32));
+ try std.testing.expectEqual(2, lowerBound(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 5), S.compareI32));
+ try std.testing.expectEqual(1, lowerBound(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, lowerBound(R, &[_]R{ R.r(-100), R.r(-40), R.r(-10), R.r(30) }, @as(i32, -20), R.compareFn));
+}
+
+/// Returns the index of the first element in `items` returning `.gt`
+/// when given to `compareFn`.
+/// - Returns `items.len` if none of the elements return `.gt`.
///
-/// `items` must be sorted in ascending order with respect to `compareFn`.
+/// `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) complexity.
+/// `O(log n)` time complexity.
+///
+/// See also: `binarySearch`, `lowerBound`, `partitionPoint`, `equalRange`.
pub fn upperBound(
comptime T: type,
- key: anytype,
items: []const T,
context: anytype,
- comptime lessThan: fn (context: @TypeOf(context), lhs: @TypeOf(key), rhs: T) bool,
+ comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) usize {
- var left: usize = 0;
- var right: usize = items.len;
+ const S = struct {
+ fn predicate(ctx: @TypeOf(context), item: T) bool {
+ return compareFn(ctx, item) != .gt;
+ }
+ };
+ return partitionPoint(T, items, context, S.predicate);
+}
- while (left < right) {
- const mid = left + (right - left) / 2;
- if (!lessThan(context, key, items[mid])) {
- left = mid + 1;
+test upperBound {
+ const S = struct {
+ fn compareU32(context: u32, item: u32) std.math.Order {
+ return std.math.order(item, context);
+ }
+ fn compareI32(context: i32, item: i32) std.math.Order {
+ return std.math.order(item, context);
+ }
+ fn compareF32(context: f32, item: f32) std.math.Order {
+ return std.math.order(item, context);
+ }
+ };
+ 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(item.val, context);
+ }
+ };
+
+ 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));
+}
+
+/// 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`.
+pub fn partitionPoint(
+ comptime T: type,
+ items: []const T,
+ context: anytype,
+ comptime predicate: fn (@TypeOf(context), T) bool,
+) usize {
+ var low: usize = 0;
+ var high: usize = items.len;
+
+ while (low < high) {
+ const mid = low + (high - low) / 2;
+ if (predicate(context, items[mid])) {
+ low = mid + 1;
} else {
- right = mid;
+ high = mid;
}
}
-
- return left;
+ return low;
}
-test upperBound {
+test partitionPoint {
const S = struct {
- fn lower_u32(context: void, lhs: u32, rhs: u32) bool {
- _ = context;
- return lhs < rhs;
+ fn lowerU32(context: u32, item: u32) bool {
+ return item < context;
+ }
+ fn lowerI32(context: i32, item: i32) bool {
+ return item < context;
+ }
+ fn lowerF32(context: f32, item: f32) bool {
+ return item < context;
+ }
+ fn lowerEqU32(context: u32, item: u32) bool {
+ return item <= context;
+ }
+ fn lowerEqI32(context: i32, item: i32) bool {
+ return item <= context;
}
- fn lower_i32(context: void, lhs: i32, rhs: i32) bool {
- _ = context;
- return lhs < rhs;
+ fn lowerEqF32(context: f32, item: f32) bool {
+ return item <= context;
}
- fn lower_f32(context: void, lhs: f32, rhs: f32) bool {
- _ = context;
- return lhs < rhs;
+ fn isEven(_: void, item: u8) bool {
+ return item % 2 == 0;
}
};
- try testing.expectEqual(
- @as(usize, 0),
- upperBound(u32, @as(u32, 0), &[_]u32{}, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 0),
- upperBound(u32, @as(u32, 0), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 1),
- upperBound(u32, @as(u32, 2), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- upperBound(u32, @as(u32, 5), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- upperBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- upperBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 3),
- upperBound(u32, @as(u32, 8), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- upperBound(u32, @as(u32, 64), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 6),
- upperBound(u32, @as(u32, 100), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(usize, 2),
- upperBound(i32, @as(i32, 5), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(usize, 1),
- upperBound(f32, @as(f32, -33.4), &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, {}, S.lower_f32),
- );
-}
-
-/// Returns a tuple of the lower and upper indices in `items` between which all elements are equal to `key`.
-/// If no element in `items` is equal to `key`, both indices are the
-/// index of the first element in `items` greater than `key`.
-/// If no element in `items` is greater than `key`, both indices equal `items.len`.
+ try std.testing.expectEqual(0, partitionPoint(u32, &[_]u32{}, @as(u32, 0), S.lowerU32));
+ try std.testing.expectEqual(0, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 0), S.lowerU32));
+ try std.testing.expectEqual(0, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 2), S.lowerU32));
+ try std.testing.expectEqual(2, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 5), S.lowerU32));
+ try std.testing.expectEqual(2, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 8), S.lowerU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, @as(u32, 8), S.lowerU32));
+ try std.testing.expectEqual(2, partitionPoint(u32, &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, @as(u32, 8), S.lowerU32));
+ try std.testing.expectEqual(5, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 64), S.lowerU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 100), S.lowerU32));
+ try std.testing.expectEqual(2, partitionPoint(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 5), S.lowerI32));
+ try std.testing.expectEqual(1, partitionPoint(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, @as(f32, -33.4), S.lowerF32));
+ try std.testing.expectEqual(0, partitionPoint(u32, &[_]u32{}, @as(u32, 0), S.lowerEqU32));
+ try std.testing.expectEqual(0, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 0), S.lowerEqU32));
+ try std.testing.expectEqual(1, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 2), S.lowerEqU32));
+ try std.testing.expectEqual(2, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 5), S.lowerEqU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 7, 7, 7, 7, 16, 32, 64 }, @as(u32, 8), S.lowerEqU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 8, 8, 8, 8, 16, 32, 64 }, @as(u32, 8), S.lowerEqU32));
+ try std.testing.expectEqual(3, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 8), S.lowerEqU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 64), S.lowerEqU32));
+ try std.testing.expectEqual(6, partitionPoint(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 100), S.lowerEqU32));
+ try std.testing.expectEqual(2, partitionPoint(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 5), S.lowerEqI32));
+ try std.testing.expectEqual(1, partitionPoint(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, @as(f32, -33.4), S.lowerEqF32));
+ try std.testing.expectEqual(4, partitionPoint(u8, &[_]u8{ 0, 50, 14, 2, 5, 71 }, {}, S.isEven));
+}
+
+/// Returns a tuple of the lower and upper indices in `items` between which all
+/// elements return `.eq` when given to `compareFn`.
+/// - If no element in `items` returns `.eq`, both indices are the
+/// index of the first element in `items` returning `.gt`.
+/// - If no element in `items` returns `.gt`, both indices equal `items.len`.
///
-/// `items` must be sorted in ascending order with respect to `compareFn`.
+/// `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 range
+/// ```
///
-/// O(log n) complexity.
+/// `O(log n)` time complexity.
///
-/// See also: `lowerBound` and `upperBound`.
+/// See also: `binarySearch`, `lowerBound, `upperBound`, `partitionPoint`.
pub fn equalRange(
comptime T: type,
- key: anytype,
items: []const T,
context: anytype,
- comptime lessThan: fn (context: @TypeOf(context), lhs: @TypeOf(key), rhs: T) bool,
+ comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) struct { usize, usize } {
return .{
- lowerBound(T, key, items, context, lessThan),
- upperBound(T, key, items, context, lessThan),
+ lowerBound(T, items, context, compareFn),
+ upperBound(T, items, context, compareFn),
};
}
test equalRange {
const S = struct {
- fn lower_u32(context: void, lhs: u32, rhs: u32) bool {
- _ = context;
- return lhs < rhs;
+ fn orderU32(context: u32, item: u32) std.math.Order {
+ return std.math.order(item, context);
}
- fn lower_i32(context: void, lhs: i32, rhs: i32) bool {
- _ = context;
- return lhs < rhs;
+ fn orderI32(context: i32, item: i32) std.math.Order {
+ return std.math.order(item, context);
}
- fn lower_f32(context: void, lhs: f32, rhs: f32) bool {
- _ = context;
- return lhs < rhs;
+ fn orderF32(context: f32, item: f32) std.math.Order {
+ return std.math.order(item, context);
+ }
+ fn orderLength(context: usize, item: []const u8) std.math.Order {
+ return std.math.order(item.len, context);
}
};
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 0, 0 }),
- equalRange(i32, @as(i32, 0), &[_]i32{}, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 0, 0 }),
- equalRange(i32, @as(i32, 0), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 0, 1 }),
- equalRange(i32, @as(i32, 2), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 2, 2 }),
- equalRange(i32, @as(i32, 5), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 2, 3 }),
- equalRange(i32, @as(i32, 8), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 5, 6 }),
- equalRange(i32, @as(i32, 64), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 6, 6 }),
- equalRange(i32, @as(i32, 100), &[_]i32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 2, 6 }),
- equalRange(i32, @as(i32, 8), &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, {}, S.lower_i32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 2, 2 }),
- equalRange(u32, @as(u32, 5), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.lower_u32),
- );
- try testing.expectEqual(
- @as(struct { usize, usize }, .{ 1, 1 }),
- equalRange(f32, @as(f32, -33.4), &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, {}, S.lower_f32),
- );
+ try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{}, @as(i32, 0), S.orderI32));
+ try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 0), S.orderI32));
+ try std.testing.expectEqual(.{ 0, 1 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 2), S.orderI32));
+ try std.testing.expectEqual(.{ 2, 2 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 5), S.orderI32));
+ try std.testing.expectEqual(.{ 2, 3 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 8), S.orderI32));
+ try std.testing.expectEqual(.{ 5, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 64), S.orderI32));
+ try std.testing.expectEqual(.{ 6, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, @as(i32, 100), S.orderI32));
+ try std.testing.expectEqual(.{ 2, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, @as(i32, 8), S.orderI32));
+ try std.testing.expectEqual(.{ 2, 2 }, equalRange(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, @as(u32, 5), S.orderU32));
+ try std.testing.expectEqual(.{ 1, 1 }, equalRange(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, @as(f32, -33.4), S.orderF32));
+ try std.testing.expectEqual(.{ 3, 5 }, equalRange(
+ []const u8,
+ &[_][]const u8{ "Mars", "Venus", "Earth", "Saturn", "Uranus", "Mercury", "Jupiter", "Neptune" },
+ @as(usize, 6),
+ S.orderLength,
+ ));
}
pub fn argMin(