stdasserttestingmemmathModeblockpdqpdqContextinsertioninsertionContextheapheapContextsiftDownascdescasc_u8asc_i32desc_u8desc_i32sort_funcscontext_sort_funcsIdAndValuelessThanswapbinarySearchorderU32orderI32orderLengthrorderlowerBoundcompareU32compareI32compareF32rcompareFnupperBoundcompareU32compareI32compareF32rcompareFnpartitionPointlowerU32lowerI32lowerF32lowerEqU32lowerEqI32lowerEqF32isEvenequalRangeorderU32orderI32orderF32orderLengthargMinminargMaxmaxisSorted
std.sort.argMax
函数
pub fn argMax( comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool, ) ?usize
参数
T: type
items: []const T
lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool
用法示例
test argMax {
try testing.expectEqual(@as(?usize, null), argMax(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 4), argMax(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 2), argMax(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 1), argMax(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
std.sort.argMin
函数
pub fn argMin( comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) ?usize
参数
T: type
items: []const T
lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool
用法示例
test argMin {
try testing.expectEqual(@as(?usize, null), argMin(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
std.sort.asc
函数
用于生成给定类型的比较函数。例如 sort(u8, slice, {}, asc(u8))。
pub fn asc(comptime T: type) fn (void, T, T) bool
参数
T: type
std.sort.asc_i32
常量
std.sort.asc_u8
常量
std.sort.asc.inner
函数
pub fn inner(_: void, a: T, b: T) bool
参数
_: void
a: T
b: T
std.sort.assert
别名
别名目标 std.debug.assert
std.sort.binarySearch
函数
返回 items 中返回 .eq 的元素索引,其比较由 compareFn 完成。
- 若存在多个这样的元素,则返回其中任意一个的索引。
- 若不存在这样的元素,则返回
null。
items 必须按 compareFn 升序排列:
[0] [len]
┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
│.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
└───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
├─────────────────┼─────────────────┼─────────────────┤
↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
├─────────────────┤
↳ 若不为 null,返回的
索引位于此范围内
O(log n) 时间复杂度。
pub fn binarySearch( comptime T: type, items: []const T, context: anytype, comptime compareFn: fn (@TypeOf(context), T) std.math.Order, ) ?usize
参数
用法示例
test binarySearch {
const S = struct {
fn orderU32(context: u32, item: u32) std.math.Order {
return std.math.order(context, item);
}
fn orderI32(context: i32, item: i32) std.math.Order {
return std.math.order(context, item);
}
fn orderLength(context: usize, item: []const u8) std.math.Order {
return std.math.order(context, item.len);
}
};
const R = struct {
b: i32,
e: i32,
fn r(b: i32, e: i32) @This() {
return .{ .b = b, .e = e };
}
fn order(context: i32, item: @This()) std.math.Order {
if (context < item.b) {
return .lt;
} else if (context > item.e) {
return .gt;
} else {
return .eq;
}
}
};
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));
}
std.sort.block
别名
别名目标 std.sort.block.block
std.sort.compareF32
函数
fn compareF32(context: f32, item: f32) std.math.Order
参数
context: f32
item: f32
std.sort.compareF32
函数
fn compareF32(context: f32, item: f32) std.math.Order
参数
context: f32
item: f32
std.sort.compareFn
函数
fn compareFn(context: i32, item: @This()) std.math.Order
参数
context: i32
item: @This()
std.sort.compareFn
函数
fn compareFn(context: i32, item: @This()) std.math.Order
参数
context: i32
item: @This()
std.sort.compareI32
函数
fn compareI32(context: i32, item: i32) std.math.Order
参数
context: i32
item: i32
std.sort.compareI32
函数
fn compareI32(context: i32, item: i32) std.math.Order
参数
context: i32
item: i32
std.sort.compareU32
函数
fn compareU32(context: u32, item: u32) std.math.Order
参数
context: u32
item: u32
std.sort.compareU32
函数
fn compareU32(context: u32, item: u32) std.math.Order
参数
context: u32
item: u32
std.sort.context_sort_funcs
常量
std.sort.desc
函数
用于生成给定类型的比较函数。例如 sort(u8, slice, {}, desc(u8))。
pub fn desc(comptime T: type) fn (void, T, T) bool
参数
T: type
std.sort.desc_i32
常量
std.sort.desc_u8
常量
std.sort.desc.inner
函数
pub fn inner(_: void, a: T, b: T) bool
参数
_: void
a: T
b: T
std.sort.equalRange
类型函数
返回 items 中下界和上界索引组成的元组,此范围内所有元素均返回 .eq(传给 compareFn 时)。
若 items 中没有元素返回 .eq,则两个索引均为 items 中第一个返回 .gt 的元素索引;若没有元素返回 .gt,则两个索引均为 items.len。
items 必须按 compareFn 升序排列:
[0] [len]
┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
│.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
└───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
├─────────────────┼─────────────────┼─────────────────┤
↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
├─────────────────┤
↳ 返回的范围
O(log n) 时间复杂度。
pub fn equalRange( comptime T: type, items: []const T, context: anytype, comptime compareFn: fn (@TypeOf(context), T) std.math.Order, ) struct { usize, usize }
参数
用法示例
test equalRange {
const S = struct {
fn orderU32(context: u32, item: u32) std.math.Order {
return std.math.order(context, item);
}
fn orderI32(context: i32, item: i32) std.math.Order {
return std.math.order(context, item);
}
fn orderF32(context: f32, item: f32) std.math.Order {
return std.math.order(context, item);
}
fn orderLength(context: usize, item: []const u8) std.math.Order {
return std.math.order(context, item.len);
}
};
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(.{ 3, 5 }, equalRange(u32, &[_]u32{ 2, 3, 4, 5, 5 }, @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,
));
}
std.sort.heap
函数
不稳定的原地排序。最佳、最坏和平均时间复杂度均为 O(n*log(n))。
内存复杂度为 O(1),不需要分配器。
按给定 lessThan 函数定义的关系升序排序。
pub fn heap( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
T: type
items: []T
lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.heap.lessThan
函数
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.sort.heap.swap
函数
pub fn swap(ctx: @This(), a: usize, b: usize) void
参数
ctx: @This()
a: usize
b: usize
std.sort.heapContext
函数
不稳定的原地排序。最佳、最坏与平均情况均为 O(n*log(n))。
使用 O(1) 内存,无需分配器。
context 必须具有 swap 和 lessThan 方法,每个都接受两个 usize 参数,表示元素索引。
按 lessThan 升序排序。
pub fn heapContext(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
std.sort.IdAndValue
容器
字段
id: usize
value: i32
std.sort.IdAndValue.lessThan
函数
fn lessThan(context: void, a: IdAndValue, b: IdAndValue) bool
参数
std.sort.insertion
函数
稳定的原地排序。最好情况 O(n),最坏情况 O(pow(n, 2))。
空间复杂度 O(1)(无需分配器)。
按给定 lessThan 函数所定义的升序排序。
pub fn insertion( comptime T: type, items: []T, context: anytype, comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool, ) void
参数
T: type
items: []T
lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool
std.sort.insertion.lessThan
函数
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.sort.insertion.swap
函数
pub fn swap(ctx: @This(), a: usize, b: usize) void
参数
ctx: @This()
a: usize
b: usize
std.sort.insertionContext
函数
稳定的原地排序。最佳时间复杂度为 O(n),最坏为 O(pow(n, 2))。
内存复杂度为 O(1),不需要分配器。
context 必须具有 swap 和 lessThan 方法,
每个方法接受两个表示条目索引的 usize 参数。
按 lessThan 定义的关系升序排序。
pub fn insertionContext(a: usize, b: usize, context: anytype) void
参数
a: usize
b: usize
std.sort.isEven
函数
fn isEven(_: void, item: u8) bool
参数
_: void
item: u8
std.sort.isSorted
函数
pub fn isSorted( comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool, ) bool
参数
T: type
items: []const T
lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool
用法示例
test isSorted {
try testing.expect(isSorted(i32, &[_]i32{}, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{10}, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ -10, 1, 1, 1, 10 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{}, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{-20}, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 3, 2, 1, 0, -1 }, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 10, -10 }, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, desc_i32));
try testing.expectEqual(false, isSorted(i32, &[_]i32{ 5, 4, 3, 2, 1 }, {}, asc_i32));
try testing.expectEqual(false, isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, desc_i32));
try testing.expect(isSorted(u8, "abcd", {}, asc_u8));
try testing.expect(isSorted(u8, "zyxw", {}, desc_u8));
try testing.expectEqual(false, isSorted(u8, "abcd", {}, desc_u8));
try testing.expectEqual(false, isSorted(u8, "zyxw", {}, asc_u8));
try testing.expect(isSorted(u8, "ffff", {}, asc_u8));
try testing.expect(isSorted(u8, "ffff", {}, desc_u8));
}
std.sort.lessThan
函数
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.sort.lowerBound
函数
返回 items 中按 compareFn 比较时,第一个大于或等于 context 的元素的索引。
如果不存在这样的元素,则返回 items.len。
items 必须按 compareFn 升序排列:
[0] [len]
┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
│.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
└───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
├─────────────────┼─────────────────┼─────────────────┤
↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
├───┤
↳ 返回的索引
时间复杂度为 O(log n)。
pub fn lowerBound( comptime T: type, items: []const T, context: anytype, comptime compareFn: fn (@TypeOf(context), T) std.math.Order, ) usize
参数
用法示例
test lowerBound {
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, 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));
}
std.sort.lowerBound.predicate
函数
fn predicate(ctx: @TypeOf(context), item: T) bool
参数
ctx: @TypeOf(context)
item: T
std.sort.lowerEqF32
函数
fn lowerEqF32(context: f32, item: f32) bool
参数
context: f32
item: f32
std.sort.lowerEqI32
函数
fn lowerEqI32(context: i32, item: i32) bool
参数
context: i32
item: i32
std.sort.lowerEqU32
函数
fn lowerEqU32(context: u32, item: u32) bool
参数
context: u32
item: u32
std.sort.lowerF32
函数
fn lowerF32(context: f32, item: f32) bool
参数
context: f32
item: f32
std.sort.lowerI32
函数
fn lowerI32(context: i32, item: i32) bool
参数
context: i32
item: i32
std.sort.lowerU32
函数
fn lowerU32(context: u32, item: u32) bool
参数
context: u32
item: u32
std.sort.math
别名
别名目标 std.math
std.sort.max
函数
pub fn max( comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool, ) ?T
参数
T: type
items: []const T
lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool
用法示例
test max {
try testing.expectEqual(@as(?i32, null), max(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 5), max(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 9), max(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 10), max(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 3), max(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
std.sort.mem
别名
别名目标 std.mem
std.sort.min
函数
pub fn min( comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool, ) ?T
参数
T: type
items: []const T
lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool
用法示例
test min {
try testing.expectEqual(@as(?i32, null), min(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 2), min(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, -10), min(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
std.sort.Mode
容器
字段
stable
unstable
std.sort.order
函数
fn order(context: i32, item: @This()) std.math.Order
参数
context: i32
item: @This()
std.sort.orderF32
函数
fn orderF32(context: f32, item: f32) std.math.Order
参数
context: f32
item: f32
std.sort.orderI32
函数
fn orderI32(context: i32, item: i32) std.math.Order
参数
context: i32
item: i32
std.sort.orderI32
函数
fn orderI32(context: i32, item: i32) std.math.Order
参数
context: i32
item: i32
std.sort.orderLength
函数
fn orderLength(context: usize, item: []const u8) std.math.Order
参数
context: usize
item: []const u8
std.sort.orderLength
函数
fn orderLength(context: usize, item: []const u8) std.math.Order
参数
context: usize
item: []const u8
std.sort.orderU32
函数
fn orderU32(context: u32, item: u32) std.math.Order
参数
context: u32
item: u32
std.sort.orderU32
函数
fn orderU32(context: u32, item: u32) std.math.Order
参数
context: u32
item: u32
std.sort.partitionPoint
函数
返回 items 相对于给定谓词的分区点索引。
- 若
items的所有元素均满足谓词,返回items.len。
items 必须包含一个所有元素均满足谓词的前缀,
且该前缀之后没有任何元素满足谓词:
[0] [len]
┌────┬────┬─/ /─┬────┬─────┬─────┬─/ /─┬─────┐
│true│true│ \ \ │true│false│false│ \ \ │false│
└────┴────┴─/ /─┴────┴─────┴─────┴─/ /─┴─────┘
├────────────────────┼───────────────────────┤
↳ 零个或多个 ↳ 零个或多个
├─────┤
↳ 返回的索引
时间复杂度为 O(log n)。
另请参见: binarySearch, lowerBound, upperBound, equalRange.
pub fn partitionPoint( comptime T: type, items: []const T, context: anytype, comptime predicate: fn (@TypeOf(context), T) bool, ) usize
参数
T: type
items: []const T
predicate: fn (@TypeOf(context), T) bool
用法示例
test partitionPoint {
const S = struct {
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 lowerEqF32(context: f32, item: f32) bool {
return item <= context;
}
fn isEven(_: void, item: u8) bool {
return item % 2 == 0;
}
};
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));
}
std.sort.pdq
别名
别名目标 std.sort.pdq.pdq
std.sort.pdqContext
别名
std.sort.r
函数
fn r(b: i32, e: i32) @This()
参数
b: i32
e: i32
std.sort.r
函数
fn r(val: i32) @This()
参数
val: i32
std.sort.r
函数
fn r(val: i32) @This()
参数
val: i32
std.sort.siftDown
函数
fn siftDown(a: usize, target: usize, b: usize, context: anytype) void
参数
a: usize
target: usize
b: usize
std.sort.sort_funcs
常量
std.sort.std
别名
别名目标 std
std.sort.swap
函数
pub fn swap(ctx: @This(), a: usize, b: usize) void
参数
ctx: @This()
a: usize
b: usize
std.sort.testing
别名
别名目标 std.testing
std.sort.upperBound
函数
返回 items 中根据 context 比较为更大的第一个元素索引,
比较由 compareFn 决定。若无此元素,返回 items.len。
items 必须按 compareFn 定义的升序排列:
[0] [len]
┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
│.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
└───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
├─────────────────┼─────────────────┼─────────────────┤
↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
├───┤
↳ 返回的索引
时间复杂度为 O(log n)。
pub fn upperBound( comptime T: type, items: []const T, context: anytype, comptime compareFn: fn (@TypeOf(context), T) std.math.Order, ) usize
参数
用法示例
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));
}
std.sort.upperBound.predicate
函数
fn predicate(ctx: @TypeOf(context), item: T) bool
参数
ctx: @TypeOf(context)
item: T
源码
std/sort.zig
const std = @import("std.zig");
const assert = std.debug.assert;
const testing = std.testing;
const mem = std.mem;
const math = std.math;
pub const Mode = enum { stable, unstable };
pub const block = @import("sort/block.zig").block;
pub const pdq = @import("sort/pdq.zig").pdq;
pub const pdqContext = @import("sort/pdq.zig").pdqContext;
/// 稳定的原地排序。最好情况 O(n),最坏情况 O(pow(n, 2))。
/// 空间复杂度 O(1)(无需分配器)。
/// 按给定 `lessThan` 函数所定义的升序排序。
pub fn insertion(
comptime T: type,
items: []T,
context: anytype,
comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
const Context = struct {
items: []T,
sub_ctx: @TypeOf(context),
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
return lessThanFn(ctx.sub_ctx, ctx.items[a], ctx.items[b]);
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
return mem.swap(T, &ctx.items[a], &ctx.items[b]);
}
};
insertionContext(0, items.len, Context{ .items = items, .sub_ctx = context });
}
/// 稳定的原地排序。最佳时间复杂度为 O(n),最坏为 O(pow(n, 2))。
/// 内存复杂度为 O(1),不需要分配器。
/// `context` 必须具有 `swap` 和 `lessThan` 方法,
/// 每个方法接受两个表示条目索引的 `usize` 参数。
/// 按 `lessThan` 定义的关系升序排序。
pub fn insertionContext(a: usize, b: usize, context: anytype) void {
assert(a <= b);
var i = a + 1;
while (i < b) : (i += 1) {
var j = i;
while (j > a and context.lessThan(j, j - 1)) : (j -= 1) {
context.swap(j, j - 1);
}
}
}
/// 不稳定的原地排序。最佳、最坏和平均时间复杂度均为 O(n*log(n))。
/// 内存复杂度为 O(1),不需要分配器。
/// 按给定 `lessThan` 函数定义的关系升序排序。
pub fn heap(
comptime T: type,
items: []T,
context: anytype,
comptime lessThanFn: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) void {
const Context = struct {
items: []T,
sub_ctx: @TypeOf(context),
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
return lessThanFn(ctx.sub_ctx, ctx.items[a], ctx.items[b]);
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
return mem.swap(T, &ctx.items[a], &ctx.items[b]);
}
};
heapContext(0, items.len, Context{ .items = items, .sub_ctx = context });
}
/// 不稳定的原地排序。最佳、最坏与平均情况均为 O(n*log(n))。
/// 使用 O(1) 内存,无需分配器。
/// `context` 必须具有 `swap` 和 `lessThan` 方法,每个都接受两个 `usize` 参数,表示元素索引。
/// 按 `lessThan` 升序排序。
///
pub fn heapContext(a: usize, b: usize, context: anytype) void {
assert(a <= b);
// 在线性时间内构建堆。
var i = a + (b - a) / 2;
while (i > a) {
i -= 1;
siftDown(a, i, b, context);
}
// 从堆中弹出最大元素。
i = b;
while (i > a) {
i -= 1;
context.swap(a, i);
siftDown(a, a, i, context);
}
}
fn siftDown(a: usize, target: usize, b: usize, context: anytype) void {
var cur = target;
while (true) {
// 如果下方乘法未溢出,则下面的表达式等于 (2*cur) - (2*a) + a + 1。
// `+ a + 1` 是安全的,因为:
// 对于 `a > 0`,有 `2a >= a + 1`。
// 对于 `a = 0`,表达式等于 `2*cur+1`。`2*cur` 是偶数,因此加 1 安全。
var child = (math.mul(usize, cur - a, 2) catch break) + a + 1;
// 若超出边界则停止
if (!(child < b)) break;
// `next_child` 最大为 `b`,因此不可能溢出
const next_child = child + 1;
// 将较大的子节点存入 `child`
if (next_child < b and context.lessThan(child, next_child)) {
child = next_child;
}
// 若 `cur` 处满足堆不变量则停止。
if (context.lessThan(child, cur)) break;
// 将 `cur` 与较大的子节点交换,
// 向下移动一层,并继续下沉。
context.swap(child, cur);
cur = child;
}
}
/// 用于生成给定类型的比较函数。例如 `sort(u8, slice, {}, asc(u8))`。
pub fn asc(comptime T: type) fn (void, T, T) bool {
return struct {
pub fn inner(_: void, a: T, b: T) bool {
return a < b;
}
}.inner;
}
/// 用于生成给定类型的比较函数。例如 `sort(u8, slice, {}, desc(u8))`。
pub fn desc(comptime T: type) fn (void, T, T) bool {
return struct {
pub fn inner(_: void, a: T, b: T) bool {
return a > b;
}
}.inner;
}
const asc_u8 = asc(u8);
const asc_i32 = asc(i32);
const desc_u8 = desc(u8);
const desc_i32 = desc(i32);
const sort_funcs = &[_]fn (comptime type, anytype, anytype, comptime anytype) void{
block,
pdq,
insertion,
heap,
};
const context_sort_funcs = &[_]fn (usize, usize, anytype) void{
// blockContext,
pdqContext,
insertionContext,
heapContext,
};
const IdAndValue = struct {
id: usize,
value: i32,
fn lessThan(context: void, a: IdAndValue, b: IdAndValue) bool {
_ = context;
return a.value < b.value;
}
};
test "stable sort" {
const expected = [_]IdAndValue{
IdAndValue{ .id = 0, .value = 0 },
IdAndValue{ .id = 1, .value = 0 },
IdAndValue{ .id = 2, .value = 0 },
IdAndValue{ .id = 0, .value = 1 },
IdAndValue{ .id = 1, .value = 1 },
IdAndValue{ .id = 2, .value = 1 },
IdAndValue{ .id = 0, .value = 2 },
IdAndValue{ .id = 1, .value = 2 },
IdAndValue{ .id = 2, .value = 2 },
};
var cases = [_][9]IdAndValue{
[_]IdAndValue{
IdAndValue{ .id = 0, .value = 0 },
IdAndValue{ .id = 0, .value = 1 },
IdAndValue{ .id = 0, .value = 2 },
IdAndValue{ .id = 1, .value = 0 },
IdAndValue{ .id = 1, .value = 1 },
IdAndValue{ .id = 1, .value = 2 },
IdAndValue{ .id = 2, .value = 0 },
IdAndValue{ .id = 2, .value = 1 },
IdAndValue{ .id = 2, .value = 2 },
},
[_]IdAndValue{
IdAndValue{ .id = 0, .value = 2 },
IdAndValue{ .id = 0, .value = 1 },
IdAndValue{ .id = 0, .value = 0 },
IdAndValue{ .id = 1, .value = 2 },
IdAndValue{ .id = 1, .value = 1 },
IdAndValue{ .id = 1, .value = 0 },
IdAndValue{ .id = 2, .value = 2 },
IdAndValue{ .id = 2, .value = 1 },
IdAndValue{ .id = 2, .value = 0 },
},
};
for (&cases) |*case| {
block(IdAndValue, (case.*)[0..], {}, IdAndValue.lessThan);
for (case.*, 0..) |item, i| {
try testing.expect(item.id == expected[i].id);
try testing.expect(item.value == expected[i].value);
}
}
}
test "stable sort fuzz testing" {
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
const random = prng.random();
const test_case_count = 10;
for (0..test_case_count) |_| {
const array_size = random.intRangeLessThan(usize, 0, 1000);
const array = try testing.allocator.alloc(IdAndValue, array_size);
defer testing.allocator.free(array);
// Value 使用较小的随机数,以制造冲突。
// Id 为逆序索引,以确保排序函数仅使用提供的 `lessThan`。
for (array, 0..) |*item, index| {
item.* = .{
.value = random.intRangeLessThan(i32, 0, 100),
.id = array_size - index,
};
}
block(IdAndValue, array, {}, IdAndValue.lessThan);
if (array_size > 0) {
for (array[0 .. array_size - 1], array[1..]) |x, y| {
try testing.expect(x.value <= y.value);
if (x.value == y.value) {
try testing.expect(x.id > y.id);
}
}
}
}
}
test "sort" {
const u8cases = [_][]const []const u8{
&[_][]const u8{
"",
"",
},
&[_][]const u8{
"a",
"a",
},
&[_][]const u8{
"az",
"az",
},
&[_][]const u8{
"za",
"az",
},
&[_][]const u8{
"asdf",
"adfs",
},
&[_][]const u8{
"one",
"eno",
},
};
const i32cases = [_][]const []const i32{
&[_][]const i32{
&[_]i32{},
&[_]i32{},
},
&[_][]const i32{
&[_]i32{1},
&[_]i32{1},
},
&[_][]const i32{
&[_]i32{ 0, 1 },
&[_]i32{ 0, 1 },
},
&[_][]const i32{
&[_]i32{ 1, 0 },
&[_]i32{ 0, 1 },
},
&[_][]const i32{
&[_]i32{ 1, -1, 0 },
&[_]i32{ -1, 0, 1 },
},
&[_][]const i32{
&[_]i32{ 2, 1, 3 },
&[_]i32{ 1, 2, 3 },
},
&[_][]const i32{
&[_]i32{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 55, 32, 39, 58, 21, 88, 43, 22, 59 },
&[_]i32{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 21, 22, 32, 39, 43, 55, 58, 59, 88 },
},
};
inline for (sort_funcs) |sortFn| {
for (u8cases) |case| {
var buf: [20]u8 = undefined;
const slice = buf[0..case[0].len];
@memcpy(slice, case[0]);
sortFn(u8, slice, {}, asc_u8);
try testing.expect(mem.eql(u8, slice, case[1]));
}
for (i32cases) |case| {
var buf: [20]i32 = undefined;
const slice = buf[0..case[0].len];
@memcpy(slice, case[0]);
sortFn(i32, slice, {}, asc_i32);
try testing.expect(mem.eql(i32, slice, case[1]));
}
}
}
test "sort descending" {
const rev_cases = [_][]const []const i32{
&[_][]const i32{
&[_]i32{},
&[_]i32{},
},
&[_][]const i32{
&[_]i32{1},
&[_]i32{1},
},
&[_][]const i32{
&[_]i32{ 0, 1 },
&[_]i32{ 1, 0 },
},
&[_][]const i32{
&[_]i32{ 1, 0 },
&[_]i32{ 1, 0 },
},
&[_][]const i32{
&[_]i32{ 1, -1, 0 },
&[_]i32{ 1, 0, -1 },
},
&[_][]const i32{
&[_]i32{ 2, 1, 3 },
&[_]i32{ 3, 2, 1 },
},
};
inline for (sort_funcs) |sortFn| {
for (rev_cases) |case| {
var buf: [8]i32 = undefined;
const slice = buf[0..case[0].len];
@memcpy(slice, case[0]);
sortFn(i32, slice, {}, desc_i32);
try testing.expect(mem.eql(i32, slice, case[1]));
}
}
}
test "sort with context in the middle of a slice" {
const Context = struct {
items: []i32,
pub fn lessThan(ctx: @This(), a: usize, b: usize) bool {
return ctx.items[a] < ctx.items[b];
}
pub fn swap(ctx: @This(), a: usize, b: usize) void {
return mem.swap(i32, &ctx.items[a], &ctx.items[b]);
}
};
const i32cases = [_][]const []const i32{
&[_][]const i32{
&[_]i32{ 0, 1, 8, 3, 6, 5, 4, 2, 9, 7, 10, 55, 32, 39, 58, 21, 88, 43, 22, 59 },
&[_]i32{ 50, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 21, 22, 32, 39, 43, 55, 58, 59, 88 },
},
};
const ranges = [_]struct { start: usize, end: usize }{
.{ .start = 10, .end = 20 },
.{ .start = 1, .end = 11 },
.{ .start = 3, .end = 7 },
};
inline for (context_sort_funcs) |sortFn| {
for (i32cases) |case| {
for (ranges) |range| {
var buf: [20]i32 = undefined;
const slice = buf[0..case[0].len];
@memcpy(slice, case[0]);
sortFn(range.start, range.end, Context{ .items = slice });
try testing.expectEqualSlices(i32, case[1][range.start..range.end], slice[range.start..range.end]);
}
}
}
}
test "sort fuzz testing" {
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
const random = prng.random();
const test_case_count = 10;
inline for (sort_funcs) |sortFn| {
for (0..test_case_count) |_| {
const array_size = random.intRangeLessThan(usize, 0, 1000);
const array = try testing.allocator.alloc(i32, array_size);
defer testing.allocator.free(array);
// 填充随机数据
for (array) |*item| {
item.* = random.intRangeLessThan(i32, 0, 100);
}
sortFn(i32, array, {}, asc_i32);
try testing.expect(isSorted(i32, array, {}, asc_i32));
}
}
}
/// 返回 `items` 中返回 `.eq` 的元素索引,其比较由 `compareFn` 完成。
/// - 若存在多个这样的元素,则返回其中任意一个的索引。
/// - 若不存在这样的元素,则返回 `null`。
///
/// `items` 必须按 `compareFn` 升序排列:
/// ```
/// [0] [len]
/// ┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
/// │.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
/// └───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
/// ├─────────────────┼─────────────────┼─────────────────┤
/// ↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
/// ├─────────────────┤
/// ↳ 若不为 null,返回的
/// 索引位于此范围内
/// ```
///
/// `O(log n)` 时间复杂度。
///
/// 另见:`lowerBound`、`upperBound`、`partitionPoint`、`equalRange`。
pub fn binarySearch(
comptime T: type,
items: []const T,
context: anytype,
comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) ?usize {
var low: usize = 0;
var high: usize = items.len;
while (low < high) {
// 避免在计算中点时溢出
const mid = low + (high - low) / 2;
switch (compareFn(context, items[mid])) {
.eq => return mid,
.gt => low = mid + 1,
.lt => high = mid,
}
}
return null;
}
test binarySearch {
const S = struct {
fn orderU32(context: u32, item: u32) std.math.Order {
return std.math.order(context, item);
}
fn orderI32(context: i32, item: i32) std.math.Order {
return std.math.order(context, item);
}
fn orderLength(context: usize, item: []const u8) std.math.Order {
return std.math.order(context, item.len);
}
};
const R = struct {
b: i32,
e: i32,
fn r(b: i32, e: i32) @This() {
return .{ .b = b, .e = e };
}
fn order(context: i32, item: @This()) std.math.Order {
if (context < item.b) {
return .lt;
} else if (context > item.e) {
return .gt;
} else {
return .eq;
}
}
};
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));
}
/// 返回 `items` 中按 `compareFn` 比较时,第一个大于或等于 `context` 的元素的索引。
/// 如果不存在这样的元素,则返回 `items.len`。
///
/// `items` 必须按 `compareFn` 升序排列:
/// ```
/// [0] [len]
/// ┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
/// │.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
/// └───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
/// ├─────────────────┼─────────────────┼─────────────────┤
/// ↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
/// ├───┤
/// ↳ 返回的索引
/// ```
///
/// 时间复杂度为 `O(log n)`。
///
/// 另请参见:`binarySearch`、`upperBound`、`partitionPoint`、`equalRange`。
pub fn lowerBound(
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() == .lt;
}
};
return partitionPoint(T, items, context, S.predicate);
}
test lowerBound {
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, 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));
}
/// 返回 `items` 中根据 `context` 比较为更大的第一个元素索引,
/// 比较由 `compareFn` 决定。若无此元素,返回 `items.len`。
///
/// `items` 必须按 `compareFn` 定义的升序排列:
/// ```
/// [0] [len]
/// ┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
/// │.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
/// └───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
/// ├─────────────────┼─────────────────┼─────────────────┤
/// ↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
/// ├───┤
/// ↳ 返回的索引
/// ```
///
/// 时间复杂度为 `O(log n)`。
///
/// 另请参见:`binarySearch`、`lowerBound`、`partitionPoint`、`equalRange`。
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);
}
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));
}
/// 返回 `items` 相对于给定谓词的分区点索引。
/// - 若 `items` 的所有元素均满足谓词,返回 `items.len`。
///
/// `items` 必须包含一个所有元素均满足谓词的前缀,
/// 且该前缀之后没有任何元素满足谓词:
/// ```
/// [0] [len]
/// ┌────┬────┬─/ /─┬────┬─────┬─────┬─/ /─┬─────┐
/// │true│true│ \ \ │true│false│false│ \ \ │false│
/// └────┴────┴─/ /─┴────┴─────┴─────┴─/ /─┴─────┘
/// ├────────────────────┼───────────────────────┤
/// ↳ 零个或多个 ↳ 零个或多个
/// ├─────┤
/// ↳ 返回的索引
/// ```
///
/// 时间复杂度为 `O(log n)`。
///
/// 另请参见: `binarySearch`, `lowerBound, `upperBound`, `equalRange`.
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;
}
test partitionPoint {
const S = struct {
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 lowerEqF32(context: f32, item: f32) bool {
return item <= context;
}
fn isEven(_: void, item: u8) bool {
return item % 2 == 0;
}
};
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));
}
/// 返回 `items` 中下界和上界索引组成的元组,此范围内所有元素均返回 `.eq`(传给 `compareFn` 时)。
/// 若 `items` 中没有元素返回 `.eq`,则两个索引均为 `items` 中第一个返回 `.gt` 的元素索引;若没有元素返回 `.gt`,则两个索引均为 `items.len`。
///
/// `items` 必须按 `compareFn` 升序排列:
/// ```
/// [0] [len]
/// ┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
/// │.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
/// └───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
/// ├─────────────────┼─────────────────┼─────────────────┤
/// ↳ 零个或多个 ↳ 零个或多个 ↳ 零个或多个
/// ├─────────────────┤
/// ↳ 返回的范围
/// ```
///
/// `O(log n)` 时间复杂度。
///
/// 另见:`binarySearch`、`lowerBound`、`upperBound`、`partitionPoint`。
///
///
///
pub fn equalRange(
comptime T: type,
items: []const T,
context: anytype,
comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) struct { usize, usize } {
var low: usize = 0;
var high: usize = items.len;
while (low < high) {
const mid = low + (high - low) / 2;
switch (compareFn(context, items[mid])) {
.gt => {
low = mid + 1;
},
.lt => {
high = mid;
},
.eq => {
return .{
low + std.sort.lowerBound(
T,
items[low..mid],
context,
compareFn,
),
mid + std.sort.upperBound(
T,
items[mid..high],
context,
compareFn,
),
};
},
}
}
return .{ low, low };
}
test equalRange {
const S = struct {
fn orderU32(context: u32, item: u32) std.math.Order {
return std.math.order(context, item);
}
fn orderI32(context: i32, item: i32) std.math.Order {
return std.math.order(context, item);
}
fn orderF32(context: f32, item: f32) std.math.Order {
return std.math.order(context, item);
}
fn orderLength(context: usize, item: []const u8) std.math.Order {
return std.math.order(context, item.len);
}
};
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(.{ 3, 5 }, equalRange(u32, &[_]u32{ 2, 3, 4, 5, 5 }, @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(
comptime T: type,
items: []const T,
context: anytype,
comptime lessThan: fn (@TypeOf(context), lhs: T, rhs: T) bool,
) ?usize {
if (items.len == 0) {
return null;
}
var smallest = items[0];
var smallest_index: usize = 0;
for (items[1..], 0..) |item, i| {
if (lessThan(context, item, smallest)) {
smallest = item;
smallest_index = i + 1;
}
}
return smallest_index;
}
test argMin {
try testing.expectEqual(@as(?usize, null), argMin(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
pub fn min(
comptime T: type,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) ?T {
const i = argMin(T, items, context, lessThan) orelse return null;
return items[i];
}
test min {
try testing.expectEqual(@as(?i32, null), min(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 2), min(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, -10), min(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
pub fn argMax(
comptime T: type,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) ?usize {
if (items.len == 0) {
return null;
}
var biggest = items[0];
var biggest_index: usize = 0;
for (items[1..], 0..) |item, i| {
if (lessThan(context, biggest, item)) {
biggest = item;
biggest_index = i + 1;
}
}
return biggest_index;
}
test argMax {
try testing.expectEqual(@as(?usize, null), argMax(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?usize, 4), argMax(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 2), argMax(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?usize, 1), argMax(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
pub fn max(
comptime T: type,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) ?T {
const i = argMax(T, items, context, lessThan) orelse return null;
return items[i];
}
test max {
try testing.expectEqual(@as(?i32, null), max(i32, &[_]i32{}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{1}, {}, asc_i32));
try testing.expectEqual(@as(?i32, 5), max(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 9), max(i32, &[_]i32{ 9, 3, 8, 2, 5 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 10), max(i32, &[_]i32{ -10, 1, 10 }, {}, asc_i32));
try testing.expectEqual(@as(?i32, 3), max(i32, &[_]i32{ 6, 3, 5, 7, 6 }, {}, desc_i32));
}
pub fn isSorted(
comptime T: type,
items: []const T,
context: anytype,
comptime lessThan: fn (context: @TypeOf(context), lhs: T, rhs: T) bool,
) bool {
var i: usize = 1;
while (i < items.len) : (i += 1) {
if (lessThan(context, items[i], items[i - 1])) {
return false;
}
}
return true;
}
test isSorted {
try testing.expect(isSorted(i32, &[_]i32{}, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{10}, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ -10, 1, 1, 1, 10 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{}, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{-20}, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 3, 2, 1, 0, -1 }, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 10, -10 }, {}, desc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, asc_i32));
try testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, {}, desc_i32));
try testing.expectEqual(false, isSorted(i32, &[_]i32{ 5, 4, 3, 2, 1 }, {}, asc_i32));
try testing.expectEqual(false, isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, {}, desc_i32));
try testing.expect(isSorted(u8, "abcd", {}, asc_u8));
try testing.expect(isSorted(u8, "zyxw", {}, desc_u8));
try testing.expectEqual(false, isSorted(u8, "abcd", {}, desc_u8));
try testing.expectEqual(false, isSorted(u8, "zyxw", {}, asc_u8));
try testing.expect(isSorted(u8, "ffff", {}, asc_u8));
try testing.expect(isSorted(u8, "ffff", {}, desc_u8));
}