frienderer 0.13.0

//! My own quad-tree texture atlas implementation.

use std::{num::NonZeroU32, time::Instant};

use glam::{U8Vec2, UVec2, UVec4, Vec2, Vec4, uvec2};
use rustc_hash::FxHashMap;
use swash::{GlyphId, zeno::Placement};

use crate::batch::HyperQuad;

use super::{DrawCommand, RawImage};

/// A texture allocated on a texture atlas.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[repr(C)]
pub struct Land {
	pub pos: UVec2,
	pub size: UVec2,
}

/// UV coordinates and size of an allocated land.
#[derive(Debug, Clone, Copy)]
#[repr(C)]
pub struct LandUv {
	pub pos: Vec2,
	pub size: Vec2,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct QuadNodeId(NonZeroU32);

#[derive(Debug, Clone, Copy)]
enum QuadSlot {
	Free {
		// intrusive linked list of free slots per level
		prev_free: Option<QuadNodeId>,
		next_free: Option<QuadNodeId>,
	},
	Branch {
		children: [[QuadNodeId; 2]; 2],
	},
	Glyph {
		key: GlyphKey,
		size: UVec2,
	},
}

#[derive(Debug, Clone, Copy)]
struct QuadNode {
	/// This serves as the parent when the node is in use,
	/// and as the link to the next free node when it is not.
	parent_or_next_free: Option<QuadNodeId>,
	pos: UVec2,
	size: UVec2,
	slot: QuadSlot,

	// intrusive linked list of nodes per priority
	prev_priority: Option<QuadNodeId>,
	next_priority: Option<QuadNodeId>,
	last_frame: u64,
}

#[derive(Debug, Clone, Copy)]
pub enum InsertGlyphError {
	/// The image is completely empty.
	EmptyImage,
	/// The glyph is bigger than the entire atlas.
	TooBig,
	/// No space left on the atlas.
	NoSpaceLeft,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct GlyphKey {
	pub id: GlyphId,
	pub quantization: U8Vec2,
	pub style_hash: u32,
}

#[derive(Debug, Clone, Copy)]
pub struct GlyphCacheEntry {
	quad_node_id: QuadNodeId,
	pub placement: Placement,
	pub is_colored: bool,
	pub level: u32,
	pub created: Instant,
}

/// A glyph atlas that allocates with a quad tree LRU cache.
pub struct Quadlas {
	size: u32,
	max_texture_size: u32,

	quad_tree: Vec<QuadNode>,
	first_unoccupied_node: Option<QuadNodeId>,
	first_free_slot_per_level: Box<[Option<QuadNodeId>; 16]>,
	first_priority_slot_per_level: Box<[Option<QuadNodeId>; 16]>,
	last_priority_slot_per_level: Box<[Option<QuadNodeId>; 16]>,
	glyph_cache: FxHashMap<GlyphKey, GlyphCacheEntry>,
}

impl Quadlas {
	pub fn new(max_texture_size: u32, size: u32) -> Self {
		let mut quadlas = Self {
			size,
			max_texture_size,

			quad_tree: Vec::new(),
			first_unoccupied_node: None,
			first_free_slot_per_level: Box::default(),
			first_priority_slot_per_level: Box::default(),
			last_priority_slot_per_level: Box::default(),
			glyph_cache: FxHashMap::default(),
		};

		quadlas.clear_with_size(size);
		quadlas
	}

	pub fn size(&self) -> u32 {
		self.size
	}

	/// Subdivide a quad node into 4 new ones
	fn subdivide_quad_node(&mut self, id: QuadNodeId, level: u32) -> [[QuadNodeId; 2]; 2] {
		/// Push a new free node to the quad tree
		fn push_quad_node(
			quadlas: &mut Quadlas,
			parent: QuadNodeId,
			parent_level: u32,
			pos: UVec2,
			size: u32,
		) -> QuadNodeId {
			let new_node = QuadNode {
				parent_or_next_free: Some(parent),
				pos,
				size: UVec2::splat(size),
				slot: QuadSlot::Free {
					prev_free: None,
					next_free: None,
				},
				prev_priority: None,
				next_priority: None,
				last_frame: 0,
			};

			let id = if let Some(first_unoccupied_node_id) = quadlas.first_unoccupied_node {
				let unoccupied = quadlas.quad_node_mut(first_unoccupied_node_id);
				let next_unoccupied = unoccupied.parent_or_next_free;
				*unoccupied = new_node;
				quadlas.first_unoccupied_node = next_unoccupied;
				first_unoccupied_node_id
			} else {
				quadlas.quad_tree.push(new_node);
				QuadNodeId(NonZeroU32::new(quadlas.quad_tree.len() as u32).unwrap())
			};

			quadlas.push_free_slot(id, parent_level + 1);

			id
		}

		let size = self.size / 2_u32.pow(level + 1);
		let pos = self.quad_node(id).pos;

		// push 4 nodes to the quad tree with adjacent positions
		let qnbr = push_quad_node(self, id, level, pos + size * uvec2(1, 1), size); // ↘
		let qnbl = push_quad_node(self, id, level, pos + size * uvec2(0, 1), size); // ↙
		let qntr = push_quad_node(self, id, level, pos + size * uvec2(1, 0), size); // ↗
		let qntl = push_quad_node(self, id, level, pos + size * uvec2(0, 0), size); // ↖

		let children = [[qntl, qntr], [qnbl, qnbr]];
		self.quad_node_mut(id).slot = QuadSlot::Branch { children };

		children
	}

