Last active
November 25, 2024 12:48
-
-
Save bakerface/63768d3a8ab6cdc0cecd1268a7aa10c0 to your computer and use it in GitHub Desktop.
A sparse set implementation in JavaScript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import { SparseSet, swap } from "./SparseSet.js"; | |
| class Positions extends SparseSet { | |
| constructor(capacity) { | |
| super(capacity); | |
| this._xs = new Float32Array(capacity); | |
| this._ys = new Float32Array(capacity); | |
| } | |
| at(index) { | |
| const entityId = super.at(index); | |
| return [entityId, this._xs[index], this._ys[index]]; | |
| } | |
| add(entityId, x, y) { | |
| const index = super.add(entityId); | |
| this._xs[index] = x; | |
| this._ys[index] = y; | |
| return index; | |
| } | |
| swap(a, b) { | |
| swap(this._xs, a, b); | |
| swap(this._ys, a, b); | |
| return super.swap(a, b); | |
| } | |
| } | |
| const positions = new Positions(100); | |
| positions.add(10, 100, 100); | |
| positions.add(20, 200, 200); | |
| positions.add(30, 300, 300); | |
| positions.delete(20); | |
| positions.swap(0, 1); | |
| for (const e of positions) { | |
| console.log(e); | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| export class SparseSetIndexOutOfRangeError extends Error { | |
| constructor(message, index, capacity) { | |
| super(message); | |
| this.index = index; | |
| this.capacity = capacity; | |
| } | |
| } | |
| export class SparseSetUnsafe { | |
| constructor(capacity) { | |
| this._dense = new Uint32Array(capacity); | |
| this._sparse = new Uint32Array(capacity); | |
| this._capacity = capacity; | |
| this._count = 0; | |
| } | |
| *[Symbol.iterator]() { | |
| for (let i = 0; i < this._count; i++) { | |
| yield this.at(i); | |
| } | |
| } | |
| get length() { | |
| return this._count; | |
| } | |
| at(index) { | |
| return this._dense[index]; | |
| } | |
| clear() { | |
| this._count = 0; | |
| } | |
| add(id) { | |
| let index = this.indexOf(id); | |
| if (index < 0) { | |
| index = this._count++; | |
| this._dense[index] = id; | |
| this._sparse[id] = index; | |
| } | |
| return index; | |
| } | |
| delete(id) { | |
| const index = this.indexOf(id); | |
| if (index < 0) { | |
| return index; | |
| } | |
| this.swap(index, --this._count); | |
| return index; | |
| } | |
| has(id) { | |
| return this.indexOf(id) >= 0; | |
| } | |
| indexOf(id) { | |
| const index = this._sparse[id]; | |
| if (index < this._count && this._dense[index] === id) { | |
| return index; | |
| } | |
| return -1; | |
| } | |
| swap(a, b) { | |
| swap(this._sparse, this._dense[a], this._dense[b]); | |
| swap(this._dense, a, b); | |
| } | |
| } | |
| export function swap(array, a, b) { | |
| const temp = array[a]; | |
| array[a] = array[b]; | |
| array[b] = temp; | |
| } | |
| export class SparseSet extends SparseSetUnsafe { | |
| indexOf(id) { | |
| if (id >= this._capacity) { | |
| throw new SparseSetIndexOutOfRangeError( | |
| "The index was out of bounds of the array.", | |
| id, | |
| this._capacity | |
| ); | |
| } | |
| return super.indexOf(id); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment