import time

def get_superclasses(a, b, **remainder):
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    model_dict, tm_dict = yield [("RD", [a['id'], "model"]), 
                                 ("RD", [a['id'], "type_mapping"])]
    tm_dict, = yield [("RD", [tm_dict, "root"])]

    worklist = set([b['value']])
    found = set([])

    cache_value = {}

    while worklist:
        name = worklist.pop()
        if name in found:
            continue
        elem, = yield [("RD", [model_dict, name])]
        found.add(name)

        # Iterate over all outgoing links
        if elem is None:
            print("ERROR: " + str(locals()))
        outgoing, = yield [("RO", [elem])]
        outgoing = set(outgoing)
        while (outgoing):
            link = outgoing.pop()

            # If the link is typed by "Inheritance", we add its destination
            link_name_node, = yield [("CALL_ARGS", [reverseKeyLookup, [{'id': model_dict}, {'id': link}]])]
            if "value" not in link_name_node:
                link_name_node['value'], = yield [("RV", [link_name_node['id']])]

            t_edge, = yield [("RD", [tm_dict, link_name_node['value']])]
            t_edge, = yield [("RV", [t_edge])]
            if t_edge == "Inheritance":
                edge, = yield [("RE", [link])]
                src, dst = edge
                # Look up dst's name and add it
                if dst not in cache_value:
                    dst_name, = yield [("CALL_ARGS", [reverseKeyLookup, [{'id': model_dict}, {'id': dst}]])]
                    if 'value' not in dst_name:
                        dst_name['value'], = yield [("RV", [dst_name['id']])]
                    cache_value[dst] = dst_name['value']
                dst_name_value = cache_value[dst]
                worklist.add(dst_name_value)

    result, = yield [("CN", [])]
    yield [("CD", [result, i, result]) for i in found]

    yield [("RETURN", [{'id': result}])]

def reverseKeyLookupMultiID(a, b, **remainder):
    edges, result = yield [("RO", [a['id']]), ("CN", [])]
    expanded_edges = yield [("RE", [i]) for i in edges]
    values = [i[1] for i in expanded_edges]

    # Keep results in a local Python set, as we want to bundle as many requests as possible
    todo = set()
    for i, edge in enumerate(values):
        if b['id'] == edge:
            todo.add(i)

    outgoings = yield [("RO", [edges[i]]) for i in todo]
    values = yield [("RE", [outgoing[0]]) for outgoing in outgoings]
    edges = yield [("CE", [result, result]) for value in values]
    yield [("CE", [edge, value[1]]) for edge, value in zip(edges, values)]

    yield [("RETURN", [{'id': result}])]

def reverseKeyLookupMultiValue(a, b, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]

    edges, result = yield [("RO", [a['id']]), ("CN", [])]
    expanded_edges = yield [("RE", [i]) for i in edges]
    values = yield [("RV", [i[1]]) for i in expanded_edges]

    # Keep results in a local Python set, as we want to bundle as many requests as possible
    todo = set()
    for i, edge in enumerate(values):
        if b['value'] == edge:
            todo.add(i)

    outgoings = yield [("RO", [edges[i]]) for i in todo]
    values = yield [("RE", [outgoing[0]]) for outgoing in outgoings]
    edges = yield [("CE", [result, result]) for value in values]
    yield [("CE", [edge, value[1]]) for edge, value in zip(edges, values)]

    yield [("RETURN", [{'id': result}])]

def reverseKeyLookup(a, b, **remainder):
    edges_out, edges_in = yield [("RO", [a['id']]), ("RI", [b['id']])]

    if edges_out is None or edges_in is None:
        yield [("RETURN", [{'value': ""}])]

    for edge in edges_in:
        if edge in edges_out:
            out_edges, = yield [("RO", [edge])]
            # Select one option randomly
            if out_edges:
                out_edge = out_edges.pop()
                e, = yield [("RE", [out_edge])]
                yield [("RETURN", [{'id': e[1]}])]
    yield [("RETURN", [{'value': ""}])]

def instantiated_name(a, b, **remainder):
    if "id" not in a:
        a['id'], = yield [("CNV", [a['value']])]
    if "value" not in b:
        b['value'], = yield [("RV", [b["id"]])]

    if b['value'] == "":
        yield [("RETURN", [{'value': "__" + str(a['id'])}])]
    else:
        yield [("RETURN", [b])]

def set_merge(a, b, **remainder):
    keys, =         yield [("RDK", [b['id']])]
    edges =         yield [("CE", [a['id'], a['id']]) for key in keys]
    _ =             yield [("CE", [edge, key]) for edge, key in zip(edges, keys)]
    yield [("RETURN", [a])]

def has_value(a, **remainder):
    if "value" not in a:
        a['value'], = yield [("RV", [a['id']])]
    if a['value'] is None:
        yield [("RETURN", [{'value': False}])]
    else:
        yield [("RETURN", [{'value': True}])]

