from lc import LC

# Constants for working with abacus histories
# These constants are for the vertex-centric

# These constants are for the square-centric viewpoint and indicate
# which sides of the square are bordered by a path
SQ_BOT = 1
SQ_TOP = 2
SQ_RIGHT = 4
SQ_LEFT = 8
SQ_ULLR = 16
SQ_URLL = 32
SQ_SE = (SQ_BOT + SQ_RIGHT)
SQ_NW = (SQ_TOP + SQ_LEFT)
SQ_SW = (SQ_BOT + SQ_LEFT)
SQ_NE = (SQ_TOP + SQ_RIGHT)

# These constants are for the vertex-centric viewpoint and indicate
# which directions have part of a path
VX_DEF = 64 # if this was default start of a path
VX_TRAILHEAD = 128 # if this is the start of a path
VX_TOP = 256
VX_RIGHT = 512
VX_BOT = 1024
VX_LEFT = 2048
VX_TL = 4096
VX_TR = 8192
VX_BL = 16384
VX_BR = 32768

# Constants for making postscript
# Postscript code not currently working as it's based on old ahist code (Aug 4, 2020)
CIRC_RAD = 0.15
CIRC_GRAY = 0.5
DIAG_GRAY = 0.3
PATH_GRAY = 0.4
DIAM_DIAM = 0.1

import re

