python library with coLie computation objects

1
##################################################################
2
#
3
# Data structures and methods for computing with coLie symbols
4
#  © 2024 Benjamin Walter <[email protected]>
5
#      (dedicated to the memory of Aydin Ozbek)
6
#
7
# Included classes:
8
#   LieTree( bracket string )
9
#   EilTree( symbol string  )
10
#   EilWord( assoc word     )
11
#   SignedWord( signed word )
12
#
13
# See docstrings for more information on use
14
#
15
##################################################################
16

17
import re   # used for weakly comparing trees 
18

19

20
class ValueTree():
21
    """ValueTree is class with attributes and methods common to trees of values
22
    
23
    Parameters
24
    ----------
25
    value : str     (default = "")
26
          Value for the root vertex of tree (used to generate the rest of tree)
27
    root  : boolean (default = True)
28
          Indicates if this is the root vertex (first call) of tree
29
          
30
    Attributes
31
    ----------
32
    value    : string
33
          Value of this vertex
34
    weight   : integer
35
          Weight (number of edges) supported by vertex
36
    _branches : list of ValueTrees
37
          Array of child nodes (subtrees)
38
    """
39
    
40
    
41
    _pos = 0   # use global position variable when scanning expressions to build trees
42
    
43
    
44
    def __init__(self,root=True):
45
        self._branches = []   # list of branches out of vertex ("child trees")
46
        self.value    = ""     # value tree stores a value at each vertex
47
        self.weight   = -1     # weight is total number of edges supported at vertex
48
                
49
        if root:               # if this is not within a recursion
50
            ValueTree._pos = 0 #  then start reading at the beginning
51

52
            
53
    def __str__(self):
54
        """String version of tree is value at root"""
55
        return self.value
56

57
    def __hash__(self):
58
        """Hash using the value of supported tree"""
59
        return hash(self.value)
60
    
61
    def __len__(self):
62
        """weight is number of edges, len is number of vertices"""
63
        return self.weight + 1
64
    
65
    def letters(self):
66
        """Get letters and multiplicities from tree"""
67
        return ''.join(sorted(re.sub(r'[/\W+/g]', '', self.value)))
68
    
69
    #########################
70
    # & is 'weak pairing' -- verify that objects use same letters with same multiplicity
71
    #                        this is used when computing pairings of symbols and Lie brackets
72
    #
73
    def __and__(self,other):
74
        """weak pairing of two objects: compare letters and multiplicity"""
75
        
76
        if self.weight != other.weight:                           # check lengths
77
            return False
78
        
79
        for x in list(set(re.sub(r'[/\W+/g]', '', self.value))):  # get list of unique letters
80
            if not self.value.count(x) == other.value.count(x):   # compare multiplicity of letters
81
                return False
82
        return True
83
    #
84
    ##########################
85
    
86

87
    
88
    def __iter__(self):
89
        """Dept-first iteration"""
90
        yield self
91
        
92
        for branch in self._branches:
93
            for twig in branch:
94
                yield twig
95
                
96
        # note: maybe better to use chain and imap from itertools???
97
        #
98
        # from itertools import chain, imap
99
        # for node in chain(*imap(iter, self._branches)):
100
        #     yield node
101
        # yield self
102

103
        
104
    #################
105
    #
106
    #  currently unused methods, but interesting
107
    #
108
    def __bool__(self):
109
        """True if tree is nonempty"""
110
        return self.weight != -1
111
       
112
    
113
    def __eq__(self,other):
114
        """trees are equal if values at root are equal"""
115
        return str(self) == str(other)
116
    
117
    
118
    def __lt__(self,other):
119
        """ordering is by weight then value"""
120
        return (self.weight, self.value) < (other.weight, other.value)
121
    
122
        
123
        
124
##################################################################
125
##################################################################
126

127
   
