import random

class TimeStamp:
    def __init__(self):
        self.values_dict = {}
        self.timestamps_dict = {} 

    #  Set TimeStamp data variables
    def set_value(self, key, value, timestamp):
        if key in self.values_dict:
            if value != self.values_dict[key][len(self.values_dict[key])-1]:
                self.values_dict[key].append(value)
                self.timestamps_dict[key].append(timestamp)
        else:
            self.values_dict[key] = [value]
            self.timestamps_dict[key] = [timestamp]

    # Find the index of right most occurrence of the given timestamp
    # using binary search
    def search_index(self, n, key, timestamp):
        left = 0
        j=right = n
        mid = 0

        while left < right:
            mid = (left+right) >> 1
            if self.timestamps_dict[key][mid] <= timestamp:
                left = mid + 1
            else:
                right = mid
        return left-1

    # Get time_stamp data variables
    def get_value(self, key, timestamp):
        if key not in self.values_dict:
            return ""
        else:
            index = self.search_index(len(self.timestamps_dict[key]),
                                      key, timestamp)
            if index > -1:
                return self.values_dict[key][index]

            return ""


# Driver code
def main():
    ts = TimeStamp()
    num = 1
    random_value = 0
    input = (
            ("course", "OOP", 3),
            ("course", "PF", 5),
            ("course", "OS", 7),
            ("course", "ALGO", 9),
            ("course", "DB", 10)
        )

    for i in input:
        print(num, ".\tAdd value: (", '"', i[0], '"',
                   ", ", '"', i[1], '"', ", ", i[2], ")", sep="")
        ts.set_value(i[0], i[1], i[2])
        random_value = random.randint(0, 10)
        print("\n\tGet value for:")
        print("\t\tKey = course  \n\t\tTimestamp = ", random_value, sep="")
        print("\n\tReturned value = ", '"',
              ts.get_value("course", random_value), '"', sep="")
        num += 1
        print("-" * 100, sep="")


if __name__ == "__main__":
    main()