###########################################################################################
###########################################################################################
class AH:
    def __init__(self, grid=[[]], sqs=[[]], paths = dict(), ends = []):
        """ for storing all information about an abacus history
        built from (but doesn't depend on) ahist
        """
        # vertex-centric grid; these are points the paths actually pass through
        self.grid = [[x for x in y] for y in grid]

        # square-centric grid for determining what can be flipped
        # values describe which edges of square have paths through them
        # vertex with same index is at lower-left of square
        self.sqs = [[x for x in y] for y in sqs]

        # paths is a dictionary whose keys are the labels for various paths
        # the values are another dictionary that carries information about each path
        # such as starting and ending positions
        self.paths = dict()
        for k in paths.keys():
            self.paths[k] = dict()
            # currently each path *must* have the following keys defined
            self.paths[k]['start'] = [x for x in paths[k]['start']] # ordered pair consisting of row, column
            self.paths[k]['end'] = [x for x in paths[k]['end']] # ordered pair consisting of row, column
            self.paths[k]['word'] = [x for x in paths[k]['word']] # word in {E,W,S,\,/}
            self.paths[k]['sgn'] = paths[k]['sgn'] # parity of number of paths to East of start (same row or higher)
        # list of ordered triples describing endpoints of paths in bottom row of AH
        # first coordinates row, second indicates column of path, third is key from paths.keys()
        # assumed to be in increasing column order (second index)
        # NOTE: Some paths may not end in the bottom row! (think omega operator)
        self.ends = [[y for y in x] for x in ends] 

        # having to do with the weightings - not implemented
        # actual weight depends on which operator is being used
        # self.west = self.get_west_steps()
        # self.inv = self.get_inv()

    ##########################################################
    @classmethod
    def snu_abacus(cls,nu=[0]):
        """ create one-row abacus corresponding to s_nu
        """
        # first compute columns for given row lengths of nu
        nurev = nu[::-1]

        # these are [row,column,i] - i becomes the key for that path
        ends = [[0,nurev[i]+i,i] for i in range(len(nurev))]

        paths = dict()
        for i in range(len(nurev)):
            paths[i] = dict()
            paths[i]['start'] = [0,ends[i][1]]
            paths[i]['end'] = [0,ends[i][1]]
            paths[i]['word'] = ''
            paths[i]['sgn'] = 1

        # ends[-1][1] is column of rightmost path; mark the start of each path
        grid = [[0 for i in range(ends[-1][1]+1)]]
        for i in range(len(ends)):
            grid[0][ends[i][1]] = VX_TRAILHEAD

        # initialize squares with nothing; none the paths have any edges yet
        sqs = [[0 for i in range(ends[-1][1]+1)]]
        for i in range(len(ends)):
            sqs[0][ends[i][1]] = VX_TRAILHEAD

        return AH(ends=ends,paths=paths,grid=grid,sqs=sqs)

    ##########################################################
    def copy(self):
        """ be paranoid about copying since I can never remember the rules...
        """
        nh = AH(grid=self.grid,sqs=self.sqs,paths=self.paths,ends=self.ends)
        # nh.west = self.west
        # nh.inv = self.inv

        return nh

    ###########################################################################3
    @classmethod
    def equal_grids(cls,grida,gridb,verbose=False):
        """ check if two grids are equal
        """
        if grida is None and gridb is None:
            return True

        if (grida is None and gridb is not None) or (grida is not None and gridb is None):
            return False

        if len(grida) != len(gridb):
            if verbose:
                print("grids don't match number of rows")
            return False
        for r in range(len(grida)):
            if len(grida[r]) != len(gridb[r]):
                if verbose:
                    print("grids don't match row length",r)
                return False
            for c in range(len(grida[r])):
                if grida[r][c] != gridb[r][c]:
                    if verbose:
                        print("grids don't match",r,c,grida[r][c],gridb[r][c])
                    return False
        return True

    ###########################################################################3
    def cnt_steps(self,step='W'):
        """ count total number of steps of a given type among all paths
        """
        cnt = 0
        for x in self.paths.values():
            cnt += len(list(filter(lambda y: y == step, x['word'])))
        return cnt

    ###########################################################################3
    def get_sign(self):
        """ determine sign of abacus history (based on parity of inversions as paths get added
        """
        cnt = 1
        for x in self.paths.values():
            cnt *= x['sgn']
        return cnt

    ###########################################################################3
    def extend_grid(self,mx=0):
        """ fill out the grid so each row has the same length
        mx is length we want (last filled column + 1)
        """
        # first, get max length we need
        if mx == 0:
            for r in range(len(self.grid)):
                for c in range(len(self.grid[r])):
                    if self.grid[r][c] > 0 and c+1 > mx:
                        mx = c+1
        for i in range(len(self.grid)):        
            if len(self.grid[i]) < mx:
                self.grid[i].extend([0 for j in range(mx-len(self.grid[i]))])
            # only take grid as far to the right as we need to
            if len(self.grid[i]) > mx:
                self.grid[i] = self.grid[i][:mx]

    ##########################################################
    def make_sqs_from_grid(self):
        """ assume grid is properly initialized, set up squares
            should be allocated when self is created
            TODO: FIX relationship in indexing ???
        """
        self.sqs = [[0 for x in y] for y in self.grid]
        # no square to left of first dot or below bottom row
        # so really don't want to see r=0 of grid (or last column?)
        for r in range(len(self.grid)):
            for c in range(len(self.grid[r])):
                if (self.grid[r][c] & VX_RIGHT) > 0:
                    self.sqs[r][c] += SQ_BOT
                if (self.grid[r][c] & VX_TOP) > 0:
                    self.sqs[r][c] += SQ_LEFT
                if r > 0 and (self.grid[r-1][c] & VX_RIGHT) > 0:
                    self.sqs[r][c] += SQ_TOP
                if c < len(self.grid[r])-1 and (self.grid[r][c+1] & VX_TOP) > 0:
                    self.sqs[r][c] += SQ_RIGHT
                if (self.grid[r][c] & VX_TR) > 0:
                    self.sqs[r][c] += SQ_URLL
                if r > 0 and (self.grid[r-r][c] & VX_BR) > 0:
                    self.sqs[r][c] += SQ_ULLR
                if (self.grid[r][c] & VX_TRAILHEAD) > 0:
                    self.sqs[r][c] += VX_TRAILHEAD

    ##########################################################
    def print_grid(self,verbose=False):
        """
        """
        if verbose:
            print(self.grid)
        for r in range(0,len(self.grid)):
            # now cover the vertical steps
            tmpstr = ""
            for c in range(len(self.grid[r])):
                if (self.grid[r][c] & VX_TOP):
                    tmpstr += "| "
                elif (self.grid[r][c] & VX_TL):
                    tmpstr += "\ "
                elif (self.grid[r][c] & VX_TR):
                    tmpstr += " /"
                else:
                    tmpstr += "  "
            # A hack to make diagonals to lower right look to be in the right place
            tmpstr = re.sub(r' \\',r'\\ ',tmpstr)
            print(tmpstr)

            # first put marks along portion of path
            tmpstr = ""
            for c in range(len(self.grid[r])):
                # put symbol at point
                if (self.grid[r][c] & VX_TRAILHEAD) != 0:
                    tmpstr += "X"
                elif (self.grid[r][c] > 0):
                    tmpstr += "*"
                else:
                    tmpstr += "."
                # put edge incoming from right if necessary
                if (self.grid[r][c] & VX_RIGHT):
                    tmpstr += "-"
                else:
                    tmpstr += " "
            print(tmpstr)
            if verbose:
                print("grid: ",self.grid)
                print("sqs: ",self.sqs)
                for k in self.paths.keys():
                    print("paths: ",k,self.paths[k])
                print("ends: ",self.ends)
        
    ##########################################################
    def print_sqs(self):
        """ print out in square-centric view
        """
        for r in range(0,len(self.sqs)):
            if r > 0:
                # now cover the vertical and diagonal steps
                tmpstr = ""
                for c in range(len(self.sqs[r])):
                    if (self.sqs[r][c] & SQ_LEFT):
                        tmpstr += "| "
                    elif (self.sqs[r][c] & SQ_URLL):
                        tmpstr += "/ "
                    elif (self.sqs[r][c] & SQ_ULLR):
                        tmpstr += "\ "
                    else:
                        tmpstr += "  "
                print(tmpstr)

            # now put marks along portion of path
            tmpstr = ""
            for c in range(len(self.sqs[r])):
                # put symbol at point
                if (self.sqs[r][c] & VX_TRAILHEAD) != 0:
                    tmpstr += "X"
                elif (((self.sqs[r][c] & SQ_BOT) > 0) or \
                      ((self.sqs[r][c] & SQ_LEFT) > 0) or \
                      ((self.sqs[r][c] & SQ_URLL) > 0) or \
                      (c > 0 and (self.sqs[r][c-1] & SQ_ULLR) > 0) or \
                      (c > 0 and (self.sqs[r][c-1] & SQ_BOT) > 0) or \
                      (r < len(self.sqs)-1 and (self.sqs[r+1][c] & SQ_LEFT) > 0)):
                    tmpstr += "*"
                else:
                    tmpstr += "."
                # put edge incoming from right if necessary
                if (self.sqs[r][c] & SQ_BOT):
                    tmpstr += "-"
                else: 
                    tmpstr += " "
            print(tmpstr)

    #####################################################################################3
    def _apply_hc(self,b,skew=False,verbose=True):
        """ apply h_c or h_c_skew operator to generate all possible extensions
        """
        # if b > 0, make sure we have at least one zero part
        self._ensure_min_zeros(1)

        # see how much each column can be moved left
        # each entry is an ordered pair consisting of possible distance to move in first coordinate
        # and key of path in second coordinate
        if len(self.ends) > 0:
            if skew:
                coldiffs = [[self.ends[0][1],self.ends[0][2]]] + \
                    [[self.ends[i][1] - self.ends[i-1][1] - 1,self.ends[i][2]] for i in range(1,len(self.ends))]
            else:
                coldiffs = [[self.ends[i][1] - self.ends[i-1][1] - 1,self.ends[i-1][2]] for i in range(1,len(self.ends))] + \
                    [[b,self.ends[-1][2]]]
        else:
            coldiffs = []
        
        # get our complete list of options for west steps at this level
        curopts = [[]]
        newopts = []
        for i in range(len(coldiffs)):
            for x in curopts:
                for j in range(coldiffs[i][0]+1):
                    newopts.append(x + [[j,coldiffs[i][1]]])
            curopts = newopts
            newopts = []

        # only keep those curopts for which the total amount adds up to b
        finopts = []
        for x in curopts:
            tot = sum([y[0] for y in x])
            if tot==b:
                finopts.append(x)

        nahlist = []
        for x in finopts:     # tuple of options for each path
            ah = self.copy()  
            w_tot = 0
            new_ends = []

            if skew:
                ah.grid.append([0 for j in range(ah.ends[-1][1]+1)])
            else:
                # make room since paths can move to the right
                ah.grid.append([0 for j in range(len(ah.grid[-1]))])
                ah.extend_grid(len(ah.grid[-1])+x[-1][0])

            for i,y in enumerate(x): # pick up choice for given path
                # print("i %s y %s" % (i,y))
                if skew:
                    ah.paths[y[1]]['word'].extend(['W' for j in range(y[0])] + ['S'])
                else:
                    ah.paths[y[1]]['word'].extend(['E' for j in range(y[0])] + ['S'])
                old_end = ah.paths[y[1]]['end']

                # adjust grid accordingly
                if skew:
                    for j in range(old_end[1]-y[0],old_end[1]):
                        ah.grid[-2][j] |= VX_RIGHT
                    for j in range(old_end[1]-y[0]+1,old_end[1]+1):
                        ah.grid[-2][j] |= VX_LEFT
                    ah.grid[-2][old_end[1]-y[0]] |= VX_BOT
                    ah.grid[-1][old_end[1]-y[0]] |= VX_TOP
                    ah.paths[y[1]]['end'] = [old_end[0]+1,old_end[1]-y[0]]       # update the ending columns
                    new_ends.append([old_end[0]+1,old_end[1]-y[0],y[1]])
                else:
                    for j in range(old_end[1],old_end[1]+y[0]):
                        ah.grid[-2][j] |= VX_RIGHT
                    # print(ah.grid,ah.grid[-2],old_end[1],y[0])
                    for j in range(old_end[1]+1,old_end[1]+y[0]+1):
                        ah.grid[-2][j] |= VX_LEFT
                    ah.grid[-2][old_end[1]+y[0]] |= VX_BOT
                    ah.grid[-1][old_end[1]+y[0]] |= VX_TOP
                    ah.paths[y[1]]['end'] = [old_end[0]+1,old_end[1]+y[0]]       # update the ending columns
                    new_ends.append([old_end[0]+1,old_end[1]+y[0],y[1]])

                w_tot += y[0]
                
            ah.ends = list(sorted(new_ends, key = lambda zz: zz[1]))
            nahlist.append(ah)

        return LC(nahlist)

    #####################################################################################
    def _apply_hc_skew(self,b,verbose=True):
        return self._apply_hc(b,skew=True,verbose=verbose)

    #####################################################################################
    def _ec_seqs_opts(self,b,skew=False,verbose=True):
        """ determine options for which sets of beads can be used for e_c or e_c_skew
        """
        # first find out where the runs of beads are
        i = 0
        arr = []
        while i <= self.ends[-1][1]:
            # WARNING: What about VX_DEF?
            if (self.grid[-1][i] == 0 and i < self.ends[-1][1] and self.grid[-1][i+1] > 0):
                new_st = i+1
            if (i == 0 and self.grid[-1][0] > 0):
                new_st = i
            if self.grid[-1][i] > 0 and (i == self.ends[-1][1] or self.grid[-1][i+1] == 0):
                arr.append([new_st,i])
            i += 1

        if verbose:
            print("arr: ",arr)

        # go through and pull the compositions that add up to b
        curopts = [[]]
        newopts = []
        for i in range(len(arr)):
            for x in curopts:
                # if ec_skew, don't want to move paths in block starting at beginning
                if skew and i==0 and arr[i][0] == 0:
                    curmax = 1
                else:
                    curmax = arr[i][1]-arr[i][0]+2
                for j in range(curmax):
                    newopts.append(x + [j])
            curopts = newopts
            newopts = []

        # only keep those curopts for which the total amount adds up to b
        finopts = []
        for x in curopts:
            tot = sum([y for y in x])
            if tot==b:
                finopts.append(x)

        # need to map column numbers to path indices
        col_ind = [-1 for j in range(len(self.grid[-1]))]
        for x in self.ends:
            col_ind[x[1]] = x[2]

        return arr, finopts, col_ind

    #####################################################################################
    def _ensure_min_zeros(self,b=1,verbose=True):
        """ make sure we have a minimum number of zeros to apply operators to
        """
        # let's make sure we have at least one
        if b==0:
            b = 1

        # first check how many zeros we start with
        c = 0
        while c < len(self.grid[-1]) and self.grid[-1][c] > 0 and b > 0:
            c += 1
            b -= 1

        # we have enough
        if b == 0:
            return

        # vertex-centric grid; these are points the paths actually pass through
        self.grid = [[0 for i in range(b)] + [x for x in y] for y in self.grid]
        for c in range(b):
            self.grid[0][c] |= VX_TRAILHEAD
            for r in range(len(self.grid)):
                if r < len(self.grid)-1:
                    self.grid[r][c] |= VX_BOT
                if r > 0:
                    self.grid[r][c] |= VX_TOP

        # square-centric grid for determining what can be flipped
        # values describe which edges of square have paths through them
        # vertex with same index is at lower-left of square
        # WARNING: Not recomputed
        self.sqs = [[0 for i in range(b)] + [x for x in y] for y in self.sqs]

        # paths is a dictionary whose keys are the labels for various paths
        # the values are another dictionary that carries information about each path
        # such as starting and ending positions
        for k in self.paths.keys():
            # currently each path *must* have the following keys defined
            pk = self.paths[k]
            self.paths[k]['start'] = [pk['start'][0],pk['start'][1]+b] # ordered pair consisting of row, column
            self.paths[k]['end'] = [pk['end'][0],pk['end'][1]+b] # ordered pair consisting of row, column
            # no changes required
            # self.paths[k]['word'] = [x for x in paths[k]['word']] # word in {E,W,S,\,/}
            # self.paths[k]['sgn'] = paths[k]['sgn'] # parity of number of paths to East of start (same row or higher)

        # add in new paths
        stkey = max(list(self.paths.keys()))+1
        for i in range(b):
            self.paths[stkey+i] = dict()
            self.paths[stkey+i]['start'] = [0,i]
            self.paths[stkey+i]['end'] = [len(self.grid)-1,i]
            self.paths[stkey+i]['word'] = ['S' for x in range(len(self.grid)-1)]
            self.paths[stkey+i]['sgn'] = 1

        # list of ordered triples describing endpoints of paths in bottom row of AH
        # first coordinates row, second indicates column of path, third is key from paths.keys()
        # assumed to be in increasing column order (second index)
        # NOTE: Some paths may not end in the bottom row! (think omega operator)
        r = len(self.grid)-1

        self.ends = [[r,i,stkey+i] for i in range(b)] + [[x[0],x[1]+b,x[2]] for x in self.ends]

    #####################################################################################
    def _apply_ec(self,b,skew=False,verbose=True):
        """ apply e_c or e_c_skew operator to generate all possible extensions
        """
        # if b > 0, make sure we have at least b zero parts
        self._ensure_min_zeros(b)

        if verbose:
            self.print_grid(verbose=True)

        # arr consists of pairs: [column of start of run, column of end of run]
        # finopts: each element is array saying how many to move from each run
        # col_ind: each entry gives index of path in that column
        arr, finopts, col_ind = self._ec_seqs_opts(b,skew=skew,verbose=verbose)

        if verbose:
            print("fin: ",finopts)
            print("co: ",col_ind)
        nahlist = []

        # go through and modify accordingly via justified diagonal steps
        for x in finopts:
            ah = self.copy()
            new_ends = []

            if skew:
                ah.grid.append([0 for j in range(ah.ends[-1][1]+1)])
            else:
                # make room since paths can move to the right
                ah.grid[-1].extend([0 for j in range(1)])
                ah.grid.append([0 for j in range(ah.ends[-1][1]+1+1)])

            for i,y in enumerate(x): # pick up choice for given path
                # print("i,y (which path from left, amt to move) is: ",i,y)
                # if skew, want to move left-justified beads
                if skew:
                    # make leftmost y beads in this sequence slant down to the left
                    for jj in range(arr[i][0],arr[i][0]+y):
                        j = col_ind[jj]                                         # convert column to a path index
                        ah.paths[j]['word'].append('L')                          # add on to the path
                        old_end = ah.paths[j]['end']                             
                        ah.paths[j]['end'] = [old_end[0]+1,old_end[1]-1]            # update the ending point data
                        ah.grid[-2][jj] |= VX_BL                                  # update grid for point leaving from
                        ah.grid[-1][jj-1] |= VX_TR                                # update grid for new arrival point
                        new_ends.append([old_end[0]+1,old_end[1]-1,j])              # update array of ending points
                    # make remaining beads travel straight down
                    for jj in range(arr[i][0]+y,arr[i][1]+1):
                        j = col_ind[jj]
                        ah.paths[j]['word'].append('S')
                        old_end = ah.paths[j]['end']                             
                        ah.paths[j]['end'] = [old_end[0]+1,old_end[1]]         # update the ending point data
                        ah.grid[-2][jj] |= VX_BOT                               # update grid for point leaving from
                        ah.grid[-1][jj] |= VX_TOP                               # update grid for new arrival point
                        new_ends.append([old_end[0]+1,old_end[1],j])              # update array of ending points
                else:
                    # make rightmost y beads in this sequence slant down to the right
                    for jj in range(y):
                        j = col_ind[arr[i][1]-jj]
                        if verbose:
                            print("jj: ",jj,i,"col index: ",j," ",arr[i][1]-jj)
                        ah.paths[j]['word'].append('R')
                        old_end = ah.paths[j]['end']                             
                        ah.paths[j]['end'] = [old_end[0]+1,old_end[1]+1]       # update the ending point data
                        ah.grid[-2][arr[i][1]-jj] |= VX_BR                     # update grid for point leaving from
                        ah.grid[-1][arr[i][1]-jj+1] |= VX_TL                   # update grid for new arrival point
                        new_ends.append([old_end[0]+1,old_end[1]+1,j])         # update array of ending points
                    # make remaining beads travel straight down
                    for jj in range(arr[i][0],arr[i][1]-y+1):
                        j = col_ind[jj]
                        ah.paths[j]['word'].append('S')
                        old_end = ah.paths[j]['end']                             
                        ah.paths[j]['end'] = [old_end[0]+1,old_end[1]]            # update the ending point data
                        ah.grid[-2][jj] |= VX_BOT                               # update grid for point leaving from
                        ah.grid[-1][jj] |= VX_TOP                               # update grid for new arrival point
                        new_ends.append([old_end[0]+1,old_end[1],j])              # update array of ending points

            ah.ends = list(sorted(new_ends, key = lambda zz: zz[1]))
            ah.extend_grid()
            nahlist.append(ah)

        return LC(nahlist)

    #####################################################################################3
    def _apply_ec_skew(self,b,verbose=True):
        return self._apply_ec(b,skew=True,verbose=verbose)

    #####################################################################################3
    def _incoming_path(self,r,c):
        """ True if path comes in from top or diagonally from top or trailhead
        """
        # print(r,c)
        return (self.grid[r][c] & VX_TOP) > 0 or (self.grid[r][c] & VX_TL) > 0 or \
            (self.grid[r][c] & VX_TR) > 0 or (self.grid[r][c] & VX_TRAILHEAD) > 0

    #####################################################################################3
    def get_shape(self,r=0,transpose=False):
        """ return partition encoded by r-th row; no zero parts!
        """
        arr = [self._incoming_path(r,c) for c in range(len(self.grid[r]))]
        # print("duh arr: ",arr)
        pcols = list(filter(lambda x: arr[x], range(len(arr))))      # cols with paths
        ncols = list(filter(lambda x: not arr[x], range(len(arr))))  # cols without paths

        if not transpose:
            # for each column with a path, count number of blanks to the left
            return [len(list(filter(lambda x: x < y, ncols))) for y in reversed(pcols)]
        else:
            return [len(list(filter(lambda x: x > y, pcols))) for y in ncols]

    #####################################################################################3
    def _get_cols(self,row,holes=False,verbose=True):
        """ return columns of paths in a given row (before subsequent E/W steps)
        """
        arr = []
        for i in range(len(self.grid[row])):
            incoming = (self.grid[row][i] & VX_TOP) > 0 or \
                (self.grid[row][i] & VX_TL) > 0 or \
                (self.grid[row][i] & VX_TR) > 0 or \
                (self.grid[row][i] & VX_TRAILHEAD) > 0
            # this is really an xor --- if not looking for holes then want something incoming
            if holes != incoming:
                arr.append(i)
        if holes:
            return [len(self.grid[row])-x-1 for x in arr]
        return arr

    #####################################################################################3
    def _has_diag_west(self,r,verbose=True):
        """ see if they're any diagonal and/or west moves in going from row r -> r+1
        """
        has_diag = False
        has_west = False
        for k in self.paths.keys():
            idx = 0
            cnt = 0
            if verbose:
                print("----> ",r,self.paths[k])
            # print("bb: ",self.paths[k]['word'],r)
            while cnt < r:
                if self.paths[k]['word'][idx] in ['S','R','L']:
                    cnt += 1
                idx += 1
            if self.paths[k]['word'][idx] in ['R','L']:
                has_diag = True
            if self.paths[k]['word'][idx] in ['E','W']:
                has_west = True
        return has_diag,has_west

    #####################################################################################3
    def _apply_omega(self,verbose=True):
        """ interchange beads and gaps; reverse the abacus
        """
        # make sure each row has the same length
        self.extend_grid()

        # make an initial ah corresponding to transpose of first row
        shape = self.get_shape(r=0,transpose=True)
        ab = AH.snu_abacus(shape)
        ab.extend_grid(mx=len(self.grid[0]))

        if verbose:
            print("shape of transpose: ",shape)
            ab.print_grid()

        # curcols and oldcols hold columns of paths or holes (whatever we're interested in)
        # if holes, they get transposed
        curcols = self._get_cols(0,holes=True)
        for row in range(len(self.grid)-1):
            oldcols = curcols
            curcols = self._get_cols(row+1,holes=True)
            # add in next row
            ab.grid.append([0 for j in range(len(ab.grid[-1]))])
            # run through looking at difference in columns for next entries
            if verbose:
                print("oldcols: ",oldcols)
                print("curcols: ",curcols)
            for j in range(len(oldcols)):
                # find path we are working on
                idx = 0
                # print("asdf r:%s idx: %s abends: %s oldcols[j] %s" % (row,idx,ab.ends,oldcols[j]))
                while ab.ends[idx][0] != row or ab.ends[idx][1] != oldcols[j]:
                    idx += 1
                # this is the path in ab we are working on
                pab = ab.paths[ab.ends[idx][2]]
                c1 = oldcols[j]
                c2 = curcols[j]
                # if next row has a trailhead at endpoint then just end this path now
                if (self.grid[row+1][c2] & VX_TRAILHEAD):
                    continue
                # if goes straight down then just tack an S on and move on
                pab['end'] = [row+1,c2]
                ab.ends[idx] = [row+1,c2,ab.ends[idx][2]]
                if c1==c2:
                    pab['word'].append('S')
                    ab.grid[row][c1] |= VX_BOT
                    ab.grid[row+1][c2] |= VX_TOP
                else:
                    # find a path that crosses over and see whether it's diagonal or not
                    hasdiag,haswest = self._has_diag_west(row,verbose=verbose)
                    if hasdiag and haswest:
                       print("Warning: has both",row)
                    if hasdiag:
                        ab.grid[row][c1] |= VX_BOT
                        ab.grid[row+1][c2] |= VX_TOP
                        if c2 > c1:
                            pab['word'].extend(['E' for x in range(c2-c1)] + ['S'])
                            for kk in range(c2-c1):
                                ab.grid[row][c1+kk] |= VX_RIGHT
                            for kk in range(1,c2-c1+1):
                                ab.grid[row][c1+kk] |= VX_LEFT
                        else:
                            pab['word'].extend(['W' for x in range(c1-c2)] + ['S'])
                            for kk in range(c1-c2):
                                ab.grid[row][c2+kk] |= VX_RIGHT
                            for kk in range(1,c1-c2+1):
                                ab.grid[row][c2+kk] |= VX_LEFT
                    if haswest:
                        if c2 > c1:
                            pab['word'].append('R')
                            ab.grid[row][c1] |= VX_BR
                            ab.grid[row+1][c1+1] |= VX_TL
                        else:
                            pab['word'].append('L')
                            ab.grid[row][c1] |= VX_BL
                            ab.grid[row+1][c1-1] |= VX_TR
                if verbose:
                    print(pab)

        if verbose:
            print("omega:")
            self.print_grid()
            ab.print_grid()
        return ab

    #####################################################################################
    # Creation operators (indexed by integers)
    #####################################################################################
    @classmethod
    def Sm_op_simplified(cls,m,lc,simplified=False,verbose=True):
        """ Bernstein creation operator S_m --- simplified version of adding a vertex
        Act on a linear combination of Schur functions
        Theorem 2
        """
        newlc = LC([])
        nahlist = []
        for f in lc.d:
            muo = f['ah'].get_shape(r=-1)[0]

            # find column of last path
            lastcol = f['ah'].ends[-1][1]
            lbl = lastcol-1
            for c in range(lastcol):
                if f['ah'].grid[-1][c] > 0:
                    lbl -= 1
            # lbl should now be label of column just to right of last path
            # newcol is column that we're trying to add something
            newcol = lastcol + (m-lbl)
            # check if that column is empty
            if newcol > lastcol:
                f['ah'].extend_grid(mx=max(len(f['ah'].grid[0]),newcol+1))
            # we get a non-zero term
            if f['ah'].grid[-1][newcol] == 0:
                nah = f['ah'].copy()  

                # add in a new path
                nah.grid[-1][newcol] |= VX_TRAILHEAD
                nkey = max(list(nah.paths.keys()))+1
                nah.paths[nkey] = dict()
                nah.paths[nkey]['start'] = [len(f['ah'].grid)-1,newcol]
                nah.paths[nkey]['end'] = [len(f['ah'].grid)-1,newcol]                
                nah.paths[nkey]['word'] = []

                # determine the adjustment to the sign
                tmpk = len(list(filter(lambda x: nah.grid[-1][x] > 0, range(newcol+1,len(f['ah'].grid[-1])))))
                nah.paths[nkey]['sgn'] = 1 # (-1)**tmpk # not used
                tmp = f['ah'].ends + [[len(f['ah'].grid)-1,newcol,nkey]]
                nah.ends = list(sorted(tmp, key = lambda zz: zz[1]))
                newlc.add_LC((-1)**tmpk*f['sgn'],0,LC([nah]))
        return newlc 

    @classmethod
    def Sm_op(cls,m,lc,simplified=False,verbose=True):
        """ Bernstein creation operator S_m
        Act on a linear combination of Schur functions
        Formula (16)
        """
        if simplified:
            return AH.Sm_op_simplified(m,lc,verbose=verbose)

        newlc = LC([])
        for f in lc.d:
            # e_c^skew requires c <= number of distinct parts of argument
            for c in range(len(f['ah'].get_shape(r=-1))+1):
                # apply the e_c skew operator to f
                nlc = f['ah']._apply_ec_skew(c,verbose=verbose)
                if verbose:
                    print("======================================== c = ",c,len(nlc.d))
                sgn = (-1)**c
                for g in nlc.d:
                    # add all of these new terms in with given multiplicative modification to coefficient
                    if verbose:
                        print("Apply hc to:")
                        g['ah'].print_grid()
                    tmplc = g['ah']._apply_hc(m+c,verbose=verbose)
                    if verbose:
                        print("---------------------")
                    newlc.add_LC(sgn,0,tmplc)
        return newlc

    #####################################################################################
    @classmethod
    def Hm_op(cls,m,lc,simplified=False,verbose=True):
        """ Jing creation operator H_m
        Act on a linear combination of Schur functions
        Formula (18)
        """
        newlc = LC([])
        for f in lc.d:
            # h_c^skew requires first part to be of length at least c
            for c in range(f['ah'].get_shape(r=-1)[0]+1):
                # apply the h_c skew operator to f
                nlc = f['ah']._apply_hc_skew(c,verbose=verbose)
                if verbose:
                    print("========================================")
                mypow = c
                for g in nlc.d:
                    # add all of these new terms in with given multiplicative modification to coefficient
                    tmplc = AH.Sm_op(m+c,LC([g['ah']]),simplified=simplified,verbose=verbose)
                    if verbose:
                        print("g is")
                        g['ah'].print_grid()
                        print("---------------------")
                    newlc.add_LC(f['sgn']*g['sgn'],f['pow']+g['pow']+mypow,tmplc)
        return newlc

    #####################################################################################
    @classmethod
    def Cm_op(cls,m,lc,simplified=False,verbose=True):
        """ Creation operatoe C_m (as defined in Remark 3.7, Haglund-Morse-Zabrocki, 
        *A compositional shuffle conjecture specifying touch points of the Dyck path*
        Act on a linear combination of Schur functions
        Formula (20)
        """
        newlc = LC([])
        for f in lc.d:
            # h_c^skew requires first part to be of length at least c
            for c in range(f['ah'].get_shape(r=-1)[0]+1):
                # apply the h_c skew operator to f
                nlc = f['ah']._apply_hc_skew(c,verbose=verbose)
                if verbose:
                    print("========================================")
                mysgn = (-1)**(m-1)
                mypow = 1-m-c
                for g in nlc.d:
                    # add all of these new terms in with given multiplicative modification to coefficient
                    tmplc = AH.Sm_op(m+c,LC([g['ah']]),simplified=simplified,verbose=verbose)
                    if verbose:
                        print("results are: ")
                        tmplc.print_lc()
                    if verbose:
                        print("---------------------",mysgn,mypow)
                    newlc.add_LC(mysgn*f['sgn'],mypow+f['pow'],tmplc)
        return newlc

    #####################################################################################
    @classmethod
    def Bm_op(cls,m,lc,simplified=False,verbose=True):
        """ B_m operator defined as omega \circ C_m \circ omega
        Act on a linear combination of Schur functions
        Formula (21) 
        """
        nlc = LC([])
        arr = []
        # apply omega to argument then apply B_m
        for f in lc.d:
            tlc = AH.Hm_op(m,LC([f['ah']._apply_omega(verbose=verbose)]),simplified=simplified,verbose=verbose)
            nlc.add_LC(f['sgn'],f['pow'],tlc)
        # apply omega operator in-place
        for g in nlc.d:
            g['ah'] = g['ah']._apply_omega(verbose=verbose)

        return nlc

    #####################################################################################
    # Operators indexed by sequences of integers applied to 1
    # By default, all use the simplified version of S_m
    #####################################################################################
    @classmethod
    def S_alpha(cls,alpha,simplified=True,verbose=False):
        """ Computes \prod_i S_{alpha_i} (1) for any finite seq of integers alpha
        For alpha a partition mu, equals Schur function s_mu
        Equation (3)
        """
        lc = LC([AH.snu_abacus()])
        for a in reversed(alpha):
            lc = AH.Sm_op(a,lc,simplified=simplified,verbose=verbose)
        return lc

    @classmethod
    def H_alpha(cls,alpha,simplified=True,verbose=False):
        """ Computes \prod_i H_{alpha_i} (1) for any finite seq of integers alpha
        For alpha a partition mu, equals Hall-Littlewood H_mu
        Equation (4)
        """
        lc = LC([AH.snu_abacus()])
        for a in reversed(alpha):
            lc = AH.Hm_op(a,lc,simplified=simplified,verbose=verbose)
        return lc

    @classmethod
    def B_alpha(cls,alpha,simplified=True,verbose=False):
        """ Computes \prod_i B_{alpha_i} (1) for any finite seq of integers alpha
        Equation (5)
        """
        lc = LC([AH.snu_abacus()])
        for a in reversed(alpha):
            lc = AH.Bm_op(a,lc,simplified=simplified,verbose=verbose)
        return lc

    @classmethod
    def C_alpha(cls,alpha,simplified=True,verbose=False):
        """ Computes \prod_i C_{alpha_i} (1) for any finite seq of integers alpha
        Equation (6)
        """
        lc = LC([AH.snu_abacus()])
        for a in reversed(alpha):
            lc = AH.Cm_op(a,lc,simplified=simplified,verbose=verbose)
        return lc

def random_ah(nu,seq,verbose=False):
    """ generate a random abacus history 
        return a seed to regenerate
    """
    ab = AH.snu_abacus(nu)
    i = 0
    ab.print_grid()
    while i < len(seq):
        if seq[i] == 0:
            tmp = ab._apply_ec(seq[i+1],verbose=verbose)
        if seq[i] == 1:
            tmp = ab._apply_ec_skew(seq[i+1],verbose=verbose)
        if seq[i] == 2:
            tmp = ab._apply_hc(seq[i+1],verbose=verbose)
        if seq[i] == 3:
            tmp = ab._apply_hc_skew(seq[i+1],verbose=verbose)
        ab = tmp[seq[i+2]%len(tmp)]
        print("-------------------------------------------------")
        ab.print_grid()
        i+=3
    return ab