128
class LieTree(ValueTree):
129
    """LieTree is a Lie bracket and tree of subbrackets, used to quickly get left and right subbrackets
130
    
131
    Parameters
132
    ----------
133
    bracket : string   (default "")
134
         The Lie bracket to split apart. Use letters for generators, spaces are ignored, commas optional.
135
    root    : boolean  (default True)
136
         This parameter is only used interally when recursively building a tree.  DON'T USE IT!
137
         
138
    Example
139
    -------
140
    bracket = LieTree("[ [a,b] , [ [c,d], e] ]")
141
    
142
    
143
    Attributes
144
    ----------
145
    value    : string
146
         The Lie bracket supported at this node
147
    weight   : integer
148
         The weight (number of bracket symbols) of bracket
149
    bracket  : list of LieTrees
150
         The left and right subbrackets
151
    short    : string
152
         Short version of bracket (don't print ,)
153
    """
154

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

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

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

181
    @property
182
    def bracket(self):
183
        return _branches
184
    
185
    
186
    @bracket.setter
187
    def bracket(self, bracket):
188
        """"set left and right values of bracket -- only do this at a root!"""
189
        self._branches = bracket
190
        self.value = f'[{self._branches[0].value},{self._branches[1].value}]'
191
        self.weight = 1 + self._branches[0].weight + self._branches[1].weight
192

193

194
    @property
195
    def left(self):
196
        """Left subbracket expression"""
197
        
198
        if self.weight > 0:
199
            return self._branches[0]
200
        
201
        return None
202
    
203
    @property
204
    def right(self):
205
        """Right subbracket expression"""
206
        
207
        if self.weight > 0:
208
            return self._branches[1]
209
        
210
        return None        
211
    
212
    @left.setter
213
    def left(self, subbracket):
214
        """set left subbracket -- only do this at the root!"""
215
        if len(self._branches) == 0:
216
            self._branches.append(subbracket)
217
        else:
218
            self._branches[0] = subbracket
219
        
220
        if len(self._branches) == 2 and isinstance(self._branches[1],LieTree):
221
            self.value  = f'[{self._branches[0].value},{self._branches[1].value}]'
222
            self.weight = 1 + self._branches[0].weight + self._branches[1].weight
223
            
224
    @right.setter
225
    def right(self, subbracket):
226
        """set right subbracket -- only do this at the root!"""
227
        if len(self._branches) == 0:
228
            self._branches[0] = None
229
            self._branches.append(subbracket)
230
        elif len(self._branches) == 1:
231
            self._branches.append(subbracket)
232
        else:            
233
            self._branches[1] = subbracket
234
        
235
        if isinstance(self._branches[0],LieTree):
236
            self.value  = f'[{self._branches[0].value},{self._branches[1].value}]'
237
            self.weight = 1 + self._branches[0].weight + self._branches[1].weight
238
        
239
    
240
    @property
241
    def short(self):
242
        return re.sub(',','', self.value)
243
    
244
    @short.setter         # you probably shouldn't change the bracket value of a node
245
    def short(self,string):
246
        value = list(string)
247
        for i in reversed(range(1,len(value))):
248
            if ((value[i-1].isalpha() and value[i].isalpha()) or
249
                (value[i-1] == ']'    and value[i].isalpha()) or
250
                (value[i-1].isalpha() and value[i] == '[')):
251
                value[i:i] = [',']
252
        self.value = ''.join(value)
253
    
254

255
    ###################
256
    #
257
    # Interesting things that aren't currently used
258
    #    
259
    def __mul__(self, other):
260
        """Overload multiplication to be Lie bracket"""
261
        
262
        if isinstance(other, LieTree):
263
            product = LieTree()
264
        
265
            product.bracket = [ self , other ]
266
            
267
            return product
268
        
269
        return NotImplemented
270

271
        
272
    def __repr__(self):
273
        return f"LieTree('{self.value}')"
274

275

276
##################################################################
277
##################################################################
278

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

288
         
289
    Example
290
    -------
291
    word = EilWord("abaab")
292
    
293
    
294
    Attributes
