00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
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
00402
00403
00404
00405
00406
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
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
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
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
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
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
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
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
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
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
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
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
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
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