data-structure/deque Home Manual Reference Source

src/implementation/Deque.js

  1. import {
  2. NotImplementedError,
  3. IndexError,
  4. ValueError,
  5. } from '@failure-abstraction/error';
  6.  
  7. /**
  8. * Deque.
  9. */
  10. export default function Deque() {}
  11.  
  12. /**
  13. * Deque.prototype.len.
  14. *
  15. * @return {Number}
  16. */
  17. Deque.prototype.len = function () {
  18. throw new NotImplementedError('len');
  19. };
  20.  
  21. /**
  22. * Deque.prototype.capacity.
  23. *
  24. * @return {Number}
  25. */
  26. Deque.prototype.capacity = function () {
  27. throw new NotImplementedError('capacity');
  28. };
  29.  
  30. /**
  31. * Deque.prototype.empty.
  32. *
  33. * @return {Boolean}
  34. */
  35. Deque.prototype.empty = function () {
  36. return this.len() === 0;
  37. };
  38.  
  39. /**
  40. * Deque.prototype[Symbol.iterator].
  41. *
  42. * @return {Iterable<any>}
  43. */
  44. Deque.prototype[Symbol.iterator] = function () {
  45. return this.values();
  46. };
  47.  
  48. /**
  49. * Deque.prototype.values.
  50. *
  51. * @return {Iterable<any>}
  52. */
  53. Deque.prototype.values = function () {
  54. throw new NotImplementedError('values');
  55. };
  56.  
  57. /**
  58. * Deque.prototype.append.
  59. *
  60. * @param {any} _x
  61. */
  62. Deque.prototype.append = function (_x) {
  63. throw new NotImplementedError('append');
  64. };
  65.  
  66. /**
  67. * Deque.prototype.appendleft.
  68. *
  69. * @param {any} _x
  70. */
  71. Deque.prototype.appendleft = function (_x) {
  72. throw new NotImplementedError('appendleft');
  73. };
  74.  
  75. /**
  76. * Deque.prototype.clear.
  77. *
  78. * @return {Deque}
  79. */
  80. Deque.prototype.clear = function () {
  81. throw new NotImplementedError('clear');
  82. };
  83.  
  84. /**
  85. * Deque.prototype.copy.
  86. *
  87. * @return {Deque}
  88. */
  89. Deque.prototype.copy = function () {
  90. throw new NotImplementedError('copy');
  91. };
  92.  
  93. /**
  94. * Deque.prototype.count.
  95. *
  96. * @param {any} x
  97. * @return {Number}
  98. */
  99. Deque.prototype.count = function (x) {
  100. let c = 0;
  101.  
  102. for (const element of this) {
  103. if (element === x) {
  104. ++c;
  105. }
  106. }
  107.  
  108. return c;
  109. };
  110.  
  111. /**
  112. * Deque.prototype.extend.
  113. *
  114. * @param {Iterable<any>} iterable
  115. */
  116. Deque.prototype.extend = function (iterable) {
  117. for (const x of iterable) {
  118. this.append(x);
  119. }
  120.  
  121. return this;
  122. };
  123.  
  124. /**
  125. * Deque.prototype.extendleft.
  126. *
  127. * @param {Iterable<any>} iterable
  128. */
  129. Deque.prototype.extendleft = function (iterable) {
  130. for (const x of iterable) {
  131. this.appendleft(x);
  132. }
  133.  
  134. return this;
  135. };
  136.  
  137. /**
  138. * Deque.prototype._checkbounds.
  139. *
  140. * @param {Number} i
  141. */
  142. Deque.prototype._checkbounds = function (i) {
  143. if (i < 0 || i >= this.len()) {
  144. throw new IndexError(i);
  145. }
  146. };
  147.  
  148. /**
  149. * Deque.prototype._where.
  150. *
  151. * @param {Number} _i
  152. * @return {Array}
  153. */
  154. Deque.prototype._where = function (_i) {
  155. throw new NotImplementedError('_where');
  156. };
  157.  
  158. /**
  159. * Deque.prototype.get.
  160. *
  161. * @param {Number} i
  162. * @return {any}
  163. */
  164. Deque.prototype.get = function (i) {
  165. const [container, index] = this._where(i);
  166.  
  167. return container[index];
  168. };
  169.  
  170. /**
  171. * Deque.prototype.set.
  172. *
  173. * @param {Number} i
  174. * @param {any} value
  175. * @return {Deque}
  176. */
  177. Deque.prototype.set = function (i, value) {
  178. const [container, index] = this._where(i);
  179.  
  180. container[index] = value;
  181.  
  182. return this;
  183. };
  184.  
  185. /**
  186. * Deque.prototype._range
  187. *
  188. * @param {Number} start
  189. * @param {Number} stop
  190. * @return {Iterable<any>}
  191. */
  192. Deque.prototype._range = function* (start, stop) {
  193. for (let i = start; i < stop; ++i) {
  194. yield [i, this.get(i)];
  195. }
  196. };
  197.  
  198. /**
  199. * Deque.prototype.index.
  200. *
  201. * @param {any} x
  202. * @param {Number} start
  203. * @param {Number} stop
  204. */
  205. Deque.prototype.index = function (x, start = 0, stop = this.len()) {
  206. for (const [i, element] of this._range(start, stop)) {
  207. if (element === x) {
  208. return i;
  209. }
  210. }
  211.  
  212. throw new ValueError('not found');
  213. };
  214.  
  215. /**
  216. * Deque.prototype.pop.
  217. *
  218. * @return {any}
  219. */
  220. Deque.prototype.pop = function () {
  221. throw new NotImplementedError('pop');
  222. };
  223.  
  224. /**
  225. * Deque.prototype.popleft.
  226. *
  227. * @return {any}
  228. */
  229. Deque.prototype.popleft = function () {
  230. throw new NotImplementedError('popleft');
  231. };
  232.  
  233. /**
  234. * Deque.prototype.insert.
  235. *
  236. * @param {Number} i
  237. * @param {any} x
  238. */
  239. Deque.prototype.insert = function (i, x) {
  240. this._checkbounds(i);
  241.  
  242. this.append(x);
  243.  
  244. let j = this.len() - 1;
  245.  
  246. for (; i < j; --j) {
  247. const a = this.get(j);
  248. this.set(j, this.get(j - 1));
  249. this.set(j - 1, a);
  250. }
  251.  
  252. return this;
  253. };
  254.  
  255. /**
  256. * Deque.prototype.delete.
  257. *
  258. * @param {Number} i
  259. */
  260. Deque.prototype.delete = function (i) {
  261. this._checkbounds(i);
  262.  
  263. const length = this.len() - 1;
  264.  
  265. for (; i < length; ++i) {
  266. this.set(i, this.get(i + 1));
  267. }
  268.  
  269. this.pop();
  270.  
  271. return this;
  272. };
  273.  
  274. /**
  275. * Deque.prototype.remove.
  276. *
  277. * @param {any} value
  278. */
  279. Deque.prototype.remove = function (value) {
  280. const i = this.index(value);
  281.  
  282. this.delete(i);
  283.  
  284. return this;
  285. };
  286.  
  287. /**
  288. * Deque.prototype.reverse.
  289. *
  290. * @return {Deque}
  291. */
  292. Deque.prototype.reverse = function () {
  293. for (let i = 0, j = this.len(); i < --j; ++i) {
  294. const a = this.get(i);
  295. const b = this.get(j);
  296. this.set(i, b);
  297. this.set(j, a);
  298. }
  299.  
  300. return this;
  301. };
  302.  
  303. /**
  304. * Deque.prototype.rotate.
  305. *
  306. * @param {Number} n
  307. */
  308. Deque.prototype.rotate = function (n) {
  309. if (n > 0) {
  310. while (n-- > 0) {
  311. this.appendleft(this.pop());
  312. }
  313. } else if (n < 0) {
  314. while (n++ < 0) {
  315. this.append(this.popleft());
  316. }
  317. }
  318.  
  319. return this;
  320. };