295
    ----------
296
    value    : string
297
         The word
298
    weight   : integer
299
         The weight of the corresponding symbol
300
    symbol   : string
301
         The symbol corresponding to the associative eil word
302
    """
303
    
304
    
305
    def __init__(self,word):
306
        self.value = word
307
    
308
    
309

310
    def __mul__(self,other):
311
        """Multiplication is overloaded to compute pairing with Lie brackets and configuration braiding with group elements"""
312
        
313
        #########################
314
        #
315
        # Pairing with Lie Brackets recursively using bracket-cobracket compatibility from [SiWa]
316
        #
317
        if isinstance(other, LieTree):
318
            
319
            if not self.__weakPair(self.value,other):  # check weakpairing
320
                return 0    
321
            
322
            return self.__pair(self.value,other)       # recursively comput pairing
323
        
324
       
325
        #########################
326
        #
327
        # Counting configuration braidings in words using algorithm from [GOSW]
328
        #   (This algorithm is originally due to Aydin Ozbek)
329
        #
330
        if isinstance(other, SignedWord):        # Algorithm in [GOSW]:
331
            
332
            sum   = [0] * len(self.value)        # s value for each eil position
333
            delta = [0] * len(self.value)        # Δ value for each eil position
334
            
335
            for letter in other:                 # pass across the word
336
                for i in range(len(self.value)): #  evaluating eil symbol from leaf to root
337
                    
338
                    sum[i]  += delta[i]          # 1. add Δ value to s value
339
                    delta[i] = 0                 #    and set Δ to 0 
340
                    
341
                    value = 0                    # 2. get value of branches
342
                    
343
                    if self.value[i] == letter.value:   # check if update is needed
344
                        if i == 0:               #    at first vertex there is no branch
345
                            value = 1 
346
                        else:                    #    otherwise look at value above
347
                            value = sum[i-1]
348
                            
349
                    if not letter:               # 3. update s and Δ
350
                        sum[i]  -= value         #    at inverses, immediately update s
351
                    else:
352
                        delta[i] = value         #    at generators, update Δ
353
                        
354
            return sum[-1] + delta[-1]           # Braiding value is s + Δ at root
355
        
356
        
357
        return NotImplemented
358
    
359
    
360
    
361
    def __weakPair(self,word,lie):
362
        """weakPair is used internally to quickly rule out pairings that will be 0
363
           It only compares multiplicity of letters appearing in word and Lie bracket
364
           This is the analog of the & operation in ValueTree (which is used for general symbols)
365
        """
366
                
367
        if len(word) != len(lie):                         # compare length
368
            return False
369
        
370
        for x in list(set(word)):                         # get list of unique letters
371
            if not word.count(x) == lie.value.count(x):   # compare multiplicity of letters
372
                return False
373
        return True
374

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

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

399
            
400
        return pairing
401
    
402
    
403
    #####################
404
    #
405
    # maybe we should allow eil(lie) instead of just eil * lie ???
406
    #
407
    def __call__(self, other):
408
        return self * other
409
    
410
    
411
    
412
    def __str__(self):
413
        return self.value
414

415
    def __hash__(self):
416
        return hash(self.value);
417
    
418
    
419
    ###################
420
    #
421
    # Interesting things that aren't currently used
422
    #
423
    @property
424
    def symbol(self):
425
        n = len(self.value)-2
426

427
        symbol = ['('] * (n+1)
428
        symbol.append(self.value[0])
429
        for i in range(1,len(self.value)):
430
            symbol.extend([')',self.value[i]])
431
                        
432
        return ''.join(symbol) 
433

434
    def letters(self):
435
        return ''.join(sorted(self.value))
436
    
437
    @property
438
    def weight(self):
439
        return len(self.value)-1
440
       
441
    
442
    def __len__(self):
443
        return len(self.value)
444

445
    
446
    def __repr__(self):
447
        return f'EilWord("{self.value}")'
448
    
449
    
450
    def __eq__(self,other):
451
        return self.value == other.value
452
    
453
    
454
    def __lt__(self,other):
455
        return self.value < other.value
456
    
457
    
458
    def cobracket(self):
459
        """This returns a generator which yields tuples of the cobracket (cutting the word at each position)"""
460
        return ( (EilWord(self.value[:n]), EilWord(self.value[n:]))  for n in range(1, len(self.value)) )
461
    
462
    
463
##################################################################
464
##################################################################
465

466
class EilTree(ValueTree):
467
    """EilTree encodes the tree structure of a coLie symbol