	/// Make this node into a free slot. If it is a branch, unoccupy all its child nodes.
	fn erase_node(&mut self, id: QuadNodeId, level: u32) {
		match self.quad_node_mut(id).slot {
			QuadSlot::Branch { children } => {
				for child_row in children {
					for child_id in child_row {
						self.erase_node(child_id, level + 1);

						// make child unoccupied
						self.quad_node_mut(child_id).parent_or_next_free = self.first_unoccupied_node;
						self.first_unoccupied_node = Some(child_id);

						// remove child from free list
						self.remove_free_slot(child_id, level + 1);
					}
				}
			}

			QuadSlot::Free { .. } => {
				// nothing to do
				return;
			}

			QuadSlot::Glyph { key, .. } => {
				self.glyph_cache.remove(&key);
			}
		}

		self.remove_priority_slot(id, level);

		// replace with free slot
		let next_free = self.first_free_slot_per_level[level as usize];
		self.quad_node_mut(id).slot = QuadSlot::Free {
			prev_free: None,
			next_free,
		};
		self.first_free_slot_per_level[level as usize] = Some(id);
	}

	pub fn to_land_uv(&self, land: Land) -> LandUv {
		LandUv {
			pos: land.pos.as_vec2() / self.size as f32,
			size: land.size.as_vec2() / self.size as f32,
		}
	}

	fn quad_node(&self, id: QuadNodeId) -> &QuadNode {
		&self.quad_tree[id.0.get() as usize - 1]
	}

	fn quad_node_mut(&mut self, id: QuadNodeId) -> &mut QuadNode {
		&mut self.quad_tree[id.0.get() as usize - 1]
	}
}

///////////////////////
// Glyph management

impl Quadlas {
	pub fn get_cached_glyph(
		&mut self,
		glyph_key: GlyphKey,
		land_padding: u32,
		current_frame: u64,
	) -> Option<(Land, GlyphCacheEntry)> {
		if let Some(&gce) = self.glyph_cache.get(&glyph_key) {
			let quad_node = self.quad_node_mut(gce.quad_node_id);

			let QuadSlot::Glyph { size, .. } = quad_node.slot else {
				panic!("non-glyph was inserted into the glyph cache");
			};

			let pos = quad_node.pos + land_padding;

			self.update_priority(gce.quad_node_id, gce.level, current_frame);

			Some((Land { pos, size }, gce))
		} else {
			None
		}
	}

