array.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * 00007 * Copyright: 00008 * Christian Schulte, 2003 00009 * Guido Tack, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-06-03 13:46:55 +0200 (Thu, 03 Jun 2010) $ by $Author: schulte $ 00013 * $Revision: 11014 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 00061 template<class A> 00062 class ArrayTraits {}; 00063 00079 template<class Var> 00080 class VarArray { 00081 protected: 00083 int n; 00085 Var* x; 00086 public: 00088 00089 00090 VarArray(void); 00092 VarArray(Space& home, int m); 00094 VarArray(Space& home, const VarArgArray<Var>&); 00096 VarArray(const VarArray<Var>& a); 00098 const VarArray<Var>& operator =(const VarArray<Var>& a); 00100 00102 00103 00104 int size(void) const; 00106 00108 00109 00110 Var& operator [](int i); 00112 const Var& operator [](int i) const; 00118 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00119 slice(int start, int inc=1, int n=-1); 00121 00123 bool assigned(void) const; 00124 00126 00127 00134 void update(Space&, bool share, VarArray<Var>& a); 00136 private: 00137 static void* operator new(size_t); 00138 static void operator delete(void*,size_t); 00139 }; 00140 00144 template<class T> 00145 typename ArrayTraits<VarArray<T> >::ArgsType 00146 operator +(const VarArray<T>& x, const VarArgArray<T>& y); 00147 00151 template<class T> 00152 typename ArrayTraits<VarArray<T> >::ArgsType 00153 operator +(const VarArray<T>& x, const VarArray<T>& y); 00154 00158 template<class T> 00159 typename ArrayTraits<VarArray<T> >::ArgsType 00160 operator +(const VarArgArray<T>& x, const VarArray<T>& y); 00161 00165 template<class T> 00166 typename ArrayTraits<VarArray<T> >::ArgsType 00167 operator +(const VarArray<T>& x, const T& y); 00168 00172 template<class T> 00173 typename ArrayTraits<VarArray<T> >::ArgsType 00174 operator +(const T& x, const VarArray<T>& y); 00175 00184 template<class View> 00185 class ViewArray { 00186 private: 00188 int n; 00190 View* x; 00192 template<class X> 00193 class ViewLess { 00194 public: 00195 bool operator ()(const X&, const X&); 00196 }; 00198 static void sort(View* x, int n); 00199 public: 00201 00202 00203 ViewArray(void); 00205 ViewArray(Space& home, int m); 00207 ViewArray(const ViewArray<View>& a); 00209 ViewArray(Space& home, const ViewArray<View>& a); 00211 const ViewArray<View>& operator =(const ViewArray<View>& a); 00218 template<class Var> 00219 ViewArray(Space& home, const VarArgArray<Var>& a) 00220 : n(a.size()) { 00221 // This may not be in the hpp file (to satisfy the MS compiler) 00222 if (n>0) { 00223 x = home.alloc<View>(n); 00224 for (int i=n; i--; ) 00225 x[i]=a[i]; 00226 } else { 00227 x = NULL; 00228 } 00229 } 00231 00233 00234 00235 int size(void) const; 00237 void size(int n); 00239 00241 00242 00243 View& operator [](int i); 00245 const View& operator [](int i) const; 00247 00249 00250 00257 void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true); 00259 void cancel(Space& home, Propagator& p, PropCond pc); 00261 void subscribe(Space& home, Advisor& a); 00263 void cancel(Space& home, Advisor& a); 00265 00267 00268 00275 void update(Space&, bool share, ViewArray<View>& a); 00277 00278 00280 00281 00282 void move_fst(int i); 00284 void move_lst(int i); 00290 void move_fst(int i, Space& home, Propagator& p, PropCond pc); 00296 void move_lst(int i, Space& home, Propagator& p, PropCond pc); 00302 void move_fst(int i, Space& home, Advisor& a); 00308 void move_lst(int i, Space& home, Advisor& a); 00310 00312 00313 00314 void drop_fst(int i); 00316 void drop_lst(int i); 00322 void drop_fst(int i, Space& home, Propagator& p, PropCond pc); 00329 void drop_lst(int i, Space& home, Propagator& p, PropCond pc); 00335 void drop_fst(int i, Space& home, Advisor& a); 00341 void drop_lst(int i, Space& home, Advisor& a); 00343 00345 bool assigned(void) const; 00346 00348 00349 00354 bool same(const Space& home) const; 00360 bool same(const Space& home, const View& y) const; 00362 void unique(const Space& home); 00364 00366 00367 00372 bool shared(const Space& home) const; 00378 template<class ViewY> 00379 bool shared(const Space& home, const ViewY& y) const; 00385 template<class ViewY> 00386 bool shared(const Space& home, const ViewArray<ViewY>& y) const; 00388 00389 private: 00390 static void* operator new(size_t); 00391 static void operator delete(void*,size_t); 00392 }; 00393 00407 template<class T> 00408 class ArgArrayBase { 00409 protected: 00411 int n; 00413 int capacity; 00415 T* a; 00417 static const int onstack_size = 16; 00419 T onstack[onstack_size]; 00421 T* allocate(int n); 00423 void resize(int i); 00425 template<class A> 00426 A concat(const ArgArrayBase<T>& x) const; 00428 template<class A> 00429 A concat(const T& x) const; 00431 template<class A> 00432 A& append(const T& x); 00434 template<class A> 00435 A& append(const ArgArrayBase<T>& x); 00441 template<class A> 00442 A slice(int start, int inc=1, int n=-1); 00443 public: 00445 00446 00447 ArgArrayBase(void); 00449 explicit ArgArrayBase(int n); 00451 ArgArrayBase(const ArgArrayBase<T>& a); 00453 const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a); 00455 00457 00458 00459 int size(void) const; 00461 00463 00464 00465 T& operator [](int i); 00467 const T& operator [](int i) const; 00469 00471 00472 00473 ~ArgArrayBase(void); 00475 private: 00476 static void* operator new(size_t); 00477 static void operator delete(void*,size_t); 00478 }; 00479 00480 template<class> class PrimArgArray; 00481 00485 template<class T> 00486 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00487 operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y); 00488 00492 template<class T> 00493 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00494 operator +(const PrimArgArray<T>& x, const T& y); 00495 00499 template<class T> 00500 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00501 operator +(const T& x, const PrimArgArray<T>& y); 00502 00514 template<class T> 00515 class PrimArgArray : public ArgArrayBase<T> { 00516 protected: 00517 using ArgArrayBase<T>::a; 00518 public: 00519 using ArgArrayBase<T>::size; 00521 00522 00523 PrimArgArray(void); 00525 explicit PrimArgArray(int n); 00527 PrimArgArray(int n, T e0, ...); 00529 PrimArgArray(int n, const T* e); 00531 PrimArgArray(const PrimArgArray<T>& a); 00533 00534 00535 00540 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00541 slice(int start, int inc=1, int n=-1); 00543 00544 00545 00546 typename ArrayTraits<PrimArgArray<T> >::ArgsType& 00547 operator <<(const T& x); 00549 typename ArrayTraits<PrimArgArray<T> >::ArgsType& 00550 operator <<(const PrimArgArray<T>& x); 00552 00553 friend typename ArrayTraits<PrimArgArray<T> >::ArgsType 00554 operator + <>(const PrimArgArray<T>& x, const PrimArgArray<T>& y); 00555 friend typename ArrayTraits<PrimArgArray<T> >::ArgsType 00556 operator + <>(const PrimArgArray<T>& x, const T& y); 00557 friend 00558 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00559 operator + <>(const T& x, const PrimArgArray<T>& y); 00560 }; 00561 00562 template<class> class ArgArray; 00563 00567 template<class T> 00568 typename ArrayTraits<ArgArray<T> >::ArgsType 00569 operator +(const ArgArray<T>& x, const ArgArray<T>& y); 00570 00574 template<class T> 00575 typename ArrayTraits<ArgArray<T> >::ArgsType 00576 operator +(const ArgArray<T>& x, const T& y); 00577 00581 template<class T> 00582 typename ArrayTraits<ArgArray<T> >::ArgsType 00583 operator +(const T& x, const ArgArray<T>& y); 00584 00596 template<class T> 00597 class ArgArray : public ArgArrayBase<T> { 00598 protected: 00599 using ArgArrayBase<T>::a; 00600 public: 00601 using ArgArrayBase<T>::size; 00603 00604 00605 ArgArray(void); 00607 explicit ArgArray(int n); 00609 ArgArray(int n, const T* e); 00611 ArgArray(const ArgArray<T>& a); 00613 00614 00615 00616 typename ArrayTraits<ArgArray<T> >::ArgsType 00617 slice(int start, int inc=1, int n=-1); 00619 00620 00621 00622 typename ArrayTraits<ArgArray<T> >::ArgsType& 00623 operator <<(const T& x); 00625 typename ArrayTraits<ArgArray<T> >::ArgsType& 00626 operator <<(const ArgArray<T>& x); 00628 00629 friend typename ArrayTraits<ArgArray<T> >::ArgsType 00630 operator + <>(const ArgArray<T>& x, const ArgArray<T>& y); 00631 friend typename ArrayTraits<ArgArray<T> >::ArgsType 00632 operator + <>(const ArgArray<T>& x, const T& y); 00633 friend 00634 typename ArrayTraits<ArgArray<T> >::ArgsType 00635 operator + <>(const T& x, const ArgArray<T>& y); 00636 }; 00637 00638 template<class> class VarArgArray; 00639 00643 template<class Var> 00644 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00645 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y); 00646 00650 template<class Var> 00651 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00652 operator +(const VarArgArray<Var>& x, const Var& y); 00653 00657 template<class Var> 00658 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00659 operator +(const Var& x, const VarArgArray<Var>& y); 00660 00672 template<class Var> 00673 class VarArgArray : public ArgArrayBase<Var> { 00674 protected: 00675 using ArgArrayBase<Var>::a; 00676 using ArgArrayBase<Var>::n; 00678 class VarLess { 00679 public: 00680 bool operator ()(const Var&, const Var&); 00681 }; 00682 public: 00683 using ArgArrayBase<Var>::size; 00685 00686 00687 VarArgArray(void); 00689 explicit VarArgArray(int n); 00691 VarArgArray(const VarArgArray<Var>& a); 00693 VarArgArray(const VarArray<Var>& a); 00695 00696 00697 00698 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00699 slice(int start, int inc=1, int n=-1); 00701 00702 00703 00704 typename ArrayTraits<VarArgArray<Var> >::ArgsType& 00705 operator <<(const Var& x); 00707 typename ArrayTraits<VarArgArray<Var> >::ArgsType& 00708 operator <<(const VarArgArray<Var>& x); 00710 00712 bool assigned(void) const; 00713 00714 friend typename ArrayTraits<VarArgArray<Var> >::ArgsType 00715 operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y); 00716 friend typename ArrayTraits<VarArgArray<Var> >::ArgsType 00717 operator + <>(const VarArgArray<Var>& x, const Var& y); 00718 friend 00719 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00720 operator + <>(const Var& x, const VarArgArray<Var>& y); 00721 00723 00724 00729 bool same(const Space& home) const; 00735 bool same(const Space& home, const Var& y) const; 00741 bool same(const Space& home, const VarArgArray<Var>& y) const; 00743 }; 00744 00749 template<class Char, class Traits, class Var> 00750 std::basic_ostream<Char,Traits>& 00751 operator <<(std::basic_ostream<Char,Traits>& os, 00752 const VarArray<Var>& x); 00753 00758 template<class Char, class Traits, class View> 00759 std::basic_ostream<Char,Traits>& 00760 operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x); 00761 00766 template<class Char, class Traits, class T> 00767 std::basic_ostream<Char,Traits>& 00768 operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x); 00769 00770 00771 /* 00772 * Implementation 00773 * 00774 */ 00775 00776 /* 00777 * Variable arrays 00778 * 00779 * These arrays are usually allocated in the space, but if they are resized, 00780 * the new array is allocated on the heap. The size (n) and capacity show 00781 * where the array is allocated: it is in the space if and only if 00782 * n==capacity. 00783 * 00784 */ 00785 00786 template<class Var> 00787 forceinline 00788 VarArray<Var>::VarArray(void) : n(0), x(NULL) {} 00789 00790 template<class Var> 00791 forceinline 00792 VarArray<Var>::VarArray(Space& home, int n0) 00793 : n(n0) { 00794 // Allocate from space 00795 x = (n>0) ? home.alloc<Var>(n) : NULL; 00796 } 00797 00798 template<class Var> 00799 forceinline 00800 VarArray<Var>::VarArray(const VarArray<Var>& a) { 00801 n = a.n; x = a.x; 00802 } 00803 00804 template<class Var> 00805 inline const VarArray<Var>& 00806 VarArray<Var>::operator =(const VarArray<Var>& a) { 00807 n = a.n; x = a.x; 00808 return *this; 00809 } 00810 00811 template<class Var> 00812 forceinline int 00813 VarArray<Var>::size(void) const { 00814 return n; 00815 } 00816 00817 template<class Var> 00818 forceinline Var& 00819 VarArray<Var>::operator [](int i) { 00820 assert((i >= 0) && (i < size())); 00821 return x[i]; 00822 } 00823 00824 template<class Var> 00825 forceinline const Var& 00826 VarArray<Var>::operator [](int i) const { 00827 assert((i >= 0) && (i < size())); 00828 return x[i]; 00829 } 00830 00831 template<class Var> 00832 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00833 VarArray<Var>::slice(int start, int inc, int maxN) { 00834 assert(start < n); 00835 if (maxN<0) 00836 maxN = n; 00837 int s; 00838 if (inc == 0) 00839 s = n-start; 00840 else if (inc > 0) 00841 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); 00842 else 00843 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); 00844 typename ArrayTraits<VarArgArray<Var> >::ArgsType r(std::min(maxN,s)); 00845 for (int i=0; i<r.size(); i++, start+=inc) 00846 r[i] = x[start]; 00847 return r; 00848 } 00849 00850 template<class Var> 00851 forceinline void 00852 VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) { 00853 n = a.n; 00854 if (n > 0) { 00855 x = home.alloc<Var>(n); 00856 for (int i = n; i--;) 00857 x[i].update(home, share, a.x[i]); 00858 } else { 00859 x = NULL; 00860 } 00861 } 00862 00863 template<class Var> 00864 forceinline bool 00865 VarArray<Var>::assigned(void) const { 00866 for (int i = n; i--;) 00867 if (!x[i].assigned()) 00868 return false; 00869 return true; 00870 } 00871 00872 template<class Var> 00873 void* 00874 VarArray<Var>::operator new(size_t) { 00875 return NULL; 00876 } 00877 00878 template<class Var> 00879 void 00880 VarArray<Var>::operator delete(void*,size_t) { 00881 } 00882 00883 template<class Var> 00884 typename ArrayTraits<VarArray<Var> >::ArgsType 00885 operator +(const VarArray<Var>& x, const VarArray<Var>& y) { 00886 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 00887 for (int i=x.size(); i--;) 00888 r[i] = x[i]; 00889 for (int i=y.size(); i--;) 00890 r[x.size()+i] = y[i]; 00891 return r; 00892 } 00893 00894 template<class Var> 00895 typename ArrayTraits<VarArray<Var> >::ArgsType 00896 operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) { 00897 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 00898 for (int i=x.size(); i--;) 00899 r[i] = x[i]; 00900 for (int i=y.size(); i--;) 00901 r[x.size()+i] = y[i]; 00902 return r; 00903 } 00904 00905 template<class Var> 00906 typename ArrayTraits<VarArray<Var> >::ArgsType 00907 operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) { 00908 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 00909 for (int i=x.size(); i--;) 00910 r[i] = x[i]; 00911 for (int i=y.size(); i--;) 00912 r[x.size()+i] = y[i]; 00913 return r; 00914 } 00915 00916 template<class Var> 00917 typename ArrayTraits<VarArray<Var> >::ArgsType 00918 operator +(const VarArray<Var>& x, const Var& y) { 00919 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+1); 00920 for (int i=x.size(); i--;) 00921 r[i] = x[i]; 00922 r[x.size()] = y; 00923 return r; 00924 } 00925 00926 template<class Var> 00927 typename ArrayTraits<VarArray<Var> >::ArgsType 00928 operator +(const Var& x, const VarArray<Var>& y) { 00929 typename ArrayTraits<VarArray<Var> >::ArgsType r(y.size()+1); 00930 r[0] = x; 00931 for (int i=y.size(); i--;) 00932 r[1+i] = y[i]; 00933 return r; 00934 } 00935 00936 /* 00937 * View arrays 00938 * 00939 */ 00940 00941 template<class View> 00942 forceinline 00943 ViewArray<View>::ViewArray(void) : n(0), x(NULL) {} 00944 00945 template<class View> 00946 forceinline 00947 ViewArray<View>::ViewArray(Space& home, int n0) 00948 : n(n0) { 00949 x = (n>0) ? home.alloc<View>(n) : NULL; 00950 } 00951 00952 template<class View> 00953 ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a) 00954 : n(a.size()) { 00955 if (n>0) { 00956 x = home.alloc<View>(n); 00957 for (int i = n; i--; ) 00958 x[i] = a[i]; 00959 } else { 00960 x = NULL; 00961 } 00962 } 00963 00964 template<class View> 00965 forceinline 00966 ViewArray<View>::ViewArray(const ViewArray<View>& a) 00967 : n(a.n), x(a.x) {} 00968 00969 template<class View> 00970 forceinline const ViewArray<View>& 00971 ViewArray<View>::operator =(const ViewArray<View>& a) { 00972 n = a.n; x = a.x; 00973 return *this; 00974 } 00975 00976 template<class View> 00977 forceinline int 00978 ViewArray<View>::size(void) const { 00979 return n; 00980 } 00981 00982 template<class View> 00983 forceinline void 00984 ViewArray<View>::size(int n0) { 00985 n = n0; 00986 } 00987 00988 template<class View> 00989 forceinline View& 00990 ViewArray<View>::operator [](int i) { 00991 assert((i >= 0) && (i < size())); 00992 return x[i]; 00993 } 00994 00995 template<class View> 00996 forceinline const View& 00997 ViewArray<View>::operator [](int i) const { 00998 assert((i >= 0) && (i < size())); 00999 return x[i]; 01000 } 01001 01002 template<class View> 01003 forceinline void 01004 ViewArray<View>::move_fst(int i) { 01005 x[i]=x[0]; x++; n--; 01006 } 01007 01008 template<class View> 01009 forceinline void 01010 ViewArray<View>::move_lst(int i) { 01011 n--; x[i]=x[n]; 01012 } 01013 01014 template<class View> 01015 forceinline void 01016 ViewArray<View>::drop_fst(int i) { 01017 assert(i>=0); 01018 x += i; n -= i; 01019 } 01020 01021 template<class View> 01022 forceinline void 01023 ViewArray<View>::drop_lst(int i) { 01024 assert(i<n); 01025 n = i+1; 01026 } 01027 01028 template<class View> 01029 forceinline void 01030 ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) { 01031 // Move x[0] to x[i] 01032 x[i].cancel(home,p,pc); 01033 x[i]=x[0]; x++; n--; 01034 } 01035 01036 template<class View> 01037 forceinline void 01038 ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) { 01039 // Move x[n-1] to x[i] 01040 x[i].cancel(home,p,pc); 01041 n--; x[i]=x[n]; 01042 } 01043 01044 template<class View> 01045 void 01046 ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) { 01047 // Drop elements from 0..i-1 01048 assert(i>=0); 01049 for (int j=i; j--; ) 01050 x[j].cancel(home,p,pc); 01051 x += i; n -= i; 01052 } 01053 01054 template<class View> 01055 void 01056 ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) { 01057 // Drop elements from i+1..n-1 01058 assert(i<n); 01059 for (int j=i+1; j<n; j++) 01060 x[j].cancel(home,p,pc); 01061 n = i+1; 01062 } 01063 01064 template<class View> 01065 forceinline void 01066 ViewArray<View>::move_fst(int i, Space& home, Advisor& a) { 01067 // Move x[0] to x[i] 01068 x[i].cancel(home,a); 01069 x[i]=x[0]; x++; n--; 01070 } 01071 01072 template<class View> 01073 forceinline void 01074 ViewArray<View>::move_lst(int i, Space& home, Advisor& a) { 01075 // Move x[n-1] to x[i] 01076 x[i].cancel(home,a); 01077 n--; x[i]=x[n]; 01078 } 01079 01080 template<class View> 01081 void 01082 ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) { 01083 // Drop elements from 0..i-1 01084 assert(i>=0); 01085 for (int j=i; j--; ) 01086 x[j].cancel(home,a); 01087 x += i; n -= i; 01088 } 01089 01090 template<class View> 01091 void 01092 ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) { 01093 // Drop elements from i+1..n-1 01094 assert(i<n); 01095 for (int j=i+1; j<n; j++) 01096 x[j].cancel(home,a); 01097 n = i+1; 01098 } 01099 01100 template<class View> 01101 void 01102 ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) { 01103 n = y.n; 01104 if (n > 0) { 01105 x = home.alloc<View>(n); 01106 for (int i = n; i--; ) 01107 x[i].update(home, share, y.x[i]); 01108 } else { 01109 x = NULL; 01110 } 01111 } 01112 01113 template<class View> 01114 void 01115 ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc, 01116 bool process) { 01117 for (int i = n; i--; ) 01118 x[i].subscribe(home,p,pc,process); 01119 } 01120 01121 template<class View> 01122 void 01123 ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) { 01124 for (int i = n; i--; ) 01125 x[i].cancel(home,p,pc); 01126 } 01127 01128 template<class View> 01129 void 01130 ViewArray<View>::subscribe(Space& home, Advisor& a) { 01131 for (int i = n; i--; ) 01132 x[i].subscribe(home,a); 01133 } 01134 01135 template<class View> 01136 void 01137 ViewArray<View>::cancel(Space& home, Advisor& a) { 01138 for (int i = n; i--; ) 01139 x[i].cancel(home,a); 01140 } 01141 01142 template<class View> 01143 forceinline bool 01144 ViewArray<View>::assigned(void) const { 01145 for (int i = n; i--;) 01146 if (!x[i].assigned()) 01147 return false; 01148 return true; 01149 } 01150 01151 template<class View> 01152 forceinline bool 01153 __before(const View& x, const View& y) { 01154 return before(x,y); 01155 } 01156 01157 template<class View> template<class X> 01158 forceinline bool 01159 ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) { 01160 return __before(a,b); 01161 } 01162 01163 template<class View> 01164 void 01165 ViewArray<View>::sort(View* y, int m) { 01166 ViewLess<View> vl; 01167 Support::quicksort<View,ViewLess<View> >(y,m,vl); 01168 } 01169 01170 template<class X, class Y> 01171 forceinline bool 01172 __same(const X& x, const Y& y) { 01173 return same(x,y); 01174 } 01175 template<class X, class Y> 01176 forceinline bool 01177 __shared(const X& x, const Y& y) { 01178 return shared(x,y); 01179 } 01180 01181 template<class View> 01182 bool 01183 ViewArray<View>::same(const Space& home) const { 01184 if (n < 2) 01185 return false; 01186 Region r(home); 01187 View* y = r.alloc<View>(n); 01188 for (int i = n; i--; ) 01189 y[i] = x[i]; 01190 sort(y,n); 01191 for (int i = n-1; i--; ) 01192 if (!y[i].assigned() && __same(y[i+1],y[i])) { 01193 r.free<View>(y,n); 01194 return true; 01195 } 01196 r.free<View>(y,n); 01197 return false; 01198 } 01199 01200 template<class View> 01201 bool 01202 ViewArray<View>::same(const Space&, const View& y) const { 01203 if (y.assigned()) 01204 return false; 01205 for (int i = n; i--; ) 01206 if (__same(x[i],y)) 01207 return true; 01208 return false; 01209 } 01210 01211 template<class View> 01212 void 01213 ViewArray<View>::unique(const Space&) { 01214 if (n < 2) 01215 return; 01216 sort(x,n); 01217 int j = 0; 01218 for (int i = 1; i<n; i++) 01219 if (!__same(x[j],x[i])) 01220 x[++j] = x[i]; 01221 n = j+1; 01222 } 01223 01224 template<class View> 01225 bool 01226 ViewArray<View>::shared(const Space& home) const { 01227 if (n < 2) 01228 return false; 01229 Region r(home); 01230 View* y = r.alloc<View>(n); 01231 for (int i = n; i--; ) 01232 y[i] = x[i]; 01233 sort(y,n); 01234 for (int i = n-1; i--; ) 01235 if (!y[i].assigned() && __shared(y[i+1],y[i])) { 01236 r.free<View>(y,n); 01237 return true; 01238 } 01239 r.free<View>(y,n); 01240 return false; 01241 } 01242 01243 template<class View> template<class ViewY> 01244 bool 01245 ViewArray<View>::shared(const Space&, const ViewY& y) const { 01246 if (y.assigned()) 01247 return false; 01248 for (int i = n; i--; ) 01249 if (!x[i].assigned() && __shared(x[i],y)) 01250 return true; 01251 return false; 01252 } 01253 01254 template<class View> template<class ViewY> 01255 bool 01256 ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const { 01257 if ((size() < 1) || (y.size() < 1)) 01258 return false; 01259 Region r(home); 01260 View* xs = r.alloc<View>(size()); 01261 for (int i=size(); i--; ) 01262 xs[i] = x[i]; 01263 ViewLess<View> xvl; 01264 Support::quicksort<View,ViewLess<View> >(xs,size(),xvl); 01265 ViewY* ys = r.alloc<ViewY>(y.size()); 01266 for (int j=y.size(); j--; ) 01267 ys[j] = y[j]; 01268 ViewLess<ViewY> yvl; 01269 Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl); 01270 { 01271 int i=0, j=0; 01272 while ((i < size()) && (j < y.size())) 01273 if (!x[i].assigned() && __shared(x[i],y[j])) { 01274 r.free<View>(xs,size()); 01275 r.free<ViewY>(ys,y.size()); 01276 return true; 01277 } else if (before(x[i],y[j])) { 01278 i++; 01279 } else { 01280 j++; 01281 } 01282 } 01283 r.free<View>(xs,size()); 01284 r.free<ViewY>(ys,y.size()); 01285 return false; 01286 } 01287 01288 template<class View> 01289 void* 01290 ViewArray<View>::operator new(size_t) { 01291 return NULL; 01292 } 01293 01294 template<class View> 01295 void 01296 ViewArray<View>::operator delete(void*,size_t) { 01297 } 01298 01299 01300 /* 01301 * Argument arrays: base class 01302 * 01303 */ 01304 01305 template<class T> 01306 forceinline T* 01307 ArgArrayBase<T>::allocate(int n) { 01308 return (n > onstack_size) ? 01309 heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0]; 01310 } 01311 01312 template<class T> 01313 forceinline void 01314 ArgArrayBase<T>::resize(int i) { 01315 if (n+i >= capacity) { 01316 assert(n+i >= onstack_size); 01317 int newCapacity = (3*capacity)/2; 01318 if (newCapacity <= n+i) 01319 newCapacity = n+i; 01320 T* newA = allocate(newCapacity); 01321 heap.copy<T>(newA,a,n); 01322 if (capacity > onstack_size) 01323 heap.free(a,capacity); 01324 capacity = newCapacity; 01325 a = newA; 01326 } 01327 } 01328 01329 template<class T> 01330 forceinline 01331 ArgArrayBase<T>::ArgArrayBase(void) 01332 : n(0), capacity(onstack_size), a(allocate(0)) {} 01333 01334 template<class T> 01335 forceinline 01336 ArgArrayBase<T>::ArgArrayBase(int n0) 01337 : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {} 01338 01339 template<class T> 01340 inline 01341 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa) 01342 : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) { 01343 heap.copy<T>(a,aa.a,n); 01344 } 01345 01346 template<class T> 01347 forceinline 01348 ArgArrayBase<T>::~ArgArrayBase(void) { 01349 if (capacity > onstack_size) 01350 heap.free(a,capacity); 01351 } 01352 01353 template<class T> 01354 forceinline const ArgArrayBase<T>& 01355 ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) { 01356 if (&aa != this) { 01357 if (capacity > onstack_size) 01358 heap.free(a,capacity); 01359 n = aa.n; 01360 capacity = (n < onstack_size ? onstack_size : n); 01361 a = allocate(aa.n); 01362 heap.copy<T>(a,aa.a,n); 01363 } 01364 return *this; 01365 } 01366 01367 template<class T> 01368 forceinline int 01369 ArgArrayBase<T>::size(void) const { 01370 return n; 01371 } 01372 01373 template<class T> 01374 forceinline T& 01375 ArgArrayBase<T>::operator [](int i) { 01376 assert((i>=0) && (i < n)); 01377 return a[i]; 01378 } 01379 01380 template<class T> 01381 forceinline const T& 01382 ArgArrayBase<T>::operator [](int i) const { 01383 assert((i>=0) && (i < n)); 01384 return a[i]; 01385 } 01386 01387 template<class T> template<class A> 01388 A 01389 ArgArrayBase<T>::slice(int start, int inc, int maxN) { 01390 assert(start < n); 01391 if (maxN<0) 01392 maxN = n; 01393 int s; 01394 if (inc == 0) 01395 s = n-start; 01396 else if (inc > 0) 01397 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); 01398 else 01399 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); 01400 A r(std::min(maxN,s)); 01401 for (int i=0; i<r.size(); i++, start+=inc) 01402 new (&r[i]) T(a[start]); 01403 return r; 01404 } 01405 01406 template<class T> template<class A> 01407 inline A& 01408 ArgArrayBase<T>::append(const T& x) { 01409 resize(1); 01410 new (&a[n++]) T(x); 01411 return static_cast<A&>(*this); 01412 } 01413 01414 template<class T> template<class A> 01415 inline A& 01416 ArgArrayBase<T>::append(const ArgArrayBase<T>& x) { 01417 resize(x.size()); 01418 for (int i=0; i<x.size(); i++) 01419 new (&a[n++]) T(x[i]); 01420 return static_cast<A&>(*this); 01421 } 01422 01423 template<class T> template<class A> 01424 inline A 01425 ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const { 01426 A r(n+x.n); 01427 for (int i=n; i--;) 01428 new (&r[i]) T(a[i]); 01429 for (int i=x.n; i--;) 01430 new (&r[n+i]) T(x.a[i]); 01431 return r; 01432 } 01433 01434 template<class T> template<class A> 01435 inline A 01436 ArgArrayBase<T>::concat(const T& x) const { 01437 A r(n+1); 01438 for (int i=n; i--;) 01439 new (&r[i]) T(a[i]); 01440 new (&r[n]) T(x); 01441 return r; 01442 } 01443 01444 /* 01445 * Argument arrays for primitive types 01446 * 01447 */ 01448 01449 template<class T> 01450 forceinline 01451 PrimArgArray<T>::PrimArgArray(void) {} 01452 01453 template<class T> 01454 forceinline 01455 PrimArgArray<T>::PrimArgArray(int n) : ArgArrayBase<T>(n) {} 01456 01457 template<class T> 01458 PrimArgArray<T>::PrimArgArray(int n, T a0, ...) 01459 : ArgArrayBase<T>(n) { 01460 va_list args; 01461 va_start(args, a0); 01462 a[0] = a0; 01463 for (int i = 1; i < n; i++) 01464 a[i] = va_arg(args,T); 01465 va_end(args); 01466 } 01467 01468 template<class T> 01469 PrimArgArray<T>::PrimArgArray(int n, const T* a0) 01470 : ArgArrayBase<T>(n) { 01471 for (int i=n; i--; ) 01472 a[i] = a0[i]; 01473 } 01474 01475 template<class T> 01476 forceinline 01477 PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa) 01478 : ArgArrayBase<T>(aa) {} 01479 01480 template<class T> 01481 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType 01482 PrimArgArray<T>::slice(int start, int inc, int maxN) { 01483 return ArgArrayBase<T>::template slice 01484 <typename ArrayTraits<PrimArgArray<T> >::ArgsType> 01485 (start,inc,maxN); 01486 } 01487 01488 template<class T> 01489 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType& 01490 PrimArgArray<T>::operator <<(const T& x) { 01491 return 01492 ArgArrayBase<T>::template append 01493 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x); 01494 } 01495 01496 template<class T> 01497 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType& 01498 PrimArgArray<T>::operator <<(const PrimArgArray<T>& x) { 01499 return 01500 ArgArrayBase<T>::template append 01501 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x); 01502 } 01503 01504 template<class T> 01505 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01506 operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y) { 01507 return x.template concat 01508 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01509 } 01510 01511 template<class T> 01512 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01513 operator +(const PrimArgArray<T>& x, const T& y) { 01514 return x.template concat 01515 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01516 } 01517 01518 template<class T> 01519 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01520 operator +(const T& x, const PrimArgArray<T>& y) { 01521 return PrimArgArray<T>(1,x).template concat 01522 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01523 } 01524 01525 01526 /* 01527 * Argument arrays for non-primitive types 01528 * 01529 */ 01530 01531 template<class T> 01532 forceinline 01533 ArgArray<T>::ArgArray(void) {} 01534 01535 template<class T> 01536 forceinline 01537 ArgArray<T>::ArgArray(int n) : ArgArrayBase<T>(n) {} 01538 01539 template<class T> 01540 ArgArray<T>::ArgArray(int n, const T* a0) 01541 : ArgArrayBase<T>(n) { 01542 for (int i=n; i--; ) 01543 a[i] = a0[i]; 01544 } 01545 01546 template<class T> 01547 forceinline 01548 ArgArray<T>::ArgArray(const ArgArray<T>& aa) 01549 : ArgArrayBase<T>(aa) {} 01550 01551 template<class T> 01552 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType 01553 ArgArray<T>::slice(int start, int inc, int maxN) { 01554 return ArgArrayBase<T>::template slice 01555 <typename ArrayTraits<ArgArray<T> >::ArgsType> 01556 (start,inc,maxN); 01557 } 01558 01559 template<class T> 01560 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType& 01561 ArgArray<T>::operator <<(const T& x) { 01562 return 01563 ArgArrayBase<T>::template append 01564 <typename ArrayTraits<ArgArray<T> >::ArgsType>(x); 01565 } 01566 01567 template<class T> 01568 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType& 01569 ArgArray<T>::operator <<(const ArgArray<T>& x) { 01570 return 01571 ArgArrayBase<T>::template append 01572 <typename ArrayTraits<ArgArray<T> >::ArgsType>(x); 01573 } 01574 01575 template<class T> 01576 typename ArrayTraits<ArgArray<T> >::ArgsType 01577 operator +(const ArgArray<T>& x, const ArgArray<T>& y) { 01578 return x.template concat 01579 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01580 } 01581 01582 template<class T> 01583 typename ArrayTraits<ArgArray<T> >::ArgsType 01584 operator +(const ArgArray<T>& x, const T& y) { 01585 return x.template concat 01586 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01587 } 01588 01589 template<class T> 01590 typename ArrayTraits<ArgArray<T> >::ArgsType 01591 operator +(const T& x, const ArgArray<T>& y) { 01592 ArgArray<T> xa(1); 01593 xa[0] = x; 01594 return xa.template concat 01595 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01596 } 01597 01598 /* 01599 * Argument arrays for variables 01600 * 01601 */ 01602 01603 template<class Var> 01604 forceinline 01605 VarArgArray<Var>::VarArgArray(void) {} 01606 01607 template<class Var> 01608 forceinline 01609 VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {} 01610 01611 template<class Var> 01612 forceinline 01613 VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa) 01614 : ArgArrayBase<Var>(aa) {} 01615 01616 template<class Var> 01617 inline 01618 VarArgArray<Var>::VarArgArray(const VarArray<Var>& x) 01619 : ArgArrayBase<Var>(x.size()) { 01620 for (int i=x.size(); i--; ) 01621 a[i]=x[i]; 01622 } 01623 01624 template<class Var> 01625 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType 01626 VarArgArray<Var>::slice(int start, int inc, int maxN) { 01627 return ArgArrayBase<Var>::template slice 01628 <typename ArrayTraits<VarArgArray<Var> >::ArgsType> 01629 (start,inc,maxN); 01630 } 01631 01632 template<class Var> 01633 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType& 01634 VarArgArray<Var>::operator <<(const Var& x) { 01635 return 01636 ArgArrayBase<Var>::template append 01637 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x); 01638 } 01639 01640 template<class Var> 01641 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType& 01642 VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) { 01643 return 01644 ArgArrayBase<Var>::template append 01645 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x); 01646 } 01647 01648 template<class Var> 01649 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01650 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) { 01651 return x.template concat 01652 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01653 } 01654 01655 template<class Var> 01656 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01657 operator +(const VarArgArray<Var>& x, const Var& y) { 01658 return x.template concat 01659 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01660 } 01661 01662 template<class Var> 01663 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01664 operator +(const Var& x, const VarArgArray<Var>& y) { 01665 VarArgArray<Var> xa(1); 01666 xa[0] = x; 01667 return xa.template concat 01668 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01669 } 01670 01671 template<class Var> 01672 forceinline bool 01673 VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) { 01674 return a.varimp() < b.varimp(); 01675 } 01676 01677 template<class Var> 01678 forceinline bool 01679 VarArgArray<Var>::assigned(void) const { 01680 for (int i = n; i--;) 01681 if (!a[i].assigned()) 01682 return false; 01683 return true; 01684 } 01685 01686 template<class Var> 01687 bool 01688 VarArgArray<Var>::same(const Space& home) const { 01689 if (n < 2) 01690 return false; 01691 Region r(home); 01692 Var* y = r.alloc<Var>(n); 01693 for (int i = n; i--; ) 01694 y[i] = a[i]; 01695 VarLess vl; 01696 Support::quicksort<Var,VarLess>(y,n,vl); 01697 for (int i = n-1; i--; ) 01698 if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) { 01699 r.free<Var>(y,n); 01700 return true; 01701 } 01702 r.free<Var>(y,n); 01703 return false; 01704 } 01705 01706 template<class Var> 01707 bool 01708 VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const { 01709 int m = n + y.n; 01710 if (m < 2) 01711 return false; 01712 Region r(home); 01713 Var* z = r.alloc<Var>(m); 01714 for (int i = n; i--; ) 01715 z[i] = a[i]; 01716 for (int i = y.n; i--; ) 01717 z[i+n] = y.a[i]; 01718 VarLess vl; 01719 Support::quicksort<Var,VarLess>(z,m,vl); 01720 for (int i = m-1; i--; ) 01721 if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) { 01722 r.free<Var>(z,m); 01723 return true; 01724 } 01725 r.free<Var>(z,m); 01726 return false; 01727 } 01728 01729 template<class Var> 01730 bool 01731 VarArgArray<Var>::same(const Space&, const Var& y) const { 01732 if (y.assigned()) 01733 return false; 01734 for (int i = n; i--; ) 01735 if (a[i].varimp() == y.varimp()) 01736 return true; 01737 return false; 01738 } 01739 01740 01741 01742 01743 01744 01745 /* 01746 * Interdependent code 01747 * 01748 */ 01749 01750 template<class Var> 01751 inline 01752 VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a) 01753 : n(a.size()) { 01754 if (n>0) { 01755 x = home.alloc<Var>(n); 01756 for (int i=n; i--;) 01757 x[i] = a[i]; 01758 } else { 01759 x = NULL; 01760 } 01761 } 01762 01763 01764 /* 01765 * Printing of arrays 01766 * 01767 */ 01768 template<class Char, class Traits, class Var> 01769 std::basic_ostream<Char,Traits>& 01770 operator <<(std::basic_ostream<Char,Traits>& os, 01771 const VarArray<Var>& x) { 01772 std::basic_ostringstream<Char,Traits> s; 01773 s.copyfmt(os); s.width(0); 01774 s << '{'; 01775 if (x.size() > 0) { 01776 s << x[0]; 01777 for (int i=1; i<x.size(); i++) 01778 s << ", " << x[i]; 01779 } 01780 s << '}'; 01781 return os << s.str(); 01782 } 01783 01784 template<class Char, class Traits, class View> 01785 std::basic_ostream<Char,Traits>& 01786 operator <<(std::basic_ostream<Char,Traits>& os, 01787 const ViewArray<View>& x) { 01788 std::basic_ostringstream<Char,Traits> s; 01789 s.copyfmt(os); s.width(0); 01790 s << '{'; 01791 if (x.size() > 0) { 01792 s << x[0]; 01793 for (int i=1; i<x.size(); i++) 01794 s << ", " << x[i]; 01795 } 01796 s << '}'; 01797 return os << s.str(); 01798 } 01799 01800 template<class Char, class Traits, class T> 01801 std::basic_ostream<Char,Traits>& 01802 operator <<(std::basic_ostream<Char,Traits>& os, 01803 const ArgArrayBase<T>& x) { 01804 std::basic_ostringstream<Char,Traits> s; 01805 s.copyfmt(os); s.width(0); 01806 s << '{'; 01807 if (x.size() > 0) { 01808 s << x[0]; 01809 for (int i=1; i<x.size(); i++) 01810 s << ", " << x[i]; 01811 } 01812 s << '}'; 01813 return os << s.str(); 01814 } 01815 01816 } 01817 01818 // STATISTICS: kernel-other