Generated on Wed Sep 5 2012 18:51:43 for Gecode by doxygen 1.8.1.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: 2011-08-18 20:10:04 +1000 (Thu, 18 Aug 2011) $ by $Author: tack $
17  * $Revision: 12313 $
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 <sstream>
48 
49 namespace Gecode {
50 
51  template<class Var> class VarArray;
52  template<class Var> class VarArgArray;
53 
66  template<class A>
67  class ArrayTraits {};
68 
84  template<class Var>
85  class VarArray {
86  protected:
88  int n;
90  Var* x;
91  public:
93 
94 
95  typedef Var value_type;
97  typedef Var& reference;
99  typedef const Var& const_reference;
101  typedef Var* pointer;
103  typedef const Var* const_pointer;
105  typedef Var* iterator;
107  typedef const Var* const_iterator;
109  typedef std::reverse_iterator<Var*> reverse_iterator;
111  typedef std::reverse_iterator<const Var*> const_reverse_iterator;
113 
115 
116 
117 
118  VarArray(void);
120  VarArray(Space& home, int m);
122  VarArray(Space& home, const VarArgArray<Var>&);
124  VarArray(const VarArray<Var>& a);
126  const VarArray<Var>& operator =(const VarArray<Var>& a);
128 
130 
131 
132  int size(void) const;
134 
136 
137 
138  Var& operator [](int i);
140  const Var& operator [](int i) const;
146  typename ArrayTraits<VarArgArray<Var> >::ArgsType
147  slice(int start, int inc=1, int n=-1);
149 
151 
152 
153  iterator begin(void);
155  const_iterator begin(void) const;
157  iterator end(void);
159  const_iterator end(void) const;
161  reverse_iterator rbegin(void);
163  const_reverse_iterator rbegin(void) const;
165  reverse_iterator rend(void);
167  const_reverse_iterator rend(void) const;
169 
171  bool assigned(void) const;
172 
174 
175 
182  void update(Space&, bool share, VarArray<Var>& a);
184  private:
185  static void* operator new(size_t);
186  static void operator delete(void*,size_t);
187  };
188 
192  template<class T>
193  typename ArrayTraits<VarArray<T> >::ArgsType
194  operator +(const VarArray<T>& x, const VarArgArray<T>& y);
195 
199  template<class T>
200  typename ArrayTraits<VarArray<T> >::ArgsType
201  operator +(const VarArray<T>& x, const VarArray<T>& y);
202 
206  template<class T>
207  typename ArrayTraits<VarArray<T> >::ArgsType
208  operator +(const VarArgArray<T>& x, const VarArray<T>& y);
209 
213  template<class T>
214  typename ArrayTraits<VarArray<T> >::ArgsType
215  operator +(const VarArray<T>& x, const T& y);
216 
220  template<class T>
221  typename ArrayTraits<VarArray<T> >::ArgsType
222  operator +(const T& x, const VarArray<T>& y);
223 
232  template<class View>
233  class ViewArray {
234  private:
236  int n;
238  View* x;
240  template<class X>
241  class ViewLess {
242  public:
243  bool operator ()(const X&, const X&);
244  };
246  static void sort(View* x, int n);
247  public:
249 
250 
251  typedef View value_type;
253  typedef View& reference;
255  typedef const View& const_reference;
257  typedef View* pointer;
259  typedef const View* const_pointer;
261  typedef View* iterator;
263  typedef const View* const_iterator;
265  typedef std::reverse_iterator<View*> reverse_iterator;
267  typedef std::reverse_iterator<const View*> const_reverse_iterator;
269 
271 
272 
273  ViewArray(void);
275  ViewArray(Space& home, int m);
277  ViewArray(Region& r, int m);
279  ViewArray(const ViewArray<View>& a);
281  ViewArray(Space& home, const ViewArray<View>& a);
283  ViewArray(Region& r, const ViewArray<View>& a);
292  template<class Var>
294  : n(a.size()) {
295  // This may not be in the hpp file (to satisfy the MS compiler)
296  if (n>0) {
297  x = home.alloc<View>(n);
298  for (int i=n; i--; )
299  x[i]=a[i];
300  } else {
301  x = NULL;
302  }
303  }
310  template<class Var>
312  : n(a.size()) {
313  // This may not be in the hpp file (to satisfy the MS compiler)
314  if (n>0) {
315  x = r.alloc<View>(n);
316  for (int i=n; i--; )
317  x[i]=a[i];
318  } else {
319  x = NULL;
320  }
321  }
323 
325 
326 
327  int size(void) const;
329  void size(int n);
331 
333 
334 
335  View& operator [](int i);
337  const View& operator [](int i) const;
339 
341 
342 
343  iterator begin(void);
345  const_iterator begin(void) const;
347  iterator end(void);
349  const_iterator end(void) const;
351  reverse_iterator rbegin(void);
353  const_reverse_iterator rbegin(void) const;
355  reverse_iterator rend(void);
357  const_reverse_iterator rend(void) const;
359 
361 
362 
369  void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
371  void cancel(Space& home, Propagator& p, PropCond pc);
373  void subscribe(Space& home, Advisor& a);
375  void cancel(Space& home, Advisor& a);
377 
379 
380 
387  void update(Space&, bool share, ViewArray<View>& a);
389 
390 
392 
393 
394  void move_fst(int i);
396  void move_lst(int i);
402  void move_fst(int i, Space& home, Propagator& p, PropCond pc);
408  void move_lst(int i, Space& home, Propagator& p, PropCond pc);
414  void move_fst(int i, Space& home, Advisor& a);
420  void move_lst(int i, Space& home, Advisor& a);
422 
424 
425 
426  void drop_fst(int i);
428  void drop_lst(int i);
434  void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
441  void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
447  void drop_fst(int i, Space& home, Advisor& a);
453  void drop_lst(int i, Space& home, Advisor& a);
455 
457  bool assigned(void) const;
458 
460 
461 
466  bool same(const Space& home) const;
472  bool same(const Space& home, const View& y) const;
474  void unique(const Space& home);
476 
478 
479 
484  bool shared(const Space& home) const;
490  template<class ViewY>
491  bool shared(const Space& home, const ViewY& y) const;
497  template<class ViewY>
498  bool shared(const Space& home, const ViewArray<ViewY>& y) const;
500 
501  private:
502  static void* operator new(size_t);
503  static void operator delete(void*,size_t);
504  };
505 
519  template<class T>
520  class ArgArrayBase {
521  protected:
523  int n;
525  int capacity;
527  T* a;
529  static const int onstack_size = 16;
533  T* allocate(int n);
535  void resize(int i);
537  template<class A>
538  A concat(const ArgArrayBase<T>& x) const;
540  template<class A>
541  A concat(const T& x) const;
543  template<class A>
544  A& append(const T& x);
546  template<class A>
547  A& append(const ArgArrayBase<T>& x);
553  template<class A>
554  A slice(int start, int inc=1, int n=-1);
555  public:
557 
558 
559  typedef T value_type;
561  typedef T& reference;
563  typedef const T& const_reference;
565  typedef T* pointer;
567  typedef const T* const_pointer;
569  typedef T* iterator;
571  typedef const T* const_iterator;
573  typedef std::reverse_iterator<T*> reverse_iterator;
575  typedef std::reverse_iterator<const T*> const_reverse_iterator;
577 
579 
580 
581  ArgArrayBase(void);
583  explicit ArgArrayBase(int n);
589 
591 
592 
593  int size(void) const;
595 
597 
598 
599  T& operator [](int i);
601  const T& operator [](int i) const;
603 
605 
606 
607  iterator begin(void);
609  const_iterator begin(void) const;
611  iterator end(void);
613  const_iterator end(void) const;
615  reverse_iterator rbegin(void);
617  const_reverse_iterator rbegin(void) const;
619  reverse_iterator rend(void);
621  const_reverse_iterator rend(void) const;
623 
625 
626 
627  ~ArgArrayBase(void);
629  private:
630  static void* operator new(size_t);
631  static void operator delete(void*,size_t);
632  };
633 
634  template<class> class PrimArgArray;
635 
639  template<class T>
640  typename ArrayTraits<PrimArgArray<T> >::ArgsType
641  operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
642 
646  template<class T>
647  typename ArrayTraits<PrimArgArray<T> >::ArgsType
648  operator +(const PrimArgArray<T>& x, const T& y);
649 
653  template<class T>
654  typename ArrayTraits<PrimArgArray<T> >::ArgsType
655  operator +(const T& x, const PrimArgArray<T>& y);
656 
668  template<class T>
669  class PrimArgArray : public ArgArrayBase<T> {
670  protected:
671  using ArgArrayBase<T>::a;
672  public:
673  using ArgArrayBase<T>::size;
675 
676 
677  PrimArgArray(void);
679  explicit PrimArgArray(int n);
681  PrimArgArray(int n, T e0, ...);
683  PrimArgArray(int n, const T* e);
687 
688 
689 
694  typename ArrayTraits<PrimArgArray<T> >::ArgsType
695  slice(int start, int inc=1, int n=-1);
697 
698 
699 
700  typename ArrayTraits<PrimArgArray<T> >::ArgsType&
701  operator <<(const T& x);
703  typename ArrayTraits<PrimArgArray<T> >::ArgsType&
704  operator <<(const PrimArgArray<T>& x);
706 
707  friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
708  operator + <>(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
709  friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
710  operator + <>(const PrimArgArray<T>& x, const T& y);
711  friend
712  typename ArrayTraits<PrimArgArray<T> >::ArgsType
713  operator + <>(const T& x, const PrimArgArray<T>& y);
714  };
715 
716  template<class> class ArgArray;
717 
721  template<class T>
722  typename ArrayTraits<ArgArray<T> >::ArgsType
723  operator +(const ArgArray<T>& x, const ArgArray<T>& y);
724 
728  template<class T>
729  typename ArrayTraits<ArgArray<T> >::ArgsType
730  operator +(const ArgArray<T>& x, const T& y);
731 
735  template<class T>
736  typename ArrayTraits<ArgArray<T> >::ArgsType
737  operator +(const T& x, const ArgArray<T>& y);
738 
750  template<class T>
751  class ArgArray : public ArgArrayBase<T> {
752  protected:
753  using ArgArrayBase<T>::a;
754  public:
755  using ArgArrayBase<T>::size;
757 
758 
759  ArgArray(void);
761  explicit ArgArray(int n);
763  ArgArray(int n, const T* e);
765  ArgArray(const ArgArray<T>& a);
767 
768 
769 
770  typename ArrayTraits<ArgArray<T> >::ArgsType
771  slice(int start, int inc=1, int n=-1);
773 
774 
775 
776  typename ArrayTraits<ArgArray<T> >::ArgsType&
777  operator <<(const T& x);
779  typename ArrayTraits<ArgArray<T> >::ArgsType&
780  operator <<(const ArgArray<T>& x);
782 
783  friend typename ArrayTraits<ArgArray<T> >::ArgsType
784  operator + <>(const ArgArray<T>& x, const ArgArray<T>& y);
785  friend typename ArrayTraits<ArgArray<T> >::ArgsType
786  operator + <>(const ArgArray<T>& x, const T& y);
787  friend
788  typename ArrayTraits<ArgArray<T> >::ArgsType
789  operator + <>(const T& x, const ArgArray<T>& y);
790  };
791 
792  template<class> class VarArgArray;
793 
797  template<class Var>
798  typename ArrayTraits<VarArgArray<Var> >::ArgsType
799  operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
800 
804  template<class Var>
805  typename ArrayTraits<VarArgArray<Var> >::ArgsType
806  operator +(const VarArgArray<Var>& x, const Var& y);
807 
811  template<class Var>
812  typename ArrayTraits<VarArgArray<Var> >::ArgsType
813  operator +(const Var& x, const VarArgArray<Var>& y);
814 
826  template<class Var>
827  class VarArgArray : public ArgArrayBase<Var> {
828  protected:
829  using ArgArrayBase<Var>::a;
830  using ArgArrayBase<Var>::n;
832  class VarLess {
833  public:
834  bool operator ()(const Var&, const Var&);
835  };
836  public:
839 
840 
841  VarArgArray(void);
843  explicit VarArgArray(int n);
847  VarArgArray(const VarArray<Var>& a);
849 
850 
851 
852  typename ArrayTraits<VarArgArray<Var> >::ArgsType
853  slice(int start, int inc=1, int n=-1);
855 
856 
857 
858  typename ArrayTraits<VarArgArray<Var> >::ArgsType&
859  operator <<(const Var& x);
861  typename ArrayTraits<VarArgArray<Var> >::ArgsType&
862  operator <<(const VarArgArray<Var>& x);
864 
866  bool assigned(void) const;
867 
868  friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
869  operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
870  friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
871  operator + <>(const VarArgArray<Var>& x, const Var& y);
872  friend
873  typename ArrayTraits<VarArgArray<Var> >::ArgsType
874  operator + <>(const Var& x, const VarArgArray<Var>& y);
875 
877 
878 
883  bool same(const Space& home) const;
889  bool same(const Space& home, const Var& y) const;
895  bool same(const Space& home, const VarArgArray<Var>& y) const;
897  };
898 
903  template<class Char, class Traits, class Var>
904  std::basic_ostream<Char,Traits>&
905  operator <<(std::basic_ostream<Char,Traits>& os,
906  const VarArray<Var>& x);
907 
912  template<class Char, class Traits, class View>
913  std::basic_ostream<Char,Traits>&
914  operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
915 
920  template<class Char, class Traits, class T>
921  std::basic_ostream<Char,Traits>&
922  operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
923 
924 
925  /*
926  * Implementation
927  *
928  */
929 
930  /*
931  * Variable arrays
932  *
933  * These arrays are usually allocated in the space, but if they are resized,
934  * the new array is allocated on the heap. The size (n) and capacity show
935  * where the array is allocated: it is in the space if and only if
936  * n==capacity.
937  *
938  */
939 
940  template<class Var>
942  VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
943 
944  template<class Var>
947  : n(n0) {
948  // Allocate from space
949  x = (n>0) ? home.alloc<Var>(n) : NULL;
950  }
951 
952  template<class Var>
955  n = a.n; x = a.x;
956  }
957 
958  template<class Var>
959  inline const VarArray<Var>&
961  n = a.n; x = a.x;
962  return *this;
963  }
964 
965  template<class Var>
966  forceinline int
967  VarArray<Var>::size(void) const {
968  return n;
969  }
970 
971  template<class Var>
974  assert((i >= 0) && (i < size()));
975  return x[i];
976  }
977 
978  template<class Var>
979  forceinline const Var&
981  assert((i >= 0) && (i < size()));
982  return x[i];
983  }
984 
985  template<class Var>
986  typename ArrayTraits<VarArgArray<Var> >::ArgsType
987  VarArray<Var>::slice(int start, int inc, int maxN) {
988  assert(n==0 || start < n);
989  if (n==0 || maxN<0)
990  maxN = n;
991  int s;
992  if (inc == 0)
993  s = n-start;
994  else if (inc > 0)
995  s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
996  else
997  s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
998  typename ArrayTraits<VarArgArray<Var> >::ArgsType r(std::min(maxN,s));
999  for (int i=0; i<r.size(); i++, start+=inc)
1000  r[i] = x[start];
1001  return r;
1002  }
1003 
1004  template<class Var>
1007  return x;
1008  }
1009 
1010  template<class Var>
1012  VarArray<Var>::begin(void) const {
1013  return x;
1014  }
1015 
1016  template<class Var>
1019  return x+n;
1020  }
1021 
1022  template<class Var>
1024  VarArray<Var>::end(void) const {
1025  return x+n;
1026  }
1027 
1028  template<class Var>
1031  return reverse_iterator(x+n);
1032  }
1033 
1034  template<class Var>
1037  return const_reverse_iterator(x+n);
1038  }
1039 
1040  template<class Var>
1043  return reverse_iterator(x);
1044  }
1045 
1046  template<class Var>
1048  VarArray<Var>::rend(void) const {
1049  return const_reverse_iterator(x);
1050  }
1051 
1052  template<class Var>
1053  forceinline void
1055  n = a.n;
1056  if (n > 0) {
1057  x = home.alloc<Var>(n);
1058  for (int i = n; i--;)
1059  x[i].update(home, share, a.x[i]);
1060  } else {
1061  x = NULL;
1062  }
1063  }
1064 
1065  template<class Var>
1066  forceinline bool
1068  for (int i = n; i--;)
1069  if (!x[i].assigned())
1070  return false;
1071  return true;
1072  }
1073 
1074  template<class Var>
1075  void*
1076  VarArray<Var>::operator new(size_t) {
1077  return NULL;
1078  }
1079 
1080  template<class Var>
1081  void
1082  VarArray<Var>::operator delete(void*,size_t) {
1083  }
1084 
1085  template<class Var>
1086  typename ArrayTraits<VarArray<Var> >::ArgsType
1088  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1089  for (int i=x.size(); i--;)
1090  r[i] = x[i];
1091  for (int i=y.size(); i--;)
1092  r[x.size()+i] = y[i];
1093  return r;
1094  }
1095 
1096  template<class Var>
1097  typename ArrayTraits<VarArray<Var> >::ArgsType
1099  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1100  for (int i=x.size(); i--;)
1101  r[i] = x[i];
1102  for (int i=y.size(); i--;)
1103  r[x.size()+i] = y[i];
1104  return r;
1105  }
1106 
1107  template<class Var>
1108  typename ArrayTraits<VarArray<Var> >::ArgsType
1110  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
1111  for (int i=x.size(); i--;)
1112  r[i] = x[i];
1113  for (int i=y.size(); i--;)
1114  r[x.size()+i] = y[i];
1115  return r;
1116  }
1117 
1118  template<class Var>
1119  typename ArrayTraits<VarArray<Var> >::ArgsType
1120  operator +(const VarArray<Var>& x, const Var& y) {
1121  typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+1);
1122  for (int i=x.size(); i--;)
1123  r[i] = x[i];
1124  r[x.size()] = y;
1125  return r;
1126  }
1127 
1128  template<class Var>
1129  typename ArrayTraits<VarArray<Var> >::ArgsType
1130  operator +(const Var& x, const VarArray<Var>& y) {
1131  typename ArrayTraits<VarArray<Var> >::ArgsType r(y.size()+1);
1132  r[0] = x;
1133  for (int i=y.size(); i--;)
1134  r[1+i] = y[i];
1135  return r;
1136  }
1137 
1138  /*
1139  * View arrays
1140  *
1141  */
1142 
1143  template<class View>
1144  forceinline
1145  ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
1146 
1147  template<class View>
1148  forceinline
1150  : n(n0) {
1151  x = (n>0) ? home.alloc<View>(n) : NULL;
1152  }
1153  template<class View>
1154  forceinline
1156  : n(n0) {
1157  x = (n>0) ? r.alloc<View>(n) : NULL;
1158  }
1159 
1160  template<class View>
1162  : n(a.size()) {
1163  if (n>0) {
1164  x = home.alloc<View>(n);
1165  for (int i = n; i--; )
1166  x[i] = a[i];
1167  } else {
1168  x = NULL;
1169  }
1170  }
1171  template<class View>
1173  : n(a.size()) {
1174  if (n>0) {
1175  x = r.alloc<View>(n);
1176  for (int i = n; i--; )
1177  x[i] = a[i];
1178  } else {
1179  x = NULL;
1180  }
1181  }
1182 
1183  template<class View>
1184  forceinline
1186  : n(a.n), x(a.x) {}
1187 
1188  template<class View>
1191  n = a.n; x = a.x;
1192  return *this;
1193  }
1194 
1195  template<class View>
1196  forceinline int
1198  return n;
1199  }
1200 
1201  template<class View>
1202  forceinline void
1204  n = n0;
1205  }
1206 
1207  template<class View>
1208  forceinline View&
1210  assert((i >= 0) && (i < size()));
1211  return x[i];
1212  }
1213 
1214  template<class View>
1215  forceinline const View&
1217  assert((i >= 0) && (i < size()));
1218  return x[i];
1219  }
1220 
1221  template<class View>
1224  return x;
1225  }
1226 
1227  template<class View>
1230  return x;
1231  }
1232 
1233  template<class View>
1236  return x+n;
1237  }
1238 
1239  template<class View>
1241  ViewArray<View>::end(void) const {
1242  return x+n;
1243  }
1244 
1245  template<class View>
1248  return reverse_iterator(x+n);
1249  }
1250 
1251  template<class View>
1254  return const_reverse_iterator(x+n);
1255  }
1256 
1257  template<class View>
1260  return reverse_iterator(x);
1261  }
1262 
1263  template<class View>
1266  return const_reverse_iterator(x);
1267  }
1268 
1269  template<class View>
1270  forceinline void
1272  x[i]=x[0]; x++; n--;
1273  }
1274 
1275  template<class View>
1276  forceinline void
1278  n--; x[i]=x[n];
1279  }
1280 
1281  template<class View>
1282  forceinline void
1284  assert(i>=0);
1285  x += i; n -= i;
1286  }
1287 
1288  template<class View>
1289  forceinline void
1291  assert(i<n);
1292  n = i+1;
1293  }
1294 
1295  template<class View>
1296  forceinline void
1298  // Move x[0] to x[i]
1299  x[i].cancel(home,p,pc);
1300  x[i]=x[0]; x++; n--;
1301  }
1302 
1303  template<class View>
1304  forceinline void
1306  // Move x[n-1] to x[i]
1307  x[i].cancel(home,p,pc);
1308  n--; x[i]=x[n];
1309  }
1310 
1311  template<class View>
1312  void
1314  // Drop elements from 0..i-1
1315  assert(i>=0);
1316  for (int j=i; j--; )
1317  x[j].cancel(home,p,pc);
1318  x += i; n -= i;
1319  }
1320 
1321  template<class View>
1322  void
1324  // Drop elements from i+1..n-1
1325  assert(i<n);
1326  for (int j=i+1; j<n; j++)
1327  x[j].cancel(home,p,pc);
1328  n = i+1;
1329  }
1330 
1331  template<class View>
1332  forceinline void
1334  // Move x[0] to x[i]
1335  x[i].cancel(home,a);
1336  x[i]=x[0]; x++; n--;
1337  }
1338 
1339  template<class View>
1340  forceinline void
1342  // Move x[n-1] to x[i]
1343  x[i].cancel(home,a);
1344  n--; x[i]=x[n];
1345  }
1346 
1347  template<class View>
1348  void
1350  // Drop elements from 0..i-1
1351  assert(i>=0);
1352  for (int j=i; j--; )
1353  x[j].cancel(home,a);
1354  x += i; n -= i;
1355  }
1356 
1357  template<class View>
1358  void
1360  // Drop elements from i+1..n-1
1361  assert(i<n);
1362  for (int j=i+1; j<n; j++)
1363  x[j].cancel(home,a);
1364  n = i+1;
1365  }
1366 
1367  template<class View>
1368  void
1370  n = y.n;
1371  if (n > 0) {
1372  x = home.alloc<View>(n);
1373  for (int i = n; i--; )
1374  x[i].update(home, share, y.x[i]);
1375  } else {
1376  x = NULL;
1377  }
1378  }
1379 
1380  template<class View>
1381  void
1383  bool process) {
1384  for (int i = n; i--; )
1385  x[i].subscribe(home,p,pc,process);
1386  }
1387 
1388  template<class View>
1389  void
1391  for (int i = n; i--; )
1392  x[i].cancel(home,p,pc);
1393  }
1394 
1395  template<class View>
1396  void
1398  for (int i = n; i--; )
1399  x[i].subscribe(home,a);
1400  }
1401 
1402  template<class View>
1403  void
1405  for (int i = n; i--; )
1406  x[i].cancel(home,a);
1407  }
1408 
1409  template<class View>
1410  forceinline bool
1412  for (int i = n; i--;)
1413  if (!x[i].assigned())
1414  return false;
1415  return true;
1416  }
1417 
1418  template<class View>
1419  forceinline bool
1420  __before(const View& x, const View& y) {
1421  return before(x,y);
1422  }
1423 
1424  template<class View> template<class X>
1425  forceinline bool
1426  ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
1427  return __before(a,b);
1428  }
1429 
1430  template<class View>
1431  void
1432  ViewArray<View>::sort(View* y, int m) {
1433  ViewLess<View> vl;
1434  Support::quicksort<View,ViewLess<View> >(y,m,vl);
1435  }
1436 
1437  template<class X, class Y>
1438  forceinline bool
1439  __same(const X& x, const Y& y) {
1440  return same(x,y);
1441  }
1442  template<class X, class Y>
1443  forceinline bool
1444  __shared(const X& x, const Y& y) {
1445  return shared(x,y);
1446  }
1447 
1448  template<class View>
1449  bool
1450  ViewArray<View>::same(const Space& home) const {
1451  if (n < 2)
1452  return false;
1453  Region r(home);
1454  View* y = r.alloc<View>(n);
1455  for (int i = n; i--; )
1456  y[i] = x[i];
1457  sort(y,n);
1458  for (int i = n-1; i--; )
1459  if (!y[i].assigned() && __same(y[i+1],y[i])) {
1460  r.free<View>(y,n);
1461  return true;
1462  }
1463  r.free<View>(y,n);
1464  return false;
1465  }
1466 
1467  template<class View>
1468  bool
1469  ViewArray<View>::same(const Space&, const View& y) const {
1470  if (y.assigned())
1471  return false;
1472  for (int i = n; i--; )
1473  if (__same(x[i],y))
1474  return true;
1475  return false;
1476  }
1477 
1478  template<class View>
1479  void
1481  if (n < 2)
1482  return;
1483  sort(x,n);
1484  int j = 0;
1485  for (int i = 1; i<n; i++)
1486  if (!__same(x[j],x[i]))
1487  x[++j] = x[i];
1488  n = j+1;
1489  }
1490 
1491  template<class View>
1492  bool
1493  ViewArray<View>::shared(const Space& home) const {
1494  if (n < 2)
1495  return false;
1496  Region r(home);
1497  View* y = r.alloc<View>(n);
1498  for (int i = n; i--; )
1499  y[i] = x[i];
1500  sort(y,n);
1501  for (int i = n-1; i--; )
1502  if (!y[i].assigned() && __shared(y[i+1],y[i])) {
1503  r.free<View>(y,n);
1504  return true;
1505  }
1506  r.free<View>(y,n);
1507  return false;
1508  }
1509 
1510  template<class View> template<class ViewY>
1511  bool
1512  ViewArray<View>::shared(const Space&, const ViewY& y) const {
1513  if (y.assigned())
1514  return false;
1515  for (int i = n; i--; )
1516  if (!x[i].assigned() && __shared(x[i],y))
1517  return true;
1518  return false;
1519  }
1520 
1521  template<class View> template<class ViewY>
1522  bool
1523  ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
1524  if ((size() < 1) || (y.size() < 1))
1525  return false;
1526  Region r(home);
1527  View* xs = r.alloc<View>(size());
1528  for (int i=size(); i--; )
1529  xs[i] = x[i];
1530  ViewLess<View> xvl;
1531  Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
1532  ViewY* ys = r.alloc<ViewY>(y.size());
1533  for (int j=y.size(); j--; )
1534  ys[j] = y[j];
1535  ViewLess<ViewY> yvl;
1536  Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
1537  {
1538  int i=0, j=0;
1539  while ((i < size()) && (j < y.size()))
1540  if (!x[i].assigned() && __shared(x[i],y[j])) {
1541  r.free<View>(xs,size());
1542  r.free<ViewY>(ys,y.size());
1543  return true;
1544  } else if (before(x[i],y[j])) {
1545  i++;
1546  } else {
1547  j++;
1548  }
1549  }
1550  r.free<View>(xs,size());
1551  r.free<ViewY>(ys,y.size());
1552  return false;
1553  }
1554 
1555  template<class View>
1556  void*
1557  ViewArray<View>::operator new(size_t) {
1558  return NULL;
1559  }
1560 
1561  template<class View>
1562  void
1563  ViewArray<View>::operator delete(void*,size_t) {
1564  }
1565 
1566 
1567  /*
1568  * Argument arrays: base class
1569  *
1570  */
1571 
1572  template<class T>
1573  forceinline T*
1575  return (n > onstack_size) ?
1576  heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
1577  }
1578 
1579  template<class T>
1580  forceinline void
1582  if (n+i >= capacity) {
1583  assert(n+i >= onstack_size);
1584  int newCapacity = (3*capacity)/2;
1585  if (newCapacity <= n+i)
1586  newCapacity = n+i;
1587  T* newA = allocate(newCapacity);
1588  heap.copy<T>(newA,a,n);
1589  if (capacity > onstack_size)
1590  heap.free(a,capacity);
1591  capacity = newCapacity;
1592  a = newA;
1593  }
1594  }
1595 
1596  template<class T>
1597  forceinline
1599  : n(0), capacity(onstack_size), a(allocate(0)) {}
1600 
1601  template<class T>
1602  forceinline
1604  : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
1605 
1606  template<class T>
1607  inline
1609  : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
1610  heap.copy<T>(a,aa.a,n);
1611  }
1612 
1613  template<class T>
1614  forceinline
1616  if (capacity > onstack_size)
1617  heap.free(a,capacity);
1618  }
1619 
1620  template<class T>
1623  if (&aa != this) {
1624  if (capacity > onstack_size)
1625  heap.free(a,capacity);
1626  n = aa.n;
1627  capacity = (n < onstack_size ? onstack_size : n);
1628  a = allocate(aa.n);
1629  heap.copy<T>(a,aa.a,n);
1630  }
1631  return *this;
1632  }
1633 
1634  template<class T>
1635  forceinline int
1637  return n;
1638  }
1639 
1640  template<class T>
1641  forceinline T&
1643  assert((i>=0) && (i < n));
1644  return a[i];
1645  }
1646 
1647  template<class T>
1648  forceinline const T&
1650  assert((i>=0) && (i < n));
1651  return a[i];
1652  }
1653 
1654  template<class T>
1657  return a;
1658  }
1659 
1660  template<class T>
1663  return a;
1664  }
1665 
1666  template<class T>
1669  return a+n;
1670  }
1671 
1672  template<class T>
1674  ArgArrayBase<T>::end(void) const {
1675  return a+n;
1676  }
1677 
1678  template<class T>
1681  return reverse_iterator(a+n);
1682  }
1683 
1684  template<class T>
1687  return const_reverse_iterator(a+n);
1688  }
1689 
1690  template<class T>
1693  return reverse_iterator(a);
1694  }
1695 
1696  template<class T>
1699  return const_reverse_iterator(a);
1700  }
1701 
1702  template<class T> template<class A>
1703  A
1704  ArgArrayBase<T>::slice(int start, int inc, int maxN) {
1705  assert(n==0 || start < n);
1706  if (n==0 || maxN<0)
1707  maxN = n;
1708  int s;
1709  if (inc == 0)
1710  s = n-start;
1711  else if (inc > 0)
1712  s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
1713  else
1714  s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
1715  A r(std::min(maxN,s));
1716  for (int i=0; i<r.size(); i++, start+=inc)
1717  new (&r[i]) T(a[start]);
1718  return r;
1719  }
1720 
1721  template<class T> template<class A>
1722  inline A&
1724  resize(1);
1725  new (&a[n++]) T(x);
1726  return static_cast<A&>(*this);
1727  }
1728 
1729  template<class T> template<class A>
1730  inline A&
1732  resize(x.size());
1733  for (int i=0; i<x.size(); i++)
1734  new (&a[n++]) T(x[i]);
1735  return static_cast<A&>(*this);
1736  }
1737 
1738  template<class T> template<class A>
1739  inline A
1741  A r(n+x.n);
1742  for (int i=n; i--;)
1743  new (&r[i]) T(a[i]);
1744  for (int i=x.n; i--;)
1745  new (&r[n+i]) T(x.a[i]);
1746  return r;
1747  }
1748 
1749  template<class T> template<class A>
1750  inline A
1751  ArgArrayBase<T>::concat(const T& x) const {
1752  A r(n+1);
1753  for (int i=n; i--;)
1754  new (&r[i]) T(a[i]);
1755  new (&r[n]) T(x);
1756  return r;
1757  }
1758 
1759  /*
1760  * Argument arrays for primitive types
1761  *
1762  */
1763 
1764  template<class T>
1765  forceinline
1767 
1768  template<class T>
1769  forceinline
1771 
1772  template<class T>
1774  : ArgArrayBase<T>(n) {
1775  va_list args;
1776  va_start(args, a0);
1777  a[0] = a0;
1778  for (int i = 1; i < n; i++)
1779  a[i] = va_arg(args,T);
1780  va_end(args);
1781  }
1782 
1783  template<class T>
1784  PrimArgArray<T>::PrimArgArray(int n, const T* a0)
1785  : ArgArrayBase<T>(n) {
1786  for (int i=n; i--; )
1787  a[i] = a0[i];
1788  }
1789 
1790  template<class T>
1791  forceinline
1793  : ArgArrayBase<T>(aa) {}
1794 
1795  template<class T>
1796  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType
1797  PrimArgArray<T>::slice(int start, int inc, int maxN) {
1798  return ArgArrayBase<T>::template slice
1799  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>
1800  (start,inc,maxN);
1801  }
1802 
1803  template<class T>
1804  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1806  return
1808  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1809  }
1810 
1811  template<class T>
1812  forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
1814  return
1816  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
1817  }
1818 
1819  template<class T>
1820  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1822  return x.template concat
1823  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1824  }
1825 
1826  template<class T>
1827  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1828  operator +(const PrimArgArray<T>& x, const T& y) {
1829  return x.template concat
1830  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1831  }
1832 
1833  template<class T>
1834  typename ArrayTraits<PrimArgArray<T> >::ArgsType
1835  operator +(const T& x, const PrimArgArray<T>& y) {
1836  return PrimArgArray<T>(1,x).template concat
1837  <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
1838  }
1839 
1840 
1841  /*
1842  * Argument arrays for non-primitive types
1843  *
1844  */
1845 
1846  template<class T>
1847  forceinline
1849 
1850  template<class T>
1851  forceinline
1853 
1854  template<class T>
1855  ArgArray<T>::ArgArray(int n, const T* a0)
1856  : ArgArrayBase<T>(n) {
1857  for (int i=n; i--; )
1858  a[i] = a0[i];
1859  }
1860 
1861  template<class T>
1862  forceinline
1864  : ArgArrayBase<T>(aa) {}
1865 
1866  template<class T>
1867  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType
1868  ArgArray<T>::slice(int start, int inc, int maxN) {
1869  return ArgArrayBase<T>::template slice
1870  <typename ArrayTraits<ArgArray<T> >::ArgsType>
1871  (start,inc,maxN);
1872  }
1873 
1874  template<class T>
1875  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1877  return
1879  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1880  }
1881 
1882  template<class T>
1883  forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
1885  return
1887  <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
1888  }
1889 
1890  template<class T>
1891  typename ArrayTraits<ArgArray<T> >::ArgsType
1892  operator +(const ArgArray<T>& x, const ArgArray<T>& y) {
1893  return x.template concat
1894  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1895  }
1896 
1897  template<class T>
1898  typename ArrayTraits<ArgArray<T> >::ArgsType
1899  operator +(const ArgArray<T>& x, const T& y) {
1900  return x.template concat
1901  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1902  }
1903 
1904  template<class T>
1905  typename ArrayTraits<ArgArray<T> >::ArgsType
1906  operator +(const T& x, const ArgArray<T>& y) {
1907  ArgArray<T> xa(1);
1908  xa[0] = x;
1909  return xa.template concat
1910  <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
1911  }
1912 
1913  /*
1914  * Argument arrays for variables
1915  *
1916  */
1917 
1918  template<class Var>
1919  forceinline
1921 
1922  template<class Var>
1923  forceinline
1925 
1926  template<class Var>
1927  forceinline
1929  : ArgArrayBase<Var>(aa) {}
1930 
1931  template<class Var>
1932  inline
1934  : ArgArrayBase<Var>(x.size()) {
1935  for (int i=x.size(); i--; )
1936  a[i]=x[i];
1937  }
1938 
1939  template<class Var>
1940  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType
1941  VarArgArray<Var>::slice(int start, int inc, int maxN) {
1942  return ArgArrayBase<Var>::template slice
1943  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>
1944  (start,inc,maxN);
1945  }
1946 
1947  template<class Var>
1948  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
1950  return
1952  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
1953  }
1954 
1955  template<class Var>
1956  forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
1958  return
1960  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
1961  }
1962 
1963  template<class Var>
1964  typename ArrayTraits<VarArgArray<Var> >::ArgsType
1966  return x.template concat
1967  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
1968  }
1969 
1970  template<class Var>
1971  typename ArrayTraits<VarArgArray<Var> >::ArgsType
1972  operator +(const VarArgArray<Var>& x, const Var& y) {
1973  return x.template concat
1974  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
1975  }
1976 
1977  template<class Var>
1978  typename ArrayTraits<VarArgArray<Var> >::ArgsType
1979  operator +(const Var& x, const VarArgArray<Var>& y) {
1980  VarArgArray<Var> xa(1);
1981  xa[0] = x;
1982  return xa.template concat
1983  <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
1984  }
1985 
1986  template<class Var>
1987  forceinline bool
1989  return a.varimp() < b.varimp();
1990  }
1991 
1992  template<class Var>
1993  forceinline bool
1995  for (int i = n; i--;)
1996  if (!a[i].assigned())
1997  return false;
1998  return true;
1999  }
2000 
2001  template<class Var>
2002  bool
2003  VarArgArray<Var>::same(const Space& home) const {
2004  if (n < 2)
2005  return false;
2006  Region r(home);
2007  Var* y = r.alloc<Var>(n);
2008  for (int i = n; i--; )
2009  y[i] = a[i];
2010  VarLess vl;
2011  Support::quicksort<Var,VarLess>(y,n,vl);
2012  for (int i = n-1; i--; )
2013  if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) {
2014  r.free<Var>(y,n);
2015  return true;
2016  }
2017  r.free<Var>(y,n);
2018  return false;
2019  }
2020 
2021  template<class Var>
2022  bool
2023  VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
2024  int m = n + y.n;
2025  if (m < 2)
2026  return false;
2027  Region r(home);
2028  Var* z = r.alloc<Var>(m);
2029  for (int i = n; i--; )
2030  z[i] = a[i];
2031  for (int i = y.n; i--; )
2032  z[i+n] = y.a[i];
2033  VarLess vl;
2034  Support::quicksort<Var,VarLess>(z,m,vl);
2035  for (int i = m-1; i--; )
2036  if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) {
2037  r.free<Var>(z,m);
2038  return true;
2039  }
2040  r.free<Var>(z,m);
2041  return false;
2042  }
2043 
2044  template<class Var>
2045  bool
2046  VarArgArray<Var>::same(const Space&, const Var& y) const {
2047  if (y.assigned())
2048  return false;
2049  for (int i = n; i--; )
2050  if (a[i].varimp() == y.varimp())
2051  return true;
2052  return false;
2053  }
2054 
2055 
2056 
2057 
2058 
2059 
2060  /*
2061  * Interdependent code
2062  *
2063  */
2064 
2065  template<class Var>
2066  inline
2068  : n(a.size()) {
2069  if (n>0) {
2070  x = home.alloc<Var>(n);
2071  for (int i=n; i--;)
2072  x[i] = a[i];
2073  } else {
2074  x = NULL;
2075  }
2076  }
2077 
2078 
2079  /*
2080  * Printing of arrays
2081  *
2082  */
2083  template<class Char, class Traits, class Var>
2084  std::basic_ostream<Char,Traits>&
2085  operator <<(std::basic_ostream<Char,Traits>& os,
2086  const VarArray<Var>& x) {
2087  std::basic_ostringstream<Char,Traits> s;
2088  s.copyfmt(os); s.width(0);
2089  s << '{';
2090  if (x.size() > 0) {
2091  s << x[0];
2092  for (int i=1; i<x.size(); i++)
2093  s << ", " << x[i];
2094  }
2095  s << '}';
2096  return os << s.str();
2097  }
2098 
2099  template<class Char, class Traits, class View>
2100  std::basic_ostream<Char,Traits>&
2101  operator <<(std::basic_ostream<Char,Traits>& os,
2102  const ViewArray<View>& x) {
2103  std::basic_ostringstream<Char,Traits> s;
2104  s.copyfmt(os); s.width(0);
2105  s << '{';
2106  if (x.size() > 0) {
2107  s << x[0];
2108  for (int i=1; i<x.size(); i++)
2109  s << ", " << x[i];
2110  }
2111  s << '}';
2112  return os << s.str();
2113  }
2114 
2115  template<class Char, class Traits, class T>
2116  std::basic_ostream<Char,Traits>&
2117  operator <<(std::basic_ostream<Char,Traits>& os,
2118  const ArgArrayBase<T>& x) {
2119  std::basic_ostringstream<Char,Traits> s;
2120  s.copyfmt(os); s.width(0);
2121  s << '{';
2122  if (x.size() > 0) {
2123  s << x[0];
2124  for (int i=1; i<x.size(); i++)
2125  s << ", " << x[i];
2126  }
2127  s << '}';
2128  return os << s.str();
2129  }
2130 
2131 }
2132 
2133 // STATISTICS: kernel-other