0001    //
0002    //  PriorityQueue.swift
0003    //  Rx
0004    //
0005    //  Created by Krunoslav Zaher on 12/27/15.
0006    //  Copyright © 2015 Krunoslav Zaher. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    struct PriorityQueue
PriorityQueue.swift:116
extension PriorityQueue : CustomDebugStringConvertible {
VirtualTimeScheduler.swift:25
    private var _schedulerQueue : PriorityQueue<VirtualSchedulerItem<VirtualTime>>
VirtualTimeScheduler.swift:53
        _schedulerQueue = PriorityQueue(hasHigherPriority: {
<Element
PriorityQueue.swift:12
    private let _hasHigherPriority: (Element, Element) -> Bool
PriorityQueue.swift:12
    private let _hasHigherPriority: (Element, Element) -> Bool
PriorityQueue.swift:13
    private var _elements = [Element]()
PriorityQueue.swift:15
    init(hasHigherPriority: (Element, Element) -> Bool) {
PriorityQueue.swift:15
    init(hasHigherPriority: (Element, Element) -> Bool) {
PriorityQueue.swift:19
    mutating func enqueue(element: Element) {
PriorityQueue.swift:24
    func peek() -> Element? {
PriorityQueue.swift:32
    mutating func dequeue() -> Element? {
PriorityQueue.swift:42
    mutating func remove(element: Element) {
: AnyObject> {
0012        private let _hasHigherPriority
PriorityQueue.swift:16
        _hasHigherPriority = hasHigherPriority
PriorityQueue.swift:74
            if _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) {
PriorityQueue.swift:96
            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:100
            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
: (Element, Element) -> Bool
0013        private var _elements
PriorityQueue.swift:20
        _elements.append(element)
PriorityQueue.swift:21
        bubbleToHigherPriority(_elements.count - 1)
PriorityQueue.swift:25
        return _elements.first
PriorityQueue.swift:29
        return _elements.count == 0
PriorityQueue.swift:43
        for i in 0 ..< _elements.count {
PriorityQueue.swift:44
            if _elements[i] === element {
PriorityQueue.swift:52
        let removingLast = index == _elements.count - 1
PriorityQueue.swift:54
            swap(&_elements[index], &_elements[_elements.count - 1])
PriorityQueue.swift:54
            swap(&_elements[index], &_elements[_elements.count - 1])
PriorityQueue.swift:54
            swap(&_elements[index], &_elements[_elements.count - 1])
PriorityQueue.swift:57
        _elements.popLast()
PriorityQueue.swift:67
        precondition(initialUnbalancedIndex < _elements.count)
PriorityQueue.swift:74
            if _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) {
PriorityQueue.swift:74
            if _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) {
PriorityQueue.swift:75
                swap(&_elements[unbalancedIndex], &_elements[parentIndex])
PriorityQueue.swift:75
                swap(&_elements[unbalancedIndex], &_elements[parentIndex])
PriorityQueue.swift:87
        precondition(initialUnbalancedIndex < _elements.count)
PriorityQueue.swift:96
            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:96
            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:96
            if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:100
            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:100
            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:100
            if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
PriorityQueue.swift:105
                swap(&_elements[highestPriorityIndex], &_elements[unbalancedIndex])
PriorityQueue.swift:105
                swap(&_elements[highestPriorityIndex], &_elements[unbalancedIndex])
PriorityQueue.swift:118
        return _elements.debugDescription
 = [Element]()
0014    
0015        init
VirtualTimeScheduler.swift:53
        _schedulerQueue = PriorityQueue(hasHigherPriority: {
(hasHigherPriority: (Element, Element) -> Bool) {
0016            _hasHigherPriority = hasHigherPriority
0017        }
0018    
0019        mutating func enqueue
VirtualTimeScheduler.swift:129
        _schedulerQueue.enqueue(item)
(element: Element) {
0020            _elements.append(element)
0021            bubbleToHigherPriority(_elements.count - 1)
0022        }
0023    
0024        func peek
PriorityQueue.swift:33
        guard let front = peek() else {
VirtualTimeScheduler.swift:171
        while let front = _schedulerQueue.peek() {
() -> Element? {
0025            return _elements.first
0026        }
0027    
0028        var isEmpty: Bool {
0029            return _elements.count == 0
0030        }
0031    
0032        mutating func dequeue() -> Element? {
0033            guard let front = peek() else {
0034                return nil
0035            }
0036    
0037            removeAt(0)
0038    
0039            return front
0040        }
0041    
0042        mutating func remove
VirtualTimeScheduler.swift:164
            _schedulerQueue.remove(next)
VirtualTimeScheduler.swift:173
                _schedulerQueue.remove(front)
VirtualTimeScheduler.swift:210
            _schedulerQueue.remove(next)
(element: Element) {
0043            for i in 0 ..< _elements.count {
0044                if _elements[i] === element {
0045                    removeAt(i)
0046                    return
0047                }
0048            }
0049        }
0050    
0051        private mutating func removeAt
PriorityQueue.swift:37
        removeAt(0)
PriorityQueue.swift:45
                removeAt(i)
(index: Int) {
0052            let removingLast = index == _elements.count - 1
0053            if !removingLast {
0054                swap(&_elements[index], &_elements[_elements.count - 1])
0055            }
0056    
0057            _elements.popLast()
0058    
0059            if !removingLast {
0060                bubbleToHigherPriority(index)
0061                bubbleToLowerPriority(index)
0062            }
0063        }
0064    
0065        private mutating func bubbleToHigherPriority
PriorityQueue.swift:21
        bubbleToHigherPriority(_elements.count - 1)
PriorityQueue.swift:60
            bubbleToHigherPriority(index)
(initialUnbalancedIndex: Int) {
0066            precondition(initialUnbalancedIndex >= 0)
0067            precondition(initialUnbalancedIndex < _elements.count)
0068    
0069            var unbalancedIndex = initialUnbalancedIndex
0070    
0071            while unbalancedIndex > 0 {
0072                let parentIndex = (unbalancedIndex - 1) / 2
0073    
0074                if _hasHigherPriority(_elements[unbalancedIndex], _elements[parentIndex]) {
0075                    swap(&_elements[unbalancedIndex], &_elements[parentIndex])
0076    
0077                    unbalancedIndex = parentIndex
0078                }
0079                else {
0080                    break
0081                }
0082            }
0083        }
0084    
0085        private mutating func bubbleToLowerPriority
PriorityQueue.swift:61
            bubbleToLowerPriority(index)
(initialUnbalancedIndex: Int) {
0086            precondition(initialUnbalancedIndex >= 0)
0087            precondition(initialUnbalancedIndex < _elements.count)
0088    
0089            var unbalancedIndex = initialUnbalancedIndex
0090            repeat {
0091                let leftChildIndex = unbalancedIndex * 2 + 1
0092                let rightChildIndex = unbalancedIndex * 2 + 2
0093    
0094                var highestPriorityIndex = unbalancedIndex
0095    
0096                if leftChildIndex < _elements.count && _hasHigherPriority(_elements[leftChildIndex], _elements[highestPriorityIndex]) {
0097                    highestPriorityIndex = leftChildIndex
0098                }
0099    
0100                if rightChildIndex < _elements.count && _hasHigherPriority(_elements[rightChildIndex], _elements[highestPriorityIndex]) {
0101                    highestPriorityIndex = rightChildIndex
0102                }
0103    
0104                if highestPriorityIndex != unbalancedIndex {
0105                    swap(&_elements[highestPriorityIndex], &_elements[unbalancedIndex])
0106    
0107                    unbalancedIndex = highestPriorityIndex
0108                }
0109                else {
0110                    break
0111                }
0112            } while true
0113        }
0114    }
0115    
0116    extension PriorityQueue : CustomDebugStringConvertible {
0117        var debugDescription
VirtualTimeScheduler.swift:255
            return self._schedulerQueue.debugDescription
: String {
0118            return _elements.debugDescription
0119        }
0120    }