1 #ifndef _STEM4U_Polynomial_h_
2 #define _STEM4U_Polynomial_h_
3 
4 namespace Upp {
5 
6 template<class T>
7 class Polynomial : public Moveable<Polynomial<T>> {
8 public:
Polynomial()9 	Polynomial() {}
Polynomial(const Polynomial & p)10 	Polynomial(const Polynomial &p) {
11 		c = clone(p.c);
12 	}
13 	template<typename... Args>
Polynomial(T val,Args...args)14 	Polynomial(T val, Args... args) {
15 		Append(val);
16     	Append(args...);
17 	}
18 	T &operator[](int i) {
19 		if (i >= c.GetCount())
20 			c.SetCount(i+1);
21 		return c[i];
22 	}
Diff()23 	Polynomial Diff() const {
24   		Polynomial res;
25   		int num = GetCount();
26   		if (num == 0)
27 			return res;
28   		res.c.SetCount(num-1);
29 		for (int i = 1; i < num; ++i)
30 			res.c[i-1] = c[i]*i;
31 		return res;
32 	}
Order(int delta)33 	Polynomial Order(int delta) const {
34 		Polynomial res;
35 		int num = c.GetCount();
36 		if (num == 0)
37 			return res;
38 		res.c.SetCount(num+delta);
39 		int init = max(0, -delta);
40 		for (int i = init; i < num; ++i)
41 			res.c[i+delta] = c[i];
42 		return res;
43 	}
y(const T val)44 	T y(const T val) {
45 		T res = 0;
46 		int num = c.GetCount();
47 		if (num == 0)
48 			return res;
49 		res = c[0];
50 		T vval = 1;
51 		for (int i = 1; i < num; ++i) {
52 			vval *= val;
53 			res += c[i]*vval;
54 		}
55 		return res;
56 	}
Order()57 	int Order() const		{return c.GetCount() - 1;}
GetCount()58 	int GetCount() const	{return c.GetCount();}
Coeff(int i)59 	T Coeff(int i) const	{return c[i];}
60 
61 	const Polynomial& operator=(const T& l) {
62 		int num = l.GetCount();
63 		c.SetCount(num);
64 		for (int i = 0; i < num; ++i)
65 			c[i] = l.Coeff[i];
66 		return *this;
67 	}
68 
69     Polynomial operator+(const Polynomial& rhs) const {
70   		Polynomial res;
71   		int num = max(GetCount(), rhs.GetCount());
72   		res.c.SetCount(num);
73   		for (int i = 0; i < GetCount(); ++i)
74   			res.c[i] = c[i];
75   		for (int i = 0; i < rhs.GetCount(); ++i)
76   			res.c[i] += rhs.c[i];
77   		return res;
78     }
79     Polynomial operator-(const Polynomial& rhs) const {
80   		Polynomial res;
81   		int num = max(GetCount(), rhs.GetCount());
82   		res.c.SetCount(num);
83   		for (int i = 0; i < GetCount(); ++i)
84   			res.c[i] = c[i];
85   		for (int i = 0; i < rhs.GetCount(); ++i)
86   			res.c[i] -= rhs.c[i];
87   		return res;
88     }
89     Polynomial operator*(const Polynomial& rhs) const {
90   		Polynomial res;
91   		int num = Order() + rhs.Order() + 1;
92   		res.c.SetCount(num, 0);
93   		for (int i = 0; i < GetCount(); ++i)
94   			for (int j = 0; j < rhs.GetCount(); ++j)
95   				res.c[i + j] += c[i] * rhs.c[j];
96   		return res;
97     }
98     Polynomial operator*(const T &rhs) const {
99         Polynomial res;
100   		int num = GetCount();
101   		res.c.SetCount(num);
102   		for (int i = 0; i < GetCount(); ++i)
103   			res.c[i] = c[i] * rhs;
104   		return res;
105     }
ToString()106     String ToString() const {
107         String ret;
108 
109 		for (int i = GetCount()-1; i >= 0; --i) {
110 			bool isneg = c[i] < 0;
111 			String str;
112 			str << abs(c[i]);
113 			if (str != "0") {
114 				if (i < GetCount()-1) {
115 					if (!isneg)
116 						ret << " + ";
117 					else
118 						ret << " - ";
119 				} else {
120 					if (isneg)
121 						ret << "-";
122 				}
123 				if (str != "1")
124 					ret << str;
125 				if (i > 1)
126 					ret << "x^" << i;
127 				else if (i == 1)
128 					ret << "x";
129 			}
130 		}
131         return ret;
132     }
133 
134 private:
135 	Vector<T> c;
136 
Append()137 	void Append() {}
Append(T val)138 	void Append(T val) {
139 		c << val;
140 	}
141 	template<typename... Args>
Append(T val,Args...args)142 	void Append(T val, Args... args) {
143 		c << val;
144     	Append(args...);
145 	}
146 };
147 
148 template<typename T>
149 Polynomial<T> operator*(const T &lhs, const Polynomial<T> &rhs) {
150     Polynomial<T> res;
151 	int num = rhs.GetCount();
152 	res.c.SetCount(num);
153 	for (int i = 0; i < num; ++i)
154 		res.c[i] = rhs.c[i] * lhs;
155 	return res;
156 }
157 
158 }
159 
160 #endif
161