plugins/net.mograsim.logic.model.verilog/src/net/mograsim/logic/model/verilog/helper/UnionFind.java

   1 package net.mograsim.logic.model.verilog.helper;
   2
   3 import java.util.HashMap;
   4 import java.util.Map;
   5
   6 public class UnionFind<E>
   7 {
   8         private final Map<E, UnionFindElement<E>> elements;
   9
  10         public UnionFind()
  11         {
  12                 this.elements = new HashMap<>();
  13         }
  14
  15         public UnionFindElement<E> getElement(E e)
  16         {
  17                 return elements.computeIfAbsent(e, UnionFindElement::new);
  18         }
  19
  20         public E find(E e)
  21         {
  22                 return find(getElement(e)).getE();
  23         }
  24
  25         public static <E> UnionFindElement<E> find(UnionFindElement<E> elem)
  26         {
  27                 if (elem == elem.parent)
  28                         return elem;
  29                 return elem.parent = find(elem.parent);
  30         }
  31
  32         public E union(E e1, E e2)
  33         {
  34                 return union(getElement(e1), getElement(e2)).getE();
  35         }
  36
  37         public static <E> UnionFindElement<E> union(UnionFindElement<E> e1, UnionFindElement<E> e2)
  38         {
  39                 UnionFindElement<E> e1Root = find(e1);
  40                 UnionFindElement<E> e2Root = find(e2);
  41
  42                 if (e1Root == e2Root)
  43                         return e1Root;
  44
  45                 if (e1Root.rank < e2Root.rank)
  46                         return e1Root.parent = e2Root;
  47                 else if (e1Root.rank > e2Root.rank)
  48                         return e2Root.parent = e1Root;
  49                 else
  50                 {
  51                         e2Root.rank++;
  52                         return e1Root.parent = e2Root;
  53                 }
  54         }
  55
  56         public static class UnionFindElement<E>
  57         {
  58                 private final E e;
  59                 private UnionFindElement<E> parent;
  60                 private int rank;
  61
  62                 private UnionFindElement(E e)
  63                 {
  64                         this.e = e;
  65                         this.parent = this;
  66                 }
  67
  68                 public E getE()
  69                 {
  70                         return e;
  71                 }
  72         }
  73 }