import re   # used for weakly comparing trees 


class ValueTree():
    """ValueTree is class with attributes and methods common to trees of values
    
    Parameters
    ----------
    value : str     (default = "")
          Value for the root vertex of tree (used to generate the rest of tree)
    root  : boolean (default = True)
          Indicates if this is the root vertex (first call) of tree
          
    Attributes
    ----------
    value    : string
          Value of this vertex
    weight   : integer
          Weight (number of edges) supported by vertex
    _branches : list of ValueTrees
          Array of child nodes (subtrees)
    """
    
    
    _pos = 0   # use global position variable when scanning expressions to build trees
    
    
    def __init__(self,root=True):
        self._branches = []   # list of branches out of vertex ("child trees")
        self.value    = ""     # value tree stores a value at each vertex
        self.weight   = -1     # weight is total number of edges supported at vertex
                
        if root:               # if this is not within a recursion
            ValueTree._pos = 0 #  then start reading at the beginning

            
    def __str__(self):
        """String version of tree is value at root"""
        return self.value

    def __hash__(self):
        """Hash using the value of supported tree"""
        return hash(self.value)
    
    def __len__(self):
        """weight is number of edges, len is number of vertices"""
        return self.weight + 1
    
    def letters(self):
        """Get letters and multiplicities from tree"""
        return ''.join(sorted(re.sub(r'[/\W+/g]', '', self.value)))
    
    #########################
    # & is 'weak pairing' -- verify that objects use same letters with same multiplicity
    #                        this is used when computing pairings of symbols and Lie brackets
    #
    def __and__(self,other):
        """weak pairing of two objects: compare letters and multiplicity"""
        
        if self.weight != other.weight:                           # check lengths
            return False
        
        for x in list(set(re.sub(r'[/\W+/g]', '', self.value))):  # get list of unique letters
            if not self.value.count(x) == other.value.count(x):   # compare multiplicity of letters
                return False
        return True
    #
    ##########################
    

    
    def __iter__(self):
        """Dept-first iteration"""
        yield self
        
        for branch in self._branches:
            for twig in branch:
                yield twig
                
        # note: maybe better to use chain and imap from itertools???
        #
        # from itertools import chain, imap
        # for node in chain(*imap(iter, self._branches)):
        #     yield node
        # yield self

        
    #################
    #
    #  currently unused methods, but interesting
    #
    def __bool__(self):
        """True if tree is nonempty"""
        return self.weight != -1
       
    
    def __eq__(self,other):
        """trees are equal if values at root are equal"""
        return str(self) == str(other)
    
    
    def __lt__(self,other):
        """ordering is by weight then value"""
        return (self.weight, self.value) < (other.weight, other.value)
    
        
        
