| 'use strict'; |
| |
| // |
| // item item item item |
| // /------\ /------\ /------\ /------\ |
| // | data | | data | | data | | data | |
| // null <--+-prev |<---+-prev |<---+-prev |<---+-prev | |
| // | next-+--->| next-+--->| next-+--->| next-+--> null |
| // \------/ \------/ \------/ \------/ |
| // ^ ^ |
| // | list | |
| // | /------\ | |
| // \--------------+-head | | |
| // | tail-+--------------/ |
| // \------/ |
| // |
| |
| function createItem(data) { |
| return { |
| prev: null, |
| next: null, |
| data: data |
| }; |
| } |
| |
| function allocateCursor(node, prev, next) { |
| var cursor; |
| |
| if (cursors !== null) { |
| cursor = cursors; |
| cursors = cursors.cursor; |
| cursor.prev = prev; |
| cursor.next = next; |
| cursor.cursor = node.cursor; |
| } else { |
| cursor = { |
| prev: prev, |
| next: next, |
| cursor: node.cursor |
| }; |
| } |
| |
| node.cursor = cursor; |
| |
| return cursor; |
| } |
| |
| function releaseCursor(node) { |
| var cursor = node.cursor; |
| |
| node.cursor = cursor.cursor; |
| cursor.prev = null; |
| cursor.next = null; |
| cursor.cursor = cursors; |
| cursors = cursor; |
| } |
| |
| var cursors = null; |
| var List = function() { |
| this.cursor = null; |
| this.head = null; |
| this.tail = null; |
| }; |
| |
| List.createItem = createItem; |
| List.prototype.createItem = createItem; |
| |
| List.prototype.updateCursors = function(prevOld, prevNew, nextOld, nextNew) { |
| var cursor = this.cursor; |
| |
| while (cursor !== null) { |
| if (cursor.prev === prevOld) { |
| cursor.prev = prevNew; |
| } |
| |
| if (cursor.next === nextOld) { |
| cursor.next = nextNew; |
| } |
| |
| cursor = cursor.cursor; |
| } |
| }; |
| |
| List.prototype.getSize = function() { |
| var size = 0; |
| var cursor = this.head; |
| |
| while (cursor) { |
| size++; |
| cursor = cursor.next; |
| } |
| |
| return size; |
| }; |
| |
| List.prototype.fromArray = function(array) { |
| var cursor = null; |
| |
| this.head = null; |
| |
| for (var i = 0; i < array.length; i++) { |
| var item = createItem(array[i]); |
| |
| if (cursor !== null) { |
| cursor.next = item; |
| } else { |
| this.head = item; |
| } |
| |
| item.prev = cursor; |
| cursor = item; |
| } |
| |
| this.tail = cursor; |
| |
| return this; |
| }; |
| |
| List.prototype.toArray = function() { |
| var cursor = this.head; |
| var result = []; |
| |
| while (cursor) { |
| result.push(cursor.data); |
| cursor = cursor.next; |
| } |
| |
| return result; |
| }; |
| |
| List.prototype.toJSON = List.prototype.toArray; |
| |
| List.prototype.isEmpty = function() { |
| return this.head === null; |
| }; |
| |
| List.prototype.first = function() { |
| return this.head && this.head.data; |
| }; |
| |
| List.prototype.last = function() { |
| return this.tail && this.tail.data; |
| }; |
| |
| List.prototype.each = function(fn, context) { |
| var item; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| // push cursor |
| var cursor = allocateCursor(this, null, this.head); |
| |
| while (cursor.next !== null) { |
| item = cursor.next; |
| cursor.next = item.next; |
| |
| fn.call(context, item.data, item, this); |
| } |
| |
| // pop cursor |
| releaseCursor(this); |
| }; |
| |
| List.prototype.forEach = List.prototype.each; |
| |
| List.prototype.eachRight = function(fn, context) { |
| var item; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| // push cursor |
| var cursor = allocateCursor(this, this.tail, null); |
| |
| while (cursor.prev !== null) { |
| item = cursor.prev; |
| cursor.prev = item.prev; |
| |
| fn.call(context, item.data, item, this); |
| } |
| |
| // pop cursor |
| releaseCursor(this); |
| }; |
| |
| List.prototype.forEachRight = List.prototype.eachRight; |
| |
| List.prototype.nextUntil = function(start, fn, context) { |
| if (start === null) { |
| return; |
| } |
| |
| var item; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| // push cursor |
| var cursor = allocateCursor(this, null, start); |
| |
| while (cursor.next !== null) { |
| item = cursor.next; |
| cursor.next = item.next; |
| |
| if (fn.call(context, item.data, item, this)) { |
| break; |
| } |
| } |
| |
| // pop cursor |
| releaseCursor(this); |
| }; |
| |
| List.prototype.prevUntil = function(start, fn, context) { |
| if (start === null) { |
| return; |
| } |
| |
| var item; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| // push cursor |
| var cursor = allocateCursor(this, start, null); |
| |
| while (cursor.prev !== null) { |
| item = cursor.prev; |
| cursor.prev = item.prev; |
| |
| if (fn.call(context, item.data, item, this)) { |
| break; |
| } |
| } |
| |
| // pop cursor |
| releaseCursor(this); |
| }; |
| |
| List.prototype.some = function(fn, context) { |
| var cursor = this.head; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| while (cursor !== null) { |
| if (fn.call(context, cursor.data, cursor, this)) { |
| return true; |
| } |
| |
| cursor = cursor.next; |
| } |
| |
| return false; |
| }; |
| |
| List.prototype.map = function(fn, context) { |
| var result = new List(); |
| var cursor = this.head; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| while (cursor !== null) { |
| result.appendData(fn.call(context, cursor.data, cursor, this)); |
| cursor = cursor.next; |
| } |
| |
| return result; |
| }; |
| |
| List.prototype.filter = function(fn, context) { |
| var result = new List(); |
| var cursor = this.head; |
| |
| if (context === undefined) { |
| context = this; |
| } |
| |
| while (cursor !== null) { |
| if (fn.call(context, cursor.data, cursor, this)) { |
| result.appendData(cursor.data); |
| } |
| cursor = cursor.next; |
| } |
| |
| return result; |
| }; |
| |
| List.prototype.clear = function() { |
| this.head = null; |
| this.tail = null; |
| }; |
| |
| List.prototype.copy = function() { |
| var result = new List(); |
| var cursor = this.head; |
| |
| while (cursor !== null) { |
| result.insert(createItem(cursor.data)); |
| cursor = cursor.next; |
| } |
| |
| return result; |
| }; |
| |
| List.prototype.prepend = function(item) { |
| // head |
| // ^ |
| // item |
| this.updateCursors(null, item, this.head, item); |
| |
| // insert to the beginning of the list |
| if (this.head !== null) { |
| // new item <- first item |
| this.head.prev = item; |
| |
| // new item -> first item |
| item.next = this.head; |
| } else { |
| // if list has no head, then it also has no tail |
| // in this case tail points to the new item |
| this.tail = item; |
| } |
| |
| // head always points to new item |
| this.head = item; |
| |
| return this; |
| }; |
| |
| List.prototype.prependData = function(data) { |
| return this.prepend(createItem(data)); |
| }; |
| |
| List.prototype.append = function(item) { |
| return this.insert(item); |
| }; |
| |
| List.prototype.appendData = function(data) { |
| return this.insert(createItem(data)); |
| }; |
| |
| List.prototype.insert = function(item, before) { |
| if (before !== undefined && before !== null) { |
| // prev before |
| // ^ |
| // item |
| this.updateCursors(before.prev, item, before, item); |
| |
| if (before.prev === null) { |
| // insert to the beginning of list |
| if (this.head !== before) { |
| throw new Error('before doesn\'t belong to list'); |
| } |
| |
| // since head points to before therefore list doesn't empty |
| // no need to check tail |
| this.head = item; |
| before.prev = item; |
| item.next = before; |
| |
| this.updateCursors(null, item); |
| } else { |
| |
| // insert between two items |
| before.prev.next = item; |
| item.prev = before.prev; |
| |
| before.prev = item; |
| item.next = before; |
| } |
| } else { |
| // tail |
| // ^ |
| // item |
| this.updateCursors(this.tail, item, null, item); |
| |
| // insert to the ending of the list |
| if (this.tail !== null) { |
| // last item -> new item |
| this.tail.next = item; |
| |
| // last item <- new item |
| item.prev = this.tail; |
| } else { |
| // if list has no tail, then it also has no head |
| // in this case head points to new item |
| this.head = item; |
| } |
| |
| // tail always points to new item |
| this.tail = item; |
| } |
| |
| return this; |
| }; |
| |
| List.prototype.insertData = function(data, before) { |
| return this.insert(createItem(data), before); |
| }; |
| |
| List.prototype.remove = function(item) { |
| // item |
| // ^ |
| // prev next |
| this.updateCursors(item, item.prev, item, item.next); |
| |
| if (item.prev !== null) { |
| item.prev.next = item.next; |
| } else { |
| if (this.head !== item) { |
| throw new Error('item doesn\'t belong to list'); |
| } |
| |
| this.head = item.next; |
| } |
| |
| if (item.next !== null) { |
| item.next.prev = item.prev; |
| } else { |
| if (this.tail !== item) { |
| throw new Error('item doesn\'t belong to list'); |
| } |
| |
| this.tail = item.prev; |
| } |
| |
| item.prev = null; |
| item.next = null; |
| |
| return item; |
| }; |
| |
| List.prototype.push = function(data) { |
| this.insert(createItem(data)); |
| }; |
| |
| List.prototype.pop = function() { |
| if (this.tail !== null) { |
| return this.remove(this.tail); |
| } |
| }; |
| |
| List.prototype.unshift = function(data) { |
| this.prepend(createItem(data)); |
| }; |
| |
| List.prototype.shift = function() { |
| if (this.head !== null) { |
| return this.remove(this.head); |
| } |
| }; |
| |
| List.prototype.prependList = function(list) { |
| return this.insertList(list, this.head); |
| }; |
| |
| List.prototype.appendList = function(list) { |
| return this.insertList(list); |
| }; |
| |
| List.prototype.insertList = function(list, before) { |
| // ignore empty lists |
| if (list.head === null) { |
| return this; |
| } |
| |
| if (before !== undefined && before !== null) { |
| this.updateCursors(before.prev, list.tail, before, list.head); |
| |
| // insert in the middle of dist list |
| if (before.prev !== null) { |
| // before.prev <-> list.head |
| before.prev.next = list.head; |
| list.head.prev = before.prev; |
| } else { |
| this.head = list.head; |
| } |
| |
| before.prev = list.tail; |
| list.tail.next = before; |
| } else { |
| this.updateCursors(this.tail, list.tail, null, list.head); |
| |
| // insert to end of the list |
| if (this.tail !== null) { |
| // if destination list has a tail, then it also has a head, |
| // but head doesn't change |
| |
| // dest tail -> source head |
| this.tail.next = list.head; |
| |
| // dest tail <- source head |
| list.head.prev = this.tail; |
| } else { |
| // if list has no a tail, then it also has no a head |
| // in this case points head to new item |
| this.head = list.head; |
| } |
| |
| // tail always start point to new item |
| this.tail = list.tail; |
| } |
| |
| list.head = null; |
| list.tail = null; |
| |
| return this; |
| }; |
| |
| List.prototype.replace = function(oldItem, newItemOrList) { |
| if ('head' in newItemOrList) { |
| this.insertList(newItemOrList, oldItem); |
| } else { |
| this.insert(newItemOrList, oldItem); |
| } |
| |
| this.remove(oldItem); |
| }; |
| |
| module.exports = List; |