plaza_server_utils 0.7.0

//! Relevance: deciding what each client needs to see.
//!
//! A multiplayer world is bigger than one screen and its players stand in
//! different places. Sending every entity to every client is `players x entities`
//! and does not scale; a horde game (thousands of short-lived enemies) shows that
//! quickly. So the server sends each client only what is *relevant* to it and
//! streams the churn (what entered or left a client's view) rather than the whole
//! set each tick.
//!
//! This module provides the mechanism as building blocks rather than a policy:
//!
//! - [`morton`]: Z-order curve encode/decode, mapping 2D or 3D integer cells to a
//!   single integer that preserves spatial locality. The mathematical primitive
//!   underneath a grid; usable on its own for locality sorts and broadphase.
//! - [`GridQuantizer`]: continuous world coordinates to integer grid cells (and
//!   their Morton keys).
//! - [`SpatialGrid`]: buckets entity ids into cells so a viewer can gather the ids
//!   near it without scanning the whole world. Rebuilt each tick; allocation-light.
//! - [`DenseGrid`]: the same surface over a world with known bounds, its buckets
//!   in a flat `Vec` indexed by [`CellSpace`] rather than a `HashMap` keyed by
//!   Morton code, so a cell lookup is an index rather than a hash.
//! - [`VisibilitySet`]: a dense bitset of who is visible to one client, with a
//!   fast bitwise diff against the previous tick, the `entered`/`left` streams a
//!   client needs to spawn and despawn entities.
//!
//! The app decides the world layout (cell size, origin), the relevance rule (a
//! radius, a frustum, a team) and how the streams are encoded on the wire. This
//! module only makes those cheap to compute.

use std::collections::HashMap;

/// Z-order (Morton) curve encoding: interleave the bits of integer coordinates
/// into one integer whose ordering follows spatial locality.
///
/// Two cells close in space have (mostly) close Morton codes, so sorting entities
/// by their code groups neighbours and a cell's code is a single `u64` key for a
/// hash bucket. This is the primitive [`GridQuantizer`] and [`SpatialGrid`] build
/// on; it is public for locality sorts, broadphase and out-of-core layouts.
pub mod morton {
  /// Spreads the low 32 bits of `v` across the even bit positions of a `u64`
  /// (one zero between each), so two of them interleave into a 64-bit code.
  fn part1by1(mut v: u64) -> u64 {
    v &= 0x0000_0000_ffff_ffff;
    v = (v | (v << 16)) & 0x0000_ffff_0000_ffff;
    v = (v | (v << 8)) & 0x00ff_00ff_00ff_00ff;
    v = (v | (v << 4)) & 0x0f0f_0f0f_0f0f_0f0f;
    v = (v | (v << 2)) & 0x3333_3333_3333_3333;
    v = (v | (v << 1)) & 0x5555_5555_5555_5555;
    v
  }

  /// Inverse of [`part1by1`]: gathers the even bits back into the low 32.
  fn compact1by1(mut v: u64) -> u64 {
    v &= 0x5555_5555_5555_5555;
    v = (v | (v >> 1)) & 0x3333_3333_3333_3333;
    v = (v | (v >> 2)) & 0x0f0f_0f0f_0f0f_0f0f;
    v = (v | (v >> 4)) & 0x00ff_00ff_00ff_00ff;
    v = (v | (v >> 8)) & 0x0000_ffff_0000_ffff;
    v = (v | (v >> 16)) & 0x0000_0000_ffff_ffff;
    v
  }

  /// Interleaves two full 32-bit coordinates into a 64-bit Morton code.
  pub fn encode_2d(x: u32, y: u32) -> u64 {
    part1by1(x as u64) | (part1by1(y as u64) << 1)
  }

  /// Recovers the two coordinates from a 2D Morton code.
  pub fn decode_2d(code: u64) -> (u32, u32) {
    (compact1by1(code) as u32, compact1by1(code >> 1) as u32)
  }

  /// Spreads the low 21 bits of `v` with two zeros between each bit, for 3D.
  fn part1by2(mut v: u64) -> u64 {
    v &= 0x1f_ffff;
    v = (v | (v << 32)) & 0x001f_0000_0000_ffff;
    v = (v | (v << 16)) & 0x001f_0000_ff00_00ff;
    v = (v | (v << 8)) & 0x100f_00f0_0f00_f00f;
    v = (v | (v << 4)) & 0x10c3_0c30_c30c_30c3;
    v = (v | (v << 2)) & 0x1249_2492_4924_9249;
    v
  }

  /// Inverse of [`part1by2`].
  fn compact1by2(mut v: u64) -> u64 {
    v &= 0x1249_2492_4924_9249;
    v = (v | (v >> 2)) & 0x10c3_0c30_c30c_30c3;
    v = (v | (v >> 4)) & 0x100f_00f0_0f00_f00f;
    v = (v | (v >> 8)) & 0x001f_0000_ff00_00ff;
    v = (v | (v >> 16)) & 0x001f_0000_0000_ffff;
    v = (v | (v >> 32)) & 0x1f_ffff;
    v
  }

  /// Interleaves three coordinates into a 64-bit Morton code.
  ///
  /// Three axes share 63 bits, so each coordinate uses its low **21 bits**
  /// (`0..=2_097_151`); higher bits are dropped. That is ample for a cell grid.
  pub fn encode_3d(x: u32, y: u32, z: u32) -> u64 {
    part1by2(x as u64) | (part1by2(y as u64) << 1) | (part1by2(z as u64) << 2)
  }

  /// Recovers the three coordinates from a 3D Morton code.
  pub fn decode_3d(code: u64) -> (u32, u32, u32) {
    (compact1by2(code) as u32, compact1by2(code >> 1) as u32, compact1by2(code >> 2) as u32)
  }
}

/// Maps continuous world coordinates onto a uniform integer grid.
///
/// `origin` should be the world's minimum corner so every coordinate lands in a
/// non-negative cell; anything at or below the origin clamps to cell 0. `cell_size`
/// is the width of a cell in world units, pick it near a viewer's relevance radius
/// so a view spans only a few cells.
#[derive(Debug, Clone, Copy)]
pub struct GridQuantizer {
  origin_x: f32,
  origin_y: f32,
  cell_size: f32,
}

