import json


def build_trace_dict(f, start_time, end_time):
    """Creates a python dictionary that has trace ids as keys and the
    corresponding trace objects as values.

    Input: python file object that points to a file with traces, written by
    htrace-c's local file span receiver.
    The exact format shouldn't concern you if you're using htrace-c correctly.
    https://github.com/apache/incubator-htrace/blob/master/htrace-c.

    Returns: a tuple (trace_dic, root_list), where trace_dic is a dictionary
    containing all traces parsed from the input file object, and root_list is a
    list of traces from trace_dic which have no parents.
    Each value in trace_dic is in the form of another dictionary with the
    folowing keys:
        "begin"   : timestamp of trace start time, microseconds
        "end"     : timestamp of trace end time, microseconds
        "desc"    : description of trace
        "parent"  : trace id of parent trace
        "children": dictionary of child traces, in the same format as trace_dic
    """
    trace_dic = {}
    root_list = []
    for line in f:
        h = json.loads(line)
        if h["e"] < start_time or h["b"] > end_time:
            continue

        entry = {"begin": h["b"], "end": h["e"], "desc": h["d"]}
        if "p" not in h or len(h["p"]) == 0:
            root_list.append(entry)
        else:
            entry["parent"] = h["p"][0]
        trace_dic[h["a"]] = entry

    for k, v in trace_dic.items():
        if "parent" not in v:
            continue
        parent = trace_dic[v["parent"]]
        if "children" not in parent:
            parent["children"] = {}
        parent["children"][k] = v

    return trace_dic, root_list