A sorted array in swift

SortedArray.swift

//
//  SortedArray.swift
//
//  Created by Damiaan on 05-11-16.
//  Copyright © 2016 Damiaan. All rights reserved.
//

import Foundation

public struct SortedArray<Element>: RandomAccessCollection, Collection {
    var sorted: [Element]
    let sortDescriptor: (Element, Element) -> Bool
    
    init(from unsortedArray: [Element] = [Element](), sortDescriptor: @escaping (Element, Element) -> Bool) {
        sorted = unsortedArray.sorted(by: sortDescriptor)
        self.sortDescriptor = sortDescriptor
    }

    /// A normal (Array) representation of this sorted array.
    public var unsorted: [Element] { return sorted }
    
    /// A type that represents a position in the collection.
    ///
    /// Valid indices consist of the position of every element and a
    /// "past the end" position that's not valid for use as a subscript
    /// argument.
    ///
    /// - SeeAlso: endIndex
    public typealias Index = Array<Element>.Index
    
    /// A type that provides the collection's iteration interface and
    /// encapsulates its iteration state.
    ///
    /// By default, a collection conforms to the `Sequence` protocol by
    /// supplying a `IndexingIterator` as its associated `Iterator`
    /// type.
    public typealias Iterator = Array<Element>.Iterator
    
    /// The position of the first element in a nonempty array.
    ///
    /// For an instance of `Array`, `startIndex` is always zero. If the array
    /// is empty, `startIndex` is equal to `endIndex`.
    public var startIndex: Int { return sorted.startIndex }
    
    /// The array's "past the end" position---that is, the position one greater
    /// than the last valid subscript argument.
    ///
    /// When you need a range that includes the last element of an array, use the
    /// half-open range operator (`..<`) with `endIndex`. The `..<` operator
    /// creates a range that doesn't include the upper bound, so it's always
    /// safe to use with `endIndex`. For example:
    ///
    ///     let numbers = [10, 20, 30, 40, 50]
    ///     if let i = numbers.index(of: 30) {
    ///         print(numbers[i ..< numbers.endIndex])
    ///     }
    ///     // Prints "[30, 40, 50]"
    ///
    /// If the array is empty, `endIndex` is equal to `startIndex`.
    public var endIndex: Int { return sorted.endIndex }
    
    /// Accesses the element at the specified position.
    ///
    /// For example, you can replace an element of an array by using its
    /// subscript.
    ///
    ///     var streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
    ///     streets[1] = "Butler"
    ///     print(streets[1])
    ///     // Prints "Butler"
    ///
    /// You can subscript a collection with any valid index other than the
    /// collection's end index. The end index refers to the position one
    /// past the last element of a collection, so it doesn't correspond with an
    /// element.
    ///
    /// - Parameter position: The position of the element to access. `position`
    ///   must be a valid index of the collection that is not equal to the
    ///   `endIndex` property.
    public subscript(position: Index) -> Element {
        get {
            return sorted[position]
        }
    }
    
    /// Accesses a contiguous subrange of the collection's elements.
    ///
    /// The accessed slice uses the same indices for the same elements as the
    /// original collection. Always use the slice's `startIndex` property
    /// instead of assuming that its indices start at a particular value.
    ///
    /// This example demonstrates getting a slice of an array of strings, finding
    /// the index of one of the strings in the slice, and then using that index
    /// in the original array.
    ///
    ///     let streets = ["Adams", "Bryant", "Channing", "Douglas", "Evarts"]
    ///     let streetsSlice = streets[2 ..< streets.endIndex]
    ///     print(streetsSlice)
    ///     // Prints "["Channing", "Douglas", "Evarts"]"
    ///
    ///     let index = streetsSlice.index(of: "Evarts")    // 4
    ///     streets[index!] = "Eustace"
    ///     print(streets[index!])
    ///     // Prints "Eustace"
    ///
    /// - Parameter bounds: A range of the collection's indices. The bounds of
    ///   the range must be valid indices of the collection.
    public subscript(bounds: Range<Index>) -> SubSequence {
        get {
            return sorted[bounds]
        }
    }
    
