"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 
  121     def __add__(self, other):
  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)