Generated on Thu Apr 11 13:58:56 2019 for Gecode by doxygen 1.6.3

array.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Gregory Crosswhite <gcross@phys.washington.edu>
00009  *
00010  *  Copyright:
00011  *     Gregory Crosswhite, 2011
00012  *     Christian Schulte, 2003
00013  *     Guido Tack, 2004
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <iostream>
00041 #include <iterator>
00042 #include <vector>
00043 #include <sstream>
00044 #include <initializer_list>
00045 
00046 namespace Gecode { namespace Kernel {
00047 
00049   template<class View>
00050   class ViewOcc {
00051   public:
00053     View x;
00055     int i;
00057     bool operator <(const ViewOcc& y) const;
00058   };
00059 
00060   template<class View>
00061   forceinline bool
00062   ViewOcc<View>::operator <(const ViewOcc& y) const {
00063     return x < y.x;
00064   }
00065 
00067   GECODE_KERNEL_EXPORT
00068   bool duplicates(void** p, int n);
00069 
00071   GECODE_KERNEL_EXPORT
00072   bool duplicates(void** p, int n, void** q, int m);
00073 
00074 }}
00075 
00076 namespace Gecode {
00077 
00078   template<class Var> class VarArray;
00079   template<class Var> class VarArgArray;
00080 
00093   template<class A>
00094   class ArrayTraits {};
00095 
00111   template<class Var>
00112   class VarArray {
00113   protected:
00115     int n;
00117     Var* x;
00118   public:
00120 
00121 
00122     typedef Var value_type;
00124     typedef Var& reference;
00126     typedef const Var& const_reference;
00128     typedef Var* pointer;
00130     typedef const Var* const_pointer;
00132     typedef Var* iterator;
00134     typedef const Var* const_iterator;
00136     typedef std::reverse_iterator<Var*> reverse_iterator;
00138     typedef std::reverse_iterator<const Var*> const_reverse_iterator;
00140 
00142 
00143 
00144 
00145     VarArray(void);
00147     VarArray(Space& home, int m);
00149     VarArray(Space& home, const VarArgArray<Var>&);
00151     VarArray(const VarArray<Var>& a);
00153     const VarArray<Var>& operator =(const VarArray<Var>& a);
00155 
00157 
00158 
00159     int size(void) const;
00161 
00163 
00164 
00165     Var& operator [](int i);
00167     const Var& operator [](int i) const;
00173     typename ArrayTraits<VarArgArray<Var>>::ArgsType
00174     slice(int start, int inc=1, int n=-1);
00176 
00178 
00179 
00180     iterator begin(void);
00182     const_iterator begin(void) const;
00184     iterator end(void);
00186     const_iterator end(void) const;
00188     reverse_iterator rbegin(void);
00190     const_reverse_iterator rbegin(void) const;
00192     reverse_iterator rend(void);
00194     const_reverse_iterator rend(void) const;
00196 
00198     bool assigned(void) const;
00199 
00201 
00202 
00203     void update(Space& home, VarArray<Var>& a);
00205   private:
00206     static void* operator new(size_t) throw();
00207     static void  operator delete(void*,size_t);
00208   };
00209 
00213   template<class T>
00214   typename ArrayTraits<VarArray<T>>::ArgsType
00215   operator +(const VarArray<T>& x, const VarArgArray<T>& y);
00216 
00220   template<class T>
00221   typename ArrayTraits<VarArray<T>>::ArgsType
00222   operator +(const VarArray<T>& x, const VarArray<T>& y);
00223 
00227   template<class T>
00228   typename ArrayTraits<VarArray<T>>::ArgsType
00229   operator +(const VarArgArray<T>& x, const VarArray<T>& y);
00230 
00234   template<class T>
00235   typename ArrayTraits<VarArray<T>>::ArgsType
00236   operator +(const VarArray<T>& x, const T& y);
00237 
00241   template<class T>
00242   typename ArrayTraits<VarArray<T>>::ArgsType
00243   operator +(const T& x, const VarArray<T>& y);
00244 
00252   template<class View>
00253   class ViewArray {
00254   private:
00256     int  n;
00258     View* x;
00259   public:
00261 
00262 
00263     typedef View value_type;
00265     typedef View& reference;
00267     typedef const View& const_reference;
00269     typedef View* pointer;
00271     typedef const View* const_pointer;
00273     typedef View* iterator;
00275     typedef const View* const_iterator;
00277     typedef std::reverse_iterator<View*> reverse_iterator;
00279     typedef std::reverse_iterator<const View*> const_reverse_iterator;
00281 
00283 
00284 
00285     ViewArray(void);
00287     ViewArray(Space& home, int m);
00289     ViewArray(Region& r, int m);
00291     ViewArray(const ViewArray<View>& a);
00293     ViewArray(Space& home, const ViewArray<View>& a);
00295     ViewArray(Region& r, const ViewArray<View>& a);
00297     const ViewArray<View>& operator =(const ViewArray<View>& a);
00304     template<class Var>
00305     ViewArray(Space& home, const VarArgArray<Var>& a)
00306       : n(a.size()) {
00307       // This may not be in the hpp file (to satisfy the MS compiler)
00308       if (n>0) {
00309         x = home.alloc<View>(n);
00310         for (int i=0; i<n; i++)
00311           x[i]=a[i];
00312       } else {
00313         x = nullptr;
00314       }
00315     }
00322     template<class Var>
00323     ViewArray(Region& r, const VarArgArray<Var>& a)
00324       : n(a.size()) {
00325       // This may not be in the hpp file (to satisfy the MS compiler)
00326       if (n>0) {
00327         x = r.alloc<View>(n);
00328         for (int i=0; i<n; i++)
00329           x[i]=a[i];
00330       } else {
00331         x = nullptr;
00332       }
00333     }
00335 
00337 
00338 
00339     int size(void) const;
00341     void size(int n);
00343 
00345 
00346 
00347     View& operator [](int i);
00349     const View& operator [](int i) const;
00351 
00353 
00354 
00355     iterator begin(void);
00357     const_iterator begin(void) const;
00359     iterator end(void);
00361     const_iterator end(void) const;
00363     reverse_iterator rbegin(void);
00365     const_reverse_iterator rbegin(void) const;
00367     reverse_iterator rend(void);
00369     const_reverse_iterator rend(void) const;
00371 
00373 
00374 
00381     void subscribe(Space& home, Propagator& p, PropCond pc,
00382                    bool schedule=true);
00384     void cancel(Space& home, Propagator& p, PropCond pc);
00386     void subscribe(Space& home, Advisor& a);
00388     void cancel(Space& home, Advisor& a);
00390     void reschedule(Space& home, Propagator& p, PropCond pc);
00392 
00394 
00395 
00396     void update(Space& home, ViewArray<View>& a);
00398 
00399 
00401 
00402 
00403     void move_fst(int i);
00405     void move_lst(int i);
00411     void move_fst(int i, Space& home, Propagator& p, PropCond pc);
00417     void move_lst(int i, Space& home, Propagator& p, PropCond pc);
00423     void move_fst(int i, Space& home, Advisor& a);
00429     void move_lst(int i, Space& home, Advisor& a);
00431 
00433 
00434 
00435     void drop_fst(int i);
00437     void drop_lst(int i);
00443     void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
00450     void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
00456     void drop_fst(int i, Space& home, Advisor& a);
00462     void drop_lst(int i, Space& home, Advisor& a);
00464 
00466     bool assigned(void) const;
00467 
00469 
00470 
00475     bool same(void) const;
00481     bool same(const View& y) const;
00483     void unique(void);
00485   private:
00486     static void* operator new(size_t) throw();
00487     static void  operator delete(void*,size_t);
00488   };
00489 
00490 
00497   template<class ViewX, class ViewY>
00498   bool shared(ViewArray<ViewX> x, ViewArray<ViewY> y);
00505   template<class ViewX, class ViewY>
00506   bool shared(ViewArray<ViewX> x, ViewY y);
00513   template<class ViewX, class ViewY>
00514   bool shared(ViewX x, ViewArray<ViewY> y);
00521   template<class View>
00522   bool shared(ViewArray<View> x);
00523 
00524 
00536   template<class T>
00537   class ArgArrayBase {
00538   protected:
00540     int n;
00542     int capacity;
00544     T*  a;
00546     static const int onstack_size = 16;
00548     T onstack[onstack_size];
00550     T* allocate(int n);
00552     void resize(int i);
00554     template<class A>
00555     A concat(const ArgArrayBase<T>& x) const;
00557     template<class A>
00558     A concat(const T& x) const;
00560     template<class A>
00561     A& append(const T& x);
00563     template<class A>
00564     A& append(const ArgArrayBase<T>& x);
00570     template<class A>
00571     A slice(int start, int inc=1, int n=-1);
00572   public:
00574 
00575 
00576     typedef T value_type;
00578     typedef T& reference;
00580     typedef const T& const_reference;
00582     typedef T* pointer;
00584     typedef const T* const_pointer;
00586     typedef T* iterator;
00588     typedef const T* const_iterator;
00590     typedef std::reverse_iterator<T*> reverse_iterator;
00592     typedef std::reverse_iterator<const T*> const_reverse_iterator;
00594 
00596 
00597 
00598     ArgArrayBase(void);
00600     explicit ArgArrayBase(int n);
00602     ArgArrayBase(const ArgArrayBase<T>& a);
00604     const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
00606     ArgArrayBase(const std::vector<T>& a);
00608     ArgArrayBase(std::initializer_list<T> a);
00610     template<class InputIterator>
00611     ArgArrayBase(InputIterator first, InputIterator last);
00613 
00615 
00616 
00617     int size(void) const;
00619 
00621 
00622 
00623     T& operator [](int i);
00625     const T& operator [](int i) const;
00627 
00629 
00630 
00631     iterator begin(void);
00633     const_iterator begin(void) const;
00635     iterator end(void);
00637     const_iterator end(void) const;
00639     reverse_iterator rbegin(void);
00641     const_reverse_iterator rbegin(void) const;
00643     reverse_iterator rend(void);
00645     const_reverse_iterator rend(void) const;
00647 
00649 
00650 
00651     ~ArgArrayBase(void);
00653   };
00654 
00655 
00656   template<class> class ArgArray;
00657 
00661   template<class T>
00662   typename ArrayTraits<ArgArray<T>>::ArgsType
00663   operator +(const ArgArray<T>& x, const ArgArray<T>& y);
00664 
00668   template<class T>
00669   typename ArrayTraits<ArgArray<T>>::ArgsType
00670   operator +(const ArgArray<T>& x, const T& y);
00671 
00675   template<class T>
00676   typename ArrayTraits<ArgArray<T>>::ArgsType
00677   operator +(const T& x, const ArgArray<T>& y);
00678 
00690   template<class T>
00691   class ArgArray : public ArgArrayBase<T> {
00692   protected:
00693     using ArgArrayBase<T>::a;
00694   public:
00695     using ArgArrayBase<T>::size;
00697 
00698 
00699     ArgArray(void);
00701     explicit ArgArray(int n);
00703     ArgArray(int n, const T* e);
00705     ArgArray(const ArgArray<T>& a);
00707     ArgArray(const std::vector<T>& a);
00709     ArgArray(std::initializer_list<T> a);
00711     template<class InputIterator>
00712     ArgArray(InputIterator first, InputIterator last);
00714 
00715 
00716 
00717     typename ArrayTraits<ArgArray<T>>::ArgsType
00718     slice(int start, int inc=1, int n=-1);
00720 
00721 
00722 
00723     typename ArrayTraits<ArgArray<T>>::ArgsType&
00724     operator <<(const T& x);
00726     typename ArrayTraits<ArgArray<T>>::ArgsType&
00727     operator <<(const ArgArray<T>& x);
00729 
00730     friend typename ArrayTraits<ArgArray<T>>::ArgsType
00731     operator + <>(const ArgArray<T>& x, const ArgArray<T>& y);
00732     friend typename ArrayTraits<ArgArray<T>>::ArgsType
00733     operator + <>(const ArgArray<T>& x, const T& y);
00734     friend
00735     typename ArrayTraits<ArgArray<T>>::ArgsType
00736     operator + <>(const T& x, const ArgArray<T>& y);
00737   };
00738 
00739   template<class> class VarArgArray;
00740 
00744   template<class Var>
00745   typename ArrayTraits<VarArgArray<Var>>::ArgsType
00746   operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
00747 
00751   template<class Var>
00752   typename ArrayTraits<VarArgArray<Var>>::ArgsType
00753   operator +(const VarArgArray<Var>& x, const Var& y);
00754 
00758   template<class Var>
00759   typename ArrayTraits<VarArgArray<Var>>::ArgsType
00760   operator +(const Var& x, const VarArgArray<Var>& y);
00761 
00773   template<class Var>
00774   class VarArgArray : public ArgArrayBase<Var> {
00775   protected:
00776     using ArgArrayBase<Var>::a;
00777     using ArgArrayBase<Var>::n;
00778   public:
00779     using ArgArrayBase<Var>::size;
00781 
00782 
00783     VarArgArray(void);
00785     explicit VarArgArray(int n);
00787     VarArgArray(const VarArgArray<Var>& a);
00789     VarArgArray(const VarArray<Var>& a);
00791     VarArgArray(const std::vector<Var>& a);
00793     VarArgArray(std::initializer_list<Var> a);
00795     template<class InputIterator>
00796     VarArgArray(InputIterator first, InputIterator last);
00798 
00799 
00800 
00801     typename ArrayTraits<VarArgArray<Var>>::ArgsType
00802     slice(int start, int inc=1, int n=-1);
00804 
00805 
00806 
00807     typename ArrayTraits<VarArgArray<Var>>::ArgsType&
00808     operator <<(const Var& x);
00810     typename ArrayTraits<VarArgArray<Var>>::ArgsType&
00811     operator <<(const VarArgArray<Var>& x);
00813 
00815     bool assigned(void) const;
00816 
00817     friend typename ArrayTraits<VarArgArray<Var>>::ArgsType
00818     operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
00819     friend typename ArrayTraits<VarArgArray<Var>>::ArgsType
00820     operator + <>(const VarArgArray<Var>& x, const Var& y);
00821     friend
00822     typename ArrayTraits<VarArgArray<Var>>::ArgsType
00823     operator + <>(const Var& x, const VarArgArray<Var>& y);
00824   };
00825 
00826 
00833   template<class Var>
00834   bool same(VarArgArray<Var> x, VarArgArray<Var> y);
00841   template<class Var>
00842   bool same(VarArgArray<Var> x, Var y);
00849   template<class Var>
00850   bool same(Var x, VarArgArray<Var> y);
00857   template<class Var>
00858   bool same(VarArgArray<Var> x);
00859 
00860 
00865   template<class Char, class Traits, class Var>
00866   std::basic_ostream<Char,Traits>&
00867   operator <<(std::basic_ostream<Char,Traits>& os,
00868              const VarArray<Var>& x);
00869 
00874   template<class Char, class Traits, class View>
00875   std::basic_ostream<Char,Traits>&
00876   operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
00877 
00882   template<class Char, class Traits, class T>
00883   std::basic_ostream<Char,Traits>&
00884   operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
00885 
00886 
00887   /*
00888    * Implementation
00889    *
00890    */
00891 
00892   /*
00893    * Variable arrays
00894    *
00895    * These arrays are allocated in the space.
00896    *
00897    */
00898 
00899   template<class Var>
00900   forceinline
00901   VarArray<Var>::VarArray(void) : n(0), x(nullptr) {}
00902 
00903   template<class Var>
00904   forceinline
00905   VarArray<Var>::VarArray(Space& home, int n0)
00906     : n(n0) {
00907     // Allocate from space
00908     x = (n>0) ? home.alloc<Var>(n) : nullptr;
00909   }
00910 
00911   template<class Var>
00912   forceinline
00913   VarArray<Var>::VarArray(const VarArray<Var>& a) {
00914     n = a.n; x = a.x;
00915   }
00916 
00917   template<class Var>
00918   inline const VarArray<Var>&
00919   VarArray<Var>::operator =(const VarArray<Var>& a) {
00920     n = a.n; x = a.x;
00921     return *this;
00922   }
00923 
00924   template<class Var>
00925   forceinline int
00926   VarArray<Var>::size(void) const {
00927     return n;
00928   }
00929 
00930   template<class Var>
00931   forceinline Var&
00932   VarArray<Var>::operator [](int i) {
00933     assert((i >= 0) && (i < size()));
00934     return x[i];
00935   }
00936 
00937   template<class Var>
00938   forceinline const Var&
00939   VarArray<Var>::operator [](int i) const {
00940     assert((i >= 0) && (i < size()));
00941     return x[i];
00942   }
00943 
00944   template<class Var>
00945   typename ArrayTraits<VarArgArray<Var>>::ArgsType
00946   VarArray<Var>::slice(int start, int inc, int maxN) {
00947     assert(n==0 || start < n);
00948     if (n==0 || maxN<0)
00949       maxN = n;
00950     int s;
00951     if (inc == 0)
00952       s = n-start;
00953     else if (inc > 0)
00954       s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
00955     else
00956       s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
00957     typename ArrayTraits<VarArgArray<Var>>::ArgsType r(std::min(maxN,s));
00958     for (int i=0; i<r.size(); i++, start+=inc)
00959       r[i] = x[start];
00960     return r;
00961   }
00962 
00963   template<class Var>
00964   forceinline typename VarArray<Var>::iterator
00965   VarArray<Var>::begin(void) {
00966     return x;
00967   }
00968 
00969   template<class Var>
00970   forceinline typename VarArray<Var>::const_iterator
00971   VarArray<Var>::begin(void) const {
00972     return x;
00973   }
00974 
00975   template<class Var>
00976   forceinline typename VarArray<Var>::iterator
00977   VarArray<Var>::end(void) {
00978     return x+n;
00979   }
00980 
00981   template<class Var>
00982   forceinline typename VarArray<Var>::const_iterator
00983   VarArray<Var>::end(void) const {
00984     return x+n;
00985   }
00986 
00987   template<class Var>
00988   forceinline typename VarArray<Var>::reverse_iterator
00989   VarArray<Var>::rbegin(void) {
00990     return reverse_iterator(x+n);
00991   }
00992 
00993   template<class Var>
00994   forceinline typename VarArray<Var>::const_reverse_iterator
00995   VarArray<Var>::rbegin(void) const {
00996     return const_reverse_iterator(x+n);
00997   }
00998 
00999   template<class Var>
01000   forceinline typename VarArray<Var>::reverse_iterator
01001   VarArray<Var>::rend(void) {
01002     return reverse_iterator(x);
01003   }
01004 
01005   template<class Var>
01006   forceinline typename VarArray<Var>::const_reverse_iterator
01007   VarArray<Var>::rend(void) const {
01008     return const_reverse_iterator(x);
01009   }
01010 
01011   template<class Var>
01012   forceinline void
01013   VarArray<Var>::update(Space& home, VarArray<Var>& a) {
01014     n = a.n;
01015     if (n > 0) {
01016       x = home.alloc<Var>(n);
01017       for (int i=0; i<n; i++)
01018         x[i].update(home, a.x[i]);
01019     } else {
01020       x = nullptr;
01021     }
01022   }
01023 
01024   template<class Var>
01025   forceinline bool
01026   VarArray<Var>::assigned(void) const {
01027     for (int i=0; i<n; i++)
01028       if (!x[i].assigned())
01029         return false;
01030     return true;
01031   }
01032 
01033   template<class Var>
01034   forceinline void*
01035   VarArray<Var>::operator new(size_t) throw() {
01036     return nullptr;
01037   }
01038 
01039   template<class Var>
01040   forceinline void
01041   VarArray<Var>::operator delete(void*,size_t) {
01042   }
01043 
01044   template<class Var>
01045   typename ArrayTraits<VarArray<Var>>::ArgsType
01046   operator +(const VarArray<Var>& x, const VarArray<Var>& y) {
01047     typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
01048     for (int i=0; i<x.size(); i++)
01049       r[i] = x[i];
01050     for (int i=0; i<y.size(); i++)
01051       r[x.size()+i] = y[i];
01052     return r;
01053   }
01054 
01055   template<class Var>
01056   typename ArrayTraits<VarArray<Var>>::ArgsType
01057   operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) {
01058     typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
01059     for (int i=0; i<x.size(); i++)
01060       r[i] = x[i];
01061     for (int i=0; i<y.size(); i++)
01062       r[x.size()+i] = y[i];
01063     return r;
01064   }
01065 
01066   template<class Var>
01067   typename ArrayTraits<VarArray<Var>>::ArgsType
01068   operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) {
01069     typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size());
01070     for (int i=0; i<x.size(); i++)
01071       r[i] = x[i];
01072     for (int i=0; i<y.size(); i++)
01073       r[x.size()+i] = y[i];
01074     return r;
01075   }
01076 
01077   template<class Var>
01078   typename ArrayTraits<VarArray<Var>>::ArgsType
01079   operator +(const VarArray<Var>& x, const Var& y) {
01080     typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+1);
01081     for (int i=0; i<x.size(); i++)
01082       r[i] = x[i];
01083     r[x.size()] = y;
01084     return r;
01085   }
01086 
01087   template<class Var>
01088   typename ArrayTraits<VarArray<Var>>::ArgsType
01089   operator +(const Var& x, const VarArray<Var>& y) {
01090     typename ArrayTraits<VarArray<Var>>::ArgsType r(y.size()+1);
01091     r[0] = x;
01092     for (int i=0; i<y.size(); i++)
01093       r[1+i] = y[i];
01094     return r;
01095   }
01096 
01097   /*
01098    * View arrays
01099    *
01100    */
01101 
01102   template<class View>
01103   forceinline
01104   ViewArray<View>::ViewArray(void) : n(0), x(nullptr) {}
01105 
01106   template<class View>
01107   forceinline
01108   ViewArray<View>::ViewArray(Space& home, int n0)
01109     : n(n0) {
01110     x = (n>0) ? home.alloc<View>(n) : nullptr;
01111   }
01112   template<class View>
01113   forceinline
01114   ViewArray<View>::ViewArray(Region& r, int n0)
01115     : n(n0) {
01116     x = (n>0) ? r.alloc<View>(n) : nullptr;
01117   }
01118 
01119   template<class View>
01120   ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
01121     : n(a.size()) {
01122     if (n>0) {
01123       x = home.alloc<View>(n);
01124       for (int i=0; i<n; i++)
01125         x[i] = a[i];
01126     } else {
01127       x = nullptr;
01128     }
01129   }
01130   template<class View>
01131   ViewArray<View>::ViewArray(Region& r, const ViewArray<View>& a)
01132     : n(a.size()) {
01133     if (n>0) {
01134       x = r.alloc<View>(n);
01135       for (int i=0; i<n; i++)
01136         x[i] = a[i];
01137     } else {
01138       x = nullptr;
01139     }
01140   }
01141 
01142   template<class View>
01143   forceinline
01144   ViewArray<View>::ViewArray(const ViewArray<View>& a)
01145     : n(a.n), x(a.x) {}
01146 
01147   template<class View>
01148   forceinline const ViewArray<View>&
01149   ViewArray<View>::operator =(const ViewArray<View>& a) {
01150     n = a.n; x = a.x;
01151     return *this;
01152   }
01153 
01154   template<class View>
01155   forceinline int
01156   ViewArray<View>::size(void) const {
01157     return n;
01158   }
01159 
01160   template<class View>
01161   forceinline void
01162   ViewArray<View>::size(int n0) {
01163     n = n0;
01164   }
01165 
01166   template<class View>
01167   forceinline View&
01168   ViewArray<View>::operator [](int i) {
01169     assert((i >= 0) && (i < size()));
01170     return x[i];
01171   }
01172 
01173   template<class View>
01174   forceinline const View&
01175   ViewArray<View>::operator [](int i) const {
01176     assert((i >= 0) && (i < size()));
01177     return x[i];
01178   }
01179 
01180   template<class View>
01181   forceinline typename ViewArray<View>::iterator
01182   ViewArray<View>::begin(void) {
01183     return x;
01184   }
01185 
01186   template<class View>
01187   forceinline typename ViewArray<View>::const_iterator
01188   ViewArray<View>::begin(void) const {
01189     return x;
01190   }
01191 
01192   template<class View>
01193   forceinline typename ViewArray<View>::iterator
01194   ViewArray<View>::end(void) {
01195     return x+n;
01196   }
01197 
01198   template<class View>
01199   forceinline typename ViewArray<View>::const_iterator
01200   ViewArray<View>::end(void) const {
01201     return x+n;
01202   }
01203 
01204   template<class View>
01205   forceinline typename ViewArray<View>::reverse_iterator
01206   ViewArray<View>::rbegin(void) {
01207     return reverse_iterator(x+n);
01208   }
01209 
01210   template<class View>
01211   forceinline typename ViewArray<View>::const_reverse_iterator
01212   ViewArray<View>::rbegin(void) const {
01213     return const_reverse_iterator(x+n);
01214   }
01215 
01216   template<class View>
01217   forceinline typename ViewArray<View>::reverse_iterator
01218   ViewArray<View>::rend(void) {
01219     return reverse_iterator(x);
01220   }
01221 
01222   template<class View>
01223   forceinline typename ViewArray<View>::const_reverse_iterator
01224   ViewArray<View>::rend(void) const {
01225     return const_reverse_iterator(x);
01226   }
01227 
01228   template<class View>
01229   forceinline void
01230   ViewArray<View>::move_fst(int i) {
01231     x[i]=x[0]; x++; n--;
01232   }
01233 
01234   template<class View>
01235   forceinline void
01236   ViewArray<View>::move_lst(int i) {
01237     n--; x[i]=x[n];
01238   }
01239 
01240   template<class View>
01241   forceinline void
01242   ViewArray<View>::drop_fst(int i) {
01243     assert(i>=0);
01244     x += i; n -= i;
01245   }
01246 
01247   template<class View>
01248   forceinline void
01249   ViewArray<View>::drop_lst(int i) {
01250     assert(i<n);
01251     n = i+1;
01252   }
01253 
01254   template<class View>
01255   forceinline void
01256   ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
01257     // Move x[0] to x[i]
01258     x[i].cancel(home,p,pc);
01259     x[i]=x[0]; x++; n--;
01260   }
01261 
01262   template<class View>
01263   forceinline void
01264   ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
01265     // Move x[n-1] to x[i]
01266     x[i].cancel(home,p,pc);
01267     n--; x[i]=x[n];
01268   }
01269 
01270   template<class View>
01271   void
01272   ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
01273     // Drop elements from 0..i-1
01274     assert(i>=0);
01275     for (int j=0; j<i; j++)
01276       x[j].cancel(home,p,pc);
01277     x += i; n -= i;
01278   }
01279 
01280   template<class View>
01281   void
01282   ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
01283     // Drop elements from i+1..n-1
01284     assert(i<n);
01285     for (int j=i+1; j<n; j++)
01286       x[j].cancel(home,p,pc);
01287     n = i+1;
01288   }
01289 
01290   template<class View>
01291   forceinline void
01292   ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
01293     // Move x[0] to x[i]
01294     x[i].cancel(home,a);
01295     x[i]=x[0]; x++; n--;
01296   }
01297 
01298   template<class View>
01299   forceinline void
01300   ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
01301     // Move x[n-1] to x[i]
01302     x[i].cancel(home,a);
01303     n--; x[i]=x[n];
01304   }
01305 
01306   template<class View>
01307   void
01308   ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
01309     // Drop elements from 0..i-1
01310     assert(i>=0);
01311     for (int j=0; j<i; j++)
01312       x[j].cancel(home,a);
01313     x += i; n -= i;
01314   }
01315 
01316   template<class View>
01317   void
01318   ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
01319     // Drop elements from i+1..n-1
01320     assert(i<n);
01321     for (int j=i+1; j<n; j++)
01322       x[j].cancel(home,a);
01323     n = i+1;
01324   }
01325 
01326   template<class View>
01327   void
01328   ViewArray<View>::update(Space& home, ViewArray<View>& y) {
01329     n = y.n;
01330     if (n > 0) {
01331       x = home.alloc<View>(n);
01332       for (int i=0; i<n; i++)
01333         x[i].update(home, y.x[i]);
01334     } else {
01335       x = nullptr;
01336     }
01337   }
01338 
01339   template<class View>
01340   void
01341   ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
01342                              bool schedule) {
01343     for (int i=0; i<n; i++)
01344       x[i].subscribe(home,p,pc,schedule);
01345   }
01346 
01347   template<class View>
01348   void
01349   ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
01350     for (int i=0; i<n; i++)
01351       x[i].cancel(home,p,pc);
01352   }
01353 
01354   template<class View>
01355   void
01356   ViewArray<View>::subscribe(Space& home, Advisor& a) {
01357     for (int i=0; i<n; i++)
01358       x[i].subscribe(home,a);
01359   }
01360 
01361   template<class View>
01362   void
01363   ViewArray<View>::cancel(Space& home, Advisor& a) {
01364     for (int i=0; i<n; i++)
01365       x[i].cancel(home,a);
01366   }
01367 
01368   template<class View>
01369   void
01370   ViewArray<View>::reschedule(Space& home, Propagator& p, PropCond pc) {
01371     for (int i=0; i<n; i++)
01372       x[i].reschedule(home,p,pc);
01373   }
01374 
01375   template<class View>
01376   forceinline bool
01377   ViewArray<View>::assigned(void) const {
01378     for (int i=0; i<n; i++)
01379       if (!x[i].assigned())
01380         return false;
01381     return true;
01382   }
01383 
01384   template<class View>
01385   bool
01386   ViewArray<View>::same(void) const {
01387     if (n < 2)
01388       return false;
01389     Region r;
01390     View* y = r.alloc<View>(n);
01391     int j=0;
01392     for (int i=0; i<n; i++)
01393       if (!x[i].assigned())
01394         y[j++] = x[i];
01395     if (j < 2)
01396       return false;
01397     Support::quicksort<View>(y,j);
01398     for (int i=1; i<j; i++)
01399       if (y[i-1] == y[i])
01400         return true;
01401     return false;
01402   }
01403 
01404   template<class View>
01405   bool
01406   ViewArray<View>::same(const View& y) const {
01407     if (y.assigned())
01408       return false;
01409     for (int i=0; i<n; i++)
01410       if (x[i] == y)
01411         return true;
01412     return false;
01413   }
01414 
01415   template<class View>
01416   void
01417   ViewArray<View>::unique(void) {
01418     if (n < 2)
01419       return;
01420     Region r;
01421     Kernel::ViewOcc<View>* o = r.alloc<Kernel::ViewOcc<View>>(n);
01422     for (int i=0; i<n; i++) {
01423       o[i].x = x[i]; o[i].i = i;
01424     }
01425     Support::quicksort<Kernel::ViewOcc<View>>(o,n);
01426     // Assign bucket numbers
01427     int* bkt = r.alloc<int>(n);
01428     int b = 0;
01429     bkt[o[0].i] = b;
01430     for (int i=1; i<n; i++) {
01431       if (o[i-1].x != o[i].x)
01432         b++;
01433       bkt[o[i].i] = b;
01434     }
01435     // Eliminate duplicate elements
01436     Support::BitSet<Region> seen(r,static_cast<unsigned int>(b+1));
01437     int j=0;
01438     for (int i=0; i<n; i++)
01439       if (!seen.get(bkt[i])) {
01440         x[j++]=x[i]; seen.set(bkt[i]);
01441       } else {
01442         x[j]=x[i];
01443       }
01444     assert(j == b+1);
01445     n = j;
01446   }
01447 
01448   template<class View>
01449   forceinline void*
01450   ViewArray<View>::operator new(size_t) throw() {
01451     return nullptr;
01452   }
01453 
01454   template<class View>
01455   forceinline void
01456   ViewArray<View>::operator delete(void*,size_t) {
01457   }
01458 
01459 
01460   /*
01461    * Sharing for view arrays
01462    *
01463    */
01464   template<class ViewX, class ViewY>
01465   bool
01466   shared(ViewArray<ViewX> x, ViewArray<ViewY> y) {
01467     if ((x.size() == 0) || (y.size() == 0))
01468       return false;
01469     Region r;
01470     void** px = r.alloc<void*>(x.size());
01471     int j=0;
01472     for (int i=0; i<x.size(); i++)
01473       if (!x[i].assigned() && x[i].varimp())
01474         px[j++] = x[i].varimp();
01475     if (j == 0)
01476       return false;
01477     void** py = r.alloc<void*>(y.size());
01478     int k=0;
01479     for (int i=0; i<y.size(); i++)
01480       if (!y[i].assigned() && y[i].varimp())
01481         py[k++] = y[i].varimp();
01482     if (k == 0)
01483       return false;
01484     return Kernel::duplicates(px,j,py,k);
01485   }
01486 
01487   template<class ViewX, class ViewY>
01488   bool
01489   shared(ViewArray<ViewX> x, ViewY y) {
01490     if (y.assigned() || !y.varimp())
01491       return false;
01492     for (int i=0; i<x.size(); i++)
01493       if (!x[i].assigned() && x[i].varimp() && (x[i].varimp() == y.varimp()))
01494         return true;
01495     return false;
01496   }
01497 
01498   template<class ViewX, class ViewY>
01499   forceinline bool
01500   shared(ViewX x, ViewArray<ViewY> y) {
01501     return shared(y,x);
01502   }
01503 
01504   template<class View>
01505   bool
01506   shared(ViewArray<View> x) {
01507     if (x.size() < 2)
01508       return false;
01509     Region r;
01510     void** px = r.alloc<void*>(x.size());
01511     int j=0;
01512     for (int i=0; i<x.size(); i++)
01513       if (!x[i].assigned() && x[i].varimp())
01514         px[j++] = x[i].varimp();
01515     return (j > 2) && Kernel::duplicates(px,j);
01516   }
01517 
01518 
01519 
01520   /*
01521    * Argument arrays: base class
01522    *
01523    */
01524 
01525   template<class T>
01526   forceinline T*
01527   ArgArrayBase<T>::allocate(int n) {
01528     return (n > onstack_size) ?
01529       heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01530   }
01531 
01532   template<class T>
01533   forceinline void
01534   ArgArrayBase<T>::resize(int i) {
01535     if (n+i >= capacity) {
01536       assert(n+i >= onstack_size);
01537       int newCapacity = (3*capacity)/2;
01538       if (newCapacity <= n+i)
01539         newCapacity = n+i;
01540       T* newA = allocate(newCapacity);
01541       heap.copy<T>(newA,a,n);
01542       if (capacity > onstack_size)
01543         heap.free(a,capacity);
01544       capacity = newCapacity;
01545       a = newA;
01546     }
01547   }
01548 
01549   template<class T>
01550   forceinline
01551   ArgArrayBase<T>::ArgArrayBase(void)
01552     : n(0), capacity(onstack_size), a(allocate(0)) {}
01553 
01554   template<class T>
01555   forceinline
01556   ArgArrayBase<T>::ArgArrayBase(int n0)
01557     : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
01558 
01559   template<class T>
01560   inline
01561   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01562     : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
01563     heap.copy<T>(a,aa.a,n);
01564   }
01565 
01566   template<class T>
01567   inline
01568   ArgArrayBase<T>::ArgArrayBase(const std::vector<T>& aa)
01569     : n(static_cast<int>(aa.size())),
01570       capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
01571     heap.copy<T>(a,&aa[0],n);
01572   }
01573 
01574   template<class T>
01575   inline
01576   ArgArrayBase<T>::ArgArrayBase(std::initializer_list<T> aa)
01577     : n(static_cast<int>(aa.size())),
01578       capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
01579     int i=0;
01580     for (const T& x : aa)
01581       a[i++]=x;
01582   }
01583 
01584   template<class T>
01585   forceinline
01586   ArgArrayBase<T>::~ArgArrayBase(void) {
01587     if (capacity > onstack_size)
01588       heap.free(a,capacity);
01589   }
01590 
01591   template<class T>
01592   forceinline const ArgArrayBase<T>&
01593   ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01594     if (&aa != this) {
01595       if (capacity > onstack_size)
01596         heap.free(a,capacity);
01597       n = aa.n;
01598       capacity = (n < onstack_size ? onstack_size : n);
01599       a = allocate(aa.n);
01600       heap.copy<T>(a,aa.a,n);
01601     }
01602     return *this;
01603   }
01604 
01605   template<class T>
01606   forceinline int
01607   ArgArrayBase<T>::size(void) const {
01608     return n;
01609   }
01610 
01611   template<class T>
01612   forceinline T&
01613   ArgArrayBase<T>::operator [](int i) {
01614     assert((i>=0) && (i < n));
01615     return a[i];
01616   }
01617 
01618   template<class T>
01619   forceinline const T&
01620   ArgArrayBase<T>::operator [](int i) const {
01621     assert((i>=0) && (i < n));
01622     return a[i];
01623   }
01624 
01625   template<class T>
01626   forceinline typename ArgArrayBase<T>::iterator
01627   ArgArrayBase<T>::begin(void) {
01628     return a;
01629   }
01630 
01631   template<class T>
01632   forceinline typename ArgArrayBase<T>::const_iterator
01633   ArgArrayBase<T>::begin(void) const {
01634     return a;
01635   }
01636 
01637   template<class T>
01638   forceinline typename ArgArrayBase<T>::iterator
01639   ArgArrayBase<T>::end(void) {
01640     return a+n;
01641   }
01642 
01643   template<class T>
01644   forceinline typename ArgArrayBase<T>::const_iterator
01645   ArgArrayBase<T>::end(void) const {
01646     return a+n;
01647   }
01648 
01649   template<class T>
01650   forceinline typename ArgArrayBase<T>::reverse_iterator
01651   ArgArrayBase<T>::rbegin(void) {
01652     return reverse_iterator(a+n);
01653   }
01654 
01655   template<class T>
01656   forceinline typename ArgArrayBase<T>::const_reverse_iterator
01657   ArgArrayBase<T>::rbegin(void) const {
01658     return const_reverse_iterator(a+n);
01659   }
01660 
01661   template<class T>
01662   forceinline typename ArgArrayBase<T>::reverse_iterator
01663   ArgArrayBase<T>::rend(void) {
01664     return reverse_iterator(a);
01665   }
01666 
01667   template<class T>
01668   forceinline typename ArgArrayBase<T>::const_reverse_iterator
01669   ArgArrayBase<T>::rend(void) const {
01670     return const_reverse_iterator(a);
01671   }
01672 
01673   template<class T> template<class A>
01674   A
01675   ArgArrayBase<T>::slice(int start, int inc, int maxN) {
01676     assert(n==0 || start < n);
01677     if (n==0 || maxN<0)
01678       maxN = n;
01679     int s;
01680     if (inc == 0)
01681       s = n-start;
01682     else if (inc > 0)
01683       s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
01684     else
01685       s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
01686     A r(std::min(maxN,s));
01687     for (int i=0; i<r.size(); i++, start+=inc)
01688       new (&r[i]) T(a[start]);
01689     return r;
01690   }
01691 
01692   template<class T> template<class A>
01693   inline A&
01694   ArgArrayBase<T>::append(const T& x) {
01695     resize(1);
01696     new (&a[n++]) T(x);
01697     return static_cast<A&>(*this);
01698   }
01699 
01700   template<class T>
01701   template<class InputIterator>
01702   inline
01703   ArgArrayBase<T>::ArgArrayBase(InputIterator first, InputIterator last)
01704   : n(0), capacity(onstack_size), a(allocate(0)) {
01705     while (first != last) {
01706       (void) append<ArgArrayBase<T>>(*first);
01707       ++first;
01708     }
01709   }
01710 
01711 
01712   template<class T> template<class A>
01713   inline A&
01714   ArgArrayBase<T>::append(const ArgArrayBase<T>& x) {
01715     resize(x.size());
01716     for (int i=0; i<x.size(); i++)
01717       new (&a[n++]) T(x[i]);
01718     return static_cast<A&>(*this);
01719   }
01720 
01721   template<class T> template<class A>
01722   inline A
01723   ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const {
01724     A r(n+x.n);
01725     for (int i=0; i<n; i++)
01726       new (&r[i]) T(a[i]);
01727     for (int i=0; i<x.n; i++)
01728       new (&r[n+i]) T(x.a[i]);
01729     return r;
01730   }
01731 
01732   template<class T> template<class A>
01733   inline A
01734   ArgArrayBase<T>::concat(const T& x) const {
01735     A r(n+1);
01736     for (int i=0; i<n; i++)
01737       new (&r[i]) T(a[i]);
01738     new (&r[n]) T(x);
01739     return r;
01740   }
01741 
01742 
01743   /*
01744    * Argument arrays
01745    *
01746    */
01747 
01748   template<class T>
01749   forceinline
01750   ArgArray<T>::ArgArray(void) {}
01751 
01752   template<class T>
01753   forceinline
01754   ArgArray<T>::ArgArray(int n)
01755     : ArgArrayBase<T>(n) {}
01756 
01757   template<class T>
01758   ArgArray<T>::ArgArray(int n, const T* a0)
01759     : ArgArrayBase<T>(n) {
01760     for (int i=0; i<n; i++)
01761       a[i] = a0[i];
01762   }
01763 
01764   template<class T>
01765   forceinline
01766   ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01767     : ArgArrayBase<T>(aa) {}
01768 
01769   template<class T>
01770   forceinline
01771   ArgArray<T>::ArgArray(const std::vector<T>& aa)
01772     : ArgArrayBase<T>(aa) {}
01773 
01774   template<class T>
01775   forceinline
01776   ArgArray<T>::ArgArray(std::initializer_list<T> aa)
01777     : ArgArrayBase<T>(aa) {}
01778 
01779   template<class T>
01780   template<class InputIterator>
01781   forceinline
01782   ArgArray<T>::ArgArray(InputIterator first, InputIterator last)
01783     : ArgArrayBase<T>(first,last) {}
01784 
01785   template<class T>
01786   forceinline typename ArrayTraits<ArgArray<T>>::ArgsType
01787   ArgArray<T>::slice(int start, int inc, int maxN) {
01788     return ArgArrayBase<T>::template slice
01789       <typename ArrayTraits<ArgArray<T>>::ArgsType>
01790       (start,inc,maxN);
01791   }
01792 
01793   template<class T>
01794   forceinline typename ArrayTraits<ArgArray<T>>::ArgsType&
01795   ArgArray<T>::operator <<(const T& x) {
01796     return
01797       ArgArrayBase<T>::template append
01798         <typename ArrayTraits<ArgArray<T>>::ArgsType>(x);
01799   }
01800 
01801   template<class T>
01802   forceinline typename ArrayTraits<ArgArray<T>>::ArgsType&
01803   ArgArray<T>::operator <<(const ArgArray<T>& x) {
01804     return
01805       ArgArrayBase<T>::template append
01806         <typename ArrayTraits<ArgArray<T>>::ArgsType>(x);
01807   }
01808 
01809   template<class T>
01810   typename ArrayTraits<ArgArray<T>>::ArgsType
01811   operator +(const ArgArray<T>& x, const ArgArray<T>& y) {
01812     return x.template concat
01813       <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
01814   }
01815 
01816   template<class T>
01817   typename ArrayTraits<ArgArray<T>>::ArgsType
01818   operator +(const ArgArray<T>& x, const T& y) {
01819     return x.template concat
01820       <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
01821   }
01822 
01823   template<class T>
01824   typename ArrayTraits<ArgArray<T>>::ArgsType
01825   operator +(const T& x, const ArgArray<T>& y) {
01826     ArgArray<T> xa(1);
01827     xa[0] = x;
01828     return xa.template concat
01829       <typename ArrayTraits<ArgArray<T>>::ArgsType>(y);
01830   }
01831 
01832   /*
01833    * Argument arrays for variables
01834    *
01835    */
01836 
01837   template<class Var>
01838   forceinline
01839   VarArgArray<Var>::VarArgArray(void) {}
01840 
01841   template<class Var>
01842   forceinline
01843   VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {}
01844 
01845   template<class Var>
01846   forceinline
01847   VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01848     : ArgArrayBase<Var>(aa) {}
01849 
01850   template<class Var>
01851   forceinline
01852   VarArgArray<Var>::VarArgArray(const std::vector<Var>& aa)
01853     : ArgArrayBase<Var>(aa) {}
01854 
01855   template<class Var>
01856   forceinline
01857   VarArgArray<Var>::VarArgArray(std::initializer_list<Var> aa)
01858     : ArgArrayBase<Var>(aa) {}
01859 
01860   template<class Var>
01861   template<class InputIterator>
01862   forceinline
01863   VarArgArray<Var>::VarArgArray(InputIterator first, InputIterator last)
01864     : ArgArrayBase<Var>(first,last) {}
01865 
01866   template<class Var>
01867   inline
01868   VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01869     : ArgArrayBase<Var>(x.size()) {
01870     for (int i=0; i<x.size(); i++)
01871       a[i]=x[i];
01872   }
01873 
01874   template<class Var>
01875   forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType
01876   VarArgArray<Var>::slice(int start, int inc, int maxN) {
01877     return ArgArrayBase<Var>::template slice
01878       <typename ArrayTraits<VarArgArray<Var>>::ArgsType>
01879         (start,inc,maxN);
01880   }
01881 
01882   template<class Var>
01883   forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType&
01884   VarArgArray<Var>::operator <<(const Var& x) {
01885     return
01886       ArgArrayBase<Var>::template append
01887         <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x);
01888   }
01889 
01890   template<class Var>
01891   forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType&
01892   VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) {
01893     return
01894       ArgArrayBase<Var>::template append
01895         <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x);
01896   }
01897 
01898   template<class Var>
01899   typename ArrayTraits<VarArgArray<Var>>::ArgsType
01900   operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) {
01901     return x.template concat
01902       <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
01903   }
01904 
01905   template<class Var>
01906   typename ArrayTraits<VarArgArray<Var>>::ArgsType
01907   operator +(const VarArgArray<Var>& x, const Var& y) {
01908     return x.template concat
01909       <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
01910   }
01911 
01912   template<class Var>
01913   typename ArrayTraits<VarArgArray<Var>>::ArgsType
01914   operator +(const Var& x, const VarArgArray<Var>& y) {
01915     VarArgArray<Var> xa(1);
01916     xa[0] = x;
01917     return xa.template concat
01918       <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y);
01919   }
01920 
01921   template<class Var>
01922   forceinline bool
01923   VarArgArray<Var>::assigned(void) const {
01924     for (int i=0; i<n; i++)
01925       if (!a[i].assigned())
01926         return false;
01927     return true;
01928   }
01929 
01930 
01931   /*
01932    * Checking for multiple occurences of the same variable
01933    *
01934    */
01935   template<class Var>
01936   bool
01937   same(VarArgArray<Var> x, VarArgArray<Var> y) {
01938     if ((x.size() == 0) || (y.size() == 0))
01939       return false;
01940     Region r;
01941     void** px = r.alloc<void*>(x.size());
01942     int j=0;
01943     for (int i=0; i<x.size(); i++)
01944       if (!x[i].assigned())
01945         px[j++] = x[i].varimp();
01946     if (j == 0)
01947       return false;
01948     void** py = r.alloc<void*>(y.size());
01949     int k=0;
01950     for (int i=0; i<y.size(); i++)
01951       if (!y[i].assigned())
01952         py[k++] = y[i].varimp();
01953     if (k == 0)
01954       return false;
01955     return Kernel::duplicates(px,j,py,k);
01956   }
01957 
01958   template<class Var>
01959   bool
01960   same(VarArgArray<Var> x, Var y) {
01961     if (y.assigned())
01962       return false;
01963     for (int i=0; i<x.size(); i++)
01964       if (x[i].varimp() == y.varimp())
01965         return true;
01966     return false;
01967   }
01968 
01969   template<class Var>
01970   forceinline bool
01971   same(Var x, VarArgArray<Var> y) {
01972     return same(y,x);
01973   }
01974 
01975   template<class Var>
01976   bool
01977   same(VarArgArray<Var> x) {
01978     if (x.size() < 2)
01979       return false;
01980     Region r;
01981     void** px = r.alloc<void*>(x.size());
01982     int j=0;
01983     for (int i=0; i<x.size(); i++)
01984       if (!x[i].assigned())
01985         px[j++] = x[i].varimp();
01986     return (j > 1) && Kernel::duplicates(px,j);
01987   }
01988 
01989 
01990 
01991   /*
01992    * Interdependent code
01993    *
01994    */
01995 
01996   template<class Var>
01997   inline
01998   VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
01999     : n(a.size()) {
02000     if (n>0) {
02001       x = home.alloc<Var>(n);
02002       for (int i=0; i<n; i++)
02003         x[i] = a[i];
02004     } else {
02005       x = nullptr;
02006     }
02007   }
02008 
02009 
02010   /*
02011    * Printing of arrays
02012    *
02013    */
02014   template<class Char, class Traits, class Var>
02015   std::basic_ostream<Char,Traits>&
02016   operator <<(std::basic_ostream<Char,Traits>& os,
02017               const VarArray<Var>& x) {
02018     std::basic_ostringstream<Char,Traits> s;
02019     s.copyfmt(os); s.width(0);
02020     s << '{';
02021     if (x.size() > 0) {
02022       s << x[0];
02023       for (int i=1; i<x.size(); i++)
02024         s << ", " << x[i];
02025     }
02026     s << '}';
02027     return os << s.str();
02028   }
02029 
02030   template<class Char, class Traits, class View>
02031   std::basic_ostream<Char,Traits>&
02032   operator <<(std::basic_ostream<Char,Traits>& os,
02033              const ViewArray<View>& x) {
02034     std::basic_ostringstream<Char,Traits> s;
02035     s.copyfmt(os); s.width(0);
02036     s << '{';
02037     if (x.size() > 0) {
02038       s << x[0];
02039       for (int i=1; i<x.size(); i++)
02040         s << ", " << x[i];
02041     }
02042     s << '}';
02043     return os << s.str();
02044   }
02045 
02046   template<class Char, class Traits, class T>
02047   std::basic_ostream<Char,Traits>&
02048   operator <<(std::basic_ostream<Char,Traits>& os,
02049              const ArgArrayBase<T>& x) {
02050     std::basic_ostringstream<Char,Traits> s;
02051     s.copyfmt(os); s.width(0);
02052     s << '{';
02053     if (x.size() > 0) {
02054       s << x[0];
02055       for (int i=1; i<x.size(); i++)
02056         s << ", " << x[i];
02057     }
02058     s << '}';
02059     return os << s.str();
02060   }
02061 
02062 }
02063 
02064 // STATISTICS: kernel-other