Как реализовать универсальный тип Mutable Ordered Set, ранее известный как NSMutableOrderedSet, в собственном Swift?
Я пытаюсь реализовать универсальный тип Mutable Ordered Set, и он должен соответствовать многим протоколам, чтобы вести себя так же, как Array и Set в Swift. Прежде всего для того, чтобы элемент универсального типа соответствовал Hashable и общая структура должна соответствовать RandomAccessCollection, SetAlgebra, ExpressibleByArrayLiteral,AdditiveArithmetic, RangeReplaceableCollection а также MutableCollection. Я также хотел бы разрешить доступ по индексу к егоSubSequence добавление поддержки PartialRangeThrough, PartialRangeUpTo, PartialRangeFrom а также UnboundedRange также.
Это мой общий OrderedSet объявление структуры:
public struct OrderedSet<Element: Hashable> {
public init() { }
private var elements: [Element] = []
private var set: Set<Element> = []
}
Несмотря на то, что это вопрос, на который я ответил сам, я был бы очень признателен и поощрял бы новые ответы, некоторые отзывы об этой реализации и / или предложения о том, как исправить / улучшить ее:
изменить / обновить:
В sorted метод работает, как ожидалось, но изменяющийся sort это даже не изменение порядка элементов.
MutableCollection
Изменение объявления
func sort()
Доступно, если Self соответствует RandomAccessCollection, а Element соответствует 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]"
Как я могу это исправить?
2 ответа
Собственная реализация изменяемого упорядоченного набора на Swift:
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 два набора назначений в следующем примере кода должны быть эквивалентными:
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. Однако, чтобы соответствовать гарантиям сложности коллекции с произвольным доступом, либо индекс для вашего настраиваемого типа должен соответствовать протоколу Strideable, либо вы должны реализовать методы index(_:offsetBy:) и distance(from:to:) с эффективностью O(1).
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 - тип, который содержит набор.
S() == []
x.intersection(x) == x
x.intersection([]) == []
x.union(x) == x
x.union([]) == x x.contains(e) подразумевает x.union(y).contains(e)
x.union(y).contains(e) подразумевает x.contains(e) || y.contains(e)
x.contains(e) && y.contains(e) тогда и только тогда, когда x.intersection(y).contains(e)
x.isSubset(of: y) подразумевает x.union(y) == y
x.isSuperset(of: y) подразумевает x.union(y) == x
x.isSubset(of: y) тогда и только тогда, когда y.isSuperset(of: x)
x.isStrictSuperset(of: y) тогда и только тогда, когда x.isSuperset(of: y) && x! = y
x.isStrictSubset (of: y) тогда и только тогда, когда 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, который имеет семантику, подобную множеству, но поддерживает порядок своих элементов.
extension OrderedSet: ExpressibleByArrayLiteral {
public typealias ArrayLiteralElement = Element
public init(arrayLiteral: Element...) {
self.init()
for element in arrayLiteral {
self.append(element)
}
}
}
Соответствие протоколу AdditiveArithmetic
Чтобы добавить соответствие протокола AdditiveArithmetic вашему собственному настраиваемому типу, реализуйте необходимые операторы и предоставьте свойство статического нуля с использованием типа, который может представлять величину любого значения вашего настраиваемого типа.
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. Вы можете переопределить любой из требуемых методов протокола, чтобы предоставить свою собственную реализацию.
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 вашим настраиваемым типам, определив свойство description.
extension OrderedSet: CustomStringConvertible {
public var description: String { .init(describing: elements) }
}
В соответствии с ее Slice к CustomStringConvertible также:
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 конструкции)
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
Проблема 1: Изготовление OrderedSet а MutableCollection
В MutableCollectionвы можете изменить отдельный элемент (или часть элементов) с помощью индекса, который поддерживает доступ для записи. И вот здесь начинаются проблемы: что должен выводить
var oset: OrderedSet = [1, 2, 3, 4]
oset[0] = 3
print(oset)
быть? Мы не можем просто заменить первый элемент, потому что тогда члены набора больше не уникальны. Ваша текущая реализация возвращается[1, 2, 3, 4], т.е. он отклоняет настройку, если новый член уже присутствует в наборе.
Это делает многие реализации по умолчанию MutableCollection методы не работают: sort(), swapAt(), shuffle() и, возможно, еще:
var oset: OrderedSet = [4, 3, 2, 1]
oset.swapAt(0, 2)
print(oset) // [4, 3, 2, 1]
oset.sort()
print(oset) // [4, 3, 2, 1]
oset.shuffle()
print(oset) // [4, 3, 2, 1]
Проблема 2: нарезка
В своей реализации вы выбрали Slice<OrderedSet<Element>> как SubSequence тип. Slice использует хранилище из исходной (базовой) коллекции и поддерживает только свою собственную startIndex а также endIndex. Это приводит к неожиданным результатам:
let oset: OrderedSet = [1, 2, 3, 4, 5]
var oslice = oset[0..<3]
oslice[0] = 5
print(oslice) // [1, 2, 3]
Настройка oslice[0]отклоняется, поскольку исходный набор содержит новый член. Это, конечно, не ожидается. Сортировка ломтика
var oset: OrderedSet = [6, 5, 4, 3, 2, 1]
oset[0..<4].sort()
print(oset) // [6, 5, 4, 3, 2, 1]
терпит неудачу, потому что отсортированные элементы записываются обратно один за другим, и это терпит неудачу, потому что члены уже присутствуют в наборе. То же самое происходит с назначением среза:
var o1: OrderedSet = [1, 2]
let o2: OrderedSet = [2, 1]
o1[0..<2] = o2[0..<2]
print(o1) // [1, 2]
Другая проблема в том, что срез oset[0..<3] не соответствует OrderedSetProtocol: Это (изменяемая) коллекция, но, например, не SetAlgebra, поэтому его нельзя использовать для образования объединений, пересечений или симметричных различий.
Вам действительно нужен MutableCollection соответствие?
Я бы серьезно подумал о том, чтобы не приниматьMutableCollectionпротокол. Это не делает упорядоченный набор неизменяемым: это означает только то, что отдельные члены не могут быть изменены с помощью установщика нижнего индекса. Вы по-прежнему можете вставлять или удалять элементы, а также образовывать объединения или пересечения с другими наборами. Только для "сложных" операций, таких как сортировка, вы должны использовать дополнительный временный набор:
var oset: OrderedSet = [4, 3, 2, 1]
oset = OrderedSet(oset.sorted())
print(oset) // [1, 2, 3, 4]
Большим преимуществом является то, что больше нет нечеткого поведения.
Да я хочу MutableCollection соответствие!
Хорошо, вы просили об этом - давайте посмотрим, что мы можем сделать. Мы могли бы попытаться исправить это, "зафиксировав" установщик нижнего индекса. Одна попытка - это ваш закомментированный код:
set {
guard set.update(with: newValue) == nil else {
insert(remove(at: elements.firstIndex(of: newValue)!), at: index)
return
}
elements[index] = newValue
}
Это приводит к перемещению существующего элемента в указанное место, смещению других элементов:
var oset: OrderedSet = [1, 2, 3, 4]
oset[0] = 3
print(oset) // [3, 1, 2, 4]
Это, кажется, чтобы сделать большинство методов работы правильно:
var oset: OrderedSet = [4, 3, 2, 1]
oset.swapAt(0, 2)
print(oset) // [2, 3, 4, 1]
oset.sort()
print(oset) // [1, 2, 3, 4]
oset.shuffle()
print(oset) // [1, 4, 3, 2]
и даже сортировка по индексу:
var oset: OrderedSet = [6, 5, 4, 3, 2, 1]
oset[0..<4].sort()
print(oset) // [3, 4, 5, 6, 2, 1]
Но вижу два недостатка:
- Пользователь может не ожидать этого побочного эффекта установщика нижнего индекса.
- Это нарушает требуемое соответствие O(1) установщика нижнего индекса.
Другой вариант - оставить средство установки индекса как есть (т.е. отклонить недопустимые настройки) и реализовать проблемные методы вместо использования реализаций по умолчанию дляMutableCollection:
extension OrderedSet {
public mutating func swapAt(_ i: Index, _ j: Index) {
elements.swapAt(i, j)
}
public mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
try elements.partition(by: belongsInSecondPartition)
}
public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
try elements.sort(by: areInIncreasingOrder)
}
}
extension OrderedSet where Element : Comparable {
public mutating func sort() {
elements.sort()
}
}
Кроме того, нам нужно реализовать установщик индекса, принимающий диапазон
public subscript(bounds: Range<Index>) -> SubSequence
так что отсортированный фрагмент снова назначается набору как одна операция, а не каждому элементу по отдельности.
В моих тестах это сработало, но есть риск, что я что-то упустил.
И для нарезки я бы сделал OrderedSet свой собственный SubSequenceтип. Это означает, что элементы дублируются. Этого можно было избежать, сделавelement хранение и ArraySlice но - как мы видели выше - set различных членов должны быть продублированы в любом случае, чтобы избежать нежелательных побочных эффектов при мутации исходного набора.
Код
Это то, что у меня есть. Насколько я могу судить, он работает правильно, но требует дополнительного тестирования.
Обратите внимание, что некоторые методы не нужно реализовывать, например ExpressibleByArrayLiteral уже имеет реализацию по умолчанию в SetAlgebra, и различные вычисления индекса имеют реализации по умолчанию, потому что Index является Strideable.
public struct OrderedSet<Element: Hashable> {
private var elements: [Element] = []
private var set: Set<Element> = []
public init() { }
}
extension OrderedSet {
public init<S>(distinctElements elements: S) where S : Sequence, S.Element == Element {
self.elements = Array(elements)
self.set = Set(elements)
precondition(self.elements.count == self.set.count, "Elements must be distinct")
}
}
extension OrderedSet: SetAlgebra {
public func contains(_ member: Element) -> Bool {
set.contains(member)
}
@discardableResult public mutating func insert(_ newMember: Element) -> (inserted: Bool, memberAfterInsert: Element) {
let insertion = set.insert(newMember)
if insertion.inserted { elements.append(newMember) }
return insertion
}
@discardableResult public mutating func remove(_ member: Element) -> Element? {
if let oldMember = set.remove(member) {
let index = elements.firstIndex(of: member)!
elements.remove(at: index)
return oldMember
} else {
return nil
}
}
@discardableResult public mutating func update(with newMember: Element) -> Element? {
if let member = set.update(with: newMember) {
return member
} else {
elements.append(newMember)
return nil
}
}
public mutating func formUnion(_ other: Self) {
other.elements.forEach { self.insert($0) }
}
public mutating func formIntersection(_ other: Self) {
for element in elements {
if !other.contains(element) {
remove(element)
}
}
}
public mutating func formSymmetricDifference(_ other: Self) {
for member in other.elements {
if set.contains(member) {
remove(member)
} else {
insert(member)
}
}
}
public func union(_ other: Self) -> Self {
var orderedSet = self
orderedSet.formUnion(other)
return orderedSet
}
public func intersection(_ other: Self) -> Self {
var orderedSet = self
orderedSet.formIntersection(other)
return orderedSet
}
public func symmetricDifference(_ other: Self) -> Self {
var orderedSet = self
orderedSet.formSymmetricDifference(other)
return orderedSet
}
public init<S>(_ elements: S) where S : Sequence, S.Element == Element {
elements.forEach { insert($0) }
}
}
extension OrderedSet: CustomStringConvertible {
public var description: String { elements.description }
}
extension OrderedSet: MutableCollection, RandomAccessCollection {
public typealias Index = Int
public typealias SubSequence = OrderedSet
public subscript(index: Index) -> Element {
get {
elements[index]
}
set {
if !set.contains(newValue) || elements[index] == newValue {
set.remove(elements[index])
set.insert(newValue)
elements[index] = newValue
}
}
}
public subscript(bounds: Range<Index>) -> SubSequence {
get {
return OrderedSet(distinctElements: elements[bounds])
}
set {
replaceSubrange(bounds, with: newValue.elements)
}
}
public var startIndex: Index { elements.startIndex}
public var endIndex: Index { elements.endIndex }
public var isEmpty: Bool { elements.isEmpty }
}
extension OrderedSet {
public mutating func swapAt(_ i: Index, _ j: Index) {
elements.swapAt(i, j)
}
public mutating func partition(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
try elements.partition(by: belongsInSecondPartition)
}
public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
try elements.sort(by: areInIncreasingOrder)
}
}
extension OrderedSet where Element : Comparable {
public mutating func sort() {
elements.sort()
}
}
extension OrderedSet: RangeReplaceableCollection {
public mutating func replaceSubrange<C>(_ subrange: Range<Index>, with newElements: C) where C : Collection, C.Element == Element {
set.subtract(elements[subrange])
let insertedElements = newElements.filter {
set.insert($0).inserted
}
elements.replaceSubrange(subrange, with: insertedElements)
}
}
Вывод
Я уже сказал, уронив MutableCollection соответствие было бы более безопасным решением.
Вышеупомянутое работает, но ненадежно: мне пришлось "угадать", какие методы необходимо реализовать, поскольку реализация по умолчанию не работает. ЕслиMutableCollectionПротокол в стандартной библиотеке Swift получает новый метод с реализацией по умолчанию. все может снова сломаться.