Last active
October 17, 2019 13:24
-
-
Save horothesun/3162c0028c450b472a1ee7cc552d8e0d to your computer and use it in GitHub Desktop.
`set_timer2` is implemented by `Scheduler.setTimer(waitForMillis:task:)`. A priority-queue's used to keep track of the scheduled tasks by priority (absolute start time).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
final class TimeProviderDefault: TimeProvider { | |
func now() -> TimeInterval { Date().timeIntervalSince1970 } | |
} | |
let scheduler = SchedulerDefault( | |
singleSlotSetTimer: set_timer(waitForMillis:task:), | |
timeProvider: TimeProviderDefault() | |
) | |
scheduler.setTimer(waitForMillis: 1_000, task: { /* ... */ }) | |
// wait 500 ms | |
scheduler.setTimer(waitForMillis: 700, task: { /* ... */ }) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// TODO: move 'elements' from array to min-heap | |
final class PriorityQueue<Element: Equatable, Priority> { | |
private var elements = [Element]() | |
private let priorityForElement: (Element) -> Priority | |
private let priorityGreaterThan: (Priority, Priority) -> Bool | |
init( | |
priorityForElement: @escaping (Element) -> Priority, | |
priorityGreaterThan: @escaping (Priority, Priority) -> Bool | |
) { | |
self.priorityForElement = priorityForElement | |
self.priorityGreaterThan = priorityGreaterThan | |
} | |
// O(1) | |
func peek() -> Element? { elements.first } | |
// O(log(n)) with min-heap | |
func insert(_ element: Element) { | |
elements.append(element) | |
elements.sort { (lhs, rhs) -> Bool in | |
priorityGreaterThan(priorityForElement(lhs), priorityForElement(rhs)) | |
} | |
} | |
// O(log(n)) with min-heap | |
func removeNext() -> Element? { | |
let next = peek() | |
elements = Array(elements.dropFirst()) | |
return next | |
} | |
// O(n) with min-heap | |
func prioritisedElements() -> [Element] { elements } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
protocol Scheduler { | |
func setTimer(waitForMillis: UInt, task: @escaping () -> Void) | |
} | |
protocol TimeProvider { | |
func now() -> TimeInterval | |
} | |
final class Event: Identifiable, Equatable { | |
let excecuteOn: TimeInterval // absolute time task will be executed | |
let task: () -> Void | |
init(excecuteOn: TimeInterval, task: @escaping () -> Void) { | |
self.excecuteOn = excecuteOn | |
self.task = task | |
} | |
static func == (lhs: Event, rhs: Event) -> Bool { lhs.id == rhs.id } | |
} | |
final class SchedulerDefault: Scheduler { | |
private let eventsQueue = PriorityQueue<Event, TimeInterval>( | |
priorityForElement: { $0.excecuteOn }, | |
priorityGreaterThan: < | |
) | |
private let singleSlotSetTimer: (_ waitForMillis: UInt, _ task: @escaping () -> Void) -> Void | |
private let timeProvider: TimeProvider | |
init( | |
singleSlotSetTimer: @escaping (UInt, @escaping () -> Void) -> Void, | |
timeProvider: TimeProvider | |
) { | |
self.singleSlotSetTimer = singleSlotSetTimer | |
self.timeProvider = timeProvider | |
} | |
func setTimer(waitForMillis: UInt, task: @escaping () -> Void) { | |
dequeueStartedEvents() | |
enqueue(task, waitForMillis) | |
accumulateTasks()() | |
} | |
private func dequeueStartedEvents() { | |
let now = timeProvider.now() | |
while let nextEvent = eventsQueue.peek(), | |
nextEvent.excecuteOn <= now { | |
_ = eventsQueue.removeNext() | |
} | |
} | |
private func enqueue(_ task: @escaping () -> Void, _ waitForMillis: UInt) { | |
let excecuteOn = timeProvider.now() + TimeInterval(Double(waitForMillis) / 1_000.0) | |
eventsQueue.insert(Event(excecuteOn: excecuteOn, task: task)) | |
} | |
// builds an accumulated task from the remaining events according to priority | |
// (foldRight over events sorted by priority) | |
private func accumulateTasks() -> () -> Void { | |
let prioritisedEvents = eventsQueue.prioritisedElements() | |
let executionTimes = prioritisedEvents.map { $0.excecuteOn } | |
let relativeWaitingMillis = zip( | |
executionTimes, | |
[timeProvider.now()] + executionTimes | |
).map { UInt(1_000 * ($0.0 - $0.1)) } | |
guard let lowestPriorityEvent = prioritisedEvents.last, | |
let lastRelativeWaitingMillis = relativeWaitingMillis.last else { return { } } | |
let lowestPrioritySchedule = { [weak self] in | |
guard let self = self else { return } | |
self.singleSlotSetTimer(lastRelativeWaitingMillis, lowestPriorityEvent.task) | |
} | |
return zip(prioritisedEvents, relativeWaitingMillis) | |
.reversed() | |
.dropFirst() | |
.reduce(lowestPrioritySchedule) { [weak self] (accumulator, eventAndRelativeWaitingMillis) -> (() -> Void) in | |
guard let self = self else { return { } } | |
let (event, relativeWaitingMillis) = eventAndRelativeWaitingMillis | |
return { | |
self.singleSlotSetTimer(relativeWaitingMillis) { | |
accumulator() | |
event.task() | |
} | |
} | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Assumption: in the following scenario | |
// | |
// set_timer(1000, task_1) // task_1'll take 20 seconds to complete | |
// // waiting 2 seconds... | |
// set_timer(500, task_2) // task_2'll take 5 seconds to complete | |
// // waiting 90 seconds... | |
// | |
// both task_1 and task_2 will be executed, | |
// even if task_2's been scheduled while task_1 was still executing. | |
// | |
func set_timer(waitForMillis: UInt, task: @escaping () -> Void) { | |
// OS provided | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment