class AABB {

	constructor(x, y, w, h) {

		// Use Float32Array for better performance when dealing with many boundary checks
		this.data = new Float32Array([x, y, w, h]);
	
	}

	// Optimized contains check with cached property access
	contains(x, y) {

		const data = this.data;
		const x0 = data[0];
		const y0 = data[1];

		return (
			x >= x0
			&& x <= x0 + data[2]
			&& y >= y0
			&& y <= y0 + data[3]
		);
	
	}

	// Optimized intersection check with cached property access
	intersects(other) {

		const a = this.data;
		const b = other.data;

		return !(
			b[0] > a[0] + a[2]
			|| b[0] + b[2] < a[0]
			|| b[1] > a[1] + a[3]
			|| b[1] + b[3] < a[1]
		);
	
	}

}

class Square {

	static init() {

		Square.nextId = 0;
	
	}

	constructor(x, y, size) {

		// Using Float32Array for better performance
		this.data = new Float32Array([
			x,                          // 0: x
			y,                          // 1: y
			size,                       // 2: size
			(Math.random() - 0.5) * 2,  // 3: dx
			(Math.random() - 0.5) * 2,  // 4: dy
			Square.nextId++             // 5: id
		]);

		this.element = document.createElement("div");
		this.element.className = "square";
		this.element.style.width = this.element.style.height = `${size}px`;
		this.isColliding = false;
		this.updateTransform();
	
	}

	// Update method is now simplified and delegated to the Demo class
	updateTransform() {

		this.element.style.transform = `translate(${this.data[0]}px,${this.data[1]}px)`;
	
	}

}

Square.init();

class QuadTree {

	static init() {

		QuadTree.pool = [];
		QuadTree.maxPoolSize = 1000;
		
		// Pre-create the pool to avoid allocations during runtime
		for(let i = 0; i < 100; i++) {

			QuadTree.pool.push(new QuadTree(null,
				4,
				5,
				0));
		
		}
	
	}

	static acquire(boundary, capacity = 4, maxDepth = 5, depth = 0) {

		if(QuadTree.pool.length > 0) {

			const qt = QuadTree.pool.pop();

			// Set properties instead of creating new objects
			qt.boundary = boundary;
			qt.capacity = capacity;
			qt.maxDepth = maxDepth;
			qt.depth = depth;
			qt.items.length = 0;
			qt.divided = false;
			qt.nw = qt.ne = qt.sw = qt.se = null;
			return qt;
		
		}
		return new QuadTree(boundary,
			capacity,
			maxDepth,
			depth);
	
	}

	static release(qt) {

		if(qt.divided) {

			QuadTree.release(qt.nw);
			QuadTree.release(qt.ne);
			QuadTree.release(qt.sw);
			QuadTree.release(qt.se);
			// Clear references to help garbage collection
			qt.nw = qt.ne = qt.sw = qt.se = null;
		
		}
		if(QuadTree.pool.length < QuadTree.maxPoolSize) {

			QuadTree.pool.push(qt);
		
		}
	
	}

	constructor(boundary, capacity = 4, maxDepth = 5, depth = 0) {

		this.boundary = boundary;
		this.capacity = capacity;
		this.maxDepth = maxDepth;
		this.depth = depth;
		this.items = [];
		this.divided = false;
		this.nw = this.ne = this.sw = this.se = null;
	
	}

	subdivide() {

		const data = this.boundary.data;
		const x = data[0];
		const y = data[1];
		const w = data[2] * 0.5; // More efficient than dividing by 2
		const h = data[3] * 0.5;
		
		// Create new AABB objects for children
		const nwBoundary = new AABB(x,
			y,
			w,
			h);
		const neBoundary = new AABB(x + w,
			y,
			w,
			h);
		const swBoundary = new AABB(x,
			y + h,
			w,
			h);
		const seBoundary = new AABB(x + w,
			y + h,
			w,
			h);

		this.nw = QuadTree.acquire(nwBoundary,
			this.capacity,
			this.maxDepth,
			this.depth + 1);
		this.ne = QuadTree.acquire(neBoundary,
			this.capacity,
			this.maxDepth,
			this.depth + 1);
		this.sw = QuadTree.acquire(swBoundary,
			this.capacity,
			this.maxDepth,
			this.depth + 1);
		this.se = QuadTree.acquire(seBoundary,
			this.capacity,
			this.maxDepth,
			this.depth + 1);

		this.divided = true;
	
	}

