Global Constraint Catalog

2.2.2. Compound data types

We provide the following compound data types:

$𝚕𝚒𝚜𝚝 (T)$ corresponds to a list of elements of type $T$ , where $T$ is a basic or a compound data type.
$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (A_{1}, A_{2}, \dots, A_{n})$ corresponds to a collection of ordered items, where each item consists of $n > 0$ attributes $A_{1}, A_{2}, \dots, A_{n}$ . Each attribute is an expression of the form $𝚊 - T$ , where $𝚊$ is the name of the attribute and $T$ the type of the attribute (a basic or a compound data type). All names of the attributes of a given collection should be distinct and different from the keyword $𝚔𝚎𝚢$ , which corresponds to an implicitThis attribute is not explicitly defined. attribute. Its value is the position of an item within the collection. The first item of a collection is associated with position 1.

The following notations are used for instantiated arguments:

A list of elements $e_{1}, e_{2}, \dots, e_{n}$ is denoted $[e_{1}, e_{2}, \dots, e_{n}]$ .
A finite set of integers $i_{1}, i_{2}, \dots, i_{n}$ is denoted ${i_{1}, i_{2}, \dots, i_{n}}$ .
A multiset of integers $i_{1}, i_{2}, \dots, i_{n}$ is denoted ${{i_{1}, i_{2}, \dots, i_{n}}}$ .
A collection of $n$ items, each item having $m$ attributes, is denoted by

$〈 𝚊_{1} - v_{11} \dots 𝚊_{m} - v_{1 m}, 𝚊_{1} - v_{21} \dots 𝚊_{m} - v_{2 m}, \dots, 𝚊_{1} - v_{n 1} \dots 𝚊_{m} - v_{n m} 〉$ . Each item is separated from the previous item by a comma. When the items of the collection involve a single attribute $𝚊_{1}$ , $〈 v_{11}, v_{21}, \dots, v_{n 1} 〉$ can possibly be used as a shortcut for $〈 𝚊_{1} - v_{11}, 𝚊_{1} - v_{21}, \dots, 𝚊_{1} - v_{n 1} 〉$ .
The $i^{t h}$ item of a collection $𝚌$ is denoted $𝚌 [i]$ .
The value of the attribute $𝚊$ of the $i^{t h}$ item of a collection $𝚌$ is denoted $𝚌 [i] . 𝚊$ . Note that, within an arithmetic expression, we can use the shortcut $𝚌 [i]$ when the collection $𝚌$ involves a single attribute.
The number of items of a collection $𝚌$ is denoted $| 𝚌 |$ .

EXAMPLE: Let us illustrate with four examples, the types one can create. These examples concern the creation of a collection of variables, a collection of tasks, a graph variable [Dooms06] and a collection of orthotopes.An orthotope corresponds to the generalisation of a segment, a rectangle and a box to the $n$ -dimensional case.

In the first example we define $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ so that it corresponds to a collection of variables. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ is for instance used in the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint. The declaration $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 : 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$ defines a collection of items, each of which having one attribute $𝚟𝚊𝚛$ that is a domain variable.
In the second example we define $𝚃𝙰𝚂𝙺𝚂$ so that it corresponds to a collection of tasks, each task being defined by its origin, its duration, its end and its resource consumption. Such a collection is for instance used in the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint. The declaration $𝚃𝙰𝚂𝙺𝚂 : 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒𝚐𝚒𝚗 - 𝚍𝚟𝚊𝚛, 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛, 𝚑𝚎𝚒𝚐𝚑𝚝 - 𝚍𝚟𝚊𝚛)$ defines a collection of items, each of which having the four attributes $𝚘𝚛𝚒𝚐𝚒𝚗$ , $𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗$ , $𝚎𝚗𝚍$ and $𝚑𝚎𝚒𝚐𝚑𝚝$ which all are domain variables.
In the third example we define a graph as a collection of nodes $𝙽𝙾𝙳𝙴𝚂$ , each node being defined by its index (i.e., identifier) and its successors. Such a collection is for instance used in the $𝚍𝚊𝚐$ constraint. The declaration $𝙽𝙾𝙳𝙴𝚂 : 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚜𝚞𝚌𝚌 - 𝚜𝚟𝚊𝚛)$ defines a collection of items, each of which having the two attributes $𝚒𝚗𝚍𝚎𝚡$ and $𝚜𝚞𝚌𝚌$ which respectively are integers and set variables.
In the last example we define $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$ so that is corresponds to a collection of orthotopes. Each orthotope is described by an attribute $𝚘𝚛𝚝𝚑$ . Unlike the previous examples, the type of this attribute does not correspond any more to a basic data type but rather to a collection of $n$ items, where $n$ is the number of dimensions of the orthotope.1 for a segment, 2 for a rectangle, 3 for a box, ... . This collection, named $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴$ , defines for a given dimension the origin, the size and the end of the object in this dimension. This leads to the two declarations:
- $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒 - 𝚍𝚟𝚊𝚛, 𝚜𝚒𝚣 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛)$ ,
- $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚝𝚑 - 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴)$ .
$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$ is for instance used in the $𝚍𝚒𝚏𝚏𝚗$ constraint.

Global Constraint Catalog

2. Describing Global Constraints

2.2.2. Compound data types