##################################################################
##################################################################

   
class LieTree(ValueTree):
    """LieTree is a Lie bracket and tree of subbrackets, used to quickly get left and right subbrackets
    
    Parameters
    ----------
    bracket : string   (default "")
         The Lie bracket to split apart. Use letters for generators, spaces are ignored, commas optional.
    root    : boolean  (default True)
         This parameter is only used interally when recursively building a tree.  DON'T USE IT!
         
    Example
    -------
    bracket = LieTree("[ [a,b] , [ [c,d], e] ]")
    
    
    Attributes
    ----------
    value    : string
         The Lie bracket supported at this node
    weight   : integer
         The weight (number of bracket symbols) of bracket
    bracket  : list of LieTrees
         The left and right subbrackets
    short    : string
         Short version of bracket (don't print ,)
    """

    
    def __init__(self, bracket="", root=True):
        super().__init__(root)
        
        if root:            # on initial call, strip whitespace, comma, and ]
            #                 (assume valid bracket input with single letter entries)
            bracket = re.sub(r'[\],\s]', '', bracket)
     
        if bracket == "":
            return
        
        # read left to right across the bracket expression using the _pos pointer to
        # track where we are looking between recursive calls

        
        if bracket[ValueTree._pos] == "[":   # this node is a bracket of subexpressions
            ValueTree._pos += 1                            # advance past [
            
            self.bracket = [LieTree(bracket,False) , LieTree(bracket,False)] 

        else:                            # this node is a single element
            self.value  = bracket[ValueTree._pos]         # include element
            self.weight = 0
            ValueTree._pos += 1                           # advance to next position
                    

    @property
    def bracket(self):
        return _branches
    
    
    @bracket.setter
    def bracket(self, bracket):
        """"set left and right values of bracket -- only do this at a root!"""
        self._branches = bracket
        self.value = f'[{self._branches[0].value},{self._branches[1].value}]'
        self.weight = 1 + self._branches[0].weight + self._branches[1].weight


    @property
    def left(self):
        """Left subbracket expression"""
        
        if self.weight > 0:
            return self._branches[0]
        
        return None
    
    @property
    def right(self):
        """Right subbracket expression"""
        
        if self.weight > 0:
            return self._branches[1]
        
        return None        
    
    @left.setter
    def left(self, subbracket):
        """set left subbracket -- only do this at the root!"""
        if len(self._branches) == 0:
            self._branches.append(subbracket)
        else:
            self._branches[0] = subbracket
        
        if len(self._branches) == 2 and isinstance(self._branches[1],LieTree):
            self.value  = f'[{self._branches[0].value},{self._branches[1].value}]'
            self.weight = 1 + self._branches[0].weight + self._branches[1].weight
            
    @right.setter
    def right(self, subbracket):
        """set right subbracket -- only do this at the root!"""
        if len(self._branches) == 0:
            self._branches[0] = None
            self._branches.append(subbracket)
        elif len(self._branches) == 1:
            self._branches.append(subbracket)
        else:            
            self._branches[1] = subbracket
        
        if isinstance(self._branches[0],LieTree):
            self.value  = f'[{self._branches[0].value},{self._branches[1].value}]'
            self.weight = 1 + self._branches[0].weight + self._branches[1].weight
        
    
    @property
    def short(self):
        return re.sub(',','', self.value)
    
    @short.setter         # you probably shouldn't change the bracket value of a node
    def short(self,string):
        value = list(string)
        for i in reversed(range(1,len(value))):
            if ((value[i-1].isalpha() and value[i].isalpha()) or
                (value[i-1] == ']'    and value[i].isalpha()) or
                (value[i-1].isalpha() and value[i] == '[')):
                value[i:i] = [',']
        self.value = ''.join(value)
    

    ###################
    #
    # Interesting things that aren't currently used
    #    
    def __mul__(self, other):
        """Overload multiplication to be Lie bracket"""
        
        if isinstance(other, LieTree):
            product = LieTree()
        
            product.bracket = [ self , other ]
            
            return product
        
        return NotImplemented

        
    def __repr__(self):
        return f"LieTree('{self.value}')"


##################################################################

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

lie = LieTree("[a,[[b,c],[d,[e,f]]]]")

print(f'      bracket = {lie}\nshort version = {lie.short}\n\n subbrackets:')

for n in lie:
    print(n)

print()

lie = LieTree("[a,b]") * LieTree("[c,d]")
print(lie)

print(lie.left)
print(lie.right)

print(LieTree("[[a,a],[b,c]]") & LieTree("[[a,b],[c,a]]"))  # grading is 2a 1b 1c for both
print(LieTree("[[a,b],[b,c]]") & LieTree("[[a,b],[c,a]]"))  # grading for left is 1a 2b 1c

print(lie.letters())

##################################################################

