'''
This code is developed by professor Jørn Vatn. The code can be used
by students and employees at NTNU. The code comes with no warranties.

You are not allowed to use the code for commercial purposes without
written permission from Jørn Vatn
'''

gates = [""] 
basics = ["$_$_$_$_"] 
combinations = [] 

def initFTAstru(): 
    global gates, basics 
    gates = [""] 
    #basics = ["$"] 

def nBasics(): 
    return len(basics) 

def getBasics(): 
    return basics 

def comb(sofar, rest, k): 
    if k == 0: 
        combinations.append(sofar) 
    else: 
        for i in range(len(rest)): 
            sofarNext = sofar[:] 
            sofarNext.append(rest[i]) 
            comb(sofarNext, rest[i + 1:], k - 1) 

def kOutOf(k, lst): # Used to implement KooN structure
    global combinations 
    combinations = [] 
    comb([], lst, k) 
    return combinations 

def inList(el, eList): 
    for x in eList: 
        if equalStrings(x, el): 
            return True 
    return False 

def isGate(gate): 
    return inList(gate, gates) 

def txt2num(el, eList): 
    i = 0 
    for x in eList: 
        if x == "": 
            eList[0] = el 
            return 0 
        if equalStrings(x, el): 
            return i 
        i += 1 
    eList.append(el) 
    return i 

def gate2num(gate): 
    return txt2num(gate, gates) 

def num2gate(gate): 
    return gates[gate] 

def basic2num(basic): 
    return -txt2num(basic, basics) 

def num2basic(basic): 
    return basics[-basic] 

def printList(eList): 
    for x in eList: 
        print(x) 

def printGates(): 
    printList(gates) 

def printBasics(): 
    printList(basics) 

def trimList(lst): # Remove duplicates
    for i in range(len(lst) - 1): 
        for j in range(i + 1, len(lst)): 
            if lst[i] == lst[j]: 
                lst.pop(j) 
                trimList(lst) 
                return 

def isSubset(A, B): 
    if len(A) > len(B): 
        return False 
    for x in A: 
        if x not in B: 
            return False 
    return True 

def expandH(MCSs, gateData): 
    changed = False 
    for i in range(len(MCSs)): 
        MCS = MCSs[i] 
        for j in range(len(MCS)): 
            if MCS[j] == gateData[0]: 
                changed = True 
                MCS[j] = gateData[2] 
                MCS.extend(gateData[3:]) 
                trimList(MCS) 
                MCSs[i] = MCS 
                break 
    return changed 

def expandV(MCSs, gateData): 
    changed = False 
    for i in range(len(MCSs)): 
        MCS = MCSs[i] 
        for j in range(len(MCS)): 
            if MCS[j] == gateData[0]: 
                changed = True 
                MCS[j] = gateData[2] 
                trimList(MCS) 
                MCSs[i] = MCS 
                for k in range(3, len(gateData)): 
                    tmp = MCS[:] 
                    tmp[j] = gateData[k] 
                    trimList(tmp) 
                    MCSs.append(tmp) 
                break 
    return changed 

def makeMinimal(MCSs): 
    for i in range(len(MCSs) - 1): 
        for j in range(i + 1, len(MCSs)): 
            if isSubset(MCSs[i], MCSs[j]): 
                MCSs.pop(j) 
                makeMinimal(MCSs) 
                return 
            elif isSubset(MCSs[j], MCSs[i]): 
                MCSs.pop(i) 
                makeMinimal(MCSs) 
                return 

def printMCSs(MCSs): 
    for k in range(10): 
        for i in range(len(MCSs)): 
            if len(MCSs[i]) == k: 
                print(MCSs[i]) 

def MCSs2txt(MCSs): 
    str_result = "" 
    for length in range(1, 10): 
        for i in range(len(MCSs)): 
            MCS = MCSs[i] 
            if len(MCS) == length: 
                str_result += "{" 
                for j in range(len(MCS)): 
                    if MCS[j] < 0: 
                        str_result += basics[-MCS[j]] + "," 
                    else: 
                        str_result += basics[MCS[j]] + "*," 
                str_result += "}" 
                str_result = str_result.replace(",}", "}\n") 
    return str_result

def equalStrings(s1,s2):
  return (s1.lower() == s2.lower())