IntervalSort

"""
Class to sort intervals.

A collection of intervals is sorted:
(1) in increasing order by start index
(2) in increasing order by end index

Sample data:
data = [(1, 2), (0, 1), (0, 3), (5, 9), (1, 4), (1, 2), (2, 5), (5, 8), (3, 6)]
"""


class IntervalSort:
    def __init__(self, data=None):
        self.data = data

    def sort(self):
        self._start_sort()
        self._end_sort()
        data_sorted = list()
        for start in self.d:
            ends = self.d[start]
            for e in ends:
                data_sorted.append((start, e))
        return data_sorted

    #
    # Helpers
    #

    def _start_sort(self):
        d = dict()
        for pair in self.data:
            start, end = pair[0], pair[1]
            if start not in d:
                end_values = [end]
                d[start] = end_values
            else:
                end_values = d[start]
                end_values.append(end)
                d[start] = end_values
        keys = d.keys()
        keys = sorted(keys)
        d_sorted = dict()
        for k in keys:
            d_sorted[k] = d[k]
        self.d = d_sorted

    def _end_sort(self):
        for start in self.d:
            values = self.d[start]
            values.sort()
            self.d[start] = values