	insert(item) {

		// Early boundary check optimization
		if(!this.boundary.contains(item.data[0],
			item.data[1])) 
			return false;

		// If we have capacity or reached max depth, add item here
		if(this.items.length < this.capacity || this.depth >= this.maxDepth) {

			this.items.push(item);
			return true;
		
		}

		// Subdivide if needed and insert into appropriate child
		if(!this.divided) 
			this.subdivide();

		// Try to insert in each quadrant (optimized with short-circuit evaluation)
		return (
			this.nw.insert(item)
			|| this.ne.insert(item)
			|| this.sw.insert(item)
			|| this.se.insert(item)
		);
	
	}

	query(range, found) {

		// Early exit optimization - no intersection with this quadrant
		if(!this.boundary.intersects(range)) 
			return found;

		// Check all items in this node
		const items = this.items;
		const itemsLength = items.length;
		
		// Manual loop is faster than for...of
		for(let i = 0; i < itemsLength; i++) {

			const item = items[i];

			if(range.contains(item.data[0],
				item.data[1])) {

				found.push(item);
			
			}
		
		}

		// Recurse into children if they exist
		if(this.divided) {

			this.nw.query(range,
				found);
			this.ne.query(range,
				found);
			this.sw.query(range,
				found);
			this.se.query(range,
				found);
		
		}

		return found;
	
	}

}

QuadTree.init();

class Demo {

	constructor() {

		this.wrapper = document.getElementById("wrapper");
		this.container = document.getElementById("container");
		this.elementsLayer = document.getElementById("elements-layer");
		this.treeLayer = document.getElementById("tree-layer");
		// Use alpha: false for better canvas performance
		this.ctx = this.treeLayer.getContext("2d",
			{ alpha: false });
		
		this.width = 0;
		this.height = 0;

		// Use individual variables instead of array fill
		this.speedValue = null;
		this.speedMultiplier = 1;
		this.fpsDisplay = null;
		this.lastFpsUpdate = 0;
		this.frameCount = 0;
		this.holdTimer = null;
		
		this.squares = [];
		this.running = true;
		this.showTrees = false;
		this.collisions = 0;
		this.holdDelay = 100;
		this.queryResults = [];
		this.collisionPairs = new Set();
		
		// Reusable AABB for queries to avoid object creation
		this.queryRange = new AABB(0,
			0,
			0,
			0);

		this.resize();
		window.addEventListener("resize",
			() => 
				this.resize());
		this.setupControls();
		this.addSquares(50);
		
		// Use requestAnimationFrame properly
		this._animateBound = this.animate.bind(this);
		requestAnimationFrame(this._animateBound);
	
	}

	resize() {

		const size = Math.min(this.wrapper.offsetWidth,
			window.innerHeight * 0.8 - 100);

		this.width = this.height = size;
		this.container.style.width = this.container.style.height = `${size}px`;
		this.treeLayer.width = this.treeLayer.height = size;
	
	}

	setupControls() {

		const setupBtn = (id, action) => {

			const btn = document.getElementById(id);
			
			// Use more efficient event handling
			const handlePointerDown = () => {

				action();
				this.holdTimer = setInterval(action,
					this.holdDelay);
			
			};
			
			const handlePointerUp = () => {

				if(this.holdTimer) {

					clearInterval(this.holdTimer);
					this.holdTimer = null;
				
				}
			
			};
			
			btn.addEventListener("pointerdown",
				handlePointerDown);
			btn.addEventListener("pointerup",
				handlePointerUp);
			btn.addEventListener("pointerleave",
				handlePointerUp);
		
		};

		// Toggle buttons
		const toggleButtons = {
			"playPause": () => {

				this.running = !this.running;
				return this.running ? "STOP" : "PLAY";
			
			},
			"toggleTrees": () => {

				this.showTrees = !this.showTrees;
				this.container.classList.toggle("debug",
					this.showTrees);
				this.treeLayer.style.display = this.showTrees ? "block" : "none";
				return this.showTrees ? "CLEAR" : "DEBUG";
			
			}
		};
		
		Object.entries(toggleButtons)
		.forEach(([id, action]) => {

			document.getElementById(id).onclick = () => {

				document.getElementById(id).textContent = action();
			
			};
		
		});

		setupBtn("minus",
			() => 
				this.remSquares(10));
		setupBtn("plus",
			() => 
				this.addSquares(10));
		setupBtn("slow",
			() => 
				this.slower());
		setupBtn("fast",
			() => 
				this.faster());

		this.speedValue = document.getElementById("speed");
		this.speedMultiplier = 1;
		this.fpsDisplay = document.getElementById("fps");
		this.frameCount = 0;
		this.lastFpsUpdate = performance.now();
	
	}

