Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A data structure that wraps a sparse array. Useful for when you know the total size of a list and need to represent it in its full size, but are lazy loading in sections of it. Sandbox: https://codesandbox.io/s/yvrv97k879
class SparseList<T = any> {
private list: T[];
emptySlotsCount: number;
constructor(size: number) {
this.list = new Array(size);
this.emptySlotsCount = size;
}
get size() {
return this.list.length;
}
get(index: number) {
return this.list[index];
}
has(index: number) {
return !!this.get(index);
}
hasRange(startIndex: number, stopIndex: number) {
let next = startIndex;
while (next <= stopIndex && this.has(next)) {
next++;
}
return next >= stopIndex;
}
add(startIndex: number, data: T[]) {
let count = 0;
while (count < data.length) {
this.list[startIndex + count] = data[count];
count++;
}
this.emptySlotsCount -= data.length;
return this;
}
toArray() {
return Array.from(this.list);
}
// this is just for debugging
print() {
this.list.forEach((item, i) => {
if (item) {
console.log(i, item);
}
});
}
// this makes it work with `for of` loops and `Array.from`
*[Symbol.iterator]() {
yield* this.list;
}
valueOf() { return '[object SparseList]' }
}
// test it out
let list = new SparseList(100);
list.add(3, [1,2,3])
list.add(25, [6,5,78,3,4])
console.log('' + list); // [object SparseList]
console.log(list.hasRange(0, 5)) // false
console.log(list.has(101)) // false
console.log(list.hasRange(3, 6)) // true
console.log(list.emptySlotsCount); // 92
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.