SegmentTiler

"""
Class to pack or tile segments.

Example data:
data = [
(0, 1), (0, 2), (0, 3), (1, 3), (2, 4), (0, 5)
]

NB: sorted segments are expected (cf. IntervalSort)!
"""

import copy


class SegmentTiler:
    def __init__(self, data):
        self.data = data
        self.n = self.find_max(data)

    def tile(self):
        tilings = list()

        num_pairs = len(self.data)

        for i in range(num_pairs):
            t = list()                          # current tiling

            h = [0] * self.n                    # occupancy mask: init to 0

            pair_i = self.data[i]

            h, _ = self.add_segment(h, pair_i)  # add first segment to occupancy mask
            t.append(pair_i)                    # add first segment to the tiling

            for j in range(num_pairs):
                if i == j:                      # cannot add the same tile twice
                    continue

                pair_j = self.data[j]           # pick next segment

                h_candidate, can_add = self.add_segment(h, pair_j)  # attempt to add the segment to occupancy mask

                if can_add:
                    h = h_candidate             # if success, update occupancy mask
                    t.append(pair_j)            # ... add pair to the current tiling

            tilings.append(t)
        return tilings

    #
    # Helpers
    #

    @staticmethod
    def add_segment(h, pair):
        h_new = copy.deepcopy(h)
        sum_h_before = sum(h)
        h_new[pair[0]:pair[1]] = [1] * (pair[1] - pair[0])
        sum_h_after = sum(h_new)
        if sum_h_after - sum_h_before == (pair[1] - pair[0]):
            can_add = True
        else:
            can_add = False
        return h_new, can_add

    @staticmethod
    def find_max(data):
        n = -1
        for pair in data:
            if pair[1] > n:
                n = pair[1]
        return n