poly_log/
poly.rs

1use std::fmt;
2
3use super::constraint::Constraint;
4
5// =============================================================================
6// Polynomial
7// =============================================================================
8
9#[derive(Clone,Debug,PartialEq)]
10pub struct Polynomial {
11    terms: Vec<Term>
12}
13
14impl Polynomial {
15    pub fn var(vindex: usize) -> Polynomial {
16	let term = Term::new(1,&[vindex]);
17	Self{terms: vec![term]}
18    }
19
20    /// Determine the _sign_ of this polynomial (if known).  Here,
21    /// _positive_ sign indicates the polynomial can never evaluate to
22    /// a negative number.  In constrast, a _negative_ sign indicates
23    /// it cannot evalute to a (strictly) positive number.  For
24    /// example, `1+2x` has positive sign, whilst `-2x` has negative
25    /// sign.
26    pub fn sign(&self) -> Option<bool> {
27        let mut sign = false;
28        for (i,t) in self.terms.iter().enumerate() {
29            let ith = t.coefficient >= 0;
30            if i == 0 { sign = ith; }
31            else if sign != ith {
32                return None;
33            }
34        }
35	Some(sign)
36    }
37
38    /// Determine the _constant_ coefficient of this polynomial.  For
39    /// example, `1` is the constant component of `2x+1`.
40    pub fn constant(&self) -> isize {
41	for t in &self.terms {
42	    if t.vars.len() == 0 {
43		return t.coefficient;
44	    }
45	}
46	0
47    }
48
49    /// Determine whether or not this polynomial could be zero (or
50    /// not).  For example, `2x+1` cannot be zero (i.e. given that `x`
51    /// cannot be negative).  However, `x - y` can be zero (e.g. when
52    /// `x=y`).  Note: just because this polynomial could evaluate to
53    /// zero, it does not mean that it will.
54    pub fn is_zero(&self) -> Option<bool> {
55	// Check whether this is zero (or not)
56	if self.terms.len() == 0 { Some(true) }
57	// Check whether cannot be zero
58	else if self.sign() != None && self.constant() != 0 {
59	    // Cannot be zero.
60	    Some(false)
61	} else {
62	    // Still could be zero
63	    None
64	}
65    }
66
67    /// Determine whether or not this polynomial always evaluates to
68    /// something above zero (or not).
69    pub fn above_zero(&self) -> Option<bool> {
70	// Check whether this is zero (or not)
71	if self.terms.len() == 0 { Some(false) }
72	// Check whether cannot be zero
73	else if self.sign() == Some(true) && self.constant() != 0 {
74            // Has positive sign and a non-zero constant.  Therefore,
75            // must be above zero.
76	    Some(true)
77	} else if self.sign() == Some(false) {
78            // Has negative sign.  Therefore, cannot be above zero.
79            Some(false)
80        } else {
81	    // Unknown whether above zero or not
82	    None
83	}
84    }
85
86    /// Determine whether or not this polynomial always evaluates to
87    /// something below zero (or not).
88    pub fn below_zero(&self) -> Option<bool> {
89	// Check whether this is zero (or not)
90	if self.terms.len() == 0 { Some(false) }
91	// Check whether cannot be zero
92	else if self.sign() == Some(false) && self.constant() != 0 {
93            // Has negative sign and a non-zero constant.  Therefore,
94            // must be below zero.
95	    Some(true)
96	} else if self.sign() == Some(true) {
97            // Has positive sign.  Therefore, cannot be below zero.
98            Some(false)
99        } else {
100	    // Unknown whether above zero or not
101	    None
102	}
103    }
104
105    /// Negate this polynomial.  This is achieved by negating each
106    /// term within the polynomial.
107    pub fn negate(mut self) -> Self {
108        for t in &mut self.terms {
109            t.negate();
110        }
111        self
112    }
113
114    /// Add a given `Polynomial` onto this polynomial.  For example,
115    /// adding `x+2` to `2x+1` gives `3x+3`.
116    pub fn add(mut self, rhs: &Polynomial) -> Self {
117        for t in &rhs.terms {
118            self.internal_add(t);
119        }
120        self
121    }
122
123    /// Subtract a given `Polynomial` from this polynomial.
124    pub fn sub(mut self, rhs: &Polynomial) -> Self {
125        for t in &rhs.terms {
126            self.internal_sub(t);
127        }
128        self
129    }
130
131    pub fn mul(mut self, rhs: &Polynomial) -> Self {
132	let mut ts = Vec::new();
133	// Swap them
134	std::mem::swap(&mut ts, &mut self.terms);
135	//
136	for t1 in ts.into_iter() {
137	    for t2 in &rhs.terms {
138		// FIXME: ugly clone :)
139		let t3 = t1.clone().mul(&t2);
140		self.internal_add(&t3);
141	    }
142	}
143	self
144    }
145
146    /// Construct a constraint enforcing the equality of two
147    /// polynomials.
148    pub fn equals(mut self, rhs: Polynomial) -> Constraint {
149        Constraint::eq_zero(self.sub(&rhs))
150    }
151
152    /// Construct a constraint enforcing the non-equality of two
153    /// polynomials.
154    pub fn not_equals(mut self, rhs: Polynomial) -> Constraint {
155        Constraint::neq_zero(self.sub(&rhs))
156    }
157
158    /// Construct a constraint enforcing that one polynomial is less
159    /// than another.
160    pub fn less_than(mut self, rhs: Polynomial) -> Constraint {
161        Constraint::gt_zero(rhs.sub(&self))
162    }
163
164    /// Construct a constraint enforcing that one polynomial is less
165    /// than or equal to another.
166    pub fn less_than_or_equals(mut self, rhs: Polynomial) -> Constraint {
167        Constraint::gteq_zero(rhs.sub(&self))
168    }
169
170    /// Evaluate this `Polynomial` at a given point.
171    pub fn eval(&self, vals: &[usize]) -> isize {
172	let mut acc = 0;
173	for t in &self.terms {
174	    acc += t.eval(vals);
175	}
176	acc
177    }
178
179    /// Substitute all occurrenes of a given variable in `self` with a
180    /// given `Polynomial`.  For example, substituting `x:=x+1` into
181    /// `2x + xy` gives `2+2x+xy+y`.
182    pub fn substitute(&self, var: usize, val: &Polynomial) -> Polynomial {
183        let mut r = Self{terms: Vec::new()};
184        //
185        for t in &self.terms {
186            let p = t.substitute(var,val);
187            r = r + p;
188        }
189        //
190        r
191    }
192
193    // Add a single term into this polynomial.
194    fn internal_add(&mut self, term: &Term) {
195        for (i,t) in &mut self.terms.iter_mut().enumerate() {
196            if t.vars == term.vars {
197                t.coefficient += term.coefficient;
198                if t.coefficient == 0 {
199                    // Remove if empty coefficient.
200                    self.terms.remove(i);
201                }
202                return;
203            }
204        }
205        // Otherwise push back
206        self.terms.push(term.clone());
207	// Resort
208	self.terms.sort();
209    }
210
211    // Add a single term into this polynomial.
212    fn internal_sub(&mut self, term: &Term) {
213        for (i,t) in &mut self.terms.iter_mut().enumerate() {
214            if t.vars == term.vars {
215                t.coefficient -= term.coefficient;
216                if t.coefficient == 0 {
217                    // Remove if empty coefficient.
218                    self.terms.remove(i);
219                }
220                return;
221            }
222        }
223        // Otherwise push back
224        let mut t = term.clone();
225        t.negate();
226        self.terms.push(t);
227	// Resort
228	self.terms.sort();
229    }
230}
231
232// Formatting
233// -----------------------------------------------------------------------------
234
235impl fmt::Display for Polynomial {
236    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
237	for (i,t) in self.terms.iter().enumerate() {
238	    if i != 0 { write!(f,"+")?; }
239	    write!(f,"{t}")?;
240	}
241	Ok(())
242    }
243}
244// Coercions
245// -----------------------------------------------------------------------------
246impl From<usize> for Polynomial {
247    fn from(val: usize) -> Self {
248	if val == 0 {
249	    Self{terms: Vec::new()}
250	} else {
251            let term = Term{coefficient: val as isize, vars: Vec::new()};
252            Self{terms: vec![term]}
253	}
254    }
255}
256
257impl From<i32> for Polynomial {
258    fn from(val: i32) -> Self {
259	if val == 0 {
260	    Self{terms: Vec::new()}
261	} else {
262            let term = Term{coefficient: val as isize, vars: Vec::new()};
263            Self{terms: vec![term]}
264	}
265    }
266}
267
268// Operator overloading
269// -----------------------------------------------------------------------------
270impl std::ops::Add<usize> for Polynomial {
271    type Output = Self;
272
273    fn add(self, rhs: usize) -> Self {
274	let r = Polynomial::from(rhs);
275	self.add(&r)
276    }
277}
278
279impl std::ops::Add for Polynomial {
280    type Output = Self;
281
282    fn add(self, rhs: Self) -> Self {
283	self.add(&rhs)
284    }
285}
286
287impl std::ops::Sub<usize> for Polynomial {
288    type Output = Self;
289
290    fn sub(self, rhs: usize) -> Self {
291	let r = Polynomial::from(rhs);
292	self.sub(&r)
293    }
294}
295
296impl std::ops::Sub for Polynomial {
297    type Output = Self;
298
299    fn sub(self, rhs: Self) -> Self {
300	self.sub(&rhs)
301    }
302}
303
304impl std::ops::Mul<usize> for Polynomial {
305    type Output = Self;
306
307    fn mul(self, rhs: usize) -> Self {
308	let r = Polynomial::from(rhs);
309	self.mul(&r)
310    }
311}
312
313impl std::ops::Mul for Polynomial {
314    type Output = Self;
315
316    fn mul(self, rhs: Polynomial) -> Self {
317	self.mul(&rhs)
318    }
319}
320
321// =============================================================================
322// Polynomial Term
323// =============================================================================
324#[derive(Clone,Debug,Eq,Ord,PartialEq,PartialOrd)]
325pub struct Term {
326    coefficient: isize,
327    vars: Vec<usize>
328}
329
330impl Term {
331    pub fn new(coefficient: isize, vars: &[usize]) -> Self {
332	Self{coefficient, vars: vars.to_vec()}
333    }
334
335    pub fn negate(&mut self) {
336        self.coefficient = -self.coefficient;
337    }
338
339    pub fn mul(mut self, rhs: &Term) -> Self {
340	self.coefficient *= rhs.coefficient;
341	self.vars.extend_from_slice(&rhs.vars);
342	self.vars.sort();
343	self
344    }
345
346    pub fn eval(&self, vals: &[usize]) -> isize {
347	let mut r = self.coefficient;
348	for v in &self.vars {
349	    r *= vals[*v] as isize;
350	}
351	r
352    }
353
354    pub fn substitute(&self, var: usize, val: &Polynomial) -> Polynomial {
355        let mut nvars = Vec::new();
356        let mut count = 0;
357        // Construct inner term.
358        for v in &self.vars {
359            if *v == var {
360                count = count + 1;
361            } else {
362                nvars.push(*v);
363            }
364        }
365        //
366        let nterm = Self{coefficient: self.coefficient, vars: nvars};
367        let mut r = Polynomial{terms: vec![nterm]};
368        // Multiply it all out
369        for i in 0..count {
370            r = r * val.clone();
371        }
372        r
373    }
374}
375
376impl fmt::Display for Term {
377    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
378        write!(f, "{}", self.coefficient)?;
379	for idx in &self.vars {
380	    // FIXME: this could fail
381	    let v = (*idx as u32) % 3;
382	    let w = (*idx as u32) / 3;
383	    let a = ('x' as u32) + v;
384	    let c = char::from_u32(a).unwrap();
385	    write!(f,"*{c}{w}")?;
386	}
387	Ok(())
388    }
389}
poly_log/poly.rs

poly_log/
poly.rs