	/// Inserts a glyph onto the atlas if it wasn't already present.
	/// Returns whether it successfully inserted the texture.
	/// It notably fails:
	/// - if all places of the atlas are occupied with priority-0 glyphs,
	/// - if a single glyph is bigger than the atlas itself (rare).
	pub fn insert_glyph_unless_cached(
		&mut self,
		glyph_key: GlyphKey,
		placement: Placement,
		is_colored: bool,
		image: RawImage,
		land_padding: u32,
		current_frame: u64,
	) -> Result<(Land, GlyphCacheEntry), InsertGlyphError> {
		if let Some(glyph_data) = self.get_cached_glyph(glyph_key, land_padding, current_frame) {
			return Ok(glyph_data);
		}

		let image_size = image.width.max(image.height) + 2 * land_padding;
		if image_size == 0 {
			return Err(InsertGlyphError::EmptyImage);
		}
		if image_size > self.size {
			return Err(InsertGlyphError::TooBig);
		}

		// get level at which the image is going to be stored
		let image_level = {
			let mut curr_size = self.size;
			let mut curr_level = 0;
			while curr_size / 2 >= image_size {
				curr_size /= 2;
				curr_level += 1;
			}
			curr_level
		};

		// get first free slot
		let glyph_node_id = match self.pop_free_slot_le_level(image_level) {
			Some(glyph_node_id) => glyph_node_id,
			None => {
				// get first least-priority slot that's not in the current frame
				self.free_last_priority_slot(image_level, current_frame);

				match self.pop_free_slot_le_level(image_level) {
					Some(glyph_node_id) => glyph_node_id,
					None => return Err(InsertGlyphError::NoSpaceLeft),
				}
			}
		};

		// make that slot into a glyph
		let size = uvec2(image.width, image.height);

		let node = self.quad_node_mut(glyph_node_id);
		node.slot = QuadSlot::Glyph { key: glyph_key, size };
		let pos = node.pos + land_padding;

		self.update_priority(glyph_node_id, image_level, current_frame);

		let glyph_cache_entry = GlyphCacheEntry {
			quad_node_id: glyph_node_id,
			placement,
			is_colored,
			level: image_level,
			created: Instant::now(),
		};

		// update glyph cache
		self.glyph_cache.insert(glyph_key, glyph_cache_entry);

		Ok((Land { pos, size }, glyph_cache_entry))
	}

	pub fn grow(&mut self) {
		self.clear_with_size(self.size * 2);
	}

	pub fn clear_with_size(&mut self, size: u32) {
		self.quad_tree.clear();
		self.first_unoccupied_node = None;
		self.first_free_slot_per_level.iter_mut().for_each(|s| *s = None);
		self.first_priority_slot_per_level.iter_mut().for_each(|s| *s = None);
		self.last_priority_slot_per_level.iter_mut().for_each(|s| *s = None);
		self.glyph_cache.clear();

		self.size = size.min(self.max_texture_size);

		self.quad_tree.push(QuadNode {
			parent_or_next_free: None,
			pos: UVec2::ZERO,
			size: UVec2::splat(self.size),
			slot: QuadSlot::Free {
				prev_free: None,
				next_free: None,
			},
			prev_priority: None,
			next_priority: None,
			last_frame: 0,
		});

		self.first_free_slot_per_level[0] = Some(QuadNodeId(NonZeroU32::MIN));
	}
}

///////////////////////////////
// Priority list management

impl Quadlas {
	/// Push a slot to the head of the priority list.
	/// This is a typical doubly linked list push-front operation.
	fn push_priority_slot(&mut self, id: QuadNodeId, level: u32, current_frame: u64) {
		let mut next_priority_slot = None;

		// set next node's prev to this node
		if let Some(first_priority_slot) = (self.first_priority_slot_per_level)[level as usize] {
			next_priority_slot = Some(first_priority_slot);

			self.quad_node_mut(first_priority_slot).prev_priority = Some(id);
		}

		{
			let node = self.quad_node_mut(id);

			// set this node's next to next node
			node.next_priority = next_priority_slot;

			// update node's last frame
			node.last_frame = current_frame;
		}

		// overwrite hashmap's first slot
		if self.first_priority_slot_per_level[level as usize].replace(id).is_none() {
			// overwrite hashmap's last slot if the list was empty
			self.last_priority_slot_per_level[level as usize] = Some(id);
		}
	}

	/// Remove a slot from anywhere in the priority list.
	/// This is a typical doubly linked list entry removal operation.
	fn remove_priority_slot(&mut self, priority_slot: QuadNodeId, level: u32) {
		// empty current node's prev and next
		let (prev_priority, next_priority) = {
			let node = self.quad_node_mut(priority_slot);
			(node.prev_priority.take(), node.next_priority.take())
		};

		// set next node's prev to current node's prev
		if let Some(next_priority) = next_priority {
			self.quad_node_mut(next_priority).prev_priority = prev_priority;
		}

		// set prev node's next to current node's next
		if let Some(prev_priority) = prev_priority {
			self.quad_node_mut(prev_priority).next_priority = next_priority;
		}

		// update first node in hashmap
		if (self.first_priority_slot_per_level)[level as usize] == Some(priority_slot) {
			if let Some(next_priority) = next_priority {
				self.first_priority_slot_per_level[level as usize] = Some(next_priority);
			} else {
				self.first_priority_slot_per_level[level as usize] = None;
			};
		}

		// update last node in hashmap
		if (self.last_priority_slot_per_level)[level as usize] == Some(priority_slot) {
			if let Some(prev_priority) = prev_priority {
				self.last_priority_slot_per_level[level as usize] = Some(prev_priority);
			} else {
				self.last_priority_slot_per_level[level as usize] = None;
			};
		}
	}

