src/ullist.js

   1 /*
   2     ullist.js
   3
   4     Description: Defines ULList, which represents a doubly linked list
   5     in which each item has a unique identifier stored in the `uid` field.
   6
   7 */
   8
   9 function ULList() {
  10     this.first = null;
  11     this.last = null;
  12     this.length = 0;
  13 }
  14
  15 /* Add an item to the beginning of the list */
  16 ULList.prototype.prepend = function(item) {
  17     if(this.first !== null) {
  18         item.next = this.first;
  19         this.first.prev = item;
  20     } else {
  21         this.last = item;
  22     }
  23     this.first = item;
  24     this.first.prev = null;
  25     this.length++;
  26     return true;
  27 };
  28
  29 /* Add an item to the end of the list */
  30 ULList.prototype.append = function(item) {
  31     if(this.last !== null) {
  32         item.prev = this.last;
  33         this.last.next = item;
  34     } else {
  35         this.first = item;
  36     }
  37     this.last = item;
  38     this.last.next = null;
  39     this.length++;
  40     return true;
  41 };
  42
  43 /* Insert an item after one which has a specified UID */
  44 ULList.prototype.insertAfter = function(item, uid) {
  45     var after = this.find(uid);
  46
  47     if(!after)
  48         return false;
  49
  50     // Update links
  51     item.next = after.next;
  52     if(item.next)
  53         item.next.prev = item;
  54     item.prev = after;
  55     after.next = item;
  56
  57     // New end of list
  58     if(after == this.last)
  59         this.last = item;
  60
  61     this.length++;
  62
  63     return true;
  64 };
  65
  66 /* Insert an item before one that has a specified UID */
  67 ULList.prototype.insertBefore = function(item, uid) {
  68     var before = this.find(uid);
  69
  70     if(!before)
  71         return false;
  72
  73     // Update links
  74     item.next = before;
  75     item.prev = before.prev;
  76     if(item.prev)
  77         item.prev.next = item;
  78     before.prev = item;
  79
  80     // New beginning of list
  81     if(before == this.first)
  82         this.first = item;
  83
  84     this.length++;
  85
  86     return true;
  87 };
  88
  89 /* Remove an item from the list */
  90 ULList.prototype.remove = function(uid) {
  91     var item = this.find(uid);
  92     if(!item)
  93         return false;
  94
  95     // Boundary conditions
  96     if(item == this.first)
  97         this.first = item.next;
  98     if(item == this.last)
  99         this.last = item.prev;
 100
 101     // General case
 102     if(item.prev)
 103         item.prev.next = item.next;
 104     if(item.next)
 105         item.next.prev = item.prev;
 106
 107     this.length--;
 108     return true;
 109 };
 110
 111 /* Find an element in the list, return false if specified UID not found */
 112 ULList.prototype.find = function(uid) {
 113     // Can't possibly find it in an empty list
 114     if(this.first === null)
 115         return false;
 116
 117     var item = this.first;
 118     var iter = this.first;
 119     while(iter !== null && item.uid != uid) {
 120         item = iter;
 121         iter = iter.next;
 122     }
 123
 124     if(item && item.uid == uid)
 125         return item;
 126     return false;
 127 };
 128
 129 /* Clear all elements from the list */
 130 ULList.prototype.clear = function() {
 131     this.first = null;
 132     this.last = null;
 133     this.length = 0;
 134 };
 135
 136 /* Dump the contents of the list into an array */
 137 ULList.prototype.toArray = function(pack) {
 138     var arr = new Array(this.length);
 139     var item = this.first;
 140     var i = 0;
 141     while(item !== null) {
 142         if(pack !== false && typeof item.pack == "function")
 143             arr[i++] = item.pack();
 144         else
 145             arr[i++] = item;
 146         item = item.next;
 147     }
 148     return arr;
 149 };
 150
 151 /* iterate across the playlist */
 152 ULList.prototype.forEach = function (fn) {
 153     var item = this.first;
 154     while(item !== null) {
 155         fn(item);
 156         item = item.next;
 157     }
 158 };
 159
 160 /* find a media with the given video id */
 161 ULList.prototype.findVideoId = function (id) {
 162     var item = this.first;
 163     while(item !== null) {
 164         if(item.media && item.media.id === id)
 165             return item;
 166         item = item.next;
 167     }
 168     return false;
 169 };
 170
 171 ULList.prototype.findAll = function(fn) {
 172     var result = [];
 173     this.forEach(function(item) {
 174         if( fn(item) ) {
 175             result.push(item);
 176         }
 177     });
 178     return result;
 179 };
 180
 181 module.exports = ULList;