1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
|
/*
This source file is part of the Swift.org open source project
Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
Licensed under Apache License v2.0 with Runtime Library Exception
See http://swift.org/LICENSE.txt for license information
See http://swift.org/CONTRIBUTORS.txt for Swift project authors
*/
/// An array which is always in sorted state.
public struct SortedArray<Element>: CustomStringConvertible {
/// Storage for our elements.
fileprivate var elements: [Element]
/// A predicate that returns `true` if its first argument should be ordered
/// before its second argument; otherwise, `false`.
fileprivate let areInIncreasingOrder: (Element, Element) -> Bool
/// Create an empty sorted array with given comparison predicate.
public init(areInIncreasingOrder: @escaping (Element, Element) -> Bool) {
self.elements = []
self.areInIncreasingOrder = areInIncreasingOrder
}
/// Create a sorted array with the given sequence and comparison predicate.
public init<S: Sequence>(
_ newElements: S,
areInIncreasingOrder: @escaping (Element, Element) -> Bool)
where S.Iterator.Element == Element
{
self.elements = newElements.sorted(by: areInIncreasingOrder)
self.areInIncreasingOrder = areInIncreasingOrder
}
/// Insert the given element, maintaining the sort order.
public mutating func insert(_ newElement: Element) {
let index = self.index(for: newElement)
elements.insert(newElement, at: index)
}
/// Returns the index to insert the element in the sorted array using binary search.
private func index(for element: Element) -> Index {
if self.isEmpty {
return 0
}
var (low, high) = (0, self.endIndex - 1)
var mid = 0
while low < high {
mid = (low + high)/2
if areInIncreasingOrder(self[mid], element) {
low = mid + 1
} else {
high = mid
}
}
// At this point, low == high, low will never be greater than high, as low is incremented by just one or high is adjusted to mid.
if areInIncreasingOrder(element, self[low]) {
return low
}
return high + 1
}
/// Insert the given sequence, maintaining the sort order.
public mutating func insert<S: Sequence>(contentsOf newElements: S) where S.Iterator.Element == Element {
let newElements = newElements.sorted(by: areInIncreasingOrder)
guard !newElements.isEmpty else {
return
}
guard !elements.isEmpty else {
elements = newElements
return
}
var lhsIndex = elements.endIndex - 1
var rhsIndex = newElements.endIndex - 1
elements.reserveCapacity(elements.count + newElements.count)
// NOTE: If SortedArray moves to stdlib an _ArrayBuffer can be used
// instead. This append can then be removed as _ArrayBuffer can be
// resized without requiring instantiated elements.
elements.append(contentsOf: newElements)
var lhs = elements[lhsIndex], rhs = newElements[rhsIndex]
// Equivalent to a merge sort, "pop" and append the max elemeent of
// each array until either array is empty.
for index in elements.indices.reversed() {
if areInIncreasingOrder(lhs, rhs) {
elements[index] = rhs
rhsIndex -= 1
guard rhsIndex >= newElements.startIndex else { break }
rhs = newElements[rhsIndex]
} else {
elements[index] = lhs
lhsIndex -= 1
guard lhsIndex >= elements.startIndex else { break }
lhs = elements[lhsIndex]
}
}
// Any remaining new elements were smaller than all old elements
// so the remaining new elements can safely replace the prefix.
if rhsIndex >= newElements.startIndex {
elements.replaceSubrange(
newElements.startIndex ... rhsIndex,
with: newElements[newElements.startIndex ... rhsIndex])
}
}
/// Returns the values as an array.
public var values: [Element] {
return elements
}
public var description: String {
return "<SortedArray: \(elements)>"
}
}
extension SortedArray: RandomAccessCollection {
public typealias Index = Int
public var startIndex: Index {
return elements.startIndex
}
public var endIndex: Index {
return elements.endIndex
}
public func index(after i: Index) -> Index {
return elements.index(after: i)
}
public func index(before i: Index) -> Index {
return elements.index(before: i)
}
public subscript(position: Index) -> Element {
return elements[position]
}
}
extension SortedArray {
public static func +=<S: Sequence>(lhs: inout SortedArray, rhs: S) where S.Iterator.Element == Element {
lhs.insert(contentsOf: rhs)
}
}
extension SortedArray where Element: Comparable {
/// Create an empty sorted array with < as the comparison predicate.
public init() {
self.init(areInIncreasingOrder: <)
}
}
|