source:sage/monoids/free_monoid_element.py@6023:19b84a5e93c9

Revision 6023:19b84a5e93c9, 7.5 KB checked in by boothby@…, 6 years ago (diff)

Updated doctest to reflect different exception.

Line
1"""
2Monoid Elements
3
4AUTHOR: David Kohel <kohel@maths.usyd.edu.au>, 2005/09/29
5
6Elements of free monoids are represented internally as lists of pairs
7of integers.
8"""
9
10#*****************************************************************************
11#  Copyright (C) 2005 David Kohel <kohel@maths.usyd.edu>
12#
14#
15#    This code is distributed in the hope that it will be useful,
16#    but WITHOUT ANY WARRANTY; without even the implied warranty
17#    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18#
19#  See the GNU General Public License for more details; the full text
20#  is available at:
21#
23#*****************************************************************************
24
25import operator
26from sage.rings.integer import Integer
27from sage.structure.element import MonoidElement
28
29def is_FreeMonoidElement(x):
30    return isinstance(x, FreeMonoidElement)
31
32class FreeMonoidElement(MonoidElement):
33    """
34    Element of a free monoid.
35
36    EXAMPLES:
37            sage: a = FreeMonoid(5, 'a').gens()
38            sage: x = a[0]*a[1]*a[4]**3
39            sage: x**3
40            a0*a1*a4^3*a0*a1*a4^3*a0*a1*a4^3
41            sage: x**0
42            1
43            sage: x**(-1)
44            Traceback (most recent call last):
45            ...
46            TypeError: bad operand type for unary ~: 'FreeMonoidElement'
47    """
48    def __init__(self, F, x, check=True):
49        """
50        Create the element \$x\$ of the FreeMonoid \$F\$.
51
52        This should typically be called by a FreeMonoid.
53        """
54        MonoidElement.__init__(self, F)
55        if isinstance(x, (int, long, Integer)):
56            if x == 1:
57                self._element_list = []
58            else:
59                raise TypeError, "Argument x (= %s) is of the wrong type."%x
60        elif isinstance(x, list):
61            if check:
62                x2 = []
63                for v in x:
64                    if not isinstance(v, tuple) and len(v) == 2:
65                        raise TypeError, "x (= %s) must be a list of 2-tuples or 1."%x
66                    if not (isinstance(v[0], (int,long,Integer)) and \
67                            isinstance(v[1], (int,long,Integer))):
68                        raise TypeError, "x (= %s) must be a list of 2-tuples of integers or 1."%x
69                    if len(x2) > 0 and v[0] == x2[len(x2)-1][0]:
70                        x2[len(x2)-1] = (v[0], v[1]+x2[len(x2)-1][1])
71                    else:
72                        x2.append(v)
73                self._element_list = x2
74            else:
75                self._element_list = list(x)  # make copy, so user can't accidently change monoid.
76
77        else:
78            # TODO: should have some other checks here...
79            raise TypeError, "Argument x (= %s) is of the wrong type."%x
80
81##     def __cmp__(left, right):
82##         """
83##         Compare two free monoid elements with the same parents.
84
85##         The ordering is the one on the underlying sorted list of
86##         (monomial,coefficients) pairs.
87
88##         EXAMPLES:
89##             sage: R.<x,y> = FreeMonoid(2)
90##             sage: x < y
91##             True
92##             sage: x * y < y * x
93##             True
94##             sage: x * y * x^2 < x * y * x^3
95##             True
96##         """
97##         return cmp(left._element_list, right._element_list)
98
99    def _repr_(self):
100        s = ""
101        v = self._element_list
102        x = self.parent().variable_names()
103        for i in range(len(v)):
104            if len(s) > 0: s += "*"
105            g = x[int(v[i][0])]
106            e = v[i][1]
107            if e == 1:
108                s += "%s"%g
109            else:
110                s += "%s^%s"%(g,e)
111        if len(s) == 0: s = "1"
112        return s
113
114    def _latex_(self):
115        """
116        Return latex representation of self.
117
118        EXAMPLES:
119            sage: F = FreeMonoid(3, 'a')
120            sage: z = F([(0,5),(1,2),(0,10),(0,2),(1,2)])
121            sage: z._latex_()
122            'a0^{5}a1^{2}a0^{12}a1^{2}'
123        """
124        s = ""
125        v = self._element_list
126        x = self.parent().variable_names()
127        for i in range(len(v)):
128            g = x[int(v[i][0])]
129            e = v[i][1]
130            if e == 1:
131                s += "%s"%g
132            else:
133                s += "%s^{%s}"%(g,e)
134        if len(s) == 0: s = "1"
135        return s
136
137    def __mul__(self, y):
138        """
139        Multiply 2 free monoid elements.
140
141        EXAMPLES:
142            sage: a = FreeMonoid(5, 'a').gens()
143            sage: x = a[0] * a[1] * a[4]**3
144            sage: y = a[4] * a[0] * a[1]
145            sage: x*y
146            a0*a1*a4^4*a0*a1
147        """
148        if not isinstance(y, FreeMonoidElement):
149            raise TypeError, "Argument y (= %s) is of wrong type."%y
150        M = self.parent()
151        z = M(1)
152        x_elt = self._element_list
153        y_elt = y._element_list
154        if len(x_elt) == 0:
155            z._element_list = y_elt
156        elif len(y_elt) == 0:
157            z._element_list = x_elt
158        else:
159            k = len(x_elt)-1
160            if x_elt[k][0] != y_elt[0][0]:
161                z._element_list = x_elt + y_elt
162            else:
163                m = (y_elt[0][0],x_elt[k][1]+y_elt[0][1])
164                z._element_list = x_elt[0:k] + [ m ] + y_elt[1:]
165        return z
166
167    def __len__(self):
168        """
169        Return the number of products that occur in this monoid element.
170        For example, the length of the identity is 0, and the length
171        of the monoid \$x_0^2x_1\$ is three.
172
173        EXAMPLES:
174            sage: F = FreeMonoid(3, 'a')
175            sage: z = F(1)
176            sage: len(z)
177            0
178            sage: a = F.gens()
179            sage: len(a[0]**2 * a[1])
180            3
181        """
182        s = 0
183        for x in self._element_list:
184            s += x[1]
185        return s
186
187    def __cmp__(self,y):
188##         """
189##         The comparison operator, defined via x = self:
190##             x < y <=> x.__cmp__(y) == -1
191##             x == y <=> x.__cmp__(y) == 0
192##             x > y <=> x.__cmp__(y) == 1
193##         It is not possible to use __cmp__ to define a
194##         non-totally ordered poset.
195##         Question: How can the operators <, >, ==, !=,
196##         <=, and >= be defined for a general poset?
197##         N.B. An equal operator __equal__ may or may not
198##         have been introduced to define == and != but can
199##         not be used in conjuction with __cmp__.
200##        """
201        if not isinstance(y,FreeMonoidElement) or y.parent() != self.parent():
202            #raise TypeError, "Argument y (= %s) is of the wrong type."%y
203            return 1
204        n = len(self)
205        m = len(y)
206        if n < m:
207            return -1
208        elif m < n:
209            return 1
210        elif n == 0:
211            return 0 # n = m = 0 hence x = y = 1
212        x_elt = self._element_list
213        y_elt = y._element_list
214        for i in range(len(x_elt)):
215            k = x_elt[i][0]
216            l = y_elt[i][0]
217            if k < l:
218                return -1
219            elif k > l:
220                return 1
221            e = x_elt[i][1]
222            f = y_elt[i][1]
223            if e < f:
224                # x_elt is longer so compare next index
225                if x_elt[i+1][0] < l:
226                    return -1
227                else:
228                    return 1
229            elif f < e:
230                # y_elt is longer so compare next index
231                if k < y_elt[i+1][0]:
232                    return -1
233                else:
234                    return 1
235        return 0 # x = self and y are equal
Note: See TracBrowser for help on using the repository browser.