Queue.swift

//
//  Queue.swift
//  NTBSwift
//
//  Created by Kåre Morstøl on 11/07/14.
//
//  Using the "Two-Lock Concurrent Queue Algorithm" from http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html#tlq, without the locks.


// should be an inner class of Queue, but inner classes and generics crash the compiler, SourceKit (repeatedly) and occasionally XCode. 
class _QueueItem<T> {
	let value: T!
	var next: _QueueItem?	
	
	init(_ newvalue: T?) {
		self.value = newvalue
	}
}

///
/// A standard queue (FIFO - First In First Out). Supports simultaneous adding and removing, but only one item can be added at a time, and only one item can be removed at a time.
///
public class Queue<T> {
	
	typealias Element = T
	
	var _front: _QueueItem<Element>
	var _back: _QueueItem<Element>
	
	public init () {
		// Insert dummy item. Will disappear when the first item is added.
		_back = _QueueItem(nil)
		_front = _back
	}
	
	/// Add a new item to the back of the queue.
	public func enqueue (value: Element) {
		_back.next = _QueueItem(value)
		_back = _back.next!
	}
	
	/// Return and remove the item at the front of the queue.
	public func dequeue () -> Element? {
		if let newhead = _front.next {
			_front = newhead
			return newhead.value
		} else {
			return nil
		}
	}
	
	public func isEmpty() -> Bool {
		return _front === _back
	}
}

QueueTests.swift

//
//  QueueTests.swift
//
//  Created by Kåre Morstøl on 11/07/14.
//  Copyright (c) 2014 NotTooBad Software. All rights reserved.
//

import XCTest 
import NTBSwift

class QueueTests: XCTestCase {
    
    func testAdd1ToQueue() {
		let sut = Queue<String>()
		sut.enqueue("1")
    }

	func testAddSeveralToQueue() {
		let sut = Queue<String>()
		XCTAssert(sut.isEmpty())
		sut.enqueue("1")
		sut.enqueue("1")
		XCTAssertFalse(sut.isEmpty())
		sut.enqueue("1")
		sut.enqueue("1")
		sut.enqueue("1")
	}
	
	func testRemoveOne() {
		let sut = Queue<String>()
		sut.enqueue("1")
		sut.enqueue("")
		sut.enqueue("")
		sut.enqueue("")
		let thefirstone = sut.dequeue()
		
		XCTAssertNotNil(thefirstone)
		XCTAssertEqual(thefirstone!, "1")
	}
	
	func testRemoveAll() {
		let sut = Queue<String>()
		sut.enqueue("1")
		sut.enqueue("2")
		sut.enqueue("3")
		sut.enqueue("4")

		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssertEqual(sut.dequeue()!, "3")
		XCTAssertEqual(sut.dequeue()!, "4")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())
		XCTAssertNil(sut.dequeue())
		XCTAssert(sut.isEmpty())
	}
	
	func testGenerics() {
		let sut = Queue<Int>()
		sut.enqueue(1)
		sut.enqueue(2)
		sut.enqueue(3)
		sut.enqueue(4)
		
		XCTAssertEqual(sut.dequeue()!, 1)
		XCTAssertEqual(sut.dequeue()!, 2)
		XCTAssertEqual(sut.dequeue()!, 3)
		XCTAssertEqual(sut.dequeue()!, 4)
	}
	
	func  testAddNil() {
		let sut = Queue<Int?>()
		sut.enqueue(nil)
		XCTAssertNil(sut.dequeue()?)
		
		sut.enqueue(2)
		sut.enqueue(nil)
		sut.enqueue(4)
		
		XCTAssertEqual(sut.dequeue()!!, 2)
		XCTAssertNil(sut.dequeue()?)
		XCTAssertEqual(sut.dequeue()!!, 4)
	}

	func testAddAfterEmpty() {
		let sut = Queue<String>()
		
		sut.enqueue("1")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertNil(sut.dequeue())
		
		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())
	}
	
	func testAddAndRemoveChaotically() {
		let sut = Queue<String>()
		
		sut.enqueue("1")
		XCTAssertFalse(sut.isEmpty())
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())

		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssert(sut.isEmpty())
		XCTAssertNil(sut.dequeue())

		sut.enqueue("1")
		sut.enqueue("2")
		XCTAssertEqual(sut.dequeue()!, "1")
		sut.enqueue("3")
		sut.enqueue("4")
		XCTAssertEqual(sut.dequeue()!, "2")
		XCTAssertEqual(sut.dequeue()!, "3")
		XCTAssertFalse(sut.isEmpty())
		XCTAssertEqual(sut.dequeue()!, "4")
		XCTAssertNil(sut.dequeue())
		XCTAssertNil(sut.dequeue())
	}

	func testConcurrency() {
		let sut = Queue<Int>()
		let numberofiterations = 2_000_00

		let addingexpectation = expectationWithDescription("adding completed")
		let addingqueue = dispatch_queue_create( "adding", DISPATCH_QUEUE_SERIAL)
		dispatch_async(addingqueue)  {
			for i in  1...numberofiterations {
				sut.enqueue(i)
			}
			addingexpectation.fulfill()
		}
		
		let deletingexpectation = expectationWithDescription("deleting completed")
		let deletingqueue = dispatch_queue_create( "deleting", DISPATCH_QUEUE_SERIAL)
		dispatch_async(deletingqueue)  {
			for (var i=1; i <= numberofiterations; 0) {
				if let result = sut.dequeue() {
					XCTAssertEqual(result, i)
					i++
				} else {
					println(" pausing deleting for one second")
					sleep(CUnsignedInt(1))
				}
			}
			deletingexpectation.fulfill()
		}
		
		waitForExpectationsWithTimeout( 600, handler:  nil)
	} 
}