Add disjoint set. · halyna-dev/javascript-algorithms@843893e · GitHub

halyna-dev / javascript-algorithms Public

forked from trekhleb/javascript-algorithms

• Notifications You must be signed in to change notification settings
• Fork 0
• Star 0

• Code
• Pull requests
• Actions
• Projects
• Security and quality
• Insights

Additional navigation options

Commit 843893e

Browse filesBrowse the repository at this point in the historyBrowse files

trekhleb

committed

Add disjoint set.

1 parent 2e76caa commit 843893e
Copy full SHA for 843893e

3 files changed

+28-22Lines changed: 28 additions & 22 deletions

File tree

Expand file treeCollapse file tree

Open diff view settings

Filter options

• src/data-structures/disjoint-set
  • DisjointSet.js
  • DisjointSetItem.js
  • __test__
    • DisjointSetItem.test.js

Expand file treeCollapse file tree

Open diff view settings

Collapse file

‎src/data-structures/disjoint-set/DisjointSet.js‎

Copy file name to clipboardExpand all lines: src/data-structures/disjoint-set/DisjointSet.js

+5-1Lines changed: 5 additions & 1 deletion

Original file line number	Diff line number	Diff line change
@@ -25,6 +25,8 @@ export default class DisjointSet {
25	25	}
26	26
27	27	/**
	28	+ * Find set representation node.
	29	+ *
28	30	* @param {*} itemValue
29	31	* @return {(string|null)}
30	32	*/
@@ -42,6 +44,8 @@ export default class DisjointSet {
42	44	}
43	45
44	46	/**
	47	+ * Union by rank.
	48	+ *
45	49	* @param {*} valueA
46	50	* @param {*} valueB
47	51	* @return {DisjointSet}
@@ -62,7 +66,7 @@ export default class DisjointSet {
62	66	const rootA = this.items[rootKeyA];
63	67	const rootB = this.items[rootKeyB];
64	68
65		- if (rootA.getAncestorsCount() < rootB.getAncestorsCount()) {
	69	+ if (rootA.getRank() < rootB.getRank()) {
66	70	// If rootB's tree is bigger then make rootB to be a new root.
67	71	rootB.addChild(rootA);
68	72

Collapse file

‎src/data-structures/disjoint-set/DisjointSetItem.js‎

Copy file name to clipboardExpand all lines: src/data-structures/disjoint-set/DisjointSetItem.js

+7-5Lines changed: 7 additions & 5 deletions

Original file line number	Diff line number	Diff line change
@@ -39,25 +39,27 @@ export default class DisjointSetItem {
39	39	}
40	40
41	41	/**
	42	+ * Rank basically means the number of all ancestors.
	43	+ *
42	44	* @return {number}
43	45	*/
44		- getAncestorsCount() {
	46	+ getRank() {
45	47	if (this.getChildren().length === 0) {
46	48	return 0;
47	49	}
48	50
49		- let count = 0;
	51	+ let rank = 0;
50	52
51	53	/** @var {DisjointSetItem} child */
52	54	this.getChildren().forEach((child) => {
53	55	// Count child itself.
54		- count += 1;
	56	+ rank += 1;
55	57
56	58	// Also add all children of current child.
57		- count += child.getAncestorsCount();
	59	+ rank += child.getRank();
58	60	});
59	61
60		- return count;
	62	+ return rank;
61	63	}
62	64
63	65	/**

Collapse file

‎src/data-structures/disjoint-set/__test__/DisjointSetItem.test.js‎

Copy file name to clipboardExpand all lines: src/data-structures/disjoint-set/__test__/DisjointSetItem.test.js

+16-16Lines changed: 16 additions & 16 deletions

Original file line number	Diff line number	Diff line change
@@ -7,7 +7,7 @@ describe('DisjointSetItem', () => {
7	7	const itemC = new DisjointSetItem('C');
8	8	const itemD = new DisjointSetItem('D');
9	9
10		- expect(itemA.getAncestorsCount()).toBe(0);
	10	+ expect(itemA.getRank()).toBe(0);
11	11	expect(itemA.getChildren()).toEqual([]);
12	12	expect(itemA.getKey()).toBe('A');
13	13	expect(itemA.getRoot()).toEqual(itemA);
@@ -17,11 +17,11 @@ describe('DisjointSetItem', () => {
17	17	itemA.addChild(itemB);
18	18	itemD.setParent(itemC);
19	19
20		- expect(itemA.getAncestorsCount()).toBe(1);
21		- expect(itemC.getAncestorsCount()).toBe(1);
	20	+ expect(itemA.getRank()).toBe(1);
	21	+ expect(itemC.getRank()).toBe(1);
22	22
23		- expect(itemB.getAncestorsCount()).toBe(0);
24		- expect(itemD.getAncestorsCount()).toBe(0);
	23	+ expect(itemB.getRank()).toBe(0);
	24	+ expect(itemD.getRank()).toBe(0);
25	25
26	26	expect(itemA.getChildren().length).toBe(1);
27	27	expect(itemC.getChildren().length).toBe(1);
@@ -50,9 +50,9 @@ describe('DisjointSetItem', () => {
50	50	expect(itemC.isRoot()).toBeFalsy();
51	51	expect(itemD.isRoot()).toBeFalsy();
52	52
53		- expect(itemA.getAncestorsCount()).toEqual(3);
54		- expect(itemB.getAncestorsCount()).toEqual(0);
55		- expect(itemC.getAncestorsCount()).toEqual(1);
	53	+ expect(itemA.getRank()).toEqual(3);
	54	+ expect(itemB.getRank()).toEqual(0);
	55	+ expect(itemC.getRank()).toEqual(1);
56	56	});
57	57
58	58	it('should do basic manipulation with disjoint set item with custom key extractor', () => {
@@ -65,7 +65,7 @@ describe('DisjointSetItem', () => {
65	65	const itemC = new DisjointSetItem({ key: 'C', value: 3 }, keyExtractor);
66	66	const itemD = new DisjointSetItem({ key: 'D', value: 4 }, keyExtractor);
67	67
68		- expect(itemA.getAncestorsCount()).toBe(0);
	68	+ expect(itemA.getRank()).toBe(0);
69	69	expect(itemA.getChildren()).toEqual([]);
70	70	expect(itemA.getKey()).toBe('A');
71	71	expect(itemA.getRoot()).toEqual(itemA);
@@ -75,11 +75,11 @@ describe('DisjointSetItem', () => {
75	75	itemA.addChild(itemB);
76	76	itemD.setParent(itemC);
77	77
78		- expect(itemA.getAncestorsCount()).toBe(1);
79		- expect(itemC.getAncestorsCount()).toBe(1);
	78	+ expect(itemA.getRank()).toBe(1);
	79	+ expect(itemC.getRank()).toBe(1);
80	80
81		- expect(itemB.getAncestorsCount()).toBe(0);
82		- expect(itemD.getAncestorsCount()).toBe(0);
	81	+ expect(itemB.getRank()).toBe(0);
	82	+ expect(itemD.getRank()).toBe(0);
83	83
84	84	expect(itemA.getChildren().length).toBe(1);
85	85	expect(itemC.getChildren().length).toBe(1);
@@ -108,8 +108,8 @@ describe('DisjointSetItem', () => {
108	108	expect(itemC.isRoot()).toBeFalsy();
109	109	expect(itemD.isRoot()).toBeFalsy();
110	110
111		- expect(itemA.getAncestorsCount()).toEqual(3);
112		- expect(itemB.getAncestorsCount()).toEqual(0);
113		- expect(itemC.getAncestorsCount()).toEqual(1);
	111	+ expect(itemA.getRank()).toEqual(3);
	112	+ expect(itemB.getRank()).toEqual(0);
	113	+ expect(itemC.getRank()).toEqual(1);
114	114	});
115	115	});

0 commit comments

Comments

0 (0)