	addSquares(count) {

		const maxSize = Math.min(window.innerWidth,
			window.innerHeight) / 27;
		
		for(let i = 0; i < count; i++) {

			const s = Math.random() * Math.round(maxSize) + 5;
			const square = new Square(
				Math.random() * (this.width - s),
				Math.random() * (this.height - s),
				s
			);

			this.squares.push(square);
			this.elementsLayer.appendChild(square.element);
		
		}
		this.updateCount();
	
	}

	remSquares(count) {

		const remove = Math.min(count,
			this.squares.length);
		
		// Use splice once with a callback instead of forEach
		const removed = this.squares.splice(-remove);

		for(let i = 0; i < removed.length; i++) {

			this.elementsLayer.removeChild(removed[i].element);
		
		}
		
		this.updateCount();
	
	}

	slower() {

		this.speedMultiplier = Math.max(this.speedMultiplier - 0.1,
			0.1);
		this.updateSpeed();
	
	}

	faster() {

		this.speedMultiplier = Math.min(this.speedMultiplier + 0.1,
			5.0);
		this.updateSpeed();
	
	}

	updateSpeed() {

		this.speedValue.textContent = `x${this.speedMultiplier.toFixed(1)}`;
	
	}

	updateCount() {

		document.getElementById("elementCount").textContent 
			= this.squares.length.toString()
			.padStart(3,
				"0");
	
	}

	checkCollisions() {

		this.collisions = 0;
		this.collisionPairs.clear();

		// Create main quadtree
		const qt = QuadTree.acquire(new AABB(0,
			0,
			this.width,
			this.height));

		// Insert all squares into the quadtree
		const squares = this.squares;
		const squaresLength = squares.length;
		
		for(let i = 0; i < squaresLength; i++) {

			const square = squares[i];

			square.isColliding = false;
			qt.insert(square);
		
		}

		// Reuse query range object
		const range = this.queryRange;
		const queryResults = this.queryResults;
		
		// Check for collisions
		for(let i = 0; i < squaresLength; i++) {

			const square = squares[i];
			const s = square.data;

			// Update range data directly instead of creating a new object
			range.data[0] = s[0] - s[2];
			range.data[1] = s[1] - s[2];
			range.data[2] = s[2] * 3;
			range.data[3] = s[2] * 3;

			// Clear and reuse query results array
			queryResults.length = 0;
			qt.query(range,
				queryResults);

			// Process potential collisions
			const resultsLength = queryResults.length;

			for(let j = 0; j < resultsLength; j++) {

				const other = queryResults[j];
				
				if(other === square) 
					continue;

				const o = other.data;
				const pairKey = `${Math.min(s[5],
					o[5])},${Math.max(s[5],
					o[5])}`;

				if(!this.collisionPairs.has(pairKey)) {

					// Optimized collision check
					const collision = !(
						s[0] + s[2] < o[0]
						|| s[0] > o[0] + o[2]
						|| s[1] + s[2] < o[1]
						|| s[1] > o[1] + o[2]
					);

					if(collision) {

						this.collisionPairs.add(pairKey);
						square.isColliding = other.isColliding = true;
						this.collisions++;
					
					}
				
				}
			
			}
		
		}

		// Update collision visual state
		for(let i = 0; i < squaresLength; i++) {

			const square = squares[i];

			square.element.classList.toggle("colliding",
				square.isColliding);
		
		}

		document.getElementById("collisions").textContent 
			= this.collisions.toString()
			.padStart(3,
				"0");

		// Render debug visualization if enabled
		if(this.showTrees) {

			this.renderDebug(qt);
		
		}

		QuadTree.release(qt);
	
	}

