Skip to content

Instantly share code, notes, and snippets.

@CTMacUser

CTMacUser/LeftOpenRange.swift

Last active April 16, 2018 02:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save CTMacUser/7413630eb723a8cc13b72861ac7f8e44 to your computer and use it in GitHub Desktop.
Save CTMacUser/7413630eb723a8cc13b72861ac7f8e44 to your computer and use it in GitHub Desktop.
Download ZIP
Linked-List Protocol and Singly-Linked List Type in Swift
Raw
LeftOpenRange.swift
//
// LeftOpenRange.swift
// NodeCollections
//
// Created by Daryle Walker on 4/6/18.
// Copyright © 2018 Daryle Walker. All rights reserved.
//
// MARK: Primary Definitions
/**
A half-open interval over a comparable type, from an unincluded lower bound up to an included upper bound.
A `LeftOpenRange` interval can be created with the left-open range operator (`>**`).
let positiveUpToFive = 0.0 >** 5.0
A `LeftOpenRange` instance can be used to quickly check if a value is contained in a particular range of values. For example:
print(positiveUpToFive.contains(3.14)) // Prints "true"
print(positiveUpToFive.contains(6.28)) // Prints "false"
print(positiveUpToFive.contains(5.0)) // Prints "true"
`LeftOpenRange` instances can represent an empty interval, like `Range`.
let empty = 0.0 >** 0.0
print(empty.contains(0.0)) // Prints "false"
print(empty.isEmpty) // Prints "true"
Like `Range` and `ClosedRange`, a `LeftOpenRange` instance can be used as a collection itself when the bound type has an integer stride.
func printStartIndex<C: Collection>(of collection: C) {
print(String(describing: collection.startIndex))
}
printStartIndex(of: 5 >** 10) // Prints "6"
*/
public struct LeftOpenRange<Bound: Comparable>: Equatable {
/**
The range's lower bound.
A range is empty if `lowerBound` is equal to `upperBound`.
*/
public let lowerBound: Bound
/**
The range's upper bound.
A range is empty if `upperBound` is equal to `lowerBound`.
*/
public let upperBound: Bound
/**
Creates an instance with the given bounds.
Because this initializer does not perform any checks, it should be used as an optimization only when you are absolutely certian that `lower` is less than or equal to `upper`. Using the left-open range operator (`>**`) to form `LeftOpenRange` instances is preferred.
- Parameter bounds: A tuple of the lower and upper bounds of the range.
- Postcondition:
- `lowerBound == bounds.lower`.
- `upperBound == bounds.upper`.
*/
public init(uncheckedBounds bounds: (lower: Bound, upper: Bound)) {
lowerBound = bounds.lower
upperBound = bounds.upper
}
/// Indicates whether the range contains no elements.
public var isEmpty: Bool { return lowerBound == upperBound }
}
/**
A partial interval extending upward after a lower bound.
You create `PartialRangePast` instances by using the postfix left-open range operator (postfix `>**`).
let moreThanFive = 5>**
You can use a partial range to quickly check if a value is contained in a particular range of values. For example:
moreThanFive.contains(4)
// false
moreThanFive.contains(5)
// false
moreThanFive.contains(6)
// true
You can use a partial range of a collection's indices to represent the range from the partial range's lower bound up to the end of the collection.
let numbers = [10, 20, 30, 40, 50, 60, 70]
print(numbers[3>**])
// Prints "[50, 60, 70]"
Using a Partial Range as a Sequence
-----------------------------------
When a partial range uses integers as its lower and upper bounds, or any other type that conforms to the `Strideable` protocol with an integer stride, you can use that range in a `for`-`in` loop or with any sequence method that doesn't require that the sequence is finite. The elements of a partial range are the consecutive values from its lower bound continuing upward indefinitely.
func isTheMagicNumber(_ x: Int) -> Bool {
return x == 3
}
for x in 1>** {
if isTheMagicNumber(x) {
print("\(x) is the magic number!")
break
} else {
print("\(x) wasn't it...")
}
}
// "2 wasn't it..."
// "3 is the magic number!"
Because a `PartialRangePast` sequence counts upward indefinitely, do not use one with methods that read the entire sequence before returning, such as `map(_:)`, `filter(_:)`, or `suffix(_:)`. It is safe to use operations that put an upper limit on the number of elements they access, such as `prefix(_:)` or `dropFirst(_:)`, and operations that you can guarantee will terminate, such as passing a closure you know will eventually return `true` to `first(where:)`.
In the following example, the `asciiTable` sequence is made by zipping together the characters in the `alphabet` string with a partial range starting at 65, the ASCII value of the capital letter A. Iterating over two zipped sequences continues only as long as the shorter of the two sequences, so the iteration stops at the end of `alphabet`.
let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
let asciiTable = zip(65>**, alphabet)
for (code, letter) in asciiTable {
print(code, letter)
}
// "66 B"
// "67 C"
// "68 D"
// ...
// "89 Y"
// "90 Z"
The behavior of incrementing indefinitely is determined by the type of `Bound`. For example, iterating over an instance of `PartialRangePast<Int>` traps when the sequence's next value would be above `Int.max`.
*/
public struct PartialRangePast<Bound: Comparable> {
public let lowerBound: Bound
public init(_ lowerBound: Bound) { self.lowerBound = lowerBound }
}
// MARK: Range Operator
infix operator >**: RangeFormationPrecedence
postfix operator >**
extension Comparable {
/**
Returns a half-open range that contains its upper bound but not its lower bound.
Use the left-open range operator (`>**`) to create a range of any type that conforms to the `Comparable` protocol. This example creates a `LeftOpenRange<Double>` from, but not including, zero up to 5.0.
let positiveUpToFive = 0.0>**5.0
print(positiveUpToFive.contains(3.14)) // Prints "true"
print(positiveUpToFive.contains(5.0)) // Prints "true"
print(positiveUpToFive.contains(0.0)) // Prints "false"
- Parameter minimum: The lower bound for the range.
- Parameter maximum: The upper bound for the range.
- Returns: The range value.
*/
public static func >**(minimum: Self, maximum: Self) -> LeftOpenRange<Self> {
precondition(minimum <= maximum)
return LeftOpenRange(uncheckedBounds: (minimum, maximum))
}
/**
Returns a partial range extending upward after a lower bound.
Use the postfix left-open range operator (postfix `>**`) to create a partial range of any type that conforms to the `Comparable` protocol. This example creates a `PartialRangePast<Double>` instance that includes any value greater than (but not equal to) `5.0`.
let moreThanFive = 5.0>**
moreThanFive.contains(4.0) // false
moreThanFive.contains(5.0) // false
moreThanFive.contains(6.0) // true
You can use this type of partial range of a collection's indices to represent the range from after the partial range's lower bound up to the end of the collection.
let numbers = [10, 20, 30, 40, 50, 60, 70]
print(numbers[3>**])
// Prints "[50, 60, 70]"
- Parameter minimum: The lower bound for the range.
- Returns: The range value.
*/
public static postfix func >**(minimum: Self) -> PartialRangePast<Self> {
return PartialRangePast(minimum)
}
}
// MARK: - Range Expressions
extension LeftOpenRange: RangeExpression {
public func relative<C: Collection>(to collection: C) -> Range<Bound> where C.Index == Bound {
guard !isEmpty else { return lowerBound ..< lowerBound }
return collection.index(after: lowerBound) ..< collection.index(after: upperBound)
}
public func contains(_ element: Bound) -> Bool {
return lowerBound < element && element <= upperBound
}
}
extension PartialRangePast: RangeExpression {
public func relative<C: Collection>(to collection: C) -> Range<Bound> where C.Index == Bound {
let end = collection.endIndex
return (collection.index(lowerBound, offsetBy: +1, limitedBy: end) ?? end)..<end
}
public func contains(_ element: Bound) -> Bool {
return lowerBound < element
}
}
// MARK: Range Operations
extension LeftOpenRange {
/**
Returns a copy of this range clamped to the given limiting range.
The bounds of the result are always limited to the bounds of `limits`. For example.
let x: LeftOpenRange = 0>**20
print(x.clamped(to: 10>**1000))
// Prints "10>**20"
If the two ranges do not overlap, the result is an empty range within the bounds of `limits`.
let y: LeftOpenRange = 0>**5
print(y.clamped(to: 10>**1000))
// Prints "10>**10"
- Parameter limits: The range to clamp the bounds of this range.
- Returns: A new range clamped to the bounds of `limits`.
*/
public func clamped(to limits: LeftOpenRange) -> LeftOpenRange {
let resultLower = Swift.max(limits.lowerBound, Swift.min(limits.upperBound, lowerBound))
let resultUpper = Swift.min(limits.upperBound, Swift.max(limits.lowerBound, upperBound))
return LeftOpenRange(uncheckedBounds: (resultLower, resultUpper))
}
/**
Returns a Boolean value indicating whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: LeftOpenRange = 0>**20
print(x.overlaps(10..<1000))
// Prints "true"
Because a left-open range does not include its lower bound, the ranges in the following example do not overlap:
let y = -5>**0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: LeftOpenRange) -> Bool {
return (!other.isEmpty && contains(other.upperBound)) || (!isEmpty && other.contains(upperBound))
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: LeftOpenRange = 0>**20
print(x.overlaps(10>*<1000 as OpenRange))
// Prints "true"
Because open ranges exclude at least one bound, the ranges in the following example do not overlap:
let y: OpenRange = -5>*<0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: OpenRange<Bound>) -> Bool {
return other.overlaps(self)
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: LeftOpenRange = 0>**20
print(x.overlaps(10..<1000 as Range))
// Prints "true"
Because left- and right-open ranges exclude one bound each, the ranges in the following example do not overlap:
let y: Range = -5..<0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: Range<Bound>) -> Bool {
guard !isEmpty, !other.isEmpty else { return false }
return other.upperBound > lowerBound && upperBound >= other.lowerBound
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: LeftOpenRange = 0>**20
print(x.overlaps(10...1000 as ClosedRange))
// Prints "true"
Because a half-open range does not include its lower bound, the ranges in the following example do not overlap:
let y: ClosedRange = -5...0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: ClosedRange<Bound>) -> Bool {
return contains(other.upperBound) || (!isEmpty && other.contains(upperBound))
}
}
extension Range {
/// Returns whether this range and the given range contain an element in common.
public func overlaps(_ other: LeftOpenRange<Bound>) -> Bool {
return other.overlaps(self)
}
}
extension ClosedRange {
/// Returns whether this range and the given range contain an element in common.
public func overlaps(_ other: LeftOpenRange<Bound>) -> Bool {
return other.overlaps(self)
}
}
// MARK: Range Conversions
extension LeftOpenRange where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `OpenRange`.
- Parameter other: A fully-open range to convert to an `LeftOpenRange` instance.
*/
public init(_ other: OpenRange<Bound>) {
guard !other.isEmpty else { self.init(uncheckedBounds: (other.lowerBound, other.upperBound)) ; return }
self = other.lowerBound >** other.upperBound.advanced(by: -1)
}
/**
Creates an instance equivalent to the given `Range`.
- Note: The equivalent range must have representable bounds. For example, if a `Range<Int>` instance used `Int.min` as its lower bound, then expanding the boundary outward would trigger a runtime error.
- Parameter other: A right-open range to convert to an `LeftOpenRange` instance.
*/
public init(_ other: Range<Bound>) {
guard !other.isEmpty else { self = other.upperBound >** other.upperBound ; return }
self = other.lowerBound.advanced(by: -1) >** other.upperBound.advanced(by: -1)
}
/**
Creates an instance equivalent to the given `ClosedRange`.
- Note: The equivalent range must have repesentable bounds. For example, if a `ClosedRange<Int>` instance used `Int.min` as its lower bound then expanding the boundary outward would trigger a runtime error.
- Parameter other: A closed range to convert to an `LeftOpenRange` instance.
*/
public init(_ other: ClosedRange<Bound>) {
self = other.lowerBound.advanced(by: -1) >** other.upperBound
}
}
extension Range where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `LeftOpenRange`.
- Parameter other: A left-open range to convert to a `Range` instance.
*/
public init(_ other: LeftOpenRange<Bound>) {
guard !other.isEmpty else { self = other.lowerBound ..< other.lowerBound ; return }
self = other.lowerBound.advanced(by: +1) ..< other.upperBound.advanced(by: +1)
}
}
extension ClosedRange where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `LeftOpenRange`.
- Precondition: `!other.isEmpty`.
- Parameter other: A left-open range to convert to a `ClosedRange` instance.
*/
public init(_ other: LeftOpenRange<Bound>) {
precondition(!other.isEmpty)
self = other.lowerBound.advanced(by: +1) ... other.upperBound
}
}
// MARK: - Sequence & Collection Support
extension LeftOpenRange: Sequence, Collection, PreflightedCollection, BidirectionalCollection, RandomAccessCollection where Bound: Strideable, Bound.Stride: SignedInteger {
public typealias Element = Bound
public typealias Iterator = StrideThroughIterator<Bound>
public typealias SubSequence = LeftOpenRange
public func makeIterator() -> Iterator {
return stride(from: lowerBound.advanced(by: +1), through: upperBound, by: +1).makeIterator()
}
public var underestimatedCount: Int {
return numericCast(lowerBound.distance(to: upperBound))
}
public typealias Index = Bound
public typealias Indices = LeftOpenRange
public var startIndex: Index {
guard !isEmpty else { return beforeStartIndex }
return lowerBound.advanced(by: +1)
}
public var endIndex: Index {
guard !isEmpty else { return startIndex }
return upperBound.advanced(by: +1)
}
public subscript(position: Index) -> Element { return position }
public subscript(bounds: Range<Index>) -> SubSequence { return LeftOpenRange(bounds) }
public var indices: Indices { return self }
public func index(after i: Index) -> Index { return i.advanced(by: +1) }
public var beforeStartIndex: Index { return lowerBound }
public func index(before i: Index) -> Index { return i.advanced(by: -1) }
public func index(_ i: Index, offsetBy n: Int) -> Index {
return i.advanced(by: numericCast(n))
}
public func distance(from start: Index, to end: Index) -> Int {
return numericCast(start.distance(to: end))
}
}
extension PartialRangePast: Sequence where Bound: Strideable, Bound.Stride: SignedInteger {
public typealias Element = Bound
public typealias Iterator = UnfoldFirstSequence<Bound>
public func makeIterator() -> Iterator {
return sequence(first: lowerBound.advanced(by: +1)) { $0.advanced(by: +1) }
}
}
// MARK: Display Support
extension LeftOpenRange: CustomStringConvertible {
public var description: String {
return "\(lowerBound)>**\(upperBound)"
}
}
extension LeftOpenRange: CustomDebugStringConvertible {
public var debugDescription: String {
return "\(String(describing: LeftOpenRange.self))(\(String(reflecting: lowerBound))>**\(String(reflecting: upperBound)))"
}
}
// MARK: Hashing
extension LeftOpenRange: Hashable where Bound: Hashable {
public var hashValue: Int {
return HashablePair(a: lowerBound, b: upperBound).hashValue
}
}
Raw
OpenRange.swift
//
// OpenRange.swift
// NodeCollections
//
// Created by Daryle Walker on 4/4/18.
// Copyright © 2018 Daryle Walker. All rights reserved.
//
// MARK: Primary Definition
/**
An open interval over a comparable type, from a lower bound up to an upper bound, excluding both endpoints.
An `OpenRange` interval can be created with the open range operator (`>*<`).
let withinZeroToFive = 0.0 >*< 5.0
An `OpenRange` instance can be used to quickly check if a value is contained in a particular range of values. For example:
print(withinZeroToFive.contains(3.14)) // Prints "true"
print(withinZeroToFive.contains(6.28)) // Prints "false"
print(withinZeroToFive.contains(5.0)) // Prints "false"
`OpenRange` instances can represent an empty interval, like `Range`.
let empty = 0.0 >*< 0.0
print(empty.contains(0.0)) // Prints "false"
print(empty.isEmpty) // Prints "true"
Like `Range` and `ClosedRange`, an `OpenRange` instance can be used as a collection itself when the bound type has an integer stride.
func printStartIndex<C: Collection>(of collection: C) {
print(String(describing: collection.startIndex))
}
printStartIndex(of: 5 >*< 10) // Prints "6"
*/
public struct OpenRange<Bound: Comparable>: Equatable { // Use automatic synthesis for Equatable.
/**
The range's lower bound.
A range is empty if `lowerBound` is equal to `upperBound`.
*/
public let lowerBound: Bound
/**
The range's upper bound.
A range is empty if `upperBound` is equal to `lowerBound`.
*/
public let upperBound: Bound
/**
Creates an instance with the given bounds.
Because this initializer does not perform any checks, it should be used as an optimization only when you are absolutely certian that `lower` is less than or equal to `upper`. Using the fully-open range operator (`>*<`) to form `OpenRange` instances is preferred.
- Parameter bounds: A tuple of the lower and upper bounds of the range.
- Postcondition:
- `lowerBound == bounds.lower`.
- `upperBound == bounds.upper`.
*/
public init(uncheckedBounds bounds: (lower: Bound, upper: Bound)) {
lowerBound = bounds.lower
upperBound = bounds.upper
}
/// Indicates whether the range contains no elements.
public var isEmpty: Bool {
return lowerBound == upperBound
}
}
// MARK: Range Operator
infix operator >*<: RangeFormationPrecedence
extension Comparable {
/**
Returns a fully-open range that contains what is strictly between its bounds, excluding said bounds.
Use the open range operator (`>*<`) to create a range of any type that conforms to the `Comparable` protocol. This example creates an `OpenRange<Double>` bounding values strictly greater than zero and strictly less than five.
let lessThanFive = 0.0>*<5.0
print(lessThanFive.contains(3.14)) // Prints "true"
print(lessThanFive.contains(5.0)) // Prints "false"
- Parameter minimum: The lower bound for the range.
- Parameter maximum: The upper bound for the range.
- Returns: The range value.
*/
public static func >*<(minimum: Self, maximum: Self) -> OpenRange<Self> {
precondition(minimum <= maximum)
return OpenRange(uncheckedBounds: (minimum, maximum))
}
}
// MARK: - Range Expressions
extension OpenRange: RangeExpression {
public func relative<C: Collection>(to collection: C) -> Range<Bound> where C.Index == Bound {
guard !isEmpty else { return upperBound ..< upperBound }
return collection.index(after: lowerBound) ..< upperBound
}
public func contains(_ element: Bound) -> Bool {
return lowerBound < element && element < upperBound
}
}
// MARK: Range Operations
extension OpenRange {
/**
Returns a copy of this range clamped to the given limiting range.
The bounds of the result are always limited to the bounds of `limits`. For example.
let x: OpenRange = 0>*<20
print(x.clamped(to: 10>*<1000))
// Prints "10>*<20"
If the two ranges do not overlap, the result is an empty range within the bounds of `limits`.
let y: OpenRange = 0>*<5
print(y.clamped(to: 10>*<1000))
// Prints "10>*<10"
- Parameter limits: The range to clamp the bounds of this range.
- Returns: A new range clamped to the bounds of `limits`.
*/
public func clamped(to limits: OpenRange) -> OpenRange {
let resultLower = Swift.max(limits.lowerBound, Swift.min(limits.upperBound, lowerBound))
let resultUpper = Swift.min(limits.upperBound, Swift.max(limits.lowerBound, upperBound))
return OpenRange(uncheckedBounds: (resultLower, resultUpper))
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: OpenRange = 0>*< 20
print(x.overlaps(10>*<1000 as OpenRange))
// Prints "true"
Because an open range does not include either bound, the ranges in the following example do not overlap:
let y: OpenRange = 20>*<30
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: OpenRange) -> Bool {
guard !isEmpty, !other.isEmpty else { return false }
return other.upperBound > lowerBound && upperBound > other.lowerBound
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: OpenRange = 0>*<20
print(x.overlaps(10>**1000 as LeftOpenRange))
// Prints "true"
Because an open range does not include either bound, the ranges in the following example do not overlap:
let y: LeftOpenRange = -5>**0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: LeftOpenRange<Bound>) -> Bool {
return contains(other.upperBound) || overlaps(other.lowerBound >*< other.upperBound)
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: OpenRange = 0>*<20
print(x.overlaps(10..<1000 as Range))
// Prints "true"
Because an open range does not include either bound, the ranges in the following example do not overlap:
let y: Range = 20..<30
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: Range<Bound>) -> Bool {
return contains(other.lowerBound) || overlaps(other.lowerBound >*< other.upperBound)
}
/**
Returns whether this range and the given range contain an element in common.
This example shows two overlapping ranges:
let x: OpenRange = 0>*<20
print(x.overlaps(10...1000 as ClosedRange))
// Prints "true"
Because an open range does not include either bound, the ranges in the following example do not overlap:
let y: ClosedRange = -5...0
print(x.overlaps(y))
// Prints "false"
- Parameter other: A range to check for elements in common.
- Returns: `true` if this range and `other` have at least one element in common; otherwise, `false`.
*/
public func overlaps(_ other: ClosedRange<Bound>) -> Bool {
return contains(other.upperBound) || overlaps(other.lowerBound ..< other.upperBound)
}
}
extension Range {
/// Returns whether this range and the given range contain an element in common.
public func overlaps(_ other: OpenRange<Bound>) -> Bool {
return other.overlaps(self)
}
}
extension ClosedRange {
/// Returns whether this range and the given range contain an element in common.
public func overlaps(_ other: OpenRange<Bound>) -> Bool {
return other.overlaps(self)
}
}
// MARK: Range Conversions
extension OpenRange where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `LeftOpenRange`.
- Note: The equivalent range must have representable bounds. For example, if a `LeftOpenRange<Int>` instance used `Int.max` as its upper bound, then expanding the boundary outward would trigger a runtime error.
- Parameter other: A left-open range to convert to an `OpenRange` instance.
*/
public init(_ other: LeftOpenRange<Bound>) {
guard !other.isEmpty else { self.init(uncheckedBounds: (other.lowerBound, other.upperBound)) ; return }
self = other.lowerBound >*< other.upperBound.advanced(by: +1)
}
/**
Creates an instance equivalent to the given `Range`.
- Note: The equivalent range must have representable bounds. For example, if a `Range<Int>` instance used `Int.min` as its lower bound, then expanding the boundary outward would trigger a runtime error.
- Parameter other: A right-open range to convert to an `OpenRange` instance.
*/
public init(_ other: Range<Bound>) {
guard !other.isEmpty else { self.init(uncheckedBounds: (other.lowerBound, other.upperBound)) ; return }
self = other.lowerBound.advanced(by: -1) >*< other.upperBound
}
/**
Creates an instance equivalent to the given `ClosedRange`.
- Note: The equivalent range must have repesentable bounds. For example, if a `ClosedRange<Int>` instance used `Int.min` as its lower bound and/or `Int.max` as its upper bound, then expanding the boundaries outward would trigger a runtime error.
- Parameter other: A closed range to convert to an `OpenRange` instance.
*/
public init(_ other: ClosedRange<Bound>) {
self = other.lowerBound.advanced(by: -1) >*< other.upperBound.advanced(by: +1)
}
}
extension Range where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `OpenRange`.
- Parameter other: A fully-open range to convert to a `Range` instance.
*/
public init(_ other: OpenRange<Bound>) {
guard !other.isEmpty else { self = other.upperBound ..< other.upperBound ; return }
self = other.lowerBound.advanced(by: +1) ..< other.upperBound
}
}
extension ClosedRange where Bound: Strideable, Bound.Stride: SignedInteger {
/**
Creates an instance equivalent to the given `OpenRange`.
- Precondition: `!other.isEmpty`.
- Parameter other: A fully-open range to convert to a `ClosedRange` instance.
*/
public init(_ other: OpenRange<Bound>) {
precondition(!other.isEmpty)
self = other.lowerBound.advanced(by: +1) ... other.upperBound.advanced(by: -1)
}
}
// MARK: - Collection Support
extension OpenRange: Sequence, Collection, PreflightedCollection, BidirectionalCollection, RandomAccessCollection where Bound: Strideable, Bound.Stride: SignedInteger {
public typealias Element = Bound
public typealias Iterator = StrideToIterator<Bound>
public typealias SubSequence = OpenRange
public typealias Index = Bound
public typealias Indices = OpenRange
public func makeIterator() -> Iterator {
return stride(from: lowerBound.advanced(by: +1), to: upperBound, by: +1).makeIterator()
}
public var underestimatedCount: Int {
return numericCast(Swift.max(0, lowerBound.distance(to: upperBound) - 1))
}
public var endIndex: Index { return upperBound }
public var startIndex: Index {
guard !isEmpty else { return endIndex }
return lowerBound.advanced(by: +1)
}
public var beforeStartIndex: Index { return lowerBound }
public subscript(position: Index) -> Element {
return position
}
public subscript(bounds: Range<Index>) -> SubSequence {
return OpenRange(bounds)
}
public var indices: Indices { return self }
public func index(after i: Index) -> Index {
return i.advanced(by: +1)
}
public func index(before i: Index) -> Index {
return i.advanced(by: -1)
}
public func index(_ i: Index, offsetBy n: Int) -> Index {
return i.advanced(by: numericCast(n))
}
public func distance(from start: Index, to end: Index) -> Int {
return numericCast(start.distance(to: end))
}
}
// MARK: Display Support
extension OpenRange: CustomStringConvertible {
public var description: String {
return "\(lowerBound)>*<\(upperBound)"
}
}
extension OpenRange: CustomDebugStringConvertible {
public var debugDescription: String {
return "\(String(describing: OpenRange.self))(\(String(reflecting: lowerBound))>*<\(String(reflecting: upperBound)))"
}
}
// MARK: Hashing
/// Quick nominal product type to enable use of automatic hash support, even for conditional conformance.
internal struct HashablePair<T: Hashable>: Hashable { let a: T, b: T }
extension OpenRange: Hashable where Bound: Hashable {
public var hashValue: Int {
return HashablePair(a: lowerBound, b: upperBound).hashValue
}
}
Raw
PreflightedCollection.swift
//
// PreflightedCollection.swift
// NodeCollections
//
// Created by Daryle Walker on 4/5/18.
// Copyright © 2018 Daryle Walker. All rights reserved.
//
// MARK: Primary Definition
/**
A collection that supports a "past the start" sentinel index value.
Before-the-start index values ensure that extraction operations on the prefixes of instances of types conforming to `PoorlyTransferableCollection` (*i.e.* singly-linked list types) can use the same methods that take a general (open) range, instead of custom variant methods targeting the prefix of a collection.
Conforming to the PreflightedCollection Protocol
================================================
To add PreflightedCollection conformance to your custom types, implement the `beforeStartIndex` property in addition to the requirements of the `Collection` protocol.
If your type also conforms to `BidirectionalCollection`, now `c.index(after: c.index(before: c.startIndex)) == c.startIndex` is valid (and `true`) for a given bi-directional collection `c`.
*/
public protocol PreflightedCollection: Collection where SubSequence: PreflightedCollection {
/**
The collection's "past the start" position—that is, the position one less than the first valid subscript argument.
Note that "past" from `startIndex` to `beforeStartIndex` is the opposite direction as going from the last valid subscript argument to `endIndex`.
When you need an (at least) left-open range that includes the first element of a collection, use the fully-open range operator (`>*<`) or left-open range operator (`>**`) with `beforeStartIndex`. Either operator creates a range that doesn’t include the lower bound, so it’s always safe to use with `beforeStartIndex`. For example:
var numbers: MyDoublyLinkedList = [10, 20, 30, 40, 50]
if let index = numbers.index(of: 30) {
let lowNumbers = numbers.segregate(out: numbers.beforeStartIndex >** index)
print(lowNumbers)
}
print(numbers)
/*
Prints: """
[10, 20, 30]
[40, 50]
"""
*/
As the "past the start" sentinel,
c.index(after: c.beforeStartIndex) == c.startIndex
b.index(before: b.startIndex) == b.beforeStartIndex
for given non-empty collections `c` and `b`, where the type of `b` also conforms to `BidirectionalCollection`. Like `endIndex`, `beforeStartIndex` is not dereferencable relative to `self` because there is no corresponding element. And it is not proper to backwards-iterate to before `beforeStartIndex`.
If the collection is empty, `beforeStartIndex` is equal to `startIndex` (and `endIndex`).
*/
var beforeStartIndex: Index { get }
}
// MARK: Support
extension Slice: PreflightedCollection where Base: PreflightedCollection {
// Note that approaching the "past the start" index requires O(n) search time.
public var beforeStartIndex: Index {
var result = base.beforeStartIndex
while result < endIndex {
let next = index(after: result)
if next == startIndex {
break
} else {
result = next
}
}
return result
}
}
extension Slice where Base: PreflightedCollection, Base: BidirectionalCollection {
public var beforeStartIndex: Index {
return base.index(startIndex, offsetBy: -1, limitedBy: base.beforeStartIndex) ?? base.beforeStartIndex
}
}
Raw
SinglyLinkedList.swift
//
// SinglyLinkedList.swift
// NodeCollections
//
// Created by Daryle Walker on 4/9/18.
// Copyright © 2018 Daryle Walker. All rights reserved.
//
/// A singly-linked list.
public struct SinglyLinkedList<Element> {
/// Nodes for the list
final class Node {
/// The type to order nodes of the same list, even if not directly connected.
typealias ListNodeID = Double
/// The type for list references.
typealias ListID = OpaquePointer
/// The data.
let payload: Element
/// The next node, but one for each list that shares this node.
var links: [ListID: (id: ListNodeID, next: Node?)]
/// Creates a node with a given payload but no links.
init(_ x: Element) { payload = x ; links = [:] }
/// Iterator over a node and its trailing siblings for a specific list.
struct ListIterator: IteratorProtocol {
/// Ths list to follow.
let list: ListID
/// The current node.
var node: Node?
/// Creates an iterator for this possible node and its followers for the given list.
init(node: Node?, list: ListID) {
precondition(nil == node || nil != node!.links[list])
self.list = list
self.node = node
}
mutating func next() -> Node? {
defer { node = node?.links[list]?.next }
return node
}
}
/// Makes an iterator that goes from this node to all of its trailing siblings for the specified list.
func makeListIterator(forList list: ListID) -> ListIterator {
return ListIterator(node: self, list: list)
}
}
/// A reference type pointing to a list of nodes.
final class Header {
/// An ID based on `self` to use in dictionaries.
var opaqueID: Node.ListID { return OpaquePointer(Unmanaged.passUnretained(self).toOpaque()) }
/// The first node, if any.
var head: Node?
/// The last node, if any. Tracked to ease appending nodes.
weak var tail: Node?
/// Creates a header for an empty list.
init() { head = nil ; tail = nil }
deinit {
let myID = opaqueID
IteratorSequence(makeNodeIterator()).reversed().forEach { $0.links.removeValue(forKey: myID) }
tail = nil
head = nil
}
/// Makes an iterator for all of this list's nodes, from head to tail.
func makeNodeIterator() -> Node.ListIterator { return Node.ListIterator(node: head, list: opaqueID) }
}
/// Kind of ranges a list uses of its list-reference.
enum NodeRange {
/// No nodes are being stored.
case empty
/// All of the list-reference's nodes are in this list.
case all(from: Header)
/// All of the list-reference's nodes starting from a given point.
case suffix(`for`: Header, from: Node)
/// A segment of the list-reference; closed bounds.
case closedRange(`for`: Header, start: Node, upThrough: Node)
/// A segment of the list-reference; right-open bounds.
case regularRange(`for`: Header, start: Node, upTo: Node)
}
/// An iterator over the nodes.
struct NodeIterator {
/// The nodes' list and an iterator. The header is retained so it isn't deleted mid-iteration.
var headerAndIterator: (header: Header, nodeIterator: Node.ListIterator)?
/// A node to stop iterating, either at or before.
let nodeLimit: Node?
/// Whether to stop before the limit.
let stopBeforeLimit: Bool
/// Creates an iterator over the given node range.
init(_ nodes: NodeRange) {
switch nodes {
case .empty:
headerAndIterator = nil ; nodeLimit = nil ; stopBeforeLimit = true
case .all(let h):
headerAndIterator = (header: h, nodeIterator: h.makeNodeIterator())
nodeLimit = nil ; stopBeforeLimit = true
case .suffix(let h, let s):
headerAndIterator = (header: h, nodeIterator: s.makeListIterator(forList: h.opaqueID))
nodeLimit = nil ; stopBeforeLimit = true
case .closedRange(let h, let s, let e):
let myID = h.opaqueID
precondition(s.links[myID]!.id < e.links[myID]!.id)
headerAndIterator = (header: h, nodeIterator: s.makeListIterator(forList: myID))
nodeLimit = e
stopBeforeLimit = false
case .regularRange(let h, let s, let e):
let myID = h.opaqueID
precondition(s.links[myID]!.id < e.links[myID]!.id)
headerAndIterator = (header: h, nodeIterator: s.makeListIterator(forList: myID))
nodeLimit = e
stopBeforeLimit = true
}
}
}
/// The list of nodes. A refernce type so multiple instances can share.
var header: Header? {
switch nodes {
case .empty:
return nil
case .all(let h):
return h
case .suffix(let h, _):
return h
case .closedRange(let h, _, _):
return h
case .regularRange(let h, _, _):
return h
}
}
/// Storage for the list-reference and the utilized range.
var nodes: NodeRange
/// Creates a list that copies a sequence of values.
public init<S: Sequence>(_ elements: S) where S.Element == Element {
let header = Header()
elements.map(Node.init).reversed().forEach { header.pushHead(with: $0) }
if case .some = header.head {
nodes = .all(from: header)
} else {
nodes = .empty
}
}
}
// MARK: Header Operations
extension SinglyLinkedList.Header {
/// Prepend a node. Must not already be in the list.
func pushHead(with newNode: SinglyLinkedList.Node, usingNodeID nodeID: SinglyLinkedList.Node.ListNodeID = 0) {
let myID = opaqueID
precondition(nil == newNode.links[myID])
precondition(nodeID.isNormal || nodeID.isZero)
let newNodeID: SinglyLinkedList.Node.ListNodeID
if let currentHead = head {
let trialID = currentHead.links[myID]!.id
newNodeID = nodeID < trialID ? nodeID : trialID - 1
} else {
newNodeID = nodeID
}
newNode.links[myID] = (id: newNodeID, next: head)
head = newNode
if case .none = tail {
tail = newNode
}
}
}
// MARK: Node-Range Operations
extension SinglyLinkedList.NodeRange {
/// Makes an iterator for all of this range's nodes, ignoring outside nodes.
func makeNodeIterator() -> SinglyLinkedList.NodeIterator { return SinglyLinkedList.NodeIterator(self) }
}
// MARK: Node-Iterator Operations
extension SinglyLinkedList.NodeIterator: IteratorProtocol {
mutating func next() -> SinglyLinkedList.Node? {
guard let nextNode = headerAndIterator?.nodeIterator.next() else { return nil }
guard let limit = nodeLimit, limit === nextNode else { return nextNode }
headerAndIterator = nil
return stopBeforeLimit ? nil : nextNode
}
}
// MARK: - Sequence/Collection Preliminaries
extension SinglyLinkedList {
/// Check whether a given node is part of the list.
func containsNode(_ n: Node) -> Bool {
guard let myID = header?.opaqueID else { return false }
guard let nLink = n.links[myID] else { return false }
switch nodes {
case .empty:
return false // should've been covered by the first guard above
case .all:
return true // the reverse covered by the second guard above
case .suffix(_, let start):
return start.links[myID]!.id <= nLink.id
case .closedRange(_, let start, let end):
return (start.links[myID]!.id ... end.links[myID]!.id).contains(nLink.id)
case .regularRange(_, let start, let end):
return (start.links[myID]!.id ..< end.links[myID]!.id).contains(nLink.id)
}
}
// An iterator over the nodes' elements.
public struct Iterator {
/// The node-level iterator.
var iterator: NodeIterator
/// Creates an iterator over the given nodes.
init(withNodes n: NodeRange) {
iterator = n.makeNodeIterator()
}
}
// An index for a node/element. Make sure sub-sequences carry over node IDs during cloning so index crossover can work.
public struct Index {
/// The node holding the element.
weak var node: Node?
/// The element's node ID for this particular list.
let nodeID: Node.ListNodeID
/// Creates an index for a given node and its ID within a list.
init(node: Node?, id: Node.ListNodeID) { self.node = node ; nodeID = id }
/// An instance that compares before any other.
static var beforeAnyOther: Index { return Index(node: nil, id: -.infinity) }
/// An instance that compares after any other.
static var afterAnyOther: Index { return Index(node: nil, id: .infinity) }
}
/// Piece-together a list from the prefix & suffix of one list and the middle of another.
static func stichList(withOutsideOf outList: SinglyLinkedList, excludedRange: LeftOpenRange<Index>, andInsideOf inList: SinglyLinkedList, includedRange: LeftOpenRange<Index>) -> (list: SinglyLinkedList, innerRange: LeftOpenRange<Index>) {
// Layout the nodes
var newListNodes = [(node: Node, id: Node.ListNodeID)]()
var n = outList.startIndex
while n <= excludedRange.lowerBound, n != outList.endIndex {
newListNodes.append((node: n.node!, id: n.nodeID))
outList.formIndex(after: &n)
}
let lastPrefixOffset = newListNodes.count - 1
n = includedRange.lowerBound
if inList.formIndex(&n, offsetBy: +1, limitedBy: includedRange.upperBound) {
while n <= includedRange.upperBound, n != inList.endIndex {
newListNodes.append((node: n.node!, id: n.nodeID))
inList.formIndex(after: &n)
}
}
let firstSuffixOffset = newListNodes.count
n = excludedRange.upperBound
if outList.formIndex(&n, offsetBy: +1, limitedBy: outList.endIndex) {
while n < outList.endIndex {
newListNodes.append((node: n.node!, id: n.nodeID))
outList.formIndex(after: &n)
}
}
// Calculate the interior nodes' new IDs from the surrounding exterior nodes.
switch (lastPrefixOffset < 0, firstSuffixOffset >= newListNodes.count) {
case (false, false):
// Interior nodes are completly interior.
let spacing = newListNodes[lastPrefixOffset].id.distance(to: newListNodes[firstSuffixOffset].id) / Node.ListNodeID.Stride(lastPrefixOffset.distance(to: firstSuffixOffset))
for i in stride(from: lastPrefixOffset + 1, to: firstSuffixOffset, by: +1) {
newListNodes[i].id = newListNodes[i - 1].id + spacing
}
case (true, false):
// Interior nodes are actually a prefix.
for i in stride(from: firstSuffixOffset - 1, through: 0, by: -1) {
newListNodes[i].id = newListNodes[i + 1].id - 1
}
case (false, true):
// Interior nodes are actually a suffix.
for i in stride(from: lastPrefixOffset + 1, to: newListNodes.count, by: +1) {
newListNodes[i].id = newListNodes[i - 1].id + 1
}
case (true, true):
// Interior nodes make up the entirety of the list; don't bother changing IDs.
break
}
// Make a new list for the nodes.
let listHeader = Header()
newListNodes.reversed().forEach { listHeader.pushHead(with: $0.node, usingNodeID: $0.id) }
if case .some = listHeader.head {
var resultList = SinglyLinkedList()
resultList.nodes = .all(from: listHeader)
let beforeInnerRange = lastPrefixOffset < 0 ? resultList.beforeStartIndex : Index(node: newListNodes[lastPrefixOffset].node, id: newListNodes[lastPrefixOffset].id)
let lastInnerOffset = firstSuffixOffset - 1
let lastInnerRange = lastInnerOffset < 0 ? beforeInnerRange : Index(node: newListNodes[lastInnerOffset].node, id: newListNodes[lastInnerOffset].id)
return (list: resultList, innerRange: beforeInnerRange >** lastInnerRange)
} else {
let resultList = SinglyLinkedList()
return (list: resultList, innerRange: resultList.beforeStartIndex >** resultList.endIndex)
}
}
}
extension SinglyLinkedList.Iterator: IteratorProtocol {
public mutating func next() -> Element? { return iterator.next()?.payload }
}
extension SinglyLinkedList.Index: Equatable {
public static func == (lhs: SinglyLinkedList.Index, rhs: SinglyLinkedList.Index) -> Bool {
switch (lhs.node, rhs.node) {
case (let ln?, let rn?):
assert(ln !== rn || lhs.nodeID == rhs.nodeID)
return ln === rn
case (nil, nil):
return lhs.nodeID == rhs.nodeID
default:
return false
}
}
}
extension SinglyLinkedList.Index: Comparable {
public static func < (lhs: SinglyLinkedList.Index, rhs: SinglyLinkedList.Index) -> Bool {
return lhs.nodeID < rhs.nodeID
}
}
// MARK: - Array-Expression Support
extension SinglyLinkedList: ExpressibleByArrayLiteral {
public init(arrayLiteral elements: Element...) {
self.init(elements)
}
}
// MARK: Collection Support
extension SinglyLinkedList: PoorlyTransferableCollection, RangeReplaceableCollection {
public func makeIterator() -> Iterator { return Iterator(withNodes: nodes) }
public var underestimatedCount: Int {
switch nodes {
case .empty:
return 0
case .all(let header):
return header.head! === header.tail! ? 1 : 2
case .suffix(let header, let start):
return start === header.tail! ? 1 : 2
case .closedRange(_, let start, let end):
return start === end ? 1 : 2
case .regularRange(_, let start, let end):
assert(start !== end)
return 1
}
}
public var endIndex: Index {
guard case .regularRange(_, _, let end) = nodes else { return .afterAnyOther }
return Index(node: end, id: end.links[header!.opaqueID]!.id)
}
public var startIndex: Index {
guard let myID = header?.opaqueID else { return endIndex }
switch nodes {
case .empty:
return endIndex // should've already been covered by the above guard
case .all(let header):
return Index(node: header.head!, id: header.head!.links[myID]!.id)
case .suffix(_, let start):
return Index(node: start, id: start.links[myID]!.id)
case .closedRange(_, let start, _):
return Index(node: start, id: start.links[myID]!.id)
case .regularRange(_, let start, _):
return Index(node: start, id: start.links[myID]!.id)
}
}
public subscript(position: Index) -> Element {
precondition(containsNode(position.node!))
return position.node!.payload
}
public subscript(bounds: Range<Index>) -> SinglyLinkedList {
guard !bounds.isEmpty else { return SinglyLinkedList(EmptyCollection()) }
var result = self
switch (bounds.lowerBound == startIndex, bounds.upperBound == endIndex) {
case (true, true):
break
case (false, true):
if let endIndexNode = endIndex.node {
result.nodes = .regularRange(for: header!, start: bounds.lowerBound.node!, upTo: endIndexNode)
} else {
result.nodes = .suffix(for: header!, from: bounds.lowerBound.node!)
}
case (_, false):
result.nodes = .regularRange(for: header!, start: bounds.lowerBound.node!, upTo: bounds.upperBound.node!)
}
return result
}
public func index(after i: Index) -> Index {
guard i != beforeStartIndex else { return startIndex }
let myID = header!.opaqueID
guard let nextNode = i.node!.links[myID]!.next else { return endIndex }
return Index(node: nextNode, id: nextNode.links[myID]!.id)
}
public var beforeStartIndex: Index {
guard let startingNode = startIndex.node else { return endIndex }
var nodeIterator = header!.makeNodeIterator()
guard var previous = nodeIterator.next(), previous !== startingNode else { return .beforeAnyOther }
while let current = nodeIterator.next() {
if current === startingNode {
break
} else {
previous = current
}
}
return Index(node: previous, id: previous.links[header!.opaqueID]!.id)
}
public init() {
self.init(EmptyCollection())
}
public mutating func trade(_ subrange: inout LeftOpenRange<Index>, with other: inout SinglyLinkedList, along otherSubrange: inout LeftOpenRange<Index>) {
let (replacementSelf, replacementSubrange) = SinglyLinkedList.stichList(withOutsideOf: self, excludedRange: subrange, andInsideOf: other, includedRange: otherSubrange)
let (replacementOther, replacementOthersubrange) = SinglyLinkedList.stichList(withOutsideOf: other, excludedRange: otherSubrange, andInsideOf: self, includedRange: subrange)
self = replacementSelf
subrange = replacementSubrange
other = replacementOther
otherSubrange = replacementOthersubrange
}
public mutating func replaceSubrange<C: Collection>(_ subrange: Range<Index>, with newElements: C) where C.Element == Element {
/// Finds the previous index.
func findPrevious(_ i: Index) -> Index {
if i == startIndex {
return beforeStartIndex
} else {
return indices.index(where: { index(after: $0) == i} )!
}
}
let shiftedLowerBound = findPrevious(subrange.lowerBound), shiftedUpperBound = findPrevious(subrange.upperBound)
var dummy = shiftedLowerBound >** shiftedUpperBound
var newList = SinglyLinkedList(newElements)
replaceSubrange(&dummy, byStealingFrom: &newList)
}
}
Raw
TransferableCollection.swift
//
// TransferableCollection.swift
// NodeCollections
//
// Created by Daryle Walker on 4/7/18.
// Copyright © 2018 Daryle Walker. All rights reserved.
//
// MARK: Primary Definition
/**
A collection that supports transfers, not just copies, of elements among instances, possibly in an insufficient manner.
The use of transfers implies that elements are individually encapsulated in (free-store) memory and are linked together with references to form sequences.
Transferable collections provide operations that move encapsulated elements, called nodes, from one instance to another. If instances can share nodes, then a transfer may affect both the source instance and **all** other instances that share the targeted nodes. (All the operations specified in this protocol transfer nodes; any node sharing between instances, like implementing `SubSequence` with `Self`, are up to the conforming type.)
`PoorlyTransferableCollection` types can model singly-linked lists. Said lists can easily support forward iterations and removal of immediately-following elements(s), but impose a O(n) search penalty on any operation that needs to look at elements before a given index. But Swift uses half-open ranges with included start points and excluded end points, so the penalty is triggered a lot. Avoiding this penalty is why the core interface uses `LeftOpenRange` ranges, which exclude start points but include end points.
Types conforming to `PoorlyTransferableCollection` and `BidirectionalCollection` can model doubly-linked lists. Since both of a node's neighbors are accessible, there is no O(n) penalty for operations that need to access elements before a targeted one. This new ease means such types gain overloads of range-based methods that work with Swift's normal range values. And single-index methods can work with targeted elements' indexes directly, instead of indexes of targets' backwards neighbors.
Conforming to the PoorlyTransferableCollection Protocol
=======================================================
To add `PoorlyTransferableCollection` conformance to your custom collection, add an empty initializer and at least the `trade(_:with:along:)` method to your custom type. (There is a default implementation for `tradeOver(_:_:)`.) Both `trade(_:with:along:)` and `tradeOver(_:_:)`, and any additional methods that may insert and/or remove elements, **must not** invalidate any indices of uninvolved elements.
Although it technically isn't proper to use `endIndex` as the upper bound of a non-empty sub-range (of a non-empty collection), it is permitted anyway to indicate a suffix range without having to compute the actual index of the last element.
*/
public protocol PoorlyTransferableCollection: PreflightedCollection where SubSequence: PoorlyTransferableCollection {
/**
Creates a new, empty collection.
- Postcondition: `isEmpty`.
*/
init()
/**
Exchanges the positions of the specified subranges of the collection.
Using the same value for both ranges has no effect. Using empty ranges for both arguments has no effect. Using exactly one empty range acts like a move.
If a non-empty range ends with `endIndex`, it will first be replaced with the index value of the last element. This may impose an O(n) search time for forward-only collections, though.
- Precondition: The two ranges must not overlap, unless they're identical. Non-identical ranges can abut, though.
- Parameter firstRange: A range of indexes for the first block to exchange. The bounds of the range must be valid for the collection.
- Parameter secondRange: A range of indexes for the second block to exchange. The bounds of the range must be valid for the collection.
- Postcondition:
- The elements for the first block are now where the second range's elements were.
- The elements for the second block are now where the first range's elements were.
- `firstRange` has been changed to demark the range for the second block's new location.
- `secondRange` has been changed to demark the range for the first block's new location.
*/
mutating func tradeOver(_ firstRange: inout LeftOpenRange<Index>, _ secondRange: inout LeftOpenRange<Index>)
/**
Exchanges ownership of the targeted elements between the receiver and the given collection.
Using empty ranges for both arguments has no effect. Using exactly one empty range acts like a move.
If a non-empty range ends with `endIndex`/`other.endIndex`, it will first be replaced with the index value of the corresponding last element. This may impose an O(n) search time for forward-only collections, though.
- Precondition: Besides `other` being distinct from `self`, the collections cannot share elements. (Sharing could happen if the collections have the same master collection for both their nodes. It's OK if the ranges merely abut in the master collection.)
- Parameter subrange: A range of indexes for the block in `self` that will be moved. The bounds of the range must be valid for `self`.
- Parameter other: The source of the elements inserted into `self`, and the destination for the elements removed from `self`.
- Parameter otherSubrange: A range of indexes for the block in `other` that will be moved. The bounds of the range must be valid for `other`.
- Postcondition:
- The elements demarked by `subrange` are now gone. The elements originally from `other` are there instead, and `subrange` has been adjusted to target those new elements.
- The elements demarked by `otherSubrange` are now gone from `other`. The elements originally from `self` are there instead, and `otherSubrange` has been adjusted to target those new-to-`other` elements.
*/
mutating func trade(_ subrange: inout LeftOpenRange<Index>, with other: inout Self, along otherSubrange: inout LeftOpenRange<Index>)
}
// MARK: Bi-directional Transferable Collections
/// A collection that supports transfers, not just copies, of elements among instances.
public typealias TransferableCollection = PoorlyTransferableCollection & BidirectionalCollection
// MARK: Default Implementations
extension PoorlyTransferableCollection {
public mutating func tradeOver(_ firstRange: inout LeftOpenRange<Index>, _ secondRange: inout LeftOpenRange<Index>) {
// If a non-empty range ends with endIndex, and we know the index of the last element, do adjustment.
switch (firstRange.lowerBound, firstRange.upperBound, secondRange.lowerBound, secondRange.upperBound) {
case (_, let fu, let sl, endIndex) where fu < endIndex && index(after: fu) == endIndex && sl != endIndex:
secondRange = secondRange.lowerBound >** fu
case (let fl, endIndex, _, let su) where fl != endIndex && su < endIndex && index(after: su) == endIndex:
firstRange = firstRange.lowerBound >** su
default:
break
}
guard firstRange != secondRange else { return }
guard !firstRange.isEmpty || !secondRange.isEmpty else { return }
precondition(!firstRange.overlaps(secondRange))
var intermediate = Self()
var intermediateRange = intermediate.beforeStartIndex >** intermediate.endIndex
trade(&firstRange, with: &intermediate, along: &intermediateRange)
trade(&secondRange, with: &intermediate, along: &intermediateRange)
trade(&firstRange, with: &intermediate, along: &intermediateRange)
assert(intermediate.isEmpty)
}
}
extension PoorlyTransferableCollection where Self: BidirectionalCollection {
public mutating func tradeOver(_ firstRange: inout LeftOpenRange<Index>, _ secondRange: inout LeftOpenRange<Index>) {
// If a non-empty range ends with endIndex, do adjustment.
if !firstRange.isEmpty, firstRange.upperBound == endIndex {
firstRange = firstRange.lowerBound >** index(before: firstRange.upperBound)
}
if !secondRange.isEmpty, secondRange.upperBound == endIndex {
secondRange = secondRange.lowerBound >** index(before: secondRange.upperBound)
}
guard firstRange != secondRange else { return }
guard !firstRange.isEmpty || !secondRange.isEmpty else { return }
precondition(!firstRange.overlaps(secondRange))
var intermediate = Self()
var intermediateRange = intermediate.beforeStartIndex >** intermediate.endIndex
trade(&firstRange, with: &intermediate, along: &intermediateRange)
trade(&secondRange, with: &intermediate, along: &intermediateRange)
trade(&firstRange, with: &intermediate, along: &intermediateRange)
assert(intermediate.isEmpty)
}
}
// MARK: Trading Elements in Bidirectional Collections
extension PoorlyTransferableCollection where Self: BidirectionalCollection {
/// Exchanges the positions of the specified subranges of the collection.
public mutating func tradeOver(_ firstRange: inout Range<Index>, _ secondRange: inout Range<Index>) {
var translatedFirstRange = convertFromRange(firstRange)
var translatedSecondRange = convertFromRange(secondRange)
tradeOver(&translatedFirstRange, &translatedSecondRange)
firstRange = convertToRegularRange(translatedFirstRange)
secondRange = convertToRegularRange(translatedSecondRange)
}
/// Exchanges ownership of the targeted elements between the receiver and the given collection.
public mutating func trade(_ subrange: inout Range<Index>, with other: inout Self, along otherSubrange: inout Range<Index>) {
var translatedSubrange = convertFromRange(subrange)
var translatedOtherSubrange = other.convertFromRange(otherSubrange)
trade(&translatedSubrange, with: &other, along: &translatedOtherSubrange)
subrange = convertToRegularRange(translatedSubrange)
otherSubrange = other.convertToRegularRange(translatedOtherSubrange)
}
}
// MARK: - Finding Elements
extension PoorlyTransferableCollection {
/// After a given start point, returns the index to the element before the first discovered element that satisfies the given predicate.
public func indexPriorToMatch(startingAfter i: Index, where predicate: (Element) throws -> Bool) rethrows -> Index? {
var prior = i
while let current = index(prior, offsetBy: +1, limitedBy: endIndex) {
if try predicate(self[current]) {
return prior
}
prior = current
}
return nil
}
/// Returns the index to the element before the first element that satisfies the given predicate.
public func indexPriorToMatch(where predicate: (Element) throws -> Bool) rethrows -> Index? {
return try indexPriorToMatch(startingAfter: beforeStartIndex, where: predicate)
}
}
extension PoorlyTransferableCollection where Element: Equatable {
/// After a given start point, returns the index to the element before the first discovered element that equals the specified value.
public func indexPriorToMatch(startingAfter i: Index, equaling element: Element) -> Index? {
return indexPriorToMatch(startingAfter: i, where: { $0 == element })
}
/// Returns the index to the element before the first element that equals the specified value.
public func indexPriorToMatch(equaling element: Element) -> Index? {
return indexPriorToMatch(where: { $0 == element })
}
}
// MARK: Members that Target All Elements
extension PoorlyTransferableCollection {
/// Exchanges every element between the receiver and the given collection, maintaining relative order.
public mutating func tradeAll(with other: inout Self) {
var allSelf = beforeStartIndex >** endIndex
tradeSubrange(&allSelf, withAllOf: &other)
}
/// Creates an instance by transferring all the elements from the given collection.
public init(stealFrom other: inout Self) {
self.init()
tradeAll(with: &other)
}
/// Removes all elements from the collection.
public mutating func removeAll() {
_ = Self(stealFrom: &self)
}
/// Creates an instance by merging the elements of two other instances, with admission order controlled by a closure.
public init(stealFromAndMerge first: inout Self, and second: inout Self, admittingFirstOverSecondBy body: (Element, Element) throws -> Bool) rethrows {
// Determine the order of insertion.
var firstIndex = first.startIndex, secondIndex = second.startIndex
var chooseFirst = [Bool]()
chooseFirst.reserveCapacity(first.underestimatedCount + second.underestimatedCount)
while firstIndex != first.endIndex, secondIndex != second.endIndex {
let goWithFirst = try body(first[firstIndex], second[secondIndex])
chooseFirst.append(goWithFirst)
if goWithFirst {
first.formIndex(after: &firstIndex)
} else {
second.formIndex(after: &secondIndex)
}
}
// Do the transfers.
self.init()
chooseFirst.forEach {
var endSelf = endIndex >** endIndex
var otherRange: LeftOpenRange<Index>
if $0 {
otherRange = first.beforeStartIndex >** first.startIndex
trade(&endSelf, with: &first, along: &otherRange)
} else {
otherRange = second.beforeStartIndex >** second.startIndex
trade(&endSelf, with: &second, along: &otherRange)
}
}
append(stealingFrom: &first)
append(stealingFrom: &second)
}
}
extension PoorlyTransferableCollection where Element: Comparable {
/// Creates an instance by merging the elements of two other instances, with a non-decreasing prefix.
public init(stealFromAndMergeWithNondecreasingPrefix first: inout Self, and second: inout Self) {
// For some reaason, if an initializer calls another, and that other initializer takes a possibly-
// throwing closure, the first initializer thinks the second UNCONDITIONALLY throws, and thus
// requires "try" management. (The second initializer throws only if its closure does.)
// Bug: SR-7392 ("Initializer incorrectly marked as 'throwing'") <https://bugs.swift.org/browse/SR-7392>
try! self.init(stealFromAndMerge: &first, and: &second, admittingFirstOverSecondBy: <)
// TODO: Remove the "try!" once Bug SR-7392 is fixed.
}
}
// MARK: Transferring Elements
extension PoorlyTransferableCollection {
/// Exchanges all the elements of the specified collection with the specified sub-range of the receiver.
public mutating func tradeSubrange(_ subrange: inout LeftOpenRange<Index>, withAllOf other: inout Self) {
var allOther = other.beforeStartIndex >** other.endIndex
trade(&subrange, with: &other, along: &allOther)
}
/// Transfers all the elements of the specified collection to replace the specified element sub-range of the receiver.
public mutating func replaceSubrange(_ subrange: inout LeftOpenRange<Index>, byStealingFrom other: inout Self) {
tradeSubrange(&subrange, withAllOf: &other)
other.removeAll()
}
/// Transfers all the elements of the specified collection to the end of the receiver.
public mutating func append(stealingFrom other: inout Self) {
insert(after: endIndex, stealingFrom: &other)
}
/// Transfers all the elements of the specified collection to the receiver after the specified element.
public mutating func insert(after i: Index, stealingFrom other: inout Self) {
var range = i >** i
replaceSubrange(&range, byStealingFrom: &other)
}
/// Transfers all the nodes of the specified collection to the beginning of the receiver.
public mutating func prepend(stealingFrom other: inout Self) {
insert(after: beforeStartIndex, stealingFrom: &other)
}
/// Transfers the specified elements out of the receiver and into a new instance.
@discardableResult
public mutating func removeSubrange(_ subrange: LeftOpenRange<Index>) -> Self {
var result = Self()
var mutableSubrange = subrange
tradeSubrange(&mutableSubrange, withAllOf: &result)
return result
}
/// Transfers the element after the specified position to a new instance.
@discardableResult
public mutating func remove(after i: Index) -> Self {
return removeSubrange(i >** index(after: i))
}
/// Transfers the initial elements of the receiver to a new instance.
@discardableResult
public mutating func removeFirst(upThrough i: Index) -> Self {
return removeSubrange(beforeStartIndex >** i)
}
/// Transfers the final elements of the receiver to a new instance.
@discardableResult
public mutating func removeLast(after i: Index) -> Self {
return removeSubrange(i >** endIndex)
}
/// Transfers all elements satisfying the given predicate out of the receiver and into a new instance.
@discardableResult
public mutating func removeAll(where predicate: (Element) throws -> Bool) rethrows -> Self {
// Find all qualifying elements.
var prior = beforeStartIndex
var allPriors = [Index]()
allPriors.reserveCapacity(underestimatedCount)
while let current = try indexPriorToMatch(startingAfter: prior, where: predicate) {
allPriors.append(prior)
prior = current
}
// Extract said elements.
var result = Self()
for i in allPriors.reversed() {
var lastQualified = remove(after: i)
result.prepend(stealingFrom: &lastQualified)
}
return result
}
/// Transfers out a suffix such that the remaining elements are strictly stored according to the given predicate.
@discardableResult
public mutating func removeAfterMissort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
var lastIncluded = startIndex
for i in indices.dropFirst() {
if try !areInIncreasingOrder(self[lastIncluded], self[i]) {
return removeLast(after: lastIncluded)
}
lastIncluded = i
}
return nil
}
}
extension PoorlyTransferableCollection where Element: Equatable {
/// Transfers all elements that equal the specified value to a new instance.
@discardableResult
public mutating func removeAll(thatEqual element: Element) -> Self {
return removeAll(where: { $0 == element })
}
}
extension PoorlyTransferableCollection where Element: Comparable {
/// Transfers the elements after where the collection first stops increasing to a new instance.
@discardableResult
public mutating func removeNonincreasingSuffix() -> Self? {
return removeAfterMissort(by: <)
}
}
extension PoorlyTransferableCollection where Self: BidirectionalCollection {
/// Convert a helf-closed range to a half-open range.
private func convertToRegularRange(_ r: LeftOpenRange<Index>) -> Range<Index> {
if r.lowerBound == endIndex {
assert(r.upperBound == endIndex)
return r.lowerBound ..< r.upperBound
} else if r.upperBound == endIndex {
return index(after: r.lowerBound) ..< r.upperBound
} else {
return index(after: r.lowerBound) ..< index(after: r.upperBound)
}
}
/// Convert a range to a half-closed range.
private func convertFromRange<R: RangeExpression>(_ r: R) -> LeftOpenRange<Index> where R.Bound == Index {
let rr = r.relative(to: self)
return index(before: rr.lowerBound) >** index(before: rr.upperBound)
}
/// Exchanges all the elements of the specified collection with the specified sub-range of the receiver.
public mutating func tradeSubrange(_ subrange: inout Range<Index>, withAllOf other: inout Self) {
var translatedSubrange = convertFromRange(subrange)
tradeSubrange(&translatedSubrange, withAllOf: &other)
subrange = convertToRegularRange(translatedSubrange)
}
/// Transfers all the elements of the specified collection to replace the specified element sub-range of the receiver.
public mutating func replaceSubrange(_ subrange: inout Range<Index>, byStealingFrom other: inout Self) {
tradeSubrange(&subrange, withAllOf: &other)
other.removeAll()
}
/// Transfers all the elements of the specified collection to the receiver before the specified element.
public mutating func insert(at i: Index, stealingFrom other: inout Self) {
insert(after: index(before: i), stealingFrom: &other)
}
/// Transfers the specified elements out of the receiver and into a new instance.
@discardableResult
public mutating func removeSubrange<R: RangeExpression>(_ subrange: R) -> Self where R.Bound == Index {
return removeSubrange(convertFromRange(subrange))
}
/// Transfers the element at the specified position to a new instance.
@discardableResult
public mutating func remove(at i: Index) -> Self {
return remove(after: index(before: i))
}
/// Transfers the initial elements of the receiver to a new instance.
@discardableResult
public mutating func removeFirst(upTo i: Index) -> Self {
return removeFirst(upThrough: index(before: i))
}
/// Transfers the final elements of the receiver to a new instance.
@discardableResult
public mutating func removeLast(from i: Index) -> Self {
return removeLast(after: index(before: i))
}
}
// MARK: Shuffling Elements
extension PoorlyTransferableCollection {
/// Rearranges the elements of the collection such that all elements that match the given predicate are after all the elements that don't match.
public mutating func arrangePartitioning(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> LeftOpenRange<Index> {
var matchingElements = try removeAll(where: belongsInSecondPartition)
var endOfFirstPartition = endIndex >** endIndex
tradeSubrange(&endOfFirstPartition, withAllOf: &matchingElements)
return endOfFirstPartition
}
/// Arranges the elements into reverse order.
public mutating func reverse() {
var scratch = Self()
while startIndex != endIndex {
var firstOfSelf = beforeStartIndex >** startIndex
var beginningOfScratch = scratch.beforeStartIndex >** scratch.beforeStartIndex
trade(&firstOfSelf, with: &scratch, along: &beginningOfScratch)
}
assert(isEmpty)
tradeAll(with: &scratch)
}
/// Sorts the collection in place via element-shuffling, using the given predicate as the comparison between elements.
public mutating func mergeSort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
// Do natural merge sort, checking if this instance is already sorted.
guard var missortedSuffix = try removeAfterMissort(by: areInIncreasingOrder) else { return }
// Undo the truncation if later steps throw. Or uselessly append an emptied intermediary upon success.
defer { append(stealingFrom: &missortedSuffix) }
// Recursively sort.
try missortedSuffix.mergeSort(by: areInIncreasingOrder)
// Merge. Using the suffix collection as the first argument should make equivalent operands choose the element from this instance first.
var sorted = try Self(stealFromAndMerge: &missortedSuffix, and: &self, admittingFirstOverSecondBy: areInIncreasingOrder)
tradeAll(with: &sorted)
}
/// Exchanges the elements at the locations immediately following the specified indices of the collection.
public mutating func swapElements(following i: Index, and j: Index) {
var iRange = i>**index(after: i), jRange = j>**index(after: j)
tradeOver(&iRange, &jRange)
}
}
extension PoorlyTransferableCollection where Element: Equatable {
/// Rearranges the elements that equal the specified value to be after all the others in the collection.
public mutating func arrangePartitioning(withBackstop element: Element) -> LeftOpenRange<Index> {
return arrangePartitioning(by: { $0 == element })
}
}
extension PoorlyTransferableCollection where Element: Comparable {
/// Sorts the collection in place via element-shuffling.
public mutating func mergeSort() {
mergeSort(by: <)
}
}
extension PoorlyTransferableCollection where Self: BidirectionalCollection {
/// Arranges the elements into reverse order.
public mutating func reverse() {
var beforeEarliest = beforeStartIndex
guard var beforeLatest = index(endIndex, offsetBy: -2, limitedBy: beforeStartIndex) else { return }
while beforeEarliest < beforeLatest {
swapElements(following: beforeEarliest, and: beforeLatest)
formIndex(after: &beforeEarliest)
formIndex(before: &beforeLatest)
}
}
/// Exchanges the elements at the specified indices of the collection.
public mutating func swapElements(at i: Index, and j: Index) {
swapElements(following: index(before: i), and: index(before: j))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment