code

protocol PriorityQueue {
    /// check whether the queue has no elements.
    func is_empty() -> Bool
    
    /// returns the highest-priority element but does not modify the queue.
    func peek() -> [UInt8]?
    /// add an element to the queue with an associated priority.
    func insert(_ element: [UInt8], priority: UInt64)
    /// remove the element from the queue that has the highest priority, and return it.
    func pop() -> [UInt8]?
}

struct PriorityQueueImpl {
    var data: [[UInt8]: [UInt8]] = [:]
}

// Do not modify anything above ^^^
// No external dependency including Foundation
extension PriorityQueueImpl {
    // TODO: finish the implementation
    
    func is_empty() -> Bool {
        return data.isEmpty
    }
    
    mutating func peek() -> [UInt8]? {
        guard let highestPriorityKey = getHighestPriorityKey() else {
            return nil
        }
        return data[highestPriorityKey]
    }
    
    mutating func insert(_ element: [UInt8], priority: UInt64) {
        class Counter {
            static var counter: Int = 0
        }
        /// 这里这个时间戳,当数据足够大的时候,我们就不能用 Int 来存储了.我们就需要用链表存储,本地存储,一段一段的存储了.取得时候也会发生相应的变化
        let currentTime = UInt64(Counter.counter)
        Counter.counter += 1
        var priorityBytes = withUnsafeBytes(of: priority.bigEndian) { Array($0) }
        let timestampBytes = withUnsafeBytes(of: currentTime.bigEndian) { Array($0) }
        priorityBytes.append(contentsOf: timestampBytes)
        data[priorityBytes] = element
    }
    
    mutating func pop() -> [UInt8]? {
        guard let highestPriorityKey = getHighestPriorityKey() else {
            return nil
        }
        let hh = data.removeValue(forKey: highestPriorityKey)
        return hh
    }
    
    /**
     得到最高优先级的key
     */
    private func getHighestPriorityKey() -> [UInt8]? {
        
        //1.得到最高的优先级
        guard let priorityNumArray = findHightPriorityKey() else { return nil }
        
        //2.得到最高优先级的key,进入最早的
        guard let key = findTimestapArray(for: Array(priorityNumArray)) else { return nil }
        
        return key
    }
    /**
     找到高优先级的key
     */
    private func findHightPriorityKey() -> [UInt8]? {
        let sortedKeys = data.keys.max(by: { lhs, rhs in
            let lhsPriority = lhs.prefix(8)
            let rhsPriority = rhs.prefix(8)
            return compare(Array(lhsPriority), Array(rhsPriority))
        })
        guard let array = sortedKeys?.prefix(8) else { return nil }
        return Array(array)
    }
    /**
     找到高优先级的最小的时间戳
     */
    private func findTimestapArray(for hightPriorityKeyArray: [UInt8]) -> [UInt8]? {
        let allKey = data.keys.filter { item in
            let lhsPriority = item.prefix(8)
            return lhsPriority == hightPriorityKeyArray.prefix(8)
        }
        let minKeyEnument = allKey.min { lhs, rhs in
            let lhsTimestamp = Array(lhs.suffix(8))
            let rhsTimestamp = Array(rhs.suffix(8))
            return compare(lhsTimestamp, rhsTimestamp)
        }
        guard let minKeyEnument = minKeyEnument else { return nil }
        return Array(minKeyEnument)
    }
    
    /**
     数组中找到相同的元素
     */
    private func filterDuplicateElements(from array:  [Array<UInt8>.SubSequence]) -> [UInt8] {
        var elementCount: [UInt8: Int] = [:]
        
        // 遍历二维数组，记录每个元素的出现次数
        for subArray in array {
            for element in subArray {
                elementCount[element, default: 0] += 1
            }
        }
        
        // 筛选出出现次数超过一次的元素
        var duplicates: [UInt8] = []
        for (element, count) in elementCount {
            if count > 1 {
                duplicates.append(element)
            }
        }
        
        return duplicates
    }
    
    /**
     比较两个数的大小
     */
    private func compare(_ lhs: [UInt8], _ rhs: [UInt8]) -> Bool {
        for i in 0..<min(lhs.count, rhs.count) {
            if lhs[i] != rhs[i] {
                return lhs[i] < rhs[i]
            }
        }
        return lhs.count < rhs.count
    }
}

func it_works() {
    
    print("start - test")
    var queue = PriorityQueueImpl();
    assert(queue.is_empty());
    
    
    queue.insert([0], priority: 5);
    assert(!queue.is_empty());
    assert(queue.peek() == [0]);
    
    queue.insert([1], priority: 10);
    queue.insert([7], priority: 10);
    queue.insert([2], priority: 3);
    queue.insert([3], priority: 4);
    queue.insert([4], priority: 6);
    queue.insert([8], priority: 10);
    
    assert(queue.pop() == [1]);
    assert(queue.pop() == [7]);
    assert(queue.pop() == [8]);
    assert(queue.pop() == [4]);
    assert(queue.pop() == [0]);
    assert(queue.pop() == [3]);
    assert(queue.pop() == [2]);
    
    assert(queue.is_empty());
    print("success - test")
}

it_works()