I think linked lists are neat too. But the problem is that from a user's perspective, the linked-ness is just an implementation detail; there's nearly nothing a linked-list does externally that a flexible array can't also do, especially since elements generally have value semantics with their containers (even if the element type itself is a reference type).
For instance, I looked at your types and you can get a Node from a collection and index. But why would I ever want a node? If I want to inspect/mutate the element value, Collection's interface with Index already provides that. The only other thing a node has are links to neighboring nodes, and you definitely don't want users to perform arbitrary link surgery; that would mess up your list's invariants. (This last point is especially important for implementations where subscripted sub-sequences share references to their parent's nodes.)
The only value-add a linked list has over an array or similar is the "move semantics" a linked list can provide by trading nodes among instances without triggering element-level copies. So the only additional interface would be to allow said swaps:
/**
A collection that supports transfers (not just copies) of elements among instances.
The use of transfers implies that elements are individually encapsulated in (free-store) memory and are linked together with references to form sequences.
Linked-node collections provide operations that move encapsulated elements, called nodes, from one instance to another. If instances can share nodes, a transfer means both the source instance and **all** other instances that shared any targeted nodes lose access to said nodes. (This protocol only specifies node-transferring operations; node-sharing arragements, like implementing `SubSequence` with `Self`, are up to the conforming type.)
`LinkedNodeCollection` types are either singly- or doubly-linked. A singly-linked node collection can only easily support forward insertions and removals. Versions of those operations that need to look at nodes before the targeted one, *i.e.* backwards, need *O(n)* search time to get a reference to the previous node. This also necessitates special routines that mess with the endpoints of a collection. These restrictions don't apply to doubly-linked node collections.
Conforming to the LinkedNodeCollection Protocol
===============================================
To add `LinkedNodeCollection` conformance to your custom collection:
* Add a single-element initializer. This lets a new default implemenation of `replaceSubrange(_:with:)` work by stitching nodes of elements together when needed.
* For singly-linked lists, implement `tradeShifted(my:forNodesOf:along:)` to swap nodes referenced by inverted ranges. For doubly-linked lists, the default implemenation of this method should suffice.
* Implement `trade(my:forNodesOf:along:)` to swap nodes referenced by regular ranges. For singly-linked lists, the implemenation should call `tradeShifted` to economize code.
*/
public protocol LinkedNodeCollection: RangeReplaceableCollection where Self.SubSequence: LinkedNodeCollection {
/**
Creates a new collection, consisting of only the specified element.
- Note: The default implementation of `replaceSubrange(_:with:)` for `LinkedNodeCollection` calls this initializer, so don't have this iniitializer forward to an initializer that ends up calling `replaceSubrange`. (The default implemenations of the sequence-converting and repeated-value initializers may do so indirectly.)
- Parameter element: The element to be stored in the collection.
*/
init(with element: Element)
/**
Trades ownership of the targeted nodes between the receiver and another collection.
Either sub-range may be empty; if so, then the trade acts as an insertion for the instance with an empty target sub-range, pushing the elements at and after that index forward.
- Precondition: There are no nodes shared between `self` along `subrange` and `other` along `otherSubrange`. If `self` and `other` use the same master collection as the home of their nodes, the ranges can abut within that collection.
- Parameter subrange: The set of nodes of `self` that will be removed. The nodes from `other` will be inserted here.
- Parameter other: The source of the incoming nodes. And the destination of the outgoing nodes.
- Parameter otherSubrange: The set of nodes from `other` that will be inserted. The nodes will be removed from `other`.
- Returns: A pair of ranges, representing the new locations of the transferred nodes. The `myNewNodes` member holds the location within `self` that the nodes that were originally from `other` reside. The `otherNewNodes` member holds the location within `other` that the nodes that were originally from `self` reside.
- Postcondition:
- `priorElement(oldSelf[subrange.lowerBound]) === priorElement(self[myNewNodes.lowerBound])`, modulo `self` not targeting a prefix or totality.
- `oldSelf[subrange.upperBound] === self[myNewNodes.upperBound]`, modulo `self` not targeting a suffix or totality.
- `priorElement(oldOther[otherSubrange.lowerBound]) === priorElement(other[otherNewNodes.lowerBound])`, modulo `other` not targeting a prefix or totality.
- `oldOther[otherSubrange.upperBound] === other[otherNewNodes.upperBound]`, modulo `other` not targeting a suffix or totality.
- Complexity: *O(n)*, or *O(1)* if the collection supports at least bi-directional traversal.
*/
mutating func trade(my subrange: Range<Index>, forNodesOf other: inout Self, along otherSubrange: Range<Index>) -> (myNewNodes: Range<Index>, otherNewNodes: Range<Index>)
/**
An inverted half-open range, a.k.a. a half-closed range.
It excludes the lower bound but includes the upper bound. Use the same value for both to indicate an empty range.
Use `nil` to indicate the pseudo-position before `startIndex`.
*/
typealias InvertedRange = (beforeLower: Index?, atUpper: Index?)
/**
Using inverted half-open ranges, trades ownership of the targeted nodes between the receiver and another collection.
Either sub-range may be empty; if so, then the trade actas as an insertion fro the instance with an empty target sub-range, pushing the elements at and before that index backward.
For an inverted-range's `atUpper` (or both that and `beforeLower`), `endIndex` may be used as a substitute for calculating the index for the last element (assuming a non-empty collection).
- Precondition: There are no nodes shared between `self` along `subrange` and `other` along `otherSubrange`. If `self` and `other` use the same master collection as the home of their nodes, the ranges can abut within that collection.
- Parameter subrange: The set of nodes of `self` that will be removed. The nodes from `other` will be inserted here.
- Parameter other: The source of the incoming nodes. And the destination of the outgoing nodes.
- Parameter otherSubrange: The set of nodes from `other` that will be inserted. The nodes will be removed from `other`.
- Returns: A pair of ranges, representing the new locations of the transferred nodes. The `myNewNodes` member holds the location within `self` that the nodes that were originally from `other` reside. The `otherNewNodes` member holds the location within `other` that the nodes that were originally from `self` reside.
- Postcondition:
- `oldSelf[subrange.beforeLower] === self[myNewNodes.beforeLower]`, if `beforeLower` doesn't point to before `startIndex`.
- `followingElement(oldSelf[subrange.atUpper]) === followingElement(self[myNewNodes.atUpper])`, modulo `self` not targeting a suffix or totality.
- `oldOther[otherSubrange.beforeLower] === other[otherNewNodes.beforeLower]`, if `beforeLower` doesn't point to before `startIndex`.
- `followingElement(oldOther[otherSubrange.atUpper]) === followingElement(other[otherNewNodes.atUpper])`, modulo `other` not targeting a suffix or totality.
- Complexity: *O(1)*.
*/
mutating func tradeShifted(my subrange: InvertedRange, forNodesOf other: inout Self, along otherSubrange: InvertedRange) -> (myNewNodes: InvertedRange, otherNewNodes: InvertedRange)
}
extension LinkedNodeCollection where Self: BidirectionalCollection {
mutating func tradeShifted(my subrange: InvertedRange, forNodesOf other: inout Self, along otherSubrange: InvertedRange) -> (myNewNodes: InvertedRange, otherNewNodes: InvertedRange) {
// Convert a half-closed range index to a half-open range index.
func forwardIndex(source: Self, i: Index?) -> Index {
guard var backIndex = i else { return source.startIndex }
source.formIndex(&backIndex, offsetBy: +1, limitedBy: source.endIndex)
return backIndex
}
let properMySubrange = forwardIndex(source: self, i: subrange.beforeLower) ..< forwardIndex(source: self, i: subrange.atUpper)
let properOtherSubrange = forwardIndex(source: other, i: otherSubrange.beforeLower) ..< forwardIndex(source: other, i: otherSubrange.atUpper)
let shiftedResult = trade(my: properMySubrange, forNodesOf: &other, along: properOtherSubrange)
let myShiftedLowerBound = index(shiftedResult.myNewNodes.lowerBound, offsetBy: -1, limitedBy: startIndex)
let myShiftedUpperBound = index(shiftedResult.myNewNodes.upperBound, offsetBy: -1, limitedBy: startIndex)
let otherShiftedLowerBound = other.index(shiftedResult.otherNewNodes.lowerBound, offsetBy: -1, limitedBy: other.startIndex)
let otherShiftedUpperBound = other.index(shiftedResult.otherNewNodes.upperBound, offsetBy: -1, limitedBy: other.startIndex)
return ((myShiftedLowerBound, myShiftedUpperBound), (otherShiftedLowerBound, otherShiftedUpperBound))
}
}
extension LinkedNodeCollection {
/**
Transfers all the nodes of the specified collection to the beginning of the receiver.
- Parameter other: The source of the elements to be newly stored in the collection.
- Postcondition: If `other` and `self` have no node overlap, `other.isEmpty`. Otherwise, the state of `other` is unspecified.
*/
public mutating func prepend(stealingFrom other: inout Self) {
tradeShifted(my: (nil, nil), forNodesOf: &other, along: (nil, other.endIndex))
}
/**
Transfers all the nodes of the specified collection to the receiver after the specified element.
- Precondition:
- `i` points to a current element in `self`.
- `other` cannot include the node that `i` points to.
- Parameter i: The index for the element whose node will immediately preceed where the nodes from `other` will go.
- Parameter other: The source of the elements to be newly stored in the collection.
- Postcondition: If `other` and `self` have no node overlap, `other.isEmpty`. Otherwise, the state of `other` is unspecified.
*/
public mutating func insertNodesAfter(i: Index, stealingFrom other: inout Self) {
tradeShifted(my: (i, i), forNodesOf: &other, along: (nil, other.endIndex))
}
/**
Transfers all the nodes of the specified collection to the end of the receiver.
Depending on how the collection keeps track of its nodes, this method may be faster than searching for the last element's index and using `insertNodesAfter(i: stealingFrom:)`.
- Parameter other: The source of the elements to be newly stored in the collection.
- Postcondition: If `other` and `self` have no node overlap, `other.isEmpty`. Otherwise, the state of `other` is unspecified.
*/
public mutating func append(stealingFrom other: inout Self) {
tradeShifted(my: (endIndex, endIndex), forNodesOf: &other, along: (nil, other.endIndex))
}
}
extension LinkedNodeCollection {
public mutating func replaceSubrange<C>(_ subrange: Range<Index>, with newElements: C) where C: Collection, C.Element == Element {
var new = Self()
for var n in newElements.map({ Self(with: $0) }) {
new.append(stealingFrom: &n)
}
trade(my: subrange, forNodesOf: &new, along: new.startIndex ..< new.endIndex)
}
}
extension LinkedNodeCollection {
/**
Transfers the specified nodes out of the receiver and into a new instance.
- Parameter subrange: The elements to remove from `self`.
- Returns: The extraced elements.
- Postcondition: The element before `subrange` and the element after `subrange` (*i.e.* `subrange.upperBound`) are adjacent, modulo `subrange` being a prefix, suffix, and/or totality.
- Complexity: *O(n)*, or *O(1)* if the collection supports at least bi-directional traversal.
*/
public mutating func segregate(out subrange: Range<Index>) -> Self {
var result = Self()
trade(my: subrange, forNodesOf: &result, along: result.startIndex ..< result.endIndex)
return result
}
/**
Using an inverted half-open range, transfers the specified nodes out of the receiver and into a new instance.
- Parameter subrange: The elements to remove from `self`.
- Returns: The extraced elements.
- Postcondition: The element before `subrange` (*i.e.* `subrange.beforeLower`) and the element after `subrange` are adjacent, modulo `subrange` being a prefix, suffix, and/or totality.
- Complexity: *O(1)*.
*/
public mutating func segregateShifted(out subrange: InvertedRange) -> Self {
var result = Self()
tradeShifted(my: subrange, forNodesOf: &result, along: (nil, nil))
return result
}
/**
Transfers the starting nodes of the receiver to a new instance.
- Parameter i: The index for the last element to be included in the returned prefix.
- Returns: The old prefix of `self`.
- Postcondition: `self` keeps only the elements that had an index greater than `i`, if any.
*/
public mutating func truncate(upThrough i: Index) -> Self {
return segregateShifted(out: (beforeLower: nil, atUpper: i))
}
/**
Transfers the ending nodes of the receiver to a new instance.
- Parameter i: The index for the last element to be excluded in the returned suffix.
- Returns: The old suffix of `self`.
- Postcondition: `self` keeps only the elements that had an index less than or equal to `i`, if any.
*/
public mutating func truncate(after i: Index) -> Self {
return segregateShifted(out: (beforeLower: i, atUpper: endIndex))
}
/**
Creates an instance by merging the nodes of two other instances, with admission order controlled by a closure.
Nodes from the same source are incorporated into this instance in the same relative order, but the interweaving order between sources is controlled by `body`. If one source is fully extracted before the other, all the remaining elements of the unexhausted source are appended.
- Precondition: `first` and `second` do not share any nodes.
- Parameter first: The first collection to steal nodes from.
- Parameter second: The second collection to steal nodes from.
- Parameter body: The selection function determining appending order. In each iteration, `body(first.first!, second.first!)` is evaluated. If `true` is returned, then the node for `first.first!` is appended to this instance; otherwise, the node for `second.first!` is transferred.
- Postcondition:
- `self` contains the elements from both `first` and `second`.
- `first.isEmpty`.
- `second.isEmpty`.
- Complexity: *O(n)*.
*/
init(merging first: inout Self, and second: inout Self, admitFirstOverSecond body: (Element, Element) throws -> Bool) rethrows {
self.init()
while let ff = first.first, let sf = second.first {
if try body(ff, sf) {
tradeShifted(my: (endIndex, endIndex), forNodesOf: &first, along: (nil, first.startIndex))
} else {
tradeShifted(my: (endIndex, endIndex), forNodesOf: &second, along: (nil, second.startIndex))
}
}
tradeShifted(my: (endIndex, endIndex), forNodesOf: &first, along: (nil, first.endIndex))
tradeShifted(my: (endIndex, endIndex), forNodesOf: &second, along: (nil, second.endIndex))
}
}