    /// A type that can represent the indices that are valid for subscripting the
    /// collection, in ascending order.
    public typealias Indices = Array<Element>.Indices
    
    /// A collection that represents a contiguous subrange of the collection's
    /// elements.
    public typealias SubSequence = Array<Element>.SubSequence
    
    /// Returns an iterator over the elements of the collection.
    public func makeIterator() -> IndexingIterator<Array<Element>> {
        return sorted.makeIterator()
    }
    
    /// Returns such index N that the sort descriptor is true for all elements up to
    /// but not including the index N, and is false for all elements
    /// starting with index N.
    /// Behavior is undefined if there is no such N.
    public func indexOf(_ element: Element) -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = index(low, offsetBy: distance(from: low, to: high)/2)
            if sortDescriptor(self[mid], element) {
                low = index(after: mid)
            } else {
                high = mid
            }
        }
        return low
    }
    
    /// Inserts a new element.
    ///
    /// The new element is inserted at an index i so that the sort descriptor returns true
    /// for as much as possible pairs of consecutive elements of the array.
    ///
    ///     var numbers = [1, 2, 3, 4, 5]
    ///     numbers.insert(-10)
    ///     numbers.insert(10)
    ///
    ///     print(numbers)
    ///     // Prints "[-10, 1, 2, 3, 4, 5, 10]"
    ///
    /// - Parameter newElement: The new element to insert into the sorted array.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the array.
    public mutating func insert(_ newElement: Element) {
        sorted.insert(newElement, at: indexOf(newElement))
    }
    
    /// Removes and returns the element at the specified position.
    ///
    /// All the elements following the specified position are moved up to
    /// close the gap.
    ///
    ///     var measurements: [Double] = [1.1, 1.5, 2.9, 1.2, 1.5, 1.3, 1.2]
    ///     let removed = measurements.remove(at: 2)
    ///     print(measurements)
    ///     // Prints "[1.1, 1.5, 1.2, 1.5, 1.3, 1.2]"
    ///
    /// - Parameter index: The position of the element to remove. `index` must
    ///   be a valid index of the array.
    /// - Returns: The element at the specified index.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the array.
    public mutating func remove(at index: Int) -> Element {
        return sorted.remove(at: index)
    }
    
    /// The total number of elements that the array can contain using its current
    /// storage.
    ///
    /// If the array grows larger than its capacity, it discards its current
    /// storage and allocates a larger one.
    ///
    /// The following example creates an array of integers from an array literal,
    /// then appends the elements of another collection. Before appending, the
    /// array allocates new storage that is large enough store the resulting
    /// elements.
    ///
    ///     var numbers = [10, 20, 30, 40, 50]
    ///     print("Count: \(numbers.count), capacity: \(numbers.capacity)")
    ///     // Prints "Count: 5, capacity: 5"
    ///
    ///     numbers.append(contentsOf: stride(from: 60, through: 100, by: 10))
    ///     print("Count: \(numbers.count), capacity: \(numbers.capacity)")
    ///     // Prints "Count: 10, capacity: 12"
    public var capacity: Int { return sorted.capacity }

    /// Reserves enough space to store the specified number of elements.
    ///
    /// If you are adding a known number of elements to an array, use this method
    /// to avoid multiple reallocations. This method ensures that the array has
    /// unique, mutable, contiguous storage, with space allocated for at least
    /// the requested number of elements.
    ///
    /// For performance reasons, the newly allocated storage may be larger than
    /// the requested capacity. Use the array's `capacity` property to determine
    /// the size of the new storage.
    ///
    /// - Parameter minimumCapacity: The requested number of elements to store.
    ///
    /// - Complexity: O(*n*), where *n* is the count of the array.
    public mutating func reserveCapacity(_ minimumCapacity: Int) {
        sorted.reserveCapacity(minimumCapacity)
    }

}

extension SortedArray where Element: Comparable {
    public init(from unsortedArray: [Element] = [Element]()) {
        self.init(from: unsortedArray, sortDescriptor: {$0<$1})
    }
}