CUPolynomial.h

//
//  CUPolynomial.h
//  Cornell University Game Library (CUGL)
//
//  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 CubicSpline and other beziers. However, we provide it publicly
//  in case it is useful for other applications.
//
//  Because math objects are intended to be on the stack, we do not provide
//  any shared pointer support in this class.
//
//  CUGL zlib License:
//      This software is provided 'as-is', without any express or implied
//      warranty.  In no event will the authors be held liable for any damages
//      arising from the use of this software.
//
//      Permission is granted to anyone to use this software for any purpose,
//      including commercial applications, and to alter it and redistribute it
//      freely, subject to the following restrictions:
//
//      1. The origin of this software must not be misrepresented; you must not
//      claim that you wrote the original software. If you use this software
//      in a product, an acknowledgment in the product documentation would be
//      appreciated but is not required.
//
//      2. Altered source versions must be plainly marked as such, and must not
//      be misrepresented as being the original software.
//
//      3. This notice may not be removed or altered from any source distribution.
//
//  Author: Walker White
//  Version: 6/20/16

#ifndef __CU_POLYNOMIAL_H__
#define __CU_POLYNOMIAL_H__

#include "CUMathBase.h"
#include "../util/CUDebug.h"
#include <iostream>
#include <vector>

namespace cugl {

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

    static const Polynomial ZERO;
    static const Polynomial ONE;

#pragma mark -
#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) {
        CUAssertLog(isValid(), "The array data is invalid");
    }
    
    Polynomial(float* array, unsigned int size, unsigned int offset=0) : vector<float>() {
        assign(array+offset,array+size+offset);
        CUAssertLog(isValid(), "The array data is invalid");
    }
    
    virtual ~Polynomial() { }
    
#pragma mark -
#pragma mark Attributes

    long degree() const  { return (long)size()-1; }
    
    bool isConstant() 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 -
#pragma mark Calculation Methods

    Polynomial derivative() const;
    
    float evaluate(float value) const;
    
    void validate();
    
    float normalize();
    
    bool roots(vector<float>& roots, float epsilon=CU_MATH_EPSILON) const;
    
#pragma mark -
#pragma mark Setters

    Polynomial& operator=(float value) {
        return set(value);
    }

    Polynomial& set(float* array, int size);

    Polynomial& set(float value) {
        resize(1); at(0) = value;
        return *this;
    }

#pragma mark -
#pragma mark Comparisons

    bool operator<(const Polynomial& p) const;

    bool operator<(float value) const {
        return size() == 1 && at(0) < value;
    }
    
    bool operator<=(const Polynomial& p) const;
    
    bool operator<=(float value) const {
        return size() == 1 && at(0) <= value;
    }
    
    bool operator>(const Polynomial& p) const;
    
    bool operator>(float value) const {
        return size() > 1 || at(0) > value;
    }
    
    bool operator>=(const Polynomial& p) const;
    
    bool operator>=(float value) const {
        return size() > 1 || at(0) >= value;
    }
    
    bool operator==(float value) const {
        return size() == 1 && at(0) == value;
    }
    
    bool operator!=(float value) const {
        return size() > 1 || at(0) != value;
    }
    
#pragma mark -
#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;
    }

    Polynomial operator-() const;

#pragma mark -
#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 bool operator<(float left, const Polynomial& right) {
        return right.size() > 1 || right[0] > left;
    }

    friend bool operator<=(float left, const Polynomial& right) {
        return right.size() > 1 || right[0] >= left;
    }
    
    friend bool operator>(float left, const Polynomial& right) {
        return right.size() == 1 && right[0] < left;
    }
    
    friend bool operator>=(float left, const Polynomial& right) {
        return right.size() == 1 && right[0] <= left;
    }

    
#pragma mark -
#pragma mark Conversion Methods

    std::string toString(bool format=true) const;
    
    operator std::string() const { return toString(); }

    
#pragma mark -
#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;
};

}

#endif /* __CU_POLYNOMIAL_H__ */