import java.util.*;
import javax.swing.*;
import javax.swing.tree.*;

public class Profile {
  /**
   * class Node - used for data collection of profiling data
   */
  static class Node {
    long itemCount = 0; // hits on this StackTraceElement
    long totalCount = 0; // hits on this and below this StackTraceElement
    HashMap<StackTraceElement, Node> children
      = new HashMap<StackTraceElement, Node>();

    public String toString() {
      return totalCount + " " + itemCount;
    }
  }

  /**
   * class DNode - used for displaying profiling data
   */
  static class DNode {
    long itemCount = 0; // hits on this StackTraceElement
    long totalCount = 0; // hits on this and below this StackTraceElement
    TreeMap<StackTraceElement, DNode> children;
    String label;

    DNode(TreeMap<StackTraceElement, DNode> children, String label) {
      this.children = children;
      this.label = label;
    }

    public String toString() {
      return label;
    }
  }

  /**
   * Comparator for class StackTraceElement
   *
   * level = 0 means just compare class name
   * level = 1 means also compare method name
   * level = 2 means also compare line number
   */
  static class STEComp implements Comparator<StackTraceElement> {
    int level;

    STEComp(int level) {
      this.level = level;
    }

    public int compare(StackTraceElement s1, StackTraceElement s2) {
      int c = s1.getClassName().compareTo(s2.getClassName());
      if(c != 0) {
        return c;
      }
      if(level <= 0) return 0;
      c = s1.getMethodName().compareTo(s2.getMethodName());
      if(c != 0) {
        return c;
      }
      if(level <= 1) return 0;
      c = s1.getLineNumber() - s2.getLineNumber();
      return c;
    }
  }

  Thread t; // the thread being profiled
  java.util.Timer timer; // the timer being used for profiling


  HashMap<StackTraceElement, Node> data
    = new HashMap<StackTraceElement, Node>(); // map of maps used for data

  long count = 0; // number of samples taken

  boolean collecting; // flag used for synchronizing collector thread

  /**
   * Create a new profiler on current thread
   */
  Profile() {
    t = Thread.currentThread();
  }

  /**
   * Create a new profiler on specific thread
   *
   * @param thread the thread to profile
   */
  Profile(Thread thread) {
    t = thread;
  }

  /**
   * Start profiling - this method waits until the thread is active
   * and stops when the thread terminates
   *
   * @param t the Thread to profile
   * @param interval the time in milliseconds between samples
   * @param collapseMethods true if different lines in same method collapsed
   * @return the timer object doing the sampling
   */
  void start(long interval) {
    synchronized(this) {
      collecting = true;
    }
    Thread th = Thread.currentThread();
    int p = th.getPriority();
    th.setPriority(10); // should be static
    timer = new java.util.Timer("Profiler");
    th.setPriority(p);
    java.util.TimerTask task =
      new java.util.TimerTask(){
        public void run() {
          synchronized(Profile.this) {
            switch(t.getState()) {
            case NEW:
              break;
            case RUNNABLE:
            case BLOCKED:
            case WAITING:
            case TIMED_WAITING:
              count++;
              StackTraceElement stack[] = t.getStackTrace();
              // do something with it
              HashMap<StackTraceElement, Node> node = data;
              for(int i = stack.length-1; i >= 0; i--) {
                Node child = node.get(stack[i]);
                if(child == null) {
                  child = new Node();
                  node.put(stack[i], child);
                }
                child.totalCount++;
                if(i==0) child.itemCount++;
                node = child.children;
              }
              break;
            case TERMINATED:
              // kill the timer
              timer.cancel();
              break;
            }
          }
        }
      };
    timer.schedule(task, interval, interval);
  }

  long stop() {
    java.util.TimerTask task =
      new java.util.TimerTask(){
        public void run() {
          timer.cancel();
          timer = null;
          synchronized(Profile.this) {
            collecting = false;
            Profile.this.notifyAll();
          }
        }
      };
    timer.schedule(task, 0);
    synchronized(this) {
      while (collecting == true) {
        try {
          this.wait();
        } catch(InterruptedException e) {}
      }
    }
    return count;
  }

  /**
   * Copies map to dmap merging entries equivalent by comp
   *
   * @param treeNode source data
   * @param dataNode destination data
   */
  void copyTree(HashMap<StackTraceElement, Node> map,
                TreeMap<StackTraceElement, DNode> dmap) {
    STEComp comp = (STEComp)dmap.comparator();
    for(Map.Entry<StackTraceElement, Node> entry: map.entrySet()) {
      StackTraceElement stackElement = entry.getKey();
      Node node = entry.getValue();
      DNode dnode = dmap.get(stackElement);
      if(dnode == null) {
        // level 0 class-name
        // level 1 class.method
        // level 2 class.method(line)
        String label = stackElement.getClassName();
        if(comp.level > 0) label += "." + stackElement.getMethodName();
        if(comp.level > 1) label += "(" + stackElement.getLineNumber() + ")";
        dnode = new DNode(new TreeMap<StackTraceElement, DNode>(comp), label);
        dmap.put(stackElement, dnode);
      }
      dnode.itemCount += node.itemCount;
      dnode.totalCount += node.totalCount;
      copyTree(node.children, dnode.children);
    }
  }

  /**
   * Copies map to dmap flattening the tree and retaining only the
   * last stack frame.
   *
   * @param treeNode source data
   * @param dataNode destination data
   */
  void flattenTree(HashMap<StackTraceElement, Node> map,
                   TreeMap<StackTraceElement, DNode> dmap,
                   TreeSet<StackTraceElement> parents) {
    STEComp comp = (STEComp)dmap.comparator();
    if(parents == null) {
      parents = new TreeSet<StackTraceElement>(comp);
    }
    for(Map.Entry<StackTraceElement, Node> entry: map.entrySet()) {
      StackTraceElement stackElement = entry.getKey();
      Node node = entry.getValue();
      DNode dnode = dmap.get(stackElement);
      if(dnode == null) {
        //STEComp comp = (STEComp)dmap.comparator();
        // level 0 class-name
        // level 1 class.method
        // level 2 class.method(line)
        String label = stackElement.getClassName();
        if(comp.level > 0) label += "." + stackElement.getMethodName();
        if(comp.level > 1) label += "(" + stackElement.getFileName()
                             + ":" + stackElement.getLineNumber() + ")";
        dnode = new DNode(null, label);
        dmap.put(stackElement, dnode);
      }
      dnode.itemCount += node.itemCount;
      TreeSet<StackTraceElement> heritage =
        new TreeSet<StackTraceElement>(parents);
      heritage.add(stackElement);
      for(StackTraceElement ste: heritage) {
        dmap.get(ste).totalCount += node.itemCount;
      }
      flattenTree(node.children, dmap, heritage);
    }
  }

  void display(HashMap<StackTraceElement, Node> node, int level) {
    for(Map.Entry<StackTraceElement, Node> entry: node.entrySet()) {
      for(int i = 0; i < level; i++) {
        System.out.print("  ");
      }
      System.out.print(entry.getValue().totalCount + " ");
      System.out.print(entry.getValue().itemCount + " ");
      System.out.println(entry.getKey());
      display(entry.getValue().children, level + 1);
    }
  }

  /**
   * Display profiling data in a JTree
   *
   * type = 0 - do no merging
   * type = 1 - ignore differing line numbers
   * type = 2 - ignore differing methods in class
   *
   * @param prune cutoff below which nodes are not displayed
   * @param type parameter on which samples to merge
   */
  void display(long prune, int type) {
    if(timer != null) {
      timer.cancel();
      timer = null;
    }
    display(data, 0);
  }

  void ddisplay(TreeMap<StackTraceElement, DNode> node,
                int level) {
    for(Map.Entry<StackTraceElement, DNode> entry: node.entrySet()) {
      for(int i = 0; i < level; i++) {
        System.out.print("  ");
      }
      System.out.print(entry.getValue().totalCount + " ");
      System.out.print(entry.getValue().itemCount + " ");
      System.out.print(entry.getValue().label + " ");
      System.out.println(entry.getKey());
      ddisplay(entry.getValue().children, level + 1);
    }
  }

