Generated on Wed Jan 4 17:49:08 2006 for Gecode by doxygen 1.4.6

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: 2005-12-05 13:45:47 +0100 (Mon, 05 Dec 2005) $ by $Author: schulte $
00012  *     $Revision: 2693 $
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 "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(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, Propagator* p, PropCond pc);
00203     void move_lst(int i, 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, Propagator* p, PropCond pc);
00224     void drop_lst(int i, 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   public:
00358     using ArgArrayBase<Var>::size;
00360 
00361 
00362     VarArgArray(int n);
00364     VarArgArray(const VarArgArray<Var>& a);
00366     VarArgArray(const VarArray<Var>& a);
00368   };
00369 
00382   template <class A>
00383   class ArrayTraits {};
00384 
00385   /*
00386    * Implementation
00387    *
00388    */
00389 
00390   /*
00391    * Variable arrays
00392    *
00393    */
00394 
00395   template <class Var>
00396   forceinline
00397   VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
00398 
00399   template <class Var>
00400   forceinline
00401   VarArray<Var>::VarArray(Space* home, int n0)
00402     : n(n0) {
00403     x = (n>0) ? static_cast<Var*>(home->alloc(sizeof(Var)*n)) : NULL;
00404   }
00405 
00406   template <class Var>
00407   forceinline
00408   VarArray<Var>::VarArray(const VarArray<Var>& a) {
00409     n = a.n; x = a.x;
00410   }
00411 
00412   template <class Var>
00413   forceinline const VarArray<Var>&
00414   VarArray<Var>::operator=(const VarArray<Var>& a) {
00415     n = a.n; x = a.x;
00416     return *this;
00417   }
00418 
00419   template <class Var>
00420   forceinline int
00421   VarArray<Var>::size(void) const {
00422     return n;
00423   }
00424 
00425   template <class Var>
00426   forceinline Var&
00427   VarArray<Var>::operator[](int i) {
00428     assert((i >= 0) && (i < size()));
00429     return x[i];
00430   }
00431 
00432   template <class Var>
00433   forceinline const Var&
00434   VarArray<Var>::operator[](int i) const {
00435     assert((i >= 0) && (i < size()));
00436     return x[i];
00437   }
00438 
00439   template <class Var>
00440   forceinline void
00441   VarArray<Var>::update(Space* home, bool share, VarArray<Var>& a) {
00442     n = a.n;
00443     if (n > 0) {
00444       x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00445       for (int i = n; i--; )
00446         x[i].update(home, share, a.x[i]);
00447     } else {
00448       x = NULL;
00449     }
00450   }
00451 
00452   template <class Var>
00453   void*
00454   VarArray<Var>::operator new(size_t) {
00455     return NULL;
00456   }
00457 
00458   template <class Var>
00459   void
00460   VarArray<Var>::operator delete(void*,size_t) {
00461   }
00462 
00463   /*
00464    * View arrays
00465    *
00466    */
00467 
00468   template <class View>
00469   forceinline
00470   ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00471 
00472   template <class View>
00473   forceinline
00474   ViewArray<View>::ViewArray(Space* home, int n0)
00475     : n(n0) {
00476     x = (n>0) ? static_cast<View*>(home->alloc(sizeof(View)*n)) : NULL;
00477   }
00478 
00479   template <class View>
00480   ViewArray<View>::ViewArray(Space* home, const ViewArray<View>& a)
00481     : n(a.size()) {
00482     if (n>0) {
00483       x = static_cast<View*>(home->alloc(sizeof(View)*n));
00484       for (int i = n; i--; )
00485         x[i] = a[i];
00486     } else {
00487       x = NULL;
00488     }
00489   }
00490 
00491   template <class View>
00492   forceinline
00493   ViewArray<View>::ViewArray(const ViewArray<View>& a)
00494     : n(a.n), x(a.x) {}
00495 
00496   template <class View>
00497   forceinline const ViewArray<View>&
00498   ViewArray<View>::operator=(const ViewArray<View>& a) {
00499     n = a.n; x = a.x;
00500     return *this;
00501   }
00502 
00503   template <class View>
00504   forceinline int
00505   ViewArray<View>::size(void) const {
00506     return n;
00507   }
00508 
00509   template <class View>
00510   forceinline void
00511   ViewArray<View>::size(int n0) {
00512     n = n0;
00513   }
00514 
00515   template <class View>
00516   forceinline View&
00517   ViewArray<View>::operator[](int i) {
00518     assert((i >= 0) && (i < size()));
00519     return x[i];
00520   }
00521 
00522   template <class View>
00523   forceinline const View&
00524   ViewArray<View>::operator[](int i) const {
00525     assert((i >= 0) && (i < size()));
00526     return x[i];
00527   }
00528 
00529   template <class View>
00530   forceinline void
00531   ViewArray<View>::move_fst(int i) {
00532     // move x[0] to x[i]
00533     assert(x[i].assigned());
00534     x[i]=x[0]; x++; n--;
00535   }
00536 
00537   template <class View>
00538   forceinline void
00539   ViewArray<View>::move_lst(int i) {
00540     // move x[n-1] to x[i]
00541     assert(x[i].assigned());
00542     n--; x[i]=x[n];
00543   }
00544 
00545   template <class View>
00546   forceinline void
00547   ViewArray<View>::drop_fst(int i) {
00548     // Drop elements from 0..i-1
00549     assert(i>=0);
00550     x += i; n -= i;
00551   }
00552 
00553   template <class View>
00554   forceinline void
00555   ViewArray<View>::drop_lst(int i) {
00556     // Drop elements from i+1..n-1
00557     assert(i<n);
00558     n = i+i;
00559   }
00560 
00561   template <class View>
00562   forceinline void
00563   ViewArray<View>::move_fst(int i, Propagator* p, PropCond pc) {
00564     // Move x[0] to x[i]
00565     x[i].cancel(p,pc);
00566     x[i]=x[0]; x++; n--;
00567   }
00568 
00569   template <class View>
00570   forceinline void
00571   ViewArray<View>::move_lst(int i, Propagator* p, PropCond pc) {
00572     // Move x[n-1] to x[i]
00573     x[i].cancel(p,pc);
00574     n--; x[i]=x[n];
00575   }
00576 
00577   template <class View>
00578   void
00579   ViewArray<View>::drop_fst(int i, Propagator* p, PropCond pc) {
00580     // Drop elements from 0..i-1
00581     assert(i>=0);
00582     for (int j=i; j--; )
00583       x[j].cancel(p,pc);
00584     x += i; n -= i;
00585   }
00586 
00587   template <class View>
00588   void
00589   ViewArray<View>::drop_lst(int i, Propagator* p, PropCond pc) {
00590     // Drop elements from i+1..n-1
00591     assert(i<n);
00592     for (int j=i+1; j<n; j++)
00593       x[j].cancel(p,pc);
00594     n = i+1;
00595   }
00596 
00597   template <class View>
00598   void
00599   ViewArray<View>::update(Space* home, bool share, ViewArray<View>& y) {
00600     n = y.n;
00601     if (n > 0) {
00602       x = static_cast<View*>(home->alloc(sizeof(View)*n));
00603       for (int i = n; i--; )
00604         x[i].update(home, share, y.x[i]);
00605     } else {
00606       x = NULL;
00607     }
00608   }
00609 
00610   template <class View>
00611   void
00612   ViewArray<View>::subscribe(Space* home, Propagator* p, PropCond pc) {
00613     for (int i = n; i--; )
00614       x[i].subscribe(home,p,pc);
00615   }
00616 
00617   template <class View>
00618   void
00619   ViewArray<View>::cancel(Propagator* p, PropCond pc) {
00620     for (int i = n; i--; )
00621       x[i].cancel(p,pc);
00622   }
00623 
00624   template <class View>
00625   forceinline bool
00626   __before(const View& x, const View& y) { 
00627     return before(x,y); 
00628   }
00629 
00630   template <class View>
00631   forceinline bool
00632   ViewArray<View>::ViewLess::operator()(const View& a, const View& b) {
00633     return __before(a,b);
00634   }
00635 
00636   template <class View>
00637   void
00638   ViewArray<View>::sort(View* y, int m) {
00639     ViewLess vl;
00640     Support::quicksort<View,ViewLess>(y,m,vl);
00641   }
00642 
00643   template <class View>
00644   forceinline bool
00645   __same(const View& x, const View& y) { 
00646     return same(x,y); 
00647   }
00648   template <class View>
00649   forceinline bool
00650   __shared(const View& x, const View& y) { 
00651     return shared(x,y); 
00652   }
00653 
00654   template <class View>
00655   bool
00656   ViewArray<View>::same(void) const {
00657     if (n < 2)
00658       return false;
00659     GECODE_AUTOARRAY(View,y,n);
00660     for (int i = n; i--; )
00661       y[i] = x[i];
00662     sort(y,n);
00663     for (int i = n-1; i--; )
00664       if (__same(y[i+1],y[i]))
00665         return true;
00666     return false;
00667   }
00668 
00669   template <class View>
00670   bool
00671   ViewArray<View>::same(const View& y) const {
00672     for (int i = n; i--; )
00673       if (__same(x[i],y))
00674         return true;
00675     return false;
00676   }
00677 
00678   template <class View>
00679   void
00680   ViewArray<View>::unique(void) {
00681     if (n < 2)
00682       return;
00683     sort(x,n);
00684     int j = 0;
00685     for (int i = 1; i<n; i++)
00686       if (!__same(x[j],x[i]))
00687         x[++j] = x[i];
00688     n = j+1;
00689   }
00690 
00691   template <class View>
00692   bool
00693   ViewArray<View>::shared(void) const {
00694     if (n < 2)
00695       return false;
00696     GECODE_AUTOARRAY(View,y,n);
00697     for (int i = n; i--; )
00698       y[i] = x[i];
00699     sort(y,n);
00700     for (int i = n-1; i--; )
00701       if (__shared(y[i+1],y[i]))
00702         return true;
00703     return false;
00704   }
00705 
00706   template <class View>
00707   bool
00708   ViewArray<View>::shared(const View& y) const {
00709     for (int i = n; i--; )
00710       if (__shared(x[i],y))
00711         return true;
00712     return false;
00713   }
00714 
00715   template <class View>
00716   void*
00717   ViewArray<View>::operator new(size_t) {
00718     return NULL;
00719   }
00720 
00721   template <class View>
00722   void
00723   ViewArray<View>::operator delete(void*,size_t) {
00724   }
00725 
00726 
00727   /*
00728    * Argument arrays: base class
00729    *
00730    */
00731 
00732   template <class T>
00733   forceinline T*
00734   ArgArrayBase<T>::allocate(int n) {
00735     return (n > onstack_size) ?
00736       Memory::bmalloc<T>(n) : &onstack[0];
00737   }
00738   
00739   template <class T>
00740   forceinline
00741   ArgArrayBase<T>::ArgArrayBase(int n0)
00742     : n(n0), a(allocate(n0)) {}
00743   
00744   template <class T>
00745   inline
00746   ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
00747     : n(aa.n), a(allocate(aa.n)) {
00748     for (int i = n; i--; )
00749       a[i] = aa.a[i];
00750   }
00751   
00752   template <class T>
00753   forceinline
00754   ArgArrayBase<T>::~ArgArrayBase(void) {
00755     if (n > onstack_size)
00756       Memory::free(a);
00757   }
00758   
00759   template <class T>
00760   forceinline const ArgArrayBase<T>&
00761   ArgArrayBase<T>::operator=(const ArgArrayBase<T>& aa) {
00762     if (&aa != this) {
00763       if (n > onstack_size)
00764         Memory::free(a);
00765       n = aa.n;
00766       a = allocate(aa.n);
00767       for (int i = n; i--; )
00768         a[i] = aa.a[i];
00769     }
00770     return *this;
00771   }
00772   
00773   template <class T>
00774   forceinline int
00775   ArgArrayBase<T>::size(void) const {
00776     return n;
00777   }
00778   
00779   template <class T>
00780   forceinline T&
00781   ArgArrayBase<T>::operator[](int i) {
00782     assert((i>=0) && (i < n));
00783     return a[i];
00784   }
00785   
00786   template <class T>
00787   forceinline const T&
00788   ArgArrayBase<T>::operator[](int i) const {
00789     assert((i>=0) && (i < n));
00790     return a[i];
00791   }
00792 
00793 
00794   /*
00795    * Argument arrays for primitive types
00796    *
00797    */
00798 
00799   template <class T>
00800   forceinline
00801   PrimArgArray<T>::PrimArgArray(int n)
00802     : ArgArrayBase<T>(n) {}
00803 
00804   template <class T>
00805   PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
00806     : ArgArrayBase<T>(n) {
00807     va_list args;
00808     va_start(args, a0);
00809     a[0] = a0;
00810     for (int i = 1; i < n; i++)
00811       a[i] = va_arg(args,T);
00812     va_end(args);
00813   }
00814 
00815   template <class T>
00816   PrimArgArray<T>::PrimArgArray(int n, const T* a0)
00817     : ArgArrayBase<T>(n) {
00818     for (int i=n; i--; )
00819       a[i] = a0[i];
00820   }
00821 
00822   template <class T>
00823   PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
00824     : ArgArrayBase<T>(aa.size()) {
00825     for (int i = size(); i--; )
00826       a[i] = aa.a[i];
00827   }
00828 
00829 
00830 
00831   /*
00832    * Argument arrays for variables
00833    *
00834    */
00835 
00836   template <class T>
00837   forceinline
00838   VarArgArray<T>::VarArgArray(int n)
00839     : ArgArrayBase<T>(n) {}
00840 
00841   template <class T>
00842   inline
00843   VarArgArray<T>::VarArgArray(const VarArgArray<T>& aa)
00844     : ArgArrayBase<T>(aa.size()) {
00845     for (int i = size(); i--; )
00846       a[i] = aa.a[i];
00847   }
00848 
00849   template <class T>
00850   inline
00851   VarArgArray<T>::VarArgArray(const VarArray<T>& x)
00852     : ArgArrayBase<T>(x.size()) {
00853     for (int i = x.size(); i--; )
00854       a[i] = x[i];
00855   }
00856 
00857 
00858 
00859 
00860 
00861   /*
00862    * Interdependent code
00863    *
00864    */
00865 
00866   template <class Var>
00867   inline
00868   VarArray<Var>::VarArray(Space* home, const VarArgArray<Var>& a)
00869     : n(a.size()) {
00870     if (n>0) {
00871       x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00872       for (int i = n; i--; )
00873         x[i] = a[i];
00874     } else {
00875       x = NULL;
00876     }
00877   }
00878 
00879 }
00880 
00881 // STATISTICS: kernel-other