zincite_check/
rectangles.rs

1//! Rectangle dimensions, optional presence and endpoint separation.
2use super::*;
3
4#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
5pub(crate) enum RectangleName {
6    Mandatory,
7    Optional,
8    FlexOptional,
9}
10impl RectangleName {
11    pub fn from_name(name: &str) -> Option<Self> {
12        for base in [
13            name,
14            name.strip_prefix("gecode_").unwrap_or(""),
15            name.strip_prefix("fzn_").unwrap_or(""),
16        ] {
17            match base {
18                "gecode_nooverlap" | "gecode_nooverlap_fzn" => return Some(Self::Mandatory),
19                "gecode_nooverlap_optional" => return Some(Self::Optional),
20                "gecode_nooverlap_flex_optional" => return Some(Self::FlexOptional),
21                _ => {}
22            }
23        }
24        None
25    }
26    #[cfg(feature = "prepare")]
27    pub fn arity(self) -> usize {
28        match self {
29            Self::Mandatory => 4,
30            Self::Optional => 5,
31            Self::FlexOptional => 7,
32        }
33    }
34    #[cfg(feature = "prepare")]
35    pub fn signature(self) -> Vec<prepare::ArgumentType> {
36        let mut args = vec![
37            prepare::ArgumentType {
38                kind: ValueType::Integer,
39                is_array: true,
40                is_var: true
41            };
42            self.arity()
43        ];
44        if self == Self::Optional {
45            args[1].is_var = false;
46            args[3].is_var = false;
47        }
48        if matches!(self, Self::Optional | Self::FlexOptional) {
49            args.last_mut().unwrap().kind = ValueType::Boolean;
50        }
51        args
52    }
53}
54#[derive(Debug, Serialize, Deserialize)]
55pub(crate) struct Rectangles {
56    pub name: RectangleName,
57    pub x: Vec<Operand>,
58    pub width: Vec<Operand>,
59    pub right: Option<Vec<Operand>>,
60    pub y: Vec<Operand>,
61    pub height: Vec<Operand>,
62    pub top: Option<Vec<Operand>>,
63    pub present: Option<Vec<Operand>>,
64}
65#[derive(Clone, Debug, Serialize)]
66pub struct RectangleArguments {
67    pub position: usize,
68    pub x: Option<ArgumentValue>,
69    pub width: Option<ArgumentValue>,
70    pub right: Option<ArgumentValue>,
71    pub y: Option<ArgumentValue>,
72    pub height: Option<ArgumentValue>,
73    pub top: Option<ArgumentValue>,
74    pub present: Option<ArgumentValue>,
75}
76#[derive(Clone, Copy, Debug, Serialize)]
77#[serde(rename_all = "snake_case")]
78pub enum RectangleDimension {
79    Width,
80    Height,
81}
82#[derive(Clone, Debug, Serialize)]
83#[serde(tag = "kind", rename_all = "snake_case")]
84pub enum RectangleFault {
85    Dimension {
86        position: usize,
87        dimension: RectangleDimension,
88        #[serde(serialize_with = "serialize_integer")]
89        value: i64,
90    },
91    Conflict {
92        first: usize,
93        second: usize,
94    },
95}
96#[derive(Clone, Debug, Serialize)]
97pub struct RectanglesFinding {
98    pub rectangles: Vec<RectangleArguments>,
99    pub faults: Vec<RectangleFault>,
100}
101struct RectangleBounds {
102    x: i64,
103    right: i64,
104    y: i64,
105    top: i64,
106}
107
108impl Rectangles {
109    pub fn integer_operands(&self) -> Vec<&Operand> {
110        self.x
111            .iter()
112            .chain(&self.width)
113            .chain(self.right.iter().flatten())
114            .chain(&self.y)
115            .chain(&self.height)
116            .chain(self.top.iter().flatten())
117            .collect()
118    }
119    pub fn operands(&self) -> Vec<&Operand> {
120        let mut operands = self.integer_operands();
121        operands.extend(self.present.iter().flatten());
122        operands
123    }
124    pub fn validate(&self) -> Result<(), &'static str> {
125        let n = self.x.len();
126        if self.width.len() != n
127            || self.y.len() != n
128            || self.height.len() != n
129            || self.right.as_ref().is_some_and(|a| a.len() != n)
130            || self.top.as_ref().is_some_and(|a| a.len() != n)
131            || self.present.as_ref().is_some_and(|a| a.len() != n)
132        {
133            return Err("rectangle arrays must have equal lengths");
134        }
135        let flex = self.name == RectangleName::FlexOptional;
136        let optional = matches!(
137            self.name,
138            RectangleName::Optional | RectangleName::FlexOptional
139        );
140        if self.right.is_some() != flex
141            || self.top.is_some() != flex
142            || self.present.is_some() != optional
143        {
144            return Err("rectangle fields do not match their interface");
145        }
146        if self.name == RectangleName::Optional && self.width.iter().chain(&self.height)
147            .any(|operand| !matches!(operand, Operand::Literal(Value::Integer(value)) if *value >= 0)) {
148            return Err("optional rectangle dimensions must be fixed nonnegative integers");
149        }
150        Ok(())
151    }
152    fn dimension_faults(&self, values: &[Option<Value>]) -> Vec<RectangleFault> {
153        let mut faults = Vec::new();
154        for i in 0..self.x.len() {
155            for (dimension, operand) in [
156                (RectangleDimension::Width, &self.width[i]),
157                (RectangleDimension::Height, &self.height[i]),
158            ] {
159                if let Some(Value::Integer(value)) = operand.value(values)
160                    && *value < 0
161                {
162                    faults.push(RectangleFault::Dimension {
163                        position: i + 1,
164                        dimension,
165                        value: *value,
166                    });
167                }
168            }
169        }
170        faults
171    }
172    fn relation_operands(&self, values: &[Option<Value>]) -> Vec<&Operand> {
173        let mut operands: Vec<_> = self
174            .width
175            .iter()
176            .chain(&self.height)
177            .chain(self.present.iter().flatten())
178            .collect();
179        for i in 0..self.x.len() {
180            if self
181                .present
182                .as_ref()
183                .is_some_and(|a| a[i].value(values) == Some(&Value::Boolean(false)))
184            {
185                continue;
186            }
187            operands.extend([&self.x[i], &self.y[i]]);
188            operands.extend(self.right.as_ref().map(|a| &a[i]));
189            operands.extend(self.top.as_ref().map(|a| &a[i]));
190        }
191        operands
192    }
193    pub fn required_operands(&self, values: &[Option<Value>]) -> Vec<&Operand> {
194        if self.dimension_faults(values).is_empty() {
195            self.relation_operands(values)
196        } else {
197            Vec::new()
198        }
199    }
200    fn bounds(
201        &self,
202        i: usize,
203        values: &[Option<Value>],
204        constraint: &Constraint,
205    ) -> Result<Option<RectangleBounds>, CheckError> {
206        if let Some(present) = &self.present
207            && present[i].value(values) != Some(&Value::Boolean(true))
208        {
209            return Ok(None);
210        }
211        let integer = |operand: &Operand| operand.value(values).map(Value::integer);
212        let (Some(x), Some(y), Some(width), Some(height)) = (
213            integer(&self.x[i]),
214            integer(&self.y[i]),
215            integer(&self.width[i]),
216            integer(&self.height[i]),
217        ) else {
218            return Ok(None);
219        };
220        if width < 0 || height < 0 {
221            return Ok(None);
222        }
223        let endpoint = |coordinates: &Option<Vec<Operand>>, start: i64, size: i64| {
224            if let Some(coordinates) = coordinates {
225                Ok(integer(&coordinates[i]))
226            } else {
227                start.checked_add(size).map(Some).ok_or_else(|| {
228                    constraint.execution_error("checked i64 overflow in rectangle endpoint")
229                })
230            }
231        };
232        let (Some(right), Some(top)) = (
233            endpoint(&self.right, x, width)?,
234            endpoint(&self.top, y, height)?,
235        ) else {
236            return Ok(None);
237        };
238        Ok(Some(RectangleBounds { x, right, y, top }))
239    }
240}
241impl PreparedModel {
242    pub(crate) fn evaluate_rectangles(
243        &self,
244        constraint: &Constraint,
245        rectangles: &Rectangles,
246        values: &[Option<Value>],
247    ) -> Result<Option<ViolationKind>, CheckError> {
248        let mut faults = rectangles.dimension_faults(values);
249        let bounds = (0..rectangles.x.len())
250            .map(|i| rectangles.bounds(i, values, constraint))
251            .collect::<Result<Vec<_>, _>>()?;
252        for (first, a) in bounds.iter().enumerate() {
253            let Some(a) = a else {
254                continue;
255            };
256            for (second, b) in bounds.iter().enumerate().skip(first + 1) {
257                if let Some(b) = b
258                    && !(a.right <= b.x || b.right <= a.x || a.top <= b.y || b.top <= a.y)
259                {
260                    faults.push(RectangleFault::Conflict {
261                        first: first + 1,
262                        second: second + 1,
263                    });
264                }
265            }
266        }
267        Ok((!faults.is_empty()).then(|| ViolationKind::Rectangles {
268            finding: RectanglesFinding {
269                rectangles: (0..rectangles.x.len())
270                    .map(|i| RectangleArguments {
271                        position: i + 1,
272                        x: self.argument(&rectangles.x[i], values),
273                        width: self.argument(&rectangles.width[i], values),
274                        right: rectangles
275                            .right
276                            .as_ref()
277                            .and_then(|a| self.argument(&a[i], values)),
278                        y: self.argument(&rectangles.y[i], values),
279                        height: self.argument(&rectangles.height[i], values),
280                        top: rectangles
281                            .top
282                            .as_ref()
283                            .and_then(|a| self.argument(&a[i], values)),
284                        present: rectangles
285                            .present
286                            .as_ref()
287                            .and_then(|a| self.argument(&a[i], values)),
288                    })
289                    .collect(),
290                faults,
291            },
292        }))
293    }
294}
zincite_check/rectangles.rs

zincite_check/
rectangles.rs
