from time import perf_counter as clock

t0 = clock()

class Node:
    """Class to define BST Node"""
    def __init__(self, unx_time, ip_adrs):
        """Assign values and 2 children"""
        self.time = unx_time
        self.adrs = ip_adrs
        self.left = None
        self.right = None

    def __repr__(self):
        """Function to Enable Printing Node"""
        return str(self.time) + " " + self.adrs


class BST:
    """Function to define binary tree"""
    def __init__(self):
        """Define Root Node"""
        self.root = None

    def __repr__(self):
        """Function to Print Tree as Sorted List"""
        self.sorted = []
        self.get_inorder(self.root)
        return str(self.sorted)

    def get_inorder(self, node):
        """Helper Function for __repr__"""
        if node:
            self.get_inorder(node.left)
            self.sorted.append(str(node.time) + " " + str(node.adrs))
            self.get_inorder(node.right)

    def add(self, time, adrs):
        """Tree Builder Function"""
        if not self.root:
            self.root = Node(time, adrs)
        else:
            self._add(self.root, time, adrs)

    def _add(self, node, time, adrs):
        """Helper for Tree Builder Function"""
        if time <= node.time:
            if node.left:
                self._add(node.left, time, adrs)
            else:
                node.left = Node(time, adrs)
        else:
            if node.right:
                self._add(node.right, time, adrs)
            else:
                node.right = Node(time, adrs)

    def lookup_LTE(self, node, time, prev_ans):
        """Function to Execute LTE Query"""
        if node == None:
            #print(prev_ans)
            f.write(prev_ans + "\n")
            return
        elif time == node.time:
            #print(node.adrs)
            f.write(node.adrs + "\n")
            return
        elif time < node.time:
            self.lookup_LTE(node.left, time, prev_ans)
        else:
            prev_ans = node.adrs
            self.lookup_LTE(node.right, time, prev_ans)


    def lookup_GTE(self, node, time, prev_ans):
        """Function to Execute GTE Query"""
        if node == None:
            #print(prev_ans)
            f.write(prev_ans + "\n")
            return
        elif time == node.time:
            #print(node.adrs)
            f.write(node.adrs + "\n")
            return
        elif time < node.time:
            prev_ans = node.adrs
            self.lookup_GTE(node.left, time, prev_ans)
        else:
            self.lookup_GTE(node.right, time, prev_ans)

    def _BTW(self, node, time, prev_time, prev_ans):
        """Helper Function for BTW Query"""
        if node == None:
            return prev_time, prev_ans

        if time == node.time:
            prev_time, prev_ans = node.time, node.adrs
        elif time < node.time:
            prev_ans = node.adrs
            prev_time = node.time
            prev_time, prev_ans = self._BTW(node.left, time,
                                            prev_time, prev_ans)
        else:
            prev_time, prev_ans = self._BTW(node.right, time,
                                            prev_time, prev_ans)
        return prev_time, prev_ans

    def lookup_BTW(self, time1, time2, prev_arr):
        """Function for BTW Query"""
        time, adrs = self._BTW(bst.root, time1, time1, "")
        if time > time2:
            f.write("\n")
        else:
            for rec in log:
                tim = rec[0]
                if tim < time1 : continue
                if tim > time2 : break
                prev_arr.append(rec[1])

            f.write(" ".join(prev_arr) + "\n")





# Input Data
log_file = '2019-Nov-Wed-1572989950_log.txt'
query_file = '2019-Nov-Wed-1572989950_queries.txt'

# Read log file and sort on time
log = []
with open(log_file, 'r') as infile:
    for rec in infile:
        rec1 = rec.strip().split()
        rec1[0] = int(rec1[0])
        log.append(rec1)

log.sort(key=lambda x: int(x[0]))

# Read queries file
queries = []
with open(query_file, 'r') as infile1:
    for rec in infile1:
        queries.append(rec.strip().split())


# Build Tree
bst = BST()
for rec in log:
    bst.add(rec[0], rec[1])

# Build Balanced Tree
bst = BST()
def BalancedBST(arr):
    if not arr : return
    mid = len(arr) // 2
    rec = arr[mid]
    bst.add(int(rec[0]), rec[1])
    BalancedBST(arr[:mid])
    BalancedBST(arr[mid+1:])

BalancedBST(log)

assert len(str(bst).strip().split(", ")) == len(log) #Ensure all ok

# Raise Queries
f = open("solution.txt", "w")
for query in queries:
    #print(query)
    if query[0] == "LTE":
        bst.lookup_LTE(bst.root, int(query[1]), "\n")
    elif query[0] == "GTE":
        bst.lookup_GTE(bst.root, int(query[1]), "\n")
    elif query[0] == "BTW":
        time1, time2 = int(query[1]), int(query[2])
        if time1 > time2:
            time1, time2 = time2, time1
        bst.lookup_BTW(time1, time2, [])
    else:
        f.write("Unknown command: " + query[0] + "\n")
f.close()

print("Time required: %.5f" % (clock()-t0))