1 package net.mograsim.logic.model.verilog.utils;
3 import java.util.Collection;
4 import java.util.HashMap;
5 import java.util.Iterator;
8 public class UnionFind<E>
10 private final Map<E, UnionFindElement<E>> elements;
14 this.elements = new HashMap<>();
17 public UnionFindElement<E> getElement(E e)
19 return elements.computeIfAbsent(e, UnionFindElement::new);
24 return find(getElement(e)).getE();
27 public static <E> UnionFindElement<E> find(UnionFindElement<E> elem)
29 if (elem == elem.parent)
31 return elem.parent = find(elem.parent);
34 public E union(E e1, E e2)
36 return union(getElement(e1), getElement(e2)).getE();
39 public static <E> UnionFindElement<E> union(UnionFindElement<E> e1, UnionFindElement<E> e2)
41 UnionFindElement<E> e1Root = find(e1);
42 UnionFindElement<E> e2Root = find(e2);
47 if (e1Root.rank < e2Root.rank)
48 return e1Root.parent = e2Root;
49 else if (e1Root.rank > e2Root.rank)
50 return e2Root.parent = e1Root;
54 return e1Root.parent = e2Root;
58 public E unionAll(Collection<E> es)
60 Iterator<E> it = es.iterator();
64 UnionFindElement<E> representant = getElement(it.next());
67 representant = union(representant, getElement(it.next()));
69 return representant.getE();
72 public static <E> UnionFindElement<E> unionAll2(Collection<UnionFindElement<E>> es)
74 Iterator<UnionFindElement<E>> it = es.iterator();
78 UnionFindElement<E> representant = it.next();
81 representant = union(representant, it.next());
86 public static class UnionFindElement<E>
89 private UnionFindElement<E> parent;
92 private UnionFindElement(E e)