<commit_before>//
//  KDTree+Equatable.swift
//  Pods
//
//  Created by <NAME> on 28/03/16.
//
//

import Foundation

private enum ReplacementDirection {
    case max
    case min
}

public enum KDTree<Element: KDTreePoint> {
    case leaf
    indirect case node(left: KDTree<Element>, value: Element, dimension: Int, right: KDTree<Element>)
}

extension KDTree {
    public init(values: [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 {
            var median = values.count / 2
            
            let selected = KDTree.quickSelect(n: median, arr: 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 && 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 {
            var median = values.startIndex + (values.endIndex - values.startIndex) / 2
            
            let selected = KDTree.quickSelect(n: median, arr: 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 > selected.startIndex && abs(selected[median-1].kdDimension(currentSplittingDimension) - medianValue) < Double.ulpOfOne {
                median -= 1
            }
            
            let leftTree = KDTree(values: selected[selected.startIndex..<median], depth: depth+1)
            let rightTree = KDTree(values: selected[median+1..<selected.endIndex], depth: depth+1)
            
            self = .node(left: leftTree, value: selected[median],
                         dimension: currentSplittingDimension, right: rightTree)
        }
    }
    
    /*
     Lomuto's partitioning algorithm.
     This is conceptually simpler than Hoare's original scheme but less efficient.
     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.
     The left partition includes all values smaller than the pivot, so
     if the pivot value occurs more than once, its duplicates will be found in the
     right partition.
     */
    private static func partitionLomuto(_ a: inout ArraySlice<Element>, kdDimension: Int) -> Int {
        // We always use the highest item as the pivot.
        let pivot = a.last!
        
        // This loop partitions the array into four (possibly empty) regions:
        //   [a.startIndex  ...   i] contains all values < pivot,
        //   [i+1  ...          j-1] contains all values >= pivot,
        //   [j    ..< a.endIndex-1] are values we haven't looked at yet,
        //   [a.endIndex           ] is the pivot value.
        var i = a.startIndex
        
        for j in a.startIndex..<a.endIndex-1 {
            if a[j].kdDimension(kdDimension) < pivot.kdDimension(kdDimension) {
                (a[i], a[j]) = (a[j], a[i])
                i += 1
            }
        }
        
        // Swap the pivot element with the first element that is greater than
        // the pivot. Now the pivot sits between the < and >= regions and the
        // array is properly partitioned.
        (a[i], a[a.endIndex-1]) = (a[a.endIndex-1], a[i])
        return i
    }
    
    /*
     takes an array and an index n and returns an array with the nth value being the nth largest
     */
    private static func quickSelect(n: Int, arr: [Element], kdDimension: Int) -> [Element] {
        if arr.count == 1 {
            return [arr.first!]
        }
        
        var varr = arr
        let selector = partitionLomuto(&varr[0...arr.endIndex-1], kdDimension: kdDimension)
        
        if selector == n {
            return varr
        }
        else if n > selector {
            let s = selector+1
            return  Array(varr[...selector] + quickSelect(n: n, arr: varr[s...], kdDimension: kdDimension))
        }
        else {
            return  Array(quickSelect(n: n, arr: varr[..<selector], kdDimension: kdDimension) + varr[selector...])
        }
    }
    
    private static func quickSelect(n: Int, arr: ArraySlice<Element>, kdDimension: Int) -> ArraySlice<Element> {
        if arr.count == 1 {
            return [arr.first!]
        }
        
        var varr = arr
        let selector = partitionLomuto(&varr, kdDimension: kdDimension)
        
        if selector == n {
            return varr
        }
        else if n > selector {
            let s = selector+1
            return varr[..<s] + quickSelect(n: n, arr: varr[s...], kdDimension: kdDimension)
        }
        else {
            return quickSelect(n: n, arr: varr[..<selector], kdDimension: kdDimension) + varr[selector...]
        }
    }
    
    /// Returns `true` iff `self` is empty.
    ///
    /// - Complexity: O(1)
    public var isEmpty: Bool {
        switch self {
        case .leaf: return true
        default: return false
        }
    }
    
    /// The number of elements the KDTree stores.
    public var count: Int {
        switch self {
        case .leaf:
            return 0
        case let .node(left, _, _, right):
            return 1 + left.count + right.count<commit_msg>median of three added to Lomuto's<commit_after>//
//  KDTree+Equatable.swift
//  Pods
//
//  Created by <NAME> on 28/03/16.
//
//

import Foundation

private enum ReplacementDirection {
    case max
    case min
}

public enum KDTree<Element: KDTreePoint> {
    case leaf
    indirect case node(left: KDTree<Element>, value: Element, dimension: Int, right: KDTree<Element>)
}

extension KDTree {
    public init(values: [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 {
            var median = values.count / 2
            
            let selected = KDTree.quickSelect(targetIndex: median, array: values[0..<values.count], 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)
        }
    }
    
    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.partitionLomuto(&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...]
        }
    }
    
    /*
     Lomuto's partitioning algorithm.
     This is conceptually simpler than Hoare's original scheme but less efficient.
     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.
     The left partition includes all values smaller than the pivot, so
     if the pivot value occurs more than once, its duplicates will be found in the
     right partition.
     */
    private static func partitionLomuto(_ array: inout ArraySlice<Element>, kdDimension: Int) -> Int {
        let lo = array.startIndex
        let hi = array.endIndex-1
        guard lo < hi else { return 0 }
        let mid = (lo + hi) / 2
        if array[mid].kdDimension(kdDimension) < array[lo].kdDimension(kdDimension) { array.swapAt(lo, mid) }
        if array[hi].kdDimension(kdDimension) < array[lo].kdDimension(kdDimension) { array.swapAt(lo, hi) }
        if array[mid].kdDimension(kdDimension) < array[hi].kdDimension(kdDimension) { array.swapAt(mid, hi) }
        let pivot = array[hi]
        
        
        
        // This loop partitions the array into four (possibly empty) regions:
        //   [a.startIndex  ...   i] contains all values < pivot,
        //   [i+1  ...          j-1] contains all values >= pivot,
        //   [j    ..< a.endIndex-1] are values we haven't looked at yet,
        //   [a.endIndex           ] is the pivot value.
        var i = array.startIndex
        
        for j in array.startIndex..<hi {
            if array[j].kdDimension(kdDimension) < pivot.kdDimension(kdDimension) {
                array.swapAt(i, j)
                i += 1
            }
        }
        
        // Swap the pivot element with the first element that is greater than
        // the pivot. Now the pivot sits between the < and >= regions and the
        // array is properly partitioned.
        array.swapAt(i, hi)
        return i
    }
    
    /// Returns `true` iff `self` is empty.
    ///
    /// - Complexity: O(1)
    public var isEmpty: Bool {
        switch self {
        case .leaf: return true
        default: return false
        }
    }
    
    /// The number of elements the KDTree stores.
    public var count: Int {
        switch self {
        case .leaf:
            return 0
        case let .node(left, _, _, right):
            return 1 + left.count + right.count
{'fraction_non_alphanumeric': 0.09632390557626251, 'fraction_numerical': 0.006065921216107579, 'mean_word_length': 1.9472323928494508, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2839914', 'n_tokens_mistral': 3825, 'n_tokens_neox': 3736, 'n_words': 1132}