def make_reverse_dictionary(a, **remainder):
    reverse, = yield [("CN", [])]

    if "id" not in a:
        yield [("RETURN", [{'id': reverse}])]

    key_nodes, = yield [("RDK", [a['id']])]
    values = yield [("RDN", [a['id'], i]) for i in key_nodes]
    yield [("CD", [reverse, str(v), k]) for k, v in zip(key_nodes, values)]
    yield [("RETURN", [{'id': reverse}])]

def make_reverse_dictionary_multi(a, **remainder):
    reverse, keys = yield [("CN", []), ("RDK", [a['id']])]

    if "id" not in a:
        yield [("RETURN", [{'id': reverse}])]

    values = yield [("RDN", [a['id'], i]) for i in keys]
    keys = yield [("RV", [i]) for i in keys]
    values = yield [("RV", [i]) for i in values]

    ndict = {}
    for k, v in zip(keys, values):
        ndict.setdefault(v, set()).add(k)

    n = yield [("CN", []) for _ in ndict]
    for k in ndict:
        set_node = n.pop()
        yield [("CD", [reverse, k, set_node])]
        yield [("CD", [set_node, v, set_node]) for v in ndict[k]]

    yield [("RETURN", [{'id': reverse}])]

def dict_eq(a, b, **remainder):
    key_nodes, = yield [("RDK", [a['id']])]
    key_values = yield [("RV", [i]) for i in key_nodes]
    values = yield [("RD", [a['id'], i]) for i in key_values]
    values = yield [("RV", [i]) for i in values]
    a_dict = dict(list(zip(key_values, values)))

    key_nodes, = yield [("RDK", [b['id']])]
    key_values = yield [("RV", [i]) for i in key_nodes]
    values = yield [("RD", [b['id'], i]) for i in key_values]
    values = yield [("RV", [i]) for i in values]
    b_dict = dict(list(zip(key_values, values)))

    yield [("RETURN", [{'value': a_dict == b_dict}])]

def string_substr(a, b, c, **remainder):
    if "value" not in a:
        a['value'], = yield [("RV", [a['id']])]
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]
    if "value" not in c:
        c['value'], = yield [("RV", [c['id']])]

    try:
        new_value = a['value'][b['value']:c['value']]
    except:
        new_value = ""
    
    yield [("RETURN", [{'value': new_value}])]

def integer_gt(a, b, **remainder):
    if 'value' not in a:
        a['value'], = yield [("RV", [a['id']])]
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    yield [("RETURN", [{'value': a['value'] > b['value']}])]

def integer_neg(a, **remainder):
    if 'value' not in a:
        a['value'], = yield [("RV", [a['id']])]
    yield [("RETURN", [{'value': -a['value']}])]

def float_gt(a, b, **remainder):
    if 'value' not in a:
        a['value'], = yield [("RV", [a['id']])]
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    yield [("RETURN", [{'value': a['value'] > b['value']}])]

def float_neg(a, **remainder):
    if 'value' not in a:
        a['value'], = yield [("RV", [a['id']])]
    yield [("RETURN", [{'value': -a['value']}])]

def value_neq(a, b, **remainder):
    if 'value' not in a:
        a['value'], = yield [("RV", [a['id']])]
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    yield [("RETURN", [{'value': a['value'] != b['value']}])]

def element_neq(a, b, **remainder):
    if 'id' not in a or 'id' not in b:
        yield [("RETURN", [{'value': False}])]
    else:
        yield [("RETURN", [{'value': a['id'] != b['id']}])]

def list_append(a, b, **remainder):
    if "id" not in b:
        b['id'], = yield [("CNV", [b['value']])]
    a_outgoing, = yield [("RO", [a['id']])]
    _ = yield [("CD", [a['id'], len(a_outgoing), b['id']])]
    yield [("RETURN", [a])]

def list_read(a, b, **remainder):
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    result, = yield [("RD", [a['id'], b['value']])]
    if result is None:
        raise Exception("List read out of bounds: %s" % b['value'])
    yield [("RETURN", [{'id': result}])]

def list_len(a, **remainder):
    outgoings, = yield [("RO", [a['id']])]
    result, = yield [("CNV", [len(outgoings)])]
    yield [("RETURN", [{'id': result}])]

def dict_add(a, b, c, **remainder):
    if 'id' not in b:
        b['id'], = yield [("CNV", [b['value']])]
    if 'id' not in c:
        c['id'], = yield [("CNV", [c['value']])]
    new_edge, = yield [("CE", [a['id'], c['id']])]
    yield [("CE", [new_edge, b['id']])]
    yield [("RETURN", [a])]

def dict_len(a, **remainder):
    outgoings, = yield [("RO", [a['id']])]
    yield [("RETURN", [{'value': len(outgoings)}])]

def set_add(a, b, **remainder):
    if 'value' not in b:
        b['value'], = yield [("RV", [b['id']])]
    is_in, =    yield [("RD", [a['id'], b['value']])]
    if not is_in:
        _, =    yield [("CD", [a['id'], b['value'], a['id']])]
    yield [("RETURN", [a])]

def set_add_node(a, b, **remainder):
    if 'id' not in b:
        b['id'], = yield [("CNV", [b['value']])]
    is_in, =    yield [("RDN", [a['id'], b['id']])]
    if not is_in:
        edge, = yield [("CE", [a['id'], a['id']])]
        _, =    yield [("CE", [edge, b['id']])]
    yield [("RETURN", [a])]

def set_pop(a, **remainder):
    outgoing, = yield [("RO", [a['id']])]
    if outgoing:
        outgoing = outgoing[0]
        new_outgoing, = yield [("RO", [outgoing])]
        new_outgoing = new_outgoing[0]
        edge, _ = yield [("RE", [new_outgoing]), ("DE", [outgoing])]
        yield [("RETURN", [{'id': edge[1]}])]
    else:
        raise Exception("POP from empty set")
        yield [("RETURN", [{'id': remainder["root"]}])]

def set_create(**remainder):
    result, = yield [("CN", [])]
    yield [("RETURN", [{'id': result}])]

def list_create(**remainder):
    result, = yield [("CN", [])]
    yield [("RETURN", [{'id': result}])]

def dict_create(**remainder):
    result, = yield [("CN", [])]
    yield [("RETURN", [{'id': result}])]

def create_tuple(a, b, **remainder):
    if "id" not in a:
        a['id'], = yield [("CNV", [a['value']])]
    if "id" not in b:
        b['id'], = yield [("CNV", [b['value']])]

    result, = yield [("CN", [])]
    _, _ =    yield [("CD", [result, 0, a['id']]),
                     ("CD", [result, 1, b['id']]),
                    ]
    yield [("RETURN", [{'id': result}])]

def set_overlap(a, b, **remainder):
    a_keys, b_keys, res = yield [("RDK", [a['id']]), ("RDK", [b['id']]), ("CN", [])]
    a_values = yield [("RV", [i]) for i in a_keys]
    b_values = yield [("RV", [i]) for i in b_keys]

    result = set(a_values) & set(b_values)
    yield [("CD", [res, value, res]) for value in result]

    yield [("RETURN", [{'id': res}])]

def list_pop_final(a, **remainder):
    lst, = yield [("RO", [a['id']])]
    length = len(lst)
    result, result_edge = yield [("RD", [a['id'], length - 1]),
                                 ("RDE", [a['id'], length -1])]
    _, = yield [("DE", [result_edge])]
    yield [("RETURN", [{'id': result}])]

def instantiate_node(a, b, c, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]

    if "value" not in c:
        c['value'], = yield [("RV", [c['id']])]
        
    node, dict_entry, tm = \
        yield [("CN", []),
               ("RD", [a['id'], "model"]),
               ("RD", [a['id'], "type_mapping"]),
              ]

    if c['value'] == "":
        name = "__" + str(node)
        name_node = {'value': name}
    else:
        name = c['value']
        name_node = c

    _, root = yield [("CD", [dict_entry, name, node]),
                     ("RD", [tm, "root"])]

    # Create new type links
    type_elem, instance_elem = yield [("CNV", [b['value']]), ("CNV", [name])]
    type_link, = yield [("CE", [root, type_elem])]
    instance_link, = yield [("CE", [type_link, instance_elem])]

    # Add them to the model
    yield  [("CD", [tm, str(type_elem), type_elem]),
            ("CD", [tm, str(instance_elem), instance_elem]),
            ("CD", [tm, str(type_link), type_link]),
            ("CD", [tm, str(instance_link), instance_link])]

    yield [("RETURN", [name_node])]

