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
00174 void subscribe(Space* home, Propagator* p, PropCond pc, bool process=true);
00176 void cancel(Space* home, Propagator* p, PropCond pc);
00178
00180
00181
00188 void update(Space*, bool share, ViewArray<View>& a);
00190
00191
00193
00194
00195 void move_fst(int i);
00197 void move_lst(int i);
00203 void move_fst(int i, Space* home, Propagator* p, PropCond pc);
00209 void move_lst(int i, Space* home, Propagator* p, PropCond pc);
00211
00213
00214
00215 void drop_fst(int i);
00217 void drop_lst(int i);
00223 void drop_fst(int i, Space* home, Propagator* p, PropCond pc);
00230 void drop_lst(int i, Space* home, Propagator* p, PropCond pc);
00232
00234
00235
00236 bool same(void) const;
00238 bool same(const View& y) const;
00240 void unique(void);
00242
00244
00245
00246 bool shared(void) const;
00248 bool shared(const View& y) const;
00250
00251 private:
00252 static void* operator new(size_t);
00253 static void operator delete(void*,size_t);
00254 };
00255
00269 template <class T>
00270 class ArgArrayBase {
00271 protected:
00273 int n;
00275 T* a;
00277 static const int onstack_size = 16;
00279 T onstack[onstack_size];
00281 T* allocate(int n);
00282 public:
00284
00285
00286 ArgArrayBase(int n);
00288 ArgArrayBase(const ArgArrayBase<T>& a);
00290 const ArgArrayBase<T>& operator=(const ArgArrayBase<T>& a);
00292
00294
00295
00296 int size(void) const;
00298
00300
00301
00302 T& operator[](int i);
00304 const T& operator[](int i) const;
00306
00308
00309
00310 ~ArgArrayBase(void);
00312 private:
00313 static void* operator new(size_t);
00314 static void operator delete(void*,size_t);
00315 };
00316
00317
00329 template <class T>
00330 class PrimArgArray : public ArgArrayBase<T> {
00331 protected:
00332 using ArgArrayBase<T>::a;
00333 public:
00334 using ArgArrayBase<T>::size;
00336
00337
00338 PrimArgArray(int n);
00340 PrimArgArray(int n, T e0, ...);
00342 PrimArgArray(int n, const T* e);
00344 PrimArgArray(const PrimArgArray<T>& a);
00346 };
00347
00359 template <class Var>
00360 class VarArgArray : public ArgArrayBase<Var> {
00361 protected:
00362 using ArgArrayBase<Var>::a;
00363 using ArgArrayBase<Var>::n;
00365 class VarLess {
00366 public:
00367 bool operator()(const Var&, const Var&);
00368 };
00369 public:
00370 using ArgArrayBase<Var>::size;
00372
00373
00374 VarArgArray(int n);
00376 VarArgArray(const VarArgArray<Var>& a);
00378 VarArgArray(const VarArray<Var>& a);
00380
00381
00382
00383 bool same(void) const;
00385 bool same(const Var& y) const;
00387 bool same(const VarArgArray<Var>& y) const;
00389 };
00390
00403 template <class A>
00404 class ArrayTraits {};
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416 template <class Var>
00417 forceinline
00418 VarArray<Var>::VarArray(void) : n(0), x(NULL) {}
00419
00420 template <class Var>
00421 forceinline
00422 VarArray<Var>::VarArray(Space* home, int n0)
00423 : n(n0) {
00424 x = (n>0) ? static_cast<Var*>(home->alloc(sizeof(Var)*n)) : NULL;
00425 }
00426
00427 template <class Var>
00428 forceinline
00429 VarArray<Var>::VarArray(const VarArray<Var>& a) {
00430 n = a.n; x = a.x;
00431 }
00432
00433 template <class Var>
00434 forceinline const VarArray<Var>&
00435 VarArray<Var>::operator=(const VarArray<Var>& a) {
00436 n = a.n; x = a.x;
00437 return *this;
00438 }
00439
00440 template <class Var>
00441 forceinline int
00442 VarArray<Var>::size(void) const {
00443 return n;
00444 }
00445
00446 template <class Var>
00447 forceinline Var&
00448 VarArray<Var>::operator[](int i) {
00449 assert((i >= 0) && (i < size()));
00450 return x[i];
00451 }
00452
00453 template <class Var>
00454 forceinline const Var&
00455 VarArray<Var>::operator[](int i) const {
00456 assert((i >= 0) && (i < size()));
00457 return x[i];
00458 }
00459
00460 template <class Var>
00461 forceinline void
00462 VarArray<Var>::update(Space* home, bool share, VarArray<Var>& a) {
00463 n = a.n;
00464 if (n > 0) {
00465 x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00466 for (int i = n; i--; )
00467 x[i].update(home, share, a.x[i]);
00468 } else {
00469 x = NULL;
00470 }
00471 }
00472
00473 template <class Var>
00474 void*
00475 VarArray<Var>::operator new(size_t) {
00476 return NULL;
00477 }
00478
00479 template <class Var>
00480 void
00481 VarArray<Var>::operator delete(void*,size_t) {
00482 }
00483
00484
00485
00486
00487
00488
00489 template <class View>
00490 forceinline
00491 ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00492
00493 template <class View>
00494 forceinline
00495 ViewArray<View>::ViewArray(Space* home, int n0)
00496 : n(n0) {
00497 x = (n>0) ? static_cast<View*>(home->alloc(sizeof(View)*n)) : NULL;
00498 }
00499
00500 template <class View>
00501 ViewArray<View>::ViewArray(Space* home, const ViewArray<View>& a)
00502 : n(a.size()) {
00503 if (n>0) {
00504 x = static_cast<View*>(home->alloc(sizeof(View)*n));
00505 for (int i = n; i--; )
00506 x[i] = a[i];
00507 } else {
00508 x = NULL;
00509 }
00510 }
00511
00512 template <class View>
00513 forceinline
00514 ViewArray<View>::ViewArray(const ViewArray<View>& a)
00515 : n(a.n), x(a.x) {}
00516
00517 template <class View>
00518 forceinline const ViewArray<View>&
00519 ViewArray<View>::operator=(const ViewArray<View>& a) {
00520 n = a.n; x = a.x;
00521 return *this;
00522 }
00523
00524 template <class View>
00525 forceinline int
00526 ViewArray<View>::size(void) const {
00527 return n;
00528 }
00529
00530 template <class View>
00531 forceinline void
00532 ViewArray<View>::size(int n0) {
00533 n = n0;
00534 }
00535
00536 template <class View>
00537 forceinline View&
00538 ViewArray<View>::operator[](int i) {
00539 assert((i >= 0) && (i < size()));
00540 return x[i];
00541 }
00542
00543 template <class View>
00544 forceinline const View&
00545 ViewArray<View>::operator[](int i) const {
00546 assert((i >= 0) && (i < size()));
00547 return x[i];
00548 }
00549
00550 template <class View>
00551 forceinline void
00552 ViewArray<View>::move_fst(int i) {
00553
00554 assert(x[i].assigned());
00555 x[i]=x[0]; x++; n--;
00556 }
00557
00558 template <class View>
00559 forceinline void
00560 ViewArray<View>::move_lst(int i) {
00561
00562 assert(x[i].assigned());
00563 n--; x[i]=x[n];
00564 }
00565
00566 template <class View>
00567 forceinline void
00568 ViewArray<View>::drop_fst(int i) {
00569
00570 assert(i>=0);
00571 x += i; n -= i;
00572 }
00573
00574 template <class View>
00575 forceinline void
00576 ViewArray<View>::drop_lst(int i) {
00577
00578 assert(i<n);
00579 n = i+1;
00580 }
00581
00582 template <class View>
00583 forceinline void
00584 ViewArray<View>::move_fst(int i, Space* home, Propagator* p, PropCond pc) {
00585
00586 x[i].cancel(home,p,pc);
00587 x[i]=x[0]; x++; n--;
00588 }
00589
00590 template <class View>
00591 forceinline void
00592 ViewArray<View>::move_lst(int i, Space* home, Propagator* p, PropCond pc) {
00593
00594 x[i].cancel(home,p,pc);
00595 n--; x[i]=x[n];
00596 }
00597
00598 template <class View>
00599 void
00600 ViewArray<View>::drop_fst(int i, Space* home, Propagator* p, PropCond pc) {
00601
00602 assert(i>=0);
00603 for (int j=i; j--; )
00604 x[j].cancel(home,p,pc);
00605 x += i; n -= i;
00606 }
00607
00608 template <class View>
00609 void
00610 ViewArray<View>::drop_lst(int i, Space* home, Propagator* p, PropCond pc) {
00611
00612 assert(i<n);
00613 for (int j=i+1; j<n; j++)
00614 x[j].cancel(home,p,pc);
00615 n = i+1;
00616 }
00617
00618 template <class View>
00619 void
00620 ViewArray<View>::update(Space* home, bool share, ViewArray<View>& y) {
00621 n = y.n;
00622 if (n > 0) {
00623 x = static_cast<View*>(home->alloc(sizeof(View)*n));
00624 for (int i = n; i--; )
00625 x[i].update(home, share, y.x[i]);
00626 } else {
00627 x = NULL;
00628 }
00629 }
00630
00631 template <class View>
00632 void
00633 ViewArray<View>::subscribe(Space* home, Propagator* p, PropCond pc,
00634 bool process) {
00635 for (int i = n; i--; )
00636 x[i].subscribe(home,p,pc,process);
00637 }
00638
00639 template <class View>
00640 void
00641 ViewArray<View>::cancel(Space* home, Propagator* p, PropCond pc) {
00642 for (int i = n; i--; )
00643 x[i].cancel(home,p,pc);
00644 }
00645
00646 template <class View>
00647 forceinline bool
00648 __before(const View& x, const View& y) {
00649 return before(x,y);
00650 }
00651
00652 template <class View>
00653 forceinline bool
00654 ViewArray<View>::ViewLess::operator()(const View& a, const View& b) {
00655 return __before(a,b);
00656 }
00657
00658 template <class View>
00659 void
00660 ViewArray<View>::sort(View* y, int m) {
00661 ViewLess vl;
00662 Support::quicksort<View,ViewLess>(y,m,vl);
00663 }
00664
00665 template <class View>
00666 forceinline bool
00667 __same(const View& x, const View& y) {
00668 return same(x,y);
00669 }
00670 template <class View>
00671 forceinline bool
00672 __shared(const View& x, const View& y) {
00673 return shared(x,y);
00674 }
00675
00676 template <class View>
00677 bool
00678 ViewArray<View>::same(void) const {
00679 if (n < 2)
00680 return false;
00681 GECODE_AUTOARRAY(View,y,n);
00682 for (int i = n; i--; )
00683 y[i] = x[i];
00684 sort(y,n);
00685 for (int i = n-1; i--; )
00686 if (__same(y[i+1],y[i]))
00687 return true;
00688 return false;
00689 }
00690
00691 template <class View>
00692 bool
00693 ViewArray<View>::same(const View& y) const {
00694 for (int i = n; i--; )
00695 if (__same(x[i],y))
00696 return true;
00697 return false;
00698 }
00699
00700 template <class View>
00701 void
00702 ViewArray<View>::unique(void) {
00703 if (n < 2)
00704 return;
00705 sort(x,n);
00706 int j = 0;
00707 for (int i = 1; i<n; i++)
00708 if (!__same(x[j],x[i]))
00709 x[++j] = x[i];
00710 n = j+1;
00711 }
00712
00713 template <class View>
00714 bool
00715 ViewArray<View>::shared(void) const {
00716 if (n < 2)
00717 return false;
00718 GECODE_AUTOARRAY(View,y,n);
00719 for (int i = n; i--; )
00720 y[i] = x[i];
00721 sort(y,n);
00722 for (int i = n-1; i--; )
00723 if (__shared(y[i+1],y[i]))
00724 return true;
00725 return false;
00726 }
00727
00728 template <class View>
00729 bool
00730 ViewArray<View>::shared(const View& y) const {
00731 for (int i = n; i--; )
00732 if (__shared(x[i],y))
00733 return true;
00734 return false;
00735 }
00736
00737 template <class View>
00738 void*
00739 ViewArray<View>::operator new(size_t) {
00740 return NULL;
00741 }
00742
00743 template <class View>
00744 void
00745 ViewArray<View>::operator delete(void*,size_t) {
00746 }
00747
00748
00749
00750
00751
00752
00753
00754 template <class T>
00755 forceinline T*
00756 ArgArrayBase<T>::allocate(int n) {
00757 return (n > onstack_size) ?
00758 Memory::bmalloc<T>(n) : &onstack[0];
00759 }
00760
00761 template <class T>
00762 forceinline
00763 ArgArrayBase<T>::ArgArrayBase(int n0)
00764 : n(n0), a(allocate(n0)) {}
00765
00766 template <class T>
00767 inline
00768 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
00769 : n(aa.n), a(allocate(aa.n)) {
00770 for (int i = n; i--; )
00771 a[i] = aa.a[i];
00772 }
00773
00774 template <class T>
00775 forceinline
00776 ArgArrayBase<T>::~ArgArrayBase(void) {
00777 if (n > onstack_size)
00778 Memory::free(a);
00779 }
00780
00781 template <class T>
00782 forceinline const ArgArrayBase<T>&
00783 ArgArrayBase<T>::operator=(const ArgArrayBase<T>& aa) {
00784 if (&aa != this) {
00785 if (n > onstack_size)
00786 Memory::free(a);
00787 n = aa.n;
00788 a = allocate(aa.n);
00789 for (int i = n; i--; )
00790 a[i] = aa.a[i];
00791 }
00792 return *this;
00793 }
00794
00795 template <class T>
00796 forceinline int
00797 ArgArrayBase<T>::size(void) const {
00798 return n;
00799 }
00800
00801 template <class T>
00802 forceinline T&
00803 ArgArrayBase<T>::operator[](int i) {
00804 assert((i>=0) && (i < n));
00805 return a[i];
00806 }
00807
00808 template <class T>
00809 forceinline const T&
00810 ArgArrayBase<T>::operator[](int i) const {
00811 assert((i>=0) && (i < n));
00812 return a[i];
00813 }
00814
00815
00816
00817
00818
00819
00820
00821 template <class T>
00822 forceinline
00823 PrimArgArray<T>::PrimArgArray(int n)
00824 : ArgArrayBase<T>(n) {}
00825
00826 template <class T>
00827 PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
00828 : ArgArrayBase<T>(n) {
00829 va_list args;
00830 va_start(args, a0);
00831 a[0] = a0;
00832 for (int i = 1; i < n; i++)
00833 a[i] = va_arg(args,T);
00834 va_end(args);
00835 }
00836
00837 template <class T>
00838 PrimArgArray<T>::PrimArgArray(int n, const T* a0)
00839 : ArgArrayBase<T>(n) {
00840 for (int i=n; i--; )
00841 a[i] = a0[i];
00842 }
00843
00844 template <class T>
00845 PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
00846 : ArgArrayBase<T>(aa.size()) {
00847 for (int i = size(); i--; )
00848 a[i] = aa.a[i];
00849 }
00850
00851
00852
00853
00854
00855
00856
00857
00858 template <class T>
00859 forceinline
00860 VarArgArray<T>::VarArgArray(int n)
00861 : ArgArrayBase<T>(n) {}
00862
00863 template <class T>
00864 inline
00865 VarArgArray<T>::VarArgArray(const VarArgArray<T>& aa)
00866 : ArgArrayBase<T>(aa.size()) {
00867 for (int i = size(); i--; )
00868 a[i] = aa.a[i];
00869 }
00870
00871 template <class T>
00872 inline
00873 VarArgArray<T>::VarArgArray(const VarArray<T>& x)
00874 : ArgArrayBase<T>(x.size()) {
00875 for (int i = x.size(); i--; )
00876 a[i] = x[i];
00877 }
00878
00879 template <class Var>
00880 forceinline bool
00881 VarArgArray<Var>::VarLess::operator()(const Var& a, const Var& b) {
00882 return a.variable() < b.variable();
00883 }
00884
00885 template <class Var>
00886 bool
00887 VarArgArray<Var>::same(void) const {
00888 if (n < 2)
00889 return false;
00890 GECODE_AUTOARRAY(Var,y,n);
00891 for (int i = n; i--; )
00892 y[i] = a[i];
00893 VarLess vl;
00894 Support::quicksort<Var,VarLess>(y,n,vl);
00895 for (int i = n-1; i--; )
00896 if (y[i+1].variable() == y[i].variable())
00897 return true;
00898 return false;
00899 }
00900
00901 template <class Var>
00902 bool
00903 VarArgArray<Var>::same(const VarArgArray<Var>& y) const {
00904 int m = n + y.n;
00905 if (m < 2)
00906 return false;
00907 GECODE_AUTOARRAY(Var,z,m);
00908 for (int i = n; i--; )
00909 z[i] = a[i];
00910 for (int i = y.n; i--; )
00911 z[i+n] = y.a[i];
00912 VarLess vl;
00913 Support::quicksort<Var,VarLess>(z,m,vl);
00914 for (int i = m-1; i--; )
00915 if (z[i+1].variable() == z[i].variable())
00916 return true;
00917 return false;
00918 }
00919
00920 template <class Var>
00921 bool
00922 VarArgArray<Var>::same(const Var& y) const {
00923 for (int i = n; i--; )
00924 if (a[i].variable() == y.variable())
00925 return true;
00926 return false;
00927 }
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937
00938
00939 template <class Var>
00940 inline
00941 VarArray<Var>::VarArray(Space* home, const VarArgArray<Var>& a)
00942 : n(a.size()) {
00943 if (n>0) {
00944 x = static_cast<Var*>(home->alloc(sizeof(Var)*n));
00945 for (int i = n; i--; )
00946 x[i] = a[i];
00947 } else {
00948 x = NULL;
00949 }
00950 }
00951
00952 }
00953
00954