////////////////// class UnionFinn  //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class UnionFinn<T>
{
  private static final class Node
  {
    private Node forelder = null;
    private int antall = 1;
  }

  Map<T, Node> noder = new HashMap<>();

  // Private hjelpemetoder

  private static Node finnRot(Node p)  // en bedre versjon
  {
    Node rotP = p;  // hjelpevariabel
    while (rotP.forelder != null) rotP = rotP.forelder;  // vi går oppover
    if (p != rotP) p.forelder = rotP;  // har vi gått oppover?
    return rotP;
  }

  private Node node(T e)
  {
    if (e == null) throw new NullPointerException("Ikke null som element!");

    Node p = noder.get(e);
    if (p == null)           // dette er et nytt element
    {
      p = new Node();        // ny node
      noder.put(e, p);       // legger inn elementet og noden
    }
    return p;
  }

  // Offentlige metoder

  public int finnMengde(T e)
  {
    Node p = noder.get(e);
    return p == null ? 0 : finnRot(p).antall;
  }

  public boolean nyMengde(T e)
  {
    if (e == null) throw new NullPointerException("Ikke null som element!");

    if (noder.get(e) != null) return false;   // elementet finnes fra før
    else
    {
      noder.put(e, new Node());               // legger inn det nye elementet
      return true;
    }
  }

  public int union(T e1, T e2)
  {
    Node rot1 = finnRot(node(e1));
    Node rot2 = finnRot(node(e2));

    if (rot1 == rot2) return 0;  // e1 og e2 er i samme mengde

    if (rot1.antall < rot2.antall)  // treet til e1 har færrest noder
    {
      rot1.forelder = rot2;
      rot2.antall += rot1.antall;
      return rot2.antall;
    }
    else // treet til e2 har færrest noder eller de har like mange
    {
      rot2.forelder = rot1;
      rot1.antall += rot2.antall;
      return rot1.antall;
    }
  }

  public String mengde(T e)
  {
    Node p = noder.get(e);
    if (p == null) throw new NoSuchElementException("Ukjent element " + e + "!");

    StringJoiner s = new StringJoiner(", ", "{", "}");
    Node rot = finnRot(p);

    for (T ee : noder.keySet())
    {
      if (finnRot(noder.get(ee)) == rot) s.add(ee.toString());
    }

    return s.toString();
  }

} // class UnionFinn