MyDictionary.swift

//
// Reference:
// https://khanlou.com/2016/07/implementing-dictionary-in-swift/
//

import Foundation

class Item<Key: Hashable, Value> {
    let key: Key
    var value: Value
    var next: Item?
    init(key: Key, value: Value) {
        self.key = key
        self.value = value
        self.next = nil
    }
}

extension Item: CustomStringConvertible {
    var description: String {
        return "[\(key): \(value)]"
    }
}

class LinkedList<Key: Hashable, Value> {
    var head: Item<Key, Value>?

    func addItem(key: Key, value: Value) {
        let item = Item(key: key, value: value)
        item.next = head
        head = item
    }

    func deleteItem(key: Key) -> Item<Key, Value>? {
        guard let head = head else { return nil }

        if head.key == key {
            self.head = head.next
            head.next = nil
            return head
        }

        var previous: Item = head
        var current = head.next

        while current != nil, current!.key != key {
            previous = current!
            current = current!.next
        }

        if current != nil {
            previous.next = current!.next
            current!.next = nil
            return current
        }

        return nil
    }
}

extension LinkedList: Sequence {
    func makeIterator() -> LinkedListIterator<Key, Value> {
        return LinkedListIterator(head)
    }
}

struct LinkedListIterator<Key: Hashable, Value>: IteratorProtocol {
    typealias Element = Item<Key, Value>

    var current: Element?
    init(_ head: Element?) {
        self.current = head
    }

    mutating func next() -> Element? {
        let element = current
        current = current?.next
        return element
    }
}

struct MyDictionary<Key, Value> where Key : Hashable {
    private var storage: [LinkedList<Key, Value>?] = Array(repeating: nil, count: 8)
    private(set) var count: Int = 0
    private let maxLoadFactor = 0.8
    private var loadFactor: Double {
        return Double(storage.compactMap { $0 }.count) / Double(storage.count)
    }

    var isEmpty: Bool {
        count == 0
    }

    subscript(key: Key) -> Value? {
        get {
            let index = abs(key.hashValue) % storage.capacity

            guard let list = storage[index] else { return nil }
            for item in list where item.key == key {
                return item.value
            }

            return nil
        }

        set {
            let index = abs(key.hashValue) % storage.capacity
            if let value = newValue {
                update(key: key, value: value, at: index)
                resizeIfNeeded()
            } else {
                delete(key: key, at: index)
            }
        }
    }

    private mutating func delete(key: Key, at index: Int) {
        guard let list = storage[index] else { return }
        if list.deleteItem(key: key) != nil {
            count -= 1
        }
        if list.head == nil {
            storage[index] = nil
        }
    }

    private mutating func update(key: Key, value: Value, at index: Int) {
        let list: LinkedList<Key, Value>
        if storage[index] == nil {
            list = .init()
            storage[index] = list
        } else {
            list = storage[index]!
        }
        if list.deleteItem(key: key) != nil {
            count -= 1
        }
        list.addItem(key: key, value: value)
        count += 1
    }

    private mutating func resizeIfNeeded() {
        guard loadFactor >= maxLoadFactor else { return }

        print("Resizing storage...")
        let temp = storage.compactMap { $0 }
        storage = Array(repeating: nil, count: storage.count * 2)
        count = 0

        var item: Item<Key, Value>?
        for list in temp {
            item = list.head
            while item != nil {
                self[item!.key] = item!.value
                item = item!.next
            }
        }
    }

    func dump() {
        print("Current load factor: \(loadFactor)")
        for item in self {
            print(item, terminator: " -> ")
        }
    }
}

extension MyDictionary: Sequence {
    func makeIterator() -> MyDictionaryIterator<Key, Value> {
        return MyDictionaryIterator(storage)
    }
}

struct MyDictionaryIterator<Key: Hashable, Value>: IteratorProtocol {
    typealias Element = Item<Key, Value>
    let storage: [LinkedList<Key, Value>]
    var currentItem: Element?
    var currentListIndex: Int

    init(_ storage: [LinkedList<Key, Value>?]) {
        self.storage = storage.compactMap { $0 }
        currentListIndex = 0
        if currentListIndex < self.storage.count-1 {
            currentItem = self.storage[currentListIndex].head
        }
    }

    mutating func next() -> Element? {
        let element = currentItem
        if currentItem?.next != nil {
            currentItem = currentItem?.next
        } else if currentListIndex < storage.count-1 {
            currentListIndex += 1
            currentItem = self.storage[currentListIndex].head
        } else {
            currentItem = nil
        }
        return element
    }
}

var dict = MyDictionary<Int, String>()
dict[300] = "Ooops"
dict[200] = "OK"
dict[400] = "test"
dict[200] = nil
dict[100] = "100"
dict[1] = "1"
dict[2] = "2"
dict[3] = "3"
dict[4] = "4"
dict[5] = "5"
dict.count
dict.isEmpty
dict[300]
dict[200]
dict[400]
dict.dump()