"""
 PQ Gram Implementation
"""

mock = [
    {'from': 'a', 'to': 'b'},
    {'from': 'b', 'to': 'c'},
    {'from': 'b', 'to': 'd'},
    {'from': 'a', 'to': 'e'},
    {'from': 'a', 'to': 'f'}
]  # children must be from left to right


def shift(reg, el):
    reg.pop(0)
    reg.append(el)
    return reg


def pq_profile(T, P, p, q, r):
    anc = ['*'] * p
    P = profile(T, p, q, P, r, anc)
    return P


def is_leaf(r, T):
    for node in T:
        if node['from'] == r:
            return False
    return True


def get_children(r, T):
    children = []
    for node in T:
        if node['from'] == r:
            children.append(node['to'])
    return children


def profile(T, p, q, P, r, anc):  # *, *
    anc = shift(anc, r)
    sib = ['*'] * q

    if is_leaf(r, T):
        P.append(anc + sib)
    else:
        children = get_children(r, T)
        for c in children:
            sib = shift(sib, c)
            P.append(anc + sib)
            P = profile(T, p, q, P, c, anc)
        for k in range(1, q):
            sib = shift(sib, '*')
            P.append(anc + sib)
    return P


gramProfile = pq_profile(mock, [], 2, 3, mock[0]['from'])

for line in gramProfile:
    print(line)