Source: collections/LinkedList.js

  1. const { Collection, CollectionEvent } = require('./Collection')
  2. , { EqualityComparer } = require('./EqualityComparer')
  3. , { Observable, fromEvent } = require('rxjs')
  4. , symbolLinkedListAdd = Symbol('linkedListAdd')
  5. , symbolLinkedListRemove = Symbol('linkedListRemove');
  8. /**
  9.  * @template T
  10.  */
  11. class LinkedListEvent extends CollectionEvent {
  12. 	/**
  13. 	 * @param {LinkedListNode<T>} node
  14. 	 * @param {Boolean} add True, if the node was added. If false, the node was removed.
  15. 	 * @param {Boolean} first True, iff the node is the first node now
  16. 	 * @param {Boolean} last True, iff the node is the last node now
  17. 	 */
  18. 	constructor(node, add, first, last) {
  19. 		super(node);
  21. 		/** @type {LinkedListNode<T>} */
  22. 		this.item = node;
  24. 		/** @protected */
  25. 		this._add = add;
  26. 		/** @protected */
  27. 		this._first = first;
  28. 		/** @protected */
  29. 		this._last = last;
  30. 	};
  32. 	/**
  33. 	 * Returns whether this represents an add-event.
  34. 	 * 
  35. 	 * @type {Boolean}
  36. 	 */
  37. 	get added() {
  38. 		return this._add;
  39. 	};
  41. 	/**
  42. 	 * Returns whether this represents a remove-event.
  43. 	 * 
  44. 	 * @type {Boolean}
  45. 	 */
  46. 	get removed() {
  47. 		return !this._add;
  48. 	};
  50. 	/**
  51. 	 * Returns whether the node is the first now.
  52. 	 * 
  53. 	 * @type {Boolean}
  54. 	 */
  55. 	get firstNode() {
  56. 		return this._first;
  57. 	};
  59. 	/**
  60. 	 * Returns whether the node is the last now.
  61. 	 * 
  62. 	 * @type {Boolean}
  63. 	 */
  64. 	get lastNode() {
  65. 		return this._last;
  66. 	};
  67. };
  70. /**
  71.  * @template T
  72.  * @author Sebastian Hönel <development@hoenel.net>
  73.  */
  74. class LinkedListNode {
  75. 	/**
  76. 	 * @param {T} item
  77. 	 * @param {LinkedList<T>} list
  78. 	 * @param {LinkedListNode<T>} prev
  79. 	 * @param {LinkedListNode<T>} next
  80. 	 */
  81. 	constructor(item, list, prev = null, next = null) {
  82. 		this.item = item;
  83. 		this.list = list;
  84. 		this.prev = prev;
  85. 		this.next = next;
  86. 	};
  87. };
  91. /**
  92.  * @template T
  93.  * @author Sebastian Hönel <development@hoenel.net>
  94.  */
  95. class LinkedList extends Collection {
  96. 	/**
  97. 	 * Creates a new, empty doubly-linked LinkedList.
  98. 	 * 
  99. 	 * @param {EqualityComparer<T>} [eqComparer] Optional. Defaults To EqualityComparer<T>.default.
  100. 	 */
  101. 	constructor(eqComparer = EqualityComparer.default) {
  102. 		super(eqComparer);
  103. 		
  104. 		/**
  105. 		 * @type {LinkedListNode<T>}
  106. 		 * @protected
  107. 		 */
  108. 		this._firstNode = null;
  109. 		/**
  110. 		 * @type {LinkedListNode<T>}
  111. 		 * @protected
  112. 		 */
  113. 		this._lastNode = null;
  114. 		
  115. 		/**
  116. 		 * @type {Set<LinkedListNode<T>>}
  117. 		 * @protected
  118. 		 */
  119. 		this._lookupSet = new Set();
  121. 		/** @protected */
  122. 		this._size = 0;
  123. 		
  124. 		/** @type {Observable<LinkedListEvent<T>>} */
  125. 		this.observableNodeAdd = Object.freeze(fromEvent(this, symbolLinkedListAdd));
  126. 		/** @type {Observable<LinkedListEvent<T>>} */
  127. 		this.observableNodeRemove = Object.freeze(fromEvent(this, symbolLinkedListRemove));
  128. 	};
  130. 	/**
  131. 	 * @protected
  132. 	 * @throws {Error} If this LinkedList is empty.
  133. 	 * @returns {Boolean} true
  134. 	 */
  135. 	_requireNotEmpty() {
  136. 		if (this._firstNode === null) {
  137. 			throw new Error('The LinkedList is empty.');
  138. 		}
  139. 		return true;
  140. 	};
  142. 	/**
  143. 	 * @protected
  144. 	 * @throws {Error} If the given node is not a LinkedListNode.
  145. 	 * @param {LinkedListNode<T>} node
  146. 	 */
  147. 	_requireIsNode(node) {
  148. 		if (!(node instanceof LinkedListNode)) {
  149. 			throw new Error('The node is not a LinkedListNode.');
  150. 		}
  151. 		return true;
  152. 	};
  154. 	/**
  155. 	 * @protected
  156. 	 * @param {LinkedListNode<T>} node 
  157. 	 * @param {T} item 
  158. 	 * @param {Boolean} after
  159. 	 * @returns {LinkedListNode<T>} The newly added node.
  160. 	 */
  161. 	_add(node, item, after = true) {
  162. 		if (!this.hasNode(node)) {
  163. 			throw new Error('The node given is not a member of this LinkedList.');
  164. 		}
  166. 		const newNode = new LinkedListNode(
  167. 			item, this, after ? node : node.prev, after ? node.next : node);
  168. 		
  169. 		if (newNode.prev instanceof LinkedListNode) {
  170. 			newNode.prev.next = newNode;
  171. 			if (newNode.prev.prev === null) {
  172. 				this._firstNode = newNode.prev;
  173. 			}
  174. 		} else {
  175. 			this._firstNode = newNode;
  176. 		}
  178. 		if (newNode.next instanceof LinkedListNode) {
  179. 			newNode.next.prev = newNode;
  180. 			if (newNode.next.next === null) {
  181. 				this._lastNode = newNode.next;
  182. 			}
  183. 		} else {
  184. 			this._lastNode = newNode;
  185. 		}
  186. 		
  187. 		this._lookupSet.add(newNode);
  188. 		this._size++;
  189. 		
  190. 		this.emit(symbolLinkedListAdd, new LinkedListEvent(
  191. 			newNode, true, this.first === newNode, this.last === newNode));
  193. 		return newNode;
  194. 	};
  196. 	/**
  197. 	 * @override
  198. 	 * @inheritDoc
  199. 	 * @type {Number}
  200. 	 */
  201. 	get size() {
  202. 		return this._size;
  203. 	};
  205. 	/**
  206. 	 * @override
  207. 	 * @inheritDoc
  208. 	 * @type {Boolean}
  209. 	 */
  210. 	get isEmpty() {
  211. 		return this._size === 0;
  212. 	};
  214. 	/**
  215. 	 * @type {LinkedListNode<T>}
  216. 	 */
  217. 	get first() {
  218. 		this._requireNotEmpty();
  219. 		return this._firstNode;
  220. 	};
  222. 	/**
  223. 	 * @type {LinkedListNode<T>}
  224. 	 */
  225. 	get last() {
  226. 		this._requireNotEmpty();
  227. 		return this._lastNode;
  228. 	};
  230. 	/**
  231. 	 * @returns {IterableIterator<LinkedListNode<T>>}
  232. 	 */
  233. 	*nodes() {
  234. 		let node = this._firstNode;
  236. 		while (node instanceof LinkedListNode) {
  237. 			yield node;
  238. 			node = node.next;
  239. 		}
  240. 	};
  242. 	/**
  243. 	 * @returns {IterableIterator<LinkedListNode<T>>}
  244. 	 */
  245. 	*nodesReversed() {
  246. 		let node = this._lastNode;
  248. 		while (node instanceof LinkedListNode) {
  249. 			yield node;
  250. 			node = node.prev;
  251. 		}
  252. 	};
  254. 	/**
  255. 	 * @returns {IterableIterator<T>}
  256. 	 */
  257. 	*entries() {
  258. 		for (const node of this.nodes()) {
  259. 			yield node.item;
  260. 		}
  261. 	};
  263. 	/**
  264. 	 * @returns {IterableIterator<T>}
  265. 	 */
  266. 	*entriesReversed() {
  267. 		for (const node of this.nodesReversed()) {
  268. 			yield node.item;
  269. 		}
  270. 	};
  272. 	/**
  273. 	 * @override
  274. 	 * @inheritDoc
  275. 	 * @param {T} item
  276. 	 * @param {EqualityComparer<T>} [eqComparer] an optional EqualityComparer to use. If not provided, will use the Collection's EqualityComparer.
  277. 	 * @returns {Boolean}
  278. 	 */
  279. 	has(item, eqComparer = null) {
  280. 		eqComparer = eqComparer instanceof EqualityComparer ? eqComparer : this._eqComparer;
  281. 		for (const value of this.entries()) {
  282. 			if (eqComparer.equals(item, value)) {
  283. 				return true;
  284. 			}
  285. 		}
  286. 		return false;
  287. 	};
  289. 	/**
  290. 	 * Returns a value indicating whether or not this LinkedList has
  291. 	 * the node provided.
  292. 	 * 
  293. 	 * @param {LinkedListNode<T>} node
  294. 	 * @returns {Boolean}
  295. 	 */
  296. 	hasNode(node) {
  297. 		this._requireIsNode(node);
  298. 		return this._lookupSet.has(node);
  299. 	};
  300. 	
  301. 	/**
  302. 	 * @override
  303. 	 * @inheritDoc
  304. 	 * @returns {this}
  305. 	 */
  306. 	clear() {
  307. 		super.clear();
  308. 		this._firstNode = null;
  309. 		this._lastNode = null;
  310. 		this._size = 0;
  311. 		this._lookupSet.clear();
  312. 		return this;
  313. 	};
  315. 	/**
  316. 	 * @param {T} item
  317. 	 * @returns {LinkedListNode<T>} The node that has been created.
  318. 	 */
  319. 	addFirst(item) {
  320. 		if (this.isEmpty) {
  321. 			this._size++;
  322. 			this._firstNode = this._lastNode = new LinkedListNode(item, this);
  323. 			this._lookupSet.add(this._firstNode);
  324. 			this.emit(symbolLinkedListAdd, new LinkedListEvent(
  325. 				this._firstNode, true, true, true));
  326. 			return this._firstNode;
  327. 		} else {
  328. 			return this._add(this.first, item, false);
  329. 		}
  330. 	};
  332. 	/**
  333. 	 * @param {T} item
  334. 	 * @returns {LinkedListNode<T>} The node that has been created.
  335. 	 */
  336. 	addLast(item) {
  337. 		if (this.isEmpty) {
  338. 			this._size++;
  339. 			this._lastNode = this._firstNode = new LinkedListNode(item, this);
  340. 			this._lookupSet.add(this._lastNode);
  341. 			this.emit(symbolLinkedListAdd, new LinkedListEvent(
  342. 				this._lastNode, true, true, true));
  343. 			return this._lastNode;
  344. 		} else {
  345. 			return this._add(this.last, item, true);
  346. 		}
  347. 	};
  349. 	/**
  350. 	 * @param {LinkedListNode<T>} node
  351. 	 * @param {T} item
  352. 	 * @returns {LinkedListNode<T>} The newly created and inserted node.
  353. 	 */
  354. 	addAfter(node, item) {
  355. 		return this._add(node, item, true);
  356. 	};
  358. 	/**
  359. 	 * @param {LinkedListNode<T>} node
  360. 	 * @param {T} item
  361. 	 */
  362. 	addBefore(node, item) {
  363. 		return this._add(node, item, false);
  364. 	};
  366. 	/**
  367. 	 * @param {LinkedListNode<T>} node
  368. 	 * @returns {LinkedListNode} The removed node
  369. 	 */
  370. 	remove(node) {
  371. 		if (!this.hasNode(node)) {
  372. 			throw new Error('This LinkedList does not have the given node.');
  373. 		}
  375. 		/**
  376. 		 * @param {LinkedListNode<T>} theNode 
  377. 		 */
  378. 		const checkHeadTail = theNode => {
  379. 			if (theNode.prev === null) {
  380. 				this._firstNode = theNode;
  381. 			}
  382. 			if (theNode.next === null) {
  383. 				this._lastNode = theNode;
  384. 			};
  385. 		}
  387. 		let wasFirst = true, wasLast = true;
  388. 		if (node.prev instanceof LinkedListNode) {
  389. 			node.prev.next = node.next instanceof LinkedListNode ? node.next : null;
  390. 			checkHeadTail(node.prev);
  391. 			wasFirst = false;
  392. 		}
  393. 		if (node.next instanceof LinkedListNode) {
  394. 			node.next.prev = node.prev instanceof LinkedListNode ? node.prev : null;
  395. 			checkHeadTail(node.next);
  396. 			wasLast = false;
  397. 		}
  399. 		node.next = node.prev = null;
  401. 		this._size--;
  402. 		this._lookupSet.delete(node);
  403. 		this.emit(symbolLinkedListRemove, new LinkedListEvent(
  404. 			node, false, wasFirst, wasLast));
  405. 		return node;
  406. 	};
  408. 	/**
  409. 	 * @returns {LinkedListNode<T>} The first node after it has been removed
  410. 	 */
  411. 	removeFirst() {
  412. 		return this.remove(this.first);
  413. 	};
  415. 	/**
  416. 	 * @returns {LinkedListNode<T>} The last node after it has been removed.
  417. 	 */
  418. 	removeLast() {
  419. 		return this.remove(this.last);
  420. 	};
  421. };
  425. module.exports = Object.freeze({
  426. 	LinkedList,
  427. 	LinkedListNode,
  428. 	LinkedListEvent,
  429. 	symbolLinkedListAdd,
  430. 	symbolLinkedListRemove
  431. });