//Compile with something like 'xcrun swiftc -sdk (xcrun --show-sdk-path --sdk macosx) ~/Desktop/deque.swift -o deque', then run with ./deque /* The elements of 'DequeBuffer' that aren't its actual buffer. In our case that's how many things are in it, and how many it can fit. */ private struct CountAndCapacity { var count : Int var capacity : Int } /* The actual storage for the deque. ManagedBuffer works together with isUniquelyReferencedNonObjC to let us determine when it's safe to mutate this (i.e. there's only one reference to it), and when we need to make a copy ("Copy-on-Write"). The layout of this is: [ (normal object header), count, capacity, variably sized chunk of memory ] */ private class DequeBuffer : ManagedBuffer, CustomDebugStringConvertible { func copy() -> DequeBuffer { return withUnsafeMutablePointerToElements { //withUnsafeMutablePointerToElements gets us a temporary pointer to the chunk of memory this DequeBuffer is managing let contentsBuffer = UnsafeBufferPointer(start:$0, count:self.value.count) //UnsafeBufferPointer lets us treat that pointer to a chunk of memory as a collection, which we can pass to createFrom() return DequeBuffer.createFrom(contentsBuffer) } } static func createFrom(elements:Collection, additionalCapacity:Int = 0) -> DequeBuffer { let elementCount = Int(elements.count.toIntMax()) //This is weird, but CollectionType.Index.Distance (which is the type of 'count') is not guaranteed to be Int, but is guaranteed to be convertable to the largest Int type via toIntMax(). A collection of that size won't work anyway, so we're fine with trapping on overflow if the result doesn't fit back into Int. return DequeBuffer.create(elementCount + additionalCapacity, initialValue: { (incompleteBuffer) in //ManagedBuffer.create() passes us the partially initialized buffer to finish setting up incompleteBuffer.withUnsafeMutablePointerToElements { $0.initializeFrom(elements) } //initializeFrom() will take care of doing things like retaining objects, if Element is a type that needs to be retained return CountAndCapacity(count: elementCount, capacity: elementCount + additionalCapacity) //Now that we've set up the buffer, we set up our "header" struct, and return that to complete initialization }) as! DequeBuffer //This downcast is guaranteed to succeed, since we know we're making a DequeBuffer } subscript(index:Int) -> Element { get { return withUnsafeMutablePointerToElements { ($0 + index).memory //pointer arithmetic? In Swift? Sure is! We could also have used UnsafeBufferPointer() here and just subscripted that } } } var debugDescription: String { return withUnsafeMutablePointerToElements { let elements = Array(UnsafeBufferPointer(start: $0, count: self.value.count)) //Array already has a nice debug description, and we hardly need to be fast here... return "DequeBuffer(count = \(self.value.count), capacity = \(self.value.capacity), elements = \(elements))" } } deinit { withUnsafeMutablePointerToElements { $0.destroy(self.value.count) //destroy()ing the values in the buffer will take care of releasing them if necessary, etc... } } } public struct Deque : MutableCollectionType, RangeReplaceableCollectionType, ArrayLiteralConvertible { private var _backing:DequeBuffer //note that the backing store is a reference type stored inside the value type, so when one of these is assigned, it copies the reference to the _backing, and the _headIndex, but not the actual contents of the _backing. Those are only copied when we do so explicitly. private var _headIndex = 0 public var capacity : Int { return _backing.value.capacity } public private(set) var count : Int { get { return _backing.value.count } set { _backing.value.count = newValue } } public init(elements:Collection) { _backing = DequeBuffer.createFrom(elements) //all the other initializers funnel through this one } public init() { self.init(elements:EmptyCollection()) } public init(elements:Sequence) { self.init(elements: Array(elements)) //we can't necessarily get the length of a sequence without consuming it, so we just convert it into an Array and let the CollectionType version of init() handle things } public init(arrayLiteral elements: Element...) { self.init(elements: elements) } public subscript (index: Int) -> Element { get { _checkIndex(index) return _backing[_normalizeIndex(index)] } mutating set { _checkIndex(index) replaceRange(index..(replacedRange: Range, with newElements: Collection) { _checkRange(replacedRange) let newElementCount = Int(newElements.count.toIntMax()) //Same CollectionType.Index.Distance conversion dance as in the DequeBuffer code let countDelta = newElementCount - replacedRange.count if !isUniquelyReferencedNonObjC(&(_backing)) { //Here's where the Copy-on-Write magic happens. Simple isn't it? :) If there's only one thing referencing _backing, then there's no need to copy to avoid mucking with someone else's copy of this Deque _backing = _backing.copy() } if countDelta != 0 { //avoid all this work if we definitely don't need to shift. TODO: can we avoid it for prepend and append? if capacity < count + countDelta { self.reserveCapacity(max(capacity * 2, count + countDelta)) //Grow by 2x if needed to amortize the cost of resizing } //_clear() will take care of destroy()ing any elements that we're replacing, making sure they're released properly before we put new ones over them //note that the implementations of _expand* and _consume* *rely on this call to clear* _clear(replacedRange.map(_normalizeIndex)) //TODO: this is slightly redundant, since we may be shifting elements, but it's simple let shouldShiftFromBack = replacedRange.startIndex >= count - replacedRange.endIndex // Attempt to avoid wrapping around if possible by shifting in the direction we have the most room if countDelta > 0 { //countDelta is positive, so we're adding more elements than we're removing, which means we need to shift 0 (if we're appending/prepending) or more existing elements to make room if shouldShiftFromBack { _expandToAddElementsAtIndexByShiftingTowardsBack(replacedRange.endIndex, distance: countDelta) } else { _expandToAddElementsAtIndexByShiftingTowardsFront(replacedRange.startIndex - 1, distance: countDelta) } } else if countDelta < 0 { //we've already checked for == 0, so < and > are exhaustive here //countDelta is negative, so we're removing more elements than we're adding, which means we need to shift 0 (if we're removing at either end) or more existing elements into the newly freed up space if shouldShiftFromBack { _consumeElementsInRangeByShiftingFromBack(replacedRange.dropFirst(newElementCount)) } else { _consumeElementsInRangeByShiftingFromFront(replacedRange.dropLast(newElementCount)) } } //now that all of our existing elements are in the right place, we can update the count. All that remains is to splat down the new elements in the empty spot count += countDelta } //This assertion verifies that the blank spot we created in the buffer is big enough to hold all the elements we're about to move in assert((replacedRange.startIndex..<(replacedRange.endIndex + countDelta)).count == newElementCount) _backing.withUnsafeMutablePointerToElements { (elementsPtr) -> Void in (elementsPtr + replacedRange.startIndex).initializeFrom(newElements) //now we just copy the elements into place :) } //Finally, make sure everything that's supposed to be true under normal operating conditions is still true _checkInvariants() } public var startIndex : Int { return 0 //regardless of where the start is in our buffer, it's still index 0 from the point of view of everything outside } public var endIndex : Int { return count //endIndex is defined as "just past the last valid index" so it's count, rather than count - 1 } mutating public func reserveCapacity(n: Int) { _backing = DequeBuffer.createFrom(self, additionalCapacity: n - capacity) //It makes me really happy how simple this is. Just copy self into a bigger buffer! _checkInvariants() } private func _checkIndex(index:Int) { precondition(index < endIndex) precondition(index >= startIndex) } private func _checkRange(range:C) { //using CollectionType rather than Range here because sometimes I'm checking Slice instead precondition(range.endIndex <= endIndex) precondition(range.startIndex >= startIndex) } private func _checkInvariants() { //Scotty, damage report! #if DEBUG print("Checking invariants for \(self)") assert(count <= capacity, "failed to resize to fit items. Capacity \(capacity), count \(count)") var counter = 0 for _ in self { counter++ } //check to make sure all elements are contiguous assert(counter == count) #endif } //Applies a sequence of shifts to element indices, described as an index to move from and an index to move to private mutating func _shift(shifts:Sequence) { _backing.withUnsafeMutablePointerToElements { (elementsPtr) in for (source, dest) in shifts { if source == dest { continue } #if DEBUG print("Shifting \"\(self._backing[source])\" from index \(source) to index \(dest)") #endif (elementsPtr + dest).moveInitializeFrom((elementsPtr + source), count: 1) //moveInitializeFrom leaves the source element uninitialized, ready for the code in replaceRange() to initialize } } } //Does what it says on the tin: clears out the specified indices, releasing their contents if needed private mutating func _clear(indices:Sequence) { _backing.withUnsafeMutablePointerToElements { (elementsPtr) in for index in indices { #if DEBUG print("Clearing index \(self._normalizeIndex(index)) which normalized from \(index)") #endif (elementsPtr + self._normalizeIndex(index)).destroy() } } } /* This is what makes an Array-Deque different from an Array. Modular arithmetic "wraps around" back to 0, so doing % capacity as we're doing here causes the indices to wrap around back to the begining of the array when they reach the end. This lets us treat the backing buffer as a loop, with the beginning and end being anywhere we want, rather than as a list with a fixed beginning and end. Because we can move the start and end indices around the loop instead of having to resize the buffer, we can insert and remove elements at both ends in O(1) time, vs O(n) for an Array. In terms of use you can think of this as converting from "external/client" indices to "internal/backing" indices. */ private func _normalizeIndex(index:Int) -> Int { if index == 0 { return _headIndex } return (index + _headIndex) % capacity } //Takes a range and an offset, and returns a list of pairs of each index in that range, and the corresponding offset index. This return type is ridiculous; sorry. private func _calculateShifts(range:Range, distance:Int) -> Zip2Sequence, Int>, LazyMapCollection, Int>, Int>> { //We use lazy here to avoid allocating temporary arrays return zip( range.lazy.map(_normalizeIndex), range.lazy.map { $0 + distance }.map(_normalizeIndex) ) } /* Shortens the array by removing the elements in the range, and shifting anything at lower indices up into the gap. So if the current contents are: [a, b (now destroy()ed by the _clear() in replaceRange()), c] and the range is: 1..<2 then this would shift a into where b used to be, yielding [a, c] or, since this is a deque and not an array, [_, a, c], with the head index pointing at a */ private mutating func _consumeElementsInRangeByShiftingFromFront(range:Slice>) { if range.isEmpty { return } _checkRange(range) _shift(_calculateShifts(0..>) { if range.isEmpty { return } _checkRange(range) _shift(_calculateShifts((range.endIndex - 1).. : MutableCollectionType, RangeReplaceableCollectionType, ArrayLiteralConvertible { var robot:[Element] var arm:Deque public var startIndex : Int { assert(robot.startIndex == arm.startIndex) return arm.startIndex } public var endIndex : Int { assert(robot.endIndex == arm.endIndex) return arm.endIndex } private func _checkInvariants() { assert(arm.count == robot.count) let elements = zip(robot, arm) for (a, b) in elements { assert(a == b) } } public init() { self = [] } public init(arrayLiteral elements: Element...) { robot = elements arm = Deque(elements:elements) } mutating public func reserveCapacity(n: Int) { robot.reserveCapacity(n) arm.reserveCapacity(n) _checkInvariants() } public subscript (index: Int) -> Element { get { assert(arm[index] == robot[index]) return arm[index] } mutating set { arm[index] = newValue robot[index] = newValue _checkInvariants() } } public mutating func replaceRange(subRange: Range, with newElements: Collection) { arm.replaceRange(subRange, with: newElements) robot.replaceRange(subRange, with: newElements) _checkInvariants() } } var mini:RoboticArm = [1] mini.append(2) mini.replaceRange(0..<1, with: []) print(mini) print(Array(mini)) var d:RoboticArm = [1, 2, 3, 4, 5, 6] print(d) print(Array(d)) d.replaceRange(2...3, with: [8, 8, 8, 8]) print(d) print(Array(d)) print(d[2...4]) d.append(92) print(d) print(Array(d)) var d2 = d d2.appendContentsOf(d) print(d2) print(Array(d2)) print(d) print(Array(d))