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}