Skip to content

Instantly share code, notes, and snippets.

@horothesun
Last active October 17, 2019 13:24
Show Gist options
  • Save horothesun/3162c0028c450b472a1ee7cc552d8e0d to your computer and use it in GitHub Desktop.
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).
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: { /* ... */ })
// 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 }
}
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()
}
}
}
}
}
// 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