  /**
   * Display profiling data in a JTree
   *
   * type = 0 - do no merging
   * type = 1 - ignore differing line numbers
   * type = 2 - ignore differing methods in class
   *
   * @param prune cutoff below which nodes are not displayed
   * @param type parameter on which samples to merge
   */
  void ddisplay(long prune, int type) {
    if(timer != null) {
      timer.cancel();
      timer = null;
    }
    TreeMap<StackTraceElement, DNode> dmap0
      = new TreeMap<StackTraceElement, DNode>(new STEComp(0));
    TreeMap<StackTraceElement, DNode> dmap1
      = new TreeMap<StackTraceElement, DNode>(new STEComp(1));
    TreeMap<StackTraceElement, DNode> dmap2
      = new TreeMap<StackTraceElement, DNode>(new STEComp(2));
    copyTree(data, dmap0);
    copyTree(data, dmap1);
    copyTree(data, dmap2);
    System.out.println();
    ddisplay(dmap0, 0);
    System.out.println();
    ddisplay(dmap1, 0);
    System.out.println();
    ddisplay(dmap2, 0);
  }

  /**
   * Display profiling data in a JTree
   *
   * type = 0 - do no merging
   * type = 1 - ignore differing line numbers
   * type = 2 - ignore differing methods in class
   *
   * @param prune cutoff below which nodes are not displayed
   * @param type parameter on which samples to merge
   */
  void fdisplay(long prune, int type) {
    if(timer != null) {
      timer.cancel();
      timer = null;
    }
    for(int level = 0; level <= 2; level++) {
      System.out.println("Level = " + level);
      TreeMap<StackTraceElement, DNode> dmap
        = new TreeMap<StackTraceElement, DNode>(new STEComp(level));
      flattenTree(data, dmap, null);
      for(Map.Entry<StackTraceElement, DNode> entry: dmap.entrySet()) {
        System.out.print(entry.getValue().totalCount + " ");
        System.out.print(entry.getValue().itemCount + " ");
        System.out.println(entry.getValue().label);
      }
    }
  }

  static Object stuff(int i) {
    Object o = new Object();
    stuff1();
    stuff1();
    return o;
  }

  static Object stuff1() {
    Object o = new Object();
    stuff2();
    stuff2();
    return o;
  }

  static Object stuff2() {
    Object o = new Object();
    stuff3();
    stuff3();
    return o;
  }

  static Object stuff3() {
    Object o = new Object();
    stuff4();
    stuff4();
    return o;
  }

  static Object stuff4() {
    Object o = new Object();
    stuff5();
    stuff5();
    return o;
  }

  static Object stuff5() {
    for(int i = 0; i < 100; i++) ;
    return new Object();
  }

  public static void main(String...args) {
    StackTraceElement stack[] = Thread.currentThread().getStackTrace();
    for(StackTraceElement elem: stack) {
      System.out.println(elem);
    }
    for(StackTraceElement elem: stack) {
      System.out.println(elem.getClassName());
      System.out.println(elem.getFileName());
      System.out.println(elem.getLineNumber());
      System.out.println(elem.getMethodName());
    }
    Profile p = new Profile();
    p.start(10);
    for(int i = 0; i < 300000; i++) stuff(5);
    for(int i = 0; i < 300000; i++) stuff(4);
    for(int i = 0; i < 300000; i++) stuff(3);
    for(int i = 0; i < 300000; i++) stuff(2);
    System.out.println("samples = " + p.stop());
    System.out.println("----------");
    p.display(1,1);
    System.out.println("----------");
    p.ddisplay(1,1);
    System.out.println("----------");
    p.fdisplay(1, 1);
    /*
    DefaultMutableTreeNode b11 = new DefaultMutableTreeNode("b11");
    DefaultMutableTreeNode b12 = new DefaultMutableTreeNode("b12");
    DefaultMutableTreeNode m1 = new DefaultMutableTreeNode("m1");
    m1.add(b11);
    m1.add(b12);
    DefaultMutableTreeNode b21 = new DefaultMutableTreeNode("b21");
    DefaultMutableTreeNode b22 = new DefaultMutableTreeNode("b22");
    DefaultMutableTreeNode m2 = new DefaultMutableTreeNode("m2");
    m2.add(b21);
    m2.add(b22);
    DefaultMutableTreeNode top = new DefaultMutableTreeNode("top");
    top.add(m1);
    top.add(m2);
    JTree jt = new JTree(top);
    //jt.setRootVisible(false);
    jt.expandPath(new TreePath(m2.getPath()));
    jt.collapsePath(new TreePath(top.getPath()));
    JFrame jf = new JFrame("Tree");
    jf.getContentPane().add(jt);
    jf.pack();
    jf.setVisible(true);
    */
  }
} // class Profile