00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #include <cstdarg>
00041 #include <iostream>
00042 #include <sstream>
00043
00044 namespace Gecode {
00045
00046 template<class Var> class VarArray;
00047 template<class Var> class VarArgArray;
00048
00064 template<class Var>
00065 class VarArray {
00066 protected:
00068 int n;
00070 int capacity;
00072 Var* x;
00073 public:
00075
00076
00077 VarArray(void);
00079 VarArray(Space& home, int m);
00081 VarArray(Space& home, const VarArgArray<Var>&);
00083 VarArray(const VarArray<Var>& a);
00085 const VarArray<Var>& operator =(const VarArray<Var>& a);
00087 ~VarArray(void);
00089
00091
00092
00093 int size(void) const;
00098 void resize(Space& home, int m);
00100
00102
00103
00104 Var& operator [](int i);
00106 const Var& operator [](int i) const;
00108 void add(Space& home, const Var& v);
00110
00112
00113
00120 void update(Space&, bool share, VarArray<Var>& a);
00122 private:
00123 static void* operator new(size_t);
00124 static void operator delete(void*,size_t);
00125 };
00126
00127
00136 template<class View>
00137 class ViewArray {
00138 private:
00140 int n;
00142 View* x;
00144 template<class X>
00145 class ViewLess {
00146 public:
00147 bool operator ()(const X&, const X&);
00148 };
00150 static void sort(View* x, int n);
00151 public:
00153
00154
00155 ViewArray(void);
00157 ViewArray(Space& home, int m);
00159 ViewArray(const ViewArray<View>& a);
00161 ViewArray(Space& home, const ViewArray<View>& a);
00163 const ViewArray<View>& operator =(const ViewArray<View>& a);
00170 template<class Var>
00171 ViewArray(Space& home, const VarArgArray<Var>& a)
00172 : n(a.size()) {
00173
00174 if (n>0) {
00175 x = home.alloc<View>(n);
00176 for (int i=n; i--; )
00177 x[i]=a[i];
00178 } else {
00179 x = NULL;
00180 }
00181 }
00183
00185
00186
00187 int size(void) const;
00189 void size(int n);
00191
00193
00194
00195 View& operator [](int i);
00197 const View& operator [](int i) const;
00199
00201
00202
00209 void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00211 void cancel(Space& home, Propagator& p, PropCond pc);
00213 void subscribe(Space& home, Advisor& a);
00215 void cancel(Space& home, Advisor& a);
00217
00219
00220
00227 void update(Space&, bool share, ViewArray<View>& a);
00229
00230
00232
00233
00234 void move_fst(int i);
00236 void move_lst(int i);
00242 void move_fst(int i, Space& home, Propagator& p, PropCond pc);
00248 void move_lst(int i, Space& home, Propagator& p, PropCond pc);
00254 void move_fst(int i, Space& home, Advisor& a);
00260 void move_lst(int i, Space& home, Advisor& a);
00262
00264
00265
00266 void drop_fst(int i);
00268 void drop_lst(int i);
00274 void drop_fst(int i, Space& home, Propagator& p, PropCond pc);
00281 void drop_lst(int i, Space& home, Propagator& p, PropCond pc);
00287 void drop_fst(int i, Space& home, Advisor& a);
00293 void drop_lst(int i, Space& home, Advisor& a);
00295
00297
00298
00303 bool same(const Space& home) const;
00309 bool same(const Space& home, const View& y) const;
00311 void unique(const Space& home);
00313
00315
00316
00321 bool shared(const Space& home) const;
00327 template<class ViewY>
00328 bool shared(const Space& home, const ViewY& y) const;
00334 template<class ViewY>
00335 bool shared(const Space& home, const ViewArray<ViewY>& y) const;
00337
00338 private:
00339 static void* operator new(size_t);
00340 static void operator delete(void*,size_t);
00341 };
00342
00356 template<class T>
00357 class ArgArrayBase {
00358 protected:
00360 int n;
00362 T* a;
00364 static const int onstack_size = 16;
00366 T onstack[onstack_size];
00368 T* allocate(int n);
00369 public:
00371
00372
00373 ArgArrayBase(int n);
00375 ArgArrayBase(const ArgArrayBase<T>& a);
00377 const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a);
00379
00381
00382
00383 int size(void) const;
00385
00387
00388
00389 T& operator [](int i);
00391 const T& operator [](int i) const;
00393
00395
00396
00397 ~ArgArrayBase(void);
00399 private:
00400 static void* operator new(size_t);
00401 static void operator delete(void*,size_t);
00402 };
00403
00404
00416 template<class T>
00417 class PrimArgArray : public ArgArrayBase<T> {
00418 protected:
00419 using ArgArrayBase<T>::a;
00420 public:
00421 using ArgArrayBase<T>::size;
00423
00424
00425 explicit PrimArgArray(int n);
00427 PrimArgArray(int n, T e0, ...);
00429 PrimArgArray(int n, const T* e);
00431 PrimArgArray(const PrimArgArray<T>& a);
00433 };
00434
00446 template<class T>
00447 class ArgArray : public ArgArrayBase<T> {
00448 protected:
00449 using ArgArrayBase<T>::a;
00450 public:
00451 using ArgArrayBase<T>::size;
00453
00454
00455 explicit ArgArray(int n);
00457 ArgArray(int n, const T* e);
00459 ArgArray(const ArgArray<T>& a);
00461 };
00462
00474 template<class Var>
00475 class VarArgArray : public ArgArrayBase<Var> {
00476 protected:
00477 using ArgArrayBase<Var>::a;
00478 using ArgArrayBase<Var>::n;
00480 class VarLess {
00481 public:
00482 bool operator ()(const Var&, const Var&);
00483 };
00484 public:
00485 using ArgArrayBase<Var>::size;
00487
00488
00489 explicit VarArgArray(int n);
00491 VarArgArray(const VarArgArray<Var>& a);
00493 VarArgArray(const VarArray<Var>& a);
00495
00496
00497
00502 bool same(const Space& home) const;
00508 bool same(const Space& home, const Var& y) const;
00514 bool same(const Space& home, const VarArgArray<Var>& y) const;
00516 };
00517
00522 template<class Char, class Traits, class Var>
00523 std::basic_ostream<Char,Traits>&
00524 operator <<(std::basic_ostream<Char,Traits>& os,
00525 const VarArray<Var>& x);
00526
00531 template<class Char, class Traits, class View>
00532 std::basic_ostream<Char,Traits>&
00533 operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
00534
00539 template<class Char, class Traits, class T>
00540 std::basic_ostream<Char,Traits>&
00541 operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
00542
00543
00544
00557 template<class A>
00558 class ArrayTraits {};
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575 template<class Var>
00576 forceinline
00577 VarArray<Var>::VarArray(void) : n(0), capacity(0), x(NULL) {}
00578
00579 template<class Var>
00580 forceinline
00581 VarArray<Var>::VarArray(Space& home, int n0)
00582 : n(n0), capacity(n0) {
00583
00584 x = (n>0) ? home.alloc<Var>(n) : NULL;
00585 }
00586
00587 template<class Var>
00588 forceinline
00589 VarArray<Var>::VarArray(const VarArray<Var>& a) {
00590 n = a.n; capacity = a.capacity; x = a.x;
00591 }
00592
00593 template<class Var>
00594 forceinline
00595 VarArray<Var>::~VarArray(void) {
00596 if (n != capacity) {
00597
00598 heap.free<Var>(x, capacity);
00599 }
00600 }
00601
00602 template<class Var>
00603 forceinline const VarArray<Var>&
00604 VarArray<Var>::operator =(const VarArray<Var>& a) {
00605 n = a.n; capacity = a.capacity; x = a.x;
00606 return *this;
00607 }
00608
00609 template<class Var>
00610 forceinline int
00611 VarArray<Var>::size(void) const {
00612 return n;
00613 }
00614
00615 template<class Var>
00616 forceinline void
00617 VarArray<Var>::resize(Space& home, int m) {
00618 int newsize;
00619 int newn;
00620 if (m<n) {
00621
00622 newsize = m+1;
00623 newn = m;
00624 } else if (m<capacity) {
00625
00626 n = m;
00627 return;
00628 } else {
00629
00630 newsize = std::max(m+1, (3*capacity)/2);
00631 newn = n;
00632 }
00633
00634 if (n == capacity) {
00635
00636 Var* oldx = x;
00637 x = heap.copy<Var>(heap.alloc<Var>(newsize), x, newn);
00638 home.rfree(oldx, capacity);
00639 } else {
00640
00641 x = heap.realloc<Var>(x, n, newsize);
00642 }
00643 capacity = newsize; n = m;
00644
00645 assert(capacity != n);
00646 }
00647
00648 template<class Var>
00649 forceinline Var&
00650 VarArray<Var>::operator [](int i) {
00651 assert((i >= 0) && (i < size()));
00652 return x[i];
00653 }
00654
00655 template<class Var>
00656 forceinline const Var&
00657 VarArray<Var>::operator [](int i) const {
00658 assert((i >= 0) && (i < size()));
00659 return x[i];
00660 }
00661
00662 template<class Var>
00663 forceinline void
00664 VarArray<Var>::add(Space& home, const Var& v) {
00665 resize(home, n+1);
00666 new (&(*this)[n-1]) Var(v);
00667 }
00668
00669 template<class Var>
00670 forceinline void
00671 VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) {
00672 capacity = a.n;
00673 n = capacity;
00674 if (capacity > 0) {
00675 x = home.alloc<Var>(capacity);
00676 for (int i = capacity; i--; )
00677 x[i].update(home, share, a.x[i]);
00678 } else {
00679 x = NULL;
00680 }
00681 }
00682
00683 template<class Var>
00684 void*
00685 VarArray<Var>::operator new(size_t) {
00686 return NULL;
00687 }
00688
00689 template<class Var>
00690 void
00691 VarArray<Var>::operator delete(void*,size_t) {
00692 }
00693
00694
00695
00696
00697
00698
00699 template<class View>
00700 forceinline
00701 ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00702
00703 template<class View>
00704 forceinline
00705 ViewArray<View>::ViewArray(Space& home, int n0)
00706 : n(n0) {
00707 x = (n>0) ? home.alloc<View>(n) : NULL;
00708 }
00709
00710 template<class View>
00711 ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
00712 : n(a.size()) {
00713 if (n>0) {
00714 x = home.alloc<View>(n);
00715 for (int i = n; i--; )
00716 x[i] = a[i];
00717 } else {
00718 x = NULL;
00719 }
00720 }
00721
00722 template<class View>
00723 forceinline
00724 ViewArray<View>::ViewArray(const ViewArray<View>& a)
00725 : n(a.n), x(a.x) {}
00726
00727 template<class View>
00728 forceinline const ViewArray<View>&
00729 ViewArray<View>::operator =(const ViewArray<View>& a) {
00730 n = a.n; x = a.x;
00731 return *this;
00732 }
00733
00734 template<class View>
00735 forceinline int
00736 ViewArray<View>::size(void) const {
00737 return n;
00738 }
00739
00740 template<class View>
00741 forceinline void
00742 ViewArray<View>::size(int n0) {
00743 n = n0;
00744 }
00745
00746 template<class View>
00747 forceinline View&
00748 ViewArray<View>::operator [](int i) {
00749 assert((i >= 0) && (i < size()));
00750 return x[i];
00751 }
00752
00753 template<class View>
00754 forceinline const View&
00755 ViewArray<View>::operator [](int i) const {
00756 assert((i >= 0) && (i < size()));
00757 return x[i];
00758 }
00759
00760 template<class View>
00761 forceinline void
00762 ViewArray<View>::move_fst(int i) {
00763 x[i]=x[0]; x++; n--;
00764 }
00765
00766 template<class View>
00767 forceinline void
00768 ViewArray<View>::move_lst(int i) {
00769 n--; x[i]=x[n];
00770 }
00771
00772 template<class View>
00773 forceinline void
00774 ViewArray<View>::drop_fst(int i) {
00775 assert(i>=0);
00776 x += i; n -= i;
00777 }
00778
00779 template<class View>
00780 forceinline void
00781 ViewArray<View>::drop_lst(int i) {
00782 assert(i<n);
00783 n = i+1;
00784 }
00785
00786 template<class View>
00787 forceinline void
00788 ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
00789
00790 x[i].cancel(home,p,pc);
00791 x[i]=x[0]; x++; n--;
00792 }
00793
00794 template<class View>
00795 forceinline void
00796 ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
00797
00798 x[i].cancel(home,p,pc);
00799 n--; x[i]=x[n];
00800 }
00801
00802 template<class View>
00803 void
00804 ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
00805
00806 assert(i>=0);
00807 for (int j=i; j--; )
00808 x[j].cancel(home,p,pc);
00809 x += i; n -= i;
00810 }
00811
00812 template<class View>
00813 void
00814 ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
00815
00816 assert(i<n);
00817 for (int j=i+1; j<n; j++)
00818 x[j].cancel(home,p,pc);
00819 n = i+1;
00820 }
00821
00822 template<class View>
00823 forceinline void
00824 ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
00825
00826 x[i].cancel(home,a);
00827 x[i]=x[0]; x++; n--;
00828 }
00829
00830 template<class View>
00831 forceinline void
00832 ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
00833
00834 x[i].cancel(home,a);
00835 n--; x[i]=x[n];
00836 }
00837
00838 template<class View>
00839 void
00840 ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
00841
00842 assert(i>=0);
00843 for (int j=i; j--; )
00844 x[j].cancel(home,a);
00845 x += i; n -= i;
00846 }
00847
00848 template<class View>
00849 void
00850 ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
00851
00852 assert(i<n);
00853 for (int j=i+1; j<n; j++)
00854 x[j].cancel(home,a);
00855 n = i+1;
00856 }
00857
00858 template<class View>
00859 void
00860 ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) {
00861 n = y.n;
00862 if (n > 0) {
00863 x = home.alloc<View>(n);
00864 for (int i = n; i--; )
00865 x[i].update(home, share, y.x[i]);
00866 } else {
00867 x = NULL;
00868 }
00869 }
00870
00871 template<class View>
00872 void
00873 ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00874 bool process) {
00875 for (int i = n; i--; )
00876 x[i].subscribe(home,p,pc,process);
00877 }
00878
00879 template<class View>
00880 void
00881 ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00882 for (int i = n; i--; )
00883 x[i].cancel(home,p,pc);
00884 }
00885
00886 template<class View>
00887 void
00888 ViewArray<View>::subscribe(Space& home, Advisor& a) {
00889 for (int i = n; i--; )
00890 x[i].subscribe(home,a);
00891 }
00892
00893 template<class View>
00894 void
00895 ViewArray<View>::cancel(Space& home, Advisor& a) {
00896 for (int i = n; i--; )
00897 x[i].cancel(home,a);
00898 }
00899
00900 template<class View>
00901 forceinline bool
00902 __before(const View& x, const View& y) {
00903 return before(x,y);
00904 }
00905
00906 template<class View> template<class X>
00907 forceinline bool
00908 ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
00909 return __before(a,b);
00910 }
00911
00912 template<class View>
00913 void
00914 ViewArray<View>::sort(View* y, int m) {
00915 ViewLess<View> vl;
00916 Support::quicksort<View,ViewLess<View> >(y,m,vl);
00917 }
00918
00919 template<class X, class Y>
00920 forceinline bool
00921 __same(const X& x, const Y& y) {
00922 return same(x,y);
00923 }
00924 template<class X, class Y>
00925 forceinline bool
00926 __shared(const X& x, const Y& y) {
00927 return shared(x,y);
00928 }
00929
00930 template<class View>
00931 bool
00932 ViewArray<View>::same(const Space& home) const {
00933 if (n < 2)
00934 return false;
00935 Region r(home);
00936 View* y = r.alloc<View>(n);
00937 for (int i = n; i--; )
00938 y[i] = x[i];
00939 sort(y,n);
00940 for (int i = n-1; i--; )
00941 if (!y[i].assigned() && __same(y[i+1],y[i])) {
00942 r.free<View>(y,n);
00943 return true;
00944 }
00945 r.free<View>(y,n);
00946 return false;
00947 }
00948
00949 template<class View>
00950 bool
00951 ViewArray<View>::same(const Space&, const View& y) const {
00952 if (y.assigned())
00953 return false;
00954 for (int i = n; i--; )
00955 if (__same(x[i],y))
00956 return true;
00957 return false;
00958 }
00959
00960 template<class View>
00961 void
00962 ViewArray<View>::unique(const Space&) {
00963 if (n < 2)
00964 return;
00965 sort(x,n);
00966 int j = 0;
00967 for (int i = 1; i<n; i++)
00968 if (!__same(x[j],x[i]))
00969 x[++j] = x[i];
00970 n = j+1;
00971 }
00972
00973 template<class View>
00974 bool
00975 ViewArray<View>::shared(const Space& home) const {
00976 if (n < 2)
00977 return false;
00978 Region r(home);
00979 View* y = r.alloc<View>(n);
00980 for (int i = n; i--; )
00981 y[i] = x[i];
00982 sort(y,n);
00983 for (int i = n-1; i--; )
00984 if (!y[i].assigned() && __shared(y[i+1],y[i])) {
00985 r.free<View>(y,n);
00986 return true;
00987 }
00988 r.free<View>(y,n);
00989 return false;
00990 }
00991
00992 template<class View> template<class ViewY>
00993 bool
00994 ViewArray<View>::shared(const Space&, const ViewY& y) const {
00995 if (y.assigned())
00996 return false;
00997 for (int i = n; i--; )
00998 if (!x[i].assigned() && __shared(x[i],y))
00999 return true;
01000 return false;
01001 }
01002
01003 template<class View> template<class ViewY>
01004 bool
01005 ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
01006 if ((size() < 1) || (y.size() < 1))
01007 return false;
01008 Region r(home);
01009 View* xs = r.alloc<View>(size());
01010 for (int i=size(); i--; )
01011 xs[i] = x[i];
01012 ViewLess<View> xvl;
01013 Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
01014 ViewY* ys = r.alloc<ViewY>(y.size());
01015 for (int j=y.size(); j--; )
01016 ys[j] = y[j];
01017 ViewLess<ViewY> yvl;
01018 Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
01019 {
01020 int i=0, j=0;
01021 while ((i < size()) && (j < y.size()))
01022 if (!x[i].assigned() && __shared(x[i],y[j])) {
01023 r.free<View>(xs,size());
01024 r.free<ViewY>(ys,y.size());
01025 return true;
01026 } else if (before(x[i],y[j])) {
01027 i++;
01028 } else {
01029 j++;
01030 }
01031 }
01032 r.free<View>(xs,size());
01033 r.free<ViewY>(ys,y.size());
01034 return false;
01035 }
01036
01037 template<class View>
01038 void*
01039 ViewArray<View>::operator new(size_t) {
01040 return NULL;
01041 }
01042
01043 template<class View>
01044 void
01045 ViewArray<View>::operator delete(void*,size_t) {
01046 }
01047
01048
01049
01050
01051
01052
01053
01054 template<class T>
01055 forceinline T*
01056 ArgArrayBase<T>::allocate(int n) {
01057 return (n > onstack_size) ?
01058 heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01059 }
01060
01061 template<class T>
01062 forceinline
01063 ArgArrayBase<T>::ArgArrayBase(int n0)
01064 : n(n0), a(allocate(n)) {}
01065
01066 template<class T>
01067 inline
01068 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01069 : n(aa.n), a(allocate(n)) {
01070 heap.copy<T>(a,aa.a,n);
01071 }
01072
01073 template<class T>
01074 forceinline
01075 ArgArrayBase<T>::~ArgArrayBase(void) {
01076 if (n > onstack_size)
01077 heap.free(a,n);
01078 }
01079
01080 template<class T>
01081 forceinline const ArgArrayBase<T>&
01082 ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01083 if (&aa != this) {
01084 if (n > onstack_size)
01085 heap.free(a,n);
01086 n = aa.n;
01087 a = allocate(aa.n);
01088 heap.copy<T>(a,aa.a,n);
01089 }
01090 return *this;
01091 }
01092
01093 template<class T>
01094 forceinline int
01095 ArgArrayBase<T>::size(void) const {
01096 return n;
01097 }
01098
01099 template<class T>
01100 forceinline T&
01101 ArgArrayBase<T>::operator [](int i) {
01102 assert((i>=0) && (i < n));
01103 return a[i];
01104 }
01105
01106 template<class T>
01107 forceinline const T&
01108 ArgArrayBase<T>::operator [](int i) const {
01109 assert((i>=0) && (i < n));
01110 return a[i];
01111 }
01112
01113
01114
01115
01116
01117
01118
01119 template<class T>
01120 forceinline
01121 PrimArgArray<T>::PrimArgArray(int n)
01122 : ArgArrayBase<T>(n) {}
01123
01124 template<class T>
01125 PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
01126 : ArgArrayBase<T>(n) {
01127 va_list args;
01128 va_start(args, a0);
01129 a[0] = a0;
01130 for (int i = 1; i < n; i++)
01131 a[i] = va_arg(args,T);
01132 va_end(args);
01133 }
01134
01135 template<class T>
01136 PrimArgArray<T>::PrimArgArray(int n, const T* a0)
01137 : ArgArrayBase<T>(n) {
01138 for (int i=n; i--; )
01139 a[i] = a0[i];
01140 }
01141
01142 template<class T>
01143 forceinline
01144 PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
01145 : ArgArrayBase<T>(aa) {}
01146
01147
01148
01149
01150
01151
01152
01153 template<class T>
01154 forceinline
01155 ArgArray<T>::ArgArray(int n)
01156 : ArgArrayBase<T>(n) {}
01157
01158 template<class T>
01159 ArgArray<T>::ArgArray(int n, const T* a0)
01160 : ArgArrayBase<T>(n) {
01161 for (int i=n; i--; )
01162 a[i] = a0[i];
01163 }
01164
01165 template<class T>
01166 forceinline
01167 ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01168 : ArgArrayBase<T>(aa) {}
01169
01170
01171
01172
01173
01174
01175
01176
01177 template<class Var>
01178 forceinline
01179 VarArgArray<Var>::VarArgArray(int n)
01180 : ArgArrayBase<Var>(n) {}
01181
01182 template<class Var>
01183 forceinline
01184 VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01185 : ArgArrayBase<Var>(aa) {}
01186
01187 template<class Var>
01188 inline
01189 VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01190 : ArgArrayBase<Var>(x.size()) {
01191 for (int i=x.size(); i--; )
01192 a[i]=x[i];
01193 }
01194
01195 template<class Var>
01196 forceinline bool
01197 VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) {
01198 return a.var() < b.var();
01199 }
01200
01201 template<class Var>
01202 bool
01203 VarArgArray<Var>::same(const Space& home) const {
01204 if (n < 2)
01205 return false;
01206 Region r(home);
01207 Var* y = r.alloc<Var>(n);
01208 for (int i = n; i--; )
01209 y[i] = a[i];
01210 VarLess vl;
01211 Support::quicksort<Var,VarLess>(y,n,vl);
01212 for (int i = n-1; i--; )
01213 if (!y[i].assigned() && (y[i+1].var() == y[i].var())) {
01214 r.free<Var>(y,n);
01215 return true;
01216 }
01217 r.free<Var>(y,n);
01218 return false;
01219 }
01220
01221 template<class Var>
01222 bool
01223 VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
01224 int m = n + y.n;
01225 if (m < 2)
01226 return false;
01227 Region r(home);
01228 Var* z = r.alloc<Var>(m);
01229 for (int i = n; i--; )
01230 z[i] = a[i];
01231 for (int i = y.n; i--; )
01232 z[i+n] = y.a[i];
01233 VarLess vl;
01234 Support::quicksort<Var,VarLess>(z,m,vl);
01235 for (int i = m-1; i--; )
01236 if (!z[i].assigned() && (z[i+1].var() == z[i].var())) {
01237 r.free<Var>(z,m);
01238 return true;
01239 }
01240 r.free<Var>(z,m);
01241 return false;
01242 }
01243
01244 template<class Var>
01245 bool
01246 VarArgArray<Var>::same(const Space&, const Var& y) const {
01247 if (y.assigned())
01248 return false;
01249 for (int i = n; i--; )
01250 if (a[i].var() == y.var())
01251 return true;
01252 return false;
01253 }
01254
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265 template<class Var>
01266 inline
01267 VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
01268 : n(a.size()), capacity(a.size()) {
01269 if (capacity>0) {
01270 x = home.alloc<Var>(capacity);
01271 for (int i = capacity; i--; )
01272 x[i] = a[i];
01273 } else {
01274 x = NULL;
01275 }
01276 }
01277
01278
01279
01280
01281
01282
01283 template<class Char, class Traits, class Var>
01284 std::basic_ostream<Char,Traits>&
01285 operator <<(std::basic_ostream<Char,Traits>& os,
01286 const VarArray<Var>& x) {
01287 std::basic_ostringstream<Char,Traits> s;
01288 s.copyfmt(os); s.width(0);
01289 s << '{';
01290 if (x.size() > 0) {
01291 s << x[0];
01292 for (int i=1; i<x.size(); i++)
01293 s << ", " << x[i];
01294 }
01295 s << '}';
01296 return os << s.str();
01297 }
01298
01299 template<class Char, class Traits, class View>
01300 std::basic_ostream<Char,Traits>&
01301 operator <<(std::basic_ostream<Char,Traits>& os,
01302 const ViewArray<View>& x) {
01303 std::basic_ostringstream<Char,Traits> s;
01304 s.copyfmt(os); s.width(0);
01305 s << '{';
01306 if (x.size() > 0) {
01307 s << x[0];
01308 for (int i=1; i<x.size(); i++)
01309 s << ", " << x[i];
01310 }
01311 s << '}';
01312 return os << s.str();
01313 }
01314
01315 template<class Char, class Traits, class T>
01316 std::basic_ostream<Char,Traits>&
01317 operator <<(std::basic_ostream<Char,Traits>& os,
01318 const ArgArrayBase<T>& x) {
01319 std::basic_ostringstream<Char,Traits> s;
01320 s.copyfmt(os); s.width(0);
01321 s << '{';
01322 if (x.size() > 0) {
01323 s << x[0];
01324 for (int i=1; i<x.size(); i++)
01325 s << ", " << x[i];
01326 }
01327 s << '}';
01328 return os << s.str();
01329 }
01330
01331 }
01332
01333