Skip to content

Instantly share code, notes, and snippets.

@gladchinda
Created October 19, 2022 17:01
Show Gist options
  • Save gladchinda/acc56596f7e1f47fb841c97e68e46596 to your computer and use it in GitHub Desktop.
Save gladchinda/acc56596f7e1f47fb841c97e68e46596 to your computer and use it in GitHub Desktop.
Configurable LL-based queue for JavaScript
var ListQueue = (() => {
const _enumerable_ = value => ({ value, enumerable: true });
const _writable_ = value => ({ ..._enumerable_(value), writable: true });
function ListQueue(config) {
if (!(this instanceof ListQueue)) {
return new ListQueue(config);
}
const { hash, fifo, maxsize, reorder } =
Object.prototype.toString.call(config) === "[object Object]"
? { ...config }
: { maxsize: config };
let $first = null;
let $last = null;
let $size = 0;
const $map = new Map();
const $hash = typeof hash === "function"
? value => hash(value)
: value => value;
const $maxsize = Math.max(0, Math.min(
Number.isInteger(maxsize) && maxsize,
ListQueue.MAX_SIZE
)) || ListQueue.MAX_SIZE;
const $fifo = fifo !== false;
const $reorder = reorder === true;
const _remove = (...args) => {
const item = args.length > 0 ? $map.get($hash(args[0])) : $first;
if (item && (item === $first || $reorder)) {
if (item.prev) item.prev.next = item.next;
if (item.next) item.next.prev = item.prev;
if (item === $first) $first = item.next;
if (item === $last) $last = item.prev;
$map.delete(item.key) && --$size;
if ($reorder) item.prev = null;
item.next = null;
return item.data;
} else return null;
};
const iterator = function*() {
let item = $first;
while (item) {
yield item.data;
item = item.next;
}
};
const dequeue = (...args) => $fifo ? _remove() : _remove(...args);
const enqueue = value => {
if (value != undefined) {
if ($reorder) _remove(value);
else if ($map.has($hash(value))) return;
if ($size === $maxsize) throw ListQueue.MAX_SIZE_ERROR;
const item = Object.create(null, {
data: _enumerable_(value),
key: _enumerable_($hash(value)),
next: _writable_(null)
});
$reorder && Object.defineProperty(item, "prev", _writable_(null));
if (item.key != undefined) {
if ($last) {
if ($reorder) item.prev = $last;
item.next = $last.next;
$last = $last.next = item;
} else $first = $last = item;
$map.set(item.key, item);
$size++;
}
}
};
const peek = () => $first ? $first.data : null;
Object.defineProperties(this, {
[Symbol.iterator]: _enumerable_(iterator),
size: { get: () => $size },
maxsize: _enumerable_($maxsize),
dequeue: _enumerable_(dequeue),
enqueue: _enumerable_(enqueue),
peek: _enumerable_(peek)
});
}
return Object.defineProperties(ListQueue, {
MAX_SIZE: _enumerable_(Math.pow(2, 32) - 1),
MAX_SIZE_ERROR: _enumerable_(new Error("Cannot exceed maximum queue size."))
});
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment