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

   1 package net.mograsim.logic.model.verilog.utils;
   2
   3 import java.util.Collection;
   4 import java.util.HashMap;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7
   8 public class UnionFind<E>
   9 {
  10         private final Map<E, UnionFindElement<E>> elements;
  11
  12         public UnionFind()
  13         {
  14                 this.elements = new HashMap<>();
  15         }
  16
  17         public UnionFindElement<E> getElement(E e)
  18         {
  19                 return elements.computeIfAbsent(e, UnionFindElement::new);
  20         }
  21
  22         public E find(E e)
  23         {
  24                 return find(getElement(e)).getE();
  25         }
  26
  27         public static <E> UnionFindElement<E> find(UnionFindElement<E> elem)
  28         {
  29                 if (elem == elem.parent)
  30                         return elem;
  31                 return elem.parent = find(elem.parent);
  32         }
  33
  34         public E union(E e1, E e2)
  35         {
  36                 return union(getElement(e1), getElement(e2)).getE();
  37         }
  38
  39         public static <E> UnionFindElement<E> union(UnionFindElement<E> e1, UnionFindElement<E> e2)
  40         {
  41                 UnionFindElement<E> e1Root = find(e1);
  42                 UnionFindElement<E> e2Root = find(e2);
  43
  44                 if (e1Root == e2Root)
  45                         return e1Root;
  46
  47                 if (e1Root.rank < e2Root.rank)
  48                         return e1Root.parent = e2Root;
  49                 else if (e1Root.rank > e2Root.rank)
  50                         return e2Root.parent = e1Root;
  51                 else
  52                 {
  53                         e2Root.rank++;
  54                         return e1Root.parent = e2Root;
  55                 }
  56         }
  57
  58         public E unionAll(Collection<E> es)
  59         {
  60                 Iterator<E> it = es.iterator();
  61                 if (!it.hasNext())
  62                         return null;
  63
  64                 UnionFindElement<E> representant = getElement(it.next());
  65
  66                 while (it.hasNext())
  67                         representant = union(representant, getElement(it.next()));
  68
  69                 return representant.getE();
  70         }
  71
  72         public static <E> UnionFindElement<E> unionAll2(Collection<UnionFindElement<E>> es)
  73         {
  74                 Iterator<UnionFindElement<E>> it = es.iterator();
  75                 if (!it.hasNext())
  76                         return null;
  77
  78                 UnionFindElement<E> representant = it.next();
  79
  80                 while (it.hasNext())
  81                         representant = union(representant, it.next());
  82
  83                 return representant;
  84         }
  85
  86         public static class UnionFindElement<E>
  87         {
  88                 private final E e;
  89                 private UnionFindElement<E> parent;
  90                 private int rank;
  91
  92                 private UnionFindElement(E e)
  93                 {
  94                         this.e = e;
  95                         this.parent = this;
  96                 }
  97
  98                 public E getE()
  99                 {
 100                         return e;
 101                 }
 102         }
 103 }