| "use strict"; |
| |
| Object.defineProperty(exports, "__esModule", { |
| value: true |
| }); |
| exports.default = DLL; |
| // Simple doubly linked list (https://en.wikipedia.org/wiki/Doubly_linked_list) implementation |
| // used for queues. This implementation assumes that the node provided by the user can be modified |
| // to adjust the next and last properties. We implement only the minimal functionality |
| // for queue support. |
| function DLL() { |
| this.head = this.tail = null; |
| this.length = 0; |
| } |
| |
| function setInitial(dll, node) { |
| dll.length = 1; |
| dll.head = dll.tail = node; |
| } |
| |
| DLL.prototype.removeLink = function (node) { |
| if (node.prev) node.prev.next = node.next;else this.head = node.next; |
| if (node.next) node.next.prev = node.prev;else this.tail = node.prev; |
| |
| node.prev = node.next = null; |
| this.length -= 1; |
| return node; |
| }; |
| |
| DLL.prototype.empty = function () { |
| while (this.head) this.shift(); |
| return this; |
| }; |
| |
| DLL.prototype.insertAfter = function (node, newNode) { |
| newNode.prev = node; |
| newNode.next = node.next; |
| if (node.next) node.next.prev = newNode;else this.tail = newNode; |
| node.next = newNode; |
| this.length += 1; |
| }; |
| |
| DLL.prototype.insertBefore = function (node, newNode) { |
| newNode.prev = node.prev; |
| newNode.next = node; |
| if (node.prev) node.prev.next = newNode;else this.head = newNode; |
| node.prev = newNode; |
| this.length += 1; |
| }; |
| |
| DLL.prototype.unshift = function (node) { |
| if (this.head) this.insertBefore(this.head, node);else setInitial(this, node); |
| }; |
| |
| DLL.prototype.push = function (node) { |
| if (this.tail) this.insertAfter(this.tail, node);else setInitial(this, node); |
| }; |
| |
| DLL.prototype.shift = function () { |
| return this.head && this.removeLink(this.head); |
| }; |
| |
| DLL.prototype.pop = function () { |
| return this.tail && this.removeLink(this.tail); |
| }; |
| |
| DLL.prototype.toArray = function () { |
| var arr = Array(this.length); |
| var curr = this.head; |
| for (var idx = 0; idx < this.length; idx++) { |
| arr[idx] = curr.data; |
| curr = curr.next; |
| } |
| return arr; |
| }; |
| |
| DLL.prototype.remove = function (testFn) { |
| var curr = this.head; |
| while (!!curr) { |
| var next = curr.next; |
| if (testFn(curr)) { |
| this.removeLink(curr); |
| } |
| curr = next; |
| } |
| return this; |
| }; |
| module.exports = exports["default"]; |