#!/usr/bin/env python2.6
# -*- coding: utf-8 -*-

'''
pypol - a Python library to manipulate polynomials and algebraic fractions.

Author: Michele Lacchia <michelelacchia@gmail.com>
Copyright: 2010-2011 Michele Lacchia
License: GNU GPL

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your
 option) any later version.

This p
rogram is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.

Requirements:
- Python 2.6 (or 2.7)

This module implements some polynomial series, such as the Lucas Sequence or the Bernoulli polynomials.

Copyright (C) 2010-2011 Michele Lacchia
'''

import fractions

from pypol import poly1d, polynomial, monomial, NULL, ONE, TWO, x
from pypol.funcs import polyder, bin_coeff, stirling2, harmonic, harmonic_g


class LucasSeq(object):
    '''
    *"The Lucas polynomial sequence is a pair of generalized polynomials which generalize the Lucas sequence to polynomials ..."* [MathWorld]_

    :param p: The *p* parameter
    :param q: The *q* parameter
    :param zero: The first element of the sequence (at index 0)
    :type zero: :class:`pypol.Polynomial`
    :param one: The second element of the sequence (at index 1)
    :type one: :class:`pypol.Polynomial`

    Setting different values for *p* and *q* we obtain some polynomial sequences, for every *p* and *q* pair there are two polynomials sequences, :math:`W(x)` and :math:`w(x)`:

    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | **p**  | **q**  |    **W(x)**                                                                          |   **w(x)**                                                                    |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | x      | 1      |  Fibonacci polynomials (:func:`fibonacci`)                                           | Lucas polynomials (:func:`lucas`)                                             |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | 2x     | 1      |  Pell polynomials (:func:`pell`)                                                     | Pell-Lucas polynomials (:func:`pell_lucas`)                                   |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | 1      | 2x     |  Jacobsthal polynomials (:func:`jacobsthal`)                                         | Jacobsthal-Lucas polynomials (:func:`jacob_lucas`)                            |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | 3x     | -2     |  Fermat polynomials (:func:`fermat`)                                                 | Fermat-Lucas polynomials (:func:`fermat_lucas`)                               |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+
    | 2x     | -1     |  Chebyshev polynomials of the second kind :math:`U_{n - 1}(x)` (:func:`chebyshev_u`) | Chebyshev polynomials of the first kind :math:`2T_n(x)` (:func:`chebyshev_t`) |
    +--------+--------+--------------------------------------------------------------------------------------+-------------------------------------------------------------------------------+

    The starting value for the :math:`W(x)` polynomials is always 2, for the :math:`w(x)` polynomials is always a null polynomial.


    .. [MathWorld] `Weisstein, Eric W. <http://mathworld.wolfram.com/about/author.html>`_ `"Lucas Polynomial Sequence. " <http://mathworld.wolfram.com/LucasPolynomialSequence.html>`_ From `MathWorld <http://mathworld.wolfram.com/>`_ -- A Wolfram Web Resource.

    .. versionadded:: 0.4
    '''

    def __init__(self, p, q, type='W'):
        self.p, self.q = p, q
        if type == 'W':
            self.zero, self.one = NULL, ONE
        elif type == 'w':
            self.zero, self.one = TWO, self.p
        else:
            raise ValueError('type should be either W or w')

        self._cache = [self.zero, self.one]

    def __call__(self, n):
        '''
        Returns the *n-th* element of the sequence

        :param integer n: the *n-th* element of the sequence
        :raises: :exc:`ValueError` if *n* is negative
        :rtype: :class:`pypol.Polynomial`

        ::

            >>> from pypol import *
            >>> from pypol.series import *
            >>> 
            >>> fibo = LucasSeq(x, ONE)
            >>> fibo(0)
            
            >>> fibo(1)
            + 1
            >>> fibo(12)
            + x^11 + 10x^9 + 36x^7 + 56x^5 + 35x^3 + 6x
            >>> fibo(19)
            + x^18 + 17x^16 + 120x^14 + 455x^12 + 1001x^10 + 1287x^8 + 924x^6 + 330x^4 + 45x^2 + 1
            >>> f = fibo(45)
            >>> f = fibo(65) ## Almost instantaneous
        '''

        if n < 0:
            raise ValueError('Lucas sequence only defined for n >= 0')
        try:
            return self._cache[n]
        except IndexError:
            for _ in xrange(len(self.cache) - 2, n - 1):
                self._cache.append(self.p * self._cache[-1] + self.q * self._cache[-2])
            return self._cache[-1]

    @ property
    def cache(self):
        '''
        The cache used to speed up the calculation
        '''

        return self._cache 

    def reset_cache(self):
        '''
        Resets the cache, i.e. sets it to list containing only the first 2 values of the series (`self.zero` and `self.one`)
        '''

        self._cache = [self.zero, self.one]

_fib = LucasSeq(x, ONE)
_lucas = LucasSeq(x, ONE, 'w')
_pell = LucasSeq(2*x, ONE)
_pell_lucas = LucasSeq(2*x, ONE, 'w')
_jacobsthal = LucasSeq(ONE, 2*x)
_jacob_lucas = LucasSeq(ONE, 2*x, 'w')
_fermat = LucasSeq(3*x, -TWO)
_fermat_lucas = LucasSeq(3*x, -TWO, 'w')
_chebyshev_t = LucasSeq(2*x, -ONE, 'w')
_chebyshev_u = LucasSeq(2*x, -ONE)

def fibonacci(n):
    '''
    Returns the *n-th* Fibonacci polynomial.

    :raises: :exc:`ValueError` if *n* is negative
    :rtype: :class:`pypol.Polynomial`

    **Examples**

    ::

        >>> fibonacci(0)
        
        >>> fibonacci(1)
        + 1
        >>> fibonacci(2)
        + x
        >>> fibonacci(3)
        + x^2 + 1
        >>> fibonacci(4)
        + x^3 + 2x
        >>> fibonacci(5)
        + x^4 + 3x^2 + 1
        >>> fibonacci(6)
        + x^5 + 4x^3 + 3x
        >>> fibonacci(23)
        + x^22 + 21x^20 + 190x^18 + 969x^16 + 3060x^14 + 6188x^12 + 8008x^10 + 6435x^8 + 3003x^6 + 715x^4 + 66x^2 + 1
        >>> fibonacci(100)
        + x^99 + 98x^97 + 4656x^95 + 142880x^93 ... + 197548686920970x^17 + 22057981462440x^15 + 1889912732400x^13 + 119653565850x^11 + 5317936260x^9 + 154143080x^7 + 2598960x^5 + 20825x^3 + 50x
        >>> fibonacci(200)
        + x^199 + 198x^197 + ... + 15913388077274800x^13 + 249145778809200x^11 + 2747472247520x^9 + 19813501785x^7 + 83291670x^5 + 166650x^3 + 100x
        >>> len(fibonacci(300))
        150
        >>> len(str(fibonacci(300)))
        8309

    The Fibonacci polynomials are the *W*-polynomials in the Lucas sequence (:class:`LucasSeq`) obtained setting ``p = x`` and ``q = 1``::

       