aboutsummaryrefslogtreecommitdiff
path: root/lib/std/sort.zig
AgeCommit message (Collapse)Author
2024-09-23`std.equalRange`: Compute lower and upper bounds simultaneouslyLucas Santos
The current implementation of `equalRange` just calls `lowerRange` and `upperRange`, but a lot of the work done by these two functions can be shared. Specifically, each iteration gives information about whether the lower bound or the upper bound can be tightened. This leads to fewer iterations and, since there is one comparison per iteration, fewer comparisons. Implementation adapted from [GCC](https://github.com/gcc-mirror/gcc/blob/519ec1cfe9d2c6a1d06709c52cb103508d2c42a7/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2063). This sample demonstrates the difference between the current implementation and mine: ```zig fn S(comptime T: type) type { return struct { needle: T, count: *usize, pub fn order(context: @This(), item: T) std.math.Order { context.count.* += 1; return std.math.order(item, context.needle); } pub fn orderLength(context: @This(), item: []const u8) std.math.Order { context.count.* += 1; return std.math.order(item.len, context.needle); } }; } pub fn main() !void { var count: usize = 0; try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{}, S(i32){ .needle = 0, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 0, 0 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 0, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 0, 1 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 2, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 2, 2 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 5, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 2, 3 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 8, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 5, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 64, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 6, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 16, 32, 64 }, S(i32){ .needle = 100, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 2, 6 }, equalRange(i32, &[_]i32{ 2, 4, 8, 8, 8, 8, 15, 22 }, S(i32){ .needle = 8, .count = &count }, S(i32).order)); try std.testing.expectEqual(.{ 2, 2 }, equalRange(u32, &[_]u32{ 2, 4, 8, 16, 32, 64 }, S(u32){ .needle = 5, .count = &count }, S(u32).order)); try std.testing.expectEqual(.{ 1, 1 }, equalRange(f32, &[_]f32{ -54.2, -26.7, 0.0, 56.55, 100.1, 322.0 }, S(f32){ .needle = -33.4, .count = &count }, S(f32).order)); try std.testing.expectEqual(.{ 3, 5 }, equalRange( []const u8, &[_][]const u8{ "Mars", "Venus", "Earth", "Saturn", "Uranus", "Mercury", "Jupiter", "Neptune" }, S(usize){ .needle = 6, .count = &count }, S(usize).orderLength, )); std.debug.print("Count: {}\n", .{count}); } ``` For each comparison, we bump the count. With the current implementation, we get 57 comparisons. With mine, we get 43. With contributions from @Olvilock. This is my second attempt at this, since I messed up the [first one](https://github.com/ziglang/zig/pull/21290).
2024-09-16std: Restore conventional `compareFn` behavior for `binarySearch`Jay Petacat
PR #20927 made some improvements to the `binarySearch` API, but one change I found surprising was the relationship between the left-hand and right-hand parameters of `compareFn` was inverted. This is different from how comparison functions typically behave, both in other parts of Zig (e.g. `std.math.order`) and in other languages (e.g. C's `bsearch`). Unless a strong reason can be identified and documented for doing otherwise, I think it'll be better to stick with convention. While writing this patch and changing things back to the way they were, the predicates of `lowerBound` and `upperBound` seemed to be the only areas that benefited from the inversion. I don't think that benefit is worth the cost, personally. Calling `Order.invert()` in the predicates accomplishes the same goal.
2024-08-04std.sort: Remove key argument from binary-search-like functions (#20927)Fri3dNstuff
closes #20110
2024-07-23add std.testing.random_seedAndrew Kelley
closes #17609
2024-06-20std: fuzz test sort stability (#20284)Alex Kladov
Stability of std sort was undertested before this change. Add a fuzz test for more confidence. Specifically, we used to have a single example test that used an array of eight elements. That ends up exercising only a tiny fraction of sorting logic, as it hits a hard-coded sorting network due to small size.
2024-05-28std: Avoid overflowing in the midpoint calculation in upperBoundT. M
2024-03-21std: promote tests to doctestsAndrew Kelley
Now these show up as "example usage" in generated documentation.
2024-02-08Replace std.rand references with std.Randome4m2
2024-02-07Changes to lowerBound/upperBound/equalRangeJohn Schmidt
The old definitions had some problems: - In `lowerBound`, the `lhs` (left hand side) argument was passed on the right hand side. - In `upperBound`, the `greaterThan` function needed to return `greaterThanOrEqual` for the function work, so either the name or the implementation is incorrect. To fix both problems, define the functions in terms of a `lessThan` function that returns `lhs < rhs`. The is more consistent with the rest of `sort.zig` and it's also how C++ implements lower/upperBound (1)(2). (1) https://en.cppreference.com/w/cpp/algorithm/lower_bound (2) https://en.cppreference.com/w/cpp/algorithm/upper_bound - Rewrite doc comments. - Add a couple of more test cases. - Add docstring for std.sort.binarySearch
2024-02-07Add lowerBound/upperBound/equalRangeCraig O'Connor
Authored by https://github.com/CraigglesO Original Discussion: #9890 I already had to create these functions and test cases for my own project so I decided to contribute to the main code base in hopes it would simplify my own. I realize this is still under discussion but this was a trivial amount of work so I thought I could help nudge the discussion towards a decision. Why add these to the standard library To better illustrate and solidify their value, the standard library's "sort" module already contains several binary search queries on arrays such as binarySearch and internal functions binaryFirst & binaryLast. A final example of its use: the Zig code itself created and used a bounding search in the linker. There still lacks the ability to allow the programmer themselves to search the array for a rough position and find an index to read &/ update. Adding these functions would also help to complement dynamic structures like ArrayList with it's insert function. Example Case I'm building a library in Zig for GIS geometry. To store points, lines, and polygons each 3D point is first translated into what's called an S2CellId. This is a fancy way of saying I reduce the Earth's spherical data into a 1D Hilbert Curve with cm precision. This gives me 2 convenient truths: Hilbert Curves have locality of reference. All points can be stored inside a 1D array Since lowerBound and upperBound to find data inside a radius for instance. If I'm interested in a specific cell at a specific "level" and want to iterate all duplicates, equalRange is a best fit.
2023-11-19lib: correct unnecessary uses of 'var'mlugg
2023-10-23x86_64: implement enough to pass unicode testsJacob Young
* implement vector comparison * implement reduce for bool vectors * fix `@memcpy` bug * enable passing std tests
2023-10-22Revert "Revert "Merge pull request #17637 from jacobly0/x86_64-test-std""Jacob Young
This reverts commit 6f0198cadbe29294f2bf3153a27beebd64377566.
2023-10-22Revert "Merge pull request #17637 from jacobly0/x86_64-test-std"Andrew Kelley
This reverts commit 0c99ba1eab63865592bb084feb271cd4e4b0357e, reversing changes made to 5f92b070bf284f1493b1b5d433dd3adde2f46727. This caused a CI failure when it landed in master branch due to a 128-bit `@byteSwap` in std.mem.
2023-10-21x86_64: disable failing tests, enable test-std testingJacob Young
2023-10-08std: add unstable sorting to array hash mapsAndrew Kelley
closes #17426
2023-06-27improve documentation of std.sort.*Context functions (#16145)yujiri8
2023-06-26std.sort.block: add safety check for lessThan return valueAli Chraghi
2023-06-22[heapsort] Protect against integer overflowNiles Salter
(Firstly, I changed `n` to `b`, as that is less confusing. It's not a length, it's a right boundary.) The invariant maintained is `cur < b`. In the worst case `2*cur + 1` results in a maximum of `2b`. Since `2b` is not guaranteed to be lower than `maxInt`, we have to add one overflow check to `siftDown` to make sure we avoid undefined behavior. LLVM also seems to have a nicer time compiling this version of the function. It is about 2x faster in my tests (I think LLVM was stumped by the `child += @intFromBool` line), and adding/removing the overflow check has a negligible performance difference on my machine. Of course, we could check `2b <= maxInt` in the parent function, and dispatch to a version of the function without the overflow check in the common case, but that probably is not worth the code size just to eliminate a single instruction.
2023-06-19all: zig fmt and rename "@XToY" to "@YFromX"Eric Joldasov
Signed-off-by: Eric Joldasov <bratishkaerik@getgoogleoff.me>
2023-06-13Fix pdqSort+heapSort for ranges besides 0..len (#15982)Niles Salter
2023-05-23std.sort: add pdqsort and heapsortAli Chraghi
2023-05-17Document the sorting order in `std.sort`.IntegratedQuantum
2023-04-28update codebase to use `@memset` and `@memcpy`Andrew Kelley
2023-03-21naming: mid for index and mid_item for itemRoman FroĊ‚ow
2023-02-21Relax `std.sort.binarySearch` requirementsAlexis Brodeur
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.
2023-02-18update std lib and compiler sources to new for loop syntaxAndrew Kelley
2022-03-10std: add sort method to ArrayHashMap and MultiArrayListAndrew Kelley
This also adds `std.sort.sortContext` and `std.sort.insertionSortContext` which are more advanced methods that allow overriding the `swap` method. The former calls the latter for now because reworking the main sort implementation is a big task that can be done later without any changes to the API.
2021-10-27std.rand: Refactor `Random` interfaceOminitay
These changes have been made to resolve issue #10037. The `Random` interface was implemented in such a way that causes significant slowdown when calling the `fill` function of the rng used. The `Random` interface is no longer stored in a field of the rng, and is instead returned by the child function `random()` of the rng. This avoids the performance issues caused by the interface.
2021-10-04migrate from `std.Target.current` to `@import("builtin").target`Andrew Kelley
closes #9388 closes #9321
2021-08-24remove redundant license headers from zig standard libraryAndrew Kelley
We already have a LICENSE file that covers the Zig Standard Library. We no longer need to remind everyone that the license is MIT in every single file. Previously this was introduced to clarify the situation for a fork of Zig that made Zig's LICENSE file harder to find, and replaced it with their own license that required annual payments to their company. However that fork now appears to be dead. So there is no need to reinforce the copyright notice in every single file.
2021-06-21fix code broken from previous commitJacob G-W
2021-05-08Merge remote-tracking branch 'origin/master' into stage2-whole-file-astgenAndrew Kelley
Conflicts: * doc/langref.html.in * lib/std/enums.zig * lib/std/fmt.zig * lib/std/hash/auto_hash.zig * lib/std/math.zig * lib/std/mem.zig * lib/std/meta.zig * test/behavior/alignof.zig * test/behavior/bitcast.zig * test/behavior/bugs/1421.zig * test/behavior/cast.zig * test/behavior/ptrcast.zig * test/behavior/type_info.zig * test/behavior/vector.zig Master branch added `try` to a bunch of testing function calls, and some lines also had changed how to refer to the native architecture and other `@import("builtin")` stuff.
2021-05-08std: update usage of std.testingVeikka Tuominen
2021-04-15std: change `@import("builtin")` to `std.builtin`Andrew Kelley
2021-01-06Fix example code in comments for asc and descAndreas Karlsson
2020-12-31Year++Frank Denis
2020-08-20add license header to all std lib filesAndrew Kelley
add SPDX license identifier copyright ownership is zig contributors
2020-07-11run zig fmt on std lib and self hostedVexu
2020-06-08std.sort: give comparator functions a context parameterAndrew Kelley
2020-04-09sort.binarySearch: Remove unneeded edge case checkYuri Pieters
2020-04-09sort.binarySearch: test for regresson of #4980Yuri Pieters
2020-04-09sort.binarySearch: fix integer underflow (#4980)Yuri Pieters
When the key was smaller than any value in the array, an error was ocurring with the mid being zero and having 1 subtracted from it.
2020-03-30std lib API deprecations for the upcoming 0.6.0 releaseAndrew Kelley
See #3811
2020-02-12Switch a bunch of FBA to use testing.allocatorBenjamin Feng
2020-02-03Change API for binarySearch fnLemonBoy
2020-01-31stdlib: Add binary search functionLemonBoy
2020-01-28std.sort.insertionSort: remove superfluous blockAndrew Kelley
2019-12-04Add std.sort.argMax and std.sort.argMinRobin Voetter
2019-12-04Make std.sort.min and std.sort.max return ?TRobin Voetter
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-29 04:48:07 +0000