/* 
 * Zeller's congruence (Rust)
 * by Project Nayuki, 2022. Public domain.
 * https://www.nayuki.io/page/zellers-congruence
 */

use std::convert::TryFrom;
extern crate rand;
use rand::distributions::IndependentSample;
use rand::distributions::range::Range;


/*---- Zeller's congruence function ----*/

/**
 * Returns the day-of-week dow for the given date
 * (y, m, d) on the proleptic Gregorian calendar.
 * Values of dow are 0 = Sunday, 1 = Monday, ..., 6 = Saturday.
 * Strict values of m are 1 = January, ..., 12 = December.
 * Strict values of d start from 1.
 * The handling of months and days-of-month is lenient.
 */
pub fn day_of_week(mut y: i32, mut m: i32, mut d: i32) -> i32 {
	m = m % 4800 - 3 + 4800 * 2;
	y = y % 400 + 400 + m / 12;
	m %= 12;
	d = d % 7 + 7;
	let temp: i32 = y + y / 4 - y / 100 + y / 400;
	(temp + (m * 13 + 12) / 5 + d) % 7
}



/*---- Test suite ----*/

fn main() {
	test_simple();
	test_ascending();
	test_descending();
	test_vs_naive_randomly();
	test_lenient_extreme();
	test_lenient_randomly();
	println!("Test passed");
}


fn test_simple() {
	const CASES: &'static [(i32,i32,i32,i32)] = &[
		(-679,  9,  8, 1),
		(-657,  2,  6, 3),
		(-629,  5, 14, 2),
		(-567,  8, 25, 0),
		(-526,  7, 24, 5),
		(-316, 11, 18, 6),
		(-270,  7, 17, 1),
		(-212,  1, 25, 5),
		(-212, 11,  2, 0),
		(- 43,  7, 20, 6),
		(1619, 10, 16, 3),
		(1620, 11, 30, 1),
		(1631,  9,  3, 3),
		(1637,  2, 18, 3),
		(1653,  5, 25, 0),
		(1735,  1,  7, 5),
		(1753,  8, 28, 2),
		(1804,  6, 30, 6),
		(1810, 10,  3, 3),
		(1835,  3,  2, 1),
		(1844,  8, 14, 3),
		(1844, 12, 16, 1),
		(1899,  5, 23, 2),
		(1912, 12, 10, 2),
		(1915,  8,  2, 1),
		(1938,  6, 18, 6),
		(1945,  6,  7, 4),
		(1965,  4, 28, 3),
		(1998,  6, 18, 4),
		(1999, 12, 31, 5),
		(2000,  1,  1, 6),
		(2000,  2,  1, 2),
		(2000,  2, 29, 2),
		(2000,  3,  1, 3),
		(2001,  3,  1, 4),
		(2002,  3,  1, 5),
		(2003,  3,  1, 6),
		(2004,  3,  1, 1),
		(2071,  6, 13, 6),
		(2094,  1, 20, 3),
		(2124,  7, 26, 3),
		(2196, 10, 12, 3),
		(2213,  5,  5, 3),
		(2216,  3, 15, 5),
		(2225,  8, 26, 5),
		(2268,  9,  2, 3),
		(2306,  7, 25, 3),
		(2336,  6, 20, 6),
		(2348,  7, 16, 5),
	];
	for &(y, m, d, dow) in CASES {
		assert_eq!(dow, day_of_week(y, m, d));
	}
}


fn test_ascending() {
	let mut ymd: (i32,i32,i32) = (1600, 1, 1);
	let mut dow = 6i32;
	while ymd.0 < 2400 {
		assert_eq!(dow, day_of_week(ymd.0, ymd.1, ymd.2));
		ymd = next_date(ymd);
		dow = (dow + 1) % 7;
	}
}


fn test_descending() {
	let mut ymd: (i32,i32,i32) = (1600, 1, 1);
	let mut dow = 6i32;
	while ymd.0 > 800 {
		assert_eq!(dow, day_of_week(ymd.0, ymd.1, ymd.2));
		ymd = previous_date(ymd);
		dow = (dow - 1 + 7) % 7;
	}
}


fn test_vs_naive_randomly() {
	const TRIALS: i32 = 1000;
	let rng = &mut rand::thread_rng();
	let yeardist = Range::new(800, 2400);
	let monthdist = Range::new(1, 13);
	for _ in 0 .. TRIALS {
		let y: i32 = yeardist.ind_sample(rng);
		let m: i32 = monthdist.ind_sample(rng);
		let daydist = Range::new(1, month_length(y, m) + 1);
		let d: i32 = daydist.ind_sample(rng);
		assert_eq!(day_of_week_naive(y, m, d), day_of_week(y, m, d));
	}
}


