Created
August 25, 2015 11:00
-
-
Save Paczesiowa/cf74ecee00326d47182e to your computer and use it in GitHub Desktop.
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
import collections | |
import csv | |
Interval = collections.namedtuple('Interval', 'start end track') | |
Switch = collections.namedtuple('Switch', 'timestamp track') | |
class Intervals(object): | |
def __init__(self, default_track): | |
self._default_track = default_track | |
self._switches = [Switch(0, default_track)] | |
def __iter__(self): | |
return iter(self._switches) | |
def _delete(self, start, end): | |
''' | |
Delete all switches that occur between | |
start (inclusive) and end (exclusive). | |
O(#switches_inside) | |
''' | |
self._switches = [switch for switch in self._switches | |
if not (start <= switch.timestamp < end)] | |
def _insert(self, new_switch): | |
''' | |
Insert a new switch (overriding if there was one at the same time). | |
O(#switches_inside) | |
''' | |
for i, switch in enumerate(self._switches): | |
if switch.timestamp == new_switch.timestamp: | |
self._switches[i] = new_switch | |
return | |
elif switch.timestamp > new_switch.timestamp: | |
self._switches.insert(i, new_switch) | |
return | |
self._switches.append(new_switch) | |
def track_at(self, timestamp): | |
''' | |
Return track name that should be played at timestamp. | |
O(#switches_inside) | |
''' | |
result = self._default_track | |
for switch in self._switches: | |
if switch.timestamp > timestamp: | |
break | |
result = switch.track | |
return result | |
def insert(self, interval): | |
''' | |
Insert new interval. | |
O(#switches_inside) | |
''' | |
after_interval_track = self.track_at(interval.end) | |
self._delete(interval.start, interval.end) | |
self._insert(Switch(interval.start, interval.track)) | |
self._insert(Switch(interval.end, after_interval_track)) | |
csv_example = '''\ | |
A,0,10 | |
E,15,35 | |
D,30,40 | |
C,20,30 | |
B,10,20''' | |
if __name__ == '__main__': | |
intervals_list = [] | |
for row in csv.reader(csv_example.split('\n')): | |
intervals_list.append(Interval(start=int(row[1]), | |
end=int(row[2]), | |
track=row[0])) | |
intervals = Intervals(intervals_list[0].track) | |
for interval in reversed(intervals_list): | |
intervals.insert(interval) | |
print list(intervals) | |
A, B, C, D, E = ('A', 'B', 'C', 'D', 'E') | |
def test(intervals, result): | |
changes = Intervals(A) | |
for interval in intervals: | |
changes.insert(interval) | |
if changes._switches != result: | |
print 'FAIL' | |
print intervals | |
print result | |
print changes._switches | |
test([Interval(10, 20, B)], | |
[(0, A), (10, B), (20, A)]) | |
test([Interval(10, 20, B), Interval(5, 9, C)], | |
[(0, A), (5, C), (9, A), (10, B), (20, A)]) | |
test([Interval(10, 20, B), Interval(5, 10, C)], | |
[(0, A), (5, C), (10, B), (20, A)]) | |
test([Interval(10, 20, B), Interval(5, 11, C)], | |
[(0, A), (5, C), (11, B), (20, A)]) | |
test([Interval(10, 20, B), Interval(20, 30, C), | |
Interval(30, 40, D), Interval(15, 35, E)], | |
[(0, A), (10, B), (15, E), (35, D), (40, A)]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment