public struct PointerKeyedMap<Key, Value> where Key: AnyObject {

    public typealias Element = (key: Key, value: Value)

    public subscript(key: Key) -> Value? {
        get {
            guard capacity > 0 else { return nil }
            let i = bucketIndex(for: key)
            return buckets[i].first(where: { $0.key === key })?.value
        }

        set {
            if newValue != nil {
                guard capacity > 0 else {
                    self.buckets = [[(key: key, value: newValue!)]]
                    return
                }

                let i = bucketIndex(for: key)
                if let j = buckets[i].index(where: { $0.key === key }) {
                    buckets[i][j] = (key: key, value: newValue!)
                } else {
                    if Double(count) > 0.75 * Double(capacity) {
                        reserveCapacity(n: capacity * 2)
                    }
                    buckets[i].append((key: key, value: newValue!))
                }
            } else {
                guard capacity > 0 else { return }
                let i = bucketIndex(for: key)
                if let j = buckets[i].index(where: { $0.key === key }) {
                    buckets[i].remove(at: j)
                }
            }
        }
    }

    public mutating func reserveCapacity(n: Int) {
        var newBuckets: [[Element]] = Array.init(repeating: [], count: n)
        for pair in self {
            let i = bucketIndex(for: pair.key, capacity: n)
            newBuckets[i].append(pair)
        }
        self.buckets = newBuckets
    }

    public var count: Int {
        return buckets.reduce(0) { $0 + $1.count }
    }

    public var capacity: Int {
        return buckets.count
    }

    private func bucketIndex(for key: Key, capacity: Int? = nil) -> Int {
        var ref = key
        return withUnsafePointer(to: &ref) { Int(bitPattern: $0) } % (capacity ?? self.capacity)
    }

    private var buckets: [[Element]]

}

extension PointerKeyedMap: Collection {

    public typealias Index = PointerKeyedMapIndex

    public subscript(i: Index) -> Element {
        return buckets[i.bucketIndex][i.cellIndex]
    }

    public var startIndex: Index {
        if let i = buckets.index(where: { !$0.isEmpty }) {
            return Index(bucketIndex: i, cellIndex: 0)
        } else {
            return endIndex
        }
    }

    public var endIndex: Index {
        return Index(bucketIndex: buckets.count, cellIndex: 0)
    }

    public func index(after i: Index) -> Index {
        if i.cellIndex < (buckets[i.bucketIndex].count - 1) {
            return Index(bucketIndex: i.bucketIndex, cellIndex: i.cellIndex + 1)
        } else if let i = buckets.dropFirst(i.bucketIndex + 1).index(where: { !$0.isEmpty }) {
            return Index(bucketIndex: i, cellIndex: 0)
        } else {
            return endIndex
        }
    }

}

extension PointerKeyedMap: ExpressibleByDictionaryLiteral {

    public init(dictionaryLiteral elements: (Key, Value)...) {
        self.buckets = Array(repeating: [], count: elements.count * 2)
        for (key, value) in elements {
            self[key] = value
        }
    }

}

public struct PointerKeyedMapIndex: Comparable {

    fileprivate let bucketIndex: Int
    fileprivate let cellIndex: Int

    public static func < (lhs: PointerKeyedMapIndex, rhs: PointerKeyedMapIndex) -> Bool {
        return lhs.bucketIndex == rhs.bucketIndex
            ? lhs.cellIndex < rhs.cellIndex
            : lhs.bucketIndex < rhs.bucketIndex
    }

}