	fn update_priority(&mut self, priority_slot: QuadNodeId, level: u32, current_frame: u64) {
		// update node's and parent nodes' priorities
		let mut parent_id = Some(priority_slot);
		let mut level = level + 1;
		while let Some(node_id) = parent_id {
			level -= 1;

			self.remove_priority_slot(node_id, level);
			self.push_priority_slot(node_id, level, current_frame);

			parent_id = self.quad_node_mut(node_id).parent_or_next_free;
		}
	}

	fn free_last_priority_slot(&mut self, level: u32, current_frame: u64) {
		let mut avail_level = level;
		let avail_slot_id = loop {
			if let Some(last_slot_id) = self.last_priority_slot_per_level[avail_level as usize] {
				let last_slot = self.quad_node(last_slot_id);
				if last_slot.last_frame < current_frame {
					break last_slot_id;
				}
			}

			if avail_level == 0 {
				return;
			}

			avail_level -= 1;
		};

		self.erase_node(avail_slot_id, avail_level);
	}
}

///////////////////////////
// Free list management

impl Quadlas {
	/// Pushes a free slot into the intrusive free slot linked list.
	fn push_free_slot(&mut self, id: QuadNodeId, level: u32) {
		let mut next_free_slot = None;

		// set next node's prev to this node
		if let Some(free_slot) = self.first_free_slot_per_level[level as usize] {
			next_free_slot = Some(free_slot);

			match &mut self.quad_node_mut(free_slot).slot {
				QuadSlot::Free { prev_free, .. } => *prev_free = Some(id),
				_ => panic!("Supposed free slot is not of variant QuadSlot::Free"),
			}
		}

		// set this node's next to next node
		match &mut self.quad_node_mut(id).slot {
			QuadSlot::Free { next_free, .. } => *next_free = next_free_slot,
			_ => panic!("Supposed free slot is not of variant QuadSlot::Free"),
		};

		// overwrite hashmap's first slot
		self.first_free_slot_per_level[level as usize] = Some(id);
	}

	/// Removes a slot from the free list.
	/// This is a typical linked list entry removal operation.
	fn remove_free_slot(&mut self, free_slot: QuadNodeId, level: u32) {
		// empty current node's prev and next
		let (curr_prev_free, curr_next_free) = match &mut self.quad_node_mut(free_slot).slot {
			QuadSlot::Free { prev_free, next_free } => (prev_free.take(), next_free.take()),
			_ => panic!("Supposed free slot is not of variant QuadSlot::Free"),
		};

		// set next node's prev to current node's prev
		if let Some(curr_next_free) = curr_next_free {
			match &mut self.quad_node_mut(curr_next_free).slot {
				QuadSlot::Free { prev_free, .. } => *prev_free = curr_prev_free,
				_ => panic!("Supposed free slot is not of variant QuadSlot::Free"),
			};
		}

		// set prev node's next to current node's next
		if let Some(curr_prev_free) = curr_prev_free {
			match &mut self.quad_node_mut(curr_prev_free).slot {
				QuadSlot::Free { next_free, .. } => *next_free = curr_next_free,
				_ => panic!("Supposed free slot is not of variant QuadSlot::Free"),
			};
		}

		// update first node in hashmap
		if self.first_free_slot_per_level[level as usize] == Some(free_slot) {
			self.first_free_slot_per_level[level as usize] = curr_next_free;
		}
	}

