Generated on Mon Nov 30 23:53:21 2009 for Gecode by doxygen 1.6.1

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: 2009-09-30 12:12:35 +0200 (Wed, 30 Sep 2009) $ by $Author: tack $
00013  *     $Revision: 9779 $
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     if (m<n) {
00620       // Shrink array and leave capacity at m+1, forcing heap allocation
00621       newsize = m+1;
00622     } else if (m<capacity) {
00623       // As m>=n<capacity, the array is heap allocated, just resize
00624       n = m;
00625       return;
00626     } else {
00627       // Resize, so that newsize != m forcing heap allocation
00628       newsize = std::max(m+1, (3*capacity)/2);
00629     }
00630 
00631     if (n == capacity) {
00632       // Array was space allocated, copy to heap with new size
00633       Var* oldx = x;
00634       x = heap.copy<Var>(heap.alloc<Var>(newsize), x, n);
00635       home.rfree(oldx, capacity);
00636     } else {
00637       // Array was heap allocated, just reallocate with new size
00638       x = heap.realloc<Var>(x, n, newsize);
00639     }
00640     capacity = newsize; n = m;
00641     // After resizing, the array is always heap allocated
00642     assert(capacity != n);
00643   }
00644 
00645   template<class Var>
00646   forceinline Var&
00647   VarArray<Var>::operator [](int i) {
00648     assert((i >= 0) && (i < size()));
00649     return x[i];
00650   }
00651 
00652   template<class Var>
00653   forceinline const Var&
00654   VarArray<Var>::operator [](int i) const {
00655     assert((i >= 0) && (i < size()));
00656     return x[i];
00657   }
00658 
00659   template<class Var>
00660   forceinline void
00661   VarArray<Var>::add(Space& home, const Var& v) {
00662     resize(home, n+1);
00663     new (&(*this)[n-1]) Var(v);
00664   }
00665 
00666   template<class Var>
00667   forceinline void
00668   VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) {
00669     capacity = a.n;
00670     n = capacity;
00671     if (capacity > 0) {
00672       x = home.alloc<Var>(capacity);
00673       for (int i = capacity; i--; )
00674         x[i].update(home, share, a.x[i]);
00675     } else {
00676       x = NULL;
00677     }
00678   }
00679 
00680   template<class Var>
00681   void*
00682   VarArray<Var>::operator new(size_t) {
00683     return NULL;
00684   }
00685 
00686   template<class Var>
00687   void
00688   VarArray<Var>::operator delete(void*,size_t) {
00689   }
00690 
00691   /*
00692    * View arrays
00693    *
00694    */
00695 
00696   template<class View>
00697   forceinline
00698   ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00699 
00700   template<class View>
00701   forceinline
00702   ViewArray<View>::ViewArray(Space& home, int n0)
00703     : n(n0) {
00704     x = (n>0) ? home.alloc<View>(n) : NULL;
00705   }
00706 
00707   template<class View>
00708   ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
00709     : n(a.size()) {
00710     if (n>0) {
00711       x = home.alloc<View>(n);
00712       for (int i = n; i--; )
00713         x[i] = a[i];
00714     } else {
00715       x = NULL;
00716     }
00717   }
00718 
00719   template<class View>
00720   forceinline
00721   ViewArray<View>::ViewArray(const ViewArray<View>& a)
00722     : n(a.n), x(a.x) {}
00723 
00724   template<class View>
00725   forceinline const ViewArray<View>&
00726   ViewArray<View>::operator =(const ViewArray<View>& a) {
00727     n = a.n; x = a.x;
00728     return *this;
00729   }
00730 
00731   template<class View>
00732   forceinline int
00733   ViewArray<View>::size(void) const {
00734     return n;
00735   }
00736 
00737   template<class View>
00738   forceinline void
00739   ViewArray<View>::size(int n0) {
00740     n = n0;
00741   }
00742 
00743   template<class View>
00744   forceinline View&
00745   ViewArray<View>::operator [](int i) {
00746     assert((i >= 0) && (i < size()));
00747     return x[i];
00748   }
00749 
00750   template<class View>
00751   forceinline const View&
00752   ViewArray<View>::operator [](int i) const {
00753     assert((i >= 0) && (i < size()));
00754     return x[i];
00755   }
00756 
00757   template<class View>
00758   forceinline void
00759   ViewArray<View>::move_fst(int i) {
00760     // move x[0] to x[i]
00761     assert(x[i].assigned());
00762     x[i]=x[0]; x++; n--;
00763   }
00764 
00765   template<class View>
00766   forceinline void
00767   ViewArray<View>::move_lst(int i) {
00768     // move x[n-1] to x[i]
00769     assert(x[i].assigned());
00770     n--; x[i]=x[n];
00771   }
00772 
00773   template<class View>
00774   forceinline void
00775   ViewArray<View>::drop_fst(int i) {
00776     // Drop elements from 0..i-1
00777     assert(i>=0);
00778     x += i; n -= i;
00779   }
00780 
00781   template<class View>
00782   forceinline void
00783   ViewArray<View>::drop_lst(int i) {
00784     // Drop elements from i+1..n-1
00785     assert(i<n);
00786     n = i+1;
00787   }
00788 
00789   template<class View>
00790   forceinline void
00791   ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
00792     // Move x[0] to x[i]
00793     x[i].cancel(home,p,pc);
00794     x[i]=x[0]; x++; n--;
00795   }
00796 
00797   template<class View>
00798   forceinline void
00799   ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
00800     // Move x[n-1] to x[i]
00801     x[i].cancel(home,p,pc);
00802     n--; x[i]=x[n];
00803   }
00804 
00805   template<class View>
00806   void
00807   ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
00808     // Drop elements from 0..i-1
00809     assert(i>=0);
00810     for (int j=i; j--; )
00811       x[j].cancel(home,p,pc);
00812     x += i; n -= i;
00813   }
00814 
00815   template<class View>
00816   void
00817   ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
00818     // Drop elements from i+1..n-1
00819     assert(i<n);
00820     for (int j=i+1; j<n; j++)
00821       x[j].cancel(home,p,pc);
00822     n = i+1;
00823   }
00824 
00825   template<class View>
00826   forceinline void
00827   ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
00828     // Move x[0] to x[i]
00829     x[i].cancel(home,a);
00830     x[i]=x[0]; x++; n--;
00831   }
00832 
00833   template<class View>
00834   forceinline void
00835   ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
00836     // Move x[n-1] to x[i]
00837     x[i].cancel(home,a);
00838     n--; x[i]=x[n];
00839   }
00840 
00841   template<class View>
00842   void
00843   ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
00844     // Drop elements from 0..i-1
00845     assert(i>=0);
00846     for (int j=i; j--; )
00847       x[j].cancel(home,a);
00848     x += i; n -= i;
00849   }
00850 
00851   template<class View>
00852   void
00853   ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
00854     // Drop elements from i+1..n-1
00855     assert(i<n);
00856     for (int j=i+1; j<n; j++)
00857       x[j].cancel(home,a);
00858     n = i+1;
00859   }
00860 
00861   template<class View>
00862   void
00863   ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) {
00864     n = y.n;
00865     if (n > 0) {
00866       x = home.alloc<View>(n);
00867       for (int i = n; i--; )
00868         x[i].update(home, share, y.x[i]);
00869     } else {
00870       x = NULL;
00871     }
00872   }
00873 
00874   template<class View>
00875   void
00876   ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00877                              bool process) {
00878     for (int i = n; i--; )
00879       x[i].subscribe(home,p,pc,process);
00880   }
00881 
00882   template<class View>
00883   void
00884   ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00885     for (int i = n; i--; )
00886       x[i].cancel(home,p,pc);
00887   }
00888 
00889   template<class View>
00890   void
00891   ViewArray<View>::subscribe(Space& home, Advisor& a) {
00892     for (int i = n; i--; )
00893       x[i].subscribe(home,a);
00894   }
00895 
00896   template<class View>
00897   void
00898   ViewArray<View>::cancel(Space& home, Advisor& a) {
00899     for (int i = n; i--; )
00900       x[i].cancel(home,a);
00901   }
00902 
00903   template<class View>
00904   forceinline bool
00905   __before(const View& x, const View& y) {
00906     return before(x,y);
00907   }
00908 
00909   template<class View> template<class X>
00910   forceinline bool
00911   ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
00912     return __before(a,b);
00913   }
00914 
00915   template<class View>
00916   void
00917   ViewArray<View>::sort(View* y, int m) {
00918     ViewLess<View> vl;
00919     Support::quicksort<View,ViewLess<View> >(y,m,vl);
00920   }
00921 
00922   template<class X, class Y>
00923   forceinline bool
00924   __same(const X& x, const Y& y) {
00925     return same(x,y);
00926   }
00927   template<class X, class Y>
00928   forceinline bool
00929   __shared(const X& x, const Y& y) {
00930     return shared(x,y);
00931   }
00932 
00933   template<class View>
00934   bool
00935   ViewArray<View>::same(const Space& home) const {
00936     if (n < 2)
00937       return false;
00938     Region r(home);
00939     View* y = r.alloc<View>(n);
00940     for (int i = n; i--; )
00941       y[i] = x[i];
00942     sort(y,n);
00943     for (int i = n-1; i--; )
00944       if (!y[i].assigned() && __same(y[i+1],y[i])) {
00945         r.free<View>(y,n);
00946         return true;
00947       }
00948     r.free<View>(y,n);
00949     return false;
00950   }
00951 
00952   template<class View>
00953   bool
00954   ViewArray<View>::same(const Space&, const View& y) const {
00955     if (y.assigned())
00956       return false;
00957     for (int i = n; i--; )
00958       if (__same(x[i],y))
00959         return true;
00960     return false;
00961   }
00962 
00963   template<class View>
00964   void
00965   ViewArray<View>::unique(const Space&) {
00966     if (n < 2)
00967       return;
00968     sort(x,n);
00969     int j = 0;
00970     for (int i = 1; i<n; i++)
00971       if (!__same(x[j],x[i]))
00972         x[++j] = x[i];
00973     n = j+1;
00974   }
00975 
00976   template<class View>
00977   bool
00978   ViewArray<View>::shared(const Space& home) const {
00979     if (n < 2)
00980       return false;
00981     Region r(home);
00982     View* y = r.alloc<View>(n);
00983     for (int i = n; i--; )
00984       y[i] = x[i];
00985     sort(y,n);
00986     for (int i = n-1; i--; )
00987       if (!y[i].assigned() && __shared(y[i+1],y[i])) {
00988         r.free<View>(y,n);
00989         return true;
00990       }
00991     r.free<View>(y,n);
00992     return false;
00993   }
00994 
00995   template<class View> template<class ViewY>
00996   bool
00997   ViewArray<View>::shared(const Space&, const ViewY& y) const {
00998     if (y.assigned())
00999       return false;
01000     for (int i = n; i--; )
01001       if (!x[i].assigned() && __shared(x[i],y))
01002         return true;
01003     return false;
01004   }
01005 
01006   template<class View> template<class ViewY>
01007   bool
01008   ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
01009     if ((size() < 1) || (y.size() < 1))
01010       return false;
01011     Region r(home);
01012     View* xs = r.alloc<View>(size());
01013     for (int i=size(); i--; )
01014       xs[i] = x[i];
01015     ViewLess<View> xvl;
01016     Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
01017     ViewY* ys = r.alloc<ViewY>(y.size());
01018     for (int j=y.size(); j--; )
01019       ys[j] = y[j];
01020     ViewLess<ViewY> yvl;
01021     Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
01022     {
01023       int i=0, j=0;
01024       while ((i < size()) && (j < y.size()))
01025         if (!x[i].assigned() && __shared(x[i],y[j])) {
01026           r.free<View>(xs,size());
01027           r.free<ViewY>(ys,y.size());
01028           return true;
01029         } else if (before(x[i],y[j])) {
01030           i++;
01031         } else {
01032           j++;
01033         }
01034     }
01035     r.free<View>(xs,size());
01036     r.free<ViewY>(ys,y.size());
01037     return false;
01038   }
01039 
01040   template<class View>
01041   void*
01042   ViewArray<View>::operator new(size_t) {
01043     return NULL;
01044   }
01045 
01046   template<class View>
01047   void
01048   ViewArray<View>::operator delete(void*,size_t) {
01049   }
01050 
01051 
01052   /*
01053    * Argument arrays: base class
01054    *
01055    */
01056 
01057   template<class T>
01058   forceinline T*
01059   ArgArrayBase<T>::allocate(int n) {
01060     return (n > onstack_size) ?
01061       heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01062   }
01063 
01064   template<class T>
01065   forceinline
01066   ArgArrayBase<T>::ArgArrayBase(int n0)
01067     : n(n0), a(allocate(n)) {}
01068 
01069   template<class T>
01070   inline
01071   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01072     : n(aa.n), a(allocate(n)) {
01073     heap.copy<T>(a,aa.a,n);
01074   }
01075 
01076   template<class T>
01077   forceinline
01078   ArgArrayBase<T>::~ArgArrayBase(void) {
01079     if (n > onstack_size)
01080       heap.free(a,n);
01081   }
01082 
01083   template<class T>
01084   forceinline const ArgArrayBase<T>&
01085   ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01086     if (&aa != this) {
01087       if (n > onstack_size)
01088         heap.free(a,n);
01089       n = aa.n;
01090       a = allocate(aa.n);
01091       heap.copy<T>(a,aa.a,n);
01092     }
01093     return *this;
01094   }
01095 
01096   template<class T>
01097   forceinline int
01098   ArgArrayBase<T>::size(void) const {
01099     return n;
01100   }
01101 
01102   template<class T>
01103   forceinline T&
01104   ArgArrayBase<T>::operator [](int i) {
01105     assert((i>=0) && (i < n));
01106     return a[i];
01107   }
01108 
01109   template<class T>
01110   forceinline const T&
01111   ArgArrayBase<T>::operator [](int i) const {
01112     assert((i>=0) && (i < n));
01113     return a[i];
01114   }
01115 
01116 
01117   /*
01118    * Argument arrays for primitive types
01119    *
01120    */
01121 
01122   template<class T>
01123   forceinline
01124   PrimArgArray<T>::PrimArgArray(int n)
01125     : ArgArrayBase<T>(n) {}
01126 
01127   template<class T>
01128   PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
01129     : ArgArrayBase<T>(n) {
01130     va_list args;
01131     va_start(args, a0);
01132     a[0] = a0;
01133     for (int i = 1; i < n; i++)
01134       a[i] = va_arg(args,T);
01135     va_end(args);
01136   }
01137 
01138   template<class T>
01139   PrimArgArray<T>::PrimArgArray(int n, const T* a0)
01140     : ArgArrayBase<T>(n) {
01141     for (int i=n; i--; )
01142       a[i] = a0[i];
01143   }
01144 
01145   template<class T>
01146   forceinline
01147   PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
01148     : ArgArrayBase<T>(aa) {}
01149 
01150 
01151   /*
01152    * Argument arrays for non-primitive types
01153    *
01154    */
01155 
01156   template<class T>
01157   forceinline
01158   ArgArray<T>::ArgArray(int n)
01159     : ArgArrayBase<T>(n) {}
01160 
01161   template<class T>
01162   ArgArray<T>::ArgArray(int n, const T* a0)
01163     : ArgArrayBase<T>(n) {
01164     for (int i=n; i--; )
01165       a[i] = a0[i];
01166   }
01167 
01168   template<class T>
01169   forceinline
01170   ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01171     : ArgArrayBase<T>(aa) {}
01172 
01173 
01174 
01175   /*
01176    * Argument arrays for variables
01177    *
01178    */
01179 
01180   template<class Var>
01181   forceinline
01182   VarArgArray<Var>::VarArgArray(int n)
01183     : ArgArrayBase<Var>(n) {}
01184 
01185   template<class Var>
01186   forceinline
01187   VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01188     : ArgArrayBase<Var>(aa) {}
01189 
01190   template<class Var>
01191   inline
01192   VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01193     : ArgArrayBase<Var>(x.size()) {
01194     for (int i=x.size(); i--; )
01195       a[i]=x[i];
01196   }
01197 
01198   template<class Var>
01199   forceinline bool
01200   VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) {
01201     return a.var() < b.var();
01202   }
01203 
01204   template<class Var>
01205   bool
01206   VarArgArray<Var>::same(const Space& home) const {
01207     if (n < 2)
01208       return false;
01209     Region r(home);
01210     Var* y = r.alloc<Var>(n);
01211     for (int i = n; i--; )
01212       y[i] = a[i];
01213     VarLess vl;
01214     Support::quicksort<Var,VarLess>(y,n,vl);
01215     for (int i = n-1; i--; )
01216       if (!y[i].assigned() && (y[i+1].var() == y[i].var())) {
01217         r.free<Var>(y,n);
01218         return true;
01219       }
01220     r.free<Var>(y,n);
01221     return false;
01222   }
01223 
01224   template<class Var>
01225   bool
01226   VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
01227     int m = n + y.n;
01228     if (m < 2)
01229       return false;
01230     Region r(home);
01231     Var* z = r.alloc<Var>(m);
01232     for (int i = n; i--; )
01233       z[i] = a[i];
01234     for (int i = y.n; i--; )
01235       z[i+n] = y.a[i];
01236     VarLess vl;
01237     Support::quicksort<Var,VarLess>(z,m,vl);
01238     for (int i = m-1; i--; )
01239       if (!z[i].assigned() && (z[i+1].var() == z[i].var())) {
01240         r.free<Var>(z,m);
01241         return true;
01242       }
01243     r.free<Var>(z,m);
01244     return false;
01245   }
01246 
01247   template<class Var>
01248   bool
01249   VarArgArray<Var>::same(const Space&, const Var& y) const {
01250     if (y.assigned())
01251       return false;
01252     for (int i = n; i--; )
01253       if (a[i].var() == y.var())
01254         return true;
01255     return false;
01256   }
01257 
01258 
01259 
01260 
01261 
01262 
01263   /*
01264    * Interdependent code
01265    *
01266    */
01267 
01268   template<class Var>
01269   inline
01270   VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
01271     : n(a.size()), capacity(a.size()) {
01272     if (capacity>0) {
01273       x = home.alloc<Var>(capacity);
01274       for (int i = capacity; i--; )
01275         x[i] = a[i];
01276     } else {
01277       x = NULL;
01278     }
01279   }
01280 
01281 
01282   /*
01283    * Printing of arrays
01284    *
01285    */
01286   template<class Char, class Traits, class Var>
01287   std::basic_ostream<Char,Traits>&
01288   operator <<(std::basic_ostream<Char,Traits>& os,
01289              const VarArray<Var>& x) {
01290     std::basic_ostringstream<Char,Traits> s;
01291     s.copyfmt(os); s.width(0);
01292     s << '{';
01293     if (x.size() > 0) {
01294       s << x[0];
01295       for (int i=1; i<x.size(); i++)
01296         s << ", " << x[i];
01297     }
01298     s << '}';
01299     return os << s.str();
01300   }
01301 
01302   template<class Char, class Traits, class View>
01303   std::basic_ostream<Char,Traits>&
01304   operator <<(std::basic_ostream<Char,Traits>& os,
01305              const ViewArray<View>& x) {
01306     std::basic_ostringstream<Char,Traits> s;
01307     s.copyfmt(os); s.width(0);
01308     s << '{';
01309     if (x.size() > 0) {
01310       s << x[0];
01311       for (int i=1; i<x.size(); i++)
01312         s << ", " << x[i];
01313     }
01314     s << '}';
01315     return os << s.str();
01316   }
01317 
01318   template<class Char, class Traits, class T>
01319   std::basic_ostream<Char,Traits>&
01320   operator <<(std::basic_ostream<Char,Traits>& os,
01321              const ArgArrayBase<T>& x) {
01322     std::basic_ostringstream<Char,Traits> s;
01323     s.copyfmt(os); s.width(0);
01324     s << '{';
01325     if (x.size() > 0) {
01326       s << x[0];
01327       for (int i=1; i<x.size(); i++)
01328         s << ", " << x[i];
01329     }
01330     s << '}';
01331     return os << s.str();
01332   }
01333 
01334 }
01335 
01336 // STATISTICS: kernel-other