[6a3a178] | 1 | "use strict";
|
---|
| 2 |
|
---|
| 3 | Object.defineProperty(exports, "__esModule", {
|
---|
| 4 | value: true
|
---|
| 5 | });
|
---|
| 6 | exports.default = DLL;
|
---|
| 7 | // Simple doubly linked list (https://en.wikipedia.org/wiki/Doubly_linked_list) implementation
|
---|
| 8 | // used for queues. This implementation assumes that the node provided by the user can be modified
|
---|
| 9 | // to adjust the next and last properties. We implement only the minimal functionality
|
---|
| 10 | // for queue support.
|
---|
| 11 | function DLL() {
|
---|
| 12 | this.head = this.tail = null;
|
---|
| 13 | this.length = 0;
|
---|
| 14 | }
|
---|
| 15 |
|
---|
| 16 | function setInitial(dll, node) {
|
---|
| 17 | dll.length = 1;
|
---|
| 18 | dll.head = dll.tail = node;
|
---|
| 19 | }
|
---|
| 20 |
|
---|
| 21 | DLL.prototype.removeLink = function (node) {
|
---|
| 22 | if (node.prev) node.prev.next = node.next;else this.head = node.next;
|
---|
| 23 | if (node.next) node.next.prev = node.prev;else this.tail = node.prev;
|
---|
| 24 |
|
---|
| 25 | node.prev = node.next = null;
|
---|
| 26 | this.length -= 1;
|
---|
| 27 | return node;
|
---|
| 28 | };
|
---|
| 29 |
|
---|
| 30 | DLL.prototype.empty = function () {
|
---|
| 31 | while (this.head) this.shift();
|
---|
| 32 | return this;
|
---|
| 33 | };
|
---|
| 34 |
|
---|
| 35 | DLL.prototype.insertAfter = function (node, newNode) {
|
---|
| 36 | newNode.prev = node;
|
---|
| 37 | newNode.next = node.next;
|
---|
| 38 | if (node.next) node.next.prev = newNode;else this.tail = newNode;
|
---|
| 39 | node.next = newNode;
|
---|
| 40 | this.length += 1;
|
---|
| 41 | };
|
---|
| 42 |
|
---|
| 43 | DLL.prototype.insertBefore = function (node, newNode) {
|
---|
| 44 | newNode.prev = node.prev;
|
---|
| 45 | newNode.next = node;
|
---|
| 46 | if (node.prev) node.prev.next = newNode;else this.head = newNode;
|
---|
| 47 | node.prev = newNode;
|
---|
| 48 | this.length += 1;
|
---|
| 49 | };
|
---|
| 50 |
|
---|
| 51 | DLL.prototype.unshift = function (node) {
|
---|
| 52 | if (this.head) this.insertBefore(this.head, node);else setInitial(this, node);
|
---|
| 53 | };
|
---|
| 54 |
|
---|
| 55 | DLL.prototype.push = function (node) {
|
---|
| 56 | if (this.tail) this.insertAfter(this.tail, node);else setInitial(this, node);
|
---|
| 57 | };
|
---|
| 58 |
|
---|
| 59 | DLL.prototype.shift = function () {
|
---|
| 60 | return this.head && this.removeLink(this.head);
|
---|
| 61 | };
|
---|
| 62 |
|
---|
| 63 | DLL.prototype.pop = function () {
|
---|
| 64 | return this.tail && this.removeLink(this.tail);
|
---|
| 65 | };
|
---|
| 66 |
|
---|
| 67 | DLL.prototype.toArray = function () {
|
---|
| 68 | var arr = Array(this.length);
|
---|
| 69 | var curr = this.head;
|
---|
| 70 | for (var idx = 0; idx < this.length; idx++) {
|
---|
| 71 | arr[idx] = curr.data;
|
---|
| 72 | curr = curr.next;
|
---|
| 73 | }
|
---|
| 74 | return arr;
|
---|
| 75 | };
|
---|
| 76 |
|
---|
| 77 | DLL.prototype.remove = function (testFn) {
|
---|
| 78 | var curr = this.head;
|
---|
| 79 | while (!!curr) {
|
---|
| 80 | var next = curr.next;
|
---|
| 81 | if (testFn(curr)) {
|
---|
| 82 | this.removeLink(curr);
|
---|
| 83 | }
|
---|
| 84 | curr = next;
|
---|
| 85 | }
|
---|
| 86 | return this;
|
---|
| 87 | };
|
---|
| 88 | module.exports = exports["default"]; |
---|