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.
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:
edit/update:
The sorted
method works as expected but the mutating sort
it is not even changing the elements order.
MutableCollection
Declaration mutating
func sort()
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]"
How can I fix it?
Problem 1: Making
OrderedSet
aMutableCollection
In a
MutableCollection
you can change an individual element (or a slice of elements) via a subscript that supports write access. And that is where the problems start: What should the output ofbe? We cannot simply replace the first element because then the set members are not unique anymore. Your current implementation returns
[1, 2, 3, 4]
, i.e. it rejects the setting if the new member is already present in the set.That makes many default implementations of
MutableCollection
methods fail:sort()
,swapAt()
,shuffle()
and probably more:Problem 2: Slicing
In your implementation you chose
Slice<OrderedSet<Element>>
as theSubSequence
type.Slice
uses the storage from the originating (base) collection and only maintains its ownstartIndex
andendIndex
. That leads to unexpected results:Setting
oslice[0]
is rejected because the originating set contains the new member. That is certainly not expected. Sorting a slicefails because the sorted elements are written back one by one, and that fails because the members are already present in the set. The same happens with a slice assignment:
Another problem is that a slice
oset[0..<3]
does not conform toOrderedSetProtocol
:It is a (mutable) collection, but for example not aSetAlgebra
, so that it cannot be used to form unions, intersections, or symmetric differences.Do you really need the
MutableCollection
conformance?I would seriously consider not to adopt the
MutableCollection
protocol. That does not make the ordered set immutable: It only means that individual members cannot be modified via the subscript setter. You can still insert or remove elements, or form unions or intersections with other sets. Only for “complex” operations like sorting you have to go via an extra temporary set:The big advantage is that there is no unclear behavior anymore.
Yes, I want the
MutableCollection
conformance!OK, you asked for it – let's see what we can do. We could try to fix this by “fixing” the subscript setter. One attempt is your commented out code:
This has the effect of moving an existing member to the given location, shifting other elements:
This seems to make most methods work correctly:
and even the subscript sorting:
But I see two disadvantages:
Another option is to leave the subscript setter as it is (i.e. reject invalid settings), and implement the problematic methods instead of using the default implementations of
MutableCollection
:In addition we need to implement the subscript setter taking a range
so that a sorted slice is assigned back to the set as one operation, and not each element individually.
That worked in my tests, but there is a risk that I overlooked something.
And for the slicing I would make
OrderedSet
its ownSubSequence
type. That means that the elements are duplicated. This could be avoided by making theelement
storage anArraySlice
but – as we saw above – theset
of distinct members has to be duplicated anyway, to avoid unwanted side effects when the originating set is mutated.The code
This is what I have so far. It works correctly as far as I can tell, but needs more testing.
Note that some methods need not be implemented, e.g.
ExpressibleByArrayLiteral
has already a default implementation inSetAlgebra
, and various index calculations have default implementations because theIndex
isStrideable
.Conclusion
I already said, dropping the
MutableCollection
conformance would be the safer solution.The above works but is fragile: I had to “guess” which methods must be implemented because the default implementation does not work. If the
MutableCollection
protocol in the Swift standard library gets a new method with a default implementation. things can break again.