SHARE
TWEET

Untitled

a guest Jan 24th, 2020 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package assignentthree;
  2. import java.util.*;
  3. public class KDTree implements Iterable<Datum>{
  4.  
  5.     KDNode      rootNode;
  6.     int         k;
  7.     int         numLeaves;
  8.    
  9.     // constructor
  10.  
  11.     public KDTree(ArrayList<Datum> datalist) throws Exception {
  12.  
  13.         Datum[]  dataListArray  = new Datum[ datalist.size() ];
  14.  
  15.         if (datalist.size() == 0) {
  16.             throw new Exception("Trying to create a KD tree with no data");
  17.         }
  18.         else
  19.             this.k = datalist.get(0).x.length;
  20.  
  21.         int ct=0;
  22.         for (Datum d :  datalist) {
  23.             dataListArray[ct] = datalist.get(ct);
  24.             ct++;
  25.         }
  26.        
  27.     //   Construct a KDNode that is the root node of the KDTree.
  28.  
  29.         rootNode = new KDNode(dataListArray);
  30.     }
  31.    
  32.     //   KDTree methods
  33.    
  34.     public Datum nearestPoint(Datum queryPoint) {
  35.         return rootNode.nearestPointInNode(queryPoint);
  36.     }
  37.    
  38.  
  39.     public int height() {
  40.         return this.rootNode.height(); 
  41.     }
  42.  
  43.     public int countNodes() {
  44.         return this.rootNode.countNodes(); 
  45.     }
  46.    
  47.     public int size() {
  48.         return this.numLeaves; 
  49.     }
  50.  
  51.     //-------------------  helper methods for KDTree   ------------------------------
  52.  
  53.     public static long distSquared(Datum d1, Datum d2) {
  54.  
  55.         long result = 0;
  56.         for (int dim = 0; dim < d1.x.length; dim++) {
  57.             result +=  (d1.x[dim] - d2.x[dim])*((long) (d1.x[dim] - d2.x[dim]));
  58.         }
  59.         // if the Datum coordinate values are large then we can easily exceed the limit of 'int'.
  60.         return result;
  61.     }
  62.  
  63.     public double meanDepth(){
  64.         int[] sumdepths_numLeaves =  this.rootNode.sumDepths_numLeaves();
  65.         return 1.0 * sumdepths_numLeaves[0] / sumdepths_numLeaves[1];
  66.     }
  67.    
  68.     class KDNode {
  69.  
  70.         boolean leaf;
  71.         Datum leafDatum;           //  only stores Datum if this is a leaf
  72.        
  73.         //  the next two variables are only defined if node is not a leaf
  74.  
  75.         int splitDim;      // the dimension we will split on
  76.         int splitValue;    // datum is in low if value in splitDim <= splitValue, and high if value in splitDim > splitValue  
  77.  
  78.         KDNode lowChild, highChild;   //  the low and high child of a particular node (null if leaf)
  79.           //  You may think of them as "left" and "right" instead of "low" and "high", respectively
  80.                
  81.                 HashSet test=new HashSet();
  82.  
  83.         KDNode(Datum[] datalist) throws Exception
  84.                 {
  85.                     ArrayList <Datum> highTemp=new ArrayList <> (0), lowTemp=new ArrayList <> (0);
  86.                    
  87.                     if (datalist.length==1)
  88.                     {
  89.                         if (test.add(datalist[0]))
  90.                         {
  91.                             this.leaf=true;
  92.                             this.leafDatum=datalist[0];
  93.                         }
  94.                         else
  95.                         {
  96.                             this.leaf=false;
  97.                         }
  98.                     }
  99.                    
  100.                     else if (datalist.length>1)
  101.                     {
  102.                         this.leaf=false;
  103.                         this.splitDim=getRangePos(datalist);
  104.                        
  105.                         int highCheck=datalist[splitDim].x[0];
  106.                         int lowCheck=datalist[splitDim].x[0];
  107.                                
  108.                         for (int z=1; z<datalist[splitDim].x.length; z++)
  109.                         {
  110.                             if (datalist[splitDim].x[z]>highCheck)
  111.                             {
  112.                                 highCheck=datalist[splitDim].x[z];
  113.                             }
  114.                            
  115.                             if (datalist[splitDim].x[z]<lowCheck)
  116.                             {
  117.                                 lowCheck=datalist[splitDim].x[z];
  118.                             }
  119.                         }
  120.                        
  121.                         splitValue=(highCheck+lowCheck)/2;
  122.                        
  123.                         for (int y=0; y<datalist.length-1; y++)
  124.                         {
  125.                             if (datalist[y]!=null)
  126.                             {
  127.                                 if (datalist[y].x[splitDim]<=splitValue)
  128.                                 {
  129.                                     highTemp.ensureCapacity(highTemp.size()+1);
  130.                                     highTemp.add(datalist[y]);
  131.                                 }
  132.                                 else
  133.                                 {
  134.                                     lowTemp.ensureCapacity(lowTemp.size()+1);
  135.                                     lowTemp.add(datalist[y]);
  136.                                 }
  137.                             }
  138.                         }
  139.                        
  140.                         Datum [] high=highTemp.toArray(new Datum [highTemp.size()]);
  141.                         Datum [] low=lowTemp.toArray(new Datum [lowTemp.size()]);
  142.                        
  143.                         if(high.length>=1)
  144.                         {
  145.                             this.highChild=new KDNode(high);
  146.                         }
  147.                        
  148.                         if(low.length>=1)
  149.                         {
  150.                             this.lowChild=new KDNode(low);
  151.                         }
  152.                     }
  153.         }
  154.                
  155.                 public int getRangePos(Datum [] datalist)
  156.                 {
  157.                     int range=0, rangePos=0, highCheck=0, lowCheck=0;
  158.                    
  159.                     if (datalist.length<=0)
  160.                     {
  161.                         throw new NullPointerException("The list is empty.");
  162.                     }
  163.                    
  164.                     for (int y=0; y<datalist.length; y++)
  165.                     {
  166.                         if (datalist[y]!=null)
  167.                         {
  168.                             for (int z=0; z<datalist[y].x.length; z++)
  169.                             {
  170.                                 if (datalist[y].x[z]>highCheck-lowCheck)
  171.                                 {
  172.                                     highCheck=datalist[y].x[z];
  173.                                 }
  174.                                 else
  175.                                 {
  176.                                     lowCheck=datalist[y].x[z];
  177.                                 }
  178.                             }
  179.  
  180.                             if (highCheck-lowCheck>range)
  181.                             {
  182.                                 range=highCheck-lowCheck;
  183.                                 rangePos=y;
  184.                             }
  185.                         }
  186.                         else
  187.                         {
  188.                             break;
  189.                         }
  190.                     }
  191.                     return rangePos;
  192.                 }
  193.  
  194.         public Datum nearestPointInNode(Datum queryPoint)
  195.                 {
  196.                         KDTreeIterator iterator=new KDTreeIterator(this);
  197.                         int i = 0, j = iterator.list.size()-1, mid = 0;
  198.        
  199.                         if (KDTree.distSquared(iterator.pos(0), queryPoint)<=0)
  200.                         {
  201.                             return iterator.pos(0);
  202.                         }
  203.                        
  204.                         if (KDTree.distSquared(iterator.pos(0), queryPoint)>=0)
  205.                         {
  206.                             return iterator.pos(iterator.list.size()-1);
  207.                         }
  208.                                
  209.                         while (i < j)
  210.                         {
  211.                             mid = (i + j) / 2;
  212.  
  213.                             if (KDTree.distSquared(iterator.pos(mid), queryPoint)==0)
  214.                             {
  215.                                 return iterator.pos(mid);
  216.                             }
  217.  
  218.                                     /* If target is less than array element,
  219.                                        then search in left */
  220.                             if (KDTree.distSquared(iterator.pos(mid), queryPoint)<0)
  221.                             {
  222.  
  223.                                         // If target is greater than previous
  224.                                         // to mid, return closest of two
  225.                                 if (mid>0 && KDTree.distSquared(iterator.pos(mid-1), queryPoint)>0)  
  226.                                 {
  227.                                     if (KDTree.distSquared(queryPoint, iterator.pos(mid-1)) >= KDTree.distSquared(iterator.pos(mid), queryPoint))  
  228.                                         return iterator.pos(mid);        
  229.                                     else
  230.                                         return iterator.pos(mid-1);
  231.                                 }
  232.                                         /* Repeat for left half */
  233.                                 j = mid;              
  234.                             }
  235.  
  236.                                     // If target is greater than mid
  237.                             else
  238.                             {
  239.                                 if (mid < iterator.list.size()-1 && (KDTree.distSquared(iterator.pos(mid+1), queryPoint)>0))
  240.                                 {
  241.                                     if (KDTree.distSquared(queryPoint, iterator.pos(mid-1)) >= KDTree.distSquared(iterator.pos(mid), queryPoint))
  242.                                         return iterator.pos(mid+1);        
  243.                                     else
  244.                                         return iterator.pos(mid);
  245.                                 }
  246.                                 i = mid + 1;
  247.                             }
  248.                         }
  249.                         // Only single element left after search
  250.                         return iterator.pos(mid);
  251.                 }
  252.        
  253.         // -----------------  KDNode helper methods (might be useful for debugging) -------------------
  254.  
  255.         public int height() {
  256.                     if (this==null)
  257.                         {
  258.                             throw new NullPointerException();
  259.                         }
  260.             if (this.leaf)
  261.                 return 0;
  262.             else
  263.                             if (this.lowChild!=null && this.highChild!=null)
  264.                             {
  265.                                 return 1 + Math.max( this.lowChild.height(), this.highChild.height());
  266.                             }
  267.                             else if (this.lowChild!=null)
  268.                             {
  269.                                 return 1 + this.lowChild.height();
  270.                             }
  271.                             else if (this.highChild!=null)
  272.                             {
  273.                                 return 1 + this.highChild.height();
  274.                             }
  275.                             else
  276.                             {
  277.                                 return 0;
  278.                             }
  279.         }
  280.                
  281.                 /*if (this.leaf)    
  282.                 return 0;
  283.             else {
  284.                 return 1 + Math.max( this.lowChild.height(), this.highChild.height());
  285.             }*/
  286.  
  287.         public int countNodes() {
  288.                         if (this==null)
  289.                         {
  290.                             throw new NullPointerException();
  291.                         }
  292.             if (this.leaf)
  293.                 return 1;
  294.             else
  295.                             if (this.lowChild!=null && this.highChild!=null)
  296.                             {
  297.                                 return 1 + this.lowChild.countNodes() + this.highChild.countNodes();
  298.                             }
  299.                             else if (this.lowChild!=null)
  300.                             {
  301.                                 return 1 + this.lowChild.countNodes();
  302.                             }
  303.                             else if (this.highChild!=null)
  304.                             {
  305.                                 return 1 + this.highChild.countNodes();
  306.                             }
  307.                             else
  308.                             {
  309.                                 return 0;
  310.                             }
  311.         }
  312.        
  313.         /*  
  314.          * Returns a 2D array of ints.  The first element is the sum of the depths of leaves
  315.          * of the subtree rooted at this KDNode.   The second element is the number of leaves
  316.          * this subtree.    Hence,  I call the variables  sumDepth_size_*  where sumDepth refers
  317.          * to element 0 and size refers to element 1.
  318.          */
  319.                
  320.         public int[] sumDepths_numLeaves(){
  321.             int[] sumDepths_numLeaves_low, sumDepths_numLeaves_high;
  322.             int[] return_sumDepths_numLeaves = new int[2];
  323.            
  324.             /*    
  325.              *  The sum of the depths of the leaves is the sum of the depth of the leaves of the subtrees,
  326.              *  plus the number of leaves (size) since each leaf defines a path and the depth of each leaf
  327.              *  is one greater than the depth of each leaf in the subtree.
  328.              */
  329.            
  330.             if (this.leaf) {  // base case
  331.                 return_sumDepths_numLeaves[0] = 0;
  332.                 return_sumDepths_numLeaves[1] = 1;
  333.             }
  334.             else {
  335.                 sumDepths_numLeaves_low  = this.lowChild.sumDepths_numLeaves();
  336.                 sumDepths_numLeaves_high = this.highChild.sumDepths_numLeaves();
  337.                 return_sumDepths_numLeaves[0] = sumDepths_numLeaves_low[0] + sumDepths_numLeaves_high[0] + sumDepths_numLeaves_low[1] + sumDepths_numLeaves_high[1];
  338.                 return_sumDepths_numLeaves[1] = sumDepths_numLeaves_low[1] + sumDepths_numLeaves_high[1];
  339.             }  
  340.             return return_sumDepths_numLeaves;
  341.         }
  342.        
  343.         }
  344.        
  345.         @Override
  346.     public Iterator<Datum> iterator(){
  347.         return new KDTreeIterator(this.rootNode);
  348.     }
  349.    
  350.     private class KDTreeIterator implements Iterator<Datum>
  351.         {
  352.            
  353.             ArrayList<Datum> list=new ArrayList();
  354.             int x;
  355.        
  356.             KDTreeIterator(KDNode curr)
  357.             {
  358.                 while (!curr.leaf)
  359.                 {
  360.                     new KDTreeIterator(curr.lowChild);
  361.                     new KDTreeIterator(curr.highChild);
  362.                    
  363.                     if (curr.leaf)
  364.                     {
  365.                         list.add(curr.leafDatum);
  366.                         break;
  367.                     }
  368.                 }
  369.                 x=0;
  370.             }
  371.  
  372.             @Override
  373.             public boolean hasNext()
  374.             {
  375.                 return !(list.get(x+1)==null);
  376.             }
  377.  
  378.             @Override
  379.             public Datum next()
  380.             {
  381.                 if (hasNext())
  382.                 {
  383.                     x++;
  384.                     return list.get(x+1);
  385.                 }
  386.                 else
  387.                 {
  388.                     throw new NullPointerException();
  389.                 }
  390.             }
  391.  
  392.             public Datum pos(int x)
  393.             {
  394.                 return list.get(x);
  395.             }
  396.         }
  397. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top