// Copyright Marcus Del Favero 2025
// Licensed under the GNU AGPLv3 with an exception, see `README.md` for details
use std::collections::VecDeque;

use crate::world::{MAX_STEPS, player::update::{PlayerUpdate, PlayerBulkUpdate}};
use crate::utils::TimedRollingAverage;

/**
 * A queue storing player updates that can have "negative length".
 *
 * This queue can have "negative length" if it's popped from more times than it
 * is pushed to. If this happens, the previous player update that was pushed
 * would be returned.
 *
 * See `after_popped` for how this queue's length can grow and shrink to
 * minimise problems experienced by the client.
 */
pub struct PlayerUpdateQueue {
	queue: VecDeque<(PlayerUpdate, u64)>,
	prev_update: (PlayerUpdate, u64),
	prev_received: u64,
	received: u64, // How many updates received from any source (regular and redundant bulk updates)
	stream_received: u64, // How many updates received from PlayerUpdate messages on the stream
	past_low_lens: TimedRollingAverage,
}

impl PlayerUpdateQueue {
	pub fn new() -> PlayerUpdateQueue {
		PlayerUpdateQueue {
			queue: VecDeque::new(),
			prev_update: (PlayerUpdate::default(), 0),
			prev_received: 0,
			received: 0,
			stream_received: 0,
			past_low_lens: TimedRollingAverage::new(1.0, 256),
		}
	}

	#[cfg(feature = "client")]
	pub fn reset(&mut self) {
		self.queue.clear();
		self.prev_update = (PlayerUpdate::default(), 0);
		self.prev_received = 0;
		self.received = 0;
		self.stream_received = 0;
	}

	/**
	 * Makes adjustments to the queue based on the history of how many updates
	 * are remaining in the queue.
	 *
	 * The ideal scenario is that the updates the client sent is the updates that
	 * get replayed back to all clients. If this doesn't happen then the clients
	 * can experience some jitter and possibly players might lose out on firing a
	 * shot.
	 *
	 * To decrease the probability of incorrect updates being replayed, one
	 * solution is to push all received updates to a queue and pop that queue
	 * when updates are needed. If the queue is empty, the previous received
	 * update is repeated again.
	 *
	 * This works well as eventually over time it becomes increasingly unlikely
	 * that the queue is empty, assuming that the client and server are running
	 * at the same speed (differences in system clock speed should be very small,
	 * but not zero). This is because when the queue is attempted to be popped
	 * while empty, the update that the client was going to send would eventually
	 * be received and added to the queue later, resulting in a larger queue.
	 *
	 * To see why doing this naïvely is a problem, consider the case that the
	 * client gets a lag spike lasting for a second (and assume ping is
	 * negligible). Then there's an entire second where the client isn't sending
	 * any updates and so the queue remains empty. Then the client responds from
	 * the lag spike and sends a second worth of updates to the server. The
	 * server pushes all those updates to its queue which is now very large.
	 * After this point, the queue is pushed to and popped from at the same rate,
	 * so it maintains its very large length forever.
	 *
	 * A large queue is a significant problem because this means there's a second
	 * worth of input lag forever which is obviously a bad problem. Scenarios
	 * like this can happen in practice if starting the game takes a while or the
	 * user moves the window to another workspace (at least in sway), so I should
	 * factor this.
	 *
	 * The solution is to truncate the queue's length if it ever gets too large.
	 * There are many possible definitions of what "too large" can be. This
	 * method takes into account the mean and standard deviation of a rolling
	 * average of the smallest the queue gets before receiving updates (standard
	 * deviation needs to be independent of the rate at which updates are
	 * received, as that's determined by the frame rate).
	 *
	 * This works well on a range of network conditions, with what counts as "too
	 * large" being larger with worse network conditions (packet loss and
	 * non-uniform ping, the size of the ping isn't relevant).
	 *
	 * There is a trade-off between input lag and jitter from popping the queue
	 * while empty and truncating the queue. The parameters `MAX` and `K` chosen
	 * below are an attempt at finding the best of both worlds.
	 */
	pub fn balance_queue(&mut self, dt: f32) {
		const MAX: f32 = 2.25;
		const K: f32 = 4.0;

		self.past_low_lens.add_time(dt);

		// Length of the queue right before update were received
		if self.received == self.prev_received {
			return;
		}

		debug_assert!(self.received > self.prev_received);
		let diff = (self.received - self.prev_received) as i64;
		self.prev_received = self.received;
		let low_len = self.queue.len() as i64 - diff;
		self.past_low_lens.add(low_len as f32);

		let Some((mean, stddev)) = self.past_low_lens.mean_and_stddev() else { return; };

		/*
		 * Avoids overestimating the standard deviation because the μ - kσ
		 * calculation is done using the assumption of a normal distribution, and
		 * it's possible that the client oscillates between neighbouring step
		 * counts, which shouldn't be considered.
		 */
		let stddev = (stddev - 0.5).max(0.0);

		// The queue length is unlikely to be below this lower bound
		let lower_bound = mean - K * stddev;

		if lower_bound > MAX {
			/*
			 * NOTE: In the future I can improve how I truncate the queue to
			 * minimise how much the player is affected.
			 */
			self.queue.drain(..((lower_bound - MAX).ceil() as usize).min(self.queue.len()));
		}
	}

	pub fn push(&mut self, update: PlayerUpdate, count: u64) {
		for _ in 0..count {
			self.stream_received += 1;
			if self.stream_received > self.received {
				self.update_received(update);
				assert_eq!(self.received, self.stream_received);
			}
		}
	}

	pub fn bulk_update(&mut self, bulk_update: PlayerBulkUpdate) {
		if let Some(bulk_update) = bulk_update.truncate(self.received + 1) {
			for update in bulk_update {
				self.update_received(update);
			}
		}
	}

	fn update_received(&mut self, update: PlayerUpdate) {
		self.received += 1;
		self.prev_update = (update, self.received);

		if self.queue.len() < MAX_STEPS {
			self.queue.push_back(self.prev_update);
		}
	}

	pub fn pop(&mut self) -> (PlayerUpdate, u64) {
		self.queue.pop_front().unwrap_or(self.prev_update)
	}
}