	/// Gets the first free slot at that level.
	/// If none exist, it tries to find a free slot of lower level to subdivide it.
	fn pop_free_slot_le_level(&mut self, level: u32) -> Option<QuadNodeId> {
		// Note: the level is never going to be higher than 16
		// (that would imply a texture of size 65536x65536),
		// so this loop is cheap.
		let mut curr_level = level;
		loop {
			if let Some(mut free_slot) = self.first_free_slot_per_level[curr_level as usize] {
				// subdivide until we get to the desired level
				while curr_level < level {
					// remove slot from free list before subdividing (it gets transformed into a branch afterwards)
					self.remove_free_slot(free_slot, curr_level);

					free_slot = self.subdivide_quad_node(free_slot, curr_level)[0][0];
					curr_level += 1;
				}

				self.remove_free_slot(free_slot, level);

				return Some(free_slot);
			}

			if curr_level == 0 {
				// no free slots available
				return None;
			}

			curr_level -= 1;
		}
	}
}

////////////////
// Debugging

#[allow(unused)]
impl Quadlas {
	#[allow(unused)]
	fn debug_free_list(&self, level: u32) {
		let mut s = format!("Free list (L{}): ", level);

		if let Some(free_slot) = self.first_free_slot_per_level[level as usize] {
			let mut i_free_slot = Some(free_slot);

			while let Some(free_slot) = i_free_slot {
				s += match &self.quad_node(free_slot).slot {
					QuadSlot::Free { next_free, .. } => {
						i_free_slot = *next_free;
						"F"
					}
					QuadSlot::Branch { .. } => {
						i_free_slot = None;
						"B??"
					}
					QuadSlot::Glyph { .. } => {
						i_free_slot = None;
						"G??"
					}
				};

				s += " > ";
			}
		}

		s += "()";

		#[cfg(feature = "logging")]
		tracing::info!("{}", s);
		#[cfg(not(feature = "logging"))]
		eprintln!("{}", s);
	}

	pub fn debug_view(&self, draw_commands: &mut Vec<DrawCommand>, pos_offset: Vec2, quad_size: Vec2) {
		let factor = quad_size / self.size as f32;
		self.debug_node_view(draw_commands, QuadNodeId(NonZeroU32::MIN), pos_offset, factor);
	}

	fn debug_node_view(&self, draw_commands: &mut Vec<DrawCommand>, id: QuadNodeId, pos_offset: Vec2, factor: Vec2) {
		let QuadNode { pos, size, slot, .. } = *self.quad_node(id);

		match slot {
			QuadSlot::Free { .. } => {
				// draw nothing
			}

			QuadSlot::Branch { children } => {
				draw_commands.push(DrawCommand::Quad(HyperQuad {
					pos: pos_offset + pos.as_vec2() * factor,
					size: size.as_vec2() * factor,
					uv_pos: Vec2::ZERO,
					uv_size: Vec2::ONE,
					color: 0xffffff20,
					texture: None,
					has_borders: true,
					box_blur: 0.0,
					border: Vec4::ONE,
					radius: Vec4::ZERO,
					rotation: 0.0,
					origin: Vec2::ZERO,
				}));

				for rows in children {
					for child in rows {
						self.debug_node_view(draw_commands, child, pos_offset, factor);
					}
				}
			}

			QuadSlot::Glyph { size: glyph_size, .. } => {
				draw_commands.push(DrawCommand::Quad(HyperQuad {
					pos: pos_offset + pos.as_vec2() * factor,
					size: size.as_vec2() * factor,
					uv_pos: Vec2::ZERO,
					uv_size: Vec2::ONE,
					color: 0xff323280,
					texture: None,
					has_borders: true,
					box_blur: 0.0,
					border: Vec4::ONE,
					radius: Vec4::ZERO,
					rotation: 0.0,
					origin: Vec2::ZERO,
				}));

				draw_commands.push(DrawCommand::Quad(HyperQuad {
					pos: pos_offset + pos.as_vec2() * factor,
					size: glyph_size.as_vec2() * factor,
					uv_pos: Vec2::ZERO,
					uv_size: Vec2::ONE,
					color: 0xffaa32ff,
					texture: None,
					has_borders: true,
					box_blur: 0.0,
					border: Vec4::ONE,
					radius: Vec4::ZERO,
					rotation: 0.0,
					origin: Vec2::ZERO,
				}));
			}
		}
	}

	pub fn debug_glyph_priorities(
		&self,
		draw_commands: &mut Vec<DrawCommand>,
		current_frame: u64,
		pos_offset: Vec2,
		quad_size: Vec2,
	) {
		let now = Instant::now();
		let factor = quad_size / self.size as f32;
		self.debug_glyph_priorities_rec(
			draw_commands,
			now,
			current_frame,
			QuadNodeId(NonZeroU32::MIN),
			pos_offset,
			factor,
		);
	}