impl GridQuantizer {
  /// # Panics
  /// Panics if `cell_size` is not positive.
  pub fn new(origin: (f32, f32), cell_size: f32) -> Self {
    if cell_size <= 0.0 || cell_size.is_nan() {
      panic!("GridQuantizer cell_size must be positive");
    }
    Self {
      origin_x: origin.0,
      origin_y: origin.1,
      cell_size,
    }
  }

  /// The integer cell a world point falls in.
  pub fn cell(&self, x: f32, y: f32) -> (u32, u32) {
    let cx = ((x - self.origin_x) / self.cell_size).floor().max(0.0);
    let cy = ((y - self.origin_y) / self.cell_size).floor().max(0.0);
    (cx as u32, cy as u32)
  }

  /// The Morton key of the cell a world point falls in.
  pub fn key(&self, x: f32, y: f32) -> u64 {
    let (cx, cy) = self.cell(x, y);
    morton::encode_2d(cx, cy)
  }

  /// The world-space minimum corner of a cell.
  ///
  /// Lets a coordinate be written *relative to its cell*: a payload that knows
  /// which cell it describes can quantise over one cell's width instead of the
  /// world's, saving several bits per axis at the same step.
  pub fn corner(&self, cx: u32, cy: u32) -> (f32, f32) {
    (
      self.origin_x + cx as f32 * self.cell_size,
      self.origin_y + cy as f32 * self.cell_size,
    )
  }

  /// How many cells a radius spans, for sizing a query's cell window.
  pub fn cells_for_radius(&self, radius: f32) -> u32 {
    (radius / self.cell_size).ceil().max(0.0) as u32
  }

  /// The Morton keys of every cell overlapping the square of half-width
  /// `radius` around `(x, y)`, row by row. Cell-granular like
  /// [`SpatialGrid::query_radius`]: the corner cells reach past the radius.
  ///
  /// This is the region walk itself, for anything keyed by cell rather than by
  /// entity: publishing one payload per occupied cell, subscribing a viewer to
  /// the cells its view touches, diffing that set as the viewer moves.
  pub fn keys_in_radius(&self, x: f32, y: f32, radius: f32) -> impl Iterator<Item = u64> + use<> {
    self.cells_in_radius(x, y, radius).map(|(gx, gy)| morton::encode_2d(gx, gy))
  }

  /// The same walk as [`keys_in_radius`](Self::keys_in_radius), yielding cell
  /// coordinates rather than Morton codes.
  ///
  /// A Morton key is the right identifier for a sparse map; a world with known
  /// bounds can index a flat `Vec` by `(cx, cy)` instead, which costs an
  /// array index where the key costs a hash. Both are here because which one
  /// fits depends on the world rather than the grid.
  pub fn cells_in_radius(&self, x: f32, y: f32, radius: f32) -> impl Iterator<Item = (u32, u32)> + use<> {
    let (cx, cy) = self.cell(x, y);
    let r = self.cells_for_radius(radius);
    let (x0, x1) = (cx.saturating_sub(r), cx.saturating_add(r));
    let (y0, y1) = (cy.saturating_sub(r), cy.saturating_add(r));
    (y0..=y1).flat_map(move |gy| (x0..=x1).map(move |gx| (gx, gy)))
  }

  pub fn cell_size(&self) -> f32 {
    self.cell_size
  }
}

/// A [`GridQuantizer`] over a world with **known bounds**, so every cell has a
/// dense integer index and anything keyed by cell can live in a flat `Vec`.
///
/// The quantizer alone answers "which cell" and a Morton key is the right
/// identifier when the world is unbounded or sparse, because only a hash map
/// can hold it. A bounded world can use an array index where the key costs a
/// hash and at the scale this is for the difference is large. Publishing one
/// payload per cell and handing each viewer the cells its view touches does
/// roughly `viewers x cells-per-view` lookups a tick; moving those off a hash
/// was measured at 1.39x of a whole tick in one consumer and 8x on the path
/// that also builds a per-cell recipient list.
///
/// It is the *addressing scheme* rather than a container. The containers are
/// whatever the caller needs keyed by place:
///
/// - `CellTable<Vec<Id>>` is a dense spatial grid.
/// - `CellTable<Bytes>` is one published payload per cell.
/// - `CellTable<Vec<ClientId>>` is the inverse index that says who is listening
///   to each cell, which is what addressing a per-cell payload needs.
///
/// All three appear in a single consumer, which is why the addressing scheme is
/// the shared piece rather than any one container.
#[derive(Debug, Clone, Copy)]
pub struct CellSpace {
  quantizer: GridQuantizer,
  side: u32,
}

impl CellSpace {
  /// A space covering `[origin, origin + extent]` on both axes.
  ///
  /// # Panics
  /// Panics if `extent` is not positive.
  pub fn new(quantizer: GridQuantizer, extent: f32) -> Self {
    if !(extent > 0.0) {
      panic!("CellSpace extent must be positive");
    }
    let side = (extent / quantizer.cell_size()).ceil() as u32 + 1;
    Self { quantizer, side }
  }

  /// Cells along one axis.
  pub fn side(&self) -> u32 {
    self.side
  }

  /// How many cells the space holds, which is the length a keyed `Vec` needs.
  pub fn len(&self) -> usize {
    self.side as usize * self.side as usize
  }

  pub fn is_empty(&self) -> bool {
    self.side == 0
  }

  pub fn quantizer(&self) -> &GridQuantizer {
    &self.quantizer
  }

  /// The dense index of a cell, clamped into the space.
  ///
  /// Clamping matches [`GridQuantizer::cell`], which floors anything below the
  /// origin into cell 0. **A point outside the bounds is therefore filed at the
  /// edge rather than rejected**, so a space smaller than its world piles the
  /// outside into its border cells. Size it to the world.
  pub fn index_at(&self, cx: u32, cy: u32) -> usize {
    let last = self.side.saturating_sub(1);
    cy.min(last) as usize * self.side as usize + cx.min(last) as usize
  }

