package yi.ds;

public class Merge
{
  int[] parent;

  public Merge(int size) {
    parent = new int[size];
    for (int i = 0; i < size; i++)
      parent[i] = i;
  }

  public void merge(int from, int to) {
    //find the parents of i and j
    int label_from = parent[from] = findParent(from);
    int label_to = parent[to] = findParent(to);

    if (label_from == label_to)
      return;

    //combine the histogram also
    parent[label_from] = label_to;
  }

  public int findParent(int x) {
    while (x != parent[x])
      x = parent[x];
    return x;
  }

  /**
   * Return the merge result.  result[from] = to, in which "from" it is the label
   * changed from and "to" is the label changed to
   * @return
   */
  public int[] result() {
    for (int i = 0; i < parent.length; i++)
      parent[i] = findParent(i);
    return parent;
  }

  /**
   * @return the merge results "decently".
   * Reassign the index to the compacted one.
   * The result[size] is the the size of compacted index.
   */
  public int[] decentResult() {
    for (int i = 0; i < parent.length; i++)
      parent[i] = findParent(i);

    boolean[] isRoot = new boolean[parent.length];
    for (int i = 0; i < isRoot.length; i++)
      if (parent[i] == i)
        isRoot[i] = true;
      else
        isRoot[i] = false;

    int[] map = new int[parent.length];
    int count = -1;
    for (int i = 0; i < map.length; i++) {
      if (isRoot[i]) {
        count++;
        map[i] = count;
      }
      else
        map[i] = -1;
    }

    int[] newIndex = new int[parent.length];
    for (int i = 0; i < parent.length; i++) {
      newIndex[i] = map[parent[i]];
    }
    return newIndex;
  }

  /**
   * Return the roots of the merge.  A root is a node which is the parent of
   * others.  A node which is only the "parent" of itself is not counted as
   * a root.
   * @return
   */
  public boolean[] getRoots() {
    boolean[] roots = new boolean[parent.length];
    int i;
    for (i = 0; i < roots.length; i++)
      roots[i] = false;
    int[] rootmap = result();
    for (i = 0; i < rootmap.length; i++)
      if (i != rootmap[i])
        roots[rootmap[i]] = true;
    return roots;
  }

  public int size() {
    int count = 0;
    for (int i = 0; i < parent.length; i++)
      if (i == findParent(i))
        count++;
    return count;

  }
}