## "Fossies" - the Fresh Open Source Software Archive

### Member "NZMATH-1.2.0/nzmath/poly/formalsum.py" (19 Nov 2012, 12875 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "formalsum.py" see the Fossies "Dox" file reference documentation.

```    1 """
2 formalsum --- formal sum, or linear combination.
3
4 The formalsum is mathematically a finite sum of terms.
5 The term consists of two parts: coefficient and base.
6 The coefficients must be in a ring.  The base is arbitrary.
7
8 Two formalsums can be added in the following way.
9 If there are terms with common base, they are fused into a
10 new term with the same base and coefficients added.
11
12 A coefficient can be looked up from the base.
13 If the specified base does not appear in the formalsum,
14 it is null.
15
16 abstract data type FS:
17   FS: list(tuple(B, C)) -> FS
18
19   +: FS x FS -> FS
20      FS -> FS
21   -: FS x FS -> FS
22      FS -> FS
23   *: C x FS -> FS
24      FS x C -> FS
25
26   []: FS x B -> C
27   bases: FS -> list(B)
28   coefficeints: FS -> list(C)
29   terms: FS -> list(tuple(B, C))
30   ==: FS x FS -> bool
31   !=: FS x FS -> bool
32   len: FS -> int
33   repr: FS -> str
34 """
35
36 import nzmath.compatibility
37
38
39 class FormalSumContainerInterface (object):
40     """
41     Interface of formal sum container.
42     Do not instantiate.
43     """
44     def __iter__(self):
45         """
46         Return the iterator.
47         It is an alias of iterterms.
48         """
49         return self.iterterms()
50
51     def __getitem__(self, base):
52         """
53         Return the coefficient of specified base.
54         If there is no term of the base, return 0.
55         """
56         raise NotImplementedError("method '__getitem__' must be overridden")
57
58     def __contains__(self, base):
59         """
60         base in self
61
62         membership test.
63         """
64         return base in self.bases()
65
66     def __len__(self):
67         """
68         Return the number of data entries.
69         """
70         raise NotImplementedError("method '__len__' must be overridden")
71
72     def __eq__(self, other):
73         """
74         self == other
75
76         This implementaion is not optimal for more structured
77         descendants.
78         """
79         if self is other:
80             return True
81         if not isinstance(other, FormalSumContainerInterface):
82             return False
83         self_bases = set(self.iterbases())
84         other_bases = set(other.iterbases())
85         if self_bases != other_bases:
86             return False
87         for base in self_bases:
88             if self[base] != other[base]:
89                 return False
90         return True
91
92     def __hash__(self):
93         val = sum([hash(self[base]) for base in set(self.iterbases())])
94         return val
95
96     def __ne__(self, other):
97         """
98         self != other
99         """
100         return not self.__eq__(other)
101
102     def __nonzero__(self):
103         """
104         Return True, if self has some nonzero coefficients.
105         False, otherwise.
106         """
107         for c in self.itercoefficients():
108             if c:
109                 return True
110         return False
111
112     def __hash__(self):
113         """
114         hash(self)
115         """
116         try:
117             return sum([hash(b)*hash(c) for (b, c) in self]) & 0x7fff
118         except TypeError:
119             raise TypeError("unhashable")
120
122         """
123         self + other
124         """
125         sum_coeff = dict(self.iterterms())
126         for base, coeff in other:
127             if base in sum_coeff:
128                 sum_coeff[base] += coeff
129             else:
130                 sum_coeff[base] = coeff
131         return self.construct_with_default([(b, c) for (b, c) in sum_coeff.iteritems() if c])
132
133     def __sub__(self, other):
134         """
135         self - other
136         """
137         sub_coeff = dict(self.iterterms())
138         for base, coeff in other:
139             if base in sub_coeff:
140                 sub_coeff[base] -= coeff
141             else:
142                 sub_coeff[base] = -coeff
143         return self.construct_with_default([(b, c) for (b, c) in sub_coeff.iteritems() if c])
144
145     def __neg__(self):
146         """
147         -self
148         """
149         raise NotImplementedError("method '__neg__' should be overridden")
150
151     def __pos__(self):
152         """
153         +self
154         """
155         raise NotImplementedError("method '__pos__' should be overridden")
156
157     def __mul__(self, other):
158         """
159         self * other
160
161         Only scalar multiplication is defined.
162         """
163         raise NotImplementedError("method '__mul__' should be overridden")
164
165     def __rmul__(self, other):
166         """
167         other * self
168
169         This method is invoked only when type of other does not
170         support multiplication with FormalSumContainerInterface
171         """
172         raise NotImplementedError("method '__rmul__' should be overridden")
173
174     def iterterms(self):
175         """
176         iterator for (degree, coefficient) pairs.
177         """
178         raise NotImplementedError("method 'iterterms' must be overridden")
179
180     def itercoefficients(self):
181         """
182         iterator for coefficients.
183         """
184         raise NotImplementedError("method 'itercoefficients' must be overridden")
185
186     def iterbases(self):
187         """
188         iterator for degrees.
189         """
190         raise NotImplementedError("method 'iterbases' must be overridden")
191
192     def terms(self):
193         """
194         Return a list of terms as (base, coefficient) pairs.
195         """
196         return list(self.iterterms())
197
198     def coefficients(self):
199         """
200         Return a list of all coefficients.
201         """
202         return list(self.itercoefficients())
203
204     def bases(self):
205         """
206         Return a list of all bases.
207         """
208         return list(self.iterbases())
209
210     def terms_map(self, func):
211         """
212         Create a new formal sum container by applying func to each
213         term.  func must be a function taking 2 arguments.
214         """
215         terms = []
216         for t in self:
217             b, c = func(*t)
218             if c:
219                 terms.append((b, c))
220         return self.construct_with_default(terms)
221
222     def coefficients_map(self, func):
223         """
224         Create a new formal sum container by applying func to each
225         coefficient.
226         """
227         return self.terms_map(lambda x, y: (x, func(y)))
228
229     def bases_map(self, func):
230         """
231         Create a new formal sum container by applying func to each
232         base.
233         """
234         return self.terms_map(lambda x, y: (func(x), y))
235
236     def construct_with_default(self, maindata):
237         """
238         Create a new formal sum container of the same class with self,
239         with given only the maindata and use copy of self's data if
240         necessary.
241         """
242         # Do not extend the signature of this method.
243         raise NotImplementedError("method 'construct_with_default' must be overridden")
244
245
246 class DictFormalSum (FormalSumContainerInterface):
247     """
248     formalsum implementation based on dict.
249     """
250     def __init__(self, args, defaultvalue=None):
251         """
252         DictFormalSum(args)
253
254         args can be any dict initial values.
255         It makes a mapping from bases to coefficients.
256
257         The optional argument defaultvalue is the default value for
258         __getitem__, i.e., if there is no term with the specified
259         base, a look up attempt returns the defaultvalue.
260         """
261         self._data = dict(args)
262         self._defaultvalue = defaultvalue
263
264     def __mul__(self, other):
265         """
266         self * other
267
268         Only scalar multiplication is defined.
269         """
270         return self.scalar_mul(other)
271
272     def scalar_mul(self, scale):
273         """
274         scalar multiplication.
275
276         self * scale
277         """
278         return self.coefficients_map(lambda c: c * scale)
279
280     def __rmul__(self, other):
281         """
282         other * self
283
284         This method is invoked only when type of other does not
285         support multiplication with FormalSumContainerInterface.
286         """
287         return self.rscalar_mul(other)
288
289     def rscalar_mul(self, scale):
290         """
291         r-scalar multiplication (r- means as of r-methods of python
292         special methods, where self is the right operand.)
293
294         scale * self
295         """
296         return self.coefficients_map(lambda c: scale * c)
297
298     def __neg__(self):
299         """
300         -self
301         """
302         return self.construct_with_default([(b, -c) for (b, c) in self])
303
304     def __pos__(self):
305         """
306         +self
307         """
308         return self.construct_with_default(self._data)
309
310     def __eq__(self, other):
311         """
312         self == other
313         """
314         if self is other:
315             return True
316         if not isinstance(other, DictFormalSum):
317             return FormalSumContainerInterface.__eq__(self, other)
318         if self._data == other._data:
319             return True
320         return False
321
322     def __hash__(self):
323         val = sum([hash(ele) for ele in self._data])
324         return val
325
326     def __getitem__(self, base):
327         """
328         self[base]
329
330         no KeyError will be raised. Insteads, it returns defaultvalue
331         specified on time of initialization.
332         """
333         return self._data.get(base, self._defaultvalue)
334
335     def iterterms(self):
336         """
337         iterator for (base, coefficient) pairs.
338         """
339         return self._data.iteritems()
340
341     def itercoefficients(self):
342         """
343         iterator for coefficients.
344         """
345         return self._data.itervalues()
346
347     def iterbases(self):
348         """
349         iterator for bases.
350         """
351         return self._data.iterkeys()
352
353     def __len__(self):
354         """
355         len(self)
356
357         Return the number of terms.
358         """
359         return len(self._data)
360
361     def __repr__(self): # for debug
362         return "%s(%s)" % (self.__class__.__name__, repr(self._data))
363
364     def construct_with_default(self, maindata):
365         """
366         Create a new formal sum container of the same class with self,
367         with given only the maindata and use copy of self's data if
368         necessary.
369         """
370         return self.__class__(maindata, defaultvalue=self._defaultvalue)
371
372
373 class ListFormalSum (FormalSumContainerInterface):
374     """
375     formalsum implementation based on List.
376     """
377     def __init__(self, args, defaultvalue=None):
378         """
379         ListFormalSum(args)
380
381         args can be sequence of tuples of (base, coefficient) pair.
382         It makes a mapping from bases to coefficients.
383         """
384         self._data = list(args)
385         self._defaultvalue = defaultvalue
386
387     def __mul__(self, other):
388         """
389         self * other
390
391         Only scalar multiplication is defined.
392         """
393         return self.scalar_mul(other)
394
395     def scalar_mul(self, scale):
396         """
397         scalar multiplication.
398
399         sum * scale
400         """
401         return self.coefficients_map(lambda c: c * scale)
402
403     def __rmul__(self, other):
404         """
405         other * self
406
407         This method is invoked only when type of other does not
408         support multiplication with FormalSum.
409         """
410         return self.rscalar_mul(other)
411
412     def rscalar_mul(self, scale):
413         """
414         scalar multiplication.
415
416         scale * sum
417         """
418         return self.coefficients_map(lambda c: scale * c)
419
420     def __neg__(self):
421         """
422         -self
423         """
424         return self.construct_with_default([(b, -c) for (b, c) in self])
425
426     def __pos__(self):
427         """
428         +self
429         """
430         return self.construct_with_default(self._data)
431
432     def __eq__(self, other):
433         """
434         self == other
435         """
436         if self is other:
437             return True
438         if not isinstance(other, ListFormalSum):
439             return FormalSumContainerInterface.__eq__(self, other)
440         if set(self._data) == set(other._data):
441             return True
442         return False
443
444     def __hash__(self):
445         val = sum([hash(ele) for ele in set(self._data)])
446         return val
447
448     def __getitem__(self, base):
449         """
450         self[base]
451
452         no KeyError will be raised. Insteads, it returns defaultvalue
453         specified on time of initialization.
454         """
455         for b, c in self:
456             if b == base:
457                 return c
458         return self._defaultvalue
459
460     def iterterms(self):
461         """
462         iterator for (base, coefficient) pairs.
463         """
464         return iter(self._data)
465
466     def itercoefficients(self):
467         """
468         iterator for coefficients.
469         """
470         for b, c in self._data:
471             yield c
472
473     def iterbases(self):
474         """
475         iterator for bases.
476         """
477         for b, c in self._data:
478             yield b
479
480     def __len__(self):
481         """
482         len(self)
483
484         Return the number of terms.
485         """
486         return len(self._data)
487
488     def __repr__(self): # for debug
489         return "%s(%s)" % (self.__class__.__name__, repr(self._data))
490
491     def construct_with_default(self, maindata):
492         """
493         Create a new formal sum container of the same class with self,
494         with given only the maindata and use copy of self's data if
495         necessary.
496         """
497         return self.__class__(maindata, defaultvalue=self._defaultvalue)
```