From 6bb0ee0bc4015823091112eade0440a5ca9e84c2 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Wed, 4 Dec 2019 16:41:32 +0100 Subject: Add std.sort.isSorted --- lib/std/sort.zig | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) (limited to 'lib') diff --git a/lib/std/sort.zig b/lib/std/sort.zig index f8b8a39134..0fb029bb51 100644 --- a/lib/std/sort.zig +++ b/lib/std/sort.zig @@ -1210,3 +1210,41 @@ pub fn max(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) T { } return biggest; } + +pub fn isSorted(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) bool { + var i: usize = 1; + while (i < items.len) : (i += 1) { + if (lessThan(items[i], items[i - 1])) { + return false; + } + } + + return true; +} + +test "std.sort.isSorted" { + testing.expect(isSorted(i32, &[_]i32{}, asc(i32))); + testing.expect(isSorted(i32, &[_]i32{10}, asc(i32))); + testing.expect(isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expect(isSorted(i32, &[_]i32{ -10, 1, 1, 1, 10 }, asc(i32))); + + testing.expect(isSorted(i32, &[_]i32{}, desc(i32))); + testing.expect(isSorted(i32, &[_]i32{-20}, desc(i32))); + testing.expect(isSorted(i32, &[_]i32{ 3, 2, 1, 0, -1 }, desc(i32))); + testing.expect(isSorted(i32, &[_]i32{ 10, -10 }, desc(i32))); + + testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expect(isSorted(i32, &[_]i32{ 1, 1, 1, 1, 1 }, desc(i32))); + + testing.expectEqual(false, isSorted(i32, &[_]i32{ 5, 4, 3, 2, 1 }, asc(i32))); + testing.expectEqual(false, isSorted(i32, &[_]i32{ 1, 2, 3, 4, 5 }, desc(i32))); + + testing.expect(isSorted(u8, "abcd", asc(u8))); + testing.expect(isSorted(u8, "zyxw", desc(u8))); + + testing.expectEqual(false, isSorted(u8, "abcd", desc(u8))); + testing.expectEqual(false, isSorted(u8, "zyxw", asc(u8))); + + testing.expect(isSorted(u8, "ffff", asc(u8))); + testing.expect(isSorted(u8, "ffff", desc(u8))); +} -- cgit v1.2.3 From 65f57e44993c51ae6a582d18ad7c460ac229e68f Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Wed, 4 Dec 2019 16:42:18 +0100 Subject: Make std.sort.max accept const slices and add tests --- lib/std/sort.zig | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/std/sort.zig b/lib/std/sort.zig index 0fb029bb51..4913fd8f78 100644 --- a/lib/std/sort.zig +++ b/lib/std/sort.zig @@ -1189,7 +1189,7 @@ fn fuzzTest(rng: *std.rand.Random) void { } } -pub fn min(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) T { +pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) T { var i: usize = 0; var smallest = items[0]; for (items[1..]) |item| { @@ -1200,7 +1200,16 @@ pub fn min(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) T { return smallest; } -pub fn max(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) T { +test "std.sort.min" { + testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(i32, 2), min(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(i32, -10), min(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); +} + +pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) T { var i: usize = 0; var biggest = items[0]; for (items[1..]) |item| { @@ -1211,6 +1220,15 @@ pub fn max(comptime T: type, items: []T, lessThan: fn (lhs: T, rhs: T) bool) T { return biggest; } +test "std.sort.max" { + testing.expectEqual(@as(i32, 1), max(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(i32, 5), max(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(i32, 9), max(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(i32, 1), max(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(i32, 10), max(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(i32, 3), max(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); +} + pub fn isSorted(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) bool { var i: usize = 1; while (i < items.len) : (i += 1) { -- cgit v1.2.3 From 0159fa284a54d25440899b6d8d84ac0a1e424a7f Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Wed, 4 Dec 2019 18:10:20 +0100 Subject: Make std.sort.min and std.sort.max return ?T --- lib/std/sort.zig | 38 ++++++++++++++++++++++++-------------- 1 file changed, 24 insertions(+), 14 deletions(-) (limited to 'lib') diff --git a/lib/std/sort.zig b/lib/std/sort.zig index 4913fd8f78..7c0e787562 100644 --- a/lib/std/sort.zig +++ b/lib/std/sort.zig @@ -1189,7 +1189,11 @@ fn fuzzTest(rng: *std.rand.Random) void { } } -pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) T { +pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { + if (items.len == 0) { + return null; + } + var i: usize = 0; var smallest = items[0]; for (items[1..]) |item| { @@ -1201,15 +1205,20 @@ pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) boo } test "std.sort.min" { - testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{1}, asc(i32))); - testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); - testing.expectEqual(@as(i32, 2), min(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); - testing.expectEqual(@as(i32, 1), min(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); - testing.expectEqual(@as(i32, -10), min(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); - testing.expectEqual(@as(i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); + testing.expectEqual(@as(?i32, null), min(i32, &[_]i32{}, asc(i32))); + testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(?i32, 2), min(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(?i32, 1), min(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(?i32, -10), min(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(?i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); } -pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) T { +pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { + if (items.len == 0) { + return null; + } + var i: usize = 0; var biggest = items[0]; for (items[1..]) |item| { @@ -1221,12 +1230,13 @@ pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) boo } test "std.sort.max" { - testing.expectEqual(@as(i32, 1), max(i32, &[_]i32{1}, asc(i32))); - testing.expectEqual(@as(i32, 5), max(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); - testing.expectEqual(@as(i32, 9), max(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); - testing.expectEqual(@as(i32, 1), max(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); - testing.expectEqual(@as(i32, 10), max(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); - testing.expectEqual(@as(i32, 3), max(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); + testing.expectEqual(@as(?i32, null), max(i32, &[_]i32{}, asc(i32))); + testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(?i32, 5), max(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(?i32, 9), max(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(?i32, 1), max(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(?i32, 10), max(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(?i32, 3), max(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); } pub fn isSorted(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) bool { -- cgit v1.2.3 From 841a37ab597d3075c1cb15dc5280e04b48eafa27 Mon Sep 17 00:00:00 2001 From: Robin Voetter Date: Wed, 4 Dec 2019 18:20:55 +0100 Subject: Add std.sort.argMax and std.sort.argMin --- lib/std/sort.zig | 50 ++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/std/sort.zig b/lib/std/sort.zig index 7c0e787562..9fa7803cba 100644 --- a/lib/std/sort.zig +++ b/lib/std/sort.zig @@ -1189,19 +1189,36 @@ fn fuzzTest(rng: *std.rand.Random) void { } } -pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { +pub fn argMin(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?usize { if (items.len == 0) { return null; } - var i: usize = 0; var smallest = items[0]; - for (items[1..]) |item| { + var smallest_index: usize = 0; + for (items[1..]) |item, i| { if (lessThan(item, smallest)) { smallest = item; + smallest_index = i + 1; } } - return smallest; + + return smallest_index; +} + +test "std.sort.argMin" { + testing.expectEqual(@as(?usize, null), argMin(i32, &[_]i32{}, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMin(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(?usize, 3), argMin(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); +} + +pub fn min(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { + const i = argMin(T, items, lessThan) orelse return null; + return items[i]; } test "std.sort.min" { @@ -1214,19 +1231,36 @@ test "std.sort.min" { testing.expectEqual(@as(?i32, 7), min(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); } -pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { +pub fn argMax(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?usize { if (items.len == 0) { return null; } - var i: usize = 0; var biggest = items[0]; - for (items[1..]) |item| { + var biggest_index: usize = 0; + for (items[1..]) |item, i| { if (lessThan(biggest, item)) { biggest = item; + biggest_index = i + 1; } } - return biggest; + + return biggest_index; +} + +test "std.sort.argMax" { + testing.expectEqual(@as(?usize, null), argMax(i32, &[_]i32{}, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{1}, asc(i32))); + testing.expectEqual(@as(?usize, 4), argMax(i32, &[_]i32{ 1, 2, 3, 4, 5 }, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 9, 3, 8, 2, 5 }, asc(i32))); + testing.expectEqual(@as(?usize, 0), argMax(i32, &[_]i32{ 1, 1, 1, 1, 1 }, asc(i32))); + testing.expectEqual(@as(?usize, 2), argMax(i32, &[_]i32{ -10, 1, 10 }, asc(i32))); + testing.expectEqual(@as(?usize, 1), argMax(i32, &[_]i32{ 6, 3, 5, 7, 6 }, desc(i32))); +} + +pub fn max(comptime T: type, items: []const T, lessThan: fn (lhs: T, rhs: T) bool) ?T { + const i = argMax(T, items, lessThan) orelse return null; + return items[i]; } test "std.sort.max" { -- cgit v1.2.3