468
      EilTre objects have multiplication overloaded to perform pairing with Lie brackets and configuration braiding with group elements
469
    
470
    Parameters
471
    ----------
472
    symbol : string   (default "")
473
         The symbol to split apart. Use letters for generators, spaces are ignored.
474
    root   : boolean  (default True)
475
         This parameter is only used interally when recursively building a tree.  DON'T USE IT!
476
         
477
    Example
478
    -------
479
    symbol = EilTree("( ((a)(b)b) (b ((a)b)) a)")
480
    
481
    
482
    Attributes
483
    ----------
484
    value      : string             (default: "")
485
         The symbol supported at this node
486
    decoration : string             (default: "")
487
         The free variable of the symbol (at the given node)
488
    weight     : integer            (default: -1)
489
         The weight (number of parenthesis pairs) of symbol (supported by the given node)
490
    subsymbols : list of EilTree's  (default: [])
491
         The immediate subsymbols of the given symbol
492
    normalValue : string
493
         A "normalized" version of the symbol -- move free variables to right, etc
494
    """
495
    
496
    def __init__(self, symbol="", root=True):
497
        super().__init__(root)
498
        
499
        self.decoration = ""     # keep track of decoration for each vertex
500

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

510
        start = ValueTree._pos           # this is the staring position for the subsymbol
511
        
512
        while ValueTree._pos < len(symbol) and not symbol[ValueTree._pos] == ")":
513
            
514
            if symbol[ValueTree._pos] == "(":            # begin a subsymbol
515
                ValueTree._pos  += 1                       # advance into subsymbol
516
                self._branches.append(EilTree(symbol,False))# append new subtree
517
                
518
            else:                                        # this is free variable (decoration of vertex)
519
                self.decoration = symbol[ValueTree._pos]   # record free variable
520
                ValueTree._pos += 1                        # advance past
521
                
522
        end = ValueTree._pos             # this is the ending position for the subsymbol
523
        
524
        self.value = symbol[start:end]   # this is the current subsymbol
525
        
526
        self.weight = sum([branch.weight + 1 for branch in self.subsymbols])
527
        # self.weight = self.value.count('(')            # this is equivalent but probably slower?
528

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

531
        
532

533
    def __mul__(self, other):
534
        """Multiplication is overloaded to compute pairing with Lie brackets and configuration braiding with group elements"""
535
        
536
        #########################
537
        #
538
        # Pairing with Lie Brackets recursively using bracket-cobracket compatibility from [SiWa]
539
        #   
540
        if isinstance(other, LieTree):
541
            
542
            if not self & other:       # check weakpairing
543
                return 0    
544
            
545
            return self.__pair(other)  # recursively compute pairing
546
  
547

548
        #########################
549
        #
550
        # Counting configuration braidings in words using algorithm from [GOSW]
551
        #
552
        if isinstance(other, SignedWord):
553
            counter = CountTree(self)    # analog of sum and delta arrays for EilWord
554
            
555
            for letter in other.word:
556
                counter.evaluate(letter) # evaluate the counter on each letter in the word
557
                
558
            return counter.total         # this is s + Δ at root
559
            
560
        
561
        return NotImplemented
562
    
563
    
564
    
565
    def __pair(self, other):
566
        """pair is used internally to recursively compute pairings of eil symbols with Lie brackets
567
           Pairing is computed by recursively using bracket-cobracket duality. 