class EilWord():
    """EilWord is a linear coLie symbol <=> associative word
      EilWord objects have multiplication overloaded to perform pairing with Lie brackets and configuration braiding with group elements
    
    Parameters
    ----------
    word : string   (default "")
        This is the linear symbol written as a word Example: abaa <=> (((a)b)a)a

         
    Example
    -------
    word = EilWord("abaab")
    
    
    Attributes
    ----------
    value    : string
         The word
    weight   : integer
         The weight of the corresponding symbol
    symbol   : string
         The symbol corresponding to the associative eil word
    """
    
    
    def __init__(self,word):
        self.value = word
    
    

    def __mul__(self,other):
        """Multiplication is overloaded to compute pairing with Lie brackets and configuration braiding with group elements"""
        
        #########################
        #
        # Pairing with Lie Brackets recursively using bracket-cobracket compatibility from [SiWa]
        #
        if isinstance(other, LieTree):
            
            if not self.__weakPair(self.value,other):  # check weakpairing
                return 0    
            
            return self.__pair(self.value,other)       # recursively comput pairing
        
       
        #########################
        #
        # Counting configuration braidings in words using algorithm from [GOSW]
        #   (This algorithm is originally due to Aydin Ozbek)
        #
        if isinstance(other, SignedWord):        # Algorithm in [GOSW]:
            
            sum   = [0] * len(self.value)        # s value for each eil position
            delta = [0] * len(self.value)        # Δ value for each eil position
            
            for letter in other:                 # pass across the word
                for i in range(len(self.value)): #  evaluating eil symbol from leaf to root
                    
                    sum[i]  += delta[i]          # 1. add Δ value to s value
                    delta[i] = 0                 #    and set Δ to 0 
                    
                    value = 0                    # 2. get value of branches
                    
                    if self.value[i] == letter.value:   # check if update is needed
                        if i == 0:               #    at first vertex there is no branch
                            value = 1 
                        else:                    #    otherwise look at value above
                            value = sum[i-1]
                            
                    if not letter:               # 3. update s and Δ
                        sum[i]  -= value         #    at inverses, immediately update s
                    else:
                        delta[i] = value         #    at generators, update Δ
                        
            return sum[-1] + delta[-1]           # Braiding value is s + Δ at root
        
        
        return NotImplemented
    
    
    
    def __weakPair(self,word,lie):
        """weakPair is used internally to quickly rule out pairings that will be 0
           It only compares multiplicity of letters appearing in word and Lie bracket
           This is the analog of the & operation in ValueTree (which is used for general symbols)
        """
                
        if len(word) != len(lie):                         # compare length
            return False
        
        for x in list(set(word)):                         # get list of unique letters
            if not word.count(x) == lie.value.count(x):   # compare multiplicity of letters
                return False
        return True

    
    
    def __pair(self,word,other):
        """pair is used internally to recursively compute pairings of eil words with Lie brackets
           Pairing is computed by recursively using bracket-cobracket duality. Cobracket of eil words is given by cutting.
           To speed things up, we compare size and letter grading (weakPair) before recursing.  This immediately eliminates most 0 pairings.
        """
        
        if len(word) == 1:                  # Base case!  Length 1 words are just a single generator
            return int(word == other.value) # Check if generators match!
        
        pairing = 0                         # Otherwise we use cobracket-bracket compatibility with pairing [SiWa]
        
        #       < eil , lie > =  < L(eil) , L(lie) > * < R(eil) , R(lie) >
        #                      - < R(eil) , L(lie) > * < L(eil) , R(lie) >
        #
        # where  ]eil[ = sum L(eil) x R(eil)   and    lie = [ L(lie) , R(lie) ]
        
        if self.__weakPair(word[:len(other.left)], other.left):     # before recursing, weakpair start with left 
            pairing += self.__pair(word[:len(other.left)],other.left) * self.__pair(word[len(other.left):],other.right)

        if self.__weakPair(word[:len(other.right)], other.right):   # before recursing, weakpair start with right 
            pairing -= self.__pair(word[:len(other.right)],other.right) * self.__pair(word[len(other.right):],other.left)            

            
        return pairing
    
    
    #####################
    #
    # maybe we should allow eil(lie) instead of just eil * lie ???
    #
    def __call__(self, other):
        return self * other
    
    
    
    def __str__(self):
        return self.value

    def __hash__(self):
        return hash(self.value);
    
    
    ###################
    #
    # Interesting things that aren't currently used
    #
    @property
    def symbol(self):
        n = len(self.value)-2

        symbol = ['('] * (n+1)
        symbol.append(self.value[0])
        for i in range(1,len(self.value)):
            symbol.extend([')',self.value[i]])
                        
        return ''.join(symbol) 

    def letters(self):
        return ''.join(sorted(self.value))
    
    @property
    def weight(self):
        return len(self.value)-1
       
    
    def __len__(self):
        return len(self.value)

    
    def __repr__(self):
        return f'EilWord("{self.value}")'
    
    
    def __eq__(self,other):
        return self.value == other.value
    
    
    def __lt__(self,other):
        return self.value < other.value
    
    
    def cobracket(self):
        """This returns a generator which yields tuples of the cobracket (cutting the word at each position)"""
        return ( (EilWord(self.value[:n]), EilWord(self.value[n:]))  for n in range(1, len(self.value)) )
    
    
