//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<Element> : ManagedBuffer<CountAndCapacity, Element>, CustomDebugStringConvertible {
    
    func copy() -> DequeBuffer<Element> {
        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<Collection : CollectionType where Collection.Generator.Element == Element>(elements:Collection, additionalCapacity:Int = 0) -> DequeBuffer<Element> {
        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<Element> : MutableCollectionType, RangeReplaceableCollectionType, ArrayLiteralConvertible {
    private var _backing:DequeBuffer<Element> //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<Collection : CollectionType where Collection.Generator.Element == Element>(elements:Collection) {
        _backing = DequeBuffer.createFrom(elements) //all the other initializers funnel through this one
    }
    
    public init() {
        self.init(elements:EmptyCollection())
    }
    
    public init<Sequence:SequenceType where Sequence.Generator.Element == Element>(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..<index, with: CollectionOfOne(newValue)) //CollectionOfOne is handy here to avoid needing another overload of replaceRange
        }
    }
    
    // replaceRange() is magical. Implement it, and practically everything else on RangeReplaceableCollectionType appears on your type in a puff of smoke
    public mutating func replaceRange<Collection : CollectionType where Collection.Generator.Element == Element>(replacedRange: Range<Int>, 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<C:CollectionType where C.Generator.Element == Int, C.Index == Int>(range:C) { //using CollectionType rather than Range here because sometimes I'm checking Slice<Range> 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<Sequence:SequenceType where Sequence.Generator.Element == (Int, Int)>(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<Sequence:SequenceType where Sequence.Generator.Element == Int>(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<Int>, distance:Int) -> Zip2Sequence<LazyMapCollection<Range<Int>, Int>, LazyMapCollection<LazyMapCollection<Range<Int>, 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<Range<Int>>) {
        if range.isEmpty { return }
        _checkRange(range)
        
        _shift(_calculateShifts(0..<range.startIndex, distance: range.count).reverse()) //we reverse the list of shifts because we want to shift higher indices first
        _headIndex = _normalizeIndex(range.count)
    }
    
    // Same as above, but from the other end. Instead of yielding [_, a, c] this would yield [a, c, _]
    private mutating func _consumeElementsInRangeByShiftingFromBack(range:Slice<Range<Int>>) {
        if range.isEmpty { return }
        _checkRange(range)
        
        _shift(_calculateShifts((range.endIndex - 1)..<count, distance: -range.count))
    }
    
    // This does the inverse of _consume*, it shifts elements to make room, rather than to fit into newly freed room. So if this were called on the [_, a, c] result yielded above, and passed arguments of index 1 and distance 1, then it would result in [a, _, c], leaving a nice blank spot for a new value to land in from replaceRange()
    private mutating func _expandToAddElementsAtIndexByShiftingTowardsFront(index:Int, distance:Int) {
        if distance == 0 { return }
        _checkIndex(index)
        
        _headIndex = _normalizeIndex(-distance)
        _shift(_calculateShifts(0...index, distance: -distance))
    }
    
    // Fourth verse, same as the third, [a, c, _] turns into [a, _, c]
    private mutating func _expandToAddElementsAtIndexByShiftingTowardsBack(index:Int, distance:Int) {
        if index == endIndex || distance == 0 { return }
        _checkIndex(index)
        
        precondition(index + distance <= endIndex + distance)
        _shift(_calculateShifts(index..<count, distance: distance).reverse())
    }
}

//For testing... this struct proxies an Array and a Deque and makes sure that doing the same operation on each yields the same result
public struct RoboticArm<Element : Equatable> : MutableCollectionType, RangeReplaceableCollectionType, ArrayLiteralConvertible {
    var robot:[Element]
    var arm:Deque<Element>
    
    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<Collection : CollectionType where Collection.Generator.Element == Element>(subRange: Range<Int>, 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))