source: branches/MetisMQI/src/main/java/weka/gui/treevisualizer/PlaceNode2.java

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    PlaceNode2.java
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.gui.treevisualizer;

import java.util.*;

/**
 * This class will place the Nodes of a tree. <p>
 * 
 * It will place these nodes so that they fall at evenly below their parent.
 * It will then go through and look for places where nodes fall on the wrong 
 * side of other nodes
 * when it finds one it will trace back up the tree to find the first common 
 * sibling group these two nodes have
 * And it will adjust the spacing between these two siblings so that the two 
 * nodes no longer overlap.
 * This is nasty to calculate with , and takes a while with the current 
 * algorithm I am using to do this.<p>
 *
 *
 * @author Malcolm Ware (mfw4@cs.waikato.ac.nz)
 * @version $Revision: 1.4 $
 */
public class PlaceNode2 implements NodePlace {
  /** The space each row will take up. */
  private double m_yRatio;

  /** An array that lists the groups and information about them. */
  private Group[] m_groups;

  /** An array that lists the levels and information about them. */
  private Level[] m_levels;

  /** The Number of groups the tree has */
  private int m_groupNum;

  /** The number of levels the group tree has */
  private int m_levelNum;
  
  /** 
   * The Funtion to call to have the nodes arranged.
   *
   * @param r The top node of the tree to arrange.
   */
  public void place(Node r) {
    //note i might write count groups into the node class as well as
    //it may be useful too;
    
    m_groupNum = Node.getGCount(r,0); //i could swap over to the node class 
    //group count,but this works os i'm not gonna
    m_groups = new Group[m_groupNum];
        
    for (int noa = 0;noa < m_groupNum;noa++) {
      m_groups[noa] = new Group();
      m_groups[noa].m_gap = 3;
      m_groups[noa].m_start = -1;
    }
    
    groupBuild(r);
    m_levelNum = Node.getHeight(r,0);
    m_yRatio = 1 / (double)(m_levelNum + 1);
    
    m_levels = new Level[m_levelNum];
    
    for (int noa = 0;noa < m_levelNum;noa++) {
      m_levels[noa] = new Level();
    }
    r.setTop(m_yRatio);
    yPlacer();
    r.setCenter(0);
    xPlacer(0);


    //ok now i just have to untangle then scale down
    //note instead of starting with coords between 1 and 0 i will
    //use ints then scale them down 
    //i will scale them down either by all relative to the largest
    //line or by each line individually

    untangle2();
    
    scaleByMax();
    //scaleByInd();
  }


  /*
  private void thinner()
  {
    //what this function does is it retains the symmetry of the
     // parent node about the children but the children are no longer evenly
      //spaced this stops children from being pushed too far to the sides
      //,note this algorithm may need the method altered as it may 
     // require heavy optimisation to go at any decent speed   
  
    Node r,s;
    Edge e;
    double parent_x;
    for (int noa = group_num - 1;noa >= 0;noa--)
      {
        Vector shifts = new Vector(20,10);
        shifts.addElement(0);
        int g_num = 0;//this is the offset from groups.m_start to get the right 1
        r = groups[noa].m_p;
        parent_x = r.getCenter();
        for (int nob = 1;(e = r.getChild(nob)) != null;nob++)
          {
            double margin;
            s = e.getTarget();
            margin = s_getCenter - r.getChild(nob - 1).getTarget().getCenter-1
                     - shift.elementAt(nob-1);
            if (margin > 0)
              {
                margin = check_down(s,g_num,margin);
                if (margin > 0)
                  {
                    shift.addElement(-margin);
                  }
                else
                  {
                    shift.addElement(0);
                  }
              }
            else
              {
                shift.addElement(0);
              }
            if (s.getChild(0) != null)
              {
                g_num++;
              }
          }
      }
  }


  private double check_down(Node r,int gn,double m)
  {
    //note i need to know where the children of the 
    //other changers are to properly overlap check
    //to do this i think the best way is to go up the other group
    //parents line and see if it goes through the current group
    //this means to save time i need to know the level that is being 
    //worked with along with the group
    
    Edge e;
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++)
      {
        
      }
  }
*/