fn test_lenient_extreme() {
	const CASES: &'static [(i32,i32,i32,i32)] = &[
		(-2147483648, -2147483648, -2147483648, 4),
		(-2147483648, -2147483648,           0, 6),
		(-2147483648, -2147483648,  2147483647, 0),
		(-2147483648,           0, -2147483648, 3),
		(-2147483648,           0,           0, 5),
		(-2147483648,           0,  2147483647, 6),
		(-2147483648,  2147483647, -2147483648, 0),
		(-2147483648,  2147483647,           0, 2),
		(-2147483648,  2147483647,  2147483647, 3),
		(          0, -2147483648, -2147483648, 0),
		(          0, -2147483648,           0, 2),
		(          0, -2147483648,  2147483647, 3),
		(          0,           0, -2147483648, 0),
		(          0,           0,           0, 2),
		(          0,           0,  2147483647, 3),
		(          0,  2147483647, -2147483648, 4),
		(          0,  2147483647,           0, 6),
		(          0,  2147483647,  2147483647, 0),
		( 2147483647, -2147483648, -2147483648, 3),
		( 2147483647, -2147483648,           0, 5),
		( 2147483647, -2147483648,  2147483647, 6),
		( 2147483647,           0, -2147483648, 3),
		( 2147483647,           0,           0, 5),
		( 2147483647,           0,  2147483647, 6),
		( 2147483647,  2147483647, -2147483648, 6),
		( 2147483647,  2147483647,           0, 1),
		( 2147483647,  2147483647,  2147483647, 2),
		
		(-2147482867,        3391,        -370, 6),
		(-2147482916, -2147474794,  2147483083, 6),
		(       -113,        4416,         846, 3),
		(-2147483527,        1953,  2147483113, 0),
		(-2147483609,        5056, -2147483507, 5),
		(-2147483145, -2147473696,  2147483050, 3),
		(-2147483364, -2147476925,  2147483110, 0),
		(-2147482829,  2147478555, -2147482893, 4),
		( 2147483004,        4207,         439, 5),
		( 2147483375,  2147476221,        -264, 1),
		( 2147483331, -2147474091,          24, 1),
		(-2147482651,       -2557,  2147482914, 0),
		(       -474,  2147481275, -2147483361, 6),
		( 2147483575,        8469,  2147483571, 4),
		(       -729,  2147482455,        -742, 3),
		(-2147483082, -2147482431,         893, 5),
		(       -935,  2147477896,        -983, 3),
		(        989,  2147478994,         103, 2),
		( 2147483388,       -7349, -2147482986, 3),
		(-2147483243,  2147478174,        -972, 1),
		( 2147483126, -2147473910,  2147483010, 3),
		( 2147482852,  2147475470,         762, 4),
		(        978,       -3684,         921, 0),
		(-2147482993,        5521,         659, 2),
		(-2147483592,       -6177,        -416, 6),
		(-2147482685,  2147480301, -2147483125, 0),
		(-2147483117,       -3192,  2147482759, 1),
		(-2147482977,  2147480575, -2147483637, 2),
		( 2147482784,  2147481908, -2147483231, 0),
		( 2147483307, -2147482066,          97, 1),
		(-2147482846, -2147483093,        -117, 4),
		(-2147483546, -2147481111,  2147483477, 1),
		(       -978,  2147477925,  2147483516, 5),
		( 2147483440,       -5509,        -328, 3),
		(-2147482752, -2147482615,  2147483471, 2),
		(-2147483374,  2147477167,        -195, 2),
		(       -655,  2147474795,  2147483487, 3),
		(-2147483616,       -3046, -2147483405, 5),
		(-2147482974, -2147475398,  2147483324, 3),
		( 2147483293, -2147473953,  2147483436, 5),
		(-2147482873, -2147478425, -2147482858, 1),
		(-2147483483,  2147475023,        -975, 2),
		(-2147482989,  2147478204,         583, 5),
		( 2147482648, -2147483615,         265, 6),
		(-2147483496, -2147479904, -2147483523, 5),
		(        865,        8184,  2147482837, 2),
		(-2147483395, -2147475567,  2147482843, 1),
		(-2147482753, -2147478064,  2147483301, 2),
		( 2147483542,  2147474858,         297, 4),
		(-2147483156,  2147480861, -2147482792, 5),
		(       -714,  2147480816,  2147482718, 1),
		( 2147482678, -2147474015, -2147483327, 6),
		( 2147482712, -2147480138, -2147482804, 0),
		(-2147482893,       -8853,         767, 2),
		( 2147483123,       -8226, -2147483251, 3),
		(-2147483312,  2147475396,         397, 3),
		(-2147483272,  2147480332,  2147482777, 6),
		( 2147483464,       -2587,  2147483428, 3),
		( 2147483440,         336,  2147483435, 5),
		( 2147483554, -2147479219,  2147483635, 3),
		( 2147483098,       -5676,        -777, 2),
		(       -978,        2245,  2147483577, 4),
		(       -385,  2147477663, -2147483334, 1),
		(        493,       -5408, -2147482835, 0),
		(       -832,  2147482578, -2147483289, 1),
		( 2147483121,         721,        -532, 3),
		(       -839, -2147476439,        -421, 0),
		(-2147483325,  2147475737,        -673, 6),
		( 2147482803,  2147482782, -2147483052, 1),
		(-2147483289,  2147477201,        -854, 0),
		( 2147482988, -2147482988,  2147483495, 0),
		( 2147482833,        -152,        -450, 0),
		(       -680,  2147476457,         614, 6),
		(       -495, -2147482633,         135, 1),
		( 2147483352,  2147473936,        -231, 1),
		(        538,  2147481471,  2147482683, 1),
		(-2147483258, -2147476749, -2147482982, 3),
		( 2147483142, -2147476915, -2147483279, 2),
		(-2147482846, -2147477082,        -811, 0),
		( 2147482814,  2147473863,         811, 1),
		( 2147483149,        4413, -2147483377, 0),
		(-2147483088,        5846, -2147483562, 4),
		(        -19, -2147481074, -2147482835, 0),
		( 2147483545,       -5504,  2147483436, 3),
		(       -699, -2147479378,  2147483028, 5),
		(-2147483459, -2147477306,        -669, 5),
		(-2147482851,  2147482950, -2147482920, 0),
		(        844, -2147483061,        -732, 5),
		( 2147483354,  2147478624, -2147483356, 0),
		(        105,  2147482272,  2147482962, 2),
		(-2147483504,  2147476125,  2147482960, 3),
		( 2147482773,  2147479428,          57, 4),
		(       -155, -2147480377,         385, 4),
		(       -565, -2147481441,        -627, 5),
		( 2147483564,  2147477196, -2147482687, 6),
		( 2147483311, -2147481163,  2147482945, 6),
		(        867, -2147481094,        -470, 3),
		(-2147483548,  2147473721, -2147483013, 0),
		( 2147483177, -2147482328,         186, 2),
		(        775,  2147474818,  2147482979, 4),
	];
	for &(y, m, d, dow) in CASES {
		assert_eq!(dow, day_of_week(y, m, d));
	}
}


