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 if (m<n) {
00620
00621 newsize = m+1;
00622 } else if (m<capacity) {
00623
00624 n = m;
00625 return;
00626 } else {
00627
00628 newsize = std::max(m+1, (3*capacity)/2);
00629 }
00630
00631 if (n == capacity) {
00632
00633 Var* oldx = x;
00634 x = heap.copy<Var>(heap.alloc<Var>(newsize), x, n);
00635 home.rfree(oldx, capacity);
00636 } else {
00637
00638 x = heap.realloc<Var>(x, n, newsize);
00639 }
00640 capacity = newsize; n = m;
00641
00642 assert(capacity != n);
00643 }
00644
00645 template<class Var>
00646 forceinline Var&
00647 VarArray<Var>::operator [](int i) {
00648 assert((i >= 0) && (i < size()));
00649 return x[i];
00650 }
00651
00652 template<class Var>
00653 forceinline const Var&
00654 VarArray<Var>::operator [](int i) const {
00655 assert((i >= 0) && (i < size()));
00656 return x[i];
00657 }
00658
00659 template<class Var>
00660 forceinline void
00661 VarArray<Var>::add(Space& home, const Var& v) {
00662 resize(home, n+1);
00663 new (&(*this)[n-1]) Var(v);
00664 }
00665
00666 template<class Var>
00667 forceinline void
00668 VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) {
00669 capacity = a.n;
00670 n = capacity;
00671 if (capacity > 0) {
00672 x = home.alloc<Var>(capacity);
00673 for (int i = capacity; i--; )
00674 x[i].update(home, share, a.x[i]);
00675 } else {
00676 x = NULL;
00677 }
00678 }
00679
00680 template<class Var>
00681 void*
00682 VarArray<Var>::operator new(size_t) {
00683 return NULL;
00684 }
00685
00686 template<class Var>
00687 void
00688 VarArray<Var>::operator delete(void*,size_t) {
00689 }
00690
00691
00692
00693
00694
00695
00696 template<class View>
00697 forceinline
00698 ViewArray<View>::ViewArray(void) : n(0), x(NULL) {}
00699
00700 template<class View>
00701 forceinline
00702 ViewArray<View>::ViewArray(Space& home, int n0)
00703 : n(n0) {
00704 x = (n>0) ? home.alloc<View>(n) : NULL;
00705 }
00706
00707 template<class View>
00708 ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a)
00709 : n(a.size()) {
00710 if (n>0) {
00711 x = home.alloc<View>(n);
00712 for (int i = n; i--; )
00713 x[i] = a[i];
00714 } else {
00715 x = NULL;
00716 }
00717 }
00718
00719 template<class View>
00720 forceinline
00721 ViewArray<View>::ViewArray(const ViewArray<View>& a)
00722 : n(a.n), x(a.x) {}
00723
00724 template<class View>
00725 forceinline const ViewArray<View>&
00726 ViewArray<View>::operator =(const ViewArray<View>& a) {
00727 n = a.n; x = a.x;
00728 return *this;
00729 }
00730
00731 template<class View>
00732 forceinline int
00733 ViewArray<View>::size(void) const {
00734 return n;
00735 }
00736
00737 template<class View>
00738 forceinline void
00739 ViewArray<View>::size(int n0) {
00740 n = n0;
00741 }
00742
00743 template<class View>
00744 forceinline View&
00745 ViewArray<View>::operator [](int i) {
00746 assert((i >= 0) && (i < size()));
00747 return x[i];
00748 }
00749
00750 template<class View>
00751 forceinline const View&
00752 ViewArray<View>::operator [](int i) const {
00753 assert((i >= 0) && (i < size()));
00754 return x[i];
00755 }
00756
00757 template<class View>
00758 forceinline void
00759 ViewArray<View>::move_fst(int i) {
00760
00761 assert(x[i].assigned());
00762 x[i]=x[0]; x++; n--;
00763 }
00764
00765 template<class View>
00766 forceinline void
00767 ViewArray<View>::move_lst(int i) {
00768
00769 assert(x[i].assigned());
00770 n--; x[i]=x[n];
00771 }
00772
00773 template<class View>
00774 forceinline void
00775 ViewArray<View>::drop_fst(int i) {
00776
00777 assert(i>=0);
00778 x += i; n -= i;
00779 }
00780
00781 template<class View>
00782 forceinline void
00783 ViewArray<View>::drop_lst(int i) {
00784
00785 assert(i<n);
00786 n = i+1;
00787 }
00788
00789 template<class View>
00790 forceinline void
00791 ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) {
00792
00793 x[i].cancel(home,p,pc);
00794 x[i]=x[0]; x++; n--;
00795 }
00796
00797 template<class View>
00798 forceinline void
00799 ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) {
00800
00801 x[i].cancel(home,p,pc);
00802 n--; x[i]=x[n];
00803 }
00804
00805 template<class View>
00806 void
00807 ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) {
00808
00809 assert(i>=0);
00810 for (int j=i; j--; )
00811 x[j].cancel(home,p,pc);
00812 x += i; n -= i;
00813 }
00814
00815 template<class View>
00816 void
00817 ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) {
00818
00819 assert(i<n);
00820 for (int j=i+1; j<n; j++)
00821 x[j].cancel(home,p,pc);
00822 n = i+1;
00823 }
00824
00825 template<class View>
00826 forceinline void
00827 ViewArray<View>::move_fst(int i, Space& home, Advisor& a) {
00828
00829 x[i].cancel(home,a);
00830 x[i]=x[0]; x++; n--;
00831 }
00832
00833 template<class View>
00834 forceinline void
00835 ViewArray<View>::move_lst(int i, Space& home, Advisor& a) {
00836
00837 x[i].cancel(home,a);
00838 n--; x[i]=x[n];
00839 }
00840
00841 template<class View>
00842 void
00843 ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) {
00844
00845 assert(i>=0);
00846 for (int j=i; j--; )
00847 x[j].cancel(home,a);
00848 x += i; n -= i;
00849 }
00850
00851 template<class View>
00852 void
00853 ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) {
00854
00855 assert(i<n);
00856 for (int j=i+1; j<n; j++)
00857 x[j].cancel(home,a);
00858 n = i+1;
00859 }
00860
00861 template<class View>
00862 void
00863 ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) {
00864 n = y.n;
00865 if (n > 0) {
00866 x = home.alloc<View>(n);
00867 for (int i = n; i--; )
00868 x[i].update(home, share, y.x[i]);
00869 } else {
00870 x = NULL;
00871 }
00872 }
00873
00874 template<class View>
00875 void
00876 ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00877 bool process) {
00878 for (int i = n; i--; )
00879 x[i].subscribe(home,p,pc,process);
00880 }
00881
00882 template<class View>
00883 void
00884 ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00885 for (int i = n; i--; )
00886 x[i].cancel(home,p,pc);
00887 }
00888
00889 template<class View>
00890 void
00891 ViewArray<View>::subscribe(Space& home, Advisor& a) {
00892 for (int i = n; i--; )
00893 x[i].subscribe(home,a);
00894 }
00895
00896 template<class View>
00897 void
00898 ViewArray<View>::cancel(Space& home, Advisor& a) {
00899 for (int i = n; i--; )
00900 x[i].cancel(home,a);
00901 }
00902
00903 template<class View>
00904 forceinline bool
00905 __before(const View& x, const View& y) {
00906 return before(x,y);
00907 }
00908
00909 template<class View> template<class X>
00910 forceinline bool
00911 ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) {
00912 return __before(a,b);
00913 }
00914
00915 template<class View>
00916 void
00917 ViewArray<View>::sort(View* y, int m) {
00918 ViewLess<View> vl;
00919 Support::quicksort<View,ViewLess<View> >(y,m,vl);
00920 }
00921
00922 template<class X, class Y>
00923 forceinline bool
00924 __same(const X& x, const Y& y) {
00925 return same(x,y);
00926 }
00927 template<class X, class Y>
00928 forceinline bool
00929 __shared(const X& x, const Y& y) {
00930 return shared(x,y);
00931 }
00932
00933 template<class View>
00934 bool
00935 ViewArray<View>::same(const Space& home) const {
00936 if (n < 2)
00937 return false;
00938 Region r(home);
00939 View* y = r.alloc<View>(n);
00940 for (int i = n; i--; )
00941 y[i] = x[i];
00942 sort(y,n);
00943 for (int i = n-1; i--; )
00944 if (!y[i].assigned() && __same(y[i+1],y[i])) {
00945 r.free<View>(y,n);
00946 return true;
00947 }
00948 r.free<View>(y,n);
00949 return false;
00950 }
00951
00952 template<class View>
00953 bool
00954 ViewArray<View>::same(const Space&, const View& y) const {
00955 if (y.assigned())
00956 return false;
00957 for (int i = n; i--; )
00958 if (__same(x[i],y))
00959 return true;
00960 return false;
00961 }
00962
00963 template<class View>
00964 void
00965 ViewArray<View>::unique(const Space&) {
00966 if (n < 2)
00967 return;
00968 sort(x,n);
00969 int j = 0;
00970 for (int i = 1; i<n; i++)
00971 if (!__same(x[j],x[i]))
00972 x[++j] = x[i];
00973 n = j+1;
00974 }
00975
00976 template<class View>
00977 bool
00978 ViewArray<View>::shared(const Space& home) const {
00979 if (n < 2)
00980 return false;
00981 Region r(home);
00982 View* y = r.alloc<View>(n);
00983 for (int i = n; i--; )
00984 y[i] = x[i];
00985 sort(y,n);
00986 for (int i = n-1; i--; )
00987 if (!y[i].assigned() && __shared(y[i+1],y[i])) {
00988 r.free<View>(y,n);
00989 return true;
00990 }
00991 r.free<View>(y,n);
00992 return false;
00993 }
00994
00995 template<class View> template<class ViewY>
00996 bool
00997 ViewArray<View>::shared(const Space&, const ViewY& y) const {
00998 if (y.assigned())
00999 return false;
01000 for (int i = n; i--; )
01001 if (!x[i].assigned() && __shared(x[i],y))
01002 return true;
01003 return false;
01004 }
01005
01006 template<class View> template<class ViewY>
01007 bool
01008 ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const {
01009 if ((size() < 1) || (y.size() < 1))
01010 return false;
01011 Region r(home);
01012 View* xs = r.alloc<View>(size());
01013 for (int i=size(); i--; )
01014 xs[i] = x[i];
01015 ViewLess<View> xvl;
01016 Support::quicksort<View,ViewLess<View> >(xs,size(),xvl);
01017 ViewY* ys = r.alloc<ViewY>(y.size());
01018 for (int j=y.size(); j--; )
01019 ys[j] = y[j];
01020 ViewLess<ViewY> yvl;
01021 Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl);
01022 {
01023 int i=0, j=0;
01024 while ((i < size()) && (j < y.size()))
01025 if (!x[i].assigned() && __shared(x[i],y[j])) {
01026 r.free<View>(xs,size());
01027 r.free<ViewY>(ys,y.size());
01028 return true;
01029 } else if (before(x[i],y[j])) {
01030 i++;
01031 } else {
01032 j++;
01033 }
01034 }
01035 r.free<View>(xs,size());
01036 r.free<ViewY>(ys,y.size());
01037 return false;
01038 }
01039
01040 template<class View>
01041 void*
01042 ViewArray<View>::operator new(size_t) {
01043 return NULL;
01044 }
01045
01046 template<class View>
01047 void
01048 ViewArray<View>::operator delete(void*,size_t) {
01049 }
01050
01051
01052
01053
01054
01055
01056
01057 template<class T>
01058 forceinline T*
01059 ArgArrayBase<T>::allocate(int n) {
01060 return (n > onstack_size) ?
01061 heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0];
01062 }
01063
01064 template<class T>
01065 forceinline
01066 ArgArrayBase<T>::ArgArrayBase(int n0)
01067 : n(n0), a(allocate(n)) {}
01068
01069 template<class T>
01070 inline
01071 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa)
01072 : n(aa.n), a(allocate(n)) {
01073 heap.copy<T>(a,aa.a,n);
01074 }
01075
01076 template<class T>
01077 forceinline
01078 ArgArrayBase<T>::~ArgArrayBase(void) {
01079 if (n > onstack_size)
01080 heap.free(a,n);
01081 }
01082
01083 template<class T>
01084 forceinline const ArgArrayBase<T>&
01085 ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) {
01086 if (&aa != this) {
01087 if (n > onstack_size)
01088 heap.free(a,n);
01089 n = aa.n;
01090 a = allocate(aa.n);
01091 heap.copy<T>(a,aa.a,n);
01092 }
01093 return *this;
01094 }
01095
01096 template<class T>
01097 forceinline int
01098 ArgArrayBase<T>::size(void) const {
01099 return n;
01100 }
01101
01102 template<class T>
01103 forceinline T&
01104 ArgArrayBase<T>::operator [](int i) {
01105 assert((i>=0) && (i < n));
01106 return a[i];
01107 }
01108
01109 template<class T>
01110 forceinline const T&
01111 ArgArrayBase<T>::operator [](int i) const {
01112 assert((i>=0) && (i < n));
01113 return a[i];
01114 }
01115
01116
01117
01118
01119
01120
01121
01122 template<class T>
01123 forceinline
01124 PrimArgArray<T>::PrimArgArray(int n)
01125 : ArgArrayBase<T>(n) {}
01126
01127 template<class T>
01128 PrimArgArray<T>::PrimArgArray(int n, T a0, ...)
01129 : ArgArrayBase<T>(n) {
01130 va_list args;
01131 va_start(args, a0);
01132 a[0] = a0;
01133 for (int i = 1; i < n; i++)
01134 a[i] = va_arg(args,T);
01135 va_end(args);
01136 }
01137
01138 template<class T>
01139 PrimArgArray<T>::PrimArgArray(int n, const T* a0)
01140 : ArgArrayBase<T>(n) {
01141 for (int i=n; i--; )
01142 a[i] = a0[i];
01143 }
01144
01145 template<class T>
01146 forceinline
01147 PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa)
01148 : ArgArrayBase<T>(aa) {}
01149
01150
01151
01152
01153
01154
01155
01156 template<class T>
01157 forceinline
01158 ArgArray<T>::ArgArray(int n)
01159 : ArgArrayBase<T>(n) {}
01160
01161 template<class T>
01162 ArgArray<T>::ArgArray(int n, const T* a0)
01163 : ArgArrayBase<T>(n) {
01164 for (int i=n; i--; )
01165 a[i] = a0[i];
01166 }
01167
01168 template<class T>
01169 forceinline
01170 ArgArray<T>::ArgArray(const ArgArray<T>& aa)
01171 : ArgArrayBase<T>(aa) {}
01172
01173
01174
01175
01176
01177
01178
01179
01180 template<class Var>
01181 forceinline
01182 VarArgArray<Var>::VarArgArray(int n)
01183 : ArgArrayBase<Var>(n) {}
01184
01185 template<class Var>
01186 forceinline
01187 VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa)
01188 : ArgArrayBase<Var>(aa) {}
01189
01190 template<class Var>
01191 inline
01192 VarArgArray<Var>::VarArgArray(const VarArray<Var>& x)
01193 : ArgArrayBase<Var>(x.size()) {
01194 for (int i=x.size(); i--; )
01195 a[i]=x[i];
01196 }
01197
01198 template<class Var>
01199 forceinline bool
01200 VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) {
01201 return a.var() < b.var();
01202 }
01203
01204 template<class Var>
01205 bool
01206 VarArgArray<Var>::same(const Space& home) const {
01207 if (n < 2)
01208 return false;
01209 Region r(home);
01210 Var* y = r.alloc<Var>(n);
01211 for (int i = n; i--; )
01212 y[i] = a[i];
01213 VarLess vl;
01214 Support::quicksort<Var,VarLess>(y,n,vl);
01215 for (int i = n-1; i--; )
01216 if (!y[i].assigned() && (y[i+1].var() == y[i].var())) {
01217 r.free<Var>(y,n);
01218 return true;
01219 }
01220 r.free<Var>(y,n);
01221 return false;
01222 }
01223
01224 template<class Var>
01225 bool
01226 VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const {
01227 int m = n + y.n;
01228 if (m < 2)
01229 return false;
01230 Region r(home);
01231 Var* z = r.alloc<Var>(m);
01232 for (int i = n; i--; )
01233 z[i] = a[i];
01234 for (int i = y.n; i--; )
01235 z[i+n] = y.a[i];
01236 VarLess vl;
01237 Support::quicksort<Var,VarLess>(z,m,vl);
01238 for (int i = m-1; i--; )
01239 if (!z[i].assigned() && (z[i+1].var() == z[i].var())) {
01240 r.free<Var>(z,m);
01241 return true;
01242 }
01243 r.free<Var>(z,m);
01244 return false;
01245 }
01246
01247 template<class Var>
01248 bool
01249 VarArgArray<Var>::same(const Space&, const Var& y) const {
01250 if (y.assigned())
01251 return false;
01252 for (int i = n; i--; )
01253 if (a[i].var() == y.var())
01254 return true;
01255 return false;
01256 }
01257
01258
01259
01260
01261
01262
01263
01264
01265
01266
01267
01268 template<class Var>
01269 inline
01270 VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a)
01271 : n(a.size()), capacity(a.size()) {
01272 if (capacity>0) {
01273 x = home.alloc<Var>(capacity);
01274 for (int i = capacity; i--; )
01275 x[i] = a[i];
01276 } else {
01277 x = NULL;
01278 }
01279 }
01280
01281
01282
01283
01284
01285
01286 template<class Char, class Traits, class Var>
01287 std::basic_ostream<Char,Traits>&
01288 operator <<(std::basic_ostream<Char,Traits>& os,
01289 const VarArray<Var>& x) {
01290 std::basic_ostringstream<Char,Traits> s;
01291 s.copyfmt(os); s.width(0);
01292 s << '{';
01293 if (x.size() > 0) {
01294 s << x[0];
01295 for (int i=1; i<x.size(); i++)
01296 s << ", " << x[i];
01297 }
01298 s << '}';
01299 return os << s.str();
01300 }
01301
01302 template<class Char, class Traits, class View>
01303 std::basic_ostream<Char,Traits>&
01304 operator <<(std::basic_ostream<Char,Traits>& os,
01305 const ViewArray<View>& x) {
01306 std::basic_ostringstream<Char,Traits> s;
01307 s.copyfmt(os); s.width(0);
01308 s << '{';
01309 if (x.size() > 0) {
01310 s << x[0];
01311 for (int i=1; i<x.size(); i++)
01312 s << ", " << x[i];
01313 }
01314 s << '}';
01315 return os << s.str();
01316 }
01317
01318 template<class Char, class Traits, class T>
01319 std::basic_ostream<Char,Traits>&
01320 operator <<(std::basic_ostream<Char,Traits>& os,
01321 const ArgArrayBase<T>& x) {
01322 std::basic_ostringstream<Char,Traits> s;
01323 s.copyfmt(os); s.width(0);
01324 s << '{';
01325 if (x.size() > 0) {
01326 s << x[0];
01327 for (int i=1; i<x.size(); i++)
01328 s << ", " << x[i];
01329 }
01330 s << '}';
01331 return os << s.str();
01332 }
01333
01334 }
01335
01336