     /// right partition.
     ///
     /// - Parameters:
-    ///   - array: the inout array slice
+    ///   - values: the pointer to the values
     ///   - kdDimension: the dimension sorted over
-    /// - Returns: the index of the pivot element in the new array
-    private static func partitionHoare(_ array: inout ArraySlice<Element>, kdDimension: Int) -> Int {
-        let lo = array.startIndex
-        let hi = array.endIndex-1
+    /// - Returns: the index of the pivot element in the pointer
+    private static func partitionHoare(_ values: UnsafeMutablePointer<Element>, startIndex lo: Int, endIndex: Int, kdDimension: Int) -> Int {
+        let hi = endIndex - 1
         guard lo < hi else { return lo }
         
         let randomIndex = Int.random(in: lo...hi)
-        array.swapAt(hi, randomIndex)
-        let pivot = array[hi]
+        values.swapAt(hi, randomIndex)
+        
+        let kdDimensionOfPivot = values[hi].kdDimension(kdDimension)
         
         // This loop partitions the array into four (possibly empty) regions:
         //   [lo   ...    i] contains all values < pivot,

            return
        }
        
        let currentSplittingDimension = depth % Element.dimensions
        if values.count == 1, let firstValue = values.first {
            self = .node(left: .leaf, value: firstValue, dimension: currentSplittingDimension, right: .leaf)
        }
        else {
            var median = values.count / 2
            
            let selected = KDTree.quickSelect(targetIndex: median, array: values[0..<values.endIndex], kdDimension: currentSplittingDimension)
            let medianElement = selected[median]
            let medianValue = medianElement.kdDimension(currentSplittingDimension)
          
            //Ensure left subtree contains currentSplittingDimension-coordinate strictly less than its parent node
            //Needed for 'contains' and 'removing' method.
            while median >= 1 && abs(selected[median-1].kdDimension(currentSplittingDimension) - medianValue) < Double.ulpOfOne {
              median -= 1
            }
          
            let leftTree = KDTree(values: selected[0..<median], depth: depth+1)
            let rightTree = KDTree(values: selected[median+1..<selected.count], depth: depth+1)
            
            self = .node(left: leftTree, value: selected[median],
                         dimension: currentSplittingDimension, right: rightTree)
        }
    }
    
    public init(values: ArraySlice<Element>, depth: Int = 0) {
        guard !values.isEmpty else {
            self = .leaf
            return
        }
        
        let currentSplittingDimension = depth % Element.dimensions
        if values.count == 1, let firstValue = values.first {
            self = .node(left: .leaf, value: firstValue, dimension: currentSplittingDimension, right: .leaf)
        }
        else {
            let sliceStartIndex = values.startIndex
            let sliceEndIndex = values.endIndex
            var median = sliceStartIndex + (sliceEndIndex - sliceStartIndex) / 2
            
            let selected = KDTree.quickSelect(targetIndex: median, array: values, kdDimension: currentSplittingDimension)
            let medianElement = selected[median]
            let medianValue = medianElement.kdDimension(currentSplittingDimension)
            
            //Ensure left subtree contains currentSplittingDimension-coordinate strictly less than its parent node
            //Needed for 'contains' and 'removing' method.
            while median >= 1 && median > sliceStartIndex && abs(selected[median-1].kdDimension(currentSplittingDimension) - medianValue) < Double.ulpOfOne {
                median -= 1
            }
            
            let leftTree = KDTree(values: selected[sliceStartIndex..<median], depth: depth+1)
            let rightTree = KDTree(values: selected[median+1..<sliceEndIndex], depth: depth+1)
            
            self = .node(left: leftTree, value: selected[median],
                         dimension: currentSplittingDimension, right: rightTree)
        }
    }
    
    /** Quickselect function is based on https://github.com/mourner/kdbush
     */
    private static func quickSelect(targetIndex: Int, array: ArraySlice<Element>, kdDimension: Int) -> ArraySlice<Element> {
        guard array.count > 1 else { return array }
        
        var varray = array
        let partitionIndex = KDTree.partitionHoare(&varray, kdDimension: kdDimension)
        
        if partitionIndex == targetIndex {
            return varray
        } else if partitionIndex < targetIndex {
            let s = partitionIndex+1
            return varray[...partitionIndex] + quickSelect(targetIndex: targetIndex, array: varray[s...], kdDimension: kdDimension)
        } else {
            // partitionIndex is greater than the targetIndex, quickSelect moves to indexes smaller than partitionIndex
            return quickSelect(targetIndex: targetIndex, array: varray[..<partitionIndex], kdDimension: kdDimension) + varray[partitionIndex...]
        }
    }
    
    /// # Hoare's partitioning algorithm.
    /// This is more efficient that Lomuto's algorithm.
    /// The return value is the index of the pivot element in the new array. The left
    /// partition is [low...p-1]; the right partition is [p+1...high], where p is the
    /// return value.
    /// - - -

        var j = hi - 1
        
        while true {
            while values[i].kdDimension(kdDimension) < kdDimensionOfPivot {
                i += 1
            }
            while lo < j && values[j].kdDimension(kdDimension) >= kdDimensionOfPivot {
                j -= 1
            }
            guard i < j else {
                break
            }
            values.swapAt(i, j)
        }
        
        // Swap the pivot element with the first element that is >=
        // the pivot. Now the pivot sits between the < and >= regions and the
        // array is properly partitioned.
        values.swapAt(i, hi)
        return i
    }
    