	fn debug_glyph_priorities_rec(
		&self,
		draw_commands: &mut Vec<DrawCommand>,
		now: Instant,
		current_frame: u64,
		id: QuadNodeId,
		pos_offset: Vec2,
		factor: Vec2,
	) {
		let QuadNode {
			pos,
			size,
			slot,
			last_frame,
			..
		} = *self.quad_node(id);

		match slot {
			QuadSlot::Free { .. } => {
				// draw nothing
			}

			QuadSlot::Branch { children } => {
				for rows in children {
					for child in rows {
						self.debug_glyph_priorities_rec(draw_commands, now, current_frame, child, pos_offset, factor);
					}
				}
			}

			QuadSlot::Glyph { ref key, .. } => {
				fn color_to_vec4(c: u32) -> Vec4 {
					UVec4::new((c >> 24) & 0xff, (c >> 16) & 0xff, (c >> 8) & 0xff, c & 0xff).as_vec4() / 255.0
				}

				fn vec4_to_color(c: Vec4) -> u32 {
					(((c.x * 255.0) as u32).min(255) << 24)
						| (((c.y * 255.0) as u32).min(255) << 16)
						| (((c.z * 255.0) as u32).min(255) << 8)
						| (((c.w * 255.0) as u32).min(255))
				}

				fn lerp_vec4(start: Vec4, end: Vec4, t: f32) -> Vec4 {
					start + (end - start) * t
				}

				let sep = current_frame - last_frame;
				let base_color = match () {
					_ if sep == 0 => color_to_vec4(0x60ff8032),
					_ if sep < 1024 => color_to_vec4(0xffff6432),
					_ if sep < 2048 => color_to_vec4(0xffaa6432),
					_ => color_to_vec4(0xff646432),
				};

				let fill_color = match self.glyph_cache.get(key) {
					Some(entry) => {
						// create flash
						let t = (now.duration_since(entry.created).as_secs_f32() / 0.500).min(1.0);
						let cubic_t = 1.0 - (1.0 - t).powi(3);
						let flash_color: Vec4 = color_to_vec4(0xffffffaa);

						// ease out cubic
						lerp_vec4(flash_color, base_color, cubic_t)
					}
					None => base_color,
				};

				draw_commands.push(DrawCommand::Quad(HyperQuad {
					pos: pos_offset + pos.as_vec2() * factor,
					size: size.as_vec2() * factor,
					uv_pos: Vec2::ZERO,
					uv_size: Vec2::ONE,
					color: vec4_to_color(fill_color),
					texture: None,
					has_borders: false,
					box_blur: 0.0,
					border: Vec4::ZERO,
					radius: Vec4::ZERO,
					rotation: 0.0,
					origin: Vec2::ZERO,
				}));
			}
		}
	}

	fn debug_ffspl(&self) -> String {
		let mut s = String::new();

		for &slot in self.first_free_slot_per_level.as_ref() {
			let Some(slot) = slot else {
				s.push('_');
				continue;
			};

			let c = match &self.quad_node(slot).slot {
				QuadSlot::Free { next_free, .. } => {
					let mut count = 1;
					let mut counter_next_free = *next_free;
					while let Some(next_slot) = counter_next_free {
						counter_next_free = match self.quad_node(next_slot).slot {
							QuadSlot::Free { next_free, .. } => next_free,
							_ => None,
						};

						if count == u8::MAX {
							break;
						}

						count += 1;
					}

					if count > 9 {
						s += "[>";
						let mut count = 1;
						let mut counter_next_free = *next_free;
						while let Some(next_slot) = counter_next_free {
							counter_next_free = match self.quad_node(next_slot).slot {
								QuadSlot::Free { next_free, .. } => {
									s += &format!(" {}", next_slot.0);
									next_free
								}
								QuadSlot::Branch { .. } => {
									s.push('B');
									None
								}
								QuadSlot::Glyph { .. } => {
									s.push('G');
									None
								}
							};

							if count == u8::MAX {
								s += "...";
								break;
							}

							count += 1;
						}
						s += "]";

						'+'
					} else {
						(b'0' + count) as char
					}
				}
				QuadSlot::Branch { .. } => 'B',
				QuadSlot::Glyph { .. } => 'G',
			};

			s.push(c);
		}

		s
	}
}

#[cfg(test)]
mod tests {
	#[test]
	fn atlas_size() {
		let size = 2048;

		let size_expectations = &[
			(5, 8, 8),
			(9, 16, 7),
			(22, 32, 6),
			(48, 64, 5),
			(128, 128, 4),
			(234, 256, 3),
			(400, 512, 2),
			(599, 1024, 1),
			(727, 1024, 1),
			(1024, 1024, 1),
			(2000, 2048, 0),
		];

		for &(image_size, expected_size, expected_level) in size_expectations {
			let mut curr_size = size;
			let mut curr_level = 0;
			while curr_size / 2 >= image_size {
				curr_size /= 2;
				curr_level += 1;
			}

			assert_eq!(curr_size, expected_size);
			assert_eq!(curr_level, expected_level);
		}
	}
}