yallist.js 8.2 KB

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