fn test_lenient_randomly() {
	const TRIALS: i32 = 1_000_000;
	let rng = &mut rand::thread_rng();
	let yeardist = Range::new(2000, 2400);
	let monthdist = Range::new(1, 13);
	let yearperturbdist = Range::new(-5000, 5000);
	let dayperturbdist = Range::new(-500, 500);
	
	for _ in 0 .. TRIALS {
		let mut y: i32 = yeardist.ind_sample(rng);
		let mut m: i32 = monthdist.ind_sample(rng);
		let daydist = Range::new(1, month_length(y, m) + 1);
		let mut d: i32 = daydist.ind_sample(rng);
		let dow: i32 = day_of_week(y, m, d);
		
		let temp: i32 = yearperturbdist.ind_sample(rng);
		y += temp;
		m -= temp * 12;
		d += dayperturbdist.ind_sample(rng) * 7;
		assert_eq!(dow, day_of_week(y, m, d));
	}
}


/*---- Helper functions ----*/

fn day_of_week_naive(y: i32, m: i32, d: i32) -> i32 {
	assert!(1 <= m && m <= 12, "Invalid month");
	assert!(1 <= d && d <= month_length(y, m), "Invalid day-of-month");
	let mut ymd: (i32,i32,i32) = (1600, 1, 1);
	let mut dow = 6i32;
	while ymd < (y, m, d) {
		ymd = next_date(ymd);
		dow = (dow + 1) % 7;
	}
	while ymd > (y, m, d) {
		ymd = previous_date(ymd);
		dow = (dow - 1 + 7) % 7;
	}
	dow
}


fn next_date((y, m, d): (i32,i32,i32)) -> (i32,i32,i32) {
	assert!(1 <= m && m <= 12, "Invalid month");
	assert!(1 <= d && d <= month_length(y, m), "Invalid day-of-month");
	if d < month_length(y, m) {
		(y, m, d + 1)
	} else if m < 12 {
		(y, m + 1, 1)
	} else {
		(y + 1, 1, 1)
	}
}


fn previous_date((y, m, d): (i32,i32,i32)) -> (i32,i32,i32) {
	assert!(1 <= m && m <= 12, "Invalid month");
	assert!(1 <= d && d <= month_length(y, m), "Invalid day-of-month");
	if d > 1 {
		(y, m, d - 1)
	} else if m > 1 {
		(y, m - 1, month_length(y, m - 1))
	} else {
		(y - 1, 12, 31)
	}
}


fn month_length(y: i32, m: i32) -> i32 {
	if m != 2 {
		MONTH_LENGTHS[usize::try_from(m).unwrap()]
	} else if is_leap_year(y) {
		29
	} else {
		28
	}
}

const MONTH_LENGTHS: [i32; 13] =
	[-1, 31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];


fn is_leap_year(y: i32) -> bool {
	y % 4 == 0 && (y % 100 != 0 || y % 400 == 0)
}