  /// The dense index of the cell a world point falls in.
  pub fn index_of(&self, x: f32, y: f32) -> usize {
    let (cx, cy) = self.quantizer.cell(x, y);
    self.index_at(cx, cy)
  }

  /// The cell coordinates an index names.
  pub fn cell_at(&self, index: usize) -> (u32, u32) {
    let side = self.side as usize;
    ((index % side) as u32, (index / side) as u32)
  }

  /// The world-space minimum corner of the cell an index names, for writing
  /// coordinates relative to their cell.
  pub fn corner(&self, index: usize) -> (f32, f32) {
    let (cx, cy) = self.cell_at(index);
    self.quantizer.corner(cx, cy)
  }

  /// The dense indices of every cell overlapping the square of half-width
  /// `radius` around `(x, y)`, deduplicated at the bounds.
  ///
  /// Cell-granular like every query here, so it reaches past the radius at the
  /// corners.
  pub fn indices_in_radius(&self, x: f32, y: f32, radius: f32) -> impl Iterator<Item = usize> + use<> {
    let (cx, cy) = self.quantizer.cell(x, y);
    let r = self.quantizer.cells_for_radius(radius);
    let last = self.side.saturating_sub(1);
    let (x0, x1) = (cx.saturating_sub(r).min(last), cx.saturating_add(r).min(last));
    let (y0, y1) = (cy.saturating_sub(r).min(last), cy.saturating_add(r).min(last));
    let side = self.side as usize;
    (y0..=y1).flat_map(move |gy| (x0..=x1).map(move |gx| gy as usize * side + gx as usize))
  }
}

/// A `Vec` keyed by [`CellSpace`], holding one `T` per cell.
///
/// The container half of the pair: `CellSpace` says which cell, this holds what
/// is in it. Reused rather than reallocated, so a table rebuilt every tick does
/// not churn the heap.
#[derive(Debug, Clone)]
pub struct CellTable<T> {
  space: CellSpace,
  slots: Vec<T>,
}

impl<T: Default> CellTable<T> {
  pub fn new(space: CellSpace) -> Self {
    let mut slots = Vec::new();
    slots.resize_with(space.len(), T::default);
    Self { space, slots }
  }

  /// Resets every cell to `T::default()`, keeping the allocation.
  ///
  /// For `T = Vec<_>` this also frees each cell's own capacity;
  /// [`clear_each`](Self::clear_each) keeps it.
  pub fn reset(&mut self) {
    for slot in self.slots.iter_mut() {
      *slot = T::default();
    }
  }
}

impl<T> CellTable<T> {
  pub fn space(&self) -> &CellSpace {
    &self.space
  }

  pub fn get(&self, index: usize) -> Option<&T> {
    self.slots.get(index)
  }

  pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
    self.slots.get_mut(index)
  }

  pub fn at(&self, x: f32, y: f32) -> Option<&T> {
    self.slots.get(self.space.index_of(x, y))
  }

  pub fn at_mut(&mut self, x: f32, y: f32) -> Option<&mut T> {
    let index = self.space.index_of(x, y);
    self.slots.get_mut(index)
  }

  pub fn iter(&self) -> impl Iterator<Item = (usize, &T)> {
    self.slots.iter().enumerate()
  }

  pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &mut T)> {
    self.slots.iter_mut().enumerate()
  }

  pub fn len(&self) -> usize {
    self.slots.len()
  }

  pub fn is_empty(&self) -> bool {
    self.slots.is_empty()
  }
}

impl<T: Clearable> CellTable<T> {
  /// Empties every cell while keeping each one's own allocation, which is what
  /// a per-tick rebuild of `Vec`-valued cells wants.
  pub fn clear_each(&mut self) {
    for slot in self.slots.iter_mut() {
      slot.clear_in_place();
    }
  }

  /// Every cell that is not empty, paired with its index.
  pub fn occupied(&self) -> impl Iterator<Item = (usize, &T)> {
    self.slots.iter().enumerate().filter(|(_, slot)| !slot.is_empty_slot())
  }
}

/// Emptied in place rather than replaced, so a per-tick rebuild keeps its
/// allocations. Implemented for the cell payload types that occur in practice.
pub trait Clearable {
  fn clear_in_place(&mut self);
  fn is_empty_slot(&self) -> bool;
}

impl<T> Clearable for Vec<T> {
  fn clear_in_place(&mut self) {
    self.clear();
  }
  fn is_empty_slot(&self) -> bool {
    self.is_empty()
  }
}

impl<T> Clearable for Option<T> {
  fn clear_in_place(&mut self) {
    *self = None;
  }
  fn is_empty_slot(&self) -> bool {
    self.is_none()
  }
}

/// Buckets entity ids into grid cells so a viewer can gather nearby ids without
/// scanning the world.
///
/// Rebuild it each tick ([`clear`](Self::clear) then [`insert`](Self::insert)
/// every entity); the buckets reuse their allocations across ticks, so a steady
/// entity count does not churn the heap. A query returns every id in the cells
/// overlapping the region, a *superset* of what is truly in range (cell-granular),
/// so apply an exact distance test afterward if you need one.
///
/// - `Id`: the entity handle (`u32` index, `u64`, `Uuid`, ...). `Copy`.
#[derive(Debug, Clone)]
pub struct SpatialGrid<Id: Copy> {
  quantizer: GridQuantizer,
  cells: HashMap<u64, Vec<Id>>,
}

impl<Id: Copy> SpatialGrid<Id> {
  pub fn new(quantizer: GridQuantizer) -> Self {
    Self {
      quantizer,
      cells: HashMap::new(),
    }
  }

  /// Empties every bucket but keeps their capacity, so the next tick's inserts do
  /// not reallocate. Call before re-inserting the world each tick.
  pub fn clear(&mut self) {
    for bucket in self.cells.values_mut() {
      bucket.clear();
    }
  }

  /// Files `id` under the cell its position falls in.
  pub fn insert(&mut self, id: Id, x: f32, y: f32) {
    let key = self.quantizer.key(x, y);
    self.cells.entry(key).or_default().push(id);
  }

