surrealmx 0.20.0

use crate::version::Version;
use bytes::Bytes;
use ferntree::impl_optimistic_read_boxed;
use smallvec::SmallVec;

pub(crate) enum IndexOrUpdate<'a> {
	/// No need to insert the entry or update
	Ignore,
	/// Insert the entry at the specified index
	Index(usize),
	/// Update an entry with the specified entry
	Update(&'a mut Version),
}

#[derive(Clone)]
pub struct Versions {
	inner: SmallVec<[Version; 4]>,
}

// SAFETY: `Versions` is `Clone + Send + Sync + 'static`; ferntree stores it
// behind `BoxedSlot`, so the displaced `Box<Versions>` must be routed through
// the epoch GC on overwrite. See `impl_optimistic_read_boxed!` docs.
impl_optimistic_read_boxed!(Versions);

impl From<Version> for Versions {
	fn from(value: Version) -> Self {
		let mut inner = SmallVec::new();
		inner.push(value);
		Versions {
			inner,
		}
	}
}

impl Versions {
	/// Create a new versions object.
	#[inline]
	pub(crate) fn new() -> Self {
		Versions {
			inner: SmallVec::new(),
		}
	}

	/// Appends or inserts an element into its sorted position.
	#[inline]
	pub(crate) fn push(&mut self, value: Version) {
		// Fast path: check if appending to the end
		if let Some(last) = self.inner.last_mut() {
			// Compare the new value with the last value
			match value.version.cmp(&last.version) {
				std::cmp::Ordering::Greater => {
					// Newer version - append if value is different
					if value.value != last.value {
						self.inner.push(value);
					}
					// Same value, ignore duplicate
					return;
				}
				std::cmp::Ordering::Equal => {
					// Same version - update if value is different
					if value.value != last.value {
						last.value = value.value;
					}
					// Same value, ignore
					return;
				}
				std::cmp::Ordering::Less => {
					// Older version - fall through to slow path
				}
			}
		} else {
			// Empty list - push if not a delete
			if value.value.is_some() {
				self.inner.push(value);
			}
			// Delete on empty list, ignore
			return;
		}
		// Otherwise, use the index or update logic
		match self.fetch_index_or_update(&value) {
			// No need to insert or update the entry
			IndexOrUpdate::Ignore => {
				// Do nothing
			}
			// Insert the entry at the specified index
			IndexOrUpdate::Index(idx) => {
				self.inner.insert(idx, value);
			}
			// Update an existing entry in the list
			IndexOrUpdate::Update(entry) => {
				entry.value = value.value;
			}
		}
	}

	/// Determine if a new entry should be ignored, inserted, or update an
	/// existing entry.
	///
	/// This function works in the following way:
	/// - Return IndexOrUpdate::Ignore if:
	///   - The latest entry with a version <= value.version has the same value
	///     as the new value
	///   - The latest entry with a version <= value.version is a delete and the
	///     new value is a delete
	/// - Return IndexOrUpdate::Update(version) if:
	///   - The new value version is the same as an existing version and we
	///     should update the entry
	/// - Return IndexOrUpdate::Index(index) if:
	///   - There is no entry with a version <= value.version
	///   - The new value version is different to the latest entry with a
	///     version <= value.version
	#[inline]
	pub(crate) fn fetch_index_or_update(&mut self, value: &Version) -> IndexOrUpdate<'_> {
		// Find the index of the item where item.version <= value.version
		let idx = self.find_index_lte_version(value.version);
		// If there is no entry with a version <= value.version
		if idx == 0 {
			// If this is a delete, ignore it (no point storing initial delete)
			if value.value.is_none() {
				return IndexOrUpdate::Ignore;
			}
			// Otherwise, insert at the beginning
			return IndexOrUpdate::Index(0);
		}
		// Get the latest entry with version <= value.version
		if let Some(existing) = self.inner.get_mut(idx - 1) {
			// Check if the version is the same as an existing version
			if existing.version == value.version {
				// Check if the values are the same
				if existing.value == value.value {
					// Same version, same value - ignore
					return IndexOrUpdate::Ignore;
				}
				// Same version, different value - update
				return IndexOrUpdate::Update(existing);
			}
			// Different version - check if values are the same
			if existing.value == value.value {
				// Latest entry has the same value - ignore
				return IndexOrUpdate::Ignore;
			}
			// Different version, different value - insert
			return IndexOrUpdate::Index(idx);
		}
		// Fallback - should not reach here
		IndexOrUpdate::Index(idx)
	}

	/// An iterator that removes the items and yields them by value.
	#[inline]
	pub fn drain<R>(&mut self, range: R)
	where
		R: std::ops::RangeBounds<usize>,
	{
		// Drain the versions
		self.inner.drain(range);
		// Shrink the vec inline
		self.inner.shrink_to_fit();
	}

	/// Check if the item at a specific version is a delete.
	#[inline]
	pub(crate) fn is_delete(&self, version: usize) -> bool {
		self.inner.get(version).is_some_and(|v| v.value.is_none())
	}

	/// Find the index of the entry where item.version < version.
	#[inline]
	pub(crate) fn find_index_lt_version(&self, version: u64) -> usize {
		// Check for any existing version
		if let Some(last) = self.inner.last() {
			// Check if the version is newer
			if version > last.version {
				// Return the index of the last version
				return self.inner.len();
			}
		}
		// Check the list length for reverse iteration or binary search
		if self.inner.len() <= 4 {
			// Use linear search to find the first element where v.version > version
			self.inner.iter().rposition(|v| v.version < version).map_or(0, |i| i + 1)
		} else {
			// Find the index of the item where item.version <= version
			self.inner.partition_point(|v| v.version < version)
		}
	}

	/// Find the index of the entry where item.version <= version.
	#[inline]
	pub(crate) fn find_index_lte_version(&self, version: u64) -> usize {
		// Check for any existing version
		if let Some(last) = self.inner.last() {
			// Check if the version is newer
			if version >= last.version {
				// Return the index of the last version
				return self.inner.len();
			}
		}
		// Check the list length for reverse iteration or binary search
		if self.inner.len() <= 4 {
			// Use linear search to find the first element where v.version > version
			self.inner.iter().rposition(|v| v.version <= version).map_or(0, |i| i + 1)
		} else {
			// Use binary search to find the first element where v.version >= version
			self.inner.partition_point(|v| v.version <= version)
		}
	}

	/// Fetch the entry at a specific version in the versions list.
	#[inline]
	pub(crate) fn fetch_version(&self, version: u64) -> Option<Bytes> {
		// Find the index of the item where item.version <= version
		let idx = self.find_index_lte_version(version);
		// If there is an entry, return the value
		if idx > 0 {
			self.inner.get(idx - 1).and_then(|v| v.value.clone())
		} else {
			None
		}
	}

	/// Check if an entry at a specific version exists and is not a delete.
	#[inline]
	pub(crate) fn exists_version(&self, version: u64) -> bool {
		// Find the index of the item where item.version <= version
		let idx = self.find_index_lte_version(version);
		// If there is an entry, return the value
		if idx > 0 {
			self.inner.get(idx - 1).is_some_and(|v| v.value.is_some())
		} else {
			false
		}
	}

	/// Get all versions as a vector of (version, value) tuples.
	#[inline]
	pub(crate) fn all_versions(&self) -> Vec<(u64, Option<Bytes>)> {
		self.inner.iter().map(|v| (v.version, v.value.clone())).collect()
	}

	/// Remove all versions older than the specified version.
	#[inline]
	pub(crate) fn gc_older_versions(&mut self, version: u64) -> usize {
		// Find the index of the item where item.version < version
		let idx = self.find_index_lt_version(version);
		// Handle the case where all versions are older than the cutoff
		if idx >= self.inner.len() {
			// Check if the last version is a delete
			if let Some(last) = self.inner.last() {
				if last.value.is_none() {
					// Last version is a delete, remove everything
					self.inner.clear();
				} else if idx > 1 {
					// Last version has data, keep it and remove all others
					self.drain(..idx - 1);
				}
			}
		} else if self.is_delete(idx) {
			// Remove all versions up to and including this delete
			self.drain(..=idx);
		} else if idx > 0 {
			// Remove all versions up to this version
			self.drain(..idx);
		}
		// Return the length
		self.inner.len()
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	use bytes::Bytes;

	/// Helper function to create a Version from a version number and optional
	/// value
	fn make_version(version: u64, value: Option<&str>) -> Version {
		Version {
			version,
			value: value.map(|s| Bytes::from(s.to_string())),
		}
	}

	/// Helper function to create a Versions instance with the given version
	/// tuples
	fn make_versions(versions: Vec<(u64, Option<&str>)>) -> Versions {
		let mut v = Versions::new();
		for (version, value) in versions {
			v.push(make_version(version, value));
		}
		v
	}

	// ==================== Tests for find_index_lt_version ====================

	#[test]
	fn test_find_index_lt_version_empty() {
		let versions = Versions::new();
		assert_eq!(versions.find_index_lt_version(0), 0);
		assert_eq!(versions.find_index_lt_version(1), 0);
		assert_eq!(versions.find_index_lt_version(100), 0);
	}

	#[test]
	fn test_find_index_lt_version_single_version() {
		let versions = make_versions(vec![(10, Some("value"))]);
		// Query before the version
		assert_eq!(versions.find_index_lt_version(5), 0);
		assert_eq!(versions.find_index_lt_version(9), 0);
		// Query at the version
		assert_eq!(versions.find_index_lt_version(10), 0);
		// Query after the version
		assert_eq!(versions.find_index_lt_version(11), 1);
		assert_eq!(versions.find_index_lt_version(100), 1);
	}

	#[test]
	fn test_find_index_lt_version_multiple_versions() {
		// Create a small list (≤32 elements) to trigger linear search
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, Some("v2")),
			(30, Some("v3")),
			(40, Some("v4")),
			(50, Some("v5")),
		]);
		// Query before the first version
		assert_eq!(versions.find_index_lt_version(0), 0);
		assert_eq!(versions.find_index_lt_version(5), 0);
		// Query at the first version
		assert_eq!(versions.find_index_lt_version(10), 0);
		// Query after the first version
		assert_eq!(versions.find_index_lt_version(15), 1);
		// Query at the second version
		assert_eq!(versions.find_index_lt_version(20), 1);
		// Query after the second version
		assert_eq!(versions.find_index_lt_version(25), 2);
		assert_eq!(versions.find_index_lt_version(30), 2);
		// Query at the third version
		assert_eq!(versions.find_index_lt_version(35), 3);
		assert_eq!(versions.find_index_lt_version(40), 3);
		// Query at the fourth version
		assert_eq!(versions.find_index_lt_version(45), 4);
		// Query at the fifth version
		assert_eq!(versions.find_index_lt_version(50), 4);
		// Query after the fifth version
		assert_eq!(versions.find_index_lt_version(51), 5);
		assert_eq!(versions.find_index_lt_version(100), 5);
	}

	#[test]
	fn test_find_index_lt_version_with_deletes() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, None), // Delete
			(30, Some("v3")),
			(40, None), // Delete
		]);
		// Query before the first version
		assert_eq!(versions.find_index_lt_version(5), 0);
		assert_eq!(versions.find_index_lt_version(9), 0);
		// Query at the first version
		assert_eq!(versions.find_index_lt_version(10), 0);
		// Query after the first version
		assert_eq!(versions.find_index_lt_version(15), 1);
		// Query at the second version
		assert_eq!(versions.find_index_lt_version(20), 1);
		// Query after the second version
		assert_eq!(versions.find_index_lt_version(25), 2);
		assert_eq!(versions.find_index_lt_version(30), 2);
		// Query at the third version
		assert_eq!(versions.find_index_lt_version(35), 3);
		assert_eq!(versions.find_index_lt_version(40), 3);
		// Query after the third version
		assert_eq!(versions.find_index_lt_version(50), 4);
	}

	// ==================== Tests for find_index_lte_version ====================

	#[test]
	fn test_find_index_lte_version_empty() {
		let versions = Versions::new();
		assert_eq!(versions.find_index_lte_version(0), 0);
		assert_eq!(versions.find_index_lte_version(1), 0);
		assert_eq!(versions.find_index_lte_version(100), 0);
	}

	#[test]
	fn test_find_index_lte_version_single_version() {
		let versions = make_versions(vec![(10, Some("value"))]);
		// Query before the version
		assert_eq!(versions.find_index_lte_version(5), 0);
		assert_eq!(versions.find_index_lte_version(9), 0);
		// Query at the version
		assert_eq!(versions.find_index_lte_version(10), 1);
		// Query after the version
		assert_eq!(versions.find_index_lte_version(11), 1);
		assert_eq!(versions.find_index_lte_version(100), 1);
	}

	#[test]
	fn test_find_index_lte_version_multiple_versions() {
		// Create a small list (≤32 elements) to trigger linear search
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, Some("v2")),
			(30, Some("v3")),
			(40, Some("v4")),
			(50, Some("v5")),
		]);
		// Query before the first version
		assert_eq!(versions.find_index_lte_version(0), 0);
		assert_eq!(versions.find_index_lte_version(5), 0);
		// Query at the first version
		assert_eq!(versions.find_index_lte_version(10), 1);
		// Query after the first version
		assert_eq!(versions.find_index_lte_version(15), 1);
		// Query at the second version
		assert_eq!(versions.find_index_lte_version(20), 2);
		// Query after the second version
		assert_eq!(versions.find_index_lte_version(25), 2);
		// Query at the third version
		assert_eq!(versions.find_index_lte_version(30), 3);
		// Query after the third version
		assert_eq!(versions.find_index_lte_version(35), 3);
		// Query at the fourth version
		assert_eq!(versions.find_index_lte_version(40), 4);
		// Query after the fourth version
		assert_eq!(versions.find_index_lte_version(45), 4);
		// Query at the fifth version
		assert_eq!(versions.find_index_lte_version(50), 5);
		// Query after the fifth version
		assert_eq!(versions.find_index_lte_version(51), 5);
		assert_eq!(versions.find_index_lte_version(100), 5);
	}

	#[test]
	fn test_find_index_lte_version_with_deletes() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, None), // Delete
			(30, Some("v3")),
			(40, None), // Delete
		]);
		// Query at the first version
		assert_eq!(versions.find_index_lte_version(10), 1);
		// Query after the first version
		assert_eq!(versions.find_index_lte_version(15), 1);
		// Query at the second version
		assert_eq!(versions.find_index_lte_version(20), 2);
		// Query after the second version
		assert_eq!(versions.find_index_lte_version(25), 2);
		// Query at the third version
		assert_eq!(versions.find_index_lte_version(30), 3);
		// Query after the third version
		assert_eq!(versions.find_index_lte_version(35), 3);
		// Query at the fourth version
		assert_eq!(versions.find_index_lte_version(40), 4);
		// Query after the fourth version
		assert_eq!(versions.find_index_lte_version(50), 4);
	}

	#[test]
	fn test_find_index_lt_vs_lte_difference() {
		// This test demonstrates the key difference between < and <=
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, Some("v2")),
			(30, Some("v3")),
			(40, Some("v4")),
			(50, Some("v5")),
		]);
		// Query at the first version
		assert_eq!(versions.find_index_lt_version(10), 0);
		assert_eq!(versions.find_index_lte_version(10), 1);
		// Query after the first version
		assert_eq!(versions.find_index_lt_version(15), 1);
		assert_eq!(versions.find_index_lte_version(15), 1);
		// Query at the second version
		assert_eq!(versions.find_index_lt_version(20), 1);
		assert_eq!(versions.find_index_lte_version(20), 2);
		// Query at the third version
		assert_eq!(versions.find_index_lt_version(30), 2);
		assert_eq!(versions.find_index_lte_version(30), 3);
		// Query after the third version
		assert_eq!(versions.find_index_lt_version(35), 3);
		assert_eq!(versions.find_index_lte_version(35), 3);
	}

	// ==================== Tests for fetch_version ====================

	#[test]
	fn test_fetch_version_empty() {
		let versions = Versions::new();
		assert_eq!(versions.fetch_version(0), None);
		assert_eq!(versions.fetch_version(10), None);
		assert_eq!(versions.fetch_version(100), None);
	}

	#[test]
	fn test_fetch_version_single_version() {
		let versions = make_versions(vec![(10, Some("value"))]);
		// Query before the version
		assert_eq!(versions.fetch_version(5), None);
		assert_eq!(versions.fetch_version(9), None);
		// Query at the version
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("value".to_string())));
		// Query after the version
		assert_eq!(versions.fetch_version(11), Some(Bytes::from("value".to_string())));
		assert_eq!(versions.fetch_version(100), Some(Bytes::from("value".to_string())));
	}

	#[test]
	fn test_fetch_version_multiple_versions() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, Some("v2")),
			(30, Some("v3")),
			(40, Some("v4")),
			(50, Some("v5")),
		]);
		// Query before the first version
		assert_eq!(versions.fetch_version(5), None);
		// Query at the first version
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
		// Query after the first version
		assert_eq!(versions.fetch_version(15), Some(Bytes::from("v1".to_string())));
		// Query at the second version
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2".to_string())));
		// Query after the second version
		assert_eq!(versions.fetch_version(25), Some(Bytes::from("v2".to_string())));
		// Query at the third version
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v3".to_string())));
		// Query after the third version
		assert_eq!(versions.fetch_version(35), Some(Bytes::from("v3".to_string())));
		// Query at the fourth version
		assert_eq!(versions.fetch_version(40), Some(Bytes::from("v4".to_string())));
		// Query after the fourth version
		assert_eq!(versions.fetch_version(45), Some(Bytes::from("v4".to_string())));
		// Query at the fifth version
		assert_eq!(versions.fetch_version(50), Some(Bytes::from("v5".to_string())));
		// Query after the fifth version
		assert_eq!(versions.fetch_version(100), Some(Bytes::from("v5".to_string())));
	}

	#[test]
	fn test_fetch_version_with_deletes() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, None), // Delete
			(30, Some("v3")),
			(40, None), // Delete
		]);
		// Query before the first version
		assert_eq!(versions.fetch_version(5), None);
		// Query at the first version
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
		// Query after the first version
		assert_eq!(versions.fetch_version(15), Some(Bytes::from("v1".to_string())));
		// Query at the second version (delete)
		assert_eq!(versions.fetch_version(20), None);
		// Query after the second version (delete)
		assert_eq!(versions.fetch_version(25), None);
		// Query at the third version
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v3".to_string())));
		// Query after the third version
		assert_eq!(versions.fetch_version(35), Some(Bytes::from("v3".to_string())));
		// Query at the fourth version (delete)
		assert_eq!(versions.fetch_version(40), None);
		// Query after the fourth version (delete)
		assert_eq!(versions.fetch_version(50), None);
	}

	// ==================== Tests for exists_version ====================

	#[test]
	fn test_exists_version_empty() {
		let versions = Versions::new();
		assert!(!versions.exists_version(0));
		assert!(!versions.exists_version(10));
		assert!(!versions.exists_version(100));
	}

	#[test]
	fn test_exists_version_single_version() {
		let versions = make_versions(vec![(10, Some("value"))]);
		// Query before the version
		assert!(!versions.exists_version(5));
		assert!(!versions.exists_version(9));
		// Query at the version
		assert!(versions.exists_version(10));
		// Query after the version
		assert!(versions.exists_version(11));
		assert!(versions.exists_version(100));
	}

	#[test]
	fn test_exists_version_multiple_versions() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, Some("v2")),
			(30, Some("v3")),
			(40, Some("v4")),
			(50, Some("v5")),
		]);
		// Query before the first version
		assert!(!versions.exists_version(5));
		// Query at the first version
		assert!(versions.exists_version(10));
		// Query after the first version
		assert!(versions.exists_version(15));
		// Query at the second version
		assert!(versions.exists_version(20));
		// Query after the second version
		assert!(versions.exists_version(25));
		// Query at the third version
		assert!(versions.exists_version(30));
		// Query after the third version
		assert!(versions.exists_version(35));
		// Query at the fourth version
		assert!(versions.exists_version(40));
		// Query after the fourth version
		assert!(versions.exists_version(45));
		// Query at the fifth version
		assert!(versions.exists_version(50));
		// Query after the fifth version
		assert!(versions.exists_version(100));
	}

	#[test]
	fn test_exists_version_with_deletes() {
		let versions = make_versions(vec![
			(10, Some("v1")),
			(20, None), // Delete
			(30, Some("v3")),
			(40, None), // Delete
		]);
		// Query before the first version
		assert!(!versions.exists_version(5));
		// Query at the first version
		assert!(versions.exists_version(10));
		// Query after the first version
		assert!(versions.exists_version(15));
		// Query at the second version (delete)
		assert!(!versions.exists_version(20));
		// Query after the second version (delete)
		assert!(!versions.exists_version(25));
		// Query at the third version
		assert!(versions.exists_version(30));
		// Query after the third version
		assert!(versions.exists_version(35));
		// Query at the fourth version (delete)
		assert!(!versions.exists_version(40));
		// Query after the fourth version (delete)
		assert!(!versions.exists_version(50));
	}

	// ==================== Tests for push ====================

	#[test]
	fn test_push_to_empty_list() {
		let mut versions = Versions::new();
		// Push a value to empty list
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
	}

	#[test]
	fn test_push_delete_to_empty_list() {
		let mut versions = Versions::new();
		// Push a delete (None) to empty list - should not add
		versions.push(make_version(10, None));
		assert_eq!(versions.inner.len(), 0);
	}

	#[test]
	fn test_push_in_order() {
		let mut versions = Versions::new();
		// Push versions in increasing order
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		versions.push(make_version(30, Some("v3")));
		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2".to_string())));
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v3".to_string())));
	}

	#[test]
	fn test_push_duplicate_values() {
		let mut versions = Versions::new();
		// Push first version
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		// Push same value at newer version - should be skipped
		versions.push(make_version(20, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		// Push different value - should be added
		versions.push(make_version(30, Some("v2")));
		assert_eq!(versions.inner.len(), 2);
		// Push same value again - should be skipped
		versions.push(make_version(40, Some("v2")));
		assert_eq!(versions.inner.len(), 2);
	}

	#[test]
	fn test_push_out_of_order() {
		let mut versions = Versions::new();
		// Push versions out of order
		versions.push(make_version(30, Some("v3")));
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Should be sorted correctly
		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.inner[0].version, 10);
		assert_eq!(versions.inner[1].version, 20);
		assert_eq!(versions.inner[2].version, 30);
	}

	#[test]
	fn test_push_with_deletes() {
		let mut versions = Versions::new();
		// Push value, then delete, then value again
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		// Push delete
		versions.push(make_version(20, None));
		assert_eq!(versions.inner.len(), 2);
		assert!(!versions.exists_version(20));
		// Push new value
		versions.push(make_version(30, Some("v3")));
		assert_eq!(versions.inner.len(), 3);
		assert!(versions.exists_version(30));
	}

	#[test]
	fn test_push_same_version_different_value() {
		let mut versions = Versions::new();
		// Push a version
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		// Push same version with different value - should update/replace
		versions.push(make_version(10, Some("v2")));
		assert_eq!(versions.inner.len(), 1);
		// The new value should have replaced the old one
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v2".to_string())));
	}

	#[test]
	fn test_push_same_version_same_value() {
		let mut versions = Versions::new();
		// Push a version
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		// Push same version with same value - should still update (no-op)
		versions.push(make_version(10, Some("v1")));
		assert_eq!(versions.inner.len(), 1);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
	}

	// ==================== Fast Path Tests ====================

	#[test]
	fn test_push_fast_path_append_different_value() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Fast path: append with different value
		versions.push(make_version(30, Some("v3")));
		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.inner[2].version, 30);
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v3".to_string())));
	}

	#[test]
	fn test_push_fast_path_append_same_value() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Fast path: append with same value as last - should be ignored
		versions.push(make_version(30, Some("v2")));
		assert_eq!(versions.inner.len(), 2);
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v2".to_string())));
	}

	#[test]
	fn test_push_fast_path_update_last_different_value() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Fast path: update last version with different value
		versions.push(make_version(20, Some("v2_updated")));
		assert_eq!(versions.inner.len(), 2);
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2_updated".to_string())));
	}

	#[test]
	fn test_push_fast_path_update_last_same_value() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Fast path: update last version with same value - no-op
		versions.push(make_version(20, Some("v2")));
		assert_eq!(versions.inner.len(), 2);
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2".to_string())));
	}

	#[test]
	fn test_push_fast_path_multiple_updates_to_last() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		// Multiple sequential updates to the same version
		versions.push(make_version(10, Some("v2")));
		versions.push(make_version(10, Some("v3")));
		versions.push(make_version(10, Some("v4")));
		assert_eq!(versions.inner.len(), 1);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v4".to_string())));
	}

	#[test]
	fn test_push_fast_path_alternating_append_update() {
		let mut versions = Versions::new();
		// Append version 10
		versions.push(make_version(10, Some("v1")));
		// Append version 20
		versions.push(make_version(20, Some("v2")));
		// Update version 20
		versions.push(make_version(20, Some("v2_updated")));
		// Append version 30
		versions.push(make_version(30, Some("v3")));
		// Update version 30
		versions.push(make_version(30, Some("v3_updated")));

		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v1".to_string())));
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2_updated".to_string())));
		assert_eq!(versions.fetch_version(30), Some(Bytes::from("v3_updated".to_string())));
	}

	#[test]
	fn test_push_slow_path_insert_middle() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(30, Some("v3")));
		// Slow path: insert in the middle (version < last.version)
		versions.push(make_version(20, Some("v2")));

		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.inner[0].version, 10);
		assert_eq!(versions.inner[1].version, 20);
		assert_eq!(versions.inner[2].version, 30);
	}

	#[test]
	fn test_push_slow_path_insert_beginning() {
		let mut versions = Versions::new();
		versions.push(make_version(20, Some("v2")));
		versions.push(make_version(30, Some("v3")));
		// Slow path: insert at the beginning
		versions.push(make_version(10, Some("v1")));

		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.inner[0].version, 10);
		assert_eq!(versions.inner[1].version, 20);
		assert_eq!(versions.inner[2].version, 30);
	}

	#[test]
	fn test_push_slow_path_update_middle() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		versions.push(make_version(30, Some("v3")));
		// Slow path: update a middle version
		versions.push(make_version(20, Some("v2_updated")));

		assert_eq!(versions.inner.len(), 3);
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2_updated".to_string())));
	}

	#[test]
	fn test_push_with_delete_at_end() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Fast path: append delete
		versions.push(make_version(30, None));

		assert_eq!(versions.inner.len(), 3);
		assert!(!versions.exists_version(30));
		assert_eq!(versions.fetch_version(30), None);
	}

	#[test]
	fn test_push_delete_then_value_same_version() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		// Push delete
		versions.push(make_version(20, None));
		assert!(!versions.exists_version(20));
		// Update same version with a value
		versions.push(make_version(20, Some("v2")));
		assert_eq!(versions.inner.len(), 2);
		assert!(versions.exists_version(20));
		assert_eq!(versions.fetch_version(20), Some(Bytes::from("v2".to_string())));
	}

	#[test]
	fn test_push_value_then_delete_same_version() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		versions.push(make_version(20, Some("v2")));
		// Update last version to delete
		versions.push(make_version(20, None));

		assert_eq!(versions.inner.len(), 2);
		assert!(!versions.exists_version(20));
		assert_eq!(versions.fetch_version(20), None);
	}

	#[test]
	fn test_push_consecutive_deletes() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		// Push delete at version 20
		versions.push(make_version(20, None));
		// Push another delete at version 30 (different from last value which is None)
		versions.push(make_version(30, None));

		// Should only have 2 entries - version 20 and 30 deletes should be separate
		assert_eq!(versions.inner.len(), 2);
		assert!(!versions.exists_version(20));
		assert!(!versions.exists_version(30));
	}

	#[test]
	fn test_push_stress_many_appends() {
		let mut versions = Versions::new();
		// Push many versions in order (all fast path appends)
		for i in 0..100 {
			let value = format!("v{}", i);
			versions.push(make_version(i * 10, Some(&value)));
		}
		assert_eq!(versions.inner.len(), 100);
		assert_eq!(versions.inner[0].version, 0);
		assert_eq!(versions.inner[99].version, 990);
	}

	#[test]
	fn test_push_stress_many_updates() {
		let mut versions = Versions::new();
		versions.push(make_version(10, Some("v1")));
		// Update the same version many times (all fast path updates)
		for i in 0..100 {
			let value = format!("v{}", i);
			versions.push(make_version(10, Some(&value)));
		}
		assert_eq!(versions.inner.len(), 1);
		assert_eq!(versions.fetch_version(10), Some(Bytes::from("v99".to_string())));
	}
}