Ignore:
Timestamp:
07/18/16 12:26:03 (8 years ago)
Author:
sherbold
Message:
  • code documentation and formatting
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/CrossPare/src/de/ugoe/cs/cpdp/training/QuadTree.java

    r86 r135  
    2424 
    2525/** 
    26  * QuadTree implementation 
     26 * <p> 
     27 * QuadTree implementation. 
     28 * </p> 
     29 * <p> 
     30 * QuadTree gets a list of instances and then recursively split them into 4 children For this it 
     31 * uses the median of the 2 values x,y. 
     32 * </p> 
    2733 *  
    28  * QuadTree gets a list of instances and then recursively split them into 4 childs For this it uses 
    29  * the median of the 2 values x,y 
     34 * @author Alexander Trautsch 
    3035 */ 
    3136public class QuadTree { 
    3237 
    33     /* 1 parent or null */ 
     38    /** 
     39     * 1 parent or null 
     40     */ 
    3441    private QuadTree parent = null; 
    3542 
    36     /* 4 childs, 1 per quadrant */ 
     43    /** 
     44     * north-west quadrant 
     45     */ 
    3746    private QuadTree child_nw; 
     47 
     48    /** 
     49     * north-east quadrant 
     50     */ 
    3851    private QuadTree child_ne; 
     52 
     53    /** 
     54     * south-east quadrant 
     55     */ 
    3956    private QuadTree child_se; 
     57 
     58    /** 
     59     * south-west quadrant 
     60     */ 
    4061    private QuadTree child_sw; 
    4162 
    42     /* list (only helps with generation of list of childs!) */ 
     63    /** 
     64     * helper list for child quadrant generation 
     65     */ 
    4366    private ArrayList<QuadTree> l = new ArrayList<QuadTree>(); 
    4467 
    45     /* level only used for debugging */ 
     68    /** 
     69     * debugging attribute 
     70     */ 
    4671    public int level = 0; 
    4772 
    48     /* size of the quadrant */ 
     73    /** 
     74     * size of the quadrant in x-dimension 
     75     */ 
    4976    private double[] x; 
     77 
     78    /** 
     79     * size of the quadrant in y-dimension 
     80     */ 
    5081    private double[] y; 
    5182 
     83    /** 
     84     * debugging parameter 
     85     */ 
    5286    public static boolean verbose = false; 
     87 
     88    /** 
     89     * global size of the QuadTree. 
     90     */ 
    5391    public static int size = 0; 
     92 
     93    /** 
     94     * recursion parameter alpha 
     95     */ 
    5496    public static double alpha = 0; 
    5597 
    56     /* cluster payloads */ 
     98    /** 
     99     * data for each cluster 
     100     */ 
    57101    public static ArrayList<ArrayList<QuadTreePayload<Instance>>> ccluster = 
    58102        new ArrayList<ArrayList<QuadTreePayload<Instance>>>(); 
    59103 
    60     /* cluster sizes (index is cluster number, arraylist is list of boxes (x0,y0,x1,y1) */ 
     104    /** 
     105     * cluster sizes (index is cluster number, {@link ArrayList} is list of boxes (x0,y0,x1,y1 
     106     */ 
    61107    public static HashMap<Integer, ArrayList<Double[][]>> csize = 
    62108        new HashMap<Integer, ArrayList<Double[][]>>(); 
    63109 
    64     /* payload of this instance */ 
     110    /** 
     111     * data within this quadrant 
     112     */ 
    65113    private ArrayList<QuadTreePayload<Instance>> payload; 
    66114 
     115    /** 
     116     * <p> 
     117     * Constructor. Creates a new QuadTree. 
     118     * </p> 
     119     * 
     120     * @param parent 
     121     *            parent of this tree 
     122     * @param payload 
     123     *            data within the quadrant 
     124     */ 
    67125    public QuadTree(QuadTree parent, ArrayList<QuadTreePayload<Instance>> payload) { 
    68126        this.parent = parent; 
    … …  
    70128    } 
    71129 
     130    /* 
     131     * (non-Javadoc) 
     132     *  
     133     * @see java.lang.Object#toString() 
     134     */ 
     135    @Override 
    72136    public String toString() { 
    73137        String n = ""; 
    … …  
    81145 
    82146    /** 
     147     * <p> 
    83148     * Returns the payload, used for clustering in the clustering list we only have children with 
    84      * paylod 
    85      *  
    86      * @return payload 
     149     * payload 
     150     * </p> 
     151     *  
     152     * @return payload the payload 
    87153     */ 
    88154    public ArrayList<QuadTreePayload<Instance>> getPayload() { 
    … …  
    91157 
    92158    /** 
    93      * Calculate the density of this quadrant 
    94      *  
    95      * density = number of instances / global size (all instances) 
    96      *  
    97      * @return density 
     159     * <p> 
     160     * Calculate the density of this quadrant as 
     161     * <ul> 
     162     * <li>density = number of instances / global size (all instances)</li> 
     163     * </ul> 
     164     *  
     165     * @return density the density 
    98166     */ 
    99167    public double getDensity() { 
    … …  
    103171    } 
    104172 
     173    /** 
     174     * <p> 
     175     * sets the size coordinates of the quadrant 
     176     * </p> 
     177     * 
     178     * @param x 
     179     *            x-dimension 
     180     * @param y 
     181     *            y-dimension 
     182     */ 
    105183    public void setSize(double[] x, double[] y) { 
    106184        this.x = x; 
    … …  
    108186    } 
    109187 
     188    /** 
     189     * <p> 
     190     * returns the size of the quadrant 
     191     * </p> 
     192     * 
     193     * @return size of the current quadrant 
     194     */ 
    110195    public double[][] getSize() { 
    111196        return new double[][] 
    … …  
    113198    } 
    114199 
     200    /** 
     201     * <p> 
     202     * returns the size of the quadrant 
     203     * </p> 
     204     * 
     205     * @return size of the current quadrant 
     206     */ 
    115207    public Double[][] getSizeDouble() { 
    116208        Double[] tmpX = new Double[2]; 
    … …  
    128220 
    129221    /** 
    130      * TODO: DRY, median ist immer dasselbe 
     222     * <p> 
     223     * calculates the median for the x axis 
     224     * </p> 
    131225     *  
    132226     * @return median for x 
    … …  
    161255    } 
    162256 
     257    /** 
     258     * <p> 
     259     * calculates the median for the y axis 
     260     * </p> 
     261     *  
     262     * @return median for y 
     263     */ 
    163264    private double getMedianForY() { 
    164265        double med_y = 0; 
    … …  
    191292 
    192293    /** 
    193      * Reurns the number of instances in the payload 
    194      *  
    195      * @return int number of instances 
     294     * <p> 
     295     * Returns the number of instances in the payload 
     296     * </p> 
     297     *  
     298     * @return number of instances 
    196299     */ 
    197300    public int getNumbers() { 
    … …  
    204307 
    205308    /** 
     309     * <p> 
    206310     * Calculate median values of payload for x, y and split into 4 sectors 
     311     * </p> 
    207312     *  
    208313     * @return Array of QuadTree nodes (4 childs) 
    … …  
    295400 
    296401    /** 
    297      * TODO: static method 
    298      *  
     402     * <p> 
     403     * creates the children of a QuadTree and recursively splits them as well 
     404     * </p> 
     405     * 
    299406     * @param q 
    300      */ 
    301     public void recursiveSplit(QuadTree q) { 
     407     *            tree that is split 
     408     */ 
     409    public static void recursiveSplit(QuadTree q) { 
    302410        if (QuadTree.verbose) { 
    303411            System.out.println("splitting: " + q); 
    … …  
    310418            try { 
    311419                QuadTree[] childs = q.split(); 
    312                 this.recursiveSplit(childs[0]); 
    313                 this.recursiveSplit(childs[1]); 
    314                 this.recursiveSplit(childs[2]); 
    315                 this.recursiveSplit(childs[3]); 
     420                recursiveSplit(childs[0]); 
     421                recursiveSplit(childs[1]); 
     422                recursiveSplit(childs[2]); 
     423                recursiveSplit(childs[3]); 
    316424            } 
    317425            catch (Exception e) { 
    … …  
    322430 
    323431    /** 
    324      * returns an list of childs sorted by density 
     432     * <p> 
     433     * returns an list of children sorted by density 
     434     * </p> 
    325435     *  
    326436     * @param q 
    327437     *            QuadTree 
    328      * @return list of QuadTrees 
    329438     */ 
    330439    private void generateList(QuadTree q) { 
    … …  
    350459 
    351460    /** 
     461     * <p> 
    352462     * Checks if passed QuadTree is neighboring to us 
     463     * </p> 
    353464     *  
    354465     * @param q 
    … …  
    396507 
    397508    /** 
     509     * <p> 
    398510     * Perform pruning and clustering of the quadtree 
    399      *  
     511     * </p> 
     512     * <p> 
    400513     * Pruning according to: Tim Menzies, Andrew Butcher, David Cok, Andrian Marcus, Lucas Layman, 
    401514     * Forrest Shull, Burak Turhan, Thomas Zimmermann, 
    402515     * "Local versus Global Lessons for Defect Prediction and Effort Estimation," IEEE Transactions 
    403516     * on Software Engineering, vol. 39, no. 6, pp. 822-834, June, 2013 
    404      *  
    405      * 1) get list of leaf quadrants 2) sort by their density 3) set stop_rule to 0.5 * highest 
    406      * Density in the list 4) merge all nodes with a density > stop_rule to the new cluster and 
    407      * remove all from list 5) repeat 
     517     * </p> 
     518     * <ol> 
     519     * <li>get list of leaf quadrants</li> 
     520     * <li>sort by their density</li> 
     521     * <li>set stop_rule to 0.5*highest Density in the list</li> 
     522     * <li>merge all nodes with a density > stop_rule to the new cluster and remove all from list 
     523     * </li> 
     524     * <li>repeat</li> 
     525     * </ol> 
    408526     *  
    409527     * @param q 
    … …  
    479597    } 
    480598 
     599    /** 
     600     * <p> 
     601     * debugging function that prints information about the QuadTree 
     602     * </p> 
     603     * 
     604     */ 
    481605    public void printInfo() { 
    482606        System.out.println("we have " + ccluster.size() + " clusters"); 
    … …  
    488612 
    489613    /** 
     614     * <p> 
    490615     * Helper Method to get a sorted list (by density) for all children 
     616     * </p> 
    491617     *  
    492618     * @param q 
Note: See TracChangeset for help on using the changeset viewer.