Проблема 1: Создание OrderedSet a MutableCollection
В MutableCollection вы можете изменить отдельный элемент (или часть элементов) через индекс, который поддерживает write доступ. И вот тут начинаются проблемы: каким должен быть вывод
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 , так что его нельзя использовать для образования союзов, пересечений или симметрий c различий.
Вам действительно нужно соответствие MutableCollection?
Я бы серьезно подумал , а не для принятия протокола MutableCollection. Это не делает упорядоченный набор неизменным: это означает только то, что отдельные элементы не могут быть изменены с помощью установщика нижнего индекса. Вы по-прежнему можете вставлять или удалять элементы, или объединять или пересекать с другими наборами. Только для «сложных» операций, таких как сортировка, вам нужно go с помощью дополнительного временного набора:
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) соответствие установщика индекса.
Другой вариант это оставить установщик индекса как есть (то есть отклонить неверные настройки) и реализовать проблемные c методы вместо использования реализаций по умолчанию 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()
}
}
Кроме того, нам нужно реализовать индекс setter с диапазоном
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 будет более безопасным решением.
Выше работает, но это fr agile: мне пришлось «угадать», какие методы должны быть реализованы, потому что реализация по умолчанию не работает. Если протокол MutableCollection в стандартной библиотеке Swift получает новый метод с реализацией по умолчанию. вещи могут снова сломаться.