Sorting

const std = @import("std");
const print = std.debug.print;

// Sorting always uses a callback function that compares
// two values and returns true if the first is less than
// the second. Let’s define one that compares two
// strings by length.
fn byLen(
    _: void,
    lhs: []const u8,
    rhs: []const u8,
) bool {
    return lhs.len < rhs.len;
}

// The first argument is a “context”, which can be used
// to parameterize the function.
fn byBytes(
    ascending: bool,
    lhs: []const u8,
    rhs: []const u8,
) bool {
    // std.mem.lessThan compares two slices
    // byte-by-byte. For simple cases, that gives us
    // alphabetical order.
    return if (ascending)
        std.mem.lessThan(u8, lhs, rhs)
    else
        std.mem.lessThan(u8, rhs, lhs);
}

pub fn main() void {
    var names: [10][]const u8 = .{
        "Olivia",
        "Amelia",
        "Isla",
        "Poppy",
        "Freya",
        "Ivy",
        "Bonnie",
        "Lottie",
        "Harper",
        "Lily",
    };
    const ns: [][]const u8 = &names;

    // std.sort.pdq implements pattern-defeating
    // quicksort. Its arguments are the element type,
    // the slice, the context, and the callback
    // function.
    //
    // {} is a value of type 'void'.
    printNames("original:", ns);
    std.sort.pdq([]const u8, ns, true, byBytes);
    printNames("sorted ascending:", ns);
    std.sort.pdq([]const u8, ns, false, byBytes);
    printNames("sorted descending:", ns);
    std.sort.pdq([]const u8, ns, {}, byLen);
    printNames("sorted by length:", ns);
}

fn printNames(
    label: []const u8,
    ns: [][]const u8,
) void {
    print("{s}", .{label});
    for (ns) |n|
        print("\n    {s}", .{n});
    print("\n", .{});
}

const std = @import("std");
const print = std.debug.print;

pub fn main() void {
    var integers: [10]u64 = .{
        1, 5, 3, 9, 8, 0, 2, 4, 7, 6,
    };
    const is: []u64 = ℤ

    // We can use std.sort.asc and std.sort.desc to
    // create callback functions.
    printIntegers("original:     ", is);
    std.sort.pdq(u64, is, {}, std.sort.asc(u64));
    printIntegers("sorted (asc): ", is);
    std.sort.pdq(u64, is, {}, std.sort.desc(u64));
    printIntegers("sorted (desc):", is);
}

fn printIntegers(label: []const u8, is: []u64) void {
    print("{s}", .{label});
    for (is) |i|
        print(" {}", .{i});
    print("\n", .{});
}

const std = @import("std");
const print = std.debug.print;

const User = struct {
    name: []const u8,
    is_admin: bool,

    fn regular(name: []const u8) User {
        return .{
            .name = name,
            .is_admin = false,
        };
    }
    fn admin(name: []const u8) User {
        return .{
            .name = name,
            .is_admin = true,
        };
    }

    // We can add comparison functions to the type
    // itself.
    fn byName(_: void, lhs: User, rhs: User) bool {
        return std.mem.lessThan(u8, lhs.name, rhs.name);
    }
    fn adminsFirst(_: void, lhs: User, rhs: User) bool {
        return lhs.is_admin and !rhs.is_admin;
    }
};

pub fn main() void {
    // We’ll create four users and sort them by name,
    // then sort again to put admin users first.
    var users: [4]User = .{
        User.regular("olivia"),
        User.regular("amelia"),
        User.regular("isla"),
        User.admin("poppy"),
    };
    const us: []User = &users;

    // Notice in the output that sorting with
    // adminsFirst left the non-admin users sorted
    // alphabetically -- that’s because we’re using
    // std.sort.block, which is a “stable sort”.
    //
    // std.sort.pdq is not guaranteed to be stable.
    printUsers("original:      ", us);
    std.sort.block(User, us, {}, User.byName);
    printUsers("sorted by name:", us);
    std.sort.block(User, us, {}, User.adminsFirst);
    printUsers("admins first:  ", us);
}

fn printUsers(
    label: []const u8,
    us: []User,
) void {
    print("{s}", .{label});
    for (us) |u|
        print(" {s}", .{u.name});
    print("\n", .{});
}

const std = @import("std");
const print = std.debug.print;
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;

const asc = std.sort.asc(f64);

// std.sort.isSorted returns true if a slice is sorted.
test "isSorted" {
    var floats: [10]f64 = .{
        0.5, 2.5, 1.5, 4.5, 4, 0, 1, 2, 3.5, 3,
    };
    const fs: []f64 = &floats;
    try expect(!std.sort.isSorted(f64, fs, {}, asc));
    std.sort.pdq(f64, fs, {}, asc);
    try expect(std.sort.isSorted(f64, fs, {}, asc));
}

// std.sort.min and std.sort.max find the minimum and
// maximum of a list.
test "min and max" {
    const min = std.sort.min;
    const max = std.sort.max;

    var floats: [10]f64 = .{
        0.5, 2.5, 1.5, 4.5, 4, 0, 1, 2, 3.5, 3,
    };
    const fs: []f64 = &floats;
    try expect(min(f64, fs, {}, asc) == 0);
    try expect(max(f64, fs, {}, asc) == 4.5);

    // The result is an [optional](optionals.html) value.
    const empty: []f64 = floats[0..0];
    try expect(min(f64, empty, {}, asc) == null);
    try expect(max(f64, empty, {}, asc) == null);
}

// std.sort.binarySearch searches for an element in a
// sorted slice.
test "binarySearch" {
    const binarySearch = std.sort.binarySearch;
    var floats: [10]f64 = .{
        0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5,
    };
    const fs: []f64 = &floats;

    var target: f64 = 2.5;
    var index = binarySearch(f64, fs, target, order);
    try expect(index != null and fs[index.?] == 2.5);

    target = 5.5;
    index = binarySearch(f64, fs, target, order);
    try expect(index == null);
}

// The callback for binarySearch returns std.math.Order.
// For numbers, we can use the std.math.order function.
fn order(context: f64, item: f64) std.math.Order {
    return std.math.order(context, item);
}