Generated on Tue Jan 28 2020 00:00:00 for Gecode by doxygen 1.8.17
array.hpp
Go to the documentation of this file.
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  * Last modified:
16  * $Date: 2016-09-25 21:42:04 +0200 (Sun, 25 Sep 2016) $ by $Author: schulte $
17  * $Revision: 15170 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <cstdarg>
45 #include <iostream>
46 #include <iterator>
47 #include <vector>
48 #include <sstream>
49 
50 namespace Gecode {
51 
52  template<class Var> class VarArray;
53  template<class Var> class VarArgArray;
54 
67  template<class A>
68  class ArrayTraits {};
69 
85  template<class Var>
86  class VarArray {
87  protected:
89  int n;
91  Var* x;
92  public:
94 
95  typedef Var value_type;
98  typedef Var& reference;
100  typedef const Var& const_reference;
102  typedef Var* pointer;
104  typedef const Var* const_pointer;
106  typedef Var* iterator;
108  typedef const Var* const_iterator;
110  typedef std::reverse_iterator<Var*> reverse_iterator;
112  typedef std::reverse_iterator<const Var*> const_reverse_iterator;
114 
116 
118  VarArray(void);
121  VarArray(Space& home, int m);
123  VarArray(Space& home, const VarArgArray<Var>&);
125  VarArray(const VarArray<Var>& a);
127  const VarArray<Var>& operator =(const VarArray<Var>& a);
129 
131 
132  int size(void) const;
135 
137 
138  Var& operator [](int i);
141  const Var& operator [](int i) const;
147  typename ArrayTraits<VarArgArray<Var> >::ArgsType
148  slice(int start, int inc=1, int n=-1);
150 
152 
153  iterator begin(void);
156  const_iterator begin(void) const;
158  iterator end(void);
160  const_iterator end(void) const;
162  reverse_iterator rbegin(void);
164  const_reverse_iterator rbegin(void) const;
166  reverse_iterator rend(void);
168  const_reverse_iterator rend(void) const;
170 
172  bool assigned(void) const;
173 
175 
176 
183  void update(Space&, bool share, VarArray<Var>& a);
185  private:
186  static void* operator new(size_t) throw();
187  static void operator delete(void*,size_t);
188  };
189 
193  template<class T>
194  typename ArrayTraits<VarArray<T> >::ArgsType
195  operator +(const VarArray<T>& x, const VarArgArray<T>& y);
196 
200  template<class T>
201  typename ArrayTraits<VarArray<T> >::ArgsType
202  operator +(const VarArray<T>& x, const VarArray<T>& y);
203 
207  template<class T>
208  typename ArrayTraits<VarArray<T> >::ArgsType
209  operator +(const VarArgArray<T>& x, const VarArray<T>& y);
210 
214  template<class T>
215  typename ArrayTraits<VarArray<T> >::ArgsType
216  operator +(const VarArray<T>& x, const T& y);
217 
221  template<class T>
222  typename ArrayTraits<VarArray<T> >::ArgsType
223  operator +(const T& x, const VarArray<T>& y);
224 
233  template<class View>
234  class ViewArray {
235  private:
237  int n;
239  View* x;
241  template<class X>
242  class ViewLess {
243  public:
244  bool operator ()(const X&, const X&);
245  };
247  static void sort(View* x, int n);
248  public:
250 
251  typedef View value_type;
254  typedef View& reference;
256  typedef const View& const_reference;
258  typedef View* pointer;
260  typedef const View* const_pointer;
262  typedef View* iterator;
264  typedef const View* const_iterator;
266  typedef std::reverse_iterator<View*> reverse_iterator;
268  typedef std::reverse_iterator<const View*> const_reverse_iterator;
270 
272 
273  ViewArray(void);
276  ViewArray(Space& home, int m);
278  ViewArray(Region& r, int m);
280  ViewArray(const ViewArray<View>& a);
282  ViewArray(Space& home, const ViewArray<View>& a);
284  ViewArray(Region& r, const ViewArray<View>& a);
293  template<class Var>
295  : n(a.size()) {
296  // This may not be in the hpp file (to satisfy the MS compiler)
297  if (n>0) {
298  x = home.alloc<View>(n);
299  for (int i=n; i--; )
300  x[i]=a[i];
301  } else {
302  x = NULL;
303  }
304  }
311  template<class Var>
313  : n(a.size()) {
314  // This may not be in the hpp file (to satisfy the MS compiler)
315  if (n>0) {
316  x = r.alloc<View>(n);
317  for (int i=n; i--; )
318  x[i]=a[i];
319  } else {
320  x = NULL;
321  }
322  }
324 
326 
327  int size(void) const;
330  void size(int n);
332 
334 
335  View& operator [](int i);
338  const View& operator [](int i) const;
340 
342 
343  iterator begin(void);
346  const_iterator begin(void) const;
348  iterator end(void);
350  const_iterator end(void) const;
352  reverse_iterator rbegin(void);
354  const_reverse_iterator rbegin(void) const;
356  reverse_iterator rend(void);
358  const_reverse_iterator rend(void) const;
360 
362 
363 
370  void subscribe(Space& home, Propagator& p, PropCond pc,
371  bool schedule=true);
373  void cancel(Space& home, Propagator& p, PropCond pc);
375  void subscribe(Space& home, Advisor& a);
377  void cancel(Space& home, Advisor& a);
379  void reschedule(Space& home, Propagator& p, PropCond pc);
381 
383 
384 
391  void update(Space&, bool share, ViewArray<View>& a);
393 
394 
396 
397  void move_fst(int i);
400  void move_lst(int i);
406  void move_fst(int i, Space& home, Propagator& p, PropCond pc);
412  void move_lst(int i, Space& home, Propagator& p, PropCond pc);
418  void move_fst(int i, Space& home, Advisor& a);
424  void move_lst(int i, Space& home, Advisor& a);
426 
428 
429  void drop_fst(int i);
432  void drop_lst(int i);
438  void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
445  void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
451  void drop_fst(int i, Space& home, Advisor& a);
457  void drop_lst(int i, Space& home, Advisor& a);
459 
461  bool assigned(void) const;
462 
464 
465 
470  bool same(const Space& home) const;
476  bool same(const Space& home, const View& y) const;
478  void unique(const Space& home);
480 
482 
483 
488  bool shared(const Space& home) const;
494  template<class ViewY>
495  bool shared(const Space& home, const ViewY& y) const;
501  template<class ViewY>
502  bool shared(const Space& home, const ViewArray<ViewY>& y) const;
504 
505  private:
506  static void* operator new(size_t) throw();
507  static void operator delete(void*,size_t);
508  };
509 
523  template<class T>
524  class ArgArrayBase {
525  protected:
527  int n;
529  int capacity;
531  T* a;
533  static const int onstack_size = 16;
537  T* allocate(int n);
539  void resize(int i);
541  template<class A>
542  A concat(const ArgArrayBase<T>& x) const;
544  template<class A>
545  A concat(const T& x) const;
547  template<class A>
548  A& append(const T& x);
550  template<class A>
551  A& append(const ArgArrayBase<T>& x);
557  template<class A>
558  A slice(int start, int inc=1, int n=-1);
559  public:
561 
562  typedef T value_type;
565  typedef T& reference;
567  typedef const T& const_reference;
569  typedef T* pointer;
571  typedef const T* const_pointer;
573  typedef T* iterator;
575  typedef const T* const_iterator;
577  typedef std::reverse_iterator<T*> reverse_iterator;
579  typedef std::reverse_iterator<const T*> const_reverse_iterator;
581 
583 
584  ArgArrayBase(void);
587  explicit ArgArrayBase(int n);
593  ArgArrayBase(const std::vector<T>& a);
595  template<class InputIterator>
596  ArgArrayBase(InputIterator first, InputIterator last);
598 
600 
601  int size(void) const;
604 
606 
607  T& operator [](int i);
610  const T& operator [](int i) const;
612 
614 
615  iterator begin(void);
618  const_iterator begin(void) const;
620  iterator end(void);
622  const_iterator end(void) const;
624  reverse_iterator rbegin(void);
626  const_reverse_iterator rbegin(void) const;
628  reverse_iterator rend(void);
630  const_reverse_iterator rend(void) const;
632 
634 
635  ~ArgArrayBase(void);
638  };
639 
640  template<class> class PrimArgArray;
641 
645  template<class T>
646  typename ArrayTraits<PrimArgArray<T> >::ArgsType
647  operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
648 
652  template<class T>
653  typename ArrayTraits<PrimArgArray<T> >::ArgsType
654  operator +(const PrimArgArray<T>& x, const T& y);
655 
659  template<class T>
660  typename ArrayTraits<PrimArgArray<T> >::ArgsType
661  operator +(const T& x, const PrimArgArray<T>& y);
662 
674  template<class T>
675  class PrimArgArray : public ArgArrayBase<T> {
676  protected:
677  using ArgArrayBase<T>::a;
678  public:
679  using ArgArrayBase<T>::size;
681 
682  PrimArgArray(void);
685  explicit PrimArgArray(int n);
687  PrimArgArray(int n, T e0, ...);
689  PrimArgArray(int n, const T* e);
693  PrimArgArray(const std::vector<T>& a);
695  template<class InputIterator>
696  PrimArgArray(InputIterator first, InputIterator last);
698 
700 
705  typename ArrayTraits<PrimArgArray<T> >::ArgsType
706  slice(int start, int inc=1, int n=-1);
708 
710  typename ArrayTraits<PrimArgArray<T> >::ArgsType&
712  operator <<(const T& x);
714  typename ArrayTraits<PrimArgArray<T> >::ArgsType&
715  operator <<(const PrimArgArray<T>& x);
717 
718  friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
719  operator + <>(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
720  friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
721  operator + <>(const PrimArgArray<T>& x, const T& y);
722  friend
723  typename ArrayTraits<PrimArgArray<T> >::ArgsType
724  operator + <>(const T& x, const PrimArgArray<T>& y);
725  };
726 
727  template<class> class ArgArray;
728 
732  template<class T>
733  typename ArrayTraits<ArgArray<T> >::ArgsType
734  operator +(const ArgArray<T>& x, const ArgArray<T>& y);
735 
739  template<class T>
740  typename ArrayTraits<ArgArray<T> >::ArgsType
741  operator +(const ArgArray<T>& x, const T& y);
742 
746  template<class T>
747  typename ArrayTraits<ArgArray<T> >::ArgsType
748  operator +(const T& x, const ArgArray<T>& y);
749 
761  template<class T>
762  class ArgArray : public ArgArrayBase<T> {
763  protected:
764  using ArgArrayBase<T>::a;
765  public:
766  using ArgArrayBase<T>::size;
768 
769  ArgArray(void);
772  explicit ArgArray(int n);
774  ArgArray(int n, const T* e);
776  ArgArray(const ArgArray<T>& a);
778  ArgArray(const std::vector<T>& a);
780  template<class InputIterator>
781  ArgArray(InputIterator first, InputIterator last);
783 
785  typename ArrayTraits<ArgArray<T> >::ArgsType
787  slice(int start, int inc=1, int n=-1);
789 
791  typename ArrayTraits<ArgArray<T> >::ArgsType&
793  operator <<(const T& x);
795  typename ArrayTraits<ArgArray<T> >::ArgsType&
796  operator <<(const ArgArray<T>& x);
798 
799  friend typename ArrayTraits<ArgArray<T> >::ArgsType
800  operator + <>(const ArgArray<T>& x, const ArgArray<T>& y);
801  friend typename ArrayTraits<ArgArray<T> >::ArgsType
802  operator + <>(const ArgArray<T>& x, const T& y);
803  friend
804  typename ArrayTraits<ArgArray<T> >::ArgsType
805  operator + <>(const T& x, const ArgArray<T>& y);
806  };
807 
808  template<class> class VarArgArray;
809 
813  template<class Var>
814  typename ArrayTraits<VarArgArray<Var> >::ArgsType
816 
820  template<class Var>
821  typename ArrayTraits<VarArgArray<Var> >::ArgsType
822  operator +(const VarArgArray<Var>& x, const Var& y);
823 
827  template<class Var>
828  typename ArrayTraits<VarArgArray<Var> >::ArgsType
829  operator +(const Var& x, const VarArgArray<Var>& y);
830 
842  template<class Var>
843  class VarArgArray : public ArgArrayBase<Var> {
844  protected:
845  using ArgArrayBase<Var>::a;
846  using ArgArrayBase<Var>::n;
848  class VarLess {
849  public:
850  bool operator ()(const Var&, const Var&);
851  };
852  public:
855 
856  VarArgArray(void);
859  explicit VarArgArray(int n);
863  VarArgArray(const VarArray<Var>& a);
865  VarArgArray(const std::vector<Var>& a);
867  template<class InputIterator>
868  VarArgArray(InputIterator first, InputIterator last);
870 
872  typename ArrayTraits<VarArgArray<Var> >::ArgsType
874  slice(int start, int inc=1, int n=-1);
876 
878  typename ArrayTraits<VarArgArray<Var> >::ArgsType&
880  operator <<(const Var& x);
882  typename ArrayTraits<VarArgArray<Var> >::ArgsType&
885 
887  bool assigned(void) const;
888 
889  friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
890  operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
891  friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
892  operator + <>(const VarArgArray<Var>& x, const Var& y);
893  friend
894  typename ArrayTraits<VarArgArray<Var> >::ArgsType
895  operator + <>(const Var& x, const VarArgArray<Var>& y);
896 
898 
899 
904  bool same(const Space& home) const;
910  bool same(const Space& home, const Var& y) const;
916  bool same(const Space& home, const VarArgArray<Var>& y) const;
918  };
919 
924  template<class Char, class Traits, class Var>
925  std::basic_ostream<Char,Traits>&
926  operator <<(std::basic_ostream<Char,Traits>& os,
927  const VarArray<Var>& x);
928 
933  template<class Char, class Traits, class View>
934  std::basic_ostream<Char,Traits>&
935  operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
936 
941  template<class Char, class Traits, class T>
942  std::basic_ostream<Char,Traits>&
943  operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
944 
945 
946  /*
947  * Implementation
948  *
949  */
950 
951  /*
952  * Variable arrays
953  *
954  * These arrays are allocated in the space.
955  *
956  */
957 
958  template<class Var>
960  VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
961 
962  template<class Var>
965  : n(n0) {
966  // Allocate from space
967  x = (n>0) ? home.alloc<Var>(n) : NULL;
968  }
969 
970  template<class Var>
973  n = a.n; x = a.x;
974  }
975 
976  template<class Var>
977  inline const VarArray<Var>&
979  n = a.n; x = a.x;
980  return *this;
981  }
982 
983  template<class Var>
984  forceinline int
985  VarArray<Var>::size(void) const {
986  return n;
987  }
988 
989  template<class Var>
992  assert((i >= 0) && (i < size()));
993  return x[i];
994  }
995 
996  template<class Var>
997  forceinline const Var&
999  assert((i >= 0) && (i < size()));
1000  return x[i];
1001  }
1002 
1003  template<class Var>
1004  typename ArrayTraits<VarArgArray<Var> >::ArgsType
1005  VarArray<Var>::slice(int start, int inc, int maxN) {
1006  assert(n==0 || start < n);
1007  if (n==0 || maxN<0)
1008  maxN = n;
1009  int s;
1010  if (inc == 0)
1011  s = n-start;
1012  else if (inc > 0)
1013  s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
1014  else
1015  s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
1016  typename ArrayTraits<VarArgArray<Var> >::ArgsType r(std::min(maxN,s));
1017  for (int i=0; i<r.size(); i++, start+=inc)
1018  r[i] = x[start];
1019  return r;
1020  }
1021 
1022  template<class Var>
1025  return x;
1026  }
1027 
1028  template<class Var>
1030  VarArray<Var>::begin(void) const {
1031  return x;
1032  }
1033 
1034  template<class Var>
1037  return x+n;
1038  }
1039 
1040  template<class Var>
1042  VarArray<Var>::end(void) const {
1043  return x+n;
1044  }
1045 
1046  template<class Var>
1049  return reverse_iterator(x+n);
1050  }
1051 
1052  template<class Var>
1055  return const_reverse_iterator(x+n);
1056  }
1057 
1058  template<class Var>
1061  return reverse_iterator(x);
1062  }
1063 
1064  template<class Var>
1066  VarArray<Var>::rend(void) const {
1067  return const_reverse_iterator(x);
1068  }
1069 
1070  template<class Var>
1071  forceinline void
1073  n = a.n;
1074  if (n > 0) {
1075  x = home.alloc<Var>(n);
1076  for (int i = n; i--;)
1077  x[i].update(home, share, a.x[i]);
1078  } else {
1079  x = NULL;
1080  }
1081  }
1082 
1083  template<class Var>
1084  forceinline bool
1086  for (int i = n; i--;)
1087  if (!x[i].assigned())
1088  return false;
1089  return true;
1090  }
1091 
1092  template<class Var>
1093  forceinline void*
1094  VarArray<Var>::operator new(size_t) throw() {
1095  return NULL;
1096  }
1097 
1098  template<class Var>
1099  forceinline void
1100  VarArray<Var>::operator delete(void*,size_t) {
1101  }
1102 
1103  template<class Var>
1104  typename ArrayTraits<VarArray<Var> >::ArgsType
1106  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1107  for (int i=x.size(); i--;)
1108  r[i] = x[i];
1109  for (int i=y.size(); i--;)
1110  r[x.size()+i] = y[i];
1111  return r;
1112  }
1113 
1114  template<class Var>
1115  typename ArrayTraits<VarArray<Var> >::ArgsType
1117  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1118  for (int i=x.size(); i--;)
1119  r[i] = x[i];
1120  for (int i=y.size(); i--;)
1121  r[x.size()+i] = y[i];
1122  return r;
1123  }
1124 
1125  template<class Var>
1126  typename ArrayTraits<VarArray<Var> >::ArgsType
1128  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1129  for (int i=x.size(); i--;)
1130  r[i] = x[i];
1131  for (int i=y.size(); i--;)
1132  r[x.size()+i] = y[i];
1133  return r;
1134  }
1135 
1136  template<class Var>
1137  typename ArrayTraits<VarArray<Var> >::ArgsType
1138  operator +(const VarArray<Var>& x, const Var& y) {
1139  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+1);
1140  for (int i=x.size(); i--;)
1141  r[i] = x[i];
1142  r[x.size()] = y;
1143  return r;
1144  }
1145 
1146  template<class Var>
1147  typename ArrayTraits<VarArray<Var> >::ArgsType
1148  operator +(const Var& x, const VarArray<Var>& y) {
1149  typename ArrayTraits<VarArray<Var> >::ArgsType r(y.size()+1);
1150  r[0] = x;
1151  for (int i=y.size(); i--;)
1152  r[1+i] = y[i];
1153  return r;
1154  }
1155 
1156  /*
1157  * View arrays
1158  *
1159  */
1160 
1161  template<class View>
1162  forceinline
1163  ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
1164 
1165  template<class View>
1166  forceinline
1168  : n(n0) {
1169  x = (n>0) ? home.alloc<View>(n) : NULL;
1170  }
1171  template<class View>
1172  forceinline
1174  : n(n0) {
1175  x = (n>0) ? r.alloc<View>(n) : NULL;
1176  }
1177 
1178  template<class View>
1180  : n(a.size()) {
1181  if (n>0) {
1182  x = home.alloc<View>(n);
1183  for (int i = n; i--; )
1184  x[i] = a[i];
1185  } else {
1186  x = NULL;
1187  }
1188  }
1189  template<class View>
1191  : n(a.size()) {
1192  if (n>0) {
1193  x = r.alloc<View>(n);
1194  for (int i = n; i--; )
1195  x[i] = a[i];
1196  } else {
1197  x = NULL;
1198  }
1199  }
1200 
1201  template<class View>
1202  forceinline
1204  : n(a.n), x(a.x) {}
1205 
1206  template<class View>
1209  n = a.n; x = a.x;
1210  return *this;
1211  }
1212 
1213  template<class View>
1214  forceinline int
1216  return n;
1217  }
1218 
1219  template<class View>
1220  forceinline void
1222  n = n0;
1223  }
1224 
1225  template<class View>
1226  forceinline View&
1228  assert((i >= 0) && (i < size()));
1229  return x[i];
1230  }
1231 
1232  template<class View>
1233  forceinline const View&
1235  assert((i >= 0) && (i < size()));
1236  return x[i];
1237  }
1238 
1239  template<class View>
1242  return x;
1243  }
1244 
1245  template<class View>
1248  return x;
1249  }
1250 
1251  template<class View>
1254  return x+n;
1255  }
1256 
1257  template<class View>
1259  ViewArray<View>::end(void) const {
1260  return x+n;
1261  }
1262 
1263  template<class View>
1266  return reverse_iterator(x+n);
1267  }
1268 
1269  template<class View>
1272  return const_reverse_iterator(x+n);
1273  }
1274 
1275  template<class View>
1278  return reverse_iterator(x);
1279  }
1280 
1281  template<class View>
1284  return const_reverse_iterator(x);
1285  }
1286 
1287  template<class View>
1288  forceinline void
1290  x[i]=x[0]; x++; n--;
1291  }
1292 
1293  template<class View>
1294  forceinline void
1296  n--; x[i]=x[n];
1297  }
1298 
1299  template<class View>
1300  forceinline void
1302  assert(i>=0);
1303  x += i; n -= i;
1304  }
1305 
1306  template<class View>
1307  forceinline void
1309  assert(i<n);
1310  n = i+1;
1311  }
1312 
1313  template<class View>
1314  forceinline void
1316  // Move x[0] to x[i]
1317  x[i].cancel(home,p,pc);
1318  x[i]=x[0]; x++; n--;
1319  }
1320 
1321  template<class View>
1322  forceinline void
1324  // Move x[n-1] to x[i]
1325  x[i].cancel(home,p,pc);
1326  n--; x[i]=x[n];
1327  }
1328 
1329  template<class View>
1330  void
1332  // Drop elements from 0..i-1
1333  assert(i>=0);
1334  for (int j=i; j--; )
1335  x[j].cancel(home,p,pc);
1336  x += i; n -= i;
1337  }
1338 
1339  template<class View>
1340  void
1342  // Drop elements from i+1..n-1
1343  assert(i<n);
1344  for (int j=i+1; j<n; j++)
1345  x[j].cancel(home,p,pc);
1346  n = i+1;
1347  }
1348 
1349  template<class View>
1350  forceinline void
1352  // Move x[0] to x[i]
1353  x[i].cancel(home,a);
1354  x[i]=x[0]; x++; n--;
1355  }
1356 
1357  template<class View>
1358  forceinline void
1360  // Move x[n-1] to x[i]
1361  x[i].cancel(home,a);
1362  n--; x[i]=x[n];
1363  }
1364 
1365  template<class View>
1366  void
1368  // Drop elements from 0..i-1
1369  assert(i>=0);
1370  for (int j=i; j--; )
1371  x[j].cancel(home,a);
1372  x += i; n -= i;
1373  }
1374 
1375  template<class View>
1376  void
1378  // Drop elements from i+1..n-1
1379  assert(i<n);
1380  for (int j=i+1; j<n; j++)
1381  x[j].cancel(home,a);
1382  n = i+1;
1383  }
1384 
1385  template<class View>
1386  void
1388  n = y.n;
1389  if (n > 0) {
1390  x = home.alloc<View>(n);
1391  for (int i = n; i--; )
1392  x[i].update(home, share, y.x[i]);
1393  } else {
1394  x = NULL;
1395  }
1396  }
1397 
1398  template<class View>
1399  void
1401  bool schedule) {
1402  for (int i = n; i--; )
1403  x[i].subscribe(home,p,pc,schedule);
1404  }
1405 
1406  template<class View>
1407  void
1409  for (int i = n; i--; )
1410  x[i].cancel(home,p,pc);
1411  }
1412 
1413  template<class View>
1414  void
1416  for (int i = n; i--; )
1417  x[i].subscribe(home,a);
1418  }
1419 
1420  template<class View>
1421  void
1423  for (int i = n; i--; )
1424  x[i].cancel(home,a);
1425  }
1426 
1427  template<class View>
1428  void
1430  for (int i = n; i--; )
1431  x[i].reschedule(home,p,pc);
1432  }
1433 
1434  template<class View>
1435  forceinline bool
1437  for (int i = n; i--;)
1438  if (!x[i].assigned())
1439  return false;
1440  return true;
1441  }
1442 
1443  template<class View>
1444  forceinline bool
1445  __before(const View& x, const View& y) {
1446  return before(x,y);
1447  }
1448 
1449  template<class View> template<class X>
1450  forceinline bool
1451  ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
1452  return __before(a,b);
1453  }
1454 
1455  template<class View>
1456  void
1457  ViewArray<View>::sort(View* y, int m) {
1458  ViewLess<View> vl;
1459  Support::quicksort<View,ViewLess<View> >(y,m,vl);
1460  }
1461 
1462  template<class X, class Y>
1463  forceinline bool
1464  __same(const X& x, const Y& y) {
1465  return same(x,y);
1466  }
1467  template<class X, class Y>
1468  forceinline bool
1469  __shared(const X& x, const Y& y) {
1470  return shared(x,y);
1471  }
1472 
1473  template<class View>
1474  bool
1475  ViewArray<View>::same(const Space& home) const {
1476  if (n < 2)
1477  return false;
1478  Region r(home);
1479  View* y = r.alloc<View>(n);
1480  for (int i = n; i--; )
1481  y[i] = x[i];
1482  sort(y,n);
1483  for (int i = n-1; i--; )
1484  if (!y[i].assigned() && __same(y[i+1],y[i])) {
1485  r.free<View>(y,n);
1486  return true;
1487  }
1488  r.free<View>(y,n);
1489  return false;
1490  }
1491 
1492  template<class View>
1493  bool
1494  ViewArray<View>::same(const Space&, const View& y) const {
1495  if (y.assigned())
1496  return false;
1497  for (int i = n; i--; )
1498  if (__same(x[i],y))
1499  return true;
1500  return false;
1501  }
1502 
1503  template<class View>
1504  void
1506  if (n < 2)
1507  return;
1508  sort(x,n);
1509  int j = 0;
1510  for (int i = 1; i<n; i++)
1511  if (!__same(x[j],x[i]))
1512  x[++j] = x[i];
1513  n = j+1;
1514  }
1515 
1516  template<class View>
1517  bool
1518  ViewArray<View>::shared(const Space& home) const {
1519  if (n < 2)
1520  return false;
1521  Region r(home);
1522  View* y = r.alloc<View>(n);
1523  for (int i = n; i--; )
1524  y[i] = x[i];
1525  sort(y,n);
1526  for (int i = n-1; i--; )
1527  if (!y[i].assigned() && __shared(y[i+1],y[i])) {
1528  r.free<View>(y,n);
1529  return true;
1530  }
1531  r.free<View>(y,n);
1532  return false;
1533  }
1534 
1535  template<class View> template<class ViewY>
1536  bool
1537  ViewArray<View>::shared(const Space&, const ViewY& y) const {
1538  if (y.assigned())
1539  return false;
1540  for (int i = n; i--; )
1541  if (!x[i].assigned() && __shared(x[i],y))
1542  return true;
1543  return false;
1544  }
1545 
1546  template<class View> template<class ViewY>
1547  bool
1548  ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
1549  if ((size() < 1) || (y.size() < 1))
1550  return false;
1551  Region r(home);
1552  View* xs = r.alloc<View>(size());
1553  for (int i=size(); i--; )
1554  xs[i] = x[i];
1555  ViewLess<View> xvl;
1556  Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
1557  ViewY* ys = r.alloc<ViewY>(y.size());
1558  for (int j=y.size(); j--; )
1559  ys[j] = y[j];
1560  ViewLess<ViewY> yvl;
1561  Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
1562  {
1563  int i=0, j=0;
1564  while ((i < size()) && (j < y.size()))
1565  if (!x[i].assigned() && __shared(x[i],y[j])) {
1566  r.free<View>(xs,size());
1567  r.free<ViewY>(ys,y.size());
1568  return true;
1569  } else if (before(x[i],y[j])) {
1570  i++;
1571  } else {
1572  j++;
1573  }
1574  }
1575  r.free<View>(xs,size());
1576  r.free<ViewY>(ys,y.size());
1577  return false;
1578  }
1579 
1580  template<class View>
1581  forceinline void*
1582  ViewArray<View>::operator new(size_t) throw() {
1583  return NULL;
1584  }
1585 
1586  template<class View>
1587  forceinline void
1588  ViewArray<View>::operator delete(void*,size_t) {
1589  }
1590 
1591 
1592  /*
1593  * Argument arrays: base class
1594  *
1595  */
1596 
1597  template<class T>
1598  forceinline T*
1600  return (n > onstack_size) ?
1601  heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
1602  }
1603 
1604  template<class T>
1605  forceinline void
1607  if (n+i >= capacity) {
1608  assert(n+i >= onstack_size);
1609  int newCapacity = (3*capacity)/2;
1610  if (newCapacity <= n+i)
1611  newCapacity = n+i;
1612  T* newA = allocate(newCapacity);
1613  heap.copy<T>(newA,a,n);
1614  if (capacity > onstack_size)
1615  heap.free(a,capacity);
1616  capacity = newCapacity;
1617  a = newA;
1618  }
1619  }
1620 
1621  template<class T>
1622  forceinline
1624  : n(0), capacity(onstack_size), a(allocate(0)) {}
1625 
1626  template<class T>
1627  forceinline
1629  : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
1630 
1631  template<class T>
1632  inline
1634  : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1635  heap.copy<T>(a,aa.a,n);
1636  }
1637 
1638  template<class T>
1639  inline
1640  ArgArrayBase<T>::ArgArrayBase(const std::vector<T>& aa)
1641  : n(static_cast<int>(aa.size())),
1642  capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1643  heap.copy<T>(a,&aa[0],n);
1644  }
1645 
1646  template<class T>
1647  forceinline
1649  if (capacity > onstack_size)
1650  heap.free(a,capacity);
1651  }
1652 
1653  template<class T>
1656  if (&aa != this) {
1657  if (capacity > onstack_size)
1658  heap.free(a,capacity);
1659  n = aa.n;
1660  capacity = (n < onstack_size ? onstack_size : n);
1661  a = allocate(aa.n);
1662  heap.copy<T>(a,aa.a,n);
1663  }
1664  return *this;
1665  }
1666 
1667  template<class T>
1668  forceinline int
1670  return n;
1671  }
1672 
1673  template<class T>
1674  forceinline T&
1676  assert((i>=0) && (i < n));
1677  return a[i];
1678  }
1679 
1680  template<class T>
1681  forceinline const T&
1683  assert((i>=0) && (i < n));
1684  return a[i];
1685  }
1686 
1687  template<class T>
1690  return a;
1691  }
1692 
1693  template<class T>
1696  return a;
1697  }
1698 
1699  template<class T>
1702  return a+n;
1703  }
1704 
1705  template<class T>
1707  ArgArrayBase<T>::end(void) const {
1708  return a+n;
1709  }
1710 
1711  template<class T>
1714  return reverse_iterator(a+n);
1715  }
1716 
1717  template<class T>
1720  return const_reverse_iterator(a+n);
1721  }
1722 
1723  template<class T>
1726  return reverse_iterator(a);
1727  }
1728 
1729  template<class T>
1732  return const_reverse_iterator(a);
1733  }
1734 
1735  template<class T> template<class A>
1736  A
1737  ArgArrayBase<T>::slice(int start, int inc, int maxN) {
1738  assert(n==0 || start < n);
1739  if (n==0 || maxN<0)
1740  maxN = n;
1741  int s;
1742  if (inc == 0)
1743  s = n-start;
1744  else if (inc > 0)
1745  s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
1746  else
1747  s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
1748  A r(std::min(maxN,s));
1749  for (int i=0; i<r.size(); i++, start+=inc)
1750  new (&r[i]) T(a[start]);
1751  return r;
1752  }
1753 
1754  template<class T> template<class A>
1755  inline A&
1757  resize(1);
1758  new (&a[n++]) T(x);
1759  return static_cast<A&>(*this);
1760  }
1761 
1762  template<class T>
1763  template<class InputIterator>
1764  inline
1765  ArgArrayBase<T>::ArgArrayBase(InputIterator first, InputIterator last)
1766  : n(0), capacity(onstack_size), a(allocate(0)) {
1767  while (first != last) {
1768  (void) append<ArgArrayBase<T> >(*first);
1769  ++first;
1770  }
1771  }
1772 
1773 
1774  template<class T> template<class A>
1775  inline A&
1777  resize(x.size());
1778  for (int i=0; i<x.size(); i++)
1779  new (&a[n++]) T(x[i]);
1780  return static_cast<A&>(*this);
1781  }
1782 
1783  template<class T> template<class A>
1784  inline A
1786  A r(n+x.n);
1787  for (int i=n; i--;)
1788  new (&r[i]) T(a[i]);
1789  for (int i=x.n; i--;)
1790  new (&r[n+i]) T(x.a[i]);
1791  return r;
1792  }
1793 
1794  template<class T> template<class A>
1795  inline A
1796  ArgArrayBase<T>::concat(const T& x) const {
1797  A r(n+1);
1798  for (int i=n; i--;)
1799  new (&r[i]) T(a[i]);
1800  new (&r[n]) T(x);
1801  return r;
1802  }
1803 
1804  /*
1805  * Argument arrays for primitive types
1806  *
1807  */
1808 
1809  template<class T>
1810  forceinline
1812 
1813  template<class T>
1814  forceinline
1816 
1817  template<class T>
1819  : ArgArrayBase<T>(n) {
1820  va_list args;
1821  va_start(args, a0);
1822  a[0] = a0;
1823  for (int i = 1; i < n; i++)
1824  a[i] = va_arg(args,T);
1825  va_end(args);
1826  }
1827 
1828  template<class T>
1830  : ArgArrayBase<T>(n) {
1831  for (int i=n; i--; )
1832  a[i] = a0[i];
1833  }
1834 
1835  template<class T>
1836  forceinline
1838  : ArgArrayBase<T>(aa) {}
1839 
1840  template<class T>
1841  forceinline
1842  PrimArgArray<T>::PrimArgArray(const std::vector<T>& aa)
1843  : ArgArrayBase<T>(aa) {}
1844 
1845  template<class T>
1846  template<class InputIterator>
1847  forceinline
1848  PrimArgArray<T>::PrimArgArray(InputIterator first, InputIterator last)
1849  : ArgArrayBase<T>(first,last) {}
1850 
1851  template<class T>
1852  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType
1853  PrimArgArray<T>::slice(int start, int inc, int maxN) {
1855  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>
1856  (start,inc,maxN);
1857  }
1858 
1859  template<class T>
1860  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1862  return
1864  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1865  }
1866 
1867  template<class T>
1868  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1870  return
1872  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1873  }
1874 
1875  template<class T>
1876  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1878  return x.template concat
1879  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1880  }
1881 
1882  template<class T>
1883  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1884  operator +(const PrimArgArray<T>& x, const T& y) {
1885  return x.template concat
1886  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1887  }
1888 
1889  template<class T>
1890  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1891  operator +(const T& x, const PrimArgArray<T>& y) {
1892  return PrimArgArray<T>(1,x).template concat
1893  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1894  }
1895 
1896 
1897  /*
1898  * Argument arrays for non-primitive types
1899  *
1900  */
1901 
1902  template<class T>
1903  forceinline
1905 
1906  template<class T>
1907  forceinline
1909 
1910  template<class T>
1911  ArgArray<T>::ArgArray(int n, const T* a0)
1912  : ArgArrayBase<T>(n) {
1913  for (int i=n; i--; )
1914  a[i] = a0[i];
1915  }
1916 
1917  template<class T>
1918  forceinline
1920  : ArgArrayBase<T>(aa) {}
1921 
1922  template<class T>
1923  forceinline
1924  ArgArray<T>::ArgArray(const std::vector<T>& aa)
1925  : ArgArrayBase<T>(aa) {}
1926 
1927  template<class T>
1928  template<class InputIterator>
1929  forceinline
1930  ArgArray<T>::ArgArray(InputIterator first, InputIterator last)
1931  : ArgArrayBase<T>(first,last) {}
1932 
1933  template<class T>
1934  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType
1935  ArgArray<T>::slice(int start, int inc, int maxN) {
1937  <typename ArrayTraits<ArgArray<T> >::ArgsType>
1938  (start,inc,maxN);
1939  }
1940 
1941  template<class T>
1942  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1944  return
1946  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1947  }
1948 
1949  template<class T>
1950  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1952  return
1954  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1955  }
1956 
1957  template<class T>
1958  typename ArrayTraits<ArgArray<T> >::ArgsType
1960  return x.template concat
1961  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1962  }
1963 
1964  template<class T>
1965  typename ArrayTraits<ArgArray<T> >::ArgsType
1966  operator +(const ArgArray<T>& x, const T& y) {
1967  return x.template concat
1968  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1969  }
1970 
1971  template<class T>
1972  typename ArrayTraits<ArgArray<T> >::ArgsType
1973  operator +(const T& x, const ArgArray<T>& y) {
1974  ArgArray<T> xa(1);
1975  xa[0] = x;
1976  return xa.template concat
1977  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1978  }
1979 
1980  /*
1981  * Argument arrays for variables
1982  *
1983  */
1984 
1985  template<class Var>
1986  forceinline
1988 
1989  template<class Var>
1990  forceinline
1992 
1993  template<class Var>
1994  forceinline
1996  : ArgArrayBase<Var>(aa) {}
1997 
1998  template<class Var>
1999  forceinline
2000  VarArgArray<Var>::VarArgArray(const std::vector<Var>& aa)
2001  : ArgArrayBase<Var>(aa) {}
2002 
2003  template<class Var>
2004  template<class InputIterator>
2005  forceinline
2006  VarArgArray<Var>::VarArgArray(InputIterator first, InputIterator last)
2007  : ArgArrayBase<Var>(first,last) {}
2008 
2009  template<class Var>
2010  inline
2012  : ArgArrayBase<Var>(x.size()) {
2013  for (int i=x.size(); i--; )
2014  a[i]=x[i];
2015  }
2016 
2017  template<class Var>
2018  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType
2019  VarArgArray<Var>::slice(int start, int inc, int maxN) {
2021  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>
2022  (start,inc,maxN);
2023  }
2024 
2025  template<class Var>
2026  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
2028  return
2030  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
2031  }
2032 
2033  template<class Var>
2034  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
2036  return
2038  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
2039  }
2040 
2041  template<class Var>
2042  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2044  return x.template concat
2045  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2046  }
2047 
2048  template<class Var>
2049  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2050  operator +(const VarArgArray<Var>& x, const Var& y) {
2051  return x.template concat
2052  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2053  }
2054 
2055  template<class Var>
2056  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2057  operator +(const Var& x, const VarArgArray<Var>& y) {
2058  VarArgArray<Var> xa(1);
2059  xa[0] = x;
2060  return xa.template concat
2061  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2062  }
2063 
2064  template<class Var>
2065  forceinline bool
2067  return a.varimp() < b.varimp();
2068  }
2069 
2070  template<class Var>
2071  forceinline bool
2073  for (int i = n; i--;)
2074  if (!a[i].assigned())
2075  return false;
2076  return true;
2077  }
2078 
2079  template<class Var>
2080  bool
2081  VarArgArray<Var>::same(const Space& home) const {
2082  if (n < 2)
2083  return false;
2084  Region r(home);
2085  Var* y = r.alloc<Var>(n);
2086  for (int i = n; i--; )
2087  y[i] = a[i];
2088  VarLess vl;
2089  Support::quicksort<Var,VarLess>(y,n,vl);
2090  for (int i = n-1; i--; )
2091  if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) {
2092  r.free<Var>(y,n);
2093  return true;
2094  }
2095  r.free<Var>(y,n);
2096  return false;
2097  }
2098 
2099  template<class Var>
2100  bool
2101  VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
2102  int m = n + y.n;
2103  if (m < 2)
2104  return false;
2105  Region r(home);
2106  Var* z = r.alloc<Var>(m);
2107  for (int i = n; i--; )
2108  z[i] = a[i];
2109  for (int i = y.n; i--; )
2110  z[i+n] = y.a[i];
2111  VarLess vl;
2112  Support::quicksort<Var,VarLess>(z,m,vl);
2113  for (int i = m-1; i--; )
2114  if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) {
2115  r.free<Var>(z,m);
2116  return true;
2117  }
2118  r.free<Var>(z,m);
2119  return false;
2120  }
2121 
2122  template<class Var>
2123  bool
2124  VarArgArray<Var>::same(const Space&, const Var& y) const {
2125  if (y.assigned())
2126  return false;
2127  for (int i = n; i--; )
2128  if (a[i].varimp() == y.varimp())
2129  return true;
2130  return false;
2131  }
2132 
2133 
2134 
2135 
2136 
2137 
2138  /*
2139  * Interdependent code
2140  *
2141  */
2142 
2143  template<class Var>
2144  inline
2146  : n(a.size()) {
2147  if (n>0) {
2148  x = home.alloc<Var>(n);
2149  for (int i=n; i--;)
2150  x[i] = a[i];
2151  } else {
2152  x = NULL;
2153  }
2154  }
2155 
2156 
2157  /*
2158  * Printing of arrays
2159  *
2160  */
2161  template<class Char, class Traits, class Var>
2162  std::basic_ostream<Char,Traits>&
2163  operator <<(std::basic_ostream<Char,Traits>& os,
2164  const VarArray<Var>& x) {
2165  std::basic_ostringstream<Char,Traits> s;
2166  s.copyfmt(os); s.width(0);
2167  s << '{';
2168  if (x.size() > 0) {
2169  s << x[0];
2170  for (int i=1; i<x.size(); i++)
2171  s << ", " << x[i];
2172  }
2173  s << '}';
2174  return os << s.str();
2175  }
2176 
2177  template<class Char, class Traits, class View>
2178  std::basic_ostream<Char,Traits>&
2179  operator <<(std::basic_ostream<Char,Traits>& os,
2180  const ViewArray<View>& x) {
2181  std::basic_ostringstream<Char,Traits> s;
2182  s.copyfmt(os); s.width(0);
2183  s << '{';
2184  if (x.size() > 0) {
2185  s << x[0];
2186  for (int i=1; i<x.size(); i++)
2187  s << ", " << x[i];
2188  }
2189  s << '}';
2190  return os << s.str();
2191  }
2192 
2193  template<class Char, class Traits, class T>
2194  std::basic_ostream<Char,Traits>&
2195  operator <<(std::basic_ostream<Char,Traits>& os,
2196  const ArgArrayBase<T>& x) {
2197  std::basic_ostringstream<Char,Traits> s;
2198  s.copyfmt(os); s.width(0);
2199  s << '{';
2200  if (x.size() > 0) {
2201  s << x[0];
2202  for (int i=1; i<x.size(); i++)
2203  s << ", " << x[i];
2204  }
2205  s << '}';
2206  return os << s.str();
2207  }
2208 
2209 }
2210 
2211 // STATISTICS: kernel-other
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1253
T * pointer
Type of a pointer to the value type.
Definition: array.hpp:569
Var & operator[](int i)
Return variable at position i.
Definition: array.hpp:991
Post propagator for SetVar x
Definition: set.hh:784
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:587
bool same(const OffsetView &x, const OffsetView &y)
Test whether views x and y are the same.
Definition: offset.hpp:297
~ArgArrayBase(void)
Destructor.
Definition: array.hpp:1648
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
const typedef View * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:264
#define forceinline
Definition: config.hpp:173
void resize(int i)
Resize to hold at least i additional elements.
Definition: array.hpp:1606
Var * pointer
Type of a pointer to the value type.
Definition: array.hpp:102
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
const typedef Var * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:108
bool operator()(const Var &, const Var &)
Definition: array.hpp:2066
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1036
Argument array for primtive types.
Definition: array.hpp:640
const VarArray< Var > & operator=(const VarArray< Var > &a)
Initialize from variable array a (share elements)
Definition: array.hpp:978
unsigned int size(I &i)
Size of all ranges of range iterator i.
int n
Number of elements.
Definition: array.hpp:527
ArgArray(void)
Allocate empty array.
Definition: array.hpp:1904
bool same(const Space &home) const
Test whether array contains same variable multiply.
Definition: array.hpp:2081
void update(const NoOffset &)
Integer-precision integer scale view.
Definition: view.hpp:605
const typedef T * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:571
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
T value_type
Type of the view stored in this array.
Definition: array.hpp:563
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:784
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:2072
bool same(const Item &i, const Item &j)
Whether two items are the same.
Definition: propagate.hpp:76
const typedef Var * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:104
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Var value_type
Type of the variable stored in this array.
Definition: array.hpp:96
Computation spaces.
Definition: core.hpp:1748
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1060
std::reverse_iterator< View * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:266
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1701
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1241
ArrayTraits< ArgArray< T > >::ArgsType slice(int start, int inc=1, int n=-1)
Return slice of length n such that forall , .
Definition: array.hpp:1935
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
Var * x
Array of variables.
Definition: array.hpp:91
Sort order for variables.
Definition: array.hpp:848
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:123
static const int onstack_size
How many elements are possible inside array.
Definition: array.hpp:533
const typedef View & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:256
bool __before(const View &x, const View &y)
Definition: array.hpp:1445
View * pointer
Type of a pointer to the value type.
Definition: array.hpp:258
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:435
T * allocate(int n)
Allocate memory for n elements.
Definition: array.hpp:1599
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
bool __same(const X &x, const Y &y)
Definition: array.hpp:1464
void move_fst(int i)
Move view from position 0 to position i (shift elements to the left)
Definition: array.hpp:1289
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1085
View & reference
Type of a reference to the value type.
Definition: array.hpp:254
Var * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:106
Variable arrays
Definition: array.hpp:52
Base class for variables.
Definition: var.hpp:44
Gecode toplevel namespace
int capacity
Allocated size of the array.
Definition: array.hpp:529
Base-class for propagators.
Definition: core.hpp:1092
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:54
Var & reference
Type of a reference to the value type.
Definition: array.hpp:98
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1277
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const ArgArrayBase< T > &x)
Definition: array.hpp:2195
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const FloatView &x)
Print float variable view.
Definition: print.hpp:62
int n
Number of variables (size)
Definition: array.hpp:89
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void reschedule(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:96
PrimArgArray(void)
Allocate empty array.
Definition: array.hpp:1811
Argument array for non-primitive types.
Definition: array.hpp:727
VarImp * varimp(void) const
Return variable implementation of variable.
Definition: var.hpp:108
bool shared(const Space &home) const
Test whether array contains shared views.
Definition: array.hpp:1518
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
A & append(const T &x)
Insert a new element x at the end of the array (increase size by 1)
Definition: array.hpp:1756
View * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:262
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
T & operator[](int i)
Return element at position i.
Definition: array.hpp:1675
Handle to region.
Definition: region.hpp:61
ArrayTraits< VarArgArray< Var > >::ArgsType slice(int start, int inc=1, int n=-1)
Return slice of length n such that forall , .
Definition: array.hpp:2019
const typedef T & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:567
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Boolean integer variables.
Definition: int.hh:494
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1713
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2868
std::reverse_iterator< T * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:577
FloatVal operator+(const FloatVal &x)
Arithmetic operator.
Definition: val.hpp:168
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
const ArgArrayBase< T > & operator=(const ArgArrayBase< T > &a)
Initialize from view array a (copy elements)
Definition: array.hpp:1655
std::reverse_iterator< const Var * > const_reverse_iterator
Type of the iterator used to iterate backwards and read-only through this array's elements.
Definition: array.hpp:112
std::reverse_iterator< const View * > const_reverse_iterator
Type of the iterator used to iterate backwards and read-only through this array's elements.
Definition: array.hpp:268
const typedef T * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:575
const int capacity[n_warehouses]
Capacity of a single warehouse.
Definition: warehouses.cpp:53
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1295
Base-class for argument arrays.
Definition: array.hpp:524
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1436
A concat(const ArgArrayBase< T > &x) const
Return this array concatenated with x.
Definition: array.hpp:1785
const ViewArray< View > & operator=(const ViewArray< View > &a)
Initialize from view array a (share elements)
Definition: array.hpp:1208
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
T * a
Element array.
Definition: array.hpp:531
void drop_fst(int i)
Drop views from positions 0 to i-1 from array.
Definition: array.hpp:1301
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1048
Heap heap
The single global heap.
Definition: heap.cpp:48
A slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1737
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1265
ViewArray(void)
Default constructor (array of size 0)
Definition: array.hpp:1163
VarArgArray(void)
Allocate empty array.
Definition: array.hpp:1987
int PropCond
Type for propagation conditions.
Definition: core.hpp:152
VarArray(void)
Default constructor (array of size 0)
Definition: array.hpp:960
const typedef Var & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:100
T * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:573
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:85
void drop_lst(int i)
Drop views from positions i+1 to size()-1 from array.
Definition: array.hpp:1308
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
ViewArray(Space &home, const VarArgArray< Var > &a)
Initialize from variable argument array a (copy elements)
Definition: array.hpp:294
const int vl[6]
Definition: distinct.cpp:265
Base-class for advisors.
Definition: core.hpp:1294
bool before(const OffsetView &x, const OffsetView &y)
Test whether view x comes before y (arbitrary order)
Definition: offset.hpp:301
bool shared(const IntSet &, VX)
Definition: view-base.hpp:122
ArrayTraits< PrimArgArray< T > >::ArgsType & operator<<(const T &x)
Insert a new element x at the end of the array (increase size by 1)
Definition: array.hpp:1861
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:461
std::reverse_iterator< Var * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:110
ArrayTraits< VarArgArray< Var > >::ArgsType slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1005
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Traits of arrays in Gecode.
Definition: array.hpp:68
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1024
ArrayTraits< PrimArgArray< T > >::ArgsType slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1853
void unique(const Space &home)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1505
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1725
std::reverse_iterator< const T * > const_reverse_iterator
Type of the iterator used to iterate backwards and read-only through this array's elements.
Definition: array.hpp:579
ArrayTraits< VarArgArray< Var > >::ArgsType & operator<<(const Var &x)
Insert a new element x at the end of the array (increase size by 1)
Definition: array.hpp:2027
ViewArray(Region &r, const VarArgArray< Var > &a)
Initialize from variable argument array a (copy elements)
Definition: array.hpp:312
View value_type
Type of the view stored in this array.
Definition: array.hpp:252
bool __shared(const X &x, const Y &y)
Definition: array.hpp:1469
View arrays.
Definition: array.hpp:234
const unsigned int slice
Size of a slice in a portfolio and scale factor for restarts(in number of failures)
Definition: search.hh:124
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:75
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
ArrayTraits< ArgArray< T > >::ArgsType & operator<<(const T &x)
Insert a new element x at the end of the array (increase size by 1)
Definition: array.hpp:1943
T onstack[onstack_size]
In-array storage for elements.
Definition: array.hpp:535
Argument array for variables.
Definition: array.hpp:53
bool same(const Space &home) const
Test whether array has multiple occurence of the same view.
Definition: array.hpp:1475
T & reference
Type of a reference to the value type.
Definition: array.hpp:565
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1429
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
View & operator[](int i)
Return view at position i.
Definition: array.hpp:1227
ArgArrayBase(void)
Allocate empty array.
Definition: array.hpp:1623
Archive & operator<<(Archive &e, FloatNumBranch nl)
Definition: val-sel.hpp:43
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1689
const typedef View * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:260