Generated on Thu Jul 6 07:06:41 2006 for Gecode by doxygen 1.4.7

array.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2006-06-20 07:40:00 +0200 (Tue, 20 Jun 2006) $ by $Author: schulte $
00012  *     $Revision: 3309 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #include <cstdarg>
00025 #include "gecode/support/sort.hh"
00026 
00027 namespace Gecode {
00028 
00029   template <class Var> class VarArray;
00030   template <class Var> class VarArgArray;
00031 
00042   template <class Var>
00043   class VarArray {
00044   protected:
00046     int  n; 
00048     Var* x;
00049   public:
00051 
00052 
00053     VarArray(void);
00055     VarArray(Space*, int m);
00057     VarArray(Space*,const VarArgArray<Var>&);
00059     VarArray(const VarArray<Var>& a);
00061     const VarArray<Var>& operator=(const VarArray<Var>& a);
00063 
00065 
00066 
00067     int size(void) const;
00069 
00071 
00072 
00073     Var& operator[](int i);
00075     const Var& operator[](int i) const;
00077 
00079 
00080 
00087     void update(Space*, bool share, VarArray<Var>& a);
00089   private:
00090     static void* operator new(size_t);
00091     static void  operator delete(void*,size_t);
00092   };
00093 
00094 
00102   template <class View>
00103   class ViewArray {
00104   private:
00106     int  n; 
00108     View* x;
00110     class ViewLess {
00111     public:
00112       bool operator()(const View&, const View&);
00113     };
00115     static void sort(View* x, int n);
00116   public:
00118 
00119 
00120     ViewArray(void);
00122     ViewArray(Space*, int m);
00124     ViewArray(const ViewArray<View>& a);
00126     ViewArray(Space*,const ViewArray<View>& a);
00128     const ViewArray<View>& operator=(const ViewArray<View>& a);
00135     template <class Var>
00136     ViewArray(Space* home, const VarArgArray<Var>& a)
00137       : n(a.size()) {
00138       // This may not be in the icc file (to satisfy the MS compiler)
00139       if (n>0) {
00140         x = static_cast<View*>(home->alloc(sizeof(View)*n));
00141         for (int i = n; i--; )
00142           x[i] = a[i];
00143       } else {
00144         x = NULL;
00145       }
00146     }
00148 
00150 
00151 
00152     int size(void) const;
00154     void size(int n);
00156 
00158 
00159 
00160     View& operator[](int i);
00162     const View& operator[](int i) const;
00164 
00166 
00167 
00168     void subscribe(Space*, Propagator* p, PropCond pc);
00170     void cancel(Space* home, Propagator* p, PropCond pc);
00172 
00174 
00175 
00182     void update(Space*, bool share, ViewArray<View>& a);
00184 
00185 
00187 
00188 
00189     void move_fst(int i);
00191     void move_lst(int i);
00197     void move_fst(int i, Space* home, Propagator* p, PropCond pc);
00203     void move_lst(int i, Space* home, Propagator* p, PropCond pc);
00205 
00207 
00208 
00209     void drop_fst(int i);
00211     void drop_lst(int i);
00217     void drop_fst(int i, Space* home, Propagator* p, PropCond pc);
00224     void drop_lst(int i, Space* home, Propagator* p, PropCond pc);
00226 
00228 
00229 
00230     bool same(void) const;
00232     bool same(const View& y) const;
00234     void unique(void);
00236 
00238 
00239 
00240     bool shared(void) const;
00242     bool shared(const View& y) const;
00244 
00245   private:
00246     static void* operator new(size_t);
00247     static void  operator delete(void*,size_t);
00248   };
00249 
00263   template <class T>
00264   class ArgArrayBase {
00265   protected:
00267     int n; 
00269     T*  a;
00271     static const int onstack_size = 16;
00273     T onstack[onstack_size];
00275     T* allocate(int n);
00276   public:
00278 
00279 
00280     ArgArrayBase(int n);
00282     ArgArrayBase(const ArgArrayBase<T>& a);
00284     const ArgArrayBase<T>& operator=(const ArgArrayBase<T>& a);
00286 
00288 
00289 
00290     int size(void) const;
00292     
00294 
00295 
00296     T& operator[](int i);
00298     const T& operator[](int i) const;
00300 
00302 
00303 
00304     ~ArgArrayBase(void);
00306   private:
00307     static void* operator new(size_t);
00308     static void  operator delete(void*,size_t);
00309   };
00310 
00311 
00323   template <class T>
00324   class PrimArgArray : public ArgArrayBase<T> {
00325   protected:
00326     using ArgArrayBase<T>::a;
00327   public:
00328     using ArgArrayBase<T>::size;
00330 
00331 
00332     PrimArgArray(int n);
00334     PrimArgArray(int n, T e0, ...);
00336     PrimArgArray(int n, const T* e);
00338     PrimArgArray(const PrimArgArray<T>& a);
00340   };
00341 
00353   template <class Var>
00354   class VarArgArray : public ArgArrayBase<Var> {
00355   protected:
00356     using ArgArrayBase<Var>::a;
00357     using ArgArrayBase<Var>::n;
00359     class VarLess {
00360     public:
00361       bool operator()(const Var&, const Var&);
00362     };
00363   public:
00364     using ArgArrayBase<Var>::size;
00366 
00367 
00368     VarArgArray(int n);
00370     VarArgArray(const VarArgArray<Var>& a);
00372     VarArgArray(const VarArray<Var>& a);
00374 
00375 
00376 
00377     bool same(void) const;
00379     bool same(const Var& y) const;
00381     bool same(const VarArgArray<Var>& y) const;
00383   };
00384 
00397   template <class A>
00398   class ArrayTraits {};
00399 
00400   /*
00401    * Implementation
00402    *
00403    */
00404 
00405   /*
00406    * Variable arrays
00407    *
00408    */
00409 
00410   template <class Var>
00411   forceinline
00412   VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
00413 
00414   template <class Var>
00415   forceinline
00416   VarArray<Var>::VarArray(Space* home, int n0)
00417     : n(n0) {
00418     x = (n>0) ? static_cast<Var*>(home->alloc(sizeof(Var)*n)) : NULL;
00419   }
00420 
00421   template <class Var>
00422   forceinline
00423   VarArray<Var>::VarArray(const VarArray<Var>& a) {
00424     n = a.n; x = a.x;
00425   }
00426 
00427   template <class Var>
00428   forceinline const VarArray<Var>&
00429   VarArray<Var>::operator=(const VarArray<Var>& a) {
00430     n = a.n; x = a.x;
00431     return *this;
00432   }
00433 
00434   template <class Var>
00435   forceinline int
00436   VarArray<Var>::size(void) const {
00437     return n;
00438   }
00439 
00440   template <class Var>
00441   forceinline Var&
00442   VarArray<Var>::operator[](int i) {
00443     assert((i >= 0) && (i < size()));
00444     return x[i];
00445   }
00446 
00447   template <class Var>
00448   forceinline const Var&
00449   VarArray<Var>::operator[](int i) const {
00450     assert((i >= 0) && (i < size()));
00451     return x[i];
00452   }
00453 
00454   template <class Var>
00455   forceinline void
00456   VarArray<Var>::update(Space* home, bool share, VarArray<Var>& a) {
00457     n = a.n;
00458     if (n > 0) {
00459       x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00460       for (int i = n; i--; )
00461         x[i].update(home, share, a.x[i]);
00462     } else {
00463       x = NULL;
00464     }
00465   }
00466 
00467   template <class Var>
00468   void*
00469   VarArray<Var>::operator new(size_t) {
00470     return NULL;
00471   }
00472 
00473   template <class Var>
00474   void
00475   VarArray<Var>::operator delete(void*,size_t) {
00476   }
00477 
00478   /*
00479    * View arrays
00480    *
00481    */
00482 
00483   template <class View>
00484   forceinline
00485   ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00486 
00487   template <class View>
00488   forceinline
00489   ViewArray<View>::ViewArray(Space* home, int n0)
00490     : n(n0) {
00491     x = (n>0) ? static_cast<View*>(home->alloc(sizeof(View)*n)) : NULL;
00492   }
00493 
00494   template <class View>
00495   ViewArray<View>::ViewArray(Space* home, const ViewArray<View>& a)
00496     : n(a.size()) {
00497     if (n>0) {
00498       x = static_cast<View*>(home->alloc(sizeof(View)*n));
00499       for (int i = n; i--; )
00500         x[i] = a[i];
00501     } else {
00502       x = NULL;
00503     }
00504   }
00505 
00506   template <class View>
00507   forceinline
00508   ViewArray<View>::ViewArray(const ViewArray<View>& a)
00509     : n(a.n), x(a.x) {}
00510 
00511   template <class View>
00512   forceinline const ViewArray<View>&
00513   ViewArray<View>::operator=(const ViewArray<View>& a) {
00514     n = a.n; x = a.x;
00515     return *this;
00516   }
00517 
00518   template <class View>
00519   forceinline int
00520   ViewArray<View>::size(void) const {
00521     return n;
00522   }
00523 
00524   template <class View>
00525   forceinline void
00526   ViewArray<View>::size(int n0) {
00527     n = n0;
00528   }
00529 
00530   template <class View>
00531   forceinline View&
00532   ViewArray<View>::operator[](int i) {
00533     assert((i >= 0) && (i < size()));
00534     return x[i];
00535   }
00536 
00537   template <class View>
00538   forceinline const View&
00539   ViewArray<View>::operator[](int i) const {
00540     assert((i >= 0) && (i < size()));
00541     return x[i];
00542   }
00543 
00544   template <class View>
00545   forceinline void
00546   ViewArray<View>::move_fst(int i) {
00547     // move x[0] to x[i]
00548     assert(x[i].assigned());
00549     x[i]=x[0]; x++; n--;
00550   }
00551 
00552   template <class View>
00553   forceinline void
00554   ViewArray<View>::move_lst(int i) {
00555     // move x[n-1] to x[i]
00556     assert(x[i].assigned());
00557     n--; x[i]=x[n];
00558   }
00559 
00560   template <class View>
00561   forceinline void
00562   ViewArray<View>::drop_fst(int i) {
00563     // Drop elements from 0..i-1
00564     assert(i>=0);
00565     x += i; n -= i;
00566   }
00567 
00568   template <class View>
00569   forceinline void
00570   ViewArray<View>::drop_lst(int i) {
00571     // Drop elements from i+1..n-1
00572     assert(i<n);
00573     n = i+i;
00574   }
00575 
00576   template <class View>
00577   forceinline void
00578   ViewArray<View>::move_fst(int i, Space* home, Propagator* p, PropCond pc) {
00579     // Move x[0] to x[i]
00580     x[i].cancel(home,p,pc);
00581     x[i]=x[0]; x++; n--;
00582   }
00583 
00584   template <class View>
00585   forceinline void
00586   ViewArray<View>::move_lst(int i, Space* home, Propagator* p, PropCond pc) {
00587     // Move x[n-1] to x[i]
00588     x[i].cancel(home,p,pc);
00589     n--; x[i]=x[n];
00590   }
00591 
00592   template <class View>
00593   void
00594   ViewArray<View>::drop_fst(int i, Space* home, Propagator* p, PropCond pc) {
00595     // Drop elements from 0..i-1
00596     assert(i>=0);
00597     for (int j=i; j--; )
00598       x[j].cancel(home,p,pc);
00599     x += i; n -= i;
00600   }
00601 
00602   template <class View>
00603   void
00604   ViewArray<View>::drop_lst(int i, Space* home, Propagator* p, PropCond pc) {
00605     // Drop elements from i+1..n-1
00606     assert(i<n);
00607     for (int j=i+1; j<n; j++)
00608       x[j].cancel(home,p,pc);
00609     n = i+1;
00610   }
00611 
00612   template <class View>
00613   void
00614   ViewArray<View>::update(Space* home, bool share, ViewArray<View>& y) {
00615     n = y.n;
00616     if (n > 0) {
00617       x = static_cast<View*>(home->alloc(sizeof(View)*n));
00618       for (int i = n; i--; )
00619         x[i].update(home, share, y.x[i]);
00620     } else {
00621       x = NULL;
00622     }
00623   }
00624 
00625   template <class View>
00626   void
00627   ViewArray<View>::subscribe(Space* home, Propagator* p, PropCond pc) {
00628     for (int i = n; i--; )
00629       x[i].subscribe(home,p,pc);
00630   }
00631 
00632   template <class View>
00633   void
00634   ViewArray<View>::cancel(Space* home, Propagator* p, PropCond pc) {
00635     for (int i = n; i--; )
00636       x[i].cancel(home,p,pc);
00637   }
00638 
00639   template <class View>
00640   forceinline bool
00641   __before(const View& x, const View& y) { 
00642     return before(x,y); 
00643   }
00644 
00645   template <class View>
00646   forceinline bool
00647   ViewArray<View>::ViewLess::operator()(const View& a, const View& b) {
00648     return __before(a,b);
00649   }
00650 
00651   template <class View>
00652   void
00653   ViewArray<View>::sort(View* y, int m) {
00654     ViewLess vl;
00655     Support::quicksort<View,ViewLess>(y,m,vl);
00656   }
00657 
00658   template <class View>
00659   forceinline bool
00660   __same(const View& x, const View& y) { 
00661     return same(x,y); 
00662   }
00663   template <class View>
00664   forceinline bool
00665   __shared(const View& x, const View& y) { 
00666     return shared(x,y); 
00667   }
00668 
00669   template <class View>
00670   bool
00671   ViewArray<View>::same(void) const {
00672     if (n < 2)
00673       return false;
00674     GECODE_AUTOARRAY(View,y,n);
00675     for (int i = n; i--; )
00676       y[i] = x[i];
00677     sort(y,n);
00678     for (int i = n-1; i--; )
00679       if (__same(y[i+1],y[i]))
00680         return true;
00681     return false;
00682   }
00683 
00684   template <class View>
00685   bool
00686   ViewArray<View>::same(const View& y) const {
00687     for (int i = n; i--; )
00688       if (__same(x[i],y))
00689         return true;
00690     return false;
00691   }
00692 
00693   template <class View>
00694   void
00695   ViewArray<View>::unique(void) {
00696     if (n < 2)
00697       return;
00698     sort(x,n);
00699     int j = 0;
00700     for (int i = 1; i<n; i++)
00701       if (!__same(x[j],x[i]))
00702         x[++j] = x[i];
00703     n = j+1;
00704   }
00705 
00706   template <class View>
00707   bool
00708   ViewArray<View>::shared(void) const {
00709     if (n < 2)
00710       return false;
00711     GECODE_AUTOARRAY(View,y,n);
00712     for (int i = n; i--; )
00713       y[i] = x[i];
00714     sort(y,n);
00715     for (int i = n-1; i--; )
00716       if (__shared(y[i+1],y[i]))
00717         return true;
00718     return false;
00719   }
00720 
00721   template <class View>
00722   bool
00723   ViewArray<View>::shared(const View& y) const {
00724     for (int i = n; i--; )
00725       if (__shared(x[i],y))
00726         return true;
00727     return false;
00728   }
00729 
00730   template <class View>
00731   void*
00732   ViewArray<View>::operator new(size_t) {
00733     return NULL;
00734   }
00735 
00736   template <class View>
00737   void
00738   ViewArray<View>::operator delete(void*,size_t) {
00739   }
00740 
00741 
00742   /*
00743    * Argument arrays: base class
00744    *
00745    */
00746 
00747   template <class T>
00748   forceinline T*
00749   ArgArrayBase<T>::allocate(int n) {
00750     return (n > onstack_size) ?
00751       Memory::bmalloc<T>(n) : &onstack[0];
00752   }
00753   
00754   template <class T>
00755   forceinline
00756   ArgArrayBase<T>::ArgArrayBase(int n0)
00757     : n(n0), a(allocate(n0)) {}
00758   
00759   template <class T>
00760   inline
00761   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
00762     : n(aa.n), a(allocate(aa.n)) {
00763     for (int i = n; i--; )
00764       a[i] = aa.a[i];
00765   }
00766   
00767   template <class T>
00768   forceinline
00769   ArgArrayBase<T>::~ArgArrayBase(void) {
00770     if (n > onstack_size)
00771       Memory::free(a);
00772   }
00773   
00774   template <class T>
00775   forceinline const ArgArrayBase<T>&
00776   ArgArrayBase<T>::operator=(const ArgArrayBase<T>& aa) {
00777     if (&aa != this) {
00778       if (n > onstack_size)
00779         Memory::free(a);
00780       n = aa.n;
00781       a = allocate(aa.n);
00782       for (int i = n; i--; )
00783         a[i] = aa.a[i];
00784     }
00785     return *this;
00786   }
00787   
00788   template <class T>
00789   forceinline int
00790   ArgArrayBase<T>::size(void) const {
00791     return n;
00792   }
00793   
00794   template <class T>
00795   forceinline T&
00796   ArgArrayBase<T>::operator[](int i) {
00797     assert((i>=0) && (i < n));
00798     return a[i];
00799   }
00800   
00801   template <class T>
00802   forceinline const T&
00803   ArgArrayBase<T>::operator[](int i) const {
00804     assert((i>=0) && (i < n));
00805     return a[i];
00806   }
00807 
00808 
00809   /*
00810    * Argument arrays for primitive types
00811    *
00812    */
00813 
00814   template <class T>
00815   forceinline
00816   PrimArgArray<T>::PrimArgArray(int n)
00817     : ArgArrayBase<T>(n) {}
00818 
00819   template <class T>
00820   PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
00821     : ArgArrayBase<T>(n) {
00822     va_list args;
00823     va_start(args, a0);
00824     a[0] = a0;
00825     for (int i = 1; i < n; i++)
00826       a[i] = va_arg(args,T);
00827     va_end(args);
00828   }
00829 
00830   template <class T>
00831   PrimArgArray<T>::PrimArgArray(int n, const T* a0)
00832     : ArgArrayBase<T>(n) {
00833     for (int i=n; i--; )
00834       a[i] = a0[i];
00835   }
00836 
00837   template <class T>
00838   PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
00839     : ArgArrayBase<T>(aa.size()) {
00840     for (int i = size(); i--; )
00841       a[i] = aa.a[i];
00842   }
00843 
00844 
00845 
00846   /*
00847    * Argument arrays for variables
00848    *
00849    */
00850 
00851   template <class T>
00852   forceinline
00853   VarArgArray<T>::VarArgArray(int n)
00854     : ArgArrayBase<T>(n) {}
00855 
00856   template <class T>
00857   inline
00858   VarArgArray<T>::VarArgArray(const VarArgArray<T>& aa)
00859     : ArgArrayBase<T>(aa.size()) {
00860     for (int i = size(); i--; )
00861       a[i] = aa.a[i];
00862   }
00863 
00864   template <class T>
00865   inline
00866   VarArgArray<T>::VarArgArray(const VarArray<T>& x)
00867     : ArgArrayBase<T>(x.size()) {
00868     for (int i = x.size(); i--; )
00869       a[i] = x[i];
00870   }
00871 
00872   template <class Var>
00873   forceinline bool
00874   VarArgArray<Var>::VarLess::operator()(const Var& a, const Var& b) {
00875     return a.variable() < b.variable();
00876   }
00877 
00878   template <class Var>
00879   bool
00880   VarArgArray<Var>::same(void) const {
00881     if (n < 2)
00882       return false;
00883     GECODE_AUTOARRAY(Var,y,n);
00884     for (int i = n; i--; )
00885       y[i] = a[i];
00886     VarLess vl;
00887     Support::quicksort<Var,VarLess>(y,n,vl);
00888     for (int i = n-1; i--; )
00889       if (y[i+1].variable() == y[i].variable())
00890         return true;
00891     return false;
00892   }
00893 
00894   template <class Var>
00895   bool
00896   VarArgArray<Var>::same(const VarArgArray<Var>& y) const {
00897     int m = n + y.n;
00898     if (m < 2)
00899       return false;
00900     GECODE_AUTOARRAY(Var,z,m);
00901     for (int i = n; i--; )
00902       z[i] = a[i];
00903     for (int i = y.n; i--; )
00904       z[i+n] = y.a[i];
00905     VarLess vl;
00906     Support::quicksort<Var,VarLess>(z,m,vl);
00907     for (int i = m-1; i--; )
00908       if (z[i+1].variable() == z[i].variable())
00909         return true;
00910     return false;
00911   }
00912 
00913   template <class Var>
00914   bool
00915   VarArgArray<Var>::same(const Var& y) const {
00916     for (int i = n; i--; )
00917       if (a[i].variable() == y.variable())
00918         return true;
00919     return false;
00920   }
00921 
00922 
00923 
00924 
00925 
00926 
00927   /*
00928    * Interdependent code
00929    *
00930    */
00931 
00932   template <class Var>
00933   inline
00934   VarArray<Var>::VarArray(Space* home, const VarArgArray<Var>& a)
00935     : n(a.size()) {
00936     if (n>0) {
00937       x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00938       for (int i = n; i--; )
00939         x[i] = a[i];
00940     } else {
00941       x = NULL;
00942     }
00943   }
00944 
00945 }
00946 
00947 // STATISTICS: kernel-other