Singly and Doubly Linked List collections in standard library


#1

Singly and doubly linked lists are often desired for O(1) insertion and deletion. I have implemented these in swift conforming to Collection protocols. It is optimized for copy on write and includes test cases as well. The complete implementation is available here: https://github.com/Tayyab-VenD/swift-collections

While ARC is great for memory management, it is not suitable to implement a node class due to next node reference. When I created 100,000 nodes, and linked them together they were held in memory as expected. But when I set first node to nil, I faced a crash, probably stack overflow. I assume it would have occurred due to recursive dealloc calling of each node.

So I have used manual memory management in the implementation but public collection and node classes do not expose this. There is an unsafe collection which owns every added node and is responsible for releasing it. This also reduces the overhead of retain and release calls while passing nodes to different functions.

I believe this general purpose implementation would be very beneficial for swift developers. Also, I would like to hear about ideas on this proposal, or any implementation changes if need be.


(Tino) #2

Yes, it’s most likely beneficial, but that’s also true for sorted arrays, various flavors of trees and other structures - and imho Swift just doesn’t have a good place to put those:
It’s already to specific for the stdlib (which has arrays, and those solve the problem of storing an arbitrary number of elements good enough for most use cases), and there’s no library for generic containers.
Imho that’s a pity, but we had many attempts to change this, and they never got enough support.


#3

You are right, there should be trees and other general purpose structures. But the linked list is a basis for many other structures such as stack and queue. When I’m developing in java, I never have to search for custom libraries as they are already available in the standard library. They should definitely be included in swift’s standard library as well.


(Félix Fischer) #4

Wow. If that’s actually the reason for the crash, that’s a bug in the ARC engine. Its behavior could instead change when under extreme recursion. For example, to a heap-allocated stack of pending deallocations.

I don’t know what’s the actual implementation though, so maybe the solution lies somewhere else.


#5

Maybe it is the intended behavior. I remember the days when we used MRC in Objective-C. In dealloc method, we used to call release on all retained variables. I think ARC would be doing the same thing.

Anyways, the following piece of code confirms that deallocation is happening recursively. So the cause of crash is definitely stack overflow.

import Foundation

class Node {
    var element: Int
    var next: Node?

    init(_ element: Int) {
        self.element = element
    }

    deinit {
        if element == 10_000 {
            print(Thread.callStackSymbols)
        }

        print("Deallocating \(element)")
    }
}

var first: Node! = Node(0)
var previous: Node! = first

for i in 1...1_00_000 {
    let node = Node(i)
    previous.next = node
    previous = node
}

first = nil // Crashes at this line...

It would be a good idea to provide a bug free linked list implementation in standard library.


(Lukas Stabe 🙃) #6

Fwiw, here you can see a way to work around this (I think the rest of the code may behave weirly with multiple copies of the queue struct, but it suffices to illustrate how to deal with the recursive dealloc).


#7

That is a smart approach. :slight_smile:

I came with a rather different solution. There is a node class with public properties as expected. However it is internaly used from an unsafe wrapper struct. The node is immediately retained after creation and its unowned instance is used for manipulation. So there are no retain and release calls while passing it to functions. There is no need to make previous property weak because node cannot deallocate itself and the object does not have to maintain a list of weak variables.

public final class LinkedListNode<Element> {
    var optionalElement: Element!
    var unsafeNext: UnsafeNode<Element>? = nil
    var unsafePrevious: UnsafeNode<Element>? = nil

    init(_ element: Element! = nil) {
        self.optionalElement = element
    }

    public var element: Element { return optionalElement! }
    public var next: LinkedListNode<Element>? { return unsafeNext?.instance }
    public var previous: LinkedListNode<Element>? { return unsafePrevious?.instance }
}

struct UnsafeNode<Element> : Equatable {
    unowned(unsafe) let instance: LinkedListNode<Element>

    static func ==(lhs: UnsafeNode<Element>, rhs: UnsafeNode<Element>) -> Bool {
        return lhs.instance === rhs.instance
    }