##################################################################

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

word = EilWord("aab")
print(f'{word} --> {word.symbol}')

print(f'  pairing with [[a,b],a] = {word * LieTree("[[a,b],a]")}')
print(f' evaluation on [[a,b],a] = {word(LieTree("[[a,b],a]"))}')

word = EilWord("aabb")

print(f'\n Cobracket of {word}:')
print([(str(cobr[0]),str(cobr[1])) for cobr in word.cobracket()])

print("\n Pairing matrix for (3,2) grading of Lie algebra:")
print([EilWord("aaabb")*LieTree("[a,[a,[[a,b],b]]]"), EilWord("aaabb")*LieTree("[[a,[a,b]],[a,b]]")])
print([EilWord("aabab")*LieTree("[a,[a,[[a,b],b]]]"), EilWord("aabab")*LieTree("[[a,[a,b]],[a,b]]")])

##################################################################

class EilTree(ValueTree):
    """EilTree encodes the tree structure of a coLie symbol
      EilTre objects have multiplication overloaded to perform pairing with Lie brackets and configuration braiding with group elements
    
    Parameters
    ----------
    symbol : string   (default "")
         The symbol to split apart. Use letters for generators, spaces are ignored.
    root   : boolean  (default True)
         This parameter is only used interally when recursively building a tree.  DON'T USE IT!
         
    Example
    -------
    symbol = EilTree("( ((a)(b)b) (b ((a)b)) a)")
    
    
    Attributes
    ----------
    value      : string             (default: "")
         The symbol supported at this node
    decoration : string             (default: "")
         The free variable of the symbol (at the given node)
    weight     : integer            (default: -1)
         The weight (number of parenthesis pairs) of symbol (supported by the given node)
    subsymbols : list of EilTree's  (default: [])
         The immediate subsymbols of the given symbol
    normalValue : string
         A "normalized" version of the symbol -- move free variables to right, etc
    """
    
    def __init__(self, symbol="", root=True):
        super().__init__(root)
        
        self.decoration = ""     # keep track of decoration for each vertex

        if root:                 # on initial call, strip whitespace
            symbol = symbol.translate(str.maketrans('', '', ' \n\t\r'))
            
        if symbol == "":
            return
 
        # read left to right across the symbol expression using the _pos pointer to
        # track where we are looking between recursive calls

        start = ValueTree._pos           # this is the staring position for the subsymbol
        
        while ValueTree._pos < len(symbol) and not symbol[ValueTree._pos] == ")":
            
            if symbol[ValueTree._pos] == "(":            # begin a subsymbol
                ValueTree._pos  += 1                       # advance into subsymbol
                self._branches.append(EilTree(symbol,False))# append new subtree
                
            else:                                        # this is free variable (decoration of vertex)
                self.decoration = symbol[ValueTree._pos]   # record free variable
                ValueTree._pos += 1                        # advance past
                
        end = ValueTree._pos             # this is the ending position for the subsymbol
        
        self.value = symbol[start:end]   # this is the current subsymbol
        
        self.weight = sum([branch.weight + 1 for branch in self.subsymbols])
        # self.weight = self.value.count('(')            # this is equivalent but probably slower?

        ValueTree._pos += 1      # advance past the closing of subsymbol

        

    def __mul__(self, other):
        """Multiplication is overloaded to compute pairing with Lie brackets and configuration braiding with group elements"""
        
        #########################
        #
        # Pairing with Lie Brackets recursively using bracket-cobracket compatibility from [SiWa]
        #   
        if isinstance(other, LieTree):
            
            if not self & other:       # check weakpairing
                return 0    
            
            return self.__pair(other)  # recursively compute pairing
  

        #########################
        #
        # Counting configuration braidings in words using algorithm from [GOSW]
        #
        if isinstance(other, SignedWord):
            counter = CountTree(self)    # analog of sum and delta arrays for EilWord
            
            for letter in other.word:
                counter.evaluate(letter) # evaluate the counter on each letter in the word
                
            return counter.total         # this is s + Δ at root
            
        
        return NotImplemented
    
    
    
    def __pair(self, other):
        """pair is used internally to recursively compute pairings of eil symbols with Lie brackets
           Pairing is computed by recursively using bracket-cobracket duality. 
           Cobracket of symbols is given by cutting out a subtree, yielding sub and excised trees.
           To speed things up, we compare size and letter grading (weakPair) before recursing.  This immediately eliminates most 0 pairings.
        """        
        
        if self.weight == 0:            # Base case! Symbol is a single character 
            return int(self.value == other.value)   # compare vs Lie value
        
        pairing = 0          # Otherwise we use cobracket-bracket compatibility with pairing [SiWa]
        
        #       < eil , lie > =  < L(eil) , L(lie) > * < R(eil) , R(lie) >
        #                      - < R(eil) , L(lie) > * < L(eil) , R(lie) >
        #
        # where  ]eil[ = sum L(eil) x R(eil)   and    lie = [ L(lie) , R(lie) ]
        #    L(eil) is subsymbol
        #    R(eil) is result of excising subsymbol
        
        for subsymbol in self:           # iterate through all subsymbols of symbol
            if subsymbol & other.left:   #   weakpair with subsymbol first, since excised symbol requires computation
                pairing += subsymbol.__pair(other.left) * self.__excise(subsymbol).__pair(other.right)
            
            if subsymbol & other.right:  #   weakpair with subsymbol first, since excised symbol requires computation
                pairing -= subsymbol.__pair(other.right) * self.__excise(subsymbol).__pair(other.left)
            
        return pairing
    
        # Note: this might be sped up by sorting subsymbols by weight initially rather than searching for weights matching other.left and other.right
                
               
        
       
    def __excise(self, subsymbol):  
        """excise is used internally to compute the symbol remaining after a subsymbol is removed
           It recursively copies a tree, skipping the excised subsymbol (and its supported subtree).
        """
        
        #if self is subsymbol:  # This should never happen during internal recursive usage!
        #    return EilTree()   
        
        eil = EilTree()        # Begin with a blank node
        
        eil.decoration = self.decoration # copy the decoration
        
        if self.weight == 0:   # Direct copy if this is a leaf node
            eil.weight = 0
            eil.value  = self.value
            
        else:    
            eil.subsymbols = [symbol.__excise(subsymbol) for symbol in self.subsymbols if not symbol is subsymbol]          
            
        return eil
    
    @property
    def subsymbols(self):
        return self._branches
    
    @subsymbols.setter
    def subsymbols(self, list):
        self._branches = list
        self.value = ''.join([f'({str(branch)})' for branch in self._branches]+[self.decoration])
        self.weight = sum([branch.weight + 1 for branch in self._branches])
       
        # self.weight = self.value.count('(')  # this should be equivalent, but probably slower?
 

    # I like to write free elements last, so append() and extend()  will actually insert at start...
    def append(self, subsymbol):
        """Insert new subsymbol, updating weight and value"""
        self._branches[:0] = [subsymbol]                  # insert subsymbol at start
        self.weight += subsymbol.weight+1                 # add to weight
        self.value   = f'({subsymbol.value}){self.value}' # add to value 
        
    def extend(self, subsymbols):
        """Insert array of subsymbols, updating weight and value"""
        self._branches[:0] = subsymbols
        self.weight += sum([symbol.weight+1 for symbol in subsymbols])
        tmp          = ')('.join([symbol.value for symbol in subsymbols])
        self.value   = f'({tmp}){self.value}'

    def copy(self):
        """Create a deep copy of EilTree"""
        eil = EilTree()
        eil.decoration = self.decoration
        eil.value , eil.weight = self.value , self.weight
                
        if len(self._branches) > 0:
            eil._branches = [subsymbol.copy() for subsymbol in self._branches]
        
        return eil
 

    ###################
    #
    # Interesting things that aren't currently used
    #
    @property
    def normalValue(self):       # the normal Value has free terms written last
        if self.weight == 0:     #  this should probably also sort branches nicely
            return self.value    #  define < used for sorting later....
        
        return ''.join([f'({branch.normalValue})' for branch in sorted(self._branches,reverse=True)]+[self.decoration])
 

    
    def normalize(self):
        """Convert EilTree to 'normalized' form -- sort branches and move free letter to the far right"""
        for symbol in self._branches:    
            symbol.normalize()
            
        #self.value = ''.join([f'({str(branch)})' for branch in sorted(self.branches,reverse=True)]+[self.decoration])
        self.subsymbols = [branch for branch in sorted(self._branches,reverse=True)]
     
    
    def __eq__(self,other):               # compare normalized forms so (a)b == b(a)
        if isinstance(other, EilTree):    #   Note: isn't perfect...
            return self.normalValue == other.normalValue
        
        return False
  

    # < is used when writing in normal form and comparing EilTrees
    def __lt__(self,other):
        if self.value == other.value:     # if values match then these are equal
            return False
        
                                          # next sort by weight and decoration
        if (self.weight,self.decoration) < (other.weight,other.decoration):
            return True
        if (self.weight,self.decoration) > (other.weight,other.decoration):
            return False
        
                                          # next sort by number of branches
        if len(self.subsymbols) < len(other.subsymbols):
            return True
        if len(self.subsymbols) > len(other.subsymbols):
            return False
        
                                           # next look at decorations and weights of branches
        return sorted([(branch.decoration,branch.weight) for branch in self.subsymbols]) < sorted([(branch.decoration,branch.weight) for branch in other.subsymbols])
    
        # note: this may incorrectly sort a(a(b)) and a(a(c))
    
    
        
    def __gt__(self,other):
        return other < self
        
        
    def __repr__(self):
        return f"EilTree('{self.value}')"        
    
    
    
    ################
    #
    # allow eil(lie) instead of just eil * lie
    #
    def __call__(self, other):
        return self * other

    
    def cobracket(self): 
        """returns a generator with tuples of cobracket elements"""
        subsymbols = iter(self)
        next(subsymbols)    # the first term in the iterator is the entire symbol (skip it)
        
        return ((subsymbol,self.__excise(subsymbol)) for subsymbol in subsymbols)
    
