yallist.js 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370
  1. module.exports = Yallist
  2. Yallist.Node = Node
  3. Yallist.create = Yallist
  4. function Yallist (list) {
  5. var self = this
  6. if (!(self instanceof Yallist)) {
  7. self = new Yallist()
  8. }
  9. self.tail = null
  10. self.head = null
  11. self.length = 0
  12. if (list && typeof list.forEach === 'function') {
  13. list.forEach(function (item) {
  14. self.push(item)
  15. })
  16. } else if (arguments.length > 0) {
  17. for (var i = 0, l = arguments.length; i < l; i++) {
  18. self.push(arguments[i])
  19. }
  20. }
  21. return self
  22. }
  23. Yallist.prototype.removeNode = function (node) {
  24. if (node.list !== this) {
  25. throw new Error('removing node which does not belong to this list')
  26. }
  27. var next = node.next
  28. var prev = node.prev
  29. if (next) {
  30. next.prev = prev
  31. }
  32. if (prev) {
  33. prev.next = next
  34. }
  35. if (node === this.head) {
  36. this.head = next
  37. }
  38. if (node === this.tail) {
  39. this.tail = prev
  40. }
  41. node.list.length--
  42. node.next = null
  43. node.prev = null
  44. node.list = null
  45. }
  46. Yallist.prototype.unshiftNode = function (node) {
  47. if (node === this.head) {
  48. return
  49. }
  50. if (node.list) {
  51. node.list.removeNode(node)
  52. }
  53. var head = this.head
  54. node.list = this
  55. node.next = head
  56. if (head) {
  57. head.prev = node
  58. }
  59. this.head = node
  60. if (!this.tail) {
  61. this.tail = node
  62. }
  63. this.length++
  64. }
  65. Yallist.prototype.pushNode = function (node) {
  66. if (node === this.tail) {
  67. return
  68. }
  69. if (node.list) {
  70. node.list.removeNode(node)
  71. }
  72. var tail = this.tail
  73. node.list = this
  74. node.prev = tail
  75. if (tail) {
  76. tail.next = node
  77. }
  78. this.tail = node
  79. if (!this.head) {
  80. this.head = node
  81. }
  82. this.length++
  83. }
  84. Yallist.prototype.push = function () {
  85. for (var i = 0, l = arguments.length; i < l; i++) {
  86. push(this, arguments[i])
  87. }
  88. return this.length
  89. }
  90. Yallist.prototype.unshift = function () {
  91. for (var i = 0, l = arguments.length; i < l; i++) {
  92. unshift(this, arguments[i])
  93. }
  94. return this.length
  95. }
  96. Yallist.prototype.pop = function () {
  97. if (!this.tail) {
  98. return undefined
  99. }
  100. var res = this.tail.value
  101. this.tail = this.tail.prev
  102. if (this.tail) {
  103. this.tail.next = null
  104. } else {
  105. this.head = null
  106. }
  107. this.length--
  108. return res
  109. }
  110. Yallist.prototype.shift = function () {
  111. if (!this.head) {
  112. return undefined
  113. }
  114. var res = this.head.value
  115. this.head = this.head.next
  116. if (this.head) {
  117. this.head.prev = null
  118. } else {
  119. this.tail = null
  120. }
  121. this.length--
  122. return res
  123. }
  124. Yallist.prototype.forEach = function (fn, thisp) {
  125. thisp = thisp || this
  126. for (var walker = this.head, i = 0; walker !== null; i++) {
  127. fn.call(thisp, walker.value, i, this)
  128. walker = walker.next
  129. }
  130. }
  131. Yallist.prototype.forEachReverse = function (fn, thisp) {
  132. thisp = thisp || this
  133. for (var walker = this.tail, i = this.length - 1; walker !== null; i--) {
  134. fn.call(thisp, walker.value, i, this)
  135. walker = walker.prev
  136. }
  137. }
  138. Yallist.prototype.get = function (n) {
  139. for (var i = 0, walker = this.head; walker !== null && i < n; i++) {
  140. // abort out of the list early if we hit a cycle
  141. walker = walker.next
  142. }
  143. if (i === n && walker !== null) {
  144. return walker.value
  145. }
  146. }
  147. Yallist.prototype.getReverse = function (n) {
  148. for (var i = 0, walker = this.tail; walker !== null && i < n; i++) {
  149. // abort out of the list early if we hit a cycle
  150. walker = walker.prev
  151. }
  152. if (i === n && walker !== null) {
  153. return walker.value
  154. }
  155. }
  156. Yallist.prototype.map = function (fn, thisp) {
  157. thisp = thisp || this
  158. var res = new Yallist()
  159. for (var walker = this.head; walker !== null;) {
  160. res.push(fn.call(thisp, walker.value, this))
  161. walker = walker.next
  162. }
  163. return res
  164. }
  165. Yallist.prototype.mapReverse = function (fn, thisp) {
  166. thisp = thisp || this
  167. var res = new Yallist()
  168. for (var walker = this.tail; walker !== null;) {
  169. res.push(fn.call(thisp, walker.value, this))
  170. walker = walker.prev
  171. }
  172. return res
  173. }
  174. Yallist.prototype.reduce = function (fn, initial) {
  175. var acc
  176. var walker = this.head
  177. if (arguments.length > 1) {
  178. acc = initial
  179. } else if (this.head) {
  180. walker = this.head.next
  181. acc = this.head.value
  182. } else {
  183. throw new TypeError('Reduce of empty list with no initial value')
  184. }
  185. for (var i = 0; walker !== null; i++) {
  186. acc = fn(acc, walker.value, i)
  187. walker = walker.next
  188. }
  189. return acc
  190. }
  191. Yallist.prototype.reduceReverse = function (fn, initial) {
  192. var acc
  193. var walker = this.tail
  194. if (arguments.length > 1) {
  195. acc = initial
  196. } else if (this.tail) {
  197. walker = this.tail.prev
  198. acc = this.tail.value
  199. } else {
  200. throw new TypeError('Reduce of empty list with no initial value')
  201. }
  202. for (var i = this.length - 1; walker !== null; i--) {
  203. acc = fn(acc, walker.value, i)
  204. walker = walker.prev
  205. }
  206. return acc
  207. }
  208. Yallist.prototype.toArray = function () {
  209. var arr = new Array(this.length)
  210. for (var i = 0, walker = this.head; walker !== null; i++) {
  211. arr[i] = walker.value
  212. walker = walker.next
  213. }
  214. return arr
  215. }
  216. Yallist.prototype.toArrayReverse = function () {
  217. var arr = new Array(this.length)
  218. for (var i = 0, walker = this.tail; walker !== null; i++) {
  219. arr[i] = walker.value
  220. walker = walker.prev
  221. }
  222. return arr
  223. }
  224. Yallist.prototype.slice = function (from, to) {
  225. to = to || this.length
  226. if (to < 0) {
  227. to += this.length
  228. }
  229. from = from || 0
  230. if (from < 0) {
  231. from += this.length
  232. }
  233. var ret = new Yallist()
  234. if (to < from || to < 0) {
  235. return ret
  236. }
  237. if (from < 0) {
  238. from = 0
  239. }
  240. if (to > this.length) {
  241. to = this.length
  242. }
  243. for (var i = 0, walker = this.head; walker !== null && i < from; i++) {
  244. walker = walker.next
  245. }
  246. for (; walker !== null && i < to; i++, walker = walker.next) {
  247. ret.push(walker.value)
  248. }
  249. return ret
  250. }
  251. Yallist.prototype.sliceReverse = function (from, to) {
  252. to = to || this.length
  253. if (to < 0) {
  254. to += this.length
  255. }
  256. from = from || 0
  257. if (from < 0) {
  258. from += this.length
  259. }
  260. var ret = new Yallist()
  261. if (to < from || to < 0) {
  262. return ret
  263. }
  264. if (from < 0) {
  265. from = 0
  266. }
  267. if (to > this.length) {
  268. to = this.length
  269. }
  270. for (var i = this.length, walker = this.tail; walker !== null && i > to; i--) {
  271. walker = walker.prev
  272. }
  273. for (; walker !== null && i > from; i--, walker = walker.prev) {
  274. ret.push(walker.value)
  275. }
  276. return ret
  277. }
  278. Yallist.prototype.reverse = function () {
  279. var head = this.head
  280. var tail = this.tail
  281. for (var walker = head; walker !== null; walker = walker.prev) {
  282. var p = walker.prev
  283. walker.prev = walker.next
  284. walker.next = p
  285. }
  286. this.head = tail
  287. this.tail = head
  288. return this
  289. }
  290. function push (self, item) {
  291. self.tail = new Node(item, self.tail, null, self)
  292. if (!self.head) {
  293. self.head = self.tail
  294. }
  295. self.length++
  296. }
  297. function unshift (self, item) {
  298. self.head = new Node(item, null, self.head, self)
  299. if (!self.tail) {
  300. self.tail = self.head
  301. }
  302. self.length++
  303. }
  304. function Node (value, prev, next, list) {
  305. if (!(this instanceof Node)) {
  306. return new Node(value, prev, next, list)
  307. }
  308. this.list = list
  309. this.value = value
  310. if (prev) {
  311. prev.next = this
  312. this.prev = prev
  313. } else {
  314. this.prev = null
  315. }
  316. if (next) {
  317. next.prev = this
  318. this.next = next
  319. } else {
  320. this.next = null
  321. }
  322. }