    static func make(_ element: Element! = nil) -> UnsafeNode<Element> {
        let instance = LinkedListNode<Element>(element)
        return UnsafeNode(instance).retain()
    }

    private init(_ instance: LinkedListNode<Element>) {
        self.instance = instance
    }

    var element: Element! {
        nonmutating get { return instance.optionalElement }
        nonmutating set(value) { instance.optionalElement = value }
    }

    var next: UnsafeNode<Element> {
        nonmutating get { return instance.unsafeNext! }
        nonmutating set(value) { instance.unsafeNext = value }
    }

    var previous: UnsafeNode<Element> {
        nonmutating get { return instance.unsafePrevious! }
        nonmutating set(value) { instance.unsafePrevious = value }
    }

    func retain() -> UnsafeNode<Element> {
        let _ = Unmanaged.passRetained(instance)
        return self
    }

    func release() {
        instance.unsafeNext = nil
        instance.unsafePrevious = nil
        Unmanaged.passUnretained(instance).release()
    }
}

There is an unsafe list object which is responsible for releasing the nodes when they are no longer needed. Both classes are made final to avoid the overhead of virtual methods.

final class UnsafeList<Element> {
    deinit {
        // Release all the nodes of this list and set their `next` and `previous` properties to nil.
        // This will ensure that a user does not accidently access deallocated nodes.
    }

    func clone(marking nodes: inout [UnsafeNode<Element>]) -> UnsafeList<Element> {
        // - Make clone of all nodes and handle them to a new `UnsafeList<Element>` object.
        // - Replace elements of existing `nodes` with cloned ones to facilitate efficient
        //   implementation of copy on write.
    }

    func attach(node: UnsafeNode<Element>, after last: UnsafeNode<Element>) {
        // - The list has already claimed `last` node.
        // - Take responsibility for new `node` as well.
    }

    func abandon(after first: UnsafeNode<Element>, before last: UnsafeNode<Element>) {
        // - The list has already claimed `first` and `last` nodes.
        // - As in between nodes are no longer needed, release them here.
    }
}

This unsafe list is eventually held by a public struct LinkedList conforming to RangeReplaceableCollection and give access to all of its rich API.


(Thomas Roughton) #8

I’m not convinced that a linked list is something you’d want in the standard library. Those O(1) insertions and deletions come at the cost of a data structure that’s generally far from ideal performance-wise due to all the pointer chasing, and including it in the standard library means people may default to it without understanding properly when a linked list is what you should use.

For example, one use case might be a queue (Array covers the stack use case); for this, a ring buffer would generally be a better choice. Similarly, if you’re inserting things into the middle of a linked list, then a better option might be to append and then sort; even though the time complexity is higher, the constant factors might be smaller by a large enough factor to mitigate it.


#9

@Torust Your post throws light on some interesting points. So I wrote a little benchmark code and ran it in release mode for both a struct and a class as element containing a single Int. Following are my findings.

