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 "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(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
00387
00388
00389
00390
00391
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
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
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
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
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
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
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
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
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
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
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
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
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
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