Commit `98dd041d53`

Alexis Brodeur <brodeuralexis@gmail.com>

2022-09-03 02:56:36

Relax `std.sort.binarySearch` requirements

Forcing the key to be of the same type as the sorted items used during the search is a valid use case. There, however, exists some cases where the key and the items are of heterogeneous types, like searching for a code point in ordered ranges of code points: ```zig const CodePoint = u21; const CodePointRange = [2]CodePoint; const valid_ranges = &[_]CodePointRange{ // an ordered array of ranges }; fn orderCodePointAndRange( context: void, code_point: CodePoint, range: CodePointRange ) std.math.Order { _ = context; if (code_point < range[0]) { return .lt; } if (code_point > range[1]) { return .gt; } return .eq; } fn isValidCodePoint(code_point: CodePoint) bool { return std.sort.binarySearch( CodePointRange, code_point, valid_ranges, void, orderCodePointAndRange ) != null; } ``` It is so expected that `std.sort.binarySearch` should therefore support both homogeneous and heterogeneous keys.

master

1 parent 2737dce

Changed files (1)

lib

std

sort.zig

@@ -6,10 +6,10 @@ const math = std.math;
 
 pub fn binarySearch(
     comptime T: type,
-    key: T,
+    key: anytype,
     items: []const T,
     context: anytype,
-    comptime compareFn: fn (context: @TypeOf(context), lhs: T, rhs: T) math.Order,
+    comptime compareFn: fn (context: @TypeOf(context), key: @TypeOf(key), mid: T) math.Order,
 ) ?usize {
     var left: usize = 0;
     var right: usize = items.len;
@@ -41,35 +41,69 @@ test "binarySearch" {
     };
     try testing.expectEqual(
         @as(?usize, null),
-        binarySearch(u32, 1, &[_]u32{}, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 1), &[_]u32{}, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, 0),
-        binarySearch(u32, 1, &[_]u32{1}, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 1), &[_]u32{1}, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, null),
-        binarySearch(u32, 1, &[_]u32{0}, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 1), &[_]u32{0}, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, null),
-        binarySearch(u32, 0, &[_]u32{1}, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 0), &[_]u32{1}, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, 4),
-        binarySearch(u32, 5, &[_]u32{ 1, 2, 3, 4, 5 }, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 5), &[_]u32{ 1, 2, 3, 4, 5 }, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, 0),
-        binarySearch(u32, 2, &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.order_u32),
+        binarySearch(u32, @as(u32, 2), &[_]u32{ 2, 4, 8, 16, 32, 64 }, {}, S.order_u32),
     );
     try testing.expectEqual(
         @as(?usize, 1),
-        binarySearch(i32, -4, &[_]i32{ -7, -4, 0, 9, 10 }, {}, S.order_i32),
+        binarySearch(i32, @as(i32, -4), &[_]i32{ -7, -4, 0, 9, 10 }, {}, S.order_i32),
     );
     try testing.expectEqual(
         @as(?usize, 3),
-        binarySearch(i32, 98, &[_]i32{ -100, -25, 2, 98, 99, 100 }, {}, S.order_i32),
+        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 };
+        }
+
+        fn order(context: void, key: i32, mid: @This()) math.Order {
+            _ = context;
+
+            if (key < mid.b) {
+                return .lt;
+            }
+
+            if (key > mid.e) {
+                return .gt;
+            }
+
+            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),
     );
 }

Commit 98dd041d53

Commit `98dd041d53`