CREATE TABLE dup(id SERIAL PRIMARY KEY, email TEXT NOT NULL, phone NOT NULL);

INSERT INTO dup(email, phone) VALUES('a','1'),('a','2'), ('b','2'), ('c','1'), ('d', '3')

SELECT DISTINCT ON(phone) * FROM 
(SELECT DISTINCT ON(email) * FROM dup) AS q;

SELECT DISTINCT ON(email) * FROM 
(SELECT DISTINCT ON(phone) * FROM dup) AS q;

WITH RECURSIVE connected_groups AS (
	-- Base case: each row starts as its own group
	SELECT 
		id, 
		email, 
		phone, 
		id AS group_id
	FROM dup

	UNION

	-- Recursive case: find connections via email or phone
	SELECT 
		d.id, 
		d.email, 
		d.phone, 
		cg.group_id
	FROM dup d JOIN connected_groups cg 
	ON d.email = cg.email OR d.phone = cg.phone
	WHERE d.id <> cg.id
),
min_group AS (
	-- Find the smallest group_id for each row's group
	SELECT 
		cg.id, 
		MIN(cg.group_id) AS group_id
	FROM connected_groups cg
	GROUP BY 
		cg.id
)
SELECT d.* FROM dup d
JOIN 
  min_group mg 
  ON d.id = mg.id
JOIN (
	-- Select one row per group (e.g., the row with the smallest id)
	SELECT 
		mg.group_id, 
		MIN(mg.id) AS min_id
	FROM min_group mg
	GROUP BY 
		mg.group_id
) grp 
ON mg.group_id = grp.group_id AND mg.id = grp.min_id;

TRUNCATE dup RESTART IDENTITY;
INSERT INTO dup(email,phone) VALUES
('a','1'),
('a','2'),
('b','2'),
('a','3'),
('a','4'),
('c','4');

TRUNCATE dup RESTART IDENTITY;
INSERT INTO dup(email,phone) VALUES
('a','1'),
('a','2'),
('b','2'),
('c','4'),
('c','5'),
('d','5');

CREATE TABLE IF NOT EXISTS email_group(id SERIAL PRIMARY KEY, email TEXT NOT NULL, ids INTEGER[]);

INSERT INTO email_group(email, ids) 
SELECT DISTINCT ON(email) email, ARRAY_AGG(id) 
FROM dup GROUP BY email;

CREATE TABLE IF NOT EXISTS phone_group(id SERIAL PRIMARY KEY, phone TEXT NOT NULL, ids INTEGER[]);

INSERT INTO phone_group(phone, ids)
SELECT DISTINCT ON(phone) phone, ARRAY_AGG(id) 
FROM dup GROUP BY phone;

SELECT * FROM dup;
 id | email | phone 
----+-------+-------
  1 | a     | 1
  2 | a     | 2
  3 | b     | 2
  4 | a     | 3
  5 | a     | 4
  6 | c     | 4
(6 rows)

SELECT * FROM email_group;
 id | email |    ids    
----+-------+-----------
  1 | a     | {1,2,4,5}
  2 | b     | {3}
  3 | c     | {6}
(3 rows)

SELECT * FROM phone_group;
 id | phone |  ids  
----+-------+-------
  1 | 1     | {1}
  2 | 2     | {2,3}
  3 | 3     | {4}
  4 | 4     | {5,6}
(4 rows)

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, i) => i);
        this.rank = Array(size).fill(1);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // Path compression
        }
        return this.parent[x];
    }

    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        
        if (rootX !== rootY) {
            // Union by rank
            if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX] += 1;
            }
        }
    }
}

function findDuplicates(groups) {
    const elementToIndex = {}; 
    let nextIndex = 0;
    let processedElements = 0;

    // Assign a unique index to every unique element across all groups
    console.log(`Assigning unique indices to elements in ${groups.length} groups...`);
    for (let group of groups) {
        for (let element of group) {
            if (!(element in elementToIndex)) { // Check existence in the object
                elementToIndex[element] = nextIndex++;
            }
        }
        // Log progress for every 100,000 groups processed
        processedElements++;
        if (processedElements % 100000 === 0) {
            console.log(`Processed ${processedElements} groups for unique indexing...`);
        }
    }
    console.log(`Finished assigning indices. Total unique elements: ${nextIndex}`);

    // Initialize union-find data structure
    const uf = new UnionFind(nextIndex);

    // Union elements within each group
    console.log(`Performing union operations for ${groups.length} groups...`);
    processedElements = 0;
    for (let group of groups) {
        for (let i = 1; i < group.length; i++) {
            uf.union(elementToIndex[group[0]], elementToIndex[group[i]]);
        }
        // Log progress for every 100,000 groups processed
        processedElements++;
        if (processedElements % 100000 === 0) {
            console.log(`Performed union operations for ${processedElements} groups...`);
        }
    }
    console.log(`Finished union operations.`);

    // Find unique sets
    console.log(`Finding unique sets...`);
    const rootToGroup = {};
    let elementCount = 0;
    for (let element in elementToIndex) {
        let root = uf.find(elementToIndex[element]);
        if (!(root in rootToGroup)) {
            rootToGroup[root] = [];
        }
        rootToGroup[root].push(element);
        
        // Log progress for every 100,000 elements processed
        elementCount++;
        if (elementCount % 100000 === 0) {
            console.log(`Processed ${elementCount} elements for unique sets...`);
        }
    }
    console.log(`Finished finding unique sets. Total unique groups: ${Object.keys(rootToGroup).length}`);

    // Collect results
    return Object.values(rootToGroup);
}

async function main() {

		const group1 = [[1,2,3],[2]];
		const group2 = [[4,5], [1,3]];

    console.log(`group1 size: ${group1.length}, group2 size: ${group2.length}`);

    // Combine all groups into one
    console.log('Starting to find duplicates...');
    const mergedGroups = findDuplicates([...group1, ...group2]);

		await fs.writeFile("duplicates.json", JSON.stringify(mergedGroups, null, 2), {encoding: "utf8"});
		let cnt = 0;
		for (const a of mergedGroups) {
			if (a.length > 1) {
				cnt++;
			}
		}
		console.log(`Number of found duplicate groups: ${cnt}`);

    pool.end();
}

main();