Conceptual Implementations of Swift's Array and Dictionary

gistfile1.swift

struct Array2<T> {
	var buffer: Buffer<T>
	var count: Int
	
	init() {
		buffer = Buffer()
		count = 0
	}
	
	init(_ elements: T...) {
		self.init()
		
		for element in elements {
			append(element)
		}
	}
	
	subscript(index: Int) -> T {
		get {
			return buffer[index]!
		}
		nonmutating set {
			buffer[index] = newValue
		}
	}
	
	mutating func append(newElement: T) {
		if (count == buffer.count) {
			let oldBuffer = buffer
			
			buffer = Buffer(max(buffer.count * 2, 1))
			for index in 0..count {
				buffer[index] = oldBuffer[index]
			}
		}
		
		buffer[count++] = newElement
	}
}

struct Dictionary2<K: Hashable, V> {
	var buckets: Buffer<List<(K, V)>>
	var count: Int
	
	init() {
		buckets = Buffer()
		count = 0
	}
	
	subscript(key: K) -> V? {
		get {
			let bucket = buckets[key.hashValue % buckets.count]
			if let entries = bucket {
				for entry in entries {
					if key == entry.0 {
						return entry.1
					}
				}
			}
			
			return nil
		}
		set {
			if (count >= buckets.count * 3 / 4) {
				let oldBuckets = buckets
				buckets = Buffer<List<(K, V)>>(buckets.count * 2 + 1)
				for bucketIndex in 0..oldBuckets.count {
					let bucket = oldBuckets[bucketIndex]
					if let entries = bucket {
						for entry in entries {
							self[entry.0] = entry.1
						}
					}
				}
			}
			
			let bucketIndex = key.hashValue % buckets.count
			let bucket = buckets[bucketIndex]
			if let entries = bucket {
				for (index, entry) in enumerate(entries) {
					if key == entry.0 {
						if let nonNilNewValue = newValue {
							entries[index] = (key, nonNilNewValue)
							return
						} else {
							entries.removeAtIndex(index)
							count--
							return
						}
					}
				}
				
				if let nonNilNewValue = newValue {
					entries.append((key, nonNilNewValue))
					count++
				}
			} else {
				if let nonNilNewValue = newValue {
					buckets[bucketIndex] = List<(K, V)>((key, nonNilNewValue))
					count++
				}
			}
		}
	}
}

class Buffer<T> {
	let array: Array<T?>
	
	init(_ count: Int) {
		self.array = Array(count: count, repeatedValue: nil)
	}
	
	convenience init() {
		self.init(0)
	}
	
	subscript(index: Int) -> T? {
		get {
			return array[index]
		}
		set {
			array[index] = newValue
		}
	}
	
	var count: Int {
		get {
			return array.count
		}
	}
}