  /**
   * This will set initial places for the x coord of the nodes.
   * @param start The `number for the first group to start on (I think).
   */
  private void xPlacer(int start) {
    //this can be one of a few x_placers (the first)
    //it will work by placing 1 space inbetween each node
    //ie the first at 0 the second at 1 and so on
    //then it will add to this value the place of the parent 
    //node - half of the size
    //i will break this up into several functions
    //first the gap setter;
    //then the shifter
    //it will require a vector shift function added to the node class
    //i will write an additional shifter for the untangler 
    //for its particular situation

    Node r;
    Edge e;
    if (m_groupNum > 0) {
      m_groups[0].m_p.setCenter(0);
      for (int noa = start;noa < m_groupNum;noa++) {
        int nob,alter =0;
        double c = m_groups[noa].m_gap;
        r = m_groups[noa].m_p;
        for (nob = 0;(e = r.getChild(nob)) != null;nob++) {
          if (e.getTarget().getParent(0) == e) {
            e.getTarget().setCenter(nob * c);
          }
          else {
            alter++;
          }
        }
        m_groups[noa].m_size = (nob - 1 - alter) * c;
        xShift(noa);
      }
    }
  }

  /**
   * This will shift a group of nodes to be aligned under their parent.
   * @param n The group number to shift
   */
  private void xShift(int n) {
    Edge e;
    Node r = m_groups[n].m_p;
    double h = m_groups[n].m_size / 2;
    double c = m_groups[n].m_p.getCenter();
    double m = c - h;
    m_groups[n].m_left = m;
    m_groups[n].m_right = c + h;
    
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
      if (e.getTarget().getParent(0) == e) {
        e.getTarget().adjustCenter(m);
      }
    }
  }

  /**
   * This scales all the x values to be between 0 and 1.
   */
  private void scaleByMax() {
    //ammendment to what i may have commented before
    //this takes the lowest x and highest x  and uses that as the scaling
    //factor
    double l_x = 5000,h_x = -5000;
    for (int noa = 0;noa < m_groupNum;noa++) {
      if (l_x > m_groups[noa].m_left) {
        l_x = m_groups[noa].m_left;
      }

      if (h_x < m_groups[noa].m_right) {
        h_x = m_groups[noa].m_right;
      }
    }
    
    Edge e;
    Node r,s;
    double m_scale = h_x - l_x + 1;
    if (m_groupNum > 0) {
      r = m_groups[0].m_p;
      r.setCenter((r.getCenter() - l_x) / m_scale);
      //System.out.println("from scaler " + l_x + " " + m_scale);
      for (int noa = 0; noa < m_groupNum;noa++) {
        r = m_groups[noa].m_p;
        for (int nob = 0;(e = r.getChild(nob)) != null;nob++) {
          s = e.getTarget();
          if (s.getParent(0) == e) {
            s.setCenter((s.getCenter() - l_x) / m_scale);
          }
        }
      }
    }
  }
  
  /**
   * This scales the x values to between 0 and 1 for each individual line
   * rather than doing them all at once.
   */
  private void scaleByInd() {
    //ammendment to what i may have commented before
    //this takes the lowest x and highest x  on each line and uses that for 
    //the line in question
    double l_x,h_x;

    Edge e;
    Node r,s;
    r = m_groups[0].m_p;
    r.setCenter(.5);
    double m_scale;
    for (int noa = 0;noa < m_levelNum;noa++) {
      l_x = m_groups[m_levels[noa].m_start].m_left;
      h_x = m_groups[m_levels[noa].m_end].m_right;
      m_scale = h_x - l_x + 1;
      for (int nob = m_levels[noa].m_start; nob <= m_levels[noa].m_end;nob++) {
        r = m_groups[nob].m_p;
        for (int noc = 0;(e = r.getChild(noc)) != null;noc++) {
          s = e.getTarget();
          if (s.getParent(0) == e) {
            s.setCenter((s.getCenter() - l_x) / m_scale);
          }
        }
      }
    }
  }
  
  /**
   * This untangles the nodes so that they will will fall on the correct
   * side of the other nodes along their row.
   */
  private void untangle2() {
    Ease a;
    Edge e;
    Node r,nf = null,ns = null,mark;
    int l = 0,times = 0;
    int f,s,tf = 0,ts = 0,pf,ps;
    while ((a = overlap(l)) != null) {
      times++;
      //System.out.println("from untang 2 " + group_num);
      f = a.m_place;
      s = a.m_place + 1;
      while (f != s) {
        a.m_lev--;
        tf = f;
        ts = s;
        f = m_groups[f].m_pg;
        s = m_groups[s].m_pg;
      }
      l = a.m_lev;
      pf = 0;
      ps = 0;
      r = m_groups[f].m_p;
      mark = m_groups[tf].m_p;
      nf = null;
      ns = null;
      for (int noa = 0; nf != mark;noa++) {
        pf++;
        nf = r.getChild(noa).getTarget();
      }
      mark = m_groups[ts].m_p;
      for (int noa = pf; ns != mark;noa++) {
        ps++; //the number of gaps between the two nodes
        ns = r.getChild(noa).getTarget();
      }
      //m_groups[f].gap =
      //              Math.ceil((a.amount / (double)ps) + m_groups[f].gap);
      //note for this method i do not need the group gap ,but i will leave
      //it for the other methods;
      Vector o_pos = new Vector(20,10);
      for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
        if (e.getTarget().getParent(0) == e) {
          Double tem = new Double(e.getTarget().getCenter());
          o_pos.addElement(tem);
        }
      }

      pf--;
      double inc = a.m_amount / (double)ps;
      for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
        ns = e.getTarget();
        if (ns.getParent(0) == e) {
          if (noa > pf + ps) {
            ns.adjustCenter(a.m_amount);
          }
          else if (noa > pf) {
            ns.adjustCenter(inc * (double)(noa - pf));
          }
        }
      }

      nf = r.getChild(0).getTarget();
      inc = ns.getCenter() - nf.getCenter();
      m_groups[f].m_size = inc;
      m_groups[f].m_left = r.getCenter() - inc / 2; 
      m_groups[f].m_right = m_groups[f].m_left + inc;
      inc = m_groups[f].m_left - nf.getCenter();

      double shift;
      int g_num = 0;
      for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
        ns = e.getTarget();
        if (ns.getParent(0) == e) {
          ns.adjustCenter(inc);
          shift = ns.getCenter() - 
            ((Double)o_pos.elementAt(noa)).doubleValue();
          if (ns.getChild(0) != null) {
            moveSubtree(m_groups[f].m_start + g_num,shift);
            g_num++;
          }
        }
        //ns.adjustCenter(-shift);
      }
      //zero_offset(r);
      
      //x_placer(f);
    }
  }


  /**
   * This will recursively shift a sub there to be centered about
   * a particular value.
   * @param n The first group in the sub tree.
   * @param o The point to start shifting the subtree.
   */
  private void moveSubtree(int n,double o) {
    Edge e;
    Node r = m_groups[n].m_p;
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
      if (e.getTarget().getParent(0) == e) {
        e.getTarget().adjustCenter(o);
      }
    }
    m_groups[n].m_left += o;
    m_groups[n].m_right += o;
    if (m_groups[n].m_start != -1) {
      for (int noa = m_groups[n].m_start;noa <= m_groups[n].m_end;noa++) {
        moveSubtree(noa,o);
      }
    }
  }


  /**
   * This will untangle the nodes in the tree so that they fall on the
   * correct side of each other.
   */
  private void untangle() {
    Ease a;
    Edge e;
    Node r,nf = null,ns = null,mark;
    int l = 0,times = 0;
    int f,s,tf = 0,ts = 0,pf,ps;
    while ((a = overlap(l)) != null) {
      times++;
      //System.out.println(group_num);
      f = a.m_place;
      s = a.m_place + 1;
      while (f != s) {
        a.m_lev--;
        tf = f;
        ts = s;
        f = m_groups[f].m_pg;
        s = m_groups[s].m_pg;
      }
      l = a.m_lev;
      pf = 0;
      ps = 0;
      r = m_groups[f].m_p;
      mark = m_groups[tf].m_p;
      nf = null;
      ns = null;
      for (int noa = 0; nf != mark;noa++) {
        pf++;
        nf = r.getChild(noa).getTarget();
      }
      mark = m_groups[ts].m_p;
      for (int noa = pf; ns != mark;noa++) {
        ps++; //the number of gaps between the two nodes
        ns = r.getChild(noa).getTarget();
      }
      m_groups[f].m_gap =
        Math.ceil((a.m_amount / (double)ps) + m_groups[f].m_gap);
      
      xPlacer(f);
    }
  }
  
  /**
   * This will find an overlap and then return information about that overlap
   * @param l The level to start on.
   * @return null if there was no overlap , otherwise an object containing
   * the group number that overlaps (only need one) how much they overlap by,
   * and the level they overlap on.
   */
  private Ease overlap(int l) {
    Ease a = new Ease();
    for (int noa = l;noa < m_levelNum;noa++) {
      for (int nob = m_levels[noa].m_start;nob < m_levels[noa].m_end;nob++) {
        a.m_amount = m_groups[nob].m_right - m_groups[nob+1].m_left + 2;
        //System.out.println(m_groups[nob].m_right + " + " + 
        //             m_groups[nob+1].m_left + " = " + a.amount);
        if (a.m_amount >= 0) {
          a.m_amount++;
          a.m_lev = noa;
          a.m_place = nob;
          return a;
        }
      }
    }
    return null;
  }
  
  /* private int count_m_groups(Node r,int l)
  {
    Edge e;
    if (r.getChild(0) != null)
      {
        l++;
      }
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++)
      {
        l = count_groups(e.getTarget(),l);
      }

    return l;
  }
  */

  /**
   * This function sets up the height of each node, and also fills the
   * levels array with information about what the start and end groups on that
   * level are.
   */
  private void yPlacer() {
    //note this places the y height and sets up the levels array
    double changer = m_yRatio;
    int lev_place = 0;
    if (m_groupNum > 0) {
      m_groups[0].m_p.setTop(m_yRatio);
      m_levels[0].m_start = 0;
      
      for (int noa = 0;noa < m_groupNum;noa++) {
        if (m_groups[noa].m_p.getTop() != changer) {
          m_levels[lev_place].m_end = noa - 1;
          lev_place++;
          m_levels[lev_place].m_start = noa;
          changer = m_groups[noa].m_p.getTop();
        }
        nodeY(m_groups[noa].m_p);
      }
      m_levels[lev_place].m_end = m_groupNum - 1;
    }
  }

  /**
   * This will set all of the children node of a particular node to their
   * height.
   * @param r The parent node of the children to set their height. 
   */
  private void nodeY(Node r) {
    Edge e;
    double h = r.getTop() + m_yRatio;
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
      if (e.getTarget().getParent(0) == e) {
        e.getTarget().setTop(h);
        if (!e.getTarget().getVisible()) {
          //System.out.println("oh bugger");
        }
      }
    }
  }
  
  /**
   * This starts to create the information about the sibling groups.
   * As more groups are created the for loop in this will check those groups
   * for lower groups.
   * @param r The top node.
   */
  private void groupBuild(Node r) {
    if (m_groupNum > 0) {
      m_groupNum = 0;
      m_groups[0].m_p = r;
      m_groupNum++;
      //note i need to count up the num of groups first
      //woe is me
      for (int noa = 0;noa < m_groupNum ;noa++) {
        groupFind(m_groups[noa].m_p,noa);
      }
    }
  }
  
  /**
   * This is called to build the rest of the grouping information.
   * @param r The parent of the group.
   * @param pg The number for the parents group.
   */
  private void groupFind(Node r,int pg) {
    Edge e;
    boolean first = true;
    for (int noa = 0;(e = r.getChild(noa)) != null;noa++) {
      if (e.getTarget().getParent(0) == e) {
        if (e.getTarget().getChild(0) != null && e.getTarget().getCVisible()) {
          if (first) {
            m_groups[pg].m_start = m_groupNum;
            first = false;
          }
          m_groups[pg].m_end = m_groupNum;
          m_groups[m_groupNum].m_p = e.getTarget();
          m_groups[m_groupNum].m_pg = pg;
          m_groups[m_groupNum].m_id = m_groupNum; //just in case I ever need
          //this info
          m_groupNum++;
        }
      }
    }
  }
  

  //note these three classes are only to help organise the data and are
  //inter related between each other and this placer class
  //so don't mess with them or try to use them somewhere else
  //(because that would be a mistake and I would pity you)
  

  /**
   * Inner class for containing the level data.
   */
  private class Level {
    /** The number for the group on the left of this level. */
    public int m_start;
    /** The number for the group on the right of this level. */
    public int m_end;

    /** These two params would appear to not be used. */
    public int m_left;
    public int m_right;
  }

  /**
   * Inner class for containing the grouping data.
   */
  private class Group {
    /** The parent node of this group. */
    public Node m_p;

    /** The group number for the parent of this group. */
    public int m_pg;

    /** The gap size for the distance between the nodes in this group. */
    public double m_gap;

    /** The leftmost position of this group. */
    public double m_left;

    /** The rightmost position of this group. */
    public double m_right;

    /** The size of this group. */
    public double m_size;

    /** The start node of this group. */
    public int m_start;

    /** The end node of this group. */
    public int m_end;

    /** The group number for this group. (may not be used!?). */
    public int m_id;
  }
  
  /**
   * An inner class used to report information about any tangles found. 
   */
  private class Ease {
    /** The number of the group on the left of the tangle. */
    public int m_place;
    /** The distance they were tangled. */
    public double m_amount;
    /** The level on which they were tangled. */
    public int m_lev;
  }
}