568
           Cobracket of symbols is given by cutting out a subtree, yielding sub and excised trees.
569
           To speed things up, we compare size and letter grading (weakPair) before recursing.  This immediately eliminates most 0 pairings.
570
        """        
571
        
572
        if self.weight == 0:            # Base case! Symbol is a single character 
573
            return int(self.value == other.value)   # compare vs Lie value
574
        
575
        pairing = 0          # Otherwise we use cobracket-bracket compatibility with pairing [SiWa]
576
        
577
        #       < eil , lie > =  < L(eil) , L(lie) > * < R(eil) , R(lie) >
578
        #                      - < R(eil) , L(lie) > * < L(eil) , R(lie) >
579
        #
580
        # where  ]eil[ = sum L(eil) x R(eil)   and    lie = [ L(lie) , R(lie) ]
581
        #    L(eil) is subsymbol
582
        #    R(eil) is result of excising subsymbol
583
        
584
        for subsymbol in self:           # iterate through all subsymbols of symbol
585
            if subsymbol & other.left:   #   weakpair with subsymbol first, since excised symbol requires computation
586
                pairing += subsymbol.__pair(other.left) * self.__excise(subsymbol).__pair(other.right)
587
            
588
            if subsymbol & other.right:  #   weakpair with subsymbol first, since excised symbol requires computation
589
                pairing -= subsymbol.__pair(other.right) * self.__excise(subsymbol).__pair(other.left)
590
            
591
        return pairing
592
    
593
        # Note: this might be sped up by sorting subsymbols by weight initially rather than searching for weights matching other.left and other.right
594
                
595
               
596
        
597
       
598
    def __excise(self, subsymbol):  
599
        """excise is used internally to compute the symbol remaining after a subsymbol is removed
600
           It recursively copies a tree, skipping the excised subsymbol (and its supported subtree).
