Generated on Mon May 10 06:46:33 2010 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  *  Copyright:
00008  *     Christian Schulte, 2003
00009  *     Guido Tack, 2004
00010  *
00011  *  Last modified:
00012  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00013  *     $Revision: 10684 $
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 <cstdarg>
00041 #include <iostream>
00042 #include <sstream>
00043 
00044 namespace Gecode {
00045 
00046   template<class Var> class VarArray;
00047   template<class Var> class VarArgArray;
00048 
00064   template<class Var>
00065   class VarArray {
00066   protected:
00068     int n;
00070     int capacity;
00072     Var* x;
00073   public:
00075 
00076 
00077     VarArray(void);
00079     VarArray(Space& home, int m);
00081     VarArray(Space& home, const VarArgArray<Var>&);
00083     VarArray(const VarArray<Var>& a);
00085     const VarArray<Var>& operator =(const VarArray<Var>& a);
00087     ~VarArray(void);
00089 
00091 
00092 
00093     int size(void) const;
00098     void resize(Space& home, int m);
00100 
00102 
00103 
00104     Var& operator [](int i);
00106     const Var& operator [](int i) const;
00108     void add(Space& home, const Var& v);
00110 
00112 
00113 
00120     void update(Space&, bool share, VarArray<Var>& a);
00122   private:
00123     static void* operator new(size_t);
00124     static void  operator delete(void*,size_t);
00125   };
00126 
00127 
00136   template<class View>
00137   class ViewArray {
00138   private:
00140     int  n;
00142     View* x;
00144     template<class X>
00145     class ViewLess {
00146     public:
00147       bool operator ()(const X&, const X&);
00148     };
00150     static void sort(View* x, int n);
00151   public:
00153 
00154 
00155     ViewArray(void);
00157     ViewArray(Space& home, int m);
00159     ViewArray(const ViewArray<View>& a);
00161     ViewArray(Space& home, const ViewArray<View>& a);
00163     const ViewArray<View>& operator =(const ViewArray<View>& a);
00170     template<class Var>
00171     ViewArray(Space& home, const VarArgArray<Var>& a)
00172       : n(a.size()) {
00173       // This may not be in the hpp file (to satisfy the MS compiler)
00174       if (n>0) {
00175         x = home.alloc<View>(n);
00176         for (int i=n; i--; )
00177           x[i]=a[i];
00178       } else {
00179         x = NULL;
00180       }
00181     }
00183 
00185 
00186 
00187     int size(void) const;
00189     void size(int n);
00191 
00193 
00194 
00195     View& operator [](int i);
00197     const View& operator [](int i) const;
00199 
00201 
00202 
00209     void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00211     void cancel(Space& home, Propagator& p, PropCond pc);
00213     void subscribe(Space& home, Advisor& a);
00215     void cancel(Space& home, Advisor& a);
00217 
00219 
00220 
00227     void update(Space&, bool share, ViewArray<View>& a);
00229 
00230 
00232 
00233 
00234     void move_fst(int i);
00236     void move_lst(int i);
00242     void move_fst(int i, Space& home, Propagator& p, PropCond pc);
00248     void move_lst(int i, Space& home, Propagator& p, PropCond pc);
00254     void move_fst(int i, Space& home, Advisor& a);
00260     void move_lst(int i, Space& home, Advisor& a);
00262 
00264 
00265 
00266     void drop_fst(int i);
00268     void drop_lst(int i);
00274     void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
00281     void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
00287     void drop_fst(int i, Space& home, Advisor& a);
00293     void drop_lst(int i, Space& home, Advisor& a);
00295 
00297 
00298 
00303     bool same(const Space& home) const;
00309     bool same(const Space& home, const View& y) const;
00311     void unique(const Space& home);
00313 
00315 
00316 
00321     bool shared(const Space& home) const;
00327     template<class ViewY>
00328     bool shared(const Space& home, const ViewY& y) const;
00334     template<class ViewY>
00335     bool shared(const Space& home, const ViewArray<ViewY>& y) const;
00337 
00338   private:
00339     static void* operator new(size_t);
00340     static void  operator delete(void*,size_t);
00341   };
00342 
00356   template<class T>
00357   class ArgArrayBase {
00358   protected:
00360     int n;
00362     T*  a;
00364     static const int onstack_size = 16;
00366     T onstack[onstack_size];
00368     T* allocate(int n);
00369   public:
00371 
00372 
00373     ArgArrayBase(int n);
00375     ArgArrayBase(const ArgArrayBase<T>& a);
00377     const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
00379 
00381 
00382 
00383     int size(void) const;
00385 
00387 
00388 
00389     T& operator [](int i);
00391     const T& operator [](int i) const;
00393 
00395 
00396 
00397     ~ArgArrayBase(void);
00399   private:
00400     static void* operator new(size_t);
00401     static void  operator delete(void*,size_t);
00402   };
00403 
00404 
00416   template<class T>
00417   class PrimArgArray : public ArgArrayBase<T> {
00418   protected:
00419     using ArgArrayBase<T>::a;
00420   public:
00421     using ArgArrayBase<T>::size;
00423 
00424 
00425     explicit PrimArgArray(int n);
00427     PrimArgArray(int n, T e0, ...);
00429     PrimArgArray(int n, const T* e);
00431     PrimArgArray(const PrimArgArray<T>& a);
00433   };
00434 
00446   template<class T>
00447   class ArgArray : public ArgArrayBase<T> {
00448   protected:
00449     using ArgArrayBase<T>::a;
00450   public:
00451     using ArgArrayBase<T>::size;
00453 
00454 
00455     explicit ArgArray(int n);
00457     ArgArray(int n, const T* e);
00459     ArgArray(const ArgArray<T>& a);
00461   };
00462 
00474   template<class Var>
00475   class VarArgArray : public ArgArrayBase<Var> {
00476   protected:
00477     using ArgArrayBase<Var>::a;
00478     using ArgArrayBase<Var>::n;
00480     class VarLess {
00481     public:
00482       bool operator ()(const Var&, const Var&);
00483     };
00484   public:
00485     using ArgArrayBase<Var>::size;
00487 
00488 
00489     explicit VarArgArray(int n);
00491     VarArgArray(const VarArgArray<Var>& a);
00493     VarArgArray(const VarArray<Var>& a);
00495 
00496 
00497 
00502     bool same(const Space& home) const;
00508     bool same(const Space& home, const Var& y) const;
00514     bool same(const Space& home, const VarArgArray<Var>& y) const;
00516   };
00517 
00522   template<class Char, class Traits, class Var>
00523   std::basic_ostream<Char,Traits>&
00524   operator <<(std::basic_ostream<Char,Traits>& os,
00525              const VarArray<Var>& x);
00526 
00531   template<class Char, class Traits, class View>
00532   std::basic_ostream<Char,Traits>&
00533   operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
00534 
00539   template<class Char, class Traits, class T>
00540   std::basic_ostream<Char,Traits>&
00541   operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
00542 
00543 
00544 
00557   template<class A>
00558   class ArrayTraits {};
00559 
00560   /*
00561    * Implementation
00562    *
00563    */
00564 
00565   /*
00566    * Variable arrays
00567    *
00568    * These arrays are usually allocated in the space, but if they are resized,
00569    * the new array is allocated on the heap. The size (n) and capacity show
00570    * where the array is allocated: it is in the space if and only if
00571    * n==capacity.
00572    *
00573    */
00574 
00575   template<class Var>
00576   forceinline
00577   VarArray<Var>::VarArray(void) : n(0), capacity(0), x(NULL) {}
00578 
00579   template<class Var>
00580   forceinline
00581   VarArray<Var>::VarArray(Space& home, int n0)
00582     : n(n0), capacity(n0) {
00583     // Allocate from space
00584     x = (n>0) ? home.alloc<Var>(n) : NULL;
00585   }
00586 
00587   template<class Var>
00588   forceinline
00589   VarArray<Var>::VarArray(const VarArray<Var>& a) {
00590     n = a.n; capacity = a.capacity; x = a.x;
00591   }
00592 
00593   template<class Var>
00594   forceinline
00595   VarArray<Var>::~VarArray(void) {
00596     if (n != capacity) {
00597       // Array was allocated on the heap
00598       heap.free<Var>(x, capacity);
00599     }
00600   }
00601 
00602   template<class Var>
00603   forceinline const VarArray<Var>&
00604   VarArray<Var>::operator =(const VarArray<Var>& a) {
00605     n = a.n; capacity = a.capacity; x = a.x;
00606     return *this;
00607   }
00608 
00609   template<class Var>
00610   forceinline int
00611   VarArray<Var>::size(void) const {
00612     return n;
00613   }
00614 
00615   template<class Var>
00616   forceinline void
00617   VarArray<Var>::resize(Space& home, int m) {
00618     int newsize;
00619     int newn;
00620     if (m<n) {
00621       // Shrink array and leave capacity at m+1, forcing heap allocation
00622       newsize = m+1;
00623       newn = m;
00624     } else if (m<capacity) {
00625       // As m>=n<capacity, the array is heap allocated, just resize
00626       n = m;
00627       return;
00628     } else {
00629       // Resize, so that newsize != m forcing heap allocation
00630       newsize = std::max(m+1, (3*capacity)/2);
00631       newn = n;
00632     }
00633 
00634     if (n == capacity) {
00635       // Array was space allocated, copy to heap with new size
00636       Var* oldx = x;
00637       x = heap.copy<Var>(heap.alloc<Var>(newsize), x, newn);
00638       home.rfree(oldx, capacity);
00639     } else {
00640       // Array was heap allocated, just reallocate with new size
00641       x = heap.realloc<Var>(x, n, newsize);
00642     }
00643     capacity = newsize; n = m;
00644     // After resizing, the array is always heap allocated
00645     assert(capacity != n);
00646   }
00647 
00648   template<class Var>
00649   forceinline Var&
00650   VarArray<Var>::operator [](int i) {
00651     assert((i >= 0) && (i < size()));
00652     return x[i];
00653   }
00654 
00655   template<class Var>
00656   forceinline const Var&
00657   VarArray<Var>::operator [](int i) const {
00658     assert((i >= 0) && (i < size()));
00659     return x[i];
00660   }
00661 
00662   template<class Var>
00663   forceinline void
00664   VarArray<Var>::add(Space& home, const Var& v) {
00665     resize(home, n+1);
00666     new (&(*this)[n-1]) Var(v);
00667   }
00668 
00669   template<class Var>
00670   forceinline void
00671   VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) {
00672     capacity = a.n;
00673     n = capacity;
00674     if (capacity > 0) {
00675       x = home.alloc<Var>(capacity);
00676       for (int i = capacity; i--; )
00677         x[i].update(home, share, a.x[i]);
00678     } else {
00679       x = NULL;
00680     }
00681   }
00682 
00683   template<class Var>
00684   void*
00685   VarArray<Var>::operator new(size_t) {
00686     return NULL;
00687   }
00688 
00689   template<class Var>
00690   void
00691   VarArray<Var>::operator delete(void*,size_t) {
00692   }
00693 
00694   /*
00695    * View arrays
00696    *
00697    */
00698 
00699   template<class View>
00700   forceinline
00701   ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00702 
00703   template<class View>
00704   forceinline
00705   ViewArray<View>::ViewArray(Space& home, int n0)
00706     : n(n0) {
00707     x = (n>0) ? home.alloc<View>(n) : NULL;
00708   }
00709 
00710   template<class View>
00711   ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
00712     : n(a.size()) {
00713     if (n>0) {
00714       x = home.alloc<View>(n);
00715       for (int i = n; i--; )
00716         x[i] = a[i];
00717     } else {
00718       x = NULL;
00719     }
00720   }
00721 
00722   template<class View>
00723   forceinline
00724   ViewArray<View>::ViewArray(const ViewArray<View>& a)
00725     : n(a.n), x(a.x) {}
00726 
00727   template<class View>
00728   forceinline const ViewArray<View>&
00729   ViewArray<View>::operator =(const ViewArray<View>& a) {
00730     n = a.n; x = a.x;
00731     return *this;
00732   }
00733 
00734   template<class View>
00735   forceinline int
00736   ViewArray<View>::size(void) const {
00737     return n;
00738   }
00739 
00740   template<class View>
00741   forceinline void
00742   ViewArray<View>::size(int n0) {
00743     n = n0;
00744   }
00745 
00746   template<class View>
00747   forceinline View&
00748   ViewArray<View>::operator [](int i) {
00749     assert((i >= 0) && (i < size()));
00750     return x[i];
00751   }
00752 
00753   template<class View>
00754   forceinline const View&
00755   ViewArray<View>::operator [](int i) const {
00756     assert((i >= 0) && (i < size()));
00757     return x[i];
00758   }
00759 
00760   template<class View>
00761   forceinline void
00762   ViewArray<View>::move_fst(int i) {
00763     x[i]=x[0]; x++; n--;
00764   }
00765 
00766   template<class View>
00767   forceinline void
00768   ViewArray<View>::move_lst(int i) {
00769     n--; x[i]=x[n];
00770   }
00771 
00772   template<class View>
00773   forceinline void
00774   ViewArray<View>::drop_fst(int i) {
00775     assert(i>=0);
00776     x += i; n -= i;
00777   }
00778 
00779   template<class View>
00780   forceinline void
00781   ViewArray<View>::drop_lst(int i) {
00782     assert(i<n);
00783     n = i+1;
00784   }
00785 
00786   template<class View>
00787   forceinline void
00788   ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
00789     // Move x[0] to x[i]
00790     x[i].cancel(home,p,pc);
00791     x[i]=x[0]; x++; n--;
00792   }
00793 
00794   template<class View>
00795   forceinline void
00796   ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
00797     // Move x[n-1] to x[i]
00798     x[i].cancel(home,p,pc);
00799     n--; x[i]=x[n];
00800   }
00801 
00802   template<class View>
00803   void
00804   ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
00805     // Drop elements from 0..i-1
00806     assert(i>=0);
00807     for (int j=i; j--; )
00808       x[j].cancel(home,p,pc);
00809     x += i; n -= i;
00810   }
00811 
00812   template<class View>
00813   void
00814   ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
00815     // Drop elements from i+1..n-1
00816     assert(i<n);
00817     for (int j=i+1; j<n; j++)
00818       x[j].cancel(home,p,pc);
00819     n = i+1;
00820   }
00821 
00822   template<class View>
00823   forceinline void
00824   ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
00825     // Move x[0] to x[i]
00826     x[i].cancel(home,a);
00827     x[i]=x[0]; x++; n--;
00828   }
00829 
00830   template<class View>
00831   forceinline void
00832   ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
00833     // Move x[n-1] to x[i]
00834     x[i].cancel(home,a);
00835     n--; x[i]=x[n];
00836   }
00837 
00838   template<class View>
00839   void
00840   ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
00841     // Drop elements from 0..i-1
00842     assert(i>=0);
00843     for (int j=i; j--; )
00844       x[j].cancel(home,a);
00845     x += i; n -= i;
00846   }
00847 
00848   template<class View>
00849   void
00850   ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
00851     // Drop elements from i+1..n-1
00852     assert(i<n);
00853     for (int j=i+1; j<n; j++)
00854       x[j].cancel(home,a);
00855     n = i+1;
00856   }
00857 
00858   template<class View>
00859   void
00860   ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) {
00861     n = y.n;
00862     if (n > 0) {
00863       x = home.alloc<View>(n);
00864       for (int i = n; i--; )
00865         x[i].update(home, share, y.x[i]);
00866     } else {
00867       x = NULL;
00868     }
00869   }
00870 
00871   template<class View>
00872   void
00873   ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00874                              bool process) {
00875     for (int i = n; i--; )
00876       x[i].subscribe(home,p,pc,process);
00877   }
00878 
00879   template<class View>
00880   void
00881   ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00882     for (int i = n; i--; )
00883       x[i].cancel(home,p,pc);
00884   }
00885 
00886   template<class View>
00887   void
00888   ViewArray<View>::subscribe(Space& home, Advisor& a) {
00889     for (int i = n; i--; )
00890       x[i].subscribe(home,a);
00891   }
00892 
00893   template<class View>
00894   void
00895   ViewArray<View>::cancel(Space& home, Advisor& a) {
00896     for (int i = n; i--; )
00897       x[i].cancel(home,a);
00898   }
00899 
00900   template<class View>
00901   forceinline bool
00902   __before(const View& x, const View& y) {
00903     return before(x,y);
00904   }
00905 
00906   template<class View> template<class X>
00907   forceinline bool
00908   ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
00909     return __before(a,b);
00910   }
00911 
00912   template<class View>
00913   void
00914   ViewArray<View>::sort(View* y, int m) {
00915     ViewLess<View> vl;
00916     Support::quicksort<View,ViewLess<View> >(y,m,vl);
00917   }
00918 
00919   template<class X, class Y>
00920   forceinline bool
00921   __same(const X& x, const Y& y) {
00922     return same(x,y);
00923   }
00924   template<class X, class Y>
00925   forceinline bool
00926   __shared(const X& x, const Y& y) {
00927     return shared(x,y);
00928   }
00929 
00930   template<class View>
00931   bool
00932   ViewArray<View>::same(const Space& home) const {
00933     if (n < 2)
00934       return false;
00935     Region r(home);
00936     View* y = r.alloc<View>(n);
00937     for (int i = n; i--; )
00938       y[i] = x[i];
00939     sort(y,n);
00940     for (int i = n-1; i--; )
00941       if (!y[i].assigned() && __same(y[i+1],y[i])) {
00942         r.free<View>(y,n);
00943         return true;
00944       }
00945     r.free<View>(y,n);
00946     return false;
00947   }
00948 
00949   template<class View>
00950   bool
00951   ViewArray<View>::same(const Space&, const View& y) const {
00952     if (y.assigned())
00953       return false;
00954     for (int i = n; i--; )
00955       if (__same(x[i],y))
00956         return true;
00957     return false;
00958   }
00959 
00960   template<class View>
00961   void
00962   ViewArray<View>::unique(const Space&) {
00963     if (n < 2)
00964       return;
00965     sort(x,n);
00966     int j = 0;
00967     for (int i = 1; i<n; i++)
00968       if (!__same(x[j],x[i]))
00969         x[++j] = x[i];
00970     n = j+1;
00971   }
00972 
00973   template<class View>
00974   bool
00975   ViewArray<View>::shared(const Space& home) const {
00976     if (n < 2)
00977       return false;
00978     Region r(home);
00979     View* y = r.alloc<View>(n);
00980     for (int i = n; i--; )
00981       y[i] = x[i];
00982     sort(y,n);
00983     for (int i = n-1; i--; )
00984       if (!y[i].assigned() && __shared(y[i+1],y[i])) {
00985         r.free<View>(y,n);
00986         return true;
00987       }
00988     r.free<View>(y,n);
00989     return false;
00990   }
00991 
00992   template<class View> template<class ViewY>
00993   bool
00994   ViewArray<View>::shared(const Space&, const ViewY& y) const {
00995     if (y.assigned())
00996       return false;
00997     for (int i = n; i--; )
00998       if (!x[i].assigned() && __shared(x[i],y))
00999         return true;
01000     return false;
01001   }
01002 
01003   template<class View> template<class ViewY>
01004   bool
01005   ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
01006     if ((size() < 1) || (y.size() < 1))
01007       return false;
01008     Region r(home);
01009     View* xs = r.alloc<View>(size());
01010     for (int i=size(); i--; )
01011       xs[i] = x[i];
01012     ViewLess<View> xvl;
01013     Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
01014     ViewY* ys = r.alloc<ViewY>(y.size());
01015     for (int j=y.size(); j--; )
01016       ys[j] = y[j];
01017     ViewLess<ViewY> yvl;
01018     Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
01019     {
01020       int i=0, j=0;
01021       while ((i < size()) && (j < y.size()))
01022         if (!x[i].assigned() && __shared(x[i],y[j])) {
01023           r.free<View>(xs,size());
01024           r.free<ViewY>(ys,y.size());
01025           return true;
01026         } else if (before(x[i],y[j])) {
01027           i++;
01028         } else {
01029           j++;
01030         }
01031     }
01032     r.free<View>(xs,size());
01033     r.free<ViewY>(ys,y.size());
01034     return false;
01035   }
01036 
01037   template<class View>
01038   void*
01039   ViewArray<View>::operator new(size_t) {
01040     return NULL;
01041   }
01042 
01043   template<class View>
01044   void
01045   ViewArray<View>::operator delete(void*,size_t) {
01046   }
01047 
01048 
01049   /*
01050    * Argument arrays: base class
01051    *
01052    */
01053 
01054   template<class T>
01055   forceinline T*
01056   ArgArrayBase<T>::allocate(int n) {
01057     return (n > onstack_size) ?
01058       heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01059   }
01060 
01061   template<class T>
01062   forceinline
01063   ArgArrayBase<T>::ArgArrayBase(int n0)
01064     : n(n0), a(allocate(n)) {}
01065 
01066   template<class T>
01067   inline
01068   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01069     : n(aa.n), a(allocate(n)) {
01070     heap.copy<T>(a,aa.a,n);
01071   }
01072 
01073   template<class T>
01074   forceinline
01075   ArgArrayBase<T>::~ArgArrayBase(void) {
01076     if (n > onstack_size)
01077       heap.free(a,n);
01078   }
01079 
01080   template<class T>
01081   forceinline const ArgArrayBase<T>&
01082   ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01083     if (&aa != this) {
01084       if (n > onstack_size)
01085         heap.free(a,n);
01086       n = aa.n;
01087       a = allocate(aa.n);
01088       heap.copy<T>(a,aa.a,n);
01089     }
01090     return *this;
01091   }
01092 
01093   template<class T>
01094   forceinline int
01095   ArgArrayBase<T>::size(void) const {
01096     return n;
01097   }
01098 
01099   template<class T>
01100   forceinline T&
01101   ArgArrayBase<T>::operator [](int i) {
01102     assert((i>=0) && (i < n));
01103     return a[i];
01104   }
01105 
01106   template<class T>
01107   forceinline const T&
01108   ArgArrayBase<T>::operator [](int i) const {
01109     assert((i>=0) && (i < n));
01110     return a[i];
01111   }
01112 
01113 
01114   /*
01115    * Argument arrays for primitive types
01116    *
01117    */
01118 
01119   template<class T>
01120   forceinline
01121   PrimArgArray<T>::PrimArgArray(int n)
01122     : ArgArrayBase<T>(n) {}
01123 
01124   template<class T>
01125   PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
01126     : ArgArrayBase<T>(n) {
01127     va_list args;
01128     va_start(args, a0);
01129     a[0] = a0;
01130     for (int i = 1; i < n; i++)
01131       a[i] = va_arg(args,T);
01132     va_end(args);
01133   }
01134 
01135   template<class T>
01136   PrimArgArray<T>::PrimArgArray(int n, const T* a0)
01137     : ArgArrayBase<T>(n) {
01138     for (int i=n; i--; )
01139       a[i] = a0[i];
01140   }
01141 
01142   template<class T>
01143   forceinline
01144   PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
01145     : ArgArrayBase<T>(aa) {}
01146 
01147 
01148   /*
01149    * Argument arrays for non-primitive types
01150    *
01151    */
01152 
01153   template<class T>
01154   forceinline
01155   ArgArray<T>::ArgArray(int n)
01156     : ArgArrayBase<T>(n) {}
01157 
01158   template<class T>
01159   ArgArray<T>::ArgArray(int n, const T* a0)
01160     : ArgArrayBase<T>(n) {
01161     for (int i=n; i--; )
01162       a[i] = a0[i];
01163   }
01164 
01165   template<class T>
01166   forceinline
01167   ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01168     : ArgArrayBase<T>(aa) {}
01169 
01170 
01171 
01172   /*
01173    * Argument arrays for variables
01174    *
01175    */
01176 
01177   template<class Var>
01178   forceinline
01179   VarArgArray<Var>::VarArgArray(int n)
01180     : ArgArrayBase<Var>(n) {}
01181 
01182   template<class Var>
01183   forceinline
01184   VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01185     : ArgArrayBase<Var>(aa) {}
01186 
01187   template<class Var>
01188   inline
01189   VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01190     : ArgArrayBase<Var>(x.size()) {
01191     for (int i=x.size(); i--; )
01192       a[i]=x[i];
01193   }
01194 
01195   template<class Var>
01196   forceinline bool
01197   VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) {
01198     return a.var() < b.var();
01199   }
01200 
01201   template<class Var>
01202   bool
01203   VarArgArray<Var>::same(const Space& home) const {
01204     if (n < 2)
01205       return false;
01206     Region r(home);
01207     Var* y = r.alloc<Var>(n);
01208     for (int i = n; i--; )
01209       y[i] = a[i];
01210     VarLess vl;
01211     Support::quicksort<Var,VarLess>(y,n,vl);
01212     for (int i = n-1; i--; )
01213       if (!y[i].assigned() && (y[i+1].var() == y[i].var())) {
01214         r.free<Var>(y,n);
01215         return true;
01216       }
01217     r.free<Var>(y,n);
01218     return false;
01219   }
01220 
01221   template<class Var>
01222   bool
01223   VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
01224     int m = n + y.n;
01225     if (m < 2)
01226       return false;
01227     Region r(home);
01228     Var* z = r.alloc<Var>(m);
01229     for (int i = n; i--; )
01230       z[i] = a[i];
01231     for (int i = y.n; i--; )
01232       z[i+n] = y.a[i];
01233     VarLess vl;
01234     Support::quicksort<Var,VarLess>(z,m,vl);
01235     for (int i = m-1; i--; )
01236       if (!z[i].assigned() && (z[i+1].var() == z[i].var())) {
01237         r.free<Var>(z,m);
01238         return true;
01239       }
01240     r.free<Var>(z,m);
01241     return false;
01242   }
01243 
01244   template<class Var>
01245   bool
01246   VarArgArray<Var>::same(const Space&, const Var& y) const {
01247     if (y.assigned())
01248       return false;
01249     for (int i = n; i--; )
01250       if (a[i].var() == y.var())
01251         return true;
01252     return false;
01253   }
01254 
01255 
01256 
01257 
01258 
01259 
01260   /*
01261    * Interdependent code
01262    *
01263    */
01264 
01265   template<class Var>
01266   inline
01267   VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
01268     : n(a.size()), capacity(a.size()) {
01269     if (capacity>0) {
01270       x = home.alloc<Var>(capacity);
01271       for (int i = capacity; i--; )
01272         x[i] = a[i];
01273     } else {
01274       x = NULL;
01275     }
01276   }
01277 
01278 
01279   /*
01280    * Printing of arrays
01281    *
01282    */
01283   template<class Char, class Traits, class Var>
01284   std::basic_ostream<Char,Traits>&
01285   operator <<(std::basic_ostream<Char,Traits>& os,
01286              const VarArray<Var>& x) {
01287     std::basic_ostringstream<Char,Traits> s;
01288     s.copyfmt(os); s.width(0);
01289     s << '{';
01290     if (x.size() > 0) {
01291       s << x[0];
01292       for (int i=1; i<x.size(); i++)
01293         s << ", " << x[i];
01294     }
01295     s << '}';
01296     return os << s.str();
01297   }
01298 
01299   template<class Char, class Traits, class View>
01300   std::basic_ostream<Char,Traits>&
01301   operator <<(std::basic_ostream<Char,Traits>& os,
01302              const ViewArray<View>& x) {
01303     std::basic_ostringstream<Char,Traits> s;
01304     s.copyfmt(os); s.width(0);
01305     s << '{';
01306     if (x.size() > 0) {
01307       s << x[0];
01308       for (int i=1; i<x.size(); i++)
01309         s << ", " << x[i];
01310     }
01311     s << '}';
01312     return os << s.str();
01313   }
01314 
01315   template<class Char, class Traits, class T>
01316   std::basic_ostream<Char,Traits>&
01317   operator <<(std::basic_ostream<Char,Traits>& os,
01318              const ArgArrayBase<T>& x) {
01319     std::basic_ostringstream<Char,Traits> s;
01320     s.copyfmt(os); s.width(0);
01321     s << '{';
01322     if (x.size() > 0) {
01323       s << x[0];
01324       for (int i=1; i<x.size(); i++)
01325         s << ", " << x[i];
01326     }
01327     s << '}';
01328     return os << s.str();
01329   }
01330 
01331 }
01332 
01333 // STATISTICS: kernel-other