CUPolynomial.h

//
//  CUPolynomial.h
//  Cornell Extensions to Cocos2D
//
//  This module provides a class that represents a polynomial. It has basic methods
//  for evaluation and root finding.  The primary purpose of this class is to support
//  CubicBezier and other splines. However, we provide it publicly in case it is
//  useful for other applications.
//
//  Math data types are much lighter-weight than other objects, and are intended to
//  be copied.  That is why we do not use reference counting for these objects.
//
//  Author: Walker White
//  Version: 11/24/15
//
#ifndef __CU_POLYNOMIAL_H__
#define __CU_POLYNOMIAL_H__

#include <cocos2d.h>
#include <iostream>
#include <vector>

using namespace std;

NS_CC_BEGIN


#pragma mark -
#pragma mark Polynomial

class Polynomial : public vector<float> {
public:
#pragma mark Constructors

    Polynomial() : std::vector<float>(1,0) { }
    
    Polynomial(long degree) : vector<float>(degree+1,0) {
        (*this)[0] = 1;
    }
    
    Polynomial(long degree, float value) : vector<float>(degree+1,value) {
    }

    Polynomial(const Polynomial& poly) : vector<float>(poly) {
    }
    
    Polynomial(const_iterator first, const_iterator last) : vector<float>(first,last) {
        CCASSERT(isValid(), "The array data is invalid");
    }
    
    Polynomial(float* array, unsigned int size, unsigned int offset=0) : vector<float>() {
        assign(array+offset,array+size+offset);
        CCASSERT(isValid(), "The array data is invalid");
    }
   
    virtual ~Polynomial() { }

    
#pragma mark Accessors

    long degree() const  { return (long)size()-1; }

    bool constant() const  { return size() == 1; }

    bool isValid() const { return size() == 1 || (size() > 1 && at(0) != 0); }
    
    bool isZero() const  { return size() == 1 && at(0) == 0; }

    
#pragma mark Basic Methods

    Polynomial derivative() const;

    float evaluate(float value) const;
    
    void validate();
    
    float normalize();

    bool roots(vector<float>& roots, float epsilon) const;
    
    string toString(bool format=true) const;

    
#pragma mark Operators

    Polynomial& operator+=(const Polynomial& other);
    
    Polynomial& operator-=(const Polynomial& other);
    
    Polynomial& operator*=(const Polynomial& other) {
        return *this = (*this)*other;
    }
    
    Polynomial& operator/=(const Polynomial& other);

    Polynomial& operator%=(const Polynomial& other);

    Polynomial operator+(const Polynomial& other) const {
        return Polynomial(*this) += other;
    }

    Polynomial operator-(const Polynomial& other) const {
        return Polynomial(*this) -= other;
    }

    Polynomial operator*(const Polynomial& other) const;

    Polynomial operator/(const Polynomial& other) const {
        return Polynomial(*this) /= other;
    }
    
    Polynomial operator%(const Polynomial& other) const {
        return Polynomial(*this) %= other;
    }

    Polynomial& operator+=(float value);
    
    Polynomial& operator-=(float value);
    
    Polynomial& operator*=(float value);
    
    Polynomial& operator/=(float value);

    Polynomial& operator%=(float value);
    
    Polynomial operator+(float value) const {
        return Polynomial(*this) += value;
    }

    Polynomial operator-(float value) const {
        return Polynomial(*this) += value;
    }
    
    Polynomial operator*(float value) const {
        return Polynomial(*this) += value;
    }

    Polynomial operator/(float value) const {
        return Polynomial(*this) /= value;
    }
    
    Polynomial operator%(float value) const {
        return Polynomial(*this) /= value;
    }
    
    
#pragma mark Friend Functions

    friend Polynomial operator+(float left, const Polynomial& right);

    friend Polynomial operator-(float left, const Polynomial& right);
    
    friend Polynomial operator*(float left, const Polynomial& right);

    friend Polynomial operator/(float left, const Polynomial& right);
    
    friend Polynomial operator%(float left, const Polynomial& right);
    
    friend ostream&   operator<<(ostream& os, const Polynomial& poly);

    
#pragma mark Internal Helpers
protected:
    static Polynomial iterative_multiply(const Polynomial& a, const Polynomial& b);
    
    static Polynomial recursive_multiply(const Polynomial& a, const Polynomial& b);
    
    Polynomial& synthetic_divide(const Polynomial& other);
    
    bool bairstow_factor(Polynomial& quad, Polynomial& result, float epsilon) const;
    
    void solve_quadratic(vector<float>& roots) const;
};

NS_CC_END

#endif /* defined(__CU_POLYNOMIAL_H__) */