45adea96062afc6c5c2eb4a87fcf094a0917e607f4caf41d4232dc5061bcde131c16b396481c972b6accdcd9704dbc7bc498bb63a40d920b01dbf39ef2a1b3 9.7 KB

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