/*
With Struct Element:

Element Count: 100
Array `append`: 0.735998153686523
Singly Linked List `append`: 0.136971473693848
Doubly Linked List `append`: 0.0640153884887695

Element Count: 1000
Array `append`: 0.0159740447998047
Singly Linked List `append`: 0.41496753692627
Doubly Linked List `append`: 0.298023223876953

Element Count: 10000
Array `append`: 0.130057334899902
Singly Linked List `append`: 2.76696681976318
Doubly Linked List `append`: 2.30205059051514

Element Count: 100000
Array `append`: 1.42598152160645
Singly Linked List `append`: 24.3179798126221
Doubly Linked List `append`: 24.4710445404053

Element Count: 1000000
Array `append`: 14.4869089126587
Singly Linked List `append`: 320.210099220276
Doubly Linked List `append`: 252.624988555908

Element Count: 100
Array `prepend`: 0.00607967376708984
Singly Linked List `prepend`: 0.0969171524047852
Doubly Linked List `prepend`: 0.0920295715332031

Element Count: 1000
Array `prepend`: 0.11599063873291
Singly Linked List `prepend`: 0.339031219482422
Doubly Linked List `prepend`: 0.241994857788086

Element Count: 10000
Array `prepend`: 12.3579502105713
Singly Linked List `prepend`: 2.39396095275879
Doubly Linked List `prepend`: 2.55501270294189

Element Count: 100000
Array `prepend`: 1854.04706001282
Singly Linked List `prepend`: 28.344988822937
Doubly Linked List `prepend`: 27.1179676055908




With Object Element:

Element Count: 100
Array `append`: 1.02198123931885
Singly Linked List `append`: 0.191926956176758
Doubly Linked List `append`: 0.102043151855469

Element Count: 1000
Array `append`: 0.355005264282227
Singly Linked List `append`: 0.715970993041992
Doubly Linked List `append`: 0.713944435119629

Element Count: 10000
Array `append`: 2.10297107696533
Singly Linked List `append`: 3.86893749237061
Doubly Linked List `append`: 5.00810146331787

Element Count: 100000
Array `append`: 24.8579978942871
Singly Linked List `append`: 46.1180210113525
Doubly Linked List `append`: 48.9749908447266

Element Count: 1000000
Array `append`: 235.588908195496
Singly Linked List `append`: 442.839026451111
Doubly Linked List `append`: 478.710055351257

Element Count: 100
Array `prepend`: 0.041961669921875
Singly Linked List `prepend`: 0.11909008026123
Doubly Linked List `prepend`: 0.105977058410645

Element Count: 1000
Array `prepend`: 0.311970710754395
Singly Linked List `prepend`: 0.458002090454102
Doubly Linked List `prepend`: 0.536084175109863

Element Count: 10000
Array `prepend`: 15.2440071105957
Singly Linked List `prepend`: 6.03294372558594
Doubly Linked List `prepend`: 4.79400157928467

Element Count: 100000
Array `prepend`: 1899.61409568787
Singly Linked List `prepend`: 48.1230020523071
Doubly Linked List `prepend`: 49.5460033416748
*/

In case of struct, array is always faster when appending an element, even upto 22 times. In case of class, the linked list is only about 2 times slower. Prepending an element is slower in linked list for upto a thousand elements but it is always faster afterwards. And the program hang when prepending more than 100000 in array. Also note that the cost of nodes deallocation is also included in each operation.

The programmers usually know what data structure they are using. And everyone knows about the overhead of linked list in terms of pointers and memory. It is not that we start using a data structure just for its complexity. There are many other things to consider as well, like you said. As for the ring buffer, I’m not sure how it handles continuous growing.

Here is the benchmark code, if anyone is interested.

import Foundation

class Data {
    var element: Int

    init(_ element: Int) {
        self.element = element
    }
}

func benchmark(block: () -> Void) -> Double {
    let startTime = CFAbsoluteTimeGetCurrent()
    block()
    let endTime = CFAbsoluteTimeGetCurrent()

    return (endTime - startTime) * 1000
}

func benchmarkAppend(with count: Int) {
    let array = benchmark {
        var array = Array<Data>()
        for i in 1...count {
            array.append(Data(i))
        }
    }

    let singly = benchmark {
        var list = SinglyLinkedList<Data>()
        for i in 1...count {
            list.append(Data(i))
        }
    }

    let doubly = benchmark {
        var list = LinkedList<Data>()
        for i in 1...count {
            list.append(Data(i))
        }
    }

    print("Element Count: \(count)")
    print("Array `append`: \(array)")
    print("Singly Linked List `append`: \(singly)")
    print("Doubly Linked List `append`: \(doubly)")
    print("")
}

