SHARE
TWEET

Untitled

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