  /// Appends to `out` every id in the cells overlapping the square of half-width
  /// `radius` around `(x, y)`. Cell-granular, so it can include ids just outside
  /// the radius; filter exactly afterward if that matters. `out` is not cleared,
  /// so a caller can gather several regions and reusing one `Vec` avoids
  /// allocating per query.
  pub fn query_radius(&self, x: f32, y: f32, radius: f32, out: &mut Vec<Id>) {
    for key in self.quantizer.keys_in_radius(x, y, radius) {
      out.extend_from_slice(self.members(key));
    }
  }

  /// The ids in one cell, by its Morton key. Empty for a cell nothing occupies.
  pub fn members(&self, key: u64) -> &[Id] {
    self.cells.get(&key).map_or(&[], Vec::as_slice)
  }

  /// Every occupied cell and its ids, in no particular order.
  ///
  /// Use it to build one payload per occupied cell, then hand each viewer the
  /// payloads for
  /// [`GridQuantizer::keys_in_radius`] of its position. Cells emptied by
  /// [`clear`](Self::clear) but not refilled are skipped.
  pub fn occupied(&self) -> impl Iterator<Item = (u64, &[Id])> {
    self
      .cells
      .iter()
      .filter(|(_, bucket)| !bucket.is_empty())
      .map(|(key, bucket)| (*key, bucket.as_slice()))
  }

  /// The quantizer this grid uses, for computing keys or cell spans directly.
  pub fn quantizer(&self) -> &GridQuantizer {
    &self.quantizer
  }
}

/// [`SpatialGrid`] for a world with known bounds: the same surface, with the
/// buckets in a flat `Vec` indexed by [`CellSpace`] instead of a `HashMap`
/// keyed by Morton code.
///
/// A cell lookup is an index rather than a hash, which is the cost that
/// dominates once thousands of entities are re-bucketed every tick and every
/// viewer's query walks its cell window. The hashed grid stays for a world
/// that is unbounded or sparse, where a table over every cell would mostly
/// hold nothing. `clear`, `insert`, `query_radius` and `quantizer` are spelled
/// the same on both, so a consumer swaps the type and its constructor and
/// nothing else; `members` and `occupied` name a cell by its dense index here
/// and by its Morton key there.
///
/// A position outside the space is filed in the border cell on that side,
/// matching [`CellSpace::index_of`], so size the space to the world.
///
/// The filled cells are listed as they fill, so `clear` and `occupied` walk
/// only those. Measure before swapping: on gow_3d's zone, a bounded world
/// that is sparsely filled at every population it runs at, this grid was
/// about twice as slow as the hashed one below 64 bodies, level at 1024 and
/// 4096 and a few percent faster only once the crowd packed. The hashed
/// grid's few buckets stay in cache where a table over every cell scatters
/// the filled ones, so this pays where most cells hold something.
#[derive(Debug, Clone)]
pub struct DenseGrid<Id: Copy> {
  cells: CellTable<Vec<Id>>,
  filled: Vec<usize>,
}

impl<Id: Copy> DenseGrid<Id> {
  pub fn new(space: CellSpace) -> Self {
    Self {
      cells: CellTable::new(space),
      filled: Vec::new(),
    }
  }

  /// Empties every filled cell but keeps each one's capacity. Call before
  /// re-inserting the world each tick.
  pub fn clear(&mut self) {
    for index in self.filled.drain(..) {
      if let Some(cell) = self.cells.get_mut(index) {
        cell.clear();
      }
    }
  }

  /// Files `id` under the cell its position falls in.
  pub fn insert(&mut self, id: Id, x: f32, y: f32) {
    let index = self.cells.space().index_of(x, y);
    if let Some(cell) = self.cells.get_mut(index) {
      if cell.is_empty() {
        self.filled.push(index);
      }
      cell.push(id);
    }
  }

  /// Appends to `out` every id in the cells overlapping the square of
  /// half-width `radius` around `(x, y)`. Cell-granular and not cleared, as
  /// [`SpatialGrid::query_radius`].
  pub fn query_radius(&self, x: f32, y: f32, radius: f32, out: &mut Vec<Id>) {
    for index in self.cells.space().indices_in_radius(x, y, radius) {
      out.extend_from_slice(self.members(index));
    }
  }

  /// The ids in one cell, by its dense index. Empty for a cell nothing
  /// occupies or an index outside the space.
  pub fn members(&self, index: usize) -> &[Id] {
    self.cells.get(index).map_or(&[], Vec::as_slice)
  }

  /// Every occupied cell and its ids, in the order the cells first filled
  /// since the last [`clear`](Self::clear).
  pub fn occupied(&self) -> impl Iterator<Item = (usize, &[Id])> {
    self.filled.iter().map(|&index| (index, self.members(index)))
  }

  pub fn space(&self) -> &CellSpace {
    self.cells.space()
  }

  pub fn quantizer(&self) -> &GridQuantizer {
    self.cells.space().quantizer()
  }
}

/// A membership boundary with hysteresis: it takes less distance to stay in
/// than to get in.
///
/// Any threshold that switches what the wire carries (a near tier at full
/// precision and rate against a far tier quantised and slow, a relevance
/// radius, an aggro range) flaps when an entity loiters on it: membership
/// changes every few frames and every change is a precision or rate step the
/// receiver has to absorb, visible as a peer marker twitching between two
/// qualities of motion. The fix is two radii with a gap, judged against where
/// the entity stood last time.
///
/// The memory is the caller's own previous membership set, which it already
/// keeps for diffing, so this costs no state: pass `was_inside` from it.
///
/// ```ignore
/// let tier = TierBoundary::new(VIEW_RADIUS * 1.3, VIEW_RADIUS * 1.5);
/// let was_near = previous.contains(&peer);
/// if tier.admits(was_near, peer_pos.dist(eye)) {
///   near.insert(peer);
/// }
/// ```
#[derive(Debug, Clone, Copy)]
pub struct TierBoundary {
  enter: f32,
  leave: f32,
}

