如何在本机Swift中实现以前称为NSMutableOrderedSet的Mutable Ordered Set泛型类型? [英] How to implement a Mutable Ordered Set generic type formerly known as NSMutableOrderedSet in native Swift?
问题描述
我正在尝试实现通用的Mutable Ordered Set类型，它需要符合许多协议才能以与Array和Set在Swift中相同的方式运行.首先要实现通用类型元素需要符合 Hashable 和通用结构需要符合 RandomAccessCollection ， ExpressibleByArrayLiteral ， AdditiveArithmetic ， RangeReplaceableCollection 和
I am trying to implement a generic Mutable Ordered Set type and it needs to conform to many protocols to behave the same way as an Array and a Set does in Swift. First of all to accomplish that the generic type element needs to conform to Hashable and the generic struct needs to conform to RandomAccessCollection, SetAlgebra, ExpressibleByArrayLiteral,AdditiveArithmetic, RangeReplaceableCollection and MutableCollection. I would like also to allow subscript access to its SubSequence adding support to PartialRangeThrough, PartialRangeUpTo, PartialRangeFrom and UnboundedRange as well.
这是我的通用OrderedSet结构声明:
This is my generic OrderedSet struct declaration:
public struct OrderedSet<Element: Hashable> {
public init() { }
private var elements: [Element] = []
private var set: Set<Element> = []
}
即使这是一个自我解答的问题，我也将非常感谢并鼓励提出新的答案，但对此实现也有一些反馈意见，并且/或者还提出了有关如何解决/改进它的建议:
Even though this is a self-answered question I would really appreciate and encourage new answers, some feedback on this implementation and/or suggestions on how to fix/improve it as well:
编辑/更新:
sorted方法可以按预期工作，但变异的sort甚至都没有改变元素顺序.
The sorted method works as expected but the mutating sort it is not even changing the elements order.
MutableCollection
声明变更
func sort()
func sort()
当Self符合RandomAccessCollection并且Element符合Comparable时可用.
Available when Self conforms to RandomAccessCollection and Element conforms to Comparable.
var numbers: OrderedSet = [15, 40, 10, 30, 60, 25, 5, 100]
numbers[0..<4] // [15, 40, 10, 30]
numbers[0..<4].sorted() // [10, 15, 30, 40]
numbers[0..<4].sort() // [15, 40, 10, 30, 60, 25, 5, 100]
print(numbers)
// Prints "[15, 40, 10, 30, 60, 25, 5, 100]"
// But it should print "[10, 15, 30, 40, 60, 25, 5, 100]"
我该如何解决?
推荐答案
可变排序集的本机Swift实现:
A native Swift implementation of a Mutable Ordered Set:
public protocol OrderedSetProtocol: MutableCollection,
RandomAccessCollection,
SetAlgebra,
AdditiveArithmetic,
RangeReplaceableCollection
where Element: Hashable, Index == Int { }
public struct OrderedSet<Element: Hashable>: OrderedSetProtocol {
public init() { }
private var elements: [Element] = []
private var set: Set<Element> = []
}
符合MutableCollection协议
要将对MutableCollection协议的一致性添加到您自己的自定义集合中，请升级您的 类型的下标以支持读取和写入访问.存储的值 插入MutableCollection实例的下标必须随后是 在同一位置可以访问.也就是说，对于可变的集合 实例a，索引i和值x，即 以下代码示例必须等效:
To add conformance to the MutableCollection protocol to your own custom collection, upgrade your type’s subscript to support both read and write access. A value stored into a subscript of a MutableCollection instance must subsequently be accessible at that same position. That is, for a mutable collection instance a, index i, and value x, the two sets of assignments in the following code sample must be equivalent:
extension OrderedSet: MutableCollection {
public subscript(index: Index) -> Element {
get { elements[index] }
set {
guard set.update(with: newValue) == nil else {
//
// needs some implementation before returning
// insert(remove(at: elements.firstIndex(of: newValue)!), at: index)
//
return
}
elements[index] = newValue
}
}
}
符合RandomAccessCollection协议
RandomAccessCollection协议在 关联的索引和子序列类型，但不强加 BidirectionalCollection协议上的其他要求. 但是，为了满足复杂性，保证了随机访问 集合中，您的自定义类型的索引必须符合 可跨越的协议，或者您必须实现index(_:offsetBy :)和 效率为O(1)的distance(from:to :)方法.
The RandomAccessCollection protocol adds further constraints on the associated Indices and SubSequence types, but otherwise imposes no additional requirements over the BidirectionalCollection protocol. However, in order to meet the complexity guarantees of a random-access collection, either the index for your custom type must conform to the Strideable protocol or you must implement the index(_:offsetBy:) and distance(from:to:) methods with O(1) efficiency.
extension OrderedSet: RandomAccessCollection {
public typealias Index = Int
public typealias Indices = Range<Int>
public typealias SubSequence = Slice<OrderedSet<Element>>
public typealias Iterator = IndexingIterator<Self>
// Generic subscript to support `PartialRangeThrough`, `PartialRangeUpTo`, `PartialRangeFrom`
public subscript<R: RangeExpression>(range: R) -> SubSequence where Index == R.Bound { .init(base: self, bounds: range.relative(to: self)) }
public var endIndex: Index { elements.endIndex }
public var startIndex: Index { elements.startIndex }
public func formIndex(after i: inout Index) { elements.formIndex(after: &i) }
public var isEmpty: Bool { elements.isEmpty }
@discardableResult
public mutating func append(_ newElement: Element) -> Bool { insert(newElement).inserted }
}
符合SetAlgebra协议
在实现符合SetAlgebra协议的自定义类型时，您必须实现 必需的初始化程序和方法.为了使继承的方法起作用 正确地，符合类型必须符合以下公理.假使，假设 S是符合SetAlgebra协议x和y的自定义类型 是S的实例，e是S.Element类型-集的类型 保持.
When implementing a custom type that conforms to the SetAlgebra protocol, you must implement the required initializers and methods. For the inherited methods to work properly, conforming types must meet the following axioms. Assume that S is a custom type that conforms to the SetAlgebra protocol, x and y are instances of S, and e is of type S.Element—the type that the set holds.
S()== []
x.intersection(x)== x
x.intersection(x) == x
x.intersection([])== []
x.intersection([ ]) == [ ]
x.union(x)== x
x.union(x) == x
x.union([])== x x.contains(e)暗含 x.union(y).contains(e)
x.union([ ]) == x x.contains(e) implies x.union(y).contains(e)
x.union(y).contains(e)暗含x.contains(e)|| y.contains(e)
x.union(y).contains(e) implies x.contains(e) || y.contains(e)
x.contains(e)&& y.包含且仅当 x.intersection(y).contains(e)
x.contains(e) && y.contains(e) if and only if x.intersection(y).contains(e)
x.isSubset(of:y)意味着x.union(y)== y
x.isSubset(of: y) implies x.union(y) == y
x.isSuperset(of:y)意味着x.union(y)== x
x.isSuperset(of: y) implies x.union(y) == x
x.isSubset(of:y)如果和 仅当y.isSuperset(of:x)
x.isSubset(of: y) if and only if y.isSuperset(of: x)
x.isStrictSuperset(of:y)当且仅当 x.isSuperset(of:y)&& x！= y
x.isStrictSuperset(of: y) if and only if x.isSuperset(of: y) && x != y
x.isStrictSubset(of:y)当且仅当 x.isSubset(of:y)&& x！= y
x.isStrictSubset(of: y) if and only if x.isSubset(of: y) && x != y
extension OrderedSet: SetAlgebra {
public mutating func insert(_ newMember: Element) -> (inserted: Bool, memberAfterInsert: Element) {
let insertion = set.insert(newMember)
if insertion.inserted { elements.append(newMember) }
return insertion
}
public mutating func remove(_ member: Element) -> Element? {
if let index = elements.firstIndex(of: member) {
elements.remove(at: index)
return set.remove(member)
}
return nil
}
public mutating func update(with newMember: Element) -> Element? {
if let index = elements.firstIndex(of: newMember) {
elements[index] = newMember
return set.update(with: newMember)
} else {
elements.append(newMember)
set.insert(newMember)
return nil
}
}
public func union(_ other: Self) -> Self {
var orderedSet = self
orderedSet.formUnion(other)
return orderedSet
}
public func intersection(_ other: Self) -> Self { filter(other.contains) }
public func symmetricDifference(_ other: Self) -> Self { filter { !other.set.contains($0) } + other.filter { !set.contains($0) } }
public mutating func formUnion(_ other: Self) { other.forEach { self.append($0) } }
public mutating func formIntersection(_ other: Self) { self = intersection(other) }
public mutating func formSymmetricDifference(_ other: Self) { self = symmetricDifference(other) }
}
符合ExpressibleByArrayLiteral
将要使用数组文字初始化的功能添加到您自己的功能中 通过声明init(arrayLiteral :)初始化程序来定制类型.这 以下示例显示了一个数组的数组文字初始值设定项 假设的OrderedSet类型，具有类似setset的语义，但 保持其元素的顺序.
Add the capability to be initialized with an array literal to your own custom types by declaring an init(arrayLiteral:) initializer. The following example shows the array literal initializer for a hypothetical OrderedSet type, which has setlike semantics but maintains the order of its elements.
extension OrderedSet: ExpressibleByArrayLiteral {
public typealias ArrayLiteralElement = Element
public init(arrayLiteral: Element...) {
self.init()
for element in arrayLiteral {
self.append(element)
}
}
}
符合AdditiveArithmetic协议
要将AdditiveArithmetic协议符合性添加到您自己的自定义类型中， 实现所需的运算符，并提供静态零属性 使用可以代表您任何值的大小的类型 自定义类型.
To add AdditiveArithmetic protocol conformance to your own custom type, implement the required operators, and provide a static zero property using a type that can represent the magnitude of any value of your custom type.
extension OrderedSet: AdditiveArithmetic {
public static var zero: Self { .init() }
public static func + (lhs: Self, rhs: Self) -> Self { lhs.union(rhs) }
public static func - (lhs: Self, rhs: Self) -> Self { lhs.subtracting(rhs) }
public static func += (lhs: inout Self, rhs: Self) { lhs.formUnion(rhs) }
public static func -= (lhs: inout Self, rhs: Self) { lhs.subtract(rhs) }
}
符合RangeReplaceableCollection协议
要将RangeReplaceableCollection一致性添加到您的自定义集合中，请添加 一个空的初始化程序和您的replaceSubrange(:with :)方法 自定义类型. RangeReplaceableCollection提供默认值 使用此初始化程序的所有其他方法的实现，以及 方法.例如，removeSubrange( :)方法是通过以下方式实现的 调用replaceSubrange(_:with :)的空集合 newElements参数.您可以覆盖协议中的任何必需条件 提供您自己的自定义实现的方法.
To add RangeReplaceableCollection conformance to your custom collection, add an empty initializer and the replaceSubrange(:with:) method to your custom type. RangeReplaceableCollection provides default implementations of all its other methods using this initializer and method. For example, the removeSubrange(:) method is implemented by calling replaceSubrange(_:with:) with an empty collection for the newElements parameter. You can override any of the protocol’s required methods to provide your own custom implementation.
extension OrderedSet: RangeReplaceableCollection {
public init<S: Sequence>(_ elements: S) where S.Element == Element {
elements.forEach { set.insert($0).inserted ? self.elements.append($0) : () }
}
mutating public func replaceSubrange<C: Collection, R: RangeExpression>(_ subrange: R, with newElements: C) where Element == C.Element, C.Element: Hashable, Index == R.Bound {
elements[subrange].forEach { set.remove($0) }
elements.removeSubrange(subrange)
var index = subrange.relative(to: self).lowerBound
newElements.forEach {
if set.insert($0).inserted {
elements.insert($0, at: index)
formIndex(after: &index)
}
}
}
符合CustomStringConvertible协议
通过以下方式向您的自定义类型添加CustomStringConvertible符合性 定义描述属性.
Add CustomStringConvertible conformance to your custom types by defining a description property.
extension OrderedSet: CustomStringConvertible {
public var description: String { .init(describing: elements) }
}
也将其Slice调整为CustomStringConvertible:
Conforming its Slice to CustomStringConvertible as well:
extension Slice: CustomStringConvertible where Base: OrderedSetProtocol {
public var description: String {
var description = "["
var first = true
for element in self {
if first {
first = false
} else {
description += ", "
}
debugPrint(element, terminator: "", to: &description)
}
return description + "]"
}
}
快速游乐场测试(OrderedSet应该具有Swift本机Array和Set结构可用的所有方法)
Quick Playground Test (OrderedSet should have all methods that are available to Swift native Array and Set structures)
var ordereSet1: OrderedSet = [1,2,3,4,5,6,1,2,3] // [1, 2, 3, 4, 5, 6]
var ordereSet2: OrderedSet = [4,5,6,7,8,9,7,8,9] // [4, 5, 6, 7, 8, 9]
ordereSet1 == ordereSet2 // false
ordereSet1.union(ordereSet2) // [1, 2, 3, 4, 5, 6, 7, 8, 9]
ordereSet1.intersection(ordereSet2) // [4, 5, 6]
ordereSet1.symmetricDifference(ordereSet2) // [1, 2, 3, 7, 8, 9]
ordereSet1.subtract(ordereSet2) // [1, 2, 3]
ordereSet1.insert(contentsOf: [1,3,4,6], at: 0) // [4, 6, 1, 2, 3]
ordereSet2.popLast() // 9
这篇关于如何在本机Swift中实现以前称为NSMutableOrderedSet的Mutable Ordered Set泛型类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
