use std::ops::Range;

pub fn verse(n: u32) -> String {
	match n {
		0 => "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n".to_string(),
		1 => "1 bottle of beer on the wall, 1 bottle of beer.\nTake it down and pass it around, no more bottles of beer on the wall.\n".to_string(),
		2 => "2 bottles of beer on the wall, 2 bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n".to_string(),
		_ => format!("{0} bottles of beer on the wall, {0} bottles of beer.\nTake one down and pass it around, {1} bottles of beer on the wall.\n", n, n - 1),
	}
}

// Length for verse 3 onwards is just for the common substrings (i.e., excluding `n` and `n - 1`, so these need to be added back).
const LENGTHS: [usize; 4] = [129, 118, 114, 112];

fn range_digits(base: usize, range: Range<usize>) -> usize {
	let (mut result, mut power, mut current_digits) = (0, 1, 0);
	while power <= range.start {
		power *= base;
		current_digits += 1;
	}
	result += (power - range.start) * current_digits;
	while power <= range.end {
		let last_power = power;
		power *= base;
		current_digits += 1;
		result += (power - last_power) * current_digits;
	}
	result -= (power - range.end) * current_digits;
	result
}

pub fn sing(start: u32, end: u32) -> String {
	let (mut s, mut e) = (start, end);
	if start < end {
		s = end;
		e = start;
	}
	match (s, e) {
		(0, 0) => verse(0),
		(1, 1) => verse(1),
		(2, 2) => verse(2),
		(_, _) => {
			let mut out = String::with_capacity(
				match (s, e) {
					(1, 0) => LENGTHS[0] + LENGTHS[1],
					(2, 0) => LENGTHS[0] + LENGTHS[1] + LENGTHS[2],
					(2, 1) => LENGTHS[1] + LENGTHS[2],
					(_, _) => {
						(s as usize - 2) * LENGTHS[3]
							+ range_digits(
								10,
								Range {
									start: 3,
									end: (s + 1) as usize,
								},
							) + match e {
							0 => LENGTHS[0] + LENGTHS[1] + LENGTHS[2],
							1 => LENGTHS[1] + LENGTHS[2],
							2 => LENGTHS[2],
							_ => 0,
						}
					}
				} + ((s - e) as usize),
			);
			if start > end {
				out.push_str(&verse(s));
				(e..=s - 1).rev().for_each(|a| {
					out.push('\n');
					out.push_str(&verse(a));
				});
			} else {
				out.push_str(&verse(e));
				(e + 1..=s).for_each(|a| {
					out.push('\n');
					out.push_str(&verse(a));
				});
			}
			out
		}
	}
}