xcsp3_rust/data_structs/expression_tree.rs
1/*=============================================================================
2* parser for CSP instances represented in XCSP3 Format
3*
4* Copyright (c) 2023 xcsp.org (contact @ xcsp.org)
5*
6* Permission is hereby granted, free of charge, to any person obtaining a copy
7* of this software and associated documentation files (the "Software"), to deal
8* in the Software without restriction, including without limitation the rights
9* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10* copies of the Software, and to permit persons to whom the Software is
11* furnished to do so, subject to the following conditions:
12*
13* The above copyright notice and this permission notice shall be included in
14* all copies or substantial portions of the Software.
15*
16* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22* THE SOFTWARE.
23*=============================================================================
24*/
25
26/*
27 * <p>@project_name: xcsp3-rust
28 * </p>
29 * <p>@author: luhan zhen
30 * </p>
31 * <p>@date: 2023/7/19 12:15
32 * </p>
33 * <p>@email: zhenlh20@mails.jlu.edu.cn
34 * </p>
35 * <p>@version: 1.0
36 * </p>
37 * <p>@description:
38 * </p>
39 */
40pub mod xcsp3_utils {
41 use crate::data_structs::xint_val_var::xcsp3_core::XVarVal;
42 use std::fmt::{Display, Formatter};
43 use std::str::FromStr;
44
45 use crate::errors::xcsp3error::xcsp3_core::Xcsp3Error;
46 use crate::variables::xvariable_set::xcsp3_core::XVariableSet;
47
48 #[derive(Debug, Clone)]
49 pub enum Operator {
50 Add,
51 Neg,
52 Abs,
53 Sub,
54 Mul,
55 Div,
56 Mod,
57 Sqr,
58 Pow,
59 Min,
60 Max,
61 Dist,
62 Lt,
63 Le,
64 Ge,
65 Gt,
66 Ne,
67 Eq,
68 And,
69 Not,
70 Or,
71 Xor,
72 Iff,
73 Imp,
74 If,
75 Set,
76 In,
77 }
78
79 impl Operator {
80 pub fn get_operator_by_str(op: &str) -> Option<Self> {
81 match op {
82 "add" => Some(Operator::Add),
83 "neg" => Some(Operator::Neg),
84 "abs" => Some(Operator::Abs),
85 "sub" => Some(Operator::Sub),
86 "mul" => Some(Operator::Mul),
87 "div" => Some(Operator::Div),
88 "mod" => Some(Operator::Mod),
89 "sqr" => Some(Operator::Sqr),
90 "pow" => Some(Operator::Pow),
91 "min" => Some(Operator::Min),
92 "max" => Some(Operator::Max),
93 "dist" => Some(Operator::Dist),
94 "lt" => Some(Operator::Lt),
95 "le" => Some(Operator::Le),
96 "ge" => Some(Operator::Ge),
97 "gt" => Some(Operator::Gt),
98 "ne" => Some(Operator::Ne),
99 "eq" => Some(Operator::Eq),
100 "and" => Some(Operator::And),
101 "not" => Some(Operator::Not),
102 "or" => Some(Operator::Or),
103 "xor" => Some(Operator::Xor),
104 "iff" => Some(Operator::Iff),
105 "imp" => Some(Operator::Imp),
106 "if" => Some(Operator::If),
107 "set" => Some(Operator::Set),
108 "in" => Some(Operator::In),
109 _ => None,
110 }
111 }
112 }
113
114 #[derive(Clone, Debug)]
115 pub enum TreeNode {
116 RightBracket,
117 LeftBracket,
118 Constant(i32),
119 Argument(i32),
120 Variable(String),
121 Operator(Operator, Vec<TreeNode>),
122 }
123
124 impl Display for TreeNode {
125 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
126 write!(
127 f,
128 "{}",
129 match self {
130 TreeNode::Constant(i) => i.to_string(),
131 TreeNode::RightBracket => ")".to_string(),
132 TreeNode::LeftBracket => "(".to_string(),
133 TreeNode::Variable(v) => v.to_string(),
134 TreeNode::Argument(a) => format!("%{}", a),
135 TreeNode::Operator(o, _) => {
136 format!("{:?}", o)
137 }
138 }
139 )
140 }
141 }
142
143 // impl TreeNode {
144 // pub(crate) fn replace_var_by_int(&mut self,var:&str,n:i32)->bool
145 // {
146 // if let TreeNode::Operator(_,ve) = self
147 // {
148 //
149 // for (i,e) in ve.iter().enumerate()
150 // {
151 // if let TreeNode::Variable(v) = e
152 // {
153 // if v.eq(var)
154 // {
155 // let ele = &mut ve[i];
156 // *ele = TreeNode::Argument(n);
157 // return true
158 // }
159 // }
160 // }
161 // }
162 // false
163 // }
164 // }
165
166 #[derive(Clone)]
167 pub struct ExpressionTree {
168 root: TreeNode,
169 // expression: String,
170 }
171
172 impl Display for ExpressionTree {
173 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
174 let mut ret = String::new();
175 for e in self.first_order_iter() {
176 ret += &*e.to_string();
177 match e {
178 TreeNode::Variable(_) => ret += ",",
179 TreeNode::Argument(_) => ret += ",",
180 TreeNode::Constant(_) => ret += ",",
181 _ => {}
182 }
183 }
184 write!(f, "{}", ret)
185 }
186 }
187 impl ExpressionTree {
188 pub fn get_scope(&self) -> Vec<String> {
189 let mut scope = vec![];
190 for e in self.first_order_iter() {
191 if let TreeNode::Variable(v) = e {
192 scope.push(v.clone());
193 }
194 }
195 scope
196 }
197 // fn replace_var_by_int(&mut self,var:&str,n:i32)
198 // {
199 //
200 // }
201 pub fn get(&self, set: &XVariableSet) -> Vec<XVarVal> {
202 let mut scope: Vec<XVarVal> = vec![];
203 for e in self.first_order_iter() {
204 if let TreeNode::Variable(v) = e {
205 let r = set.find_variable(v);
206 match r {
207 Ok(_) => {
208 // println!("{}", r);
209 scope.push(XVarVal::IntVar(v.to_string()))
210 }
211 Err(_) => {
212
213 // println!("{}, {}", e, err)
214 }
215 }
216 }
217 }
218 scope
219 }
220
221 pub fn from_string(expression: &str) -> Result<Self, Xcsp3Error> {
222 match ExpressionTree::parse(expression) {
223 Ok(e) => Ok(ExpressionTree {
224 root: e,
225 // expression: expression.to_string(),
226 }),
227 Err(e) => Err(e),
228 }
229 }
230
231 fn operator(exp: &str, stack: &mut Vec<TreeNode>) -> Option<Xcsp3Error> {
232 let expression: String = exp.chars().rev().collect();
233 // expression = expression.replace("(", "").replace(")", "");
234 match Operator::get_operator_by_str(&expression) {
235 None => {
236 if expression.contains('%') {
237 match i32::from_str(&expression[1..]) {
238 Ok(n) => stack.push(TreeNode::Argument(n)),
239 Err(_) => {
240 return Some(Xcsp3Error::get_constraint_expression_error(
241 "parse the expression error!!",
242 ));
243 }
244 }
245 } else {
246 match i32::from_str(&expression[..]) {
247 Ok(n) => stack.push(TreeNode::Constant(n)),
248 Err(_) => stack.push(TreeNode::Variable(expression)),
249 }
250 }
251 }
252 Some(ope) => {
253 let mut nodes = vec![];
254 loop {
255 let top = stack.pop();
256 match top {
257 None => {
258 return Some(Xcsp3Error::get_constraint_expression_error(
259 "parse the expression error!!",
260 ));
261 }
262 Some(n) => match n {
263 TreeNode::RightBracket => {
264 stack.push(TreeNode::Operator(ope, nodes));
265 break;
266 }
267 _ => {
268 nodes.push(n);
269 }
270 },
271 }
272 }
273 }
274 }
275 None
276 }
277
278 fn parse(expression: &str) -> Result<TreeNode, Xcsp3Error> {
279 let mut stack: Vec<TreeNode> = vec![];
280 let exp: String = expression.chars().filter(|c| !c.is_whitespace()).collect();
281
282 let rev_exp: String = exp.chars().rev().collect();
283 // println!("{rev_exp}");
284 let mut i = 0;
285 let mut last = 0;
286 while i < rev_exp.len() {
287 if &rev_exp[i..i + 1] == ")" {
288 stack.push(TreeNode::RightBracket);
289 last = i;
290 } else if &rev_exp[i..i + 1] == "," || &rev_exp[i..i + 1] == "(" {
291 if let Some(e) = ExpressionTree::operator(&rev_exp[last + 1..i], &mut stack) {
292 return Err(e);
293 }
294 last = i;
295 } else if i == rev_exp.len() - 1 {
296 if let Some(e) = ExpressionTree::operator(&rev_exp[last + 1..i + 1], &mut stack)
297 {
298 return Err(e);
299 }
300 }
301
302 i += 1
303 }
304
305 Ok(stack.pop().unwrap())
306 }
307 pub fn first_order_iter(&self) -> ExpressionFirstOrderIter {
308 ExpressionFirstOrderIter {
309 stack: vec![&self.root],
310 }
311 }
312 // pub fn last_order_iter(&self) -> ExpressionLastOrderIter {
313 // ExpressionLastOrderIter { stack: vec![&self.root] }
314 // }
315 }
316
317 pub struct ExpressionFirstOrderIter<'a> {
318 stack: Vec<&'a TreeNode>,
319 }
320
321 impl<'a> Iterator for ExpressionFirstOrderIter<'a> {
322 type Item = &'a TreeNode;
323 fn next(&mut self) -> Option<Self::Item> {
324 let top = match self.stack.pop() {
325 None => {
326 return None;
327 }
328 Some(t) => t,
329 };
330 if let TreeNode::Operator(_, vec) = top {
331 self.stack.push(&TreeNode::RightBracket);
332 (0..vec.len()).rev().for_each(|i| {
333 self.stack.push(&vec[i]);
334 });
335 self.stack.push(&TreeNode::LeftBracket);
336 };
337
338 Some(top)
339 }
340 }
341
342 // pub struct ExpressionLastOrderIter<'a> {
343 // stack: Vec<&'a TreeNode>,
344 // }
345 //
346 // impl<'a> Iterator for ExpressionLastOrderIter<'a> {
347 // type Item = &'a TreeNode;
348 // fn next(&mut self) -> Option<Self::Item> {
349 // loop
350 // {
351 // match self.stack.last() {
352 // None => { return None; }
353 // Some(top) => {
354 // match top
355 // {
356 // TreeNode::Operator(_, vec) => {
357 // (0..vec.len()).rev().for_each(|i| {
358 // self.stack.push(&vec[i]);
359 // })
360 // }
361 // _ => {break}
362 // }
363 // }
364 // }
365 // }
366 // match self.stack.pop()
367 // {
368 // None => { None }
369 // Some(t) => { Some(t) }
370 // }
371 // }
372 // }
373}