class LC:
    def __init__(self,l):
        """ for storing a linear combination of abacus histories; assume argument is just a list
        this was just implemented to make it possible to avoid sage if needed
        """
        # array of paths in the linear combination
        self.d = []
        self.add_list(1,0,l)

    def print_lc(self):
        """
        """
        for v in self.d:
            str = ""
            if v['sgn'] == 1:
                str += "+"
            else:
                str += "-"
            str += ("q^%d" % (v['pow']))
            v['ah'].print_grid()
            print("Coeff: ",str)

    def add_list(self,sgn,mypow,ahlist):
        """ add in abacus histories in list with given sign and power
        """
        for l in ahlist:
            ahd = dict()
            ahd['ah'] = l
            ahd['sgn'] = sgn
            ahd['pow'] = mypow
            self.d.append(ahd)

    def add_LC(self,sgn,mypow,oldlc):
        """ add in LC, appropriate modifications to sign and coefficient
        """
        for l in oldlc.d:
            l['sgn'] *= sgn
            l['pow'] += mypow
            self.d.append(l)

    ######################################################################
    def compute_shapes(self):
        """ computes the shape field for each ah; returns list of shapes
        """
        arr = []
        for f in self.d:
            tmp = [x for x in f['ah'].get_shape(r=-1) if x != 0]
            f['shape'] = [x for x in tmp]
            if tmp not in arr:
                arr.append(tmp)
        return arr

    def extract_shape(self,ptn):
        """ return LC formed by AH's of a given shape; assumes compute_shapes has been called
        """
        nlc = LC([])
        for x in self.d:
            if x['shape'] == ptn:
                nlc.d.append(x)
        return nlc

    def compute_coeff(self):
        """ find poly corresponding to LC (assume all of the same shape)
        """
        arr = [[x['sgn'],x['pow']] for x in self.d]
        maxpow = max([x[1] for x in arr])
        minpow = min([x[1] for x in arr])
        narr = [0 for x in range(minpow,maxpow+1)]
        for x in arr:
            narr[x[1]-minpow] += x[0]
        # trim
        lastval = len(narr)-1
        while lastval > 0 and narr[lastval] == 0:
            lastval -= 1
        firstval = 0
        while firstval < len(narr)-1 and narr[firstval] == 0:
            firstval += 1
        return minpow+firstval,narr[firstval:lastval+1]

    def pretty_coeff(self,st,vals):
        """
        """
        if len(list(filter(lambda x: x != 0, vals))) > 1:
            tmpstr = "("
            needsparen = True
        else:
            tmpstr = ""
            needsparen = False
        # print("vals: ",st,vals)
        for i in range(len(vals)):
            if vals[i] != 0:
                if i > 0:
                    tmpstr += " "
                if vals[i] == 1:
                    tmpstr += "+" # leave 1 implicit
                    if i+st==0:
                        tmpstr += "1"
                elif vals[i] == -1:
                    tmpstr += "-" # leave 1 implicit
                    if i+st==0:
                        tmpstr += "1"
                elif vals[i] > 0:
                    tmpstr += ("+ %d" % (vals[i]))
                else:
                    tmpstr += ("- %d" % (-vals[i]))
                if i+st != 0:
                    tmpstr += (" q^%d" % (i+st))
        if needsparen:
            tmpstr += ")"
        else:
            tmpstr += ""
        return tmpstr

    def print_lc_simplified(self):
        """ print out an LC as a weighted sum of Schur polys
        """
        shapes = sorted(self.compute_shapes())
        tmpstr = ""
        for i,sh in enumerate(shapes):
            lc = self.extract_shape(sh)
            # print("Extracting")
            # for x in lc.d:
            #     print("one: ",x)
            st,coeff = lc.compute_coeff()
            # print("st,coeff: ",st,coeff)
            mystr = lc.pretty_coeff(st,coeff)
            if i > 0 and ')' in mystr:
                prep = "+"
            else:
                prep = ""
            if len(mystr) > 0:
                tmpstr += ("%s %s s_%s" % (prep,mystr,''.join(map(lambda x: str(x), sh))))
                if i < len(shapes):
                    tmpstr += " "
        if tmpstr == "":
            print("  0")
        else:
            print(tmpstr)