impl TierBoundary {
  /// `enter` is the radius that admits a newcomer; `leave`, which must not be
  /// smaller, is the one past which a member is dropped. The gap between them
  /// is the loitering band, sized to the wobble the boundary actually sees
  /// (a step or two of movement per update interval).
  pub const fn new(enter: f32, leave: f32) -> Self {
    debug_assert!(enter <= leave, "hysteresis needs enter <= leave");
    Self {
      enter,
      leave: if leave < enter { enter } else { leave },
    }
  }

  /// Whether an entity at `distance` is a member this round, given whether it
  /// was one last round.
  pub fn admits(&self, was_inside: bool, distance: f32) -> bool {
    distance <= if was_inside { self.leave } else { self.enter }
  }
}

/// A dense bitset of which entities are visible to one client, with a fast diff
/// against the previous tick.
///
/// Interest management needs, per client, the set of entities in view and the
/// *change* since last tick: who [`entered`](Self::diff) (spawn it) and who
/// [`left`](Self::diff) (despawn it). With entities addressed by a dense `u32`
/// index (recycle indices for short-lived swarm entities, as in the horde case),
/// that set is a bitset and the diff is a word-at-a-time `new & !old` / `old & !new`
/// with no per-entity hashing.
///
/// For sparse handles (`Uuid`), map them to dense indices first or diff two
/// sorted id lists instead; this type is the dense-index fast path.
#[derive(Debug, Clone, Default)]
pub struct VisibilitySet {
  words: Vec<u64>,
}

impl VisibilitySet {
  pub fn new() -> Self {
    Self { words: Vec::new() }
  }

  /// Pre-sizes for entity indices up to `max_index`, so inserts up to it do not
  /// reallocate.
  pub fn with_capacity(max_index: u32) -> Self {
    Self {
      words: vec![0; (max_index as usize / 64) + 1],
    }
  }

  /// Empties the set but keeps its capacity, for reuse each tick.
  pub fn clear(&mut self) {
    for w in &mut self.words {
      *w = 0;
    }
  }

  /// Marks entity `index` visible.
  pub fn insert(&mut self, index: u32) {
    let (w, bit) = (index as usize / 64, index as usize % 64);
    if w >= self.words.len() {
      self.words.resize(w + 1, 0);
    }
    self.words[w] |= 1u64 << bit;
  }

  /// Marks entity `index` not visible.
  ///
  /// Useful when an entity is destroyed rather than merely leaving range: clear
  /// it explicitly so the next diff treats a *reused* slot as a fresh arrival
  /// instead of silently carrying the old occupant's membership forward.
  pub fn remove(&mut self, index: u32) {
    let (w, bit) = (index as usize / 64, index as usize % 64);
    if let Some(word) = self.words.get_mut(w) {
      *word &= !(1u64 << bit);
    }
  }

  /// Whether entity `index` is visible.
  pub fn contains(&self, index: u32) -> bool {
    let (w, bit) = (index as usize / 64, index as usize % 64);
    self.words.get(w).is_some_and(|word| word & (1u64 << bit) != 0)
  }

  /// The change from `previous` to `self`: appends newly-visible indices to
  /// `entered` (`self & !previous`) and no-longer-visible ones to `left`
  /// (`previous & !self`), each ascending. The vectors are not cleared, so reuse
  /// them across ticks to avoid allocating. This is the spawn/despawn stream.
  pub fn diff(&self, previous: &VisibilitySet, entered: &mut Vec<u32>, left: &mut Vec<u32>) {
    let n = self.words.len().max(previous.words.len());
    for w in 0..n {
      let cur = self.words.get(w).copied().unwrap_or(0);
      let prev = previous.words.get(w).copied().unwrap_or(0);
      emit_bits(cur & !prev, w, entered);
      emit_bits(prev & !cur, w, left);
    }
  }

  /// The visible indices, ascending.
  pub fn iter(&self) -> impl Iterator<Item = u32> + '_ {
    self.words.iter().enumerate().flat_map(|(w, &word)| BitIter { word, base: (w * 64) as u32 })
  }

  /// An order-independent digest of the visible indices, for checking that a
  /// client's mirror of this set still matches. See [`SetDigest`]; feed richer
  /// keys through that directly if membership alone is too weak a check.
  pub fn digest(&self) -> u64 {
    SetDigest::from_keys(self.iter().map(u64::from)).digest()
  }

  /// How many entities are visible.
  pub fn count(&self) -> usize {
    self.words.iter().map(|w| w.count_ones() as usize).sum()
  }

  #[cfg(test)]
  fn from_iter_for_test<I: IntoIterator<Item = u32>>(ids: I) -> Self {
    let mut v = Self::new();
    for i in ids {
      v.insert(i);
    }
    v
  }
}

// The digest is shared with the client crate so both sides run the same fold,
// which means a disagreement always reflects different sets. Re-exported here
// because this is where server code reaches for it.
pub use plaza_client_utils::digest::SetDigest;

/// Appends the set bit indices of `word` (in the `w`-th 64-bit block) to `out`.
fn emit_bits(mut word: u64, w: usize, out: &mut Vec<u32>) {
  let base = (w * 64) as u32;
  while word != 0 {
    out.push(base + word.trailing_zeros());
    word &= word - 1; // clear the lowest set bit
  }
}

/// Iterates the set bit indices of a single word.
struct BitIter {
  word: u64,
  base: u32,
}