601
        """
602
        
603
        #if self is subsymbol:  # This should never happen during internal recursive usage!
604
        #    return EilTree()   
605
        
606
        eil = EilTree()        # Begin with a blank node
607
        
608
        eil.decoration = self.decoration # copy the decoration
609
        
610
        if self.weight == 0:   # Direct copy if this is a leaf node
611
            eil.weight = 0
612
            eil.value  = self.value
613
            
614
        else:    
615
            eil.subsymbols = [symbol.__excise(subsymbol) for symbol in self.subsymbols if not symbol is subsymbol]          
616
            
617
        return eil
618
    
619
    @property
620
    def subsymbols(self):
621
        return self._branches
622
    
623
    @subsymbols.setter
624
    def subsymbols(self, list):
625
        self._branches = list
626
        self.value = ''.join([f'({str(branch)})' for branch in self._branches]+[self.decoration])
627
        self.weight = sum([branch.weight + 1 for branch in self._branches])
628
       
629
        # self.weight = self.value.count('(')  # this should be equivalent, but probably slower?
630
 
631

632
    # I like to write free elements last, so append() and extend()  will actually insert at start...
633
    def append(self, subsymbol):
634
        """Insert new subsymbol, updating weight and value"""
635
        self._branches[:0] = [subsymbol]                  # insert subsymbol at start
636
        self.weight += subsymbol.weight+1                 # add to weight
637
        self.value   = f'({subsymbol.value}){self.value}' # add to value 
638
        
639
    def extend(self, subsymbols):
640
        """Insert array of subsymbols, updating weight and value"""
641
        self._branches[:0] = subsymbols
642
        self.weight += sum([symbol.weight+1 for symbol in subsymbols])
643
        tmp          = ')('.join([symbol.value for symbol in subsymbols])
644
        self.value   = f'({tmp}){self.value}'
645

646
    def copy(self):
647
        """Create a deep copy of EilTree"""
648
        eil = EilTree()
649
        eil.decoration = self.decoration
650
        eil.value , eil.weight = self.value , self.weight
651
                
652
        if len(self._branches) > 0:
653
            eil._branches = [subsymbol.copy() for subsymbol in self._branches]
654
        
655
        return eil
656
 
657

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

670
    
671
    def normalize(self):
672
        """Convert EilTree to 'normalized' form -- sort branches and move free letter to the far right"""
673
        for symbol in self._branches:    
674
            symbol.normalize()
675
            
676
        #self.value = ''.join([f'({str(branch)})' for branch in sorted(self.branches,reverse=True)]+[self.decoration])
677
        self.subsymbols = [branch for branch in sorted(self._branches,reverse=True)]
678
     
679
    
680
    def __eq__(self,other):               # compare normalized forms so (a)b == b(a)
681
        if isinstance(other, EilTree):    #   Note: isn't perfect...
682
            return self.normalValue == other.normalValue
683
        
684
        return False
685
  
686

687
    # < is used when writing in normal form and comparing EilTrees
688
    def __lt__(self,other):
689
        if self.value == other.value:     # if values match then these are equal
690
            return False
691
        
692
                                          # next sort by weight and decoration
693
        if (self.weight,self.decoration) < (other.weight,other.decoration):
694
            return True
695
        if (self.weight,self.decoration) > (other.weight,other.decoration):
696
            return False
697
        
698
                                          # next sort by number of branches
699
        if len(self.subsymbols) < len(other.subsymbols):
700
            return True
701
        if len(self.subsymbols) > len(other.subsymbols):
702
            return False
703
        
704
                                           # next look at decorations and weights of branches
705
        return sorted([(branch.decoration,branch.weight) for branch in self.subsymbols]) < sorted([(branch.decoration,branch.weight) for branch in other.subsymbols])
706
    
707
        # note: this may incorrectly sort a(a(b)) and a(a(c))
708
    
709
    
710
        
711
    def __gt__(self,other):
712
        return other < self
713
        
714
        
715
    def __repr__(self):
716
        return f"EilTree('{self.value}')"        
717
    
718
    
719
    
720
    ################
721
    #
722
    # allow eil(lie) instead of just eil * lie
723
    #
724
    def __call__(self, other):
725
        return self * other
726

727
    
728
    def cobracket(self): 
729
        """returns a generator with tuples of cobracket elements"""
730
        subsymbols = iter(self)
731
        next(subsymbols)    # the first term in the iterator is the entire symbol (skip it)
732
        
733
        return ((subsymbol,self.__excise(subsymbol)) for subsymbol in subsymbols)
734
    
735
##################################################################
736
##################################################################
737

738

739
class CountTree():
740
    """CountTree is a helper class for combinatorial braiding of coLie symbols on words.
741
    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. 
742
    
743
    Objects of this class should only be used internally!
744
    
745
    Parameters
746
    ----------
747
    eil : EilTree
748
       corresponding node of an EilTree
749
       
750
    Attributes
751
    ----------
752
    sum      : integer
753
       current s value for this node (initialized to 0)
754
    delta    : integer
755
       current Δ value for this node (initialized to 0)
756
    branches : list of CountTree's
757
       list of branches from this node
758
    eil      : EilTree
759
       corresponding node of the EilTree
760
    total    : integer
761
       sum + delta
762
    """
763
    
764
    
765
    def __init__(self,eil):
766
        self.sum   = 0
767
        self.delta = 0
768
        self.eil   = eil
769
        
770
        self.branches = [CountTree(branch) for branch in eil.subsymbols]
771
        
772
        
773
    @property 
774
    def total(self):
775
        return self.sum + self.delta
776
    
777
    
778
    def evaluate(self,letter):
779
        """evaluate updates values of the counter tree at the given letter following the algorithm outlined in [GOSW]
780
           Compare to the use of 'sum' and 'delta' arrays in the __mul__() method of EilWord.
