const expect_equal = std.testing.expectEqual;
const std = @import("std");

pub fn
divisible(comptime digit_type: type, comptime base: digit_type, digits: []const digit_type, comptime divisor: digit_type) digit_type
// return the remainder of digits divided by divisor
{
	const lut = comptime blk: {
		var entry: digit_type = 0;
		var tmp: [divisor]digit_type = undefined;

		@setEvalBranchQuota(10000);
		while (entry < divisor) : (entry +%= 1) {
			tmp[entry] = (entry * base) % divisor;
		}

		break :blk tmp;
	};

	var digit: usize = 0;
	var quotient: digit_type = 0;
	var tmp: digit_type = 0;

	while (digit < digits.len) : (digit +%= 1) {
		tmp = (quotient +% digits[digit]) % divisor;
		quotient = lut[tmp];
	}

	return tmp;
}

// tests

fn
t_range(comptime digit_type: type, comptime base: digit_type, comptime divisor: digit_type) !void
{
	var num: usize = 0;
	const maximum: usize = 1000000;
	while (num < maximum) : (num += 1) {
		const b2 = base * base;
		const b3 = b2 * base;
		const digits = [_]digit_type {@intCast(num / b3), @intCast(num % b3 / b2), @intCast(num % b2 / base), @intCast(num % base)};
		try expect_equal
			(@as(digit_type, @intCast(@mod(num, @as(usize, @intCast(divisor)))))
			,divisible(digit_type, base, @ptrCast(&digits), divisor));
	}
}

test "divisible by 2 in base 2"
{
	const digit_type = u8;

	const base: digit_type = 2;
	const digits_f = [_]digit_type {1, 0, 1};
	const digits_t = [_]digit_type {1, 1, 0};
	const divisor: digit_type = 2;

	try expect_equal(1, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 7 in base 2"
{
	const digit_type = u8;

	const base: digit_type = 2;
	const digits_f = [_]digit_type {1, 0, 1};
	const digits_t = [_]digit_type {1, 1, 1};
	const divisor: digit_type = 7;

	try expect_equal(5, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 7 in base 10"
{
	const digit_type = u8;

	const base: digit_type = 10;
	const digits_f = [_]digit_type {3, 1, 4, 1, 5, 9, 2, 6};
	const digits_t = [_]digit_type {3, 1, 4, 1, 5, 9, 2, 6, 5};
	const divisor: digit_type = 7;

	try expect_equal(3, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 10 in base 10"
{
	const digit_type = u8;

	const base: digit_type = 10;
	const digits_f = [_]digit_type {1, 0, 1};
	const digits_t = [_]digit_type {1, 0, 0};
	const divisor: digit_type = 10;

	try expect_equal(1, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 16 in base 16"
{
	const digit_type = u8;

	const base: digit_type = 16;
	const digits_f = [_]digit_type {1, 6, 1};
	const digits_t = [_]digit_type {1, 6, 0};
	const divisor: digit_type = 16;

	try expect_equal(1, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 1024 in base 1024"
{
	const digit_type = u32;

	const base: digit_type = 1024;
	const digits_f = [_]digit_type {1, 0, 1};// 1024² + 1
	const digits_t = [_]digit_type {1, 0, 0};// 1024²
	const divisor: digit_type = 1024;

	try expect_equal(1, divisible(digit_type, base, @ptrCast(&digits_f), divisor));
	try expect_equal(0, divisible(digit_type, base, @ptrCast(&digits_t), divisor));
}

test "divisible by 42 in base 2 (range)"
{
	const digit_type = u32;
	const base: digit_type = 2;
	const divisor: digit_type = 42;
	try t_range(digit_type, base, divisor);
}

test "divisible by 11 in base 10 (range)"
{
	const digit_type = u16;
	const base: digit_type = 10;
	const divisor: digit_type = 11;
	try t_range(digit_type, base, divisor);
}

test "divisible by 7 in base 16 (range)"
{
	const digit_type = u16;
	const base: digit_type = 16;
	const divisor: digit_type = 7;
	try t_range(digit_type, base, divisor);
}