impl Iterator for BitIter {
  type Item = u32;
  fn next(&mut self) -> Option<u32> {
    if self.word == 0 {
      return None;
    }
    let idx = self.base + self.word.trailing_zeros();
    self.word &= self.word - 1;
    Some(idx)
  }
}

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

  #[test]
  fn morton_2d_round_trips_across_the_range() {
    for &(x, y) in &[(0u32, 0u32), (1, 0), (0, 1), (12345, 67890), (u32::MAX, u32::MAX), (0xdead_beef, 0x0bad_f00d)] {
      let code = morton::encode_2d(x, y);
      assert_eq!(morton::decode_2d(code), (x, y), "2d round trip for ({x}, {y})");
    }
  }

  #[test]
  fn morton_3d_round_trips_within_21_bits() {
    let max21 = (1u32 << 21) - 1;
    for &(x, y, z) in &[(0u32, 0u32, 0u32), (1, 2, 3), (max21, max21, max21), (100_000, 5, 2_000_000)] {
      let code = morton::encode_3d(x, y, z);
      assert_eq!(morton::decode_3d(code), (x, y, z), "3d round trip for ({x}, {y}, {z})");
    }
  }

  #[test]
  fn morton_preserves_locality_within_a_cell_row() {
    // Adjacent cells on a row have codes that bracket their neighbours. A
    // Z-order curve is not a total order over 2D, but locality holds locally.
    let a = morton::encode_2d(10, 10);
    let b = morton::encode_2d(11, 10);
    let far = morton::encode_2d(10, 1000);
    assert!((a as i64 - b as i64).abs() < (a as i64 - far as i64).abs(), "neighbours are closer in code than a distant cell");
  }

  #[test]
  fn the_quantizer_maps_points_to_cells_and_clamps_below_the_origin() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    assert_eq!(q.cell(5.0, 5.0), (0, 0));
    assert_eq!(q.cell(15.0, 25.0), (1, 2));
    assert_eq!(q.cell(-4.0, -100.0), (0, 0), "below the origin clamps to cell 0");
    assert_eq!(q.cells_for_radius(25.0), 3, "25 world units spans 3 cells of 10");
  }

  #[test]
  #[should_panic]
  fn a_non_positive_cell_size_panics() {
    let _ = GridQuantizer::new((0.0, 0.0), 0.0);
  }

  #[test]
  fn the_grid_returns_ids_near_a_point_and_omits_distant_ones() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = SpatialGrid::new(q);
    grid.insert(1u32, 5.0, 5.0); // cell (0,0)
    grid.insert(2, 12.0, 5.0); // cell (1,0), adjacent
    grid.insert(3, 500.0, 500.0); // far away

    let mut out = Vec::new();
    grid.query_radius(5.0, 5.0, 10.0, &mut out); // one cell of slack each way
    assert!(out.contains(&1) && out.contains(&2), "near ids returned: {out:?}");
    assert!(!out.contains(&3), "distant id omitted");
  }

  #[test]
  fn clearing_the_grid_keeps_capacity_and_empties_buckets() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = SpatialGrid::new(q);
    grid.insert(1u32, 5.0, 5.0);
    grid.clear();
    let mut out = Vec::new();
    grid.query_radius(5.0, 5.0, 10.0, &mut out);
    assert!(out.is_empty(), "cleared grid returns nothing");
  }

  #[test]
  fn keys_in_radius_walks_the_window_query_radius_reads() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let keys: Vec<u64> = q.keys_in_radius(25.0, 25.0, 10.0).collect();
    assert_eq!(keys.len(), 9, "one cell of slack each way around (2,2): {keys:?}");
    for gx in 1..=3u32 {
      for gy in 1..=3u32 {
        assert!(keys.contains(&morton::encode_2d(gx, gy)), "missing cell ({gx},{gy})");
      }
    }
    let clamped: Vec<u64> = q.keys_in_radius(5.0, 5.0, 10.0).collect();
    assert_eq!(clamped.len(), 4, "the window clamps at the origin: {clamped:?}");
  }

  #[test]
  fn a_cell_first_pass_reaches_everyone_a_viewer_first_pass_does() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = SpatialGrid::new(q);
    for (id, x, y) in [(1u32, 5.0, 5.0), (2, 12.0, 5.0), (3, 500.0, 500.0)] {
      grid.insert(id, x, y);
    }

    let placed: usize = grid.occupied().map(|(_, ids)| ids.len()).count();
    assert_eq!(placed, 3, "three ids in three cells");
    assert_eq!(grid.members(q.key(12.0, 5.0)), &[2]);
    assert!(grid.members(q.key(50.0, 50.0)).is_empty(), "a vacant cell is empty, not an error");

    let mut viewer_first = Vec::new();
    grid.query_radius(5.0, 5.0, 10.0, &mut viewer_first);
    let mut cell_first: Vec<u32> = q
      .keys_in_radius(5.0, 5.0, 10.0)
      .flat_map(|key| grid.members(key).iter().copied())
      .collect();
    viewer_first.sort_unstable();
    cell_first.sort_unstable();
    assert_eq!(viewer_first, cell_first);
  }

  #[test]
  fn a_cell_space_indexes_the_same_cells_the_quantizer_names() {
    let q = GridQuantizer::new((-100.0, -100.0), 10.0);
    let space = CellSpace::new(q, 200.0);
    assert_eq!(space.side(), 21);
    assert_eq!(space.len(), 441);

    let index = space.index_of(-95.0, -95.0);
    assert_eq!(space.cell_at(index), q.cell(-95.0, -95.0));
    assert_eq!(space.corner(index), (-100.0, -100.0));

    // Out of bounds files at the edge rather than out of range, matching the
    // quantizer's own clamp, which is why a space must be sized to its world.
    let far = space.index_of(9000.0, 9000.0);
    assert!(far < space.len());
    assert_eq!(space.cell_at(far), (20, 20));
  }

  #[test]
  fn a_dense_window_agrees_with_the_morton_one() {
    let q = GridQuantizer::new((-100.0, -100.0), 10.0);
    let space = CellSpace::new(q, 200.0);

    let dense: Vec<(u32, u32)> = space.indices_in_radius(0.0, 0.0, 10.0).map(|i| space.cell_at(i)).collect();
    let sparse: Vec<(u32, u32)> = q.cells_in_radius(0.0, 0.0, 10.0).collect();
    assert_eq!(dense, sparse, "the two addressing schemes walk the same cells");
    assert_eq!(dense.len(), 9);
  }

  #[test]
  fn one_cell_space_keys_the_three_tables_a_publisher_needs() {
    // Publishing per cell needs entities by cell, a payload by cell and the
    // inverse index of who is listening to each cell. All three use the same
    // addressing.
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let space = CellSpace::new(q, 100.0);

    let mut bodies: CellTable<Vec<u32>> = CellTable::new(space);
    let mut payloads: CellTable<Option<Vec<u8>>> = CellTable::new(space);
    let mut audience: CellTable<Vec<u16>> = CellTable::new(space);

    bodies.clear_each();
    for (id, x, y) in [(1u32, 5.0, 5.0), (2, 7.0, 5.0), (3, 55.0, 55.0)] {
      bodies.at_mut(x, y).unwrap().push(id);
    }
    assert_eq!(bodies.occupied().count(), 2, "two cells hold anything");

    payloads.clear_each();
    for (index, ids) in bodies.occupied() {
      payloads.get_mut(index).unwrap().replace(ids.iter().map(|i| *i as u8).collect());
    }
    assert_eq!(payloads.occupied().count(), 2);

    audience.clear_each();
    for (viewer, x, y) in [(10u16, 5.0, 5.0), (11, 55.0, 55.0)] {
      for index in space.indices_in_radius(x, y, 10.0) {
        if payloads.get(index).is_some_and(|p| p.is_some()) {
          audience.get_mut(index).unwrap().push(viewer);
        }
      }
    }
    let listeners: usize = audience.occupied().map(|(_, v)| v.len()).sum();
    assert_eq!(listeners, 2, "each viewer hears the one occupied cell it stands in");
    assert_eq!(audience.at(5.0, 5.0).unwrap(), &[10]);
  }

  #[test]
  fn clearing_a_table_keeps_each_cell_s_allocation() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut table: CellTable<Vec<u32>> = CellTable::new(CellSpace::new(q, 100.0));
    let index = table.space().index_of(5.0, 5.0);
    table.get_mut(index).unwrap().extend([1, 2, 3, 4]);
    let capacity = table.get(index).unwrap().capacity();

    table.clear_each();
    assert!(table.get(index).unwrap().is_empty());
    assert_eq!(table.get(index).unwrap().capacity(), capacity, "a rebuild must not churn the heap");
    assert_eq!(table.occupied().count(), 0);
  }

  #[test]
  #[should_panic(expected = "extent must be positive")]
  fn a_cell_space_needs_an_extent() {
    CellSpace::new(GridQuantizer::new((0.0, 0.0), 10.0), 0.0);
  }

  #[test]
  fn occupied_skips_buckets_a_clear_emptied() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = SpatialGrid::new(q);
    grid.insert(1u32, 5.0, 5.0);
    grid.insert(2, 25.0, 25.0);
    grid.clear();
    grid.insert(3u32, 25.0, 25.0);
    let cells: Vec<(u64, Vec<u32>)> = grid.occupied().map(|(k, ids)| (k, ids.to_vec())).collect();
    assert_eq!(cells, vec![(q.key(25.0, 25.0), vec![3])]);
  }

  #[test]
  fn a_visibility_set_inserts_and_contains() {
    let mut v = VisibilitySet::new();
    v.insert(3);
    v.insert(70); // second word
    assert!(v.contains(3) && v.contains(70));
    assert!(!v.contains(4));
    assert_eq!(v.count(), 2);
    let seen: Vec<u32> = v.iter().collect();
    assert_eq!(seen, vec![3, 70], "iterates ascending across words");
  }

  #[test]
  fn a_digest_ignores_order_but_not_contents() {
    let a = SetDigest::from_keys([7u64, 1, 99, 4]);
    let b = SetDigest::from_keys([99u64, 4, 7, 1]);
    assert_eq!(a.digest(), b.digest(), "the same set in a different order agrees");

    let c = SetDigest::from_keys([7u64, 1, 99, 5]);
    assert_ne!(a.digest(), c.digest(), "a different member disagrees");

    let d = SetDigest::from_keys([7u64, 1, 99]);
    assert_ne!(a.digest(), d.digest(), "a missing member disagrees");
  }

  #[test]
  fn maintaining_a_digest_incrementally_matches_rebuilding_it() {
    let mut live = SetDigest::new();
    for k in [3u64, 9, 21, 40] {
      live.insert(k);
    }
    live.remove(9);
    live.insert(77);

    let rebuilt = SetDigest::from_keys([3u64, 21, 40, 77]);
    assert_eq!(live.digest(), rebuilt.digest(), "O(1) updates agree with a full rebuild");
    assert_eq!(live.len(), 4);
  }

  #[test]
  fn a_delta_that_never_landed_is_detectable() {
    // The server removed an entity, the client never applied it and nothing
    // else about the client looks wrong.
    let mut server = SetDigest::from_keys([1u64, 2, 3, 4]);
    let client = SetDigest::from_keys([1u64, 2, 3, 4]);
    assert_eq!(server.digest(), client.digest());

    server.remove(3); // the client misses this despawn
    assert_ne!(server.digest(), client.digest(), "the mirror is stale and it shows");
  }

  #[test]
  fn a_visibility_set_digest_tracks_its_membership() {
    let mut v = VisibilitySet::new();
    for i in [2u32, 8, 300] {
      v.insert(i);
    }
    let before = v.digest();
    v.remove(8);
    assert_ne!(before, v.digest());

    let same = VisibilitySet::from_iter_for_test([2u32, 300]);
    assert_eq!(v.digest(), same.digest(), "membership alone decides the digest");
  }

  #[test]
  fn removing_clears_a_bit_so_a_reused_slot_reads_as_a_fresh_arrival() {
    let mut v = VisibilitySet::new();
    v.insert(5);
    v.remove(5);
    assert!(!v.contains(5));

    // With the bit cleared, the next diff sees 5 as newly visible rather than
    // carrying the dead occupant's membership forward.
    let mut next = VisibilitySet::new();
    next.insert(5);
    let (mut entered, mut left) = (Vec::new(), Vec::new());
    next.diff(&v, &mut entered, &mut left);
    assert_eq!(entered, vec![5]);
    assert!(left.is_empty());
  }

  #[test]
  fn the_visibility_diff_reports_spawns_and_despawns() {
    // Previous tick saw {1, 2, 3}; this tick sees {2, 3, 4, 100}.
    let mut prev = VisibilitySet::new();
    for i in [1, 2, 3] {
      prev.insert(i);
    }
    let mut cur = VisibilitySet::new();
    for i in [2, 3, 4, 100] {
      cur.insert(i);
    }

    let (mut entered, mut left) = (Vec::new(), Vec::new());
    cur.diff(&prev, &mut entered, &mut left);
    assert_eq!(entered, vec![4, 100], "newly visible: spawn these");
    assert_eq!(left, vec![1], "no longer visible: despawn these");
  }

  #[test]
  fn a_full_relevance_pass_matches_a_brute_force_check() {
    // The grid query plus an exact distance test should select exactly the ids a
    // naive all-pairs scan would, for a random-ish spread of entities.
    let q = GridQuantizer::new((0.0, 0.0), 32.0);
    let mut grid = SpatialGrid::new(q);
    let radius = 50.0;

    // Deterministic pseudo-spread of 200 entities over a 1000x1000 field.
    let entities: Vec<(u32, f32, f32)> = (0..200u32)
      .map(|i| {
        let x = ((i * 73 % 1000) as f32) + 0.5;
        let y = ((i * 149 % 1000) as f32) + 0.5;
        (i, x, y)
      })
      .collect();
    for &(id, x, y) in &entities {
      grid.insert(id, x, y);
    }

    let (vx, vy) = (500.0f32, 500.0f32); // a viewer in the middle
    let brute: std::collections::BTreeSet<u32> = entities
      .iter()
      .filter(|(_, x, y)| ((x - vx).powi(2) + (y - vy).powi(2)).sqrt() <= radius)
      .map(|(id, _, _)| *id)
      .collect();

    // Grid gathers a cell-granular superset; the exact test narrows it.
    let mut candidates = Vec::new();
    grid.query_radius(vx, vy, radius, &mut candidates);
    let grid_result: std::collections::BTreeSet<u32> = candidates
      .into_iter()
      .filter(|id| {
        let (_, x, y) = entities[*id as usize];
        ((x - vx).powi(2) + (y - vy).powi(2)).sqrt() <= radius
      })
      .collect();

    assert_eq!(grid_result, brute, "grid + exact test equals brute force");
  }

  #[test]
  fn a_peer_loitering_on_the_boundary_does_not_flap() {
    // Wobbling a step either side of one radius must not change membership.
    let tier = TierBoundary::new(100.0, 120.0);

    // A member wobbling between the two radii stays a member...
    assert!(tier.admits(true, 110.0));
    assert!(tier.admits(true, 119.0));
    // ...and a non-member in the same band stays out.
    assert!(!tier.admits(false, 110.0));
    assert!(!tier.admits(false, 101.0));

    // Only a real approach admits, and only a real departure drops.
    assert!(tier.admits(false, 99.0));
    assert!(!tier.admits(true, 121.0));
  }

  #[test]
  fn the_dense_grid_answers_what_the_hashed_one_answers() {
    let q = GridQuantizer::new((-100.0, -100.0), 10.0);
    let mut hashed = SpatialGrid::new(q);
    let mut dense = DenseGrid::new(CellSpace::new(q, 200.0));
    for id in 0..400u32 {
      let (x, y) = (-100.0 + (id % 20) as f32 * 10.3, -100.0 + (id / 20) as f32 * 9.7 + 0.5);
      hashed.insert(id, x, y);
      dense.insert(id, x, y);
    }

    for (x, y) in [(0.0, 0.0), (-95.0, -95.0), (95.0, 95.0), (33.3, -12.0)] {
      let (mut from_hashed, mut from_dense) = (Vec::new(), Vec::new());
      hashed.query_radius(x, y, 15.0, &mut from_hashed);
      dense.query_radius(x, y, 15.0, &mut from_dense);
      from_hashed.sort_unstable();
      from_dense.sort_unstable();
      assert!(!from_dense.is_empty(), "query at ({x}, {y}) found nobody");
      assert_eq!(from_dense, from_hashed, "query at ({x}, {y})");
    }
    assert_eq!(dense.occupied().count(), hashed.occupied().count());
  }

  #[test]
  fn clearing_the_dense_grid_keeps_each_cell_s_capacity() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = DenseGrid::new(CellSpace::new(q, 100.0));
    for id in 0..8u32 {
      grid.insert(id, 5.0, 5.0);
    }
    let index = grid.space().index_of(5.0, 5.0);
    let capacity = grid.cells.get(index).unwrap().capacity();

    grid.clear();
    assert!(grid.members(index).is_empty());
    assert_eq!(grid.cells.get(index).unwrap().capacity(), capacity, "a rebuild must not churn the heap");
    assert_eq!(grid.occupied().count(), 0);
    assert!(grid.cells.occupied().count() == 0, "the table itself is empty, not only the list");
    let mut out = Vec::new();
    grid.query_radius(5.0, 5.0, 10.0, &mut out);
    assert!(out.is_empty());

    grid.insert(9, 5.0, 5.0);
    grid.insert(10, 5.0, 5.0);
    grid.insert(11, 95.0, 95.0);
    let cells: Vec<usize> = grid.occupied().map(|(index, _)| index).collect();
    assert_eq!(cells, vec![index, grid.space().index_of(95.0, 95.0)], "each filled cell listed once, as it filled");
  }

  #[test]
  fn a_point_outside_the_space_is_filed_at_the_edge_and_found_there() {
    let q = GridQuantizer::new((0.0, 0.0), 10.0);
    let mut grid = DenseGrid::new(CellSpace::new(q, 100.0));
    grid.insert(1u32, 5000.0, 5000.0);
    grid.insert(2, -50.0, -50.0);

    let last = grid.space().side() - 1;
    assert_eq!(grid.members(grid.space().index_at(last, last)), &[1]);
    assert_eq!(grid.members(grid.space().index_at(0, 0)), &[2]);
    assert!(grid.members(grid.space().len()).is_empty(), "an index past the space is empty, not a panic");

    let mut out = Vec::new();
    grid.query_radius(100.0, 100.0, 5.0, &mut out);
    assert_eq!(out, vec![1], "a query at the edge reaches the border cell");
  }
}