781
        """
782
        
783
        
784
        for branch in self.branches:    # Evaluate leaf to root
785
            branch.evaluate(letter)     #   (update branch values first)   
786
            
787
        self.sum  += self.delta         # 1. add Δ to s
788
        self.delta = 0                  #    and set Δ = 0
789
        
790
        value = 0                       # 2. incorporate values from branches
791
 
792
        if letter.value == self.eil.decoration: # check if update is needed
793
            if len(self.branches) == 0: #    at leaf just copy the value
794
                value = 1
795
            else:                       #    otherwise add values from branches
796
                value = sum([branch.sum for branch in self.branches])
797
            
798
            
799
        if not letter:                  # 3. at inverses, immediately update s
800
            self.sum   -= value
801
        else:                           #    otherwise, update Δ
802
            self.delta  = value
803
        
804
 
805

806
    ###################
807
    #
808
    # Interesting things that aren't currently used
809
    #
810
    def __iter__(self):
811
        for branch in self.branches:
812
            for twig in branch:
813
                yield twig          
814
        yield self
815

816

817

818
##################################################################
819
##################################################################
820

821

822
class SignedLetter():
823
    """SignedLetter is a letter with a sign, intended to represent a generator or an inverse
824
     * as a boolean it is True for generator and False for inverse
825
     * as an integer it is 1 for generator and -1 for inverse
826
     * as a string it looks pretty
827
    
828
    Parameters
829
    ----------
830
    letter : string
831
        this should be a single character
832
    sign   : boolean or integer
833
    
834
    Examples: 
835
      SignedLetter("a",False)
836
      SignedLetter("a",-1)
837
    
838
    Attributes
839
    ----------
840
    value : string
841
        this is the letter
842
    sign  : boolean
843
        True corresponds to generator
844
        False correspnds to inverse
845
    
846
    """
847
    def __init__(self,letter,sign):
848
        self.value = letter
849
        self.sign  = True if sign == 1 else False
850
    
851
    def __bool__(self):
852
        return self.sign
853
    
854
    def __int__(self):
855
        return 1 if self.sign else -1
856
    
857
    def __str__(self):
858
        return f'{self.value}' if self.sign else f'{self.value}\N{SUPERSCRIPT MINUS}\N{SUPERSCRIPT ONE}'
859

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

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

866
    def __hash__(self):
867
        return hash(self.short())
868

869
##################################################################
870

871

872
class SignedWord():
873
    """SignedWord is a list of SignedLetters
874
    
875
    Parameters
876
    ----------
877
    word : string or list
878
    
879
    Examples: 
880
     SignedWord("aba^{-1}b^{-1}")
881
     SignedWord("aba-b-")
882
     SignedWord( [ ("a",1), ("b",1), ("a",-1), ("b",-1) ] )
883
    
884
    Attributes
885
    ----------
886
    word : list of SignedLetters
887
    """
888
    def __init__(self,word):
889
        self.word = []
890
        
891
        if isinstance(word, str):
892
            i = 0
893
            while i < len(word):
894
                if i+1 < len(word) and (word[i+1] == "-" or word[i+1] == "^"):
895
                    self.word.append(SignedLetter(word[i],-1))
896
                else:
897
                    self.word.append(SignedLetter(word[i], 1))
898
                i += 1
899
                
900
                while i < len(word) and not word[i].isalpha():
901
                    i += 1
902
        elif isinstance(word, list):
903
            if isinstance(word[0], SignedLetter):
904
                self.word = word
905
            else:    
906
                self.word = [SignedLetter(x[0],x[1]) for x in word]
907
        else:
908
            raise ValueError("Word format not recognized!")
909
            
910

911
    def __len__(self):
912
        return len(self.word)
913
            
914
    def __str__(self):
915
        return ''.join([str(x) for x in self.word])
916

917
    def __repr__(self):
918
        return 'SignedWord("' + ''.join([x.short() for x in self.word]) + '")'
919
    
920
    def __hash__(self):
921
        return hash(''.join([x.short() for x in self.word]))
922
        
923
    def __iter__(self):
924
        return iter(self.word)      
925

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