571 lines
18 KiB
Zig
571 lines
18 KiB
Zig
const std = @import("std");
|
||
const mem = std.mem;
|
||
const Allocator = std.mem.Allocator;
|
||
const ArrayList = std.ArrayList;
|
||
|
||
// Only covers ISO-8859-1 accented characters plus, for consistency, Ÿ
|
||
const UC_ACCENTS = [_][]const u8{ "ÀÁÂÃÄÅ", "Ç", "ÈÉÊË", "ÌÍÎÏ", "Ñ", "ÒÓÔÕÖØ", "ÙÚÛÜ", "ÝŸ" };
|
||
const LC_ACCENTS = [_][]const u8{ "àáâãäå", "ç", "èéêë", "ìíîï", "ñ", "òóôõöø", "ùúûü", "ýÿ" };
|
||
const UC_UNACCENTS = [_][]const u8{ "A", "C", "E", "I", "N", "O", "U", "Y" };
|
||
const LC_UNACCENTS = [_][]const u8{ "a", "c", "e", "i", "n", "o", "u", "y" };
|
||
|
||
// Only the more common ligatures
|
||
const UC_LIGATURES = [_][]const u8{ "Æ", "IJ", "Œ" };
|
||
const LC_LIGATURES = [_][]const u8{ "æ", "ij", "œ" };
|
||
const UC_SEPARATES = [_][]const u8{ "AE", "IJ", "OE" };
|
||
const LC_SEPARATES = [_][]const u8{ "ae", "ij", "oe" };
|
||
|
||
// Miscellaneous replacements
|
||
const MISC_LETTERS = [_][]const u8{ "ß", "ſ", "ʒ" };
|
||
const MISC_REPLACEMENTS = [_][]const u8{ "ss", "s", "s" };
|
||
|
||
// Remove leading spaces
|
||
fn leftTrim(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var i: usize = 0;
|
||
while (i < text.len and text[i] == ' ') : (i += 1) {}
|
||
return allocator.dupe(u8, text[i..]);
|
||
}
|
||
|
||
// Replace multiple spaces with a single space
|
||
fn replaceSpaces(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
|
||
var i: usize = 0;
|
||
var inSpaces = false;
|
||
while (i < text.len) : (i += 1) {
|
||
if (text[i] == ' ') {
|
||
if (!inSpaces) {
|
||
try result.append(' ');
|
||
inSpaces = true;
|
||
}
|
||
} else {
|
||
try result.append(text[i]);
|
||
inSpaces = false;
|
||
}
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Replace whitespace with a single space
|
||
fn replaceWhitespace(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
|
||
var i: usize = 0;
|
||
var inWhitespace = false;
|
||
while (i < text.len) : (i += 1) {
|
||
if (std.ascii.isWhitespace(text[i])) {
|
||
if (!inWhitespace) {
|
||
try result.append(' ');
|
||
inWhitespace = true;
|
||
}
|
||
} else {
|
||
try result.append(text[i]);
|
||
inWhitespace = false;
|
||
}
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Display strings including whitespace as if the latter were literal characters
|
||
fn toDisplayString(allocator: Allocator, text: []const u8) ![]u8 {
|
||
const whitespace_1 = [_][]const u8{ "\t", "\n", "\x0B", "\x0C", "\r" };
|
||
const whitespace_2 = [_][]const u8{ "\\t", "\\n", "\\u000b", "\\u000c", "\\r" };
|
||
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
|
||
var i: usize = 0;
|
||
while (i < text.len) : (i += 1) {
|
||
var replaced = false;
|
||
for (whitespace_1, 0..) |ws, j| {
|
||
if (i + ws.len <= text.len and mem.eql(u8, text[i..i+ws.len], ws)) {
|
||
try result.appendSlice(whitespace_2[j]);
|
||
i += ws.len - 1;
|
||
replaced = true;
|
||
break;
|
||
}
|
||
}
|
||
|
||
if (!replaced) {
|
||
try result.append(text[i]);
|
||
}
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Transform the string into lower case
|
||
fn toLowerCase(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = try allocator.alloc(u8, text.len);
|
||
errdefer allocator.free(result);
|
||
|
||
for (text, 0..) |c, i| {
|
||
result[i] = std.ascii.toLower(c);
|
||
}
|
||
|
||
return result;
|
||
}
|
||
|
||
// Pad each numeric character with leading zeros to a total length of 20
|
||
fn zeroPadding(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
|
||
var i: usize = 0;
|
||
while (i < text.len) {
|
||
if (std.ascii.isDigit(text[i]) or (text[i] == '-' and i + 1 < text.len and std.ascii.isDigit(text[i+1]))) {
|
||
const start = i;
|
||
if (text[i] == '-') {
|
||
i += 1;
|
||
}
|
||
while (i < text.len and std.ascii.isDigit(text[i])) : (i += 1) {}
|
||
|
||
const numStr = text[start..i];
|
||
const padding = if (numStr.len < 20) 20 - numStr.len else 0;
|
||
|
||
for (0..padding) |_| {
|
||
try result.append('0');
|
||
}
|
||
try result.appendSlice(numStr);
|
||
} else {
|
||
try result.append(text[i]);
|
||
i += 1;
|
||
}
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
fn removeTitle(allocator: Allocator, text: []const u8) ![]u8 {
|
||
if (text.len >= 4 and mem.eql(u8, text[0..4], "The ")) {
|
||
return allocator.dupe(u8, text[4..]);
|
||
} else if (text.len >= 3 and mem.eql(u8, text[0..3], "An ")) {
|
||
return allocator.dupe(u8, text[3..]);
|
||
} else if (text.len >= 2 and mem.eql(u8, text[0..2], "A ")) {
|
||
return allocator.dupe(u8, text[2..]);
|
||
} else {
|
||
return allocator.dupe(u8, text);
|
||
}
|
||
}
|
||
|
||
// Replace accented letters with their unaccented equivalent
|
||
fn replaceAccents(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
|
||
var i: usize = 0;
|
||
while (i < text.len) {
|
||
// Handle UTF-8 characters
|
||
var char: [4]u8 = undefined;
|
||
var char_len: usize = 0;
|
||
|
||
if ((text[i] & 0x80) == 0) {
|
||
// ASCII character
|
||
try result.append(text[i]);
|
||
i += 1;
|
||
continue;
|
||
}
|
||
|
||
// Extract UTF-8 character
|
||
if ((text[i] & 0xE0) == 0xC0) {
|
||
char_len = 2;
|
||
} else if ((text[i] & 0xF0) == 0xE0) {
|
||
char_len = 3;
|
||
} else if ((text[i] & 0xF8) == 0xF0) {
|
||
char_len = 4;
|
||
} else {
|
||
// Invalid UTF-8, just copy
|
||
try result.append(text[i]);
|
||
i += 1;
|
||
continue;
|
||
}
|
||
|
||
if (i + char_len > text.len) {
|
||
// Incomplete UTF-8 sequence
|
||
try result.append(text[i]);
|
||
i += 1;
|
||
continue;
|
||
}
|
||
|
||
@memcpy(char[0..char_len], text[i..i+char_len]);
|
||
|
||
var replaced = false;
|
||
const charSlice = char[0..char_len];
|
||
|
||
for (UC_ACCENTS, 0..) |accents, j| {
|
||
if (containsUtf8Char(accents, charSlice)) {
|
||
try result.appendSlice(UC_UNACCENTS[j]);
|
||
replaced = true;
|
||
break;
|
||
}
|
||
}
|
||
|
||
if (!replaced) {
|
||
for (LC_ACCENTS, 0..) |accents, j| {
|
||
if (containsUtf8Char(accents, charSlice)) {
|
||
try result.appendSlice(LC_UNACCENTS[j]);
|
||
replaced = true;
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
if (!replaced) {
|
||
try result.appendSlice(charSlice);
|
||
}
|
||
|
||
i += char_len;
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Helper function to check if a UTF-8 string contains a character
|
||
fn containsUtf8Char(haystack: []const u8, needle: []const u8) bool {
|
||
var i: usize = 0;
|
||
while (i < haystack.len) {
|
||
const char_len = utf8CharLen(haystack[i]);
|
||
if (i + char_len <= haystack.len and mem.eql(u8, haystack[i..i+char_len], needle)) {
|
||
return true;
|
||
}
|
||
i += char_len;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
// Helper function to get UTF-8 character length
|
||
fn utf8CharLen(first_byte: u8) usize {
|
||
if ((first_byte & 0x80) == 0) return 1;
|
||
if ((first_byte & 0xE0) == 0xC0) return 2;
|
||
if ((first_byte & 0xF0) == 0xE0) return 3;
|
||
if ((first_byte & 0xF8) == 0xF0) return 4;
|
||
return 1; // invalid UTF-8, treat as single byte
|
||
}
|
||
|
||
// Replace ligatures with separated letters
|
||
fn replaceLigatures(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
try result.appendSlice(text);
|
||
|
||
for (UC_LIGATURES, 0..) |ligature, i| {
|
||
var newResult = ArrayList(u8).init(allocator);
|
||
defer newResult.deinit();
|
||
|
||
var j: usize = 0;
|
||
while (j < result.items.len) {
|
||
const char_len = utf8CharLen(result.items[j]);
|
||
if (j + char_len <= result.items.len and isUtf8Char(result.items[j..j+char_len], ligature)) {
|
||
try newResult.appendSlice(UC_SEPARATES[i]);
|
||
j += char_len;
|
||
} else {
|
||
try newResult.append(result.items[j]);
|
||
j += 1;
|
||
}
|
||
}
|
||
|
||
result.clearAndFree();
|
||
try result.appendSlice(newResult.items);
|
||
}
|
||
|
||
for (LC_LIGATURES, 0..) |ligature, i| {
|
||
var newResult = ArrayList(u8).init(allocator);
|
||
defer newResult.deinit();
|
||
|
||
var j: usize = 0;
|
||
while (j < result.items.len) {
|
||
const char_len = utf8CharLen(result.items[j]);
|
||
if (j + char_len <= result.items.len and isUtf8Char(result.items[j..j+char_len], ligature)) {
|
||
try newResult.appendSlice(LC_SEPARATES[i]);
|
||
j += char_len;
|
||
} else {
|
||
try newResult.append(result.items[j]);
|
||
j += 1;
|
||
}
|
||
}
|
||
|
||
result.clearAndFree();
|
||
try result.appendSlice(newResult.items);
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Helper function to compare UTF-8 characters
|
||
fn isUtf8Char(a: []const u8, b: []const u8) bool {
|
||
return mem.eql(u8, a, b);
|
||
}
|
||
|
||
// Replace miscellaneous letters with their equivalent replacements
|
||
fn replaceCharacters(allocator: Allocator, text: []const u8) ![]u8 {
|
||
var result = ArrayList(u8).init(allocator);
|
||
defer result.deinit();
|
||
try result.appendSlice(text);
|
||
|
||
for (MISC_LETTERS, 0..) |letter, i| {
|
||
var newResult = ArrayList(u8).init(allocator);
|
||
defer newResult.deinit();
|
||
|
||
var j: usize = 0;
|
||
while (j < result.items.len) {
|
||
const char_len = utf8CharLen(result.items[j]);
|
||
if (j + char_len <= result.items.len and isUtf8Char(result.items[j..j+char_len], letter)) {
|
||
try newResult.appendSlice(MISC_REPLACEMENTS[i]);
|
||
j += char_len;
|
||
} else {
|
||
try newResult.append(result.items[j]);
|
||
j += 1;
|
||
}
|
||
}
|
||
|
||
result.clearAndFree();
|
||
try result.appendSlice(newResult.items);
|
||
}
|
||
|
||
return result.toOwnedSlice();
|
||
}
|
||
|
||
// Custom context for sort comparators
|
||
const SortContext = struct {
|
||
allocator: Allocator,
|
||
};
|
||
|
||
pub fn main() !void {
|
||
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
||
defer _ = gpa.deinit();
|
||
const allocator = gpa.allocator();
|
||
|
||
const stdout = std.io.getStdOut().writer();
|
||
try stdout.print("The 9 string lists, sorted 'naturally':\n", .{});
|
||
|
||
var s1 = ArrayList([]const u8).init(allocator);
|
||
defer s1.deinit();
|
||
try s1.append("ignore leading spaces: 2-2");
|
||
try s1.append(" ignore leading spaces: 2-1");
|
||
try s1.append(" ignore leading spaces: 2+0");
|
||
try s1.append(" ignore leading spaces: 2+1");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using leftTrim
|
||
const ctx1 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s1.items, ctx1, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = leftTrim(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = leftTrim(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s1.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s2 = ArrayList([]const u8).init(allocator);
|
||
defer s2.deinit();
|
||
try s2.append("ignore m.a.s spaces: 2-2");
|
||
try s2.append("ignore m.a.s spaces: 2-1");
|
||
try s2.append("ignore m.a.s spaces: 2+0");
|
||
try s2.append("ignore m.a.s spaces: 2+1");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using replaceSpaces
|
||
const ctx2 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s2.items, ctx2, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = replaceSpaces(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = replaceSpaces(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s2.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s3 = ArrayList([]const u8).init(allocator);
|
||
defer s3.deinit();
|
||
try s3.append("Equiv. spaces: 3-3");
|
||
try s3.append("Equiv.\rspaces: 3-2");
|
||
try s3.append("Equiv.\x0Cspaces: 3-1");
|
||
try s3.append("Equiv.\x0Bspaces: 3+0");
|
||
try s3.append("Equiv.\nspaces: 3+1");
|
||
try s3.append("Equiv.\tspaces: 3+2");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using replaceWhitespace
|
||
const ctx3 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s3.items, ctx3, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = replaceWhitespace(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = replaceWhitespace(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s3.items) |s| {
|
||
const displayStr = try toDisplayString(allocator, s);
|
||
defer allocator.free(displayStr);
|
||
try stdout.print("{s}\n", .{displayStr});
|
||
}
|
||
|
||
var s4 = ArrayList([]const u8).init(allocator);
|
||
defer s4.deinit();
|
||
try s4.append("cASE INDEPENENT: 3-2");
|
||
try s4.append("caSE INDEPENENT: 3-1");
|
||
try s4.append("casE INDEPENENT: 3+0");
|
||
try s4.append("case INDEPENENT: 3+1");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using toLowerCase
|
||
const ctx4 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s4.items, ctx4, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = toLowerCase(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = toLowerCase(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s4.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s5 = ArrayList([]const u8).init(allocator);
|
||
defer s5.deinit();
|
||
try s5.append("foo100bar99baz0.txt");
|
||
try s5.append("foo100bar10baz0.txt");
|
||
try s5.append("foo1000bar99baz10.txt");
|
||
try s5.append("foo1000bar99baz9.txt");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using zeroPadding
|
||
const ctx5 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s5.items, ctx5, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = zeroPadding(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = zeroPadding(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s5.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s6 = ArrayList([]const u8).init(allocator);
|
||
defer s6.deinit();
|
||
try s6.append("The Wind in the Willows");
|
||
try s6.append("The 40th step more");
|
||
try s6.append("The 39 steps");
|
||
try s6.append("Wanda");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using removeTitle
|
||
const ctx6 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s6.items, ctx6, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = removeTitle(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = removeTitle(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s6.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s7 = ArrayList([]const u8).init(allocator);
|
||
defer s7.deinit();
|
||
try s7.append("Equiv. ý accents: 2-2");
|
||
try s7.append("Equiv. Ý accents: 2-1");
|
||
try s7.append("Equiv. y accents: 2+0");
|
||
try s7.append("Equiv. Y accents: 2+1");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using replaceAccents
|
||
const ctx7 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s7.items, ctx7, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = replaceAccents(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = replaceAccents(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s7.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s8 = ArrayList([]const u8).init(allocator);
|
||
defer s8.deinit();
|
||
try s8.append("IJ ligatured ij");
|
||
try s8.append("no ligature");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using replaceLigatures
|
||
const ctx8 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s8.items, ctx8, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = replaceLigatures(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = replaceLigatures(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s8.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
|
||
var s9 = ArrayList([]const u8).init(allocator);
|
||
defer s9.deinit();
|
||
try s9.append("Start with an ʒ: 2-2");
|
||
try s9.append("Start with an ſ: 2-1");
|
||
try s9.append("Start with an ß: 2+0");
|
||
try s9.append("Start with an s: 2+1");
|
||
|
||
try stdout.print("\n", .{});
|
||
|
||
// Sort using replaceCharacters
|
||
const ctx9 = SortContext{ .allocator = allocator };
|
||
std.sort.insertion([]const u8, s9.items, ctx9, struct {
|
||
fn lessThan(ctx: SortContext, lhs: []const u8, rhs: []const u8) bool {
|
||
const l = replaceCharacters(ctx.allocator, lhs) catch return false;
|
||
defer ctx.allocator.free(l);
|
||
const r = replaceCharacters(ctx.allocator, rhs) catch return false;
|
||
defer ctx.allocator.free(r);
|
||
return mem.lessThan(u8, l, r);
|
||
}
|
||
}.lessThan);
|
||
|
||
for (s9.items) |s| {
|
||
try stdout.print("{s}\n", .{s});
|
||
}
|
||
}
|