Generated on Sat Feb 7 2015 02:01:14 for Gecode by doxygen 1.8.9.1
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: 2014-11-05 00:53:26 +0100 (Wed, 05 Nov 2014) $ by $Author: tack $
17  * $Revision: 14294 $
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, bool process=true);
372  void cancel(Space& home, Propagator& p, PropCond pc);
374  void subscribe(Space& home, Advisor& a);
376  void cancel(Space& home, Advisor& a);
378 
380 
381 
388  void update(Space&, bool share, ViewArray<View>& a);
390 
391 
393 
394  void move_fst(int i);
397  void move_lst(int i);
403  void move_fst(int i, Space& home, Propagator& p, PropCond pc);
409  void move_lst(int i, Space& home, Propagator& p, PropCond pc);
415  void move_fst(int i, Space& home, Advisor& a);
421  void move_lst(int i, Space& home, Advisor& a);
423 
425 
426  void drop_fst(int i);
429  void drop_lst(int i);
435  void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
442  void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
448  void drop_fst(int i, Space& home, Advisor& a);
454  void drop_lst(int i, Space& home, Advisor& a);
456 
458  bool assigned(void) const;
459 
461 
462 
467  bool same(const Space& home) const;
473  bool same(const Space& home, const View& y) const;
475  void unique(const Space& home);
477 
479 
480 
485  bool shared(const Space& home) const;
491  template<class ViewY>
492  bool shared(const Space& home, const ViewY& y) const;
498  template<class ViewY>
499  bool shared(const Space& home, const ViewArray<ViewY>& y) const;
501 
502  private:
503  static void* operator new(size_t) throw();
504  static void operator delete(void*,size_t);
505  };
506 
520  template<class T>
521  class ArgArrayBase {
522  protected:
524  int n;
526  int capacity;
528  T* a;
530  static const int onstack_size = 16;
534  T* allocate(int n);
536  void resize(int i);
538  template<class A>
539  A concat(const ArgArrayBase<T>& x) const;
541  template<class A>
542  A concat(const T& x) const;
544  template<class A>
545  A& append(const T& x);
547  template<class A>
548  A& append(const ArgArrayBase<T>& x);
554  template<class A>
555  A slice(int start, int inc=1, int n=-1);
556  public:
558 
559  typedef T value_type;
562  typedef T& reference;
564  typedef const T& const_reference;
566  typedef T* pointer;
568  typedef const T* const_pointer;
570  typedef T* iterator;
572  typedef const T* const_iterator;
574  typedef std::reverse_iterator<T*> reverse_iterator;
576  typedef std::reverse_iterator<const T*> const_reverse_iterator;
578 
580 
581  ArgArrayBase(void);
584  explicit ArgArrayBase(int n);
586  ArgArrayBase(const ArgArrayBase<T>& a);
588  const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
590  ArgArrayBase(const std::vector<T>& a);
592  template<class InputIterator>
593  ArgArrayBase(InputIterator first, InputIterator last);
595 
597 
598  int size(void) const;
601 
603 
604  T& operator [](int i);
607  const T& operator [](int i) const;
609 
611 
612  iterator begin(void);
615  const_iterator begin(void) const;
617  iterator end(void);
619  const_iterator end(void) const;
621  reverse_iterator rbegin(void);
623  const_reverse_iterator rbegin(void) const;
625  reverse_iterator rend(void);
627  const_reverse_iterator rend(void) const;
629 
631 
632  ~ArgArrayBase(void);
635  private:
636  static void* operator new(size_t) throw();
637  static void operator delete(void*,size_t);
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
815  operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
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&
883  operator <<(const VarArgArray<Var>& x);
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 process) {
1402  for (int i = n; i--; )
1403  x[i].subscribe(home,p,pc,process);
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  forceinline bool
1430  for (int i = n; i--;)
1431  if (!x[i].assigned())
1432  return false;
1433  return true;
1434  }
1435 
1436  template<class View>
1437  forceinline bool
1438  __before(const View& x, const View& y) {
1439  return before(x,y);
1440  }
1441 
1442  template<class View> template<class X>
1443  forceinline bool
1444  ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
1445  return __before(a,b);
1446  }
1447 
1448  template<class View>
1449  void
1450  ViewArray<View>::sort(View* y, int m) {
1451  ViewLess<View> vl;
1452  Support::quicksort<View,ViewLess<View> >(y,m,vl);
1453  }
1454 
1455  template<class X, class Y>
1456  forceinline bool
1457  __same(const X& x, const Y& y) {
1458  return same(x,y);
1459  }
1460  template<class X, class Y>
1461  forceinline bool
1462  __shared(const X& x, const Y& y) {
1463  return shared(x,y);
1464  }
1465 
1466  template<class View>
1467  bool
1468  ViewArray<View>::same(const Space& home) const {
1469  if (n < 2)
1470  return false;
1471  Region r(home);
1472  View* y = r.alloc<View>(n);
1473  for (int i = n; i--; )
1474  y[i] = x[i];
1475  sort(y,n);
1476  for (int i = n-1; i--; )
1477  if (!y[i].assigned() && __same(y[i+1],y[i])) {
1478  r.free<View>(y,n);
1479  return true;
1480  }
1481  r.free<View>(y,n);
1482  return false;
1483  }
1484 
1485  template<class View>
1486  bool
1487  ViewArray<View>::same(const Space&, const View& y) const {
1488  if (y.assigned())
1489  return false;
1490  for (int i = n; i--; )
1491  if (__same(x[i],y))
1492  return true;
1493  return false;
1494  }
1495 
1496  template<class View>
1497  void
1499  if (n < 2)
1500  return;
1501  sort(x,n);
1502  int j = 0;
1503  for (int i = 1; i<n; i++)
1504  if (!__same(x[j],x[i]))
1505  x[++j] = x[i];
1506  n = j+1;
1507  }
1508 
1509  template<class View>
1510  bool
1511  ViewArray<View>::shared(const Space& home) const {
1512  if (n < 2)
1513  return false;
1514  Region r(home);
1515  View* y = r.alloc<View>(n);
1516  for (int i = n; i--; )
1517  y[i] = x[i];
1518  sort(y,n);
1519  for (int i = n-1; i--; )
1520  if (!y[i].assigned() && __shared(y[i+1],y[i])) {
1521  r.free<View>(y,n);
1522  return true;
1523  }
1524  r.free<View>(y,n);
1525  return false;
1526  }
1527 
1528  template<class View> template<class ViewY>
1529  bool
1530  ViewArray<View>::shared(const Space&, const ViewY& y) const {
1531  if (y.assigned())
1532  return false;
1533  for (int i = n; i--; )
1534  if (!x[i].assigned() && __shared(x[i],y))
1535  return true;
1536  return false;
1537  }
1538 
1539  template<class View> template<class ViewY>
1540  bool
1541  ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
1542  if ((size() < 1) || (y.size() < 1))
1543  return false;
1544  Region r(home);
1545  View* xs = r.alloc<View>(size());
1546  for (int i=size(); i--; )
1547  xs[i] = x[i];
1548  ViewLess<View> xvl;
1549  Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
1550  ViewY* ys = r.alloc<ViewY>(y.size());
1551  for (int j=y.size(); j--; )
1552  ys[j] = y[j];
1553  ViewLess<ViewY> yvl;
1554  Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
1555  {
1556  int i=0, j=0;
1557  while ((i < size()) && (j < y.size()))
1558  if (!x[i].assigned() && __shared(x[i],y[j])) {
1559  r.free<View>(xs,size());
1560  r.free<ViewY>(ys,y.size());
1561  return true;
1562  } else if (before(x[i],y[j])) {
1563  i++;
1564  } else {
1565  j++;
1566  }
1567  }
1568  r.free<View>(xs,size());
1569  r.free<ViewY>(ys,y.size());
1570  return false;
1571  }
1572 
1573  template<class View>
1574  forceinline void*
1575  ViewArray<View>::operator new(size_t) throw() {
1576  return NULL;
1577  }
1578 
1579  template<class View>
1580  forceinline void
1581  ViewArray<View>::operator delete(void*,size_t) {
1582  }
1583 
1584 
1585  /*
1586  * Argument arrays: base class
1587  *
1588  */
1589 
1590  template<class T>
1591  forceinline T*
1593  return (n > onstack_size) ?
1594  heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
1595  }
1596 
1597  template<class T>
1598  forceinline void
1600  if (n+i >= capacity) {
1601  assert(n+i >= onstack_size);
1602  int newCapacity = (3*capacity)/2;
1603  if (newCapacity <= n+i)
1604  newCapacity = n+i;
1605  T* newA = allocate(newCapacity);
1606  heap.copy<T>(newA,a,n);
1607  if (capacity > onstack_size)
1608  heap.free(a,capacity);
1609  capacity = newCapacity;
1610  a = newA;
1611  }
1612  }
1613 
1614  template<class T>
1615  forceinline
1617  : n(0), capacity(onstack_size), a(allocate(0)) {}
1618 
1619  template<class T>
1620  forceinline
1622  : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
1623 
1624  template<class T>
1625  inline
1627  : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1628  heap.copy<T>(a,aa.a,n);
1629  }
1630 
1631  template<class T>
1632  inline
1633  ArgArrayBase<T>::ArgArrayBase(const std::vector<T>& aa)
1634  : n(static_cast<int>(aa.size())),
1635  capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1636  heap.copy<T>(a,&aa[0],n);
1637  }
1638 
1639  template<class T>
1640  forceinline
1642  if (capacity > onstack_size)
1643  heap.free(a,capacity);
1644  }
1645 
1646  template<class T>
1649  if (&aa != this) {
1650  if (capacity > onstack_size)
1651  heap.free(a,capacity);
1652  n = aa.n;
1653  capacity = (n < onstack_size ? onstack_size : n);
1654  a = allocate(aa.n);
1655  heap.copy<T>(a,aa.a,n);
1656  }
1657  return *this;
1658  }
1659 
1660  template<class T>
1661  forceinline int
1663  return n;
1664  }
1665 
1666  template<class T>
1667  forceinline T&
1669  assert((i>=0) && (i < n));
1670  return a[i];
1671  }
1672 
1673  template<class T>
1674  forceinline const T&
1676  assert((i>=0) && (i < n));
1677  return a[i];
1678  }
1679 
1680  template<class T>
1683  return a;
1684  }
1685 
1686  template<class T>
1689  return a;
1690  }
1691 
1692  template<class T>
1695  return a+n;
1696  }
1697 
1698  template<class T>
1700  ArgArrayBase<T>::end(void) const {
1701  return a+n;
1702  }
1703 
1704  template<class T>
1707  return reverse_iterator(a+n);
1708  }
1709 
1710  template<class T>
1713  return const_reverse_iterator(a+n);
1714  }
1715 
1716  template<class T>
1719  return reverse_iterator(a);
1720  }
1721 
1722  template<class T>
1725  return const_reverse_iterator(a);
1726  }
1727 
1728  template<class T> template<class A>
1729  A
1730  ArgArrayBase<T>::slice(int start, int inc, int maxN) {
1731  assert(n==0 || start < n);
1732  if (n==0 || maxN<0)
1733  maxN = n;
1734  int s;
1735  if (inc == 0)
1736  s = n-start;
1737  else if (inc > 0)
1738  s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
1739  else
1740  s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
1741  A r(std::min(maxN,s));
1742  for (int i=0; i<r.size(); i++, start+=inc)
1743  new (&r[i]) T(a[start]);
1744  return r;
1745  }
1746 
1747  template<class T> template<class A>
1748  inline A&
1750  resize(1);
1751  new (&a[n++]) T(x);
1752  return static_cast<A&>(*this);
1753  }
1754 
1755  template<class T>
1756  template<class InputIterator>
1757  inline
1758  ArgArrayBase<T>::ArgArrayBase(InputIterator first, InputIterator last)
1759  : n(0), capacity(onstack_size), a(allocate(0)) {
1760  while (first != last) {
1761  (void) append<ArgArrayBase<T> >(*first);
1762  ++first;
1763  }
1764  }
1765 
1766 
1767  template<class T> template<class A>
1768  inline A&
1770  resize(x.size());
1771  for (int i=0; i<x.size(); i++)
1772  new (&a[n++]) T(x[i]);
1773  return static_cast<A&>(*this);
1774  }
1775 
1776  template<class T> template<class A>
1777  inline A
1779  A r(n+x.n);
1780  for (int i=n; i--;)
1781  new (&r[i]) T(a[i]);
1782  for (int i=x.n; i--;)
1783  new (&r[n+i]) T(x.a[i]);
1784  return r;
1785  }
1786 
1787  template<class T> template<class A>
1788  inline A
1789  ArgArrayBase<T>::concat(const T& x) const {
1790  A r(n+1);
1791  for (int i=n; i--;)
1792  new (&r[i]) T(a[i]);
1793  new (&r[n]) T(x);
1794  return r;
1795  }
1796 
1797  template<class T>
1798  forceinline void*
1799  ArgArrayBase<T>::operator new(size_t) throw () {
1800  return NULL;
1801  }
1802 
1803  template<class T>
1804  forceinline void
1805  ArgArrayBase<T>::operator delete(void*,size_t) {
1806  }
1807 
1808  /*
1809  * Argument arrays for primitive types
1810  *
1811  */
1812 
1813  template<class T>
1814  forceinline
1816 
1817  template<class T>
1818  forceinline
1820 
1821  template<class T>
1823  : ArgArrayBase<T>(n) {
1824  va_list args;
1825  va_start(args, a0);
1826  a[0] = a0;
1827  for (int i = 1; i < n; i++)
1828  a[i] = va_arg(args,T);
1829  va_end(args);
1830  }
1831 
1832  template<class T>
1834  : ArgArrayBase<T>(n) {
1835  for (int i=n; i--; )
1836  a[i] = a0[i];
1837  }
1838 
1839  template<class T>
1840  forceinline
1842  : ArgArrayBase<T>(aa) {}
1843 
1844  template<class T>
1845  forceinline
1846  PrimArgArray<T>::PrimArgArray(const std::vector<T>& aa)
1847  : ArgArrayBase<T>(aa) {}
1848 
1849  template<class T>
1850  template<class InputIterator>
1851  forceinline
1852  PrimArgArray<T>::PrimArgArray(InputIterator first, InputIterator last)
1853  : ArgArrayBase<T>(first,last) {}
1854 
1855  template<class T>
1856  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType
1857  PrimArgArray<T>::slice(int start, int inc, int maxN) {
1858  return ArgArrayBase<T>::template slice
1859  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>
1860  (start,inc,maxN);
1861  }
1862 
1863  template<class T>
1864  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1866  return
1868  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1869  }
1870 
1871  template<class T>
1872  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1874  return
1876  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1877  }
1878 
1879  template<class T>
1880  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1882  return x.template concat
1883  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1884  }
1885 
1886  template<class T>
1887  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1888  operator +(const PrimArgArray<T>& x, const T& y) {
1889  return x.template concat
1890  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1891  }
1892 
1893  template<class T>
1894  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1895  operator +(const T& x, const PrimArgArray<T>& y) {
1896  return PrimArgArray<T>(1,x).template concat
1897  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1898  }
1899 
1900 
1901  /*
1902  * Argument arrays for non-primitive types
1903  *
1904  */
1905 
1906  template<class T>
1907  forceinline
1909 
1910  template<class T>
1911  forceinline
1913 
1914  template<class T>
1915  ArgArray<T>::ArgArray(int n, const T* a0)
1916  : ArgArrayBase<T>(n) {
1917  for (int i=n; i--; )
1918  a[i] = a0[i];
1919  }
1920 
1921  template<class T>
1922  forceinline
1924  : ArgArrayBase<T>(aa) {}
1925 
1926  template<class T>
1927  forceinline
1928  ArgArray<T>::ArgArray(const std::vector<T>& aa)
1929  : ArgArrayBase<T>(aa) {}
1930 
1931  template<class T>
1932  template<class InputIterator>
1933  forceinline
1934  ArgArray<T>::ArgArray(InputIterator first, InputIterator last)
1935  : ArgArrayBase<T>(first,last) {}
1936 
1937  template<class T>
1938  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType
1939  ArgArray<T>::slice(int start, int inc, int maxN) {
1940  return ArgArrayBase<T>::template slice
1941  <typename ArrayTraits<ArgArray<T> >::ArgsType>
1942  (start,inc,maxN);
1943  }
1944 
1945  template<class T>
1946  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1948  return
1950  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1951  }
1952 
1953  template<class T>
1954  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1956  return
1958  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1959  }
1960 
1961  template<class T>
1962  typename ArrayTraits<ArgArray<T> >::ArgsType
1963  operator +(const ArgArray<T>& x, const ArgArray<T>& y) {
1964  return x.template concat
1965  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1966  }
1967 
1968  template<class T>
1969  typename ArrayTraits<ArgArray<T> >::ArgsType
1970  operator +(const ArgArray<T>& x, const T& y) {
1971  return x.template concat
1972  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1973  }
1974 
1975  template<class T>
1976  typename ArrayTraits<ArgArray<T> >::ArgsType
1977  operator +(const T& x, const ArgArray<T>& y) {
1978  ArgArray<T> xa(1);
1979  xa[0] = x;
1980  return xa.template concat
1981  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1982  }
1983 
1984  /*
1985  * Argument arrays for variables
1986  *
1987  */
1988 
1989  template<class Var>
1990  forceinline
1992 
1993  template<class Var>
1994  forceinline
1996 
1997  template<class Var>
1998  forceinline
2000  : ArgArrayBase<Var>(aa) {}
2001 
2002  template<class Var>
2003  forceinline
2004  VarArgArray<Var>::VarArgArray(const std::vector<Var>& aa)
2005  : ArgArrayBase<Var>(aa) {}
2006 
2007  template<class Var>
2008  template<class InputIterator>
2009  forceinline
2010  VarArgArray<Var>::VarArgArray(InputIterator first, InputIterator last)
2011  : ArgArrayBase<Var>(first,last) {}
2012 
2013  template<class Var>
2014  inline
2016  : ArgArrayBase<Var>(x.size()) {
2017  for (int i=x.size(); i--; )
2018  a[i]=x[i];
2019  }
2020 
2021  template<class Var>
2022  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType
2023  VarArgArray<Var>::slice(int start, int inc, int maxN) {
2024  return ArgArrayBase<Var>::template slice
2025  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>
2026  (start,inc,maxN);
2027  }
2028 
2029  template<class Var>
2030  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
2032  return
2034  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
2035  }
2036 
2037  template<class Var>
2038  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
2040  return
2042  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
2043  }
2044 
2045  template<class Var>
2046  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2048  return x.template concat
2049  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2050  }
2051 
2052  template<class Var>
2053  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2054  operator +(const VarArgArray<Var>& x, const Var& y) {
2055  return x.template concat
2056  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2057  }
2058 
2059  template<class Var>
2060  typename ArrayTraits<VarArgArray<Var> >::ArgsType
2061  operator +(const Var& x, const VarArgArray<Var>& y) {
2062  VarArgArray<Var> xa(1);
2063  xa[0] = x;
2064  return xa.template concat
2065  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
2066  }
2067 
2068  template<class Var>
2069  forceinline bool
2071  return a.varimp() < b.varimp();
2072  }
2073 
2074  template<class Var>
2075  forceinline bool
2077  for (int i = n; i--;)
2078  if (!a[i].assigned())
2079  return false;
2080  return true;
2081  }
2082 
2083  template<class Var>
2084  bool
2085  VarArgArray<Var>::same(const Space& home) const {
2086  if (n < 2)
2087  return false;
2088  Region r(home);
2089  Var* y = r.alloc<Var>(n);
2090  for (int i = n; i--; )
2091  y[i] = a[i];
2092  VarLess vl;
2093  Support::quicksort<Var,VarLess>(y,n,vl);
2094  for (int i = n-1; i--; )
2095  if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) {
2096  r.free<Var>(y,n);
2097  return true;
2098  }
2099  r.free<Var>(y,n);
2100  return false;
2101  }
2102 
2103  template<class Var>
2104  bool
2105  VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
2106  int m = n + y.n;
2107  if (m < 2)
2108  return false;
2109  Region r(home);
2110  Var* z = r.alloc<Var>(m);
2111  for (int i = n; i--; )
2112  z[i] = a[i];
2113  for (int i = y.n; i--; )
2114  z[i+n] = y.a[i];
2115  VarLess vl;
2116  Support::quicksort<Var,VarLess>(z,m,vl);
2117  for (int i = m-1; i--; )
2118  if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) {
2119  r.free<Var>(z,m);
2120  return true;
2121  }
2122  r.free<Var>(z,m);
2123  return false;
2124  }
2125 
2126  template<class Var>
2127  bool
2128  VarArgArray<Var>::same(const Space&, const Var& y) const {
2129  if (y.assigned())
2130  return false;
2131  for (int i = n; i--; )
2132  if (a[i].varimp() == y.varimp())
2133  return true;
2134  return false;
2135  }
2136 
2137 
2138 
2139 
2140 
2141 
2142  /*
2143  * Interdependent code
2144  *
2145  */
2146 
2147  template<class Var>
2148  inline
2150  : n(a.size()) {
2151  if (n>0) {
2152  x = home.alloc<Var>(n);
2153  for (int i=n; i--;)
2154  x[i] = a[i];
2155  } else {
2156  x = NULL;
2157  }
2158  }
2159 
2160 
2161  /*
2162  * Printing of arrays
2163  *
2164  */
2165  template<class Char, class Traits, class Var>
2166  std::basic_ostream<Char,Traits>&
2167  operator <<(std::basic_ostream<Char,Traits>& os,
2168  const VarArray<Var>& x) {
2169  std::basic_ostringstream<Char,Traits> s;
2170  s.copyfmt(os); s.width(0);
2171  s << '{';
2172  if (x.size() > 0) {
2173  s << x[0];
2174  for (int i=1; i<x.size(); i++)
2175  s << ", " << x[i];
2176  }
2177  s << '}';
2178  return os << s.str();
2179  }
2180 
2181  template<class Char, class Traits, class View>
2182  std::basic_ostream<Char,Traits>&
2183  operator <<(std::basic_ostream<Char,Traits>& os,
2184  const ViewArray<View>& x) {
2185  std::basic_ostringstream<Char,Traits> s;
2186  s.copyfmt(os); s.width(0);
2187  s << '{';
2188  if (x.size() > 0) {
2189  s << x[0];
2190  for (int i=1; i<x.size(); i++)
2191  s << ", " << x[i];
2192  }
2193  s << '}';
2194  return os << s.str();
2195  }
2196 
2197  template<class Char, class Traits, class T>
2198  std::basic_ostream<Char,Traits>&
2199  operator <<(std::basic_ostream<Char,Traits>& os,
2200  const ArgArrayBase<T>& x) {
2201  std::basic_ostringstream<Char,Traits> s;
2202  s.copyfmt(os); s.width(0);
2203  s << '{';
2204  if (x.size() > 0) {
2205  s << x[0];
2206  for (int i=1; i<x.size(); i++)
2207  s << ", " << x[i];
2208  }
2209  s << '}';
2210  return os << s.str();
2211  }
2212 
2213 }
2214 
2215 // STATISTICS: kernel-other
A slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1730
int capacity
Allocated size of the array.
Definition: array.hpp:526
Var value_type
Type of the variable stored in this array.
Definition: array.hpp:96
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:552
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:1947
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1706
const T * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:572
bool operator()(const Var &, const Var &)
Definition: array.hpp:2070
const ArgArrayBase< T > & operator=(const ArgArrayBase< T > &a)
Initialize from view array a (copy elements)
Definition: array.hpp:1648
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1253
Argument array for primtive types.
Definition: array.hpp:640
bool __shared(const X &x, const Y &y)
Definition: array.hpp:1462
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:84
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1718
Var * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:106
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:576
Var & reference
Type of a reference to the value type.
Definition: array.hpp:98
Base-class for propagators.
Definition: core.hpp:755
Var * pointer
Type of a pointer to the value type.
Definition: array.hpp:102
Base-class for advisors.
Definition: core.hpp:926
Variable arrays
Definition: array.hpp:52
T * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:570
View & operator[](int i)
Return view at position i.
Definition: array.hpp:1227
Handle to region.
Definition: region.hpp:61
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1036
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:2031
const View & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:256
void unique(const Space &home)
Remove all duplicate views from array (changes element order)
Definition: array.hpp:1498
Computation spaces.
Definition: core.hpp:1362
const ViewArray< View > & operator=(const ViewArray< View > &a)
Initialize from view array a (share elements)
Definition: array.hpp:1208
View * iterator
Type of the iterator used to iterate through this array's elements.
Definition: array.hpp:262
Heap heap
The single global heap.
Definition: heap.cpp:49
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
View * pointer
Type of a pointer to the value type.
Definition: array.hpp:258
VarArgArray(void)
Allocate empty array.
Definition: array.hpp:1991
ArgArray(void)
Allocate empty array.
Definition: array.hpp:1908
const Var & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:100
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing)
Definition: sort.hpp:137
~ArgArrayBase(void)
Destructor.
Definition: array.hpp:1641
bool same(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether two views are the same.
Definition: view.hpp:603
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
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
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
void drop_lst(int i)
Drop views from positions i+1 to size()-1 from array.
Definition: array.hpp:1308
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Argument array for non-primitive types.
Definition: array.hpp:727
ArrayTraits< ArgArray< T > >::ArgsType slice(int start, int inc=1, int n=-1)
Return slice of length n such that forall , .
Definition: array.hpp:1939
void resize(int i)
Resize to hold at least i additional elements.
Definition: array.hpp:1599
Var * x
Array of variables.
Definition: array.hpp:91
const View * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:260
FloatVal operator+(const FloatVal &x)
Definition: val.hpp:168
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1048
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
bool shared(const Space &home) const
Test whether array contains shared views.
Definition: array.hpp:1511
T onstack[onstack_size]
In-array storage for elements.
Definition: array.hpp:532
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1060
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:74
bool before(const ViewA &x, const ViewB &y)
Definition: view.hpp:650
unsigned int size(I &i)
Size of all ranges of range iterator i.
ArgArrayBase(void)
Allocate empty array.
Definition: array.hpp:1616
PrimArgArray(void)
Allocate empty array.
Definition: array.hpp:1815
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1682
ViewArray(Region &r, const VarArgArray< Var > &a)
Initialize from variable argument array a (copy elements)
Definition: array.hpp:312
VarArray(void)
Default constructor (array of size 0)
Definition: array.hpp:960
T & reference
Type of a reference to the value type.
Definition: array.hpp:562
bool __before(const View &x, const View &y)
Definition: array.hpp:1438
View arrays.
Definition: array.hpp:234
ArrayTraits< VarArgArray< Var > >::ArgsType slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1005
int n
Number of variables (size)
Definition: array.hpp:89
void drop_fst(int i)
Drop views from positions 0 to i-1 from array.
Definition: array.hpp:1301
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1241
bool __same(const X &x, const Y &y)
Definition: array.hpp:1457
void move_lst(int i)
Move view from position size()-1 to position i (truncate array by one)
Definition: array.hpp:1295
iterator begin(void)
Return an iterator at the beginning of the array.
Definition: array.hpp:1024
reverse_iterator rend(void)
Return a reverse iterator past the beginning of the array.
Definition: array.hpp:1277
ArrayTraits< PrimArgArray< T > >::ArgsType slice(int start, int inc=1, int n=-1)
Definition: array.hpp:1857
T * pointer
Type of a pointer to the value type.
Definition: array.hpp:566
View & reference
Type of a reference to the value type.
Definition: array.hpp:254
Base class for variables.
Definition: var.hpp:44
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base-class for argument arrays.
Definition: array.hpp:521
A concat(const ArgArrayBase< T > &x) const
Return this array concatenated with x.
Definition: array.hpp:1778
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
#define forceinline
Definition: config.hpp:132
void free(T *b, long unsigned int n)
Delete n objects allocated from the region starting at b.
Definition: region.hpp:352
ArrayTraits< VarArgArray< Var > >::ArgsType slice(int start, int inc=1, int n=-1)
Return slice of length n such that forall , .
Definition: array.hpp:2023
bool same(const Space &home) const
Test whether array has multiple occurence of the same view.
Definition: array.hpp:1468
const int vl[6]
Definition: distinct.cpp:209
const Var * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:104
reverse_iterator rbegin(void)
Return a reverse iterator at the end of the array.
Definition: array.hpp:1265
int n
Number of elements.
Definition: array.hpp:524
Var & operator[](int i)
Return variable at position i.
Definition: array.hpp:991
A & append(const T &x)
Insert a new element x at the end of the array (increase size by 1)
Definition: array.hpp:1749
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:662
Sort order for variables.
Definition: array.hpp:848
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
T value_type
Type of the view stored in this array.
Definition: array.hpp:560
Traits of arrays in Gecode.
Definition: array.hpp:68
const T & const_reference
Type of a constant reference to the value type.
Definition: array.hpp:564
void move_fst(int i)
Move view from position 0 to position i (shift elements to the left)
Definition: array.hpp:1289
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
Argument array for variables.
Definition: array.hpp:53
const int capacity[n_warehouses]
Capacity of a single warehouse.
Definition: warehouses.cpp:53
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
ViewArray(Space &home, const VarArgArray< Var > &a)
Initialize from variable argument array a (copy elements)
Definition: array.hpp:294
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1085
std::reverse_iterator< T * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:574
iterator end(void)
Return an iterator past the end of the array.
Definition: array.hpp:1694
const Var * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:108
View value_type
Type of the view stored in this array.
Definition: array.hpp:252
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:1865
T & operator[](int i)
Return element at position i.
Definition: array.hpp:1668
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
static const int onstack_size
How many elements are possible inside array.
Definition: array.hpp:530
const View * const_iterator
Type of the iterator used to iterate read-only through this array's elements.
Definition: array.hpp:264
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1429
const VarArray< Var > & operator=(const VarArray< Var > &a)
Initialize from variable array a (share elements)
Definition: array.hpp:978
std::reverse_iterator< View * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:266
const T * const_pointer
Type of a read-only pointer to the value type.
Definition: array.hpp:568
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
T * allocate(int n)
Allocate memory for n elements.
Definition: array.hpp:1592
bool same(const Space &home) const
Test whether array contains same variable multiply.
Definition: array.hpp:2085
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:2076
std::reverse_iterator< Var * > reverse_iterator
Type of the iterator used to iterate backwards through this array's elements.
Definition: array.hpp:110
T * a
Element array.
Definition: array.hpp:528
ViewArray(void)
Default constructor (array of size 0)
Definition: array.hpp:1163