	renderDebug(tree) {

		const { ctx } = this;
		const width = this.width;
		const height = this.height;

		// Get background color from CSS once
		ctx.fillStyle = getComputedStyle(document.body)
		.getPropertyValue("--surface");
		ctx.fillRect(0,
			0,
			width,
			height);

		// Draw quadtree structure
		ctx.strokeStyle = "rgba(56, 189, 248, 0.33)";
		ctx.lineWidth = 0.25;

		// Use iterative approach instead of recursive for better performance
		const renderNode = node => {

			const nodesToProcess = [node];
			
			while(nodesToProcess.length > 0) {

				const currentNode = nodesToProcess.pop();
				const { data } = currentNode.boundary;
				
				// Draw boundary rectangle
				ctx.strokeRect(data[0],
					data[1],
					data[2],
					data[3]);
				
				// Draw points for items in this node
				if(currentNode.items.length) {

					ctx.fillStyle = "rgba(56, 189, 248, 0.5)";
					const items = currentNode.items;
					const itemsLength = items.length;
					
					for(let i = 0; i < itemsLength; i++) {

						const item = items[i];
						const itemData = item.data;
						
						ctx.beginPath();
						ctx.arc(
							itemData[0] + itemData[2] / 2,
							itemData[1] + itemData[2] / 2,
							1.5,
							0,
							Math.PI * 2
						);
						ctx.fill();
					
					}
				
				}
				
				// Add child nodes to processing queue if this node is divided
				if(currentNode.divided) {

					nodesToProcess.push(currentNode.se);
					nodesToProcess.push(currentNode.sw);
					nodesToProcess.push(currentNode.ne);
					nodesToProcess.push(currentNode.nw);
				
				}
			
			}
		
		};
		
		renderNode(tree);

		// Draw collision query ranges
		ctx.strokeStyle = "rgba(255, 100, 100, 0.27)";
		ctx.lineWidth = 0.5;
		
		// Convert to array once for iteration
		const pairKeys = Array.from(this.collisionPairs);
		const pairLength = pairKeys.length;
		
		for(let i = 0; i < pairLength; i++) {

			const pairKey = pairKeys[i];
			const id = +pairKey.split(",")[0];
			
			// Find square with matching ID
			const squares = this.squares;
			const squaresLength = squares.length;
			
			for(let j = 0; j < squaresLength; j++) {

				const square = squares[j];

				if(square.data[5] === id) {

					const s = square.data;

					ctx.strokeRect(s[0] - s[2],
						s[1] - s[2],
						s[2] * 3,
						s[2] * 3);
					break;
				
				}
			
			}
		
		}
	
	}

	updateSquares() {

		const width = this.width;
		const height = this.height;
		const speedMultiplier = this.speedMultiplier;
		const squares = this.squares;
		const squaresLength = squares.length;
		
		for(let i = 0; i < squaresLength; i++) {

			const square = squares[i];
			const s = square.data;
			
			// Apply velocity
			s[0] += s[3] * speedMultiplier;
			s[1] += s[4] * speedMultiplier;
			
			// Boundary checks for x-axis
			if(s[0] <= 0) {

				s[0] = 0;
				s[3] *= -1;
			
			}
			else if(s[0] + s[2] >= width) {

				s[0] = width - s[2];
				s[3] *= -1;
			
			}
			
			// Boundary checks for y-axis
			if(s[1] <= 0) {

				s[1] = 0;
				s[4] *= -1;
			
			}
			else if(s[1] + s[2] >= height) {

				s[1] = height - s[2];
				s[4] *= -1;
			
			}
			
			// Update DOM element position
			square.element.style.transform = `translate(${s[0]}px,${s[1]}px)`;
		
		}
	
	}

	animate(now) {

		// Calculate and update FPS
		if(now - this.lastFpsUpdate >= 1000) {

			const fps = Math.round(this.frameCount * 1000 / (now - this.lastFpsUpdate));

			this.fpsDisplay.textContent = fps.toString()
			.padStart(2,
				"0");
			this.frameCount = 0;
			this.lastFpsUpdate = now;
		
		}
		this.frameCount++;
		
		// Schedule next frame
		requestAnimationFrame(this._animateBound);
		
		// Update simulation if running
		if(this.running) {

			this.updateSquares();
			this.checkCollisions();
		
		}
	
	}

}

new Demo();