func benchmarkInsert(with count: Int) {
    let array = benchmark {
        var array = Array<Data>()
        for i in 1...count {
            array.insert(Data(i), at: 0)
        }
    }

    let singly = benchmark {
        var list = SinglyLinkedList<Data>()
        for i in 1...count {
            list.insert(Data(i), at: list.startIndex)
        }
    }

    let doubly = benchmark {
        var list = LinkedList<Data>()
        for i in 1...count {
            list.insert(Data(i), at: list.startIndex)
        }
    }

    print("Element Count: \(count)")
    print("Array `prepend`: \(array)")
    print("Singly Linked List `prepend`: \(singly)")
    print("Doubly Linked List `prepend`: \(doubly)")
    print("")
}

func benchmark(_ closure: (Int) -> Void, counts: [Int]) {
    for i in counts {
        closure(i)
    }
}

benchmark(benchmarkAppend, counts: [100, 1_000, 10_000, 100_000, 10_00_000])
benchmark(benchmarkInsert, counts: [100, 1_000, 10_000, 100_000])

#10

Perhaps one of the yet-to-be created “nonstandard libraries” ought to be for data structures. I suspect that a priority queue (possibly double-ended) would see a fair bit of use.


(Chris Lattner) #11

I tend to agree with you. With modern memory hierarchies, you have to have a truly massive linked list for the complexity benefits overweigh the constant time factors. I wrote about some of these things ages ago here:
http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task

If you’re interested in this sort of thing, I’d encourage thinking about how to implement intrusive linked lists. They really do provide benefits, because you can contain heterogenous elements. We use these pervasively for the compiler representations in LLVM/Swift:
http://llvm.org/docs/ProgrammersManual.html#llvm-adt-ilist-h

I’m haven’t thought much about what the best way to make a generic intrusive list is in Swift.


(Daryle Walker) #12

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))
    }

}

(Félix Fischer) #13

They also allow you to implement O(1) memory Mergesort. You can also do it relatively quickly if you scan the list in a smart manner.

But if you needed to sort elements, a list isn’t the structure you’d want to start with. The use-case of on-demand sorting over a linked list is very niche, and probably outside of what a StdLib could give you without being too general for the specific cases.


(Chris Lattner) #14

I’m not a fan of lists for most things, but they do have specific technical advantages that are killer features in some domains. For example, the iterator invalidation behavior is a killer feature for compiler IRs. That said, I’d be the first to admit that this is niche, and lists are not difficult to roll your own when you need them.

OTOH, the challenge of implementing them in swift is that you really don’t want to use strong pointers for forward and back pointers (you want unsafe pointers between the nodes and the list to handle their ownership).

Maybe there is a more primitive concept that would be possible to build and expose, allowing users to build their own efficient lists out of that underlying concept?

-Chris


(^) #15

if only Swift had SmallVector


(Chris Lattner) #16

Seriously. My forthcoming constexpr proposal is an important piece to providing constant arguments for generics, which may be the path forward for fixed size arrays, the essential ingredient we’re missing to be able to implement a SmallVector-like type in Swift.

-Chris


(^) #17

Can I ask why constant generic parameters are the way to go here? my gut feel here is we already have a problem with separating out what’s allowed to go inside <>s and what isn’t. Like, isn’t that why we have to type .self after every type name in Swift?


(Chris Lattner) #18

I’m not sure what you’re asking and how .self is related. There are still some people (myself included) who hope we can eventually drop the requirement to use .self. I believe that @Joe_Groff feels the same way, but I’m not sure if he’s changed his mind recently.

-Chris


(^) #19

maybe i’m being stupid here but wouldn’t allowing stuff like SmallVector<Int, 5> be treating the 5 as a weird kind of type parameter so you’d have to either start writing 5.self whenever you want to use it as a value, or come up with some other way to infer that the constant is supposed to be a value instead of a type parameter

I guess you could say that the compiler will always treat 5 as a value unless it’s inside <>s, but idk how that’d play out if you want to support expressions inside the <>s


(Chris Lattner) #20

The generics manifesto doesn’t explicitly specify a client side syntax for this. That said, I don’t see why we’d have to do something like that.

-Chris