this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Gregory Crosswhite <gcross@phys.washington.edu>
9 *
10 * Copyright:
11 * Gregory Crosswhite, 2011
12 * Christian Schulte, 2003
13 * Guido Tack, 2004
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <iostream>
41#include <iterator>
42#include <vector>
43#include <sstream>
44#include <initializer_list>
45
46namespace Gecode { namespace Kernel {
47
48 /// Occurence information for a view
49 template<class View>
50 class ViewOcc {
51 public:
52 /// The view
53 View x;
54 /// The original index in the array
55 int i;
56 /// Sorting order
57 bool operator <(const ViewOcc& y) const;
58 };
59
60 template<class View>
61 forceinline bool
62 ViewOcc<View>::operator <(const ViewOcc& y) const {
63 return x < y.x;
64 }
65
66 /// Check whether \a p has duplicates among its \a n elements (changes \a p)
67 GECODE_KERNEL_EXPORT
68 bool duplicates(void** p, int n);
69
70 /// Check whether \a p has common elements with \a q
71 GECODE_KERNEL_EXPORT
72 bool duplicates(void** p, int n, void** q, int m);
73
74}}
75
76namespace Gecode {
77
78 template<class Var> class VarArray;
79 template<class Var> class VarArgArray;
80
81 /** \brief Traits of arrays in %Gecode
82 *
83 * This class collects the traits of an array in Gecode.
84 * The traits used are the following.
85 * - <code>typedef Type StorageType</code> where \c Type is the type
86 * of an appropriate storage type for this array.
87 * - <code>typedef Type ValueType</code> where \c Type is the type
88 * of the elements of this array.
89 * - <code>typedef Type ArgsType</code> where \c Type is the type
90 * of the appropriate Args-array type (e.g., \c BoolVarArgs if \c A is
91 * \c BoolVarArray).
92 */
93 template<class A>
94 class ArrayTraits {};
95
96 /**
97 * \brief %Variable arrays
98 *
99 * %Variable arrays store variables. They are typically used
100 * for storing the variables being part of a solution.
101 *
102 * Never use them for temporary purposes, use argument arrays
103 * instead.
104 *
105 * %Variable arrays can be enlarged dynamically. For memory efficiency, the
106 * initial array is allocated in the space. When adding variables, it is
107 * automatically resized and allocated on the heap.
108 *
109 * \ingroup TaskVar
110 */
111 template<class Var>
112 class VarArray {
113 protected:
114 /// Number of variables (size)
115 int n;
116 /// Array of variables
117 Var* x;
118 public:
119 /// \name Associated types
120 //@{
121 /// Type of the variable stored in this array
122 typedef Var value_type;
123 /// Type of a reference to the value type
124 typedef Var& reference;
125 /// Type of a constant reference to the value type
126 typedef const Var& const_reference;
127 /// Type of a pointer to the value type
128 typedef Var* pointer;
129 /// Type of a read-only pointer to the value type
130 typedef const Var* const_pointer;
131 /// Type of the iterator used to iterate through this array's elements
132 typedef Var* iterator;
133 /// Type of the iterator used to iterate read-only through this array's elements
134 typedef const Var* const_iterator;
135 /// Type of the iterator used to iterate backwards through this array's elements
136 typedef std::reverse_iterator<Var*> reverse_iterator;
137 /// Type of the iterator used to iterate backwards and read-only through this array's elements
138 typedef std::reverse_iterator<const Var*> const_reverse_iterator;
139 //@}
140
141 //@{
142 /// \name Constructors and initialization
143 //@{
144 /// Default constructor (array of size 0)
145 VarArray(void);
146 /// Allocate array with \a m variables
147 VarArray(Space& home, int m);
148 /// Initialize from variable argument array \a a (copy elements)
149 VarArray(Space& home, const VarArgArray<Var>&);
150 /// Initialize from variable array \a a (share elements)
151 VarArray(const VarArray<Var>& a);
152 /// Initialize from variable array \a a (share elements)
153 const VarArray<Var>& operator =(const VarArray<Var>& a);
154 //@}
155
156 /// \name Array size
157 //@{
158 /// Return size of array (number of elements)
159 int size(void) const;
160 //@}
161
162 /// \name Array elements
163 //@{
164 /// Return variable at position \a i
165 Var& operator [](int i);
166 /// Return variable at position \a i
167 const Var& operator [](int i) const;
168 /** Return slice \f$y\f$ of length at most \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$
169 *
170 * If \a n is -1, then all possible elements starting from \a start
171 * with increment \a inc are returned.
172 */
173 typename ArrayTraits<VarArgArray<Var>>::ArgsType
174 slice(int start, int inc=1, int n=-1);
175 //@}
176
177 /// \name Array iteration
178 //@{
179 /// Return an iterator at the beginning of the array
180 iterator begin(void);
181 /// Return a read-only iterator at the beginning of the array
182 const_iterator begin(void) const;
183 /// Return an iterator past the end of the array
184 iterator end(void);
185 /// Return a read-only iterator past the end of the array
186 const_iterator end(void) const;
187 /// Return a reverse iterator at the end of the array
188 reverse_iterator rbegin(void);
189 /// Return a reverse and read-only iterator at the end of the array
190 const_reverse_iterator rbegin(void) const;
191 /// Return a reverse iterator past the beginning of the array
192 reverse_iterator rend(void);
193 /// Return a reverse and read-only iterator past the beginning of the array
194 const_reverse_iterator rend(void) const;
195 //@}
196
197 /// Test if all variables are assigned
198 bool assigned(void) const;
199
200 /// \name Cloning
201 //@{
202 /// Update array to be a clone of array \a a
203 void update(Space& home, VarArray<Var>& a);
204 //@}
205
206 /// Allocate memory from heap (disabled)
207 static void* operator new(size_t s) = delete;
208 /// Free memory allocated from heap (disabled)
209 static void operator delete(void* p) = delete;
210 };
211
212 /** Concatenate \a x and \a y and return result
213 * \relates VarArray
214 */
215 template<class T>
216 typename ArrayTraits<VarArray<T>>::ArgsType
217 operator +(const VarArray<T>& x, const VarArgArray<T>& y);
218
219 /** Concatenate \a x and \a y and return result
220 * \relates VarArray
221 */
222 template<class T>
223 typename ArrayTraits<VarArray<T>>::ArgsType
224 operator +(const VarArray<T>& x, const VarArray<T>& y);
225
226 /** Concatenate \a x and \a y and return result
227 * \relates VarArray
228 */
229 template<class T>
230 typename ArrayTraits<VarArray<T>>::ArgsType
231 operator +(const VarArgArray<T>& x, const VarArray<T>& y);
232
233 /** Concatenate \a x and \a y and return result
234 * \relates VarArray
235 */
236 template<class T>
237 typename ArrayTraits<VarArray<T>>::ArgsType
238 operator +(const VarArray<T>& x, const T& y);
239
240 /** Concatenate \a x and \a y and return result
241 * \relates VarArray
242 */
243 template<class T>
244 typename ArrayTraits<VarArray<T>>::ArgsType
245 operator +(const T& x, const VarArray<T>& y);
246
247 /**
248 * \brief View arrays
249 *
250 * View arrays store views. They are typically used for storing the
251 * views with which propagators and branchers compute.
252 * \ingroup TaskActor
253 */
254 template<class View>
255 class ViewArray {
256 private:
257 /// Number of views (size)
258 int n;
259 /// Views
260 View* x;
261 public:
262 /// \name Associated types
263 //@{
264 /// Type of the view stored in this array
265 typedef View value_type;
266 /// Type of a reference to the value type
267 typedef View& reference;
268 /// Type of a constant reference to the value type
269 typedef const View& const_reference;
270 /// Type of a pointer to the value type
271 typedef View* pointer;
272 /// Type of a read-only pointer to the value type
273 typedef const View* const_pointer;
274 /// Type of the iterator used to iterate through this array's elements
275 typedef View* iterator;
276 /// Type of the iterator used to iterate read-only through this array's elements
277 typedef const View* const_iterator;
278 /// Type of the iterator used to iterate backwards through this array's elements
279 typedef std::reverse_iterator<View*> reverse_iterator;
280 /// Type of the iterator used to iterate backwards and read-only through this array's elements
281 typedef std::reverse_iterator<const View*> const_reverse_iterator;
282 //@}
283
284 /// \name Constructors and initialization
285 //@{
286 /// Default constructor (array of size 0)
287 ViewArray(void);
288 /// Allocate array with \a m views
289 ViewArray(Space& home, int m);
290 /// Allocate array with \a m views
291 ViewArray(Region& r, int m);
292 /// Initialize from view array \a a (share elements)
293 ViewArray(const ViewArray<View>& a);
294 /// Initialize from view array \a a (copy elements)
295 ViewArray(Space& home, const ViewArray<View>& a);
296 /// Initialize from view array \a a (copy elements)
297 ViewArray(Region& r, const ViewArray<View>& a);
298 /// Initialize from view array \a a (share elements)
299 const ViewArray<View>& operator =(const ViewArray<View>& a);
300 /**
301 * \brief Initialize from variable argument array \a a (copy elements)
302 *
303 * Note that the view type \a View must provide a constructor
304 * for the associated \a Var type.
305 */
306 template<class Var>
307 ViewArray(Space& home, const VarArgArray<Var>& a)
308 : n(a.size()) {
309 // This may not be in the hpp file (to satisfy the MS compiler)
310 if (n>0) {
311 x = home.alloc<View>(n);
312 for (int i=0; i<n; i++)
313 x[i]=a[i];
314 } else {
315 x = nullptr;
316 }
317 }
318 /**
319 * \brief Initialize from variable argument array \a a (copy elements)
320 *
321 * Note that the view type \a View must provide a constructor
322 * for the associated \a Var type.
323 */
324 template<class Var>
325 ViewArray(Region& r, const VarArgArray<Var>& a)
326 : n(a.size()) {
327 // This may not be in the hpp file (to satisfy the MS compiler)
328 if (n>0) {
329 x = r.alloc<View>(n);
330 for (int i=0; i<n; i++)
331 x[i]=a[i];
332 } else {
333 x = nullptr;
334 }
335 }
336 //@}
337
338 /// \name Array size
339 //@{
340 /// Return size of array (number of elements)
341 int size(void) const;
342 /// Decrease size of array (number of elements)
343 void size(int n);
344 //@}
345
346 /// \name Array elements
347 //@{
348 /// Return view at position \a i
349 View& operator [](int i);
350 /// Return view at position \a i
351 const View& operator [](int i) const;
352 //@}
353
354 /// \name Array iteration
355 //@{
356 /// Return an iterator at the beginning of the array
357 iterator begin(void);
358 /// Return a read-only iterator at the beginning of the array
359 const_iterator begin(void) const;
360 /// Return an iterator past the end of the array
361 iterator end(void);
362 /// Return a read-only iterator past the end of the array
363 const_iterator end(void) const;
364 /// Return a reverse iterator at the end of the array
365 reverse_iterator rbegin(void);
366 /// Return a reverse and read-only iterator at the end of the array
367 const_reverse_iterator rbegin(void) const;
368 /// Return a reverse iterator past the beginning of the array
369 reverse_iterator rend(void);
370 /// Return a reverse and read-only iterator past the beginning of the array
371 const_reverse_iterator rend(void) const;
372 //@}
373
374 /// \name Dependencies
375 //@{
376 /**
377 * \brief Subscribe propagator \a p with propagation condition \a pc to variable
378 *
379 * In case \a process is false, the propagator is just subscribed but
380 * not scheduled for execution (this must be used when creating
381 * subscriptions during propagation).
382 */
383 void subscribe(Space& home, Propagator& p, PropCond pc,
384 bool schedule=true);
385 /// Cancel subscription of propagator \a p with propagation condition \a pc to all views
386 void cancel(Space& home, Propagator& p, PropCond pc);
387 /// Subscribe advisor \a a to variable
388 void subscribe(Space& home, Advisor& a);
389 /// Cancel subscription of advisor \a a
390 void cancel(Space& home, Advisor& a);
391 /// Re-schedule propagator \a p with propagation condition \a pc
392 void reschedule(Space& home, Propagator& p, PropCond pc);
393 //@}
394
395 /// \name Cloning
396 //@{
397 /// Update array to be a clone of array \a a
398 void update(Space& home, ViewArray<View>& a);
399 //@}
400
401
402 /// \name Moving elements
403 //@{
404 /// Move view from position 0 to position \a i (shift elements to the left)
405 void move_fst(int i);
406 /// Move view from position \c size()-1 to position \a i (truncate array by one)
407 void move_lst(int i);
408 /** \brief Move view from position 0 to position \a i (shift elements to the left)
409 *
410 * Before moving, cancel subscription of propagator \a p with
411 * propagation condition \a pc to view at position \a i.
412 */
413 void move_fst(int i, Space& home, Propagator& p, PropCond pc);
414 /** \brief Move view from position \c size()-1 to position \a i (truncate array by one)
415 *
416 * Before moving, cancel subscription of propagator \a p with
417 * propagation condition \a pc to view at position \a i.
418 */
419 void move_lst(int i, Space& home, Propagator& p, PropCond pc);
420 /** \brief Move view from position 0 to position \a i (shift elements to the left)
421 *
422 * Before moving, cancel subscription of advisor \a a
423 * to view at position \a i.
424 */
425 void move_fst(int i, Space& home, Advisor& a);
426 /** \brief Move view from position \c size()-1 to position \a i (truncate array by one)
427 *
428 * Before moving, cancel subscription of advisor \a a to view
429 * at position \a i.
430 */
431 void move_lst(int i, Space& home, Advisor& a);
432 //@}
433
434 /// \name Dropping elements
435 //@{
436 /// Drop views from positions 0 to \a i-1 from array
437 void drop_fst(int i);
438 /// Drop views from positions \a i+1 to \c size()-1 from array
439 void drop_lst(int i);
440 /** \brief Drop views from positions 0 to \a i-1 from array
441 *
442 * Before moving, cancel subscription of propagator \a p with
443 * propagation condition \a pc to views at positions 0 to \a i-1.
444 */
445 void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
446 /** \brief Drop assigned views from positions \a i+1 to \c size()-1 from array
447 *
448 * Before moving, cancel subscription of propagator \a p with
449 * propagation condition \a pc to views at positions \a i+1 to
450 * \c size()-1.
451 */
452 void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
453 /** \brief Drop views from positions 0 to \a i-1 from array
454 *
455 * Before moving, cancel subscription of advisor \a a to views at
456 * positions 0 to \a i-1.
457 */
458 void drop_fst(int i, Space& home, Advisor& a);
459 /** \brief Drop assigned views from positions \a i+1 to \c size()-1 from array
460 *
461 * Before moving, cancel subscription of advisor \a a to views at
462 * positions \a i+1 to \c size()-1.
463 */
464 void drop_lst(int i, Space& home, Advisor& a);
465 //@}
466
467 /// Test if all variables are assigned
468 bool assigned(void) const;
469
470 /// \name View equality
471 //@{
472 /**
473 * \brief Test whether array has multiple occurence of the same view
474 *
475 * Note that assigned views are ignored.
476 */
477 bool same(void) const;
478 /**
479 * \brief Test whether array contains a view being the same as \a y
480 *
481 * Note that assigned views are ignored.
482 */
483 bool same(const View& y) const;
484 /// Remove all duplicate views from array (changes element order)
485 void unique(void);
486 //@}
487
488 /// Allocate memory from heap (disabled)
489 static void* operator new(size_t s) = delete;
490 /// Free memory allocated from heap (disabled)
491 static void operator delete(void* p) = delete;
492 };
493
494
495 /**
496 * \brief Test whether array \a x together with array \a y contains shared views
497 *
498 * Note that assigned views are ignored.
499 * \relates ViewArray
500 */
501 template<class ViewX, class ViewY>
502 bool shared(ViewArray<ViewX> x, ViewArray<ViewY> y);
503 /**
504 * \brief Test whether array \a x contains a view shared with \a y
505 *
506 * Note that assigned views are ignored.
507 * \relates ViewArray
508 */
509 template<class ViewX, class ViewY>
510 bool shared(ViewArray<ViewX> x, ViewY y);
511 /**
512 * \brief Test whether array \a y contains a view shared with \a x
513 *
514 * Note that assigned views are ignored.
515 * \relates ViewArray
516 */
517 template<class ViewX, class ViewY>
518 bool shared(ViewX x, ViewArray<ViewY> y);
519 /**
520 * \brief Test whether array \a x contains shared views
521 *
522 * Note that assigned views are ignored.
523 * \relates ViewArray
524 */
525 template<class View>
526 bool shared(ViewArray<View> x);
527
528
529 /**
530 * \brief Base-class for argument arrays
531 *
532 * Argument arrays are used as convenient mechanism of passing arguments
533 * when calling functions as they combine both the size and the elements
534 * of an array. For a small number of elements, memory is allocated by
535 * creating an argument array object. Otherwise the memory is allocated
536 * from the heap.
537 *
538 * \ingroup TaskVar
539 */
540 template<class T>
541 class ArgArrayBase {
542 protected:
543 /// Number of elements
544 int n;
545 /// Allocated size of the array
546 int capacity;
547 /// Element array
548 T* a;
549 /// How many elements are possible inside array
550 static const int onstack_size = 16;
551 /// In-array storage for elements
552 T onstack[onstack_size];
553 /// Allocate memory for \a n elements
554 T* allocate(int n);
555 /// Resize to hold at least \a i additional elements
556 void resize(int i);
557 /// Return this array concatenated with \a x
558 template<class A>
559 A concat(const ArgArrayBase<T>& x) const;
560 /// Return this array concatenated with \a x
561 template<class A>
562 A concat(const T& x) const;
563 /// Insert a new element \a x at the end of the array (increase size by 1)
564 template<class A>
565 A& append(const T& x);
566 /// Append \a x to the end of the array
567 template<class A>
568 A& append(const ArgArrayBase<T>& x);
569 /** Return slice \f$y\f$ of length at most \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$
570 *
571 * If \a n is -1, then all possible elements starting from \a start
572 * with increment \a inc are returned.
573 */
574 template<class A>
575 A slice(int start, int inc=1, int n=-1);
576 public:
577 /// \name Associated types
578 //@{
579 /// Type of the view stored in this array
580 typedef T value_type;
581 /// Type of a reference to the value type
582 typedef T& reference;
583 /// Type of a constant reference to the value type
584 typedef const T& const_reference;
585 /// Type of a pointer to the value type
586 typedef T* pointer;
587 /// Type of a read-only pointer to the value type
588 typedef const T* const_pointer;
589 /// Type of the iterator used to iterate through this array's elements
590 typedef T* iterator;
591 /// Type of the iterator used to iterate read-only through this array's elements
592 typedef const T* const_iterator;
593 /// Type of the iterator used to iterate backwards through this array's elements
594 typedef std::reverse_iterator<T*> reverse_iterator;
595 /// Type of the iterator used to iterate backwards and read-only through this array's elements
596 typedef std::reverse_iterator<const T*> const_reverse_iterator;
597 //@}
598
599 /// \name Constructors and initialization
600 //@{
601 /// Allocate empty array
602 ArgArrayBase(void);
603 /// Allocate array with \a n elements
604 explicit ArgArrayBase(int n);
605 /// Initialize from argument array \a a (copy elements)
606 ArgArrayBase(const ArgArrayBase<T>& a);
607 /// Initialize from view array \a a (copy elements)
608 const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
609 /// Initialize from vector \a a
610 ArgArrayBase(const std::vector<T>& a);
611 /// Initialize from initializer list \a a
612 ArgArrayBase(std::initializer_list<T> a);
613 /// Initialize from InputIterator \a begin and \a end
614 template<class InputIterator>
615 ArgArrayBase(InputIterator first, InputIterator last);
616 //@}
617
618 /// \name Array size
619 //@{
620 /// Return size of array (number of elements)
621 int size(void) const;
622 //@}
623
624 /// \name Array elements
625 //@{
626 /// Return element at position \a i
627 T& operator [](int i);
628 /// Return element at position \a i
629 const T& operator [](int i) const;
630 //@}
631
632 /// \name Array iteration
633 //@{
634 /// Return an iterator at the beginning of the array
635 iterator begin(void);
636 /// Return a read-only iterator at the beginning of the array
637 const_iterator begin(void) const;
638 /// Return an iterator past the end of the array
639 iterator end(void);
640 /// Return a read-only iterator past the end of the array
641 const_iterator end(void) const;
642 /// Return a reverse iterator at the end of the array
643 reverse_iterator rbegin(void);
644 /// Return a reverse and read-only iterator at the end of the array
645 const_reverse_iterator rbegin(void) const;
646 /// Return a reverse iterator past the beginning of the array
647 reverse_iterator rend(void);
648 /// Return a reverse and read-only iterator past the beginning of the array
649 const_reverse_iterator rend(void) const;
650 //@}
651
652 /// \name Destructor
653 //@{
654 /// Destructor
655 ~ArgArrayBase(void);
656 //@}
657 };
658
659
660 template<class> class ArgArray;
661
662 /** Concatenate \a x and \a y and return result
663 * \relates ArgArray
664 */
665 template<class T>
666 typename ArrayTraits<ArgArray<T>>::ArgsType
667 operator +(const ArgArray<T>& x, const ArgArray<T>& y);
668
669 /** Concatenate \a x and \a y and return result
670 * \relates ArgArray
671 */
672 template<class T>
673 typename ArrayTraits<ArgArray<T>>::ArgsType
674 operator +(const ArgArray<T>& x, const T& y);
675
676 /** Concatenate \a x and \a y and return result
677 * \relates ArgArray
678 */
679 template<class T>
680 typename ArrayTraits<ArgArray<T>>::ArgsType
681 operator +(const T& x, const ArgArray<T>& y);
682
683 /**
684 * \brief Argument array for non-primitive types
685 *
686 * Argument arrays are used as convenient mechanism of passing arguments
687 * when calling functions as they combine both the size and the elements
688 * of an array. For a small number of elements, memory is allocated by
689 * creating an argument array object. Otherwise the memory is allocated
690 * from the heap.
691 *
692 * \ingroup TaskVar
693 */
694 template<class T>
695 class ArgArray : public ArgArrayBase<T> {
696 protected:
697 using ArgArrayBase<T>::a;
698 public:
699 using ArgArrayBase<T>::size;
700 /// \name Constructors and initialization
701 //@{
702 /// Allocate empty array
703 ArgArray(void);
704 /// Allocate array with \a n elements
705 explicit ArgArray(int n);
706 /// Allocate array with \a n elements and initialize with elements from array \a e
707 ArgArray(int n, const T* e);
708 /// Initialize from argument array \a a (copy elements)
709 ArgArray(const ArgArray<T>& a);
710 /// Initialize from vector \a a
711 ArgArray(const std::vector<T>& a);
712 /// Initialize from initializer list \a a
713 ArgArray(std::initializer_list<T> a);
714 /// Initialize from InputIterator \a first and \a last
715 template<class InputIterator>
716 ArgArray(InputIterator first, InputIterator last);
717 //@}
718 /// \name Array elements
719 //@{
720 /// Return slice \f$y\f$ of length \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$
721 typename ArrayTraits<ArgArray<T>>::ArgsType
722 slice(int start, int inc=1, int n=-1);
723 //@}
724 /// \name Appending elements
725 //@{
726 /// Insert a new element \a x at the end of the array (increase size by 1)
727 typename ArrayTraits<ArgArray<T>>::ArgsType&
728 operator <<(const T& x);
729 /// Append \a x to the end of the array
730 typename ArrayTraits<ArgArray<T>>::ArgsType&
731 operator <<(const ArgArray<T>& x);
732 //@}
733
734 friend typename ArrayTraits<ArgArray<T>>::ArgsType
735 operator + <>(const ArgArray<T>& x, const ArgArray<T>& y);
736 friend typename ArrayTraits<ArgArray<T>>::ArgsType
737 operator + <>(const ArgArray<T>& x, const T& y);
738 friend
739 typename ArrayTraits<ArgArray<T>>::ArgsType
740 operator + <>(const T& x, const ArgArray<T>& y);
741 };
742
743 template<class> class VarArgArray;
744
745 /** Concatenate \a x and \a y and return result
746 * \relates ArgArray
747 */
748 template<class Var>
749 typename ArrayTraits<VarArgArray<Var>>::ArgsType
750 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
751
752 /** Concatenate \a x and \a y and return result
753 * \relates ArgArray
754 */
755 template<class Var>
756 typename ArrayTraits<VarArgArray<Var>>::ArgsType
757 operator +(const VarArgArray<Var>& x, const Var& y);
758
759 /** Concatenate \a x and \a y and return result
760 * \relates ArgArray
761 */
762 template<class Var>
763 typename ArrayTraits<VarArgArray<Var>>::ArgsType
764 operator +(const Var& x, const VarArgArray<Var>& y);
765
766 /**
767 * \brief Argument array for variables
768 *
769 * Argument arrays are used as convenient mechanism of passing arguments
770 * when calling functions as they combine both the size and the elements
771 * of an array. For a small number of elements, memory is allocated by
772 * creating an argument array object. Otherwise the memory is allocated
773 * from the heap.
774 *
775 * \ingroup TaskVar
776 */
777 template<class Var>
778 class VarArgArray : public ArgArrayBase<Var> {
779 protected:
780 using ArgArrayBase<Var>::a;
781 using ArgArrayBase<Var>::n;
782 public:
783 using ArgArrayBase<Var>::size;
784 /// \name Constructors and initialization
785 //@{
786 /// Allocate empty array
787 VarArgArray(void);
788 /// Allocate array with \a n elements
789 explicit VarArgArray(int n);
790 /// Initialize from variable argument array \a a (copy elements)
791 VarArgArray(const VarArgArray<Var>& a);
792 /// Initialize from variable array \a a (copy elements)
793 VarArgArray(const VarArray<Var>& a);
794 /// Initialize from vector \a a
795 VarArgArray(const std::vector<Var>& a);
796 /// Initialize from initializer list \a a
797 VarArgArray(std::initializer_list<Var> a);
798 /// Initialize from InputIterator \a first and \a last
799 template<class InputIterator>
800 VarArgArray(InputIterator first, InputIterator last);
801 //@}
802 /// \name Array elements
803 //@{
804 /// Return slice \f$y\f$ of length \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$
805 typename ArrayTraits<VarArgArray<Var>>::ArgsType
806 slice(int start, int inc=1, int n=-1);
807 //@}
808 /// \name Appending elements
809 //@{
810 /// Insert a new element \a x at the end of the array (increase size by 1)
811 typename ArrayTraits<VarArgArray<Var>>::ArgsType&
812 operator <<(const Var& x);
813 /// Append \a x to the end of the array
814 typename ArrayTraits<VarArgArray<Var>>::ArgsType&
815 operator <<(const VarArgArray<Var>& x);
816 //@}
817
818 /// Test if all variables are assigned
819 bool assigned(void) const;
820
821 friend typename ArrayTraits<VarArgArray<Var>>::ArgsType
822 operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
823 friend typename ArrayTraits<VarArgArray<Var>>::ArgsType
824 operator + <>(const VarArgArray<Var>& x, const Var& y);
825 friend
826 typename ArrayTraits<VarArgArray<Var>>::ArgsType
827 operator + <>(const Var& x, const VarArgArray<Var>& y);
828 };
829
830
831 /**
832 * \brief Test whether array \a x together with array \a y contains at least one variable being the same
833 *
834 * Note that assigned variables are ignored.
835 * \relates VarArgArray
836 */
837 template<class Var>
838 bool same(VarArgArray<Var> x, VarArgArray<Var> y);
839 /**
840 * \brief Test whether array \a x contains variable \a y
841 *
842 * Note that assigned variables are ignored.
843 * \relates VarArgArray
844 */
845 template<class Var>
846 bool same(VarArgArray<Var> x, Var y);
847 /**
848 * \brief Test whether array \a y contains variable \a x
849 *
850 * Note that assigned variables are ignored.
851 * \relates VarArgArray
852 */
853 template<class Var>
854 bool same(Var x, VarArgArray<Var> y);
855 /**
856 * \brief Test whether array \a x contains a variable multiply
857 *
858 * Note that assigned variables are ignored.
859 * \relates VarArgArray
860 */
861 template<class Var>
862 bool same(VarArgArray<Var> x);
863
864
865 /**
866 * \brief Print array elements enclosed in curly brackets
867 * \relates VarArray
868 */
869 template<class Char, class Traits, class Var>
870 std::basic_ostream<Char,Traits>&
871 operator <<(std::basic_ostream<Char,Traits>& os,
872 const VarArray<Var>& x);
873
874 /**
875 * \brief Print array elements enclosed in curly brackets
876 * \relates ViewArray
877 */
878 template<class Char, class Traits, class View>
879 std::basic_ostream<Char,Traits>&
880 operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
881
882 /**
883 * \brief Print array elements enclosed in curly brackets
884 * \relates ArgArrayBase
885 */
886 template<class Char, class Traits, class T>
887 std::basic_ostream<Char,Traits>&
888 operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
889
890
891 /*
892 * Implementation
893 *
894 */
895
896 /*
897 * Variable arrays
898 *
899 * These arrays are allocated in the space.
900 *
901 */
902
903 template<class Var>
904 forceinline
905 VarArray<Var>::VarArray(void) : n(0), x(nullptr) {}
906
907 template<class Var>
908 forceinline
909 VarArray<Var>::VarArray(Space& home, int n0)
910 : n(n0) {
911 // Allocate from space
912 x = (n>0) ? home.alloc<Var>(n) : nullptr;
913 }
914
915 template<class Var>
916 forceinline
917 VarArray<Var>::VarArray(const VarArray<Var>& a) {
918 n = a.n; x = a.x;
919 }
920
921 template<class Var>
922 inline const VarArray<Var>&
923 VarArray<Var>::operator =(const VarArray<Var>& a) {
924 n = a.n; x = a.x;
925 return *this;
926 }
927
928 template<class Var>
929 forceinline int
930 VarArray<Var>::size(void) const {
931 return n;
932 }
933
934 template<class Var>
935 forceinline Var&
936 VarArray<Var>::operator [](int i) {
937 assert((i >= 0) && (i < size()));
938 return x[i];
939 }
940
941 template<class Var>
942 forceinline const Var&
943 VarArray<Var>::operator [](int i) const {
944 assert((i >= 0) && (i < size()));
945 return x[i];
946 }
947
948 template<class Var>
949 typename ArrayTraits<VarArgArray<Var>>::ArgsType
950 VarArray<Var>::slice(int start, int inc, int maxN) {
951 assert(n==0 || start < n);
952 if (n==0 || maxN<0)
953 maxN = n;
954 int s;
955 if (inc == 0)
956 s = n-start;
957 else if (inc > 0)
958 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
959 else
960 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
961 typename ArrayTraits<VarArgArray<Var>>::ArgsType r(std::min(maxN,s));
962 for (int i=0; i<r.size(); i++, start+=inc)
963 r[i] = x[start];
964 return r;
965 }
966
967 template<class Var>
968 forceinline typename VarArray<Var>::iterator
969 VarArray<Var>::begin(void) {
970 return x;
971 }
972
973 template<class Var>
974 forceinline typename VarArray<Var>::const_iterator
975 VarArray<Var>::begin(void) const {
976 return x;
977 }
978
979 template<class Var>
980 forceinline typename VarArray<Var>::iterator
981 VarArray<Var>::end(void) {
982 return x+n;
983 }
984
985 template<class Var>
986 forceinline typename VarArray<Var>::const_iterator
987 VarArray<Var>::end(void) const {
988 return x+n;
989 }
990
991 template<class Var>
992 forceinline typename VarArray<Var>::reverse_iterator
993 VarArray<Var>::rbegin(void) {
994 return reverse_iterator(x+n);
995 }
996
997 template<class Var>
998 forceinline typename VarArray<Var>::const_reverse_iterator
999 VarArray<Var>::rbegin(void) const {
1000 return const_reverse_iterator(x+n);
1001 }
1002
1003 template<class Var>
1004 forceinline typename VarArray<Var>::reverse_iterator
1005 VarArray<Var>::rend(void) {
1006 return reverse_iterator(x);
1007 }
1008
1009 template<class Var>
1010 forceinline typename VarArray<Var>::const_reverse_iterator
1011 VarArray<Var>::rend(void) const {
1012 return const_reverse_iterator(x);
1013 }
1014
1015 template<class Var>
1016 forceinline void
1017 VarArray<Var>::update(Space& home, VarArray<Var>& a) {
1018 n = a.n;
1019 if (n > 0) {
1020 x = home.alloc<Var>(n);
1021 for (int i=0; i<n; i++)
1022 x[i].update(home, a.x[i]);
1023 } else {
1024 x = nullptr;
1025 }
1026 }
1027
1028 template<class Var>
1029 forceinline bool
1030 VarArray<Var>::assigned(void) const {
1031 for (int i=0; i<n; i++)
1032 if (!x[i].assigned())
1033 return false;
1034 return true;
1035 }
1036
1037
1038 template<class Var>
1039 typename ArrayTraits<VarArray<Var>>::ArgsType
1040 operator +(const VarArray<Var>& x, const VarArray<Var>& y) {
1041 typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
1042 for (int i=0; i<x.size(); i++)
1043 r[i] = x[i];
1044 for (int i=0; i<y.size(); i++)
1045 r[x.size()+i] = y[i];
1046 return r;
1047 }
1048
1049 template<class Var>
1050 typename ArrayTraits<VarArray<Var>>::ArgsType
1051 operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) {
1052 typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
1053 for (int i=0; i<x.size(); i++)
1054 r[i] = x[i];
1055 for (int i=0; i<y.size(); i++)
1056 r[x.size()+i] = y[i];
1057 return r;
1058 }
1059
1060 template<class Var>
1061 typename ArrayTraits<VarArray<Var>>::ArgsType
1062 operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) {
1063 typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
1064 for (int i=0; i<x.size(); i++)
1065 r[i] = x[i];
1066 for (int i=0; i<y.size(); i++)
1067 r[x.size()+i] = y[i];
1068 return r;
1069 }
1070
1071 template<class Var>
1072 typename ArrayTraits<VarArray<Var>>::ArgsType
1073 operator +(const VarArray<Var>& x, const Var& y) {
1074 typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+1);
1075 for (int i=0; i<x.size(); i++)
1076 r[i] = x[i];
1077 r[x.size()] = y;
1078 return r;
1079 }
1080
1081 template<class Var>
1082 typename ArrayTraits<VarArray<Var>>::ArgsType
1083 operator +(const Var& x, const VarArray<Var>& y) {
1084 typename ArrayTraits<VarArray<Var>>::ArgsType r(y.size()+1);
1085 r[0] = x;
1086 for (int i=0; i<y.size(); i++)
1087 r[1+i] = y[i];
1088 return r;
1089 }
1090
1091 /*
1092 * View arrays
1093 *
1094 */
1095
1096 template<class View>
1097 forceinline
1098 ViewArray<View>::ViewArray(void) : n(0), x(nullptr) {}
1099
1100 template<class View>
1101 forceinline
1102 ViewArray<View>::ViewArray(Space& home, int n0)
1103 : n(n0) {
1104 x = (n>0) ? home.alloc<View>(n) : nullptr;
1105 }
1106 template<class View>
1107 forceinline
1108 ViewArray<View>::ViewArray(Region& r, int n0)
1109 : n(n0) {
1110 x = (n>0) ? r.alloc<View>(n) : nullptr;
1111 }
1112
1113 template<class View>
1114 ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
1115 : n(a.size()) {
1116 if (n>0) {
1117 x = home.alloc<View>(n);
1118 for (int i=0; i<n; i++)
1119 x[i] = a[i];
1120 } else {
1121 x = nullptr;
1122 }
1123 }
1124 template<class View>
1125 ViewArray<View>::ViewArray(Region& r, const ViewArray<View>& a)
1126 : n(a.size()) {
1127 if (n>0) {
1128 x = r.alloc<View>(n);
1129 for (int i=0; i<n; i++)
1130 x[i] = a[i];
1131 } else {
1132 x = nullptr;
1133 }
1134 }
1135
1136 template<class View>
1137 forceinline
1138 ViewArray<View>::ViewArray(const ViewArray<View>& a)
1139 : n(a.n), x(a.x) {}
1140
1141 template<class View>
1142 forceinline const ViewArray<View>&
1143 ViewArray<View>::operator =(const ViewArray<View>& a) {
1144 n = a.n; x = a.x;
1145 return *this;
1146 }
1147
1148 template<class View>
1149 forceinline int
1150 ViewArray<View>::size(void) const {
1151 return n;
1152 }
1153
1154 template<class View>
1155 forceinline void
1156 ViewArray<View>::size(int n0) {
1157 n = n0;
1158 }
1159
1160 template<class View>
1161 forceinline View&
1162 ViewArray<View>::operator [](int i) {
1163 assert((i >= 0) && (i < size()));
1164 return x[i];
1165 }
1166
1167 template<class View>
1168 forceinline const View&
1169 ViewArray<View>::operator [](int i) const {
1170 assert((i >= 0) && (i < size()));
1171 return x[i];
1172 }
1173
1174 template<class View>
1175 forceinline typename ViewArray<View>::iterator
1176 ViewArray<View>::begin(void) {
1177 return x;
1178 }
1179
1180 template<class View>
1181 forceinline typename ViewArray<View>::const_iterator
1182 ViewArray<View>::begin(void) const {
1183 return x;
1184 }
1185
1186 template<class View>
1187 forceinline typename ViewArray<View>::iterator
1188 ViewArray<View>::end(void) {
1189 return x+n;
1190 }
1191
1192 template<class View>
1193 forceinline typename ViewArray<View>::const_iterator
1194 ViewArray<View>::end(void) const {
1195 return x+n;
1196 }
1197
1198 template<class View>
1199 forceinline typename ViewArray<View>::reverse_iterator
1200 ViewArray<View>::rbegin(void) {
1201 return reverse_iterator(x+n);
1202 }
1203
1204 template<class View>
1205 forceinline typename ViewArray<View>::const_reverse_iterator
1206 ViewArray<View>::rbegin(void) const {
1207 return const_reverse_iterator(x+n);
1208 }
1209
1210 template<class View>
1211 forceinline typename ViewArray<View>::reverse_iterator
1212 ViewArray<View>::rend(void) {
1213 return reverse_iterator(x);
1214 }
1215
1216 template<class View>
1217 forceinline typename ViewArray<View>::const_reverse_iterator
1218 ViewArray<View>::rend(void) const {
1219 return const_reverse_iterator(x);
1220 }
1221
1222 template<class View>
1223 forceinline void
1224 ViewArray<View>::move_fst(int i) {
1225 x[i]=x[0]; x++; n--;
1226 }
1227
1228 template<class View>
1229 forceinline void
1230 ViewArray<View>::move_lst(int i) {
1231 n--; x[i]=x[n];
1232 }
1233
1234 template<class View>
1235 forceinline void
1236 ViewArray<View>::drop_fst(int i) {
1237 assert(i>=0);
1238 x += i; n -= i;
1239 }
1240
1241 template<class View>
1242 forceinline void
1243 ViewArray<View>::drop_lst(int i) {
1244 assert(i<n);
1245 n = i+1;
1246 }
1247
1248 template<class View>
1249 forceinline void
1250 ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
1251 // Move x[0] to x[i]
1252 x[i].cancel(home,p,pc);
1253 x[i]=x[0]; x++; n--;
1254 }
1255
1256 template<class View>
1257 forceinline void
1258 ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
1259 // Move x[n-1] to x[i]
1260 x[i].cancel(home,p,pc);
1261 n--; x[i]=x[n];
1262 }
1263
1264 template<class View>
1265 void
1266 ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
1267 // Drop elements from 0..i-1
1268 assert(i>=0);
1269 for (int j=0; j<i; j++)
1270 x[j].cancel(home,p,pc);
1271 x += i; n -= i;
1272 }
1273
1274 template<class View>
1275 void
1276 ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
1277 // Drop elements from i+1..n-1
1278 assert(i<n);
1279 for (int j=i+1; j<n; j++)
1280 x[j].cancel(home,p,pc);
1281 n = i+1;
1282 }
1283
1284 template<class View>
1285 forceinline void
1286 ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
1287 // Move x[0] to x[i]
1288 x[i].cancel(home,a);
1289 x[i]=x[0]; x++; n--;
1290 }
1291
1292 template<class View>
1293 forceinline void
1294 ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
1295 // Move x[n-1] to x[i]
1296 x[i].cancel(home,a);
1297 n--; x[i]=x[n];
1298 }
1299
1300 template<class View>
1301 void
1302 ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
1303 // Drop elements from 0..i-1
1304 assert(i>=0);
1305 for (int j=0; j<i; j++)
1306 x[j].cancel(home,a);
1307 x += i; n -= i;
1308 }
1309
1310 template<class View>
1311 void
1312 ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
1313 // Drop elements from i+1..n-1
1314 assert(i<n);
1315 for (int j=i+1; j<n; j++)
1316 x[j].cancel(home,a);
1317 n = i+1;
1318 }
1319
1320 template<class View>
1321 void
1322 ViewArray<View>::update(Space& home, ViewArray<View>& y) {
1323 n = y.n;
1324 if (n > 0) {
1325 x = home.alloc<View>(n);
1326 for (int i=0; i<n; i++)
1327 x[i].update(home, y.x[i]);
1328 } else {
1329 x = nullptr;
1330 }
1331 }
1332
1333 template<class View>
1334 void
1335 ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
1336 bool schedule) {
1337 for (int i=0; i<n; i++)
1338 x[i].subscribe(home,p,pc,schedule);
1339 }
1340
1341 template<class View>
1342 void
1343 ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
1344 for (int i=0; i<n; i++)
1345 x[i].cancel(home,p,pc);
1346 }
1347
1348 template<class View>
1349 void
1350 ViewArray<View>::subscribe(Space& home, Advisor& a) {
1351 for (int i=0; i<n; i++)
1352 x[i].subscribe(home,a);
1353 }
1354
1355 template<class View>
1356 void
1357 ViewArray<View>::cancel(Space& home, Advisor& a) {
1358 for (int i=0; i<n; i++)
1359 x[i].cancel(home,a);
1360 }
1361
1362 template<class View>
1363 void
1364 ViewArray<View>::reschedule(Space& home, Propagator& p, PropCond pc) {
1365 for (int i=0; i<n; i++)
1366 x[i].reschedule(home,p,pc);
1367 }
1368
1369 template<class View>
1370 forceinline bool
1371 ViewArray<View>::assigned(void) const {
1372 for (int i=0; i<n; i++)
1373 if (!x[i].assigned())
1374 return false;
1375 return true;
1376 }
1377
1378 template<class View>
1379 bool
1380 ViewArray<View>::same(void) const {
1381 if (n < 2)
1382 return false;
1383 Region r;
1384 View* y = r.alloc<View>(n);
1385 int j=0;
1386 for (int i=0; i<n; i++)
1387 if (!x[i].assigned())
1388 y[j++] = x[i];
1389 if (j < 2)
1390 return false;
1391 Support::quicksort<View>(y,j);
1392 for (int i=1; i<j; i++)
1393 if (y[i-1] == y[i])
1394 return true;
1395 return false;
1396 }
1397
1398 template<class View>
1399 bool
1400 ViewArray<View>::same(const View& y) const {
1401 if (y.assigned())
1402 return false;
1403 for (int i=0; i<n; i++)
1404 if (x[i] == y)
1405 return true;
1406 return false;
1407 }
1408
1409 template<class View>
1410 void
1411 ViewArray<View>::unique(void) {
1412 if (n < 2)
1413 return;
1414 Region r;
1415 Kernel::ViewOcc<View>* o = r.alloc<Kernel::ViewOcc<View>>(n);
1416 for (int i=0; i<n; i++) {
1417 o[i].x = x[i]; o[i].i = i;
1418 }
1419 Support::quicksort<Kernel::ViewOcc<View>>(o,n);
1420 // Assign bucket numbers
1421 int* bkt = r.alloc<int>(n);
1422 int b = 0;
1423 bkt[o[0].i] = b;
1424 for (int i=1; i<n; i++) {
1425 if (o[i-1].x != o[i].x)
1426 b++;
1427 bkt[o[i].i] = b;
1428 }
1429 // Eliminate duplicate elements
1430 Support::BitSet<Region> seen(r,static_cast<unsigned int>(b+1));
1431 int j=0;
1432 for (int i=0; i<n; i++)
1433 if (!seen.get(static_cast<unsigned int>(bkt[i]))) {
1434 x[j++]=x[i]; seen.set(static_cast<unsigned int>(bkt[i]));
1435 } else {
1436 x[j]=x[i];
1437 }
1438 assert(j == b+1);
1439 n = j;
1440 }
1441
1442
1443 /*
1444 * Sharing for view arrays
1445 *
1446 */
1447 template<class ViewX, class ViewY>
1448 bool
1449 shared(ViewArray<ViewX> x, ViewArray<ViewY> y) {
1450 if ((x.size() == 0) || (y.size() == 0))
1451 return false;
1452 Region r;
1453 void** px = r.alloc<void*>(x.size());
1454 int j=0;
1455 for (int i=0; i<x.size(); i++)
1456 if (!x[i].assigned() && x[i].varimp())
1457 px[j++] = x[i].varimp();
1458 if (j == 0)
1459 return false;
1460 void** py = r.alloc<void*>(y.size());
1461 int k=0;
1462 for (int i=0; i<y.size(); i++)
1463 if (!y[i].assigned() && y[i].varimp())
1464 py[k++] = y[i].varimp();
1465 if (k == 0)
1466 return false;
1467 return Kernel::duplicates(px,j,py,k);
1468 }
1469
1470 template<class ViewX, class ViewY>
1471 bool
1472 shared(ViewArray<ViewX> x, ViewY y) {
1473 if (y.assigned() || !y.varimp())
1474 return false;
1475 for (int i=0; i<x.size(); i++)
1476 if (!x[i].assigned() && x[i].varimp() && (x[i].varimp() == y.varimp()))
1477 return true;
1478 return false;
1479 }
1480
1481 template<class ViewX, class ViewY>
1482 forceinline bool
1483 shared(ViewX x, ViewArray<ViewY> y) {
1484 return shared(y,x);
1485 }
1486
1487 template<class View>
1488 bool
1489 shared(ViewArray<View> x) {
1490 if (x.size() < 2)
1491 return false;
1492 Region r;
1493 void** px = r.alloc<void*>(x.size());
1494 int j=0;
1495 for (int i=0; i<x.size(); i++)
1496 if (!x[i].assigned() && x[i].varimp())
1497 px[j++] = x[i].varimp();
1498 return (j > 2) && Kernel::duplicates(px,j);
1499 }
1500
1501
1502
1503 /*
1504 * Argument arrays: base class
1505 *
1506 */
1507
1508 template<class T>
1509 forceinline T*
1510 ArgArrayBase<T>::allocate(int n) {
1511 return (n > onstack_size) ?
1512 heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
1513 }
1514
1515 template<class T>
1516 forceinline void
1517 ArgArrayBase<T>::resize(int i) {
1518 if (n+i >= capacity) {
1519 assert(n+i >= onstack_size);
1520 int newCapacity = (3*capacity)/2;
1521 if (newCapacity <= n+i)
1522 newCapacity = n+i;
1523 T* newA = allocate(newCapacity);
1524 heap.copy<T>(newA,a,n);
1525 if (capacity > onstack_size)
1526 heap.free(a,capacity);
1527 capacity = newCapacity;
1528 a = newA;
1529 }
1530 }
1531
1532 template<class T>
1533 forceinline
1534 ArgArrayBase<T>::ArgArrayBase(void)
1535 : n(0), capacity(onstack_size), a(allocate(0)) {}
1536
1537 template<class T>
1538 forceinline
1539 ArgArrayBase<T>::ArgArrayBase(int n0)
1540 : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
1541
1542 template<class T>
1543 inline
1544 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
1545 : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1546 heap.copy<T>(a,aa.a,n);
1547 }
1548
1549 template<class T>
1550 inline
1551 ArgArrayBase<T>::ArgArrayBase(const std::vector<T>& aa)
1552 : n(static_cast<int>(aa.size())),
1553 capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1554 heap.copy<T>(a,&aa[0],n);
1555 }
1556
1557 template<class T>
1558 inline
1559 ArgArrayBase<T>::ArgArrayBase(std::initializer_list<T> aa)
1560 : n(static_cast<int>(aa.size())),
1561 capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1562 int i=0;
1563 for (const T& x : aa)
1564 a[i++]=x;
1565 }
1566
1567 template<class T>
1568 forceinline
1569 ArgArrayBase<T>::~ArgArrayBase(void) {
1570 if (capacity > onstack_size)
1571 heap.free(a,capacity);
1572 }
1573
1574 template<class T>
1575 forceinline const ArgArrayBase<T>&
1576 ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
1577 if (&aa != this) {
1578 if (capacity > onstack_size)
1579 heap.free(a,capacity);
1580 n = aa.n;
1581 capacity = (n < onstack_size ? onstack_size : n);
1582 a = allocate(aa.n);
1583 heap.copy<T>(a,aa.a,n);
1584 }
1585 return *this;
1586 }
1587
1588 template<class T>
1589 forceinline int
1590 ArgArrayBase<T>::size(void) const {
1591 return n;
1592 }
1593
1594 template<class T>
1595 forceinline T&
1596 ArgArrayBase<T>::operator [](int i) {
1597 assert((i>=0) && (i < n));
1598 return a[i];
1599 }
1600
1601 template<class T>
1602 forceinline const T&
1603 ArgArrayBase<T>::operator [](int i) const {
1604 assert((i>=0) && (i < n));
1605 return a[i];
1606 }
1607
1608 template<class T>
1609 forceinline typename ArgArrayBase<T>::iterator
1610 ArgArrayBase<T>::begin(void) {
1611 return a;
1612 }
1613
1614 template<class T>
1615 forceinline typename ArgArrayBase<T>::const_iterator
1616 ArgArrayBase<T>::begin(void) const {
1617 return a;
1618 }
1619
1620 template<class T>
1621 forceinline typename ArgArrayBase<T>::iterator
1622 ArgArrayBase<T>::end(void) {
1623 return a+n;
1624 }
1625
1626 template<class T>
1627 forceinline typename ArgArrayBase<T>::const_iterator
1628 ArgArrayBase<T>::end(void) const {
1629 return a+n;
1630 }
1631
1632 template<class T>
1633 forceinline typename ArgArrayBase<T>::reverse_iterator
1634 ArgArrayBase<T>::rbegin(void) {
1635 return reverse_iterator(a+n);
1636 }
1637
1638 template<class T>
1639 forceinline typename ArgArrayBase<T>::const_reverse_iterator
1640 ArgArrayBase<T>::rbegin(void) const {
1641 return const_reverse_iterator(a+n);
1642 }
1643
1644 template<class T>
1645 forceinline typename ArgArrayBase<T>::reverse_iterator
1646 ArgArrayBase<T>::rend(void) {
1647 return reverse_iterator(a);
1648 }
1649
1650 template<class T>
1651 forceinline typename ArgArrayBase<T>::const_reverse_iterator
1652 ArgArrayBase<T>::rend(void) const {
1653 return const_reverse_iterator(a);
1654 }
1655
1656 template<class T> template<class A>
1657 A
1658 ArgArrayBase<T>::slice(int start, int inc, int maxN) {
1659 assert(n==0 || start < n);
1660 if (n==0 || maxN<0)
1661 maxN = n;
1662 int s;
1663 if (inc == 0)
1664 s = n-start;
1665 else if (inc > 0)
1666 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
1667 else
1668 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
1669 A r(std::min(maxN,s));
1670 for (int i=0; i<r.size(); i++, start+=inc)
1671 new (&r[i]) T(a[start]);
1672 return r;
1673 }
1674
1675 template<class T> template<class A>
1676 inline A&
1677 ArgArrayBase<T>::append(const T& x) {
1678 resize(1);
1679 new (&a[n++]) T(x);
1680 return static_cast<A&>(*this);
1681 }
1682
1683 template<class T>
1684 template<class InputIterator>
1685 inline
1686 ArgArrayBase<T>::ArgArrayBase(InputIterator first, InputIterator last)
1687 : n(0), capacity(onstack_size), a(allocate(0)) {
1688 while (first != last) {
1689 (void) append<ArgArrayBase<T>>(*first);
1690 ++first;
1691 }
1692 }
1693
1694
1695 template<class T> template<class A>
1696 inline A&
1697 ArgArrayBase<T>::append(const ArgArrayBase<T>& x) {
1698 resize(x.size());
1699 for (int i=0; i<x.size(); i++)
1700 new (&a[n++]) T(x[i]);
1701 return static_cast<A&>(*this);
1702 }
1703
1704 template<class T> template<class A>
1705 inline A
1706 ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const {
1707 A r(n+x.n);
1708 for (int i=0; i<n; i++)
1709 new (&r[i]) T(a[i]);
1710 for (int i=0; i<x.n; i++)
1711 new (&r[n+i]) T(x.a[i]);
1712 return r;
1713 }
1714
1715 template<class T> template<class A>
1716 inline A
1717 ArgArrayBase<T>::concat(const T& x) const {
1718 A r(n+1);
1719 for (int i=0; i<n; i++)
1720 new (&r[i]) T(a[i]);
1721 new (&r[n]) T(x);
1722 return r;
1723 }
1724
1725
1726 /*
1727 * Argument arrays
1728 *
1729 */
1730
1731 template<class T>
1732 forceinline
1733 ArgArray<T>::ArgArray(void) {}
1734
1735 template<class T>
1736 forceinline
1737 ArgArray<T>::ArgArray(int n)
1738 : ArgArrayBase<T>(n) {}
1739
1740 template<class T>
1741 ArgArray<T>::ArgArray(int n, const T* a0)
1742 : ArgArrayBase<T>(n) {
1743 for (int i=0; i<n; i++)
1744 a[i] = a0[i];
1745 }
1746
1747 template<class T>
1748 forceinline
1749 ArgArray<T>::ArgArray(const ArgArray<T>& aa)
1750 : ArgArrayBase<T>(aa) {}
1751
1752 template<class T>
1753 forceinline
1754 ArgArray<T>::ArgArray(const std::vector<T>& aa)
1755 : ArgArrayBase<T>(aa) {}
1756
1757 template<class T>
1758 forceinline
1759 ArgArray<T>::ArgArray(std::initializer_list<T> aa)
1760 : ArgArrayBase<T>(aa) {}
1761
1762 template<class T>
1763 template<class InputIterator>
1764 forceinline
1765 ArgArray<T>::ArgArray(InputIterator first, InputIterator last)
1766 : ArgArrayBase<T>(first,last) {}
1767
1768 template<class T>
1769 forceinline typename ArrayTraits<ArgArray<T>>::ArgsType
1770 ArgArray<T>::slice(int start, int inc, int maxN) {
1771 return ArgArrayBase<T>::template slice
1772 <typename ArrayTraits<ArgArray<T>>::ArgsType>
1773 (start,inc,maxN);
1774 }
1775
1776 template<class T>
1777 forceinline typename ArrayTraits<ArgArray<T>>::ArgsType&
1778 ArgArray<T>::operator <<(const T& x) {
1779 return
1780 ArgArrayBase<T>::template append
1781 <typename ArrayTraits<ArgArray<T>>::ArgsType>(x);
1782 }
1783
1784 template<class T>
1785 forceinline typename ArrayTraits<ArgArray<T>>::ArgsType&
1786 ArgArray<T>::operator <<(const ArgArray<T>& x) {
1787 return
1788 ArgArrayBase<T>::template append
1789 <typename ArrayTraits<ArgArray<T>>::ArgsType>(x);
1790 }
1791
1792 template<class T>
1793 typename ArrayTraits<ArgArray<T>>::ArgsType
1794 operator +(const ArgArray<T>& x, const ArgArray<T>& y) {
1795 return x.template concat
1796 <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
1797 }
1798
1799 template<class T>
1800 typename ArrayTraits<ArgArray<T>>::ArgsType
1801 operator +(const ArgArray<T>& x, const T& y) {
1802 return x.template concat
1803 <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
1804 }
1805
1806 template<class T>
1807 typename ArrayTraits<ArgArray<T>>::ArgsType
1808 operator +(const T& x, const ArgArray<T>& y) {
1809 ArgArray<T> xa(1);
1810 xa[0] = x;
1811 return xa.template concat
1812 <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
1813 }
1814
1815 /*
1816 * Argument arrays for variables
1817 *
1818 */
1819
1820 template<class Var>
1821 forceinline
1822 VarArgArray<Var>::VarArgArray(void) {}
1823
1824 template<class Var>
1825 forceinline
1826 VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {}
1827
1828 template<class Var>
1829 forceinline
1830 VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
1831 : ArgArrayBase<Var>(aa) {}
1832
1833 template<class Var>
1834 forceinline
1835 VarArgArray<Var>::VarArgArray(const std::vector<Var>& aa)
1836 : ArgArrayBase<Var>(aa) {}
1837
1838 template<class Var>
1839 forceinline
1840 VarArgArray<Var>::VarArgArray(std::initializer_list<Var> aa)
1841 : ArgArrayBase<Var>(aa) {}
1842
1843 template<class Var>
1844 template<class InputIterator>
1845 forceinline
1846 VarArgArray<Var>::VarArgArray(InputIterator first, InputIterator last)
1847 : ArgArrayBase<Var>(first,last) {}
1848
1849 template<class Var>
1850 inline
1851 VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
1852 : ArgArrayBase<Var>(x.size()) {
1853 for (int i=0; i<x.size(); i++)
1854 a[i]=x[i];
1855 }
1856
1857 template<class Var>
1858 forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType
1859 VarArgArray<Var>::slice(int start, int inc, int maxN) {
1860 return ArgArrayBase<Var>::template slice
1861 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>
1862 (start,inc,maxN);
1863 }
1864
1865 template<class Var>
1866 forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType&
1867 VarArgArray<Var>::operator <<(const Var& x) {
1868 return
1869 ArgArrayBase<Var>::template append
1870 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x);
1871 }
1872
1873 template<class Var>
1874 forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType&
1875 VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) {
1876 return
1877 ArgArrayBase<Var>::template append
1878 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x);
1879 }
1880
1881 template<class Var>
1882 typename ArrayTraits<VarArgArray<Var>>::ArgsType
1883 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) {
1884 return x.template concat
1885 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
1886 }
1887
1888 template<class Var>
1889 typename ArrayTraits<VarArgArray<Var>>::ArgsType
1890 operator +(const VarArgArray<Var>& x, const Var& y) {
1891 return x.template concat
1892 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
1893 }
1894
1895 template<class Var>
1896 typename ArrayTraits<VarArgArray<Var>>::ArgsType
1897 operator +(const Var& x, const VarArgArray<Var>& y) {
1898 VarArgArray<Var> xa(1);
1899 xa[0] = x;
1900 return xa.template concat
1901 <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
1902 }
1903
1904 template<class Var>
1905 forceinline bool
1906 VarArgArray<Var>::assigned(void) const {
1907 for (int i=0; i<n; i++)
1908 if (!a[i].assigned())
1909 return false;
1910 return true;
1911 }
1912
1913
1914 /*
1915 * Checking for multiple occurences of the same variable
1916 *
1917 */
1918 template<class Var>
1919 bool
1920 same(VarArgArray<Var> x, VarArgArray<Var> y) {
1921 if ((x.size() == 0) || (y.size() == 0))
1922 return false;
1923 Region r;
1924 void** px = r.alloc<void*>(x.size());
1925 int j=0;
1926 for (int i=0; i<x.size(); i++)
1927 if (!x[i].assigned())
1928 px[j++] = x[i].varimp();
1929 if (j == 0)
1930 return false;
1931 void** py = r.alloc<void*>(y.size());
1932 int k=0;
1933 for (int i=0; i<y.size(); i++)
1934 if (!y[i].assigned())
1935 py[k++] = y[i].varimp();
1936 if (k == 0)
1937 return false;
1938 return Kernel::duplicates(px,j,py,k);
1939 }
1940
1941 template<class Var>
1942 bool
1943 same(VarArgArray<Var> x, Var y) {
1944 if (y.assigned())
1945 return false;
1946 for (int i=0; i<x.size(); i++)
1947 if (x[i].varimp() == y.varimp())
1948 return true;
1949 return false;
1950 }
1951
1952 template<class Var>
1953 forceinline bool
1954 same(Var x, VarArgArray<Var> y) {
1955 return same(y,x);
1956 }
1957
1958 template<class Var>
1959 bool
1960 same(VarArgArray<Var> x) {
1961 if (x.size() < 2)
1962 return false;
1963 Region r;
1964 void** px = r.alloc<void*>(x.size());
1965 int j=0;
1966 for (int i=0; i<x.size(); i++)
1967 if (!x[i].assigned())
1968 px[j++] = x[i].varimp();
1969 return (j > 1) && Kernel::duplicates(px,j);
1970 }
1971
1972
1973
1974 /*
1975 * Interdependent code
1976 *
1977 */
1978
1979 template<class Var>
1980 inline
1981 VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
1982 : n(a.size()) {
1983 if (n>0) {
1984 x = home.alloc<Var>(n);
1985 for (int i=0; i<n; i++)
1986 x[i] = a[i];
1987 } else {
1988 x = nullptr;
1989 }
1990 }
1991
1992
1993 /*
1994 * Printing of arrays
1995 *
1996 */
1997 template<class Char, class Traits, class Var>
1998 std::basic_ostream<Char,Traits>&
1999 operator <<(std::basic_ostream<Char,Traits>& os,
2000 const VarArray<Var>& x) {
2001 std::basic_ostringstream<Char,Traits> s;
2002 s.copyfmt(os); s.width(0);
2003 s << '{';
2004 if (x.size() > 0) {
2005 s << x[0];
2006 for (int i=1; i<x.size(); i++)
2007 s << ", " << x[i];
2008 }
2009 s << '}';
2010 return os << s.str();
2011 }
2012
2013 template<class Char, class Traits, class View>
2014 std::basic_ostream<Char,Traits>&
2015 operator <<(std::basic_ostream<Char,Traits>& os,
2016 const ViewArray<View>& x) {
2017 std::basic_ostringstream<Char,Traits> s;
2018 s.copyfmt(os); s.width(0);
2019 s << '{';
2020 if (x.size() > 0) {
2021 s << x[0];
2022 for (int i=1; i<x.size(); i++)
2023 s << ", " << x[i];
2024 }
2025 s << '}';
2026 return os << s.str();
2027 }
2028
2029 template<class Char, class Traits, class T>
2030 std::basic_ostream<Char,Traits>&
2031 operator <<(std::basic_ostream<Char,Traits>& os,
2032 const ArgArrayBase<T>& x) {
2033 std::basic_ostringstream<Char,Traits> s;
2034 s.copyfmt(os); s.width(0);
2035 s << '{';
2036 if (x.size() > 0) {
2037 s << x[0];
2038 for (int i=1; i<x.size(); i++)
2039 s << ", " << x[i];
2040 }
2041 s << '}';
2042 return os << s.str();
2043 }
2044
2045}
2046
2047// STATISTICS: kernel-other