def list_insert(a, b, c, **remainder):
    if "id" not in b:
        b["id"], = yield [("CNV", [b['value']])]
    if "value" not in c:
        c['value'], = yield [("RV", [c['id']])]

    a_outgoing, = yield [("RO", [a['id']])]
    links = yield [("RD", [a['id'], i]) for i in range(c['value'], len(a_outgoing))] + \
                  [("RDE", [a['id'], i]) for i in range(c['value'], len(a_outgoing))]

    values = links[:len(links) // 2]
    edges = links[len(links) // 2:] 

    yield [("CD", [a['id'], c['value'], b['id']])] + \
          [("CD", [a['id'], c['value'] + 1 + index, value]) for index, value in enumerate(values)] + \
          [("DE", [i]) for i in edges]
    yield [("RETURN", [a])]

def list_delete(a, b, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]

    a_outgoing,  = yield [("RO", [a['id']])]
    links = yield [("RD", [a['id'], i]) for i in range(b['value'], len(a_outgoing))] + \
                  [("RDE", [a['id'], i]) for i in range(b['value'], len(a_outgoing))]

    values = links[:len(links) // 2]
    edges = links[len(links) // 2:]

    yield [("CD", [a['id'], b['value'] + index, value]) for index, value in enumerate(values[1:])] + \
          [("DE", [i]) for i in edges]
    yield [("RETURN", [a])]

def set_len(a, **remainder):
    if "id" not in a:
        yield [("RETURN", [{'value': 0}])]
    else:
        outgoing, = yield [("RO", [a['id']])]
        yield [("RETURN", [{'value': len(outgoing)}])]

def set_in(a, b, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]
    value, = yield [("RD", [a['id'], b['value']])]
    yield [("RETURN", [{'value': value is not None}])]

def set_in_node(a, b, **remainder):
    if "id" not in b:
        # Not even allocated the node, so it is certain not to be in the dictionary
        yield [("RETURN", [{'value': False}])]
    value, = yield [("RDN", [a['id'], b['id']])]
    yield [("RETURN", [{'value': value is not None}])]

def read_type(a, b, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]

    model, type_mapping, metamodel = yield [("RD", [a['id'], 'model']), ("RD", [a['id'], 'type_mapping']), ("RD", [a['id'], 'metamodel'])]
    type_mapping, = yield [("RD", [type_mapping, "root"])]
    metamodel, in_model, type_value = yield [("RD", [metamodel, 'model']), ("RD", [model, b['value']]), ("RD", [type_mapping, b['value']])]

    if in_model is None:
        yield [("RETURN", [{'value': ""}])]
    elif type_value is None:
        yield [("RETURN", [{'value': ""}])]
    else:
        type_value, = yield [("RV", [type_value])]
        in_metamodel, = yield [("RD", [metamodel, type_value])]
        if in_metamodel is None:
            yield [("RETURN", [{'value': ""}])]
        else:
            yield [("RETURN", [{'value': type_value}])]

def retype(a, b, c, **remainder):
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]
    if "value" not in c:
        c['value'], = yield [("RV", [c['id']])]

    tm, = yield [("RD", [a["id"], "type_mapping"])]
    root, = yield [("RD", [tm, "root"])]

    # remove_type
    val, = yield [("RD", [root, b["value"]])]
    if val is not None:
        # Key exists, so remove
        yield [("DN", [val])]

    # Create new type links
    type_elem, instance_elem = yield [("CNV", [c['value']]), ("CNV", [b['value']])]
    type_link, = yield [("CE", [root, type_elem])]
    instance_link, = yield [("CE", [type_link, instance_elem])]

    # Add them to the model
    yield  [("CD", [tm, str(type_elem), type_elem]),
            ("CD", [tm, str(instance_elem), instance_elem]),
            ("CD", [tm, str(type_link), type_link]), 
            ("CD", [tm, str(instance_link), instance_link])]

    yield [("RETURN", [None])]

def set_equality(a, b, **remainder):
    if "id" not in a:
        yield [("RETURN", [{'value': False}])]
    if "id" not in b:
        yield [("RETURN", [{'value': False}])]

    keys_a, keys_b = yield [("RDK", [a["id"]]), ("RDK", [b["id"]])]
    if (len(keys_a) != len(keys_b)):
        yield [("RETURN", [{'value': False}])]

    keys_a = yield [("RV", [i]) for i in keys_a]
    keys_b = yield [("RV", [i]) for i in keys_b]
    yield [("RETURN", [{'value': keys_a == keys_b}])]

def set_difference(a, b, **remainder):
    keys_a, keys_b = yield [("RDK", [a["id"]]), ("RDK", [b["id"]])]
    keys_a = yield [("RV", [i]) for i in keys_a]
    keys_b = yield [("RV", [i]) for i in keys_b]
    result = set(keys_a) - set(keys_b)
    res, = yield [("CN", [])]
    yield [("CD", [res, v, res]) for v in result]
    yield [("RETURN", [{'id': res}])]

def string_startswith(a, b, **remainder):
    if "value" not in a:
        a['value'], = yield [("RV", [a['id']])]
    if "value" not in b:
        b['value'], = yield [("RV", [b['id']])]

    yield [("RETURN", [{"value": a['value'].startswith(b['value'])}])]

def dict_copy(a, **remainder):
    keys, new = yield [("RDK", [a['id']]), ("CN", [])]
    values = yield [("RDN", [a['id'], i]) for i in keys]
    keys = yield [("RV", [i]) for i in keys]
    yield [("CD", [new, k, v]) for k, v in zip(keys, values)]
    yield [("RETURN", [{'id': new}])]