Generated on Sat Feb 12 2011 17:40:49 for Gecode by doxygen 1.7.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  *  Last modified:
00016  *     $Date: 2011-01-27 13:03:05 +0100 (Thu, 27 Jan 2011) $ by $Author: schulte $
00017  *     $Revision: 11570 $
00018  *
00019  *  This file is part of Gecode, the generic constraint
00020  *  development environment:
00021  *     http://www.gecode.org
00022  *
00023  *  Permission is hereby granted, free of charge, to any person obtaining
00024  *  a copy of this software and associated documentation files (the
00025  *  "Software"), to deal in the Software without restriction, including
00026  *  without limitation the rights to use, copy, modify, merge, publish,
00027  *  distribute, sublicense, and/or sell copies of the Software, and to
00028  *  permit persons to whom the Software is furnished to do so, subject to
00029  *  the following conditions:
00030  *
00031  *  The above copyright notice and this permission notice shall be
00032  *  included in all copies or substantial portions of the Software.
00033  *
00034  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00035  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00036  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00037  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00038  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00039  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00040  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00041  *
00042  */
00043 
00044 #include <cstdarg>
00045 #include <iostream>
00046 #include <iterator>
00047 #include <sstream>
00048 
00049 namespace Gecode {
00050 
00051   template<class Var> class VarArray;
00052   template<class Var> class VarArgArray;
00053 
00066   template<class A>
00067   class ArrayTraits {};
00068 
00084   template<class Var>
00085   class VarArray {
00086   protected:
00088     int n;
00090     Var* x;
00091   public:
00093 
00094 
00095     typedef Var value_type;
00097     typedef Var& reference;
00099     typedef const Var& const_reference;
00101     typedef Var* pointer;
00103     typedef const Var* const_pointer;
00105     typedef Var* iterator;
00107     typedef const Var* const_iterator;
00109     typedef std::reverse_iterator<Var*> reverse_iterator;
00111     typedef std::reverse_iterator<const Var*> const_reverse_iterator;
00113 
00115 
00116 
00117 
00118     VarArray(void);
00120     VarArray(Space& home, int m);
00122     VarArray(Space& home, const VarArgArray<Var>&);
00124     VarArray(const VarArray<Var>& a);
00126     const VarArray<Var>& operator =(const VarArray<Var>& a);
00128 
00130 
00131 
00132     int size(void) const;
00134 
00136 
00137 
00138     Var& operator [](int i);
00140     const Var& operator [](int i) const;
00146     typename ArrayTraits<VarArgArray<Var> >::ArgsType
00147     slice(int start, int inc=1, int n=-1);
00149 
00151 
00152 
00153     iterator begin(void);
00155     const_iterator begin(void) const;
00157     iterator end(void);
00159     const_iterator end(void) const;
00161     reverse_iterator rbegin(void);
00163     const_reverse_iterator rbegin(void) const;
00165     reverse_iterator rend(void);
00167     const_reverse_iterator rend(void) const;
00169 
00171     bool assigned(void) const;
00172 
00174 
00175 
00182     void update(Space&, bool share, VarArray<Var>& a);
00184   private:
00185     static void* operator new(size_t);
00186     static void  operator delete(void*,size_t);
00187   };
00188 
00192   template<class T>
00193   typename ArrayTraits<VarArray<T> >::ArgsType
00194   operator +(const VarArray<T>& x, const VarArgArray<T>& y);
00195 
00199   template<class T>
00200   typename ArrayTraits<VarArray<T> >::ArgsType
00201   operator +(const VarArray<T>& x, const VarArray<T>& y);
00202 
00206   template<class T>
00207   typename ArrayTraits<VarArray<T> >::ArgsType
00208   operator +(const VarArgArray<T>& x, const VarArray<T>& y);
00209 
00213   template<class T>
00214   typename ArrayTraits<VarArray<T> >::ArgsType
00215   operator +(const VarArray<T>& x, const T& y);
00216 
00220   template<class T>
00221   typename ArrayTraits<VarArray<T> >::ArgsType
00222   operator +(const T& x, const VarArray<T>& y);
00223 
00232   template<class View>
00233   class ViewArray {
00234   private:
00236     int  n;
00238     View* x;
00240     template<class X>
00241     class ViewLess {
00242     public:
00243       bool operator ()(const X&, const X&);
00244     };
00246     static void sort(View* x, int n);
00247   public:
00249 
00250 
00251     typedef View value_type;
00253     typedef View& reference;
00255     typedef const View& const_reference;
00257     typedef View* pointer;
00259     typedef const View* const_pointer;
00261     typedef View* iterator;
00263     typedef const View* const_iterator;
00265     typedef std::reverse_iterator<View*> reverse_iterator;
00267     typedef std::reverse_iterator<const View*> const_reverse_iterator;
00269 
00271 
00272 
00273     ViewArray(void);
00275     ViewArray(Space& home, int m);
00277     ViewArray(const ViewArray<View>& a);
00279     ViewArray(Space& home, const ViewArray<View>& a);
00281     const ViewArray<View>& operator =(const ViewArray<View>& a);
00288     template<class Var>
00289     ViewArray(Space& home, const VarArgArray<Var>& a)
00290       : n(a.size()) {
00291       // This may not be in the hpp file (to satisfy the MS compiler)
00292       if (n>0) {
00293         x = home.alloc<View>(n);
00294         for (int i=n; i--; )
00295           x[i]=a[i];
00296       } else {
00297         x = NULL;
00298       }
00299     }
00301 
00303 
00304 
00305     int size(void) const;
00307     void size(int n);
00309 
00311 
00312 
00313     View& operator [](int i);
00315     const View& operator [](int i) const;
00317 
00319 
00320 
00321     iterator begin(void);
00323     const_iterator begin(void) const;
00325     iterator end(void);
00327     const_iterator end(void) const;
00329     reverse_iterator rbegin(void);
00331     const_reverse_iterator rbegin(void) const;
00333     reverse_iterator rend(void);
00335     const_reverse_iterator rend(void) const;
00337 
00339 
00340 
00347     void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00349     void cancel(Space& home, Propagator& p, PropCond pc);
00351     void subscribe(Space& home, Advisor& a);
00353     void cancel(Space& home, Advisor& a);
00355 
00357 
00358 
00365     void update(Space&, bool share, ViewArray<View>& a);
00367 
00368 
00370 
00371 
00372     void move_fst(int i);
00374     void move_lst(int i);
00380     void move_fst(int i, Space& home, Propagator& p, PropCond pc);
00386     void move_lst(int i, Space& home, Propagator& p, PropCond pc);
00392     void move_fst(int i, Space& home, Advisor& a);
00398     void move_lst(int i, Space& home, Advisor& a);
00400 
00402 
00403 
00404     void drop_fst(int i);
00406     void drop_lst(int i);
00412     void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
00419     void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
00425     void drop_fst(int i, Space& home, Advisor& a);
00431     void drop_lst(int i, Space& home, Advisor& a);
00433 
00435     bool assigned(void) const;
00436 
00438 
00439 
00444     bool same(const Space& home) const;
00450     bool same(const Space& home, const View& y) const;
00452     void unique(const Space& home);
00454 
00456 
00457 
00462     bool shared(const Space& home) const;
00468     template<class ViewY>
00469     bool shared(const Space& home, const ViewY& y) const;
00475     template<class ViewY>
00476     bool shared(const Space& home, const ViewArray<ViewY>& y) const;
00478 
00479   private:
00480     static void* operator new(size_t);
00481     static void  operator delete(void*,size_t);
00482   };
00483 
00497   template<class T>
00498   class ArgArrayBase {
00499   protected:
00501     int n;
00503     int capacity;
00505     T*  a;
00507     static const int onstack_size = 16;
00509     T onstack[onstack_size];
00511     T* allocate(int n);
00513     void resize(int i);
00515     template<class A>
00516     A concat(const ArgArrayBase<T>& x) const;
00518     template<class A>
00519     A concat(const T& x) const;
00521     template<class A>
00522     A& append(const T& x);
00524     template<class A>
00525     A& append(const ArgArrayBase<T>& x);
00531     template<class A>
00532     A slice(int start, int inc=1, int n=-1);
00533   public:
00535 
00536 
00537     typedef T value_type;
00539     typedef T& reference;
00541     typedef const T& const_reference;
00543     typedef T* pointer;
00545     typedef const T* const_pointer;
00547     typedef T* iterator;
00549     typedef const T* const_iterator;
00551     typedef std::reverse_iterator<T*> reverse_iterator;
00553     typedef std::reverse_iterator<const T*> const_reverse_iterator;
00555 
00557 
00558 
00559     ArgArrayBase(void);
00561     explicit ArgArrayBase(int n);
00563     ArgArrayBase(const ArgArrayBase<T>& a);
00565     const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
00567 
00569 
00570 
00571     int size(void) const;
00573 
00575 
00576 
00577     T& operator [](int i);
00579     const T& operator [](int i) const;
00581 
00583 
00584 
00585     iterator begin(void);
00587     const_iterator begin(void) const;
00589     iterator end(void);
00591     const_iterator end(void) const;
00593     reverse_iterator rbegin(void);
00595     const_reverse_iterator rbegin(void) const;
00597     reverse_iterator rend(void);
00599     const_reverse_iterator rend(void) const;
00601 
00603 
00604 
00605     ~ArgArrayBase(void);
00607   private:
00608     static void* operator new(size_t);
00609     static void  operator delete(void*,size_t);
00610   };
00611 
00612   template<class> class PrimArgArray;
00613 
00617   template<class T>
00618   typename ArrayTraits<PrimArgArray<T> >::ArgsType
00619   operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
00620 
00624   template<class T>
00625   typename ArrayTraits<PrimArgArray<T> >::ArgsType
00626   operator +(const PrimArgArray<T>& x, const T& y);
00627 
00631   template<class T>
00632   typename ArrayTraits<PrimArgArray<T> >::ArgsType
00633   operator +(const T& x, const PrimArgArray<T>& y);
00634 
00646   template<class T>
00647   class PrimArgArray : public ArgArrayBase<T> {
00648   protected:
00649     using ArgArrayBase<T>::a;
00650   public:
00651     using ArgArrayBase<T>::size;
00653 
00654 
00655     PrimArgArray(void);
00657     explicit PrimArgArray(int n);
00659     PrimArgArray(int n, T e0, ...);
00661     PrimArgArray(int n, const T* e);
00663     PrimArgArray(const PrimArgArray<T>& a);
00665 
00666 
00667 
00672     typename ArrayTraits<PrimArgArray<T> >::ArgsType
00673     slice(int start, int inc=1, int n=-1);
00675 
00676 
00677 
00678     typename ArrayTraits<PrimArgArray<T> >::ArgsType&
00679     operator <<(const T& x);
00681     typename ArrayTraits<PrimArgArray<T> >::ArgsType&
00682     operator <<(const PrimArgArray<T>& x);
00684 
00685     friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
00686     operator + <>(const PrimArgArray<T>& x, const PrimArgArray<T>& y);
00687     friend typename ArrayTraits<PrimArgArray<T> >::ArgsType
00688     operator + <>(const PrimArgArray<T>& x, const T& y);
00689     friend
00690     typename ArrayTraits<PrimArgArray<T> >::ArgsType
00691     operator + <>(const T& x, const PrimArgArray<T>& y);
00692   };
00693 
00694   template<class> class ArgArray;
00695 
00699   template<class T>
00700   typename ArrayTraits<ArgArray<T> >::ArgsType
00701   operator +(const ArgArray<T>& x, const ArgArray<T>& y);
00702 
00706   template<class T>
00707   typename ArrayTraits<ArgArray<T> >::ArgsType
00708   operator +(const ArgArray<T>& x, const T& y);
00709 
00713   template<class T>
00714   typename ArrayTraits<ArgArray<T> >::ArgsType
00715   operator +(const T& x, const ArgArray<T>& y);
00716 
00728   template<class T>
00729   class ArgArray : public ArgArrayBase<T> {
00730   protected:
00731     using ArgArrayBase<T>::a;
00732   public:
00733     using ArgArrayBase<T>::size;
00735 
00736 
00737     ArgArray(void);
00739     explicit ArgArray(int n);
00741     ArgArray(int n, const T* e);
00743     ArgArray(const ArgArray<T>& a);
00745 
00746 
00747 
00748     typename ArrayTraits<ArgArray<T> >::ArgsType
00749     slice(int start, int inc=1, int n=-1);
00751 
00752 
00753 
00754     typename ArrayTraits<ArgArray<T> >::ArgsType&
00755     operator <<(const T& x);
00757     typename ArrayTraits<ArgArray<T> >::ArgsType&
00758     operator <<(const ArgArray<T>& x);
00760 
00761     friend typename ArrayTraits<ArgArray<T> >::ArgsType
00762     operator + <>(const ArgArray<T>& x, const ArgArray<T>& y);
00763     friend typename ArrayTraits<ArgArray<T> >::ArgsType
00764     operator + <>(const ArgArray<T>& x, const T& y);
00765     friend
00766     typename ArrayTraits<ArgArray<T> >::ArgsType
00767     operator + <>(const T& x, const ArgArray<T>& y);
00768   };
00769 
00770   template<class> class VarArgArray;
00771 
00775   template<class Var>
00776   typename ArrayTraits<VarArgArray<Var> >::ArgsType
00777   operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
00778 
00782   template<class Var>
00783   typename ArrayTraits<VarArgArray<Var> >::ArgsType
00784   operator +(const VarArgArray<Var>& x, const Var& y);
00785 
00789   template<class Var>
00790   typename ArrayTraits<VarArgArray<Var> >::ArgsType
00791   operator +(const Var& x, const VarArgArray<Var>& y);
00792 
00804   template<class Var>
00805   class VarArgArray : public ArgArrayBase<Var> {
00806   protected:
00807     using ArgArrayBase<Var>::a;
00808     using ArgArrayBase<Var>::n;
00810     class VarLess {
00811     public:
00812       bool operator ()(const Var&, const Var&);
00813     };
00814   public:
00815     using ArgArrayBase<Var>::size;
00817 
00818 
00819     VarArgArray(void);
00821     explicit VarArgArray(int n);
00823     VarArgArray(const VarArgArray<Var>& a);
00825     VarArgArray(const VarArray<Var>& a);
00827 
00828 
00829 
00830     typename ArrayTraits<VarArgArray<Var> >::ArgsType
00831     slice(int start, int inc=1, int n=-1);
00833 
00834 
00835 
00836     typename ArrayTraits<VarArgArray<Var> >::ArgsType&
00837     operator <<(const Var& x);
00839     typename ArrayTraits<VarArgArray<Var> >::ArgsType&
00840     operator <<(const VarArgArray<Var>& x);
00842 
00844     bool assigned(void) const;
00845 
00846     friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
00847     operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
00848     friend typename ArrayTraits<VarArgArray<Var> >::ArgsType
00849     operator + <>(const VarArgArray<Var>& x, const Var& y);
00850     friend
00851     typename ArrayTraits<VarArgArray<Var> >::ArgsType
00852     operator + <>(const Var& x, const VarArgArray<Var>& y);
00853 
00855 
00856 
00861     bool same(const Space& home) const;
00867     bool same(const Space& home, const Var& y) const;
00873     bool same(const Space& home, const VarArgArray<Var>& y) const;
00875   };
00876 
00881   template<class Char, class Traits, class Var>
00882   std::basic_ostream<Char,Traits>&
00883   operator <<(std::basic_ostream<Char,Traits>& os,
00884              const VarArray<Var>& x);
00885 
00890   template<class Char, class Traits, class View>
00891   std::basic_ostream<Char,Traits>&
00892   operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
00893 
00898   template<class Char, class Traits, class T>
00899   std::basic_ostream<Char,Traits>&
00900   operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
00901 
00902 
00903   /*
00904    * Implementation
00905    *
00906    */
00907 
00908   /*
00909    * Variable arrays
00910    *
00911    * These arrays are usually allocated in the space, but if they are resized,
00912    * the new array is allocated on the heap. The size (n) and capacity show
00913    * where the array is allocated: it is in the space if and only if
00914    * n==capacity.
00915    *
00916    */
00917 
00918   template<class Var>
00919   forceinline
00920   VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
00921 
00922   template<class Var>
00923   forceinline
00924   VarArray<Var>::VarArray(Space& home, int n0)
00925     : n(n0) {
00926     // Allocate from space
00927     x = (n>0) ? home.alloc<Var>(n) : NULL;
00928   }
00929 
00930   template<class Var>
00931   forceinline
00932   VarArray<Var>::VarArray(const VarArray<Var>& a) {
00933     n = a.n; x = a.x;
00934   }
00935 
00936   template<class Var>
00937   inline const VarArray<Var>&
00938   VarArray<Var>::operator =(const VarArray<Var>& a) {
00939     n = a.n; x = a.x;
00940     return *this;
00941   }
00942 
00943   template<class Var>
00944   forceinline int
00945   VarArray<Var>::size(void) const {
00946     return n;
00947   }
00948 
00949   template<class Var>
00950   forceinline Var&
00951   VarArray<Var>::operator [](int i) {
00952     assert((i >= 0) && (i < size()));
00953     return x[i];
00954   }
00955 
00956   template<class Var>
00957   forceinline const Var&
00958   VarArray<Var>::operator [](int i) const {
00959     assert((i >= 0) && (i < size()));
00960     return x[i];
00961   }
00962 
00963   template<class Var>
00964   typename ArrayTraits<VarArgArray<Var> >::ArgsType
00965   VarArray<Var>::slice(int start, int inc, int maxN) {
00966     assert(start < n);
00967     if (maxN<0)
00968       maxN = n;
00969     int s;
00970     if (inc == 0)
00971       s = n-start;
00972     else if (inc > 0)
00973       s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
00974     else
00975       s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
00976     typename ArrayTraits<VarArgArray<Var> >::ArgsType r(std::min(maxN,s));
00977     for (int i=0; i<r.size(); i++, start+=inc)
00978       r[i] = x[start];
00979     return r;
00980   }
00981 
00982   template<class Var>
00983   forceinline typename VarArray<Var>::iterator
00984   VarArray<Var>::begin(void) {
00985     return x;
00986   }
00987 
00988   template<class Var>
00989   forceinline typename VarArray<Var>::const_iterator
00990   VarArray<Var>::begin(void) const {
00991     return x;
00992   }
00993 
00994   template<class Var>
00995   forceinline typename VarArray<Var>::iterator
00996   VarArray<Var>::end(void) {
00997     return x+n;
00998   }
00999 
01000   template<class Var>
01001   forceinline typename VarArray<Var>::const_iterator
01002   VarArray<Var>::end(void) const {
01003     return x+n;
01004   }
01005 
01006   template<class Var>
01007   forceinline typename VarArray<Var>::reverse_iterator
01008   VarArray<Var>::rbegin(void) {
01009     return reverse_iterator(x+n);
01010   }
01011 
01012   template<class Var>
01013   forceinline typename VarArray<Var>::const_reverse_iterator
01014   VarArray<Var>::rbegin(void) const {
01015     return const_reverse_iterator(x+n);
01016   }
01017 
01018   template<class Var>
01019   forceinline typename VarArray<Var>::reverse_iterator
01020   VarArray<Var>::rend(void) {
01021     return reverse_iterator(x);
01022   }
01023 
01024   template<class Var>
01025   forceinline typename VarArray<Var>::const_reverse_iterator
01026   VarArray<Var>::rend(void) const {
01027     return const_reverse_iterator(x);
01028   }
01029 
01030   template<class Var>
01031   forceinline void
01032   VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) {
01033     n = a.n;
01034     if (n > 0) {
01035       x = home.alloc<Var>(n);
01036       for (int i = n; i--;)
01037         x[i].update(home, share, a.x[i]);
01038     } else {
01039       x = NULL;
01040     }
01041   }
01042 
01043   template<class Var>
01044   forceinline bool
01045   VarArray<Var>::assigned(void) const {
01046     for (int i = n; i--;)
01047       if (!x[i].assigned())
01048         return false;
01049     return true;
01050   }
01051   
01052   template<class Var>
01053   void*
01054   VarArray<Var>::operator new(size_t) {
01055     return NULL;
01056   }
01057 
01058   template<class Var>
01059   void
01060   VarArray<Var>::operator delete(void*,size_t) {
01061   }
01062 
01063   template<class Var>
01064   typename ArrayTraits<VarArray<Var> >::ArgsType
01065   operator +(const VarArray<Var>& x, const VarArray<Var>& y) {
01066     typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
01067     for (int i=x.size(); i--;)
01068       r[i] = x[i];
01069     for (int i=y.size(); i--;)
01070       r[x.size()+i] = y[i];
01071     return r;
01072   }
01073 
01074   template<class Var>
01075   typename ArrayTraits<VarArray<Var> >::ArgsType
01076   operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) {
01077     typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
01078     for (int i=x.size(); i--;)
01079       r[i] = x[i];
01080     for (int i=y.size(); i--;)
01081       r[x.size()+i] = y[i];
01082     return r;
01083   }
01084 
01085   template<class Var>
01086   typename ArrayTraits<VarArray<Var> >::ArgsType
01087   operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) {
01088     typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size());
01089     for (int i=x.size(); i--;)
01090       r[i] = x[i];
01091     for (int i=y.size(); i--;)
01092       r[x.size()+i] = y[i];
01093     return r;
01094   }
01095 
01096   template<class Var>
01097   typename ArrayTraits<VarArray<Var> >::ArgsType
01098   operator +(const VarArray<Var>& x, const Var& y) {
01099     typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+1);
01100     for (int i=x.size(); i--;)
01101       r[i] = x[i];
01102     r[x.size()] = y;
01103     return r;    
01104   }
01105 
01106   template<class Var>
01107   typename ArrayTraits<VarArray<Var> >::ArgsType
01108   operator +(const Var& x, const VarArray<Var>& y) {
01109     typename ArrayTraits<VarArray<Var> >::ArgsType r(y.size()+1);
01110     r[0] = x;
01111     for (int i=y.size(); i--;)
01112       r[1+i] = y[i];
01113     return r;
01114   }
01115 
01116   /*
01117    * View arrays
01118    *
01119    */
01120 
01121   template<class View>
01122   forceinline
01123   ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
01124 
01125   template<class View>
01126   forceinline
01127   ViewArray<View>::ViewArray(Space& home, int n0)
01128     : n(n0) {
01129     x = (n>0) ? home.alloc<View>(n) : NULL;
01130   }
01131 
01132   template<class View>
01133   ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
01134     : n(a.size()) {
01135     if (n>0) {
01136       x = home.alloc<View>(n);
01137       for (int i = n; i--; )
01138         x[i] = a[i];
01139     } else {
01140       x = NULL;
01141     }
01142   }
01143 
01144   template<class View>
01145   forceinline
01146   ViewArray<View>::ViewArray(const ViewArray<View>& a)
01147     : n(a.n), x(a.x) {}
01148 
01149   template<class View>
01150   forceinline const ViewArray<View>&
01151   ViewArray<View>::operator =(const ViewArray<View>& a) {
01152     n = a.n; x = a.x;
01153     return *this;
01154   }
01155 
01156   template<class View>
01157   forceinline int
01158   ViewArray<View>::size(void) const {
01159     return n;
01160   }
01161 
01162   template<class View>
01163   forceinline void
01164   ViewArray<View>::size(int n0) {
01165     n = n0;
01166   }
01167 
01168   template<class View>
01169   forceinline View&
01170   ViewArray<View>::operator [](int i) {
01171     assert((i >= 0) && (i < size()));
01172     return x[i];
01173   }
01174 
01175   template<class View>
01176   forceinline const View&
01177   ViewArray<View>::operator [](int i) const {
01178     assert((i >= 0) && (i < size()));
01179     return x[i];
01180   }
01181 
01182   template<class View>
01183   forceinline typename ViewArray<View>::iterator
01184   ViewArray<View>::begin(void) {
01185     return x;
01186   }
01187 
01188   template<class View>
01189   forceinline typename ViewArray<View>::const_iterator
01190   ViewArray<View>::begin(void) const {
01191     return x;
01192   }
01193 
01194   template<class View>
01195   forceinline typename ViewArray<View>::iterator
01196   ViewArray<View>::end(void) {
01197     return x+n;
01198   }
01199 
01200   template<class View>
01201   forceinline typename ViewArray<View>::const_iterator
01202   ViewArray<View>::end(void) const {
01203     return x+n;
01204   }
01205 
01206   template<class View>
01207   forceinline typename ViewArray<View>::reverse_iterator
01208   ViewArray<View>::rbegin(void) {
01209     return reverse_iterator(x+n);
01210   }
01211 
01212   template<class View>
01213   forceinline typename ViewArray<View>::const_reverse_iterator
01214   ViewArray<View>::rbegin(void) const {
01215     return const_reverse_iterator(x+n);
01216   }
01217 
01218   template<class View>
01219   forceinline typename ViewArray<View>::reverse_iterator
01220   ViewArray<View>::rend(void) {
01221     return reverse_iterator(x);
01222   }
01223 
01224   template<class View>
01225   forceinline typename ViewArray<View>::const_reverse_iterator
01226   ViewArray<View>::rend(void) const {
01227     return const_reverse_iterator(x);
01228   }
01229 
01230   template<class View>
01231   forceinline void
01232   ViewArray<View>::move_fst(int i) {
01233     x[i]=x[0]; x++; n--;
01234   }
01235 
01236   template<class View>
01237   forceinline void
01238   ViewArray<View>::move_lst(int i) {
01239     n--; x[i]=x[n];
01240   }
01241 
01242   template<class View>
01243   forceinline void
01244   ViewArray<View>::drop_fst(int i) {
01245     assert(i>=0);
01246     x += i; n -= i;
01247   }
01248 
01249   template<class View>
01250   forceinline void
01251   ViewArray<View>::drop_lst(int i) {
01252     assert(i<n);
01253     n = i+1;
01254   }
01255 
01256   template<class View>
01257   forceinline void
01258   ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
01259     // Move x[0] to x[i]
01260     x[i].cancel(home,p,pc);
01261     x[i]=x[0]; x++; n--;
01262   }
01263 
01264   template<class View>
01265   forceinline void
01266   ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
01267     // Move x[n-1] to x[i]
01268     x[i].cancel(home,p,pc);
01269     n--; x[i]=x[n];
01270   }
01271 
01272   template<class View>
01273   void
01274   ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
01275     // Drop elements from 0..i-1
01276     assert(i>=0);
01277     for (int j=i; j--; )
01278       x[j].cancel(home,p,pc);
01279     x += i; n -= i;
01280   }
01281 
01282   template<class View>
01283   void
01284   ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
01285     // Drop elements from i+1..n-1
01286     assert(i<n);
01287     for (int j=i+1; j<n; j++)
01288       x[j].cancel(home,p,pc);
01289     n = i+1;
01290   }
01291 
01292   template<class View>
01293   forceinline void
01294   ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
01295     // Move x[0] to x[i]
01296     x[i].cancel(home,a);
01297     x[i]=x[0]; x++; n--;
01298   }
01299 
01300   template<class View>
01301   forceinline void
01302   ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
01303     // Move x[n-1] to x[i]
01304     x[i].cancel(home,a);
01305     n--; x[i]=x[n];
01306   }
01307 
01308   template<class View>
01309   void
01310   ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
01311     // Drop elements from 0..i-1
01312     assert(i>=0);
01313     for (int j=i; j--; )
01314       x[j].cancel(home,a);
01315     x += i; n -= i;
01316   }
01317 
01318   template<class View>
01319   void
01320   ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
01321     // Drop elements from i+1..n-1
01322     assert(i<n);
01323     for (int j=i+1; j<n; j++)
01324       x[j].cancel(home,a);
01325     n = i+1;
01326   }
01327 
01328   template<class View>
01329   void
01330   ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) {
01331     n = y.n;
01332     if (n > 0) {
01333       x = home.alloc<View>(n);
01334       for (int i = n; i--; )
01335         x[i].update(home, share, y.x[i]);
01336     } else {
01337       x = NULL;
01338     }
01339   }
01340 
01341   template<class View>
01342   void
01343   ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
01344                              bool process) {
01345     for (int i = n; i--; )
01346       x[i].subscribe(home,p,pc,process);
01347   }
01348 
01349   template<class View>
01350   void
01351   ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
01352     for (int i = n; i--; )
01353       x[i].cancel(home,p,pc);
01354   }
01355 
01356   template<class View>
01357   void
01358   ViewArray<View>::subscribe(Space& home, Advisor& a) {
01359     for (int i = n; i--; )
01360       x[i].subscribe(home,a);
01361   }
01362 
01363   template<class View>
01364   void
01365   ViewArray<View>::cancel(Space& home, Advisor& a) {
01366     for (int i = n; i--; )
01367       x[i].cancel(home,a);
01368   }
01369 
01370   template<class View>
01371   forceinline bool
01372   ViewArray<View>::assigned(void) const {
01373     for (int i = n; i--;)
01374       if (!x[i].assigned())
01375         return false;
01376     return true;
01377   }
01378 
01379   template<class View>
01380   forceinline bool
01381   __before(const View& x, const View& y) {
01382     return before(x,y);
01383   }
01384 
01385   template<class View> template<class X>
01386   forceinline bool
01387   ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
01388     return __before(a,b);
01389   }
01390 
01391   template<class View>
01392   void
01393   ViewArray<View>::sort(View* y, int m) {
01394     ViewLess<View> vl;
01395     Support::quicksort<View,ViewLess<View> >(y,m,vl);
01396   }
01397 
01398   template<class X, class Y>
01399   forceinline bool
01400   __same(const X& x, const Y& y) {
01401     return same(x,y);
01402   }
01403   template<class X, class Y>
01404   forceinline bool
01405   __shared(const X& x, const Y& y) {
01406     return shared(x,y);
01407   }
01408 
01409   template<class View>
01410   bool
01411   ViewArray<View>::same(const Space& home) const {
01412     if (n < 2)
01413       return false;
01414     Region r(home);
01415     View* y = r.alloc<View>(n);
01416     for (int i = n; i--; )
01417       y[i] = x[i];
01418     sort(y,n);
01419     for (int i = n-1; i--; )
01420       if (!y[i].assigned() && __same(y[i+1],y[i])) {
01421         r.free<View>(y,n);
01422         return true;
01423       }
01424     r.free<View>(y,n);
01425     return false;
01426   }
01427 
01428   template<class View>
01429   bool
01430   ViewArray<View>::same(const Space&, const View& y) const {
01431     if (y.assigned())
01432       return false;
01433     for (int i = n; i--; )
01434       if (__same(x[i],y))
01435         return true;
01436     return false;
01437   }
01438 
01439   template<class View>
01440   void
01441   ViewArray<View>::unique(const Space&) {
01442     if (n < 2)
01443       return;
01444     sort(x,n);
01445     int j = 0;
01446     for (int i = 1; i<n; i++)
01447       if (!__same(x[j],x[i]))
01448         x[++j] = x[i];
01449     n = j+1;
01450   }
01451 
01452   template<class View>
01453   bool
01454   ViewArray<View>::shared(const Space& home) const {
01455     if (n < 2)
01456       return false;
01457     Region r(home);
01458     View* y = r.alloc<View>(n);
01459     for (int i = n; i--; )
01460       y[i] = x[i];
01461     sort(y,n);
01462     for (int i = n-1; i--; )
01463       if (!y[i].assigned() && __shared(y[i+1],y[i])) {
01464         r.free<View>(y,n);
01465         return true;
01466       }
01467     r.free<View>(y,n);
01468     return false;
01469   }
01470 
01471   template<class View> template<class ViewY>
01472   bool
01473   ViewArray<View>::shared(const Space&, const ViewY& y) const {
01474     if (y.assigned())
01475       return false;
01476     for (int i = n; i--; )
01477       if (!x[i].assigned() && __shared(x[i],y))
01478         return true;
01479     return false;
01480   }
01481 
01482   template<class View> template<class ViewY>
01483   bool
01484   ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
01485     if ((size() < 1) || (y.size() < 1))
01486       return false;
01487     Region r(home);
01488     View* xs = r.alloc<View>(size());
01489     for (int i=size(); i--; )
01490       xs[i] = x[i];
01491     ViewLess<View> xvl;
01492     Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
01493     ViewY* ys = r.alloc<ViewY>(y.size());
01494     for (int j=y.size(); j--; )
01495       ys[j] = y[j];
01496     ViewLess<ViewY> yvl;
01497     Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
01498     {
01499       int i=0, j=0;
01500       while ((i < size()) && (j < y.size()))
01501         if (!x[i].assigned() && __shared(x[i],y[j])) {
01502           r.free<View>(xs,size());
01503           r.free<ViewY>(ys,y.size());
01504           return true;
01505         } else if (before(x[i],y[j])) {
01506           i++;
01507         } else {
01508           j++;
01509         }
01510     }
01511     r.free<View>(xs,size());
01512     r.free<ViewY>(ys,y.size());
01513     return false;
01514   }
01515 
01516   template<class View>
01517   void*
01518   ViewArray<View>::operator new(size_t) {
01519     return NULL;
01520   }
01521 
01522   template<class View>
01523   void
01524   ViewArray<View>::operator delete(void*,size_t) {
01525   }
01526 
01527 
01528   /*
01529    * Argument arrays: base class
01530    *
01531    */
01532 
01533   template<class T>
01534   forceinline T*
01535   ArgArrayBase<T>::allocate(int n) {
01536     return (n > onstack_size) ?
01537       heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01538   }
01539 
01540   template<class T>
01541   forceinline void
01542   ArgArrayBase<T>::resize(int i) {
01543     if (n+i >= capacity) {
01544       assert(n+i >= onstack_size);
01545       int newCapacity = (3*capacity)/2;
01546       if (newCapacity <= n+i)
01547         newCapacity = n+i;
01548       T* newA = allocate(newCapacity);
01549       heap.copy<T>(newA,a,n);
01550       if (capacity > onstack_size)
01551         heap.free(a,capacity);
01552       capacity = newCapacity;
01553       a = newA;
01554     }
01555   }
01556 
01557   template<class T>
01558   forceinline
01559   ArgArrayBase<T>::ArgArrayBase(void)
01560     : n(0), capacity(onstack_size), a(allocate(0)) {}
01561 
01562   template<class T>
01563   forceinline
01564   ArgArrayBase<T>::ArgArrayBase(int n0)
01565     : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
01566 
01567   template<class T>
01568   inline
01569   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01570     : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {
01571     heap.copy<T>(a,aa.a,n);
01572   }
01573 
01574   template<class T>
01575   forceinline
01576   ArgArrayBase<T>::~ArgArrayBase(void) {
01577     if (capacity > onstack_size)
01578       heap.free(a,capacity);
01579   }
01580 
01581   template<class T>
01582   forceinline const ArgArrayBase<T>&
01583   ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01584     if (&aa != this) {
01585       if (capacity > onstack_size)
01586         heap.free(a,capacity);
01587       n = aa.n;
01588       capacity = (n < onstack_size ? onstack_size : n);
01589       a = allocate(aa.n);
01590       heap.copy<T>(a,aa.a,n);
01591     }
01592     return *this;
01593   }
01594 
01595   template<class T>
01596   forceinline int
01597   ArgArrayBase<T>::size(void) const {
01598     return n;
01599   }
01600 
01601   template<class T>
01602   forceinline T&
01603   ArgArrayBase<T>::operator [](int i) {
01604     assert((i>=0) && (i < n));
01605     return a[i];
01606   }
01607 
01608   template<class T>
01609   forceinline const T&
01610   ArgArrayBase<T>::operator [](int i) const {
01611     assert((i>=0) && (i < n));
01612     return a[i];
01613   }
01614 
01615   template<class T>
01616   forceinline typename ArgArrayBase<T>::iterator
01617   ArgArrayBase<T>::begin(void) {
01618     return a;
01619   }
01620 
01621   template<class T>
01622   forceinline typename ArgArrayBase<T>::const_iterator
01623   ArgArrayBase<T>::begin(void) const {
01624     return a;
01625   }
01626 
01627   template<class T>
01628   forceinline typename ArgArrayBase<T>::iterator
01629   ArgArrayBase<T>::end(void) {
01630     return a+n;
01631   }
01632 
01633   template<class T>
01634   forceinline typename ArgArrayBase<T>::const_iterator
01635   ArgArrayBase<T>::end(void) const {
01636     return a+n;
01637   }
01638 
01639   template<class T>
01640   forceinline typename ArgArrayBase<T>::reverse_iterator
01641   ArgArrayBase<T>::rbegin(void) {
01642     return reverse_iterator(a+n);
01643   }
01644 
01645   template<class T>
01646   forceinline typename ArgArrayBase<T>::const_reverse_iterator
01647   ArgArrayBase<T>::rbegin(void) const {
01648     return const_reverse_iterator(a+n);
01649   }
01650 
01651   template<class T>
01652   forceinline typename ArgArrayBase<T>::reverse_iterator
01653   ArgArrayBase<T>::rend(void) {
01654     return reverse_iterator(a);
01655   }
01656 
01657   template<class T>
01658   forceinline typename ArgArrayBase<T>::const_reverse_iterator
01659   ArgArrayBase<T>::rend(void) const {
01660     return const_reverse_iterator(a);
01661   }
01662 
01663   template<class T> template<class A>
01664   A
01665   ArgArrayBase<T>::slice(int start, int inc, int maxN) {
01666     assert(start < n);
01667     if (maxN<0)
01668       maxN = n;
01669     int s;
01670     if (inc == 0)
01671       s = n-start;
01672     else if (inc > 0)
01673       s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1);
01674     else
01675       s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1);
01676     A r(std::min(maxN,s));
01677     for (int i=0; i<r.size(); i++, start+=inc)
01678       new (&r[i]) T(a[start]);
01679     return r;
01680   }
01681 
01682   template<class T> template<class A>
01683   inline A&
01684   ArgArrayBase<T>::append(const T& x) {
01685     resize(1);
01686     new (&a[n++]) T(x);
01687     return static_cast<A&>(*this);
01688   }
01689 
01690   template<class T> template<class A>
01691   inline A&
01692   ArgArrayBase<T>::append(const ArgArrayBase<T>& x) {
01693     resize(x.size());
01694     for (int i=0; i<x.size(); i++)
01695       new (&a[n++]) T(x[i]);
01696     return static_cast<A&>(*this);
01697   }
01698 
01699   template<class T> template<class A>
01700   inline A
01701   ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const {
01702     A r(n+x.n);
01703     for (int i=n; i--;)
01704       new (&r[i]) T(a[i]);
01705     for (int i=x.n; i--;)
01706       new (&r[n+i]) T(x.a[i]);
01707     return r;
01708   }
01709 
01710   template<class T> template<class A>
01711   inline A
01712   ArgArrayBase<T>::concat(const T& x) const {
01713     A r(n+1);
01714     for (int i=n; i--;)
01715       new (&r[i]) T(a[i]);
01716     new (&r[n]) T(x);
01717     return r;
01718   }
01719 
01720   /*
01721    * Argument arrays for primitive types
01722    *
01723    */
01724 
01725   template<class T>
01726   forceinline
01727   PrimArgArray<T>::PrimArgArray(void) {}
01728 
01729   template<class T>
01730   forceinline
01731   PrimArgArray<T>::PrimArgArray(int n) : ArgArrayBase<T>(n) {}
01732 
01733   template<class T>
01734   PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
01735     : ArgArrayBase<T>(n) {
01736     va_list args;
01737     va_start(args, a0);
01738     a[0] = a0;
01739     for (int i = 1; i < n; i++)
01740       a[i] = va_arg(args,T);
01741     va_end(args);
01742   }
01743 
01744   template<class T>
01745   PrimArgArray<T>::PrimArgArray(int n, const T* a0)
01746     : ArgArrayBase<T>(n) {
01747     for (int i=n; i--; )
01748       a[i] = a0[i];
01749   }
01750 
01751   template<class T>
01752   forceinline
01753   PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
01754     : ArgArrayBase<T>(aa) {}
01755 
01756   template<class T>
01757   forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType
01758   PrimArgArray<T>::slice(int start, int inc, int maxN) {
01759     return ArgArrayBase<T>::template slice
01760       <typename ArrayTraits<PrimArgArray<T> >::ArgsType>
01761         (start,inc,maxN);
01762   }
01763 
01764   template<class T>
01765   forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
01766   PrimArgArray<T>::operator <<(const T& x) {
01767     return
01768       ArgArrayBase<T>::template append
01769         <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
01770   }
01771 
01772   template<class T>
01773   forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType&
01774   PrimArgArray<T>::operator <<(const PrimArgArray<T>& x) {
01775     return
01776       ArgArrayBase<T>::template append
01777         <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x);
01778   }
01779 
01780   template<class T>
01781   typename ArrayTraits<PrimArgArray<T> >::ArgsType
01782   operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y) {
01783     return x.template concat
01784       <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);
01785   }
01786 
01787   template<class T>
01788   typename ArrayTraits<PrimArgArray<T> >::ArgsType
01789   operator +(const PrimArgArray<T>& x, const T& y) {
01790     return x.template concat
01791       <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);    
01792   }
01793 
01794   template<class T>
01795   typename ArrayTraits<PrimArgArray<T> >::ArgsType
01796   operator +(const T& x, const PrimArgArray<T>& y) {
01797     return PrimArgArray<T>(1,x).template concat
01798       <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y);    
01799   }
01800 
01801 
01802   /*
01803    * Argument arrays for non-primitive types
01804    *
01805    */
01806 
01807   template<class T>
01808   forceinline
01809   ArgArray<T>::ArgArray(void) {}
01810 
01811   template<class T>
01812   forceinline
01813   ArgArray<T>::ArgArray(int n) : ArgArrayBase<T>(n) {}
01814 
01815   template<class T>
01816   ArgArray<T>::ArgArray(int n, const T* a0)
01817     : ArgArrayBase<T>(n) {
01818     for (int i=n; i--; )
01819       a[i] = a0[i];
01820   }
01821 
01822   template<class T>
01823   forceinline
01824   ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01825     : ArgArrayBase<T>(aa) {}
01826 
01827   template<class T>
01828   forceinline typename ArrayTraits<ArgArray<T> >::ArgsType
01829   ArgArray<T>::slice(int start, int inc, int maxN) {
01830     return ArgArrayBase<T>::template slice
01831       <typename ArrayTraits<ArgArray<T> >::ArgsType>
01832       (start,inc,maxN);
01833   }
01834 
01835   template<class T>
01836   forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
01837   ArgArray<T>::operator <<(const T& x) {
01838     return
01839       ArgArrayBase<T>::template append
01840         <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
01841   }
01842 
01843   template<class T>
01844   forceinline typename ArrayTraits<ArgArray<T> >::ArgsType&
01845   ArgArray<T>::operator <<(const ArgArray<T>& x) {
01846     return
01847       ArgArrayBase<T>::template append
01848         <typename ArrayTraits<ArgArray<T> >::ArgsType>(x);
01849   }
01850 
01851   template<class T>
01852   typename ArrayTraits<ArgArray<T> >::ArgsType
01853   operator +(const ArgArray<T>& x, const ArgArray<T>& y) {
01854     return x.template concat
01855       <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);
01856   }
01857 
01858   template<class T>
01859   typename ArrayTraits<ArgArray<T> >::ArgsType
01860   operator +(const ArgArray<T>& x, const T& y) {
01861     return x.template concat
01862       <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);    
01863   }
01864 
01865   template<class T>
01866   typename ArrayTraits<ArgArray<T> >::ArgsType
01867   operator +(const T& x, const ArgArray<T>& y) {
01868     ArgArray<T> xa(1);
01869     xa[0] = x;
01870     return xa.template concat
01871       <typename ArrayTraits<ArgArray<T> >::ArgsType>(y);    
01872   }
01873 
01874   /*
01875    * Argument arrays for variables
01876    *
01877    */
01878 
01879   template<class Var>
01880   forceinline
01881   VarArgArray<Var>::VarArgArray(void) {}
01882 
01883   template<class Var>
01884   forceinline
01885   VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {}
01886 
01887   template<class Var>
01888   forceinline
01889   VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01890     : ArgArrayBase<Var>(aa) {}
01891 
01892   template<class Var>
01893   inline
01894   VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01895     : ArgArrayBase<Var>(x.size()) {
01896     for (int i=x.size(); i--; )
01897       a[i]=x[i];
01898   }
01899 
01900   template<class Var>
01901   forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType
01902   VarArgArray<Var>::slice(int start, int inc, int maxN) {
01903     return ArgArrayBase<Var>::template slice
01904       <typename ArrayTraits<VarArgArray<Var> >::ArgsType>
01905         (start,inc,maxN);
01906   }
01907 
01908   template<class Var>
01909   forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
01910   VarArgArray<Var>::operator <<(const Var& x) {
01911     return
01912       ArgArrayBase<Var>::template append
01913         <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
01914   }
01915 
01916   template<class Var>
01917   forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType&
01918   VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) {
01919     return
01920       ArgArrayBase<Var>::template append
01921         <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x);
01922   }
01923 
01924   template<class Var>
01925   typename ArrayTraits<VarArgArray<Var> >::ArgsType
01926   operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) {
01927     return x.template concat
01928       <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);
01929   }
01930 
01931   template<class Var>
01932   typename ArrayTraits<VarArgArray<Var> >::ArgsType
01933   operator +(const VarArgArray<Var>& x, const Var& y) {
01934     return x.template concat
01935       <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);    
01936   }
01937 
01938   template<class Var>
01939   typename ArrayTraits<VarArgArray<Var> >::ArgsType
01940   operator +(const Var& x, const VarArgArray<Var>& y) {
01941     VarArgArray<Var> xa(1);
01942     xa[0] = x;
01943     return xa.template concat
01944       <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y);    
01945   }
01946 
01947   template<class Var>
01948   forceinline bool
01949   VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) {
01950     return a.varimp() < b.varimp();
01951   }
01952 
01953   template<class Var>
01954   forceinline bool
01955   VarArgArray<Var>::assigned(void) const {
01956     for (int i = n; i--;)
01957       if (!a[i].assigned())
01958         return false;
01959     return true;
01960   }
01961 
01962   template<class Var>
01963   bool
01964   VarArgArray<Var>::same(const Space& home) const {
01965     if (n < 2)
01966       return false;
01967     Region r(home);
01968     Var* y = r.alloc<Var>(n);
01969     for (int i = n; i--; )
01970       y[i] = a[i];
01971     VarLess vl;
01972     Support::quicksort<Var,VarLess>(y,n,vl);
01973     for (int i = n-1; i--; )
01974       if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) {
01975         r.free<Var>(y,n);
01976         return true;
01977       }
01978     r.free<Var>(y,n);
01979     return false;
01980   }
01981 
01982   template<class Var>
01983   bool
01984   VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
01985     int m = n + y.n;
01986     if (m < 2)
01987       return false;
01988     Region r(home);
01989     Var* z = r.alloc<Var>(m);
01990     for (int i = n; i--; )
01991       z[i] = a[i];
01992     for (int i = y.n; i--; )
01993       z[i+n] = y.a[i];
01994     VarLess vl;
01995     Support::quicksort<Var,VarLess>(z,m,vl);
01996     for (int i = m-1; i--; )
01997       if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) {
01998         r.free<Var>(z,m);
01999         return true;
02000       }
02001     r.free<Var>(z,m);
02002     return false;
02003   }
02004 
02005   template<class Var>
02006   bool
02007   VarArgArray<Var>::same(const Space&, const Var& y) const {
02008     if (y.assigned())
02009       return false;
02010     for (int i = n; i--; )
02011       if (a[i].varimp() == y.varimp())
02012         return true;
02013     return false;
02014   }
02015 
02016 
02017 
02018 
02019 
02020 
02021   /*
02022    * Interdependent code
02023    *
02024    */
02025 
02026   template<class Var>
02027   inline
02028   VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
02029     : n(a.size()) {
02030     if (n>0) {
02031       x = home.alloc<Var>(n);
02032       for (int i=n; i--;)
02033         x[i] = a[i];
02034     } else {
02035       x = NULL;
02036     }
02037   }
02038 
02039 
02040   /*
02041    * Printing of arrays
02042    *
02043    */
02044   template<class Char, class Traits, class Var>
02045   std::basic_ostream<Char,Traits>&
02046   operator <<(std::basic_ostream<Char,Traits>& os,
02047              const VarArray<Var>& x) {
02048     std::basic_ostringstream<Char,Traits> s;
02049     s.copyfmt(os); s.width(0);
02050     s << '{';
02051     if (x.size() > 0) {
02052       s << x[0];
02053       for (int i=1; i<x.size(); i++)
02054         s << ", " << x[i];
02055     }
02056     s << '}';
02057     return os << s.str();
02058   }
02059 
02060   template<class Char, class Traits, class View>
02061   std::basic_ostream<Char,Traits>&
02062   operator <<(std::basic_ostream<Char,Traits>& os,
02063              const ViewArray<View>& x) {
02064     std::basic_ostringstream<Char,Traits> s;
02065     s.copyfmt(os); s.width(0);
02066     s << '{';
02067     if (x.size() > 0) {
02068       s << x[0];
02069       for (int i=1; i<x.size(); i++)
02070         s << ", " << x[i];
02071     }
02072     s << '}';
02073     return os << s.str();
02074   }
02075 
02076   template<class Char, class Traits, class T>
02077   std::basic_ostream<Char,Traits>&
02078   operator <<(std::basic_ostream<Char,Traits>& os,
02079              const ArgArrayBase<T>& x) {
02080     std::basic_ostringstream<Char,Traits> s;
02081     s.copyfmt(os); s.width(0);
02082     s << '{';
02083     if (x.size() > 0) {
02084       s << x[0];
02085       for (int i=1; i<x.size(); i++)
02086         s << ", " << x[i];
02087     }
02088     s << '}';
02089     return os << s.str();
02090   }
02091 
02092 }
02093 
02094 // STATISTICS: kernel-other