##################################################################

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

eil = EilTree("c(b)(a)(c(d(f))(e(f)(g)))(c(d(f))(e(f)(f))")

print(eil.normalValue)

print(eil.letters())

print(EilTree("(a)b(c)") * LieTree("[a,[b,c]]"))

print(EilTree("(((a)b)c)d") * LieTree("[[[a,b],c],d]"))

##################################################################


class CountTree():
    """CountTree is a helper class for combinatorial braiding of coLie symbols on words.
    This copies the structure of an EilTree and takes the place of the 'sum' and 'delta' arrays that were used in the __mul__ method of EilWord. 
    
    Objects of this class should only be used internally!
    
    Parameters
    ----------
    eil : EilTree
       corresponding node of an EilTree
       
    Attributes
    ----------
    sum      : integer
       current s value for this node (initialized to 0)
    delta    : integer
       current Δ value for this node (initialized to 0)
    branches : list of CountTree's
       list of branches from this node
    eil      : EilTree
       corresponding node of the EilTree
    total    : integer
       sum + delta
    """
    
    
    def __init__(self,eil):
        self.sum   = 0
        self.delta = 0
        self.eil   = eil
        
        self.branches = [CountTree(branch) for branch in eil.subsymbols]
        
        
    @property 
    def total(self):
        return self.sum + self.delta
    
    
    def evaluate(self,letter):
        """evaluate updates values of the counter tree at the given letter following the algorithm outlined in [GOSW]
           Compare to the use of 'sum' and 'delta' arrays in the __mul__() method of EilWord.
        """
        
        
        for branch in self.branches:    # Evaluate leaf to root
            branch.evaluate(letter)     #   (update branch values first)   
            
        self.sum  += self.delta         # 1. add Δ to s
        self.delta = 0                  #    and set Δ = 0
        
        value = 0                       # 2. incorporate values from branches
 
        if letter.value == self.eil.decoration: # check if update is needed
            if len(self.branches) == 0: #    at leaf just copy the value
                value = 1
            else:                       #    otherwise add values from branches
                value = sum([branch.sum for branch in self.branches])
            
            
        if not letter:                  # 3. at inverses, immediately update s
            self.sum   -= value
        else:                           #    otherwise, update Δ
            self.delta  = value
        
 

    ###################
    #
    # Interesting things that aren't currently used
    #
    def __iter__(self):
        for branch in self.branches:
            for twig in branch:
                yield twig          
        yield self



##################################################################
##################################################################


class SignedLetter():
    """SignedLetter is a letter with a sign, intended to represent a generator or an inverse
     * as a boolean it is True for generator and False for inverse
     * as an integer it is 1 for generator and -1 for inverse
     * as a string it looks pretty
    
    Parameters
    ----------
    letter : string
        this should be a single character
    sign   : boolean or integer
    
    Examples: 
      SignedLetter("a",False)
      SignedLetter("a",-1)
    
    Attributes
    ----------
    value : string
        this is the letter
    sign  : boolean
        True corresponds to generator
        False correspnds to inverse
    
    """
    def __init__(self,letter,sign):
        self.value = letter
        self.sign  = True if sign == 1 else False
    
    def __bool__(self):
        return self.sign
    
    def __int__(self):
        return 1 if self.sign else -1
    
    def __str__(self):
        return f'{self.value}' if self.sign else f'{self.value}\N{SUPERSCRIPT MINUS}\N{SUPERSCRIPT ONE}'

    def __repr__(self):
        return f'SignedLetter("{self.value}",{"1" if self.sign else "-1"})'

    def short(self):
        return f'{self.value}{"" if self.sign else "-"}'

    def __hash__(self):
        return hash(self.short())

##################################################################


class SignedWord():
    """SignedWord is a list of SignedLetters
    
    Parameters
    ----------
    word : string or list
    
    Examples: 
     SignedWord("aba^{-1}b^{-1}")
     SignedWord("aba-b-")
     SignedWord( [ ("a",1), ("b",1), ("a",-1), ("b",-1) ] )
    
    Attributes
    ----------
    word : list of SignedLetters
    """
    def __init__(self,word):
        self.word = []
        
        if isinstance(word, str):
            i = 0
            while i < len(word):
                if i+1 < len(word) and (word[i+1] == "-" or word[i+1] == "^"):
                    self.word.append(SignedLetter(word[i],-1))
                else:
                    self.word.append(SignedLetter(word[i], 1))
                i += 1
                
                while i < len(word) and not word[i].isalpha():
                    i += 1
        elif isinstance(word, list):
            if isinstance(word[0], SignedLetter):
                self.word = word
            else:    
                self.word = [SignedLetter(x[0],x[1]) for x in word]
        else:
            raise ValueError("Word format not recognized!")
            

    def __len__(self):
        return len(self.word)
            
    def __str__(self):
        return ''.join([str(x) for x in self.word])

    def __repr__(self):
        return 'SignedWord("' + ''.join([x.short() for x in self.word]) + '")'
    
    def __hash__(self):
        return hash(''.join([x.short() for x in self.word]))
        
    def __iter__(self):
        return iter(self.word)      

    def letters(self):
        return ''.join(sorted(set([letter.value for letter in self.word])))
    
##################################################################

#################################################
#     TESTING BLOCK!!!!                         #
#################################################

print(SignedLetter('a',-1))

print(SignedWord('a b a^{-1} b^{-1}'))

print( SignedWord( [ ("a",1), ("b",1), ("a",-1), ("b",-1) ] ) )

print(EilTree("(a)b") * SignedWord("aba-b-"))

print(EilWord("ab") * SignedWord("aba-b-"))

print(SignedWord("aba-b-").letters())

repr(SignedWord( [ ("a",1), ("b",1), ("a",-1), ("b",-1) ] ))