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 * Contributing authors: 00008 * Gregory Crosswhite <gcross@phys.washington.edu> 00009 * 00010 * Copyright: 00011 * Gregory Crosswhite, 2011 00012 * Christian Schulte, 2003 00013 * Guido Tack, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2011-01-27 13:03:05 +0100 (Thu, 27 Jan 2011) $ by $Author: schulte $ 00017 * $Revision: 11570 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 #include <cstdarg> 00045 #include <iostream> 00046 #include <iterator> 00047 #include <sstream> 00048 00049 namespace Gecode { 00050 00051 template<class Var> class VarArray; 00052 template<class Var> class VarArgArray; 00053 00066 template<class A> 00067 class ArrayTraits {}; 00068 00084 template<class Var> 00085 class VarArray { 00086 protected: 00088 int n; 00090 Var* x; 00091 public: 00093 00094 00095 typedef Var value_type; 00097 typedef Var& reference; 00099 typedef const Var& const_reference; 00101 typedef Var* pointer; 00103 typedef const Var* const_pointer; 00105 typedef Var* iterator; 00107 typedef const Var* const_iterator; 00109 typedef std::reverse_iterator<Var*> reverse_iterator; 00111 typedef std::reverse_iterator<const Var*> const_reverse_iterator; 00113 00115 00116 00117 00118 VarArray(void); 00120 VarArray(Space& home, int m); 00122 VarArray(Space& home, const VarArgArray<Var>&); 00124 VarArray(const VarArray<Var>& a); 00126 const VarArray<Var>& operator =(const VarArray<Var>& a); 00128 00130 00131 00132 int size(void) const; 00134 00136 00137 00138 Var& operator [](int i); 00140 const Var& operator [](int i) const; 00146 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00147 slice(int start, int inc=1, int n=-1); 00149 00151 00152 00153 iterator begin(void); 00155 const_iterator begin(void) const; 00157 iterator end(void); 00159 const_iterator end(void) const; 00161 reverse_iterator rbegin(void); 00163 const_reverse_iterator rbegin(void) const; 00165 reverse_iterator rend(void); 00167 const_reverse_iterator rend(void) const; 00169 00171 bool assigned(void) const; 00172 00174 00175 00182 void update(Space&, bool share, VarArray<Var>& a); 00184 private: 00185 static void* operator new(size_t); 00186 static void operator delete(void*,size_t); 00187 }; 00188 00192 template<class T> 00193 typename ArrayTraits<VarArray<T> >::ArgsType 00194 operator +(const VarArray<T>& x, const VarArgArray<T>& y); 00195 00199 template<class T> 00200 typename ArrayTraits<VarArray<T> >::ArgsType 00201 operator +(const VarArray<T>& x, const VarArray<T>& y); 00202 00206 template<class T> 00207 typename ArrayTraits<VarArray<T> >::ArgsType 00208 operator +(const VarArgArray<T>& x, const VarArray<T>& y); 00209 00213 template<class T> 00214 typename ArrayTraits<VarArray<T> >::ArgsType 00215 operator +(const VarArray<T>& x, const T& y); 00216 00220 template<class T> 00221 typename ArrayTraits<VarArray<T> >::ArgsType 00222 operator +(const T& x, const VarArray<T>& y); 00223 00232 template<class View> 00233 class ViewArray { 00234 private: 00236 int n; 00238 View* x; 00240 template<class X> 00241 class ViewLess { 00242 public: 00243 bool operator ()(const X&, const X&); 00244 }; 00246 static void sort(View* x, int n); 00247 public: 00249 00250 00251 typedef View value_type; 00253 typedef View& reference; 00255 typedef const View& const_reference; 00257 typedef View* pointer; 00259 typedef const View* const_pointer; 00261 typedef View* iterator; 00263 typedef const View* const_iterator; 00265 typedef std::reverse_iterator<View*> reverse_iterator; 00267 typedef std::reverse_iterator<const View*> const_reverse_iterator; 00269 00271 00272 00273 ViewArray(void); 00275 ViewArray(Space& home, int m); 00277 ViewArray(const ViewArray<View>& a); 00279 ViewArray(Space& home, const ViewArray<View>& a); 00281 const ViewArray<View>& operator =(const ViewArray<View>& a); 00288 template<class Var> 00289 ViewArray(Space& home, const VarArgArray<Var>& a) 00290 : n(a.size()) { 00291 // This may not be in the hpp file (to satisfy the MS compiler) 00292 if (n>0) { 00293 x = home.alloc<View>(n); 00294 for (int i=n; i--; ) 00295 x[i]=a[i]; 00296 } else { 00297 x = NULL; 00298 } 00299 } 00301 00303 00304 00305 int size(void) const; 00307 void size(int n); 00309 00311 00312 00313 View& operator [](int i); 00315 const View& operator [](int i) const; 00317 00319 00320 00321 iterator begin(void); 00323 const_iterator begin(void) const; 00325 iterator end(void); 00327 const_iterator end(void) const; 00329 reverse_iterator rbegin(void); 00331 const_reverse_iterator rbegin(void) const; 00333 reverse_iterator rend(void); 00335 const_reverse_iterator rend(void) const; 00337 00339 00340 00347 void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true); 00349 void cancel(Space& home, Propagator& p, PropCond pc); 00351 void subscribe(Space& home, Advisor& a); 00353 void cancel(Space& home, Advisor& a); 00355 00357 00358 00365 void update(Space&, bool share, ViewArray<View>& a); 00367 00368 00370 00371 00372 void move_fst(int i); 00374 void move_lst(int i); 00380 void move_fst(int i, Space& home, Propagator& p, PropCond pc); 00386 void move_lst(int i, Space& home, Propagator& p, PropCond pc); 00392 void move_fst(int i, Space& home, Advisor& a); 00398 void move_lst(int i, Space& home, Advisor& a); 00400 00402 00403 00404 void drop_fst(int i); 00406 void drop_lst(int i); 00412 void drop_fst(int i, Space& home, Propagator& p, PropCond pc); 00419 void drop_lst(int i, Space& home, Propagator& p, PropCond pc); 00425 void drop_fst(int i, Space& home, Advisor& a); 00431 void drop_lst(int i, Space& home, Advisor& a); 00433 00435 bool assigned(void) const; 00436 00438 00439 00444 bool same(const Space& home) const; 00450 bool same(const Space& home, const View& y) const; 00452 void unique(const Space& home); 00454 00456 00457 00462 bool shared(const Space& home) const; 00468 template<class ViewY> 00469 bool shared(const Space& home, const ViewY& y) const; 00475 template<class ViewY> 00476 bool shared(const Space& home, const ViewArray<ViewY>& y) const; 00478 00479 private: 00480 static void* operator new(size_t); 00481 static void operator delete(void*,size_t); 00482 }; 00483 00497 template<class T> 00498 class ArgArrayBase { 00499 protected: 00501 int n; 00503 int capacity; 00505 T* a; 00507 static const int onstack_size = 16; 00509 T onstack[onstack_size]; 00511 T* allocate(int n); 00513 void resize(int i); 00515 template<class A> 00516 A concat(const ArgArrayBase<T>& x) const; 00518 template<class A> 00519 A concat(const T& x) const; 00521 template<class A> 00522 A& append(const T& x); 00524 template<class A> 00525 A& append(const ArgArrayBase<T>& x); 00531 template<class A> 00532 A slice(int start, int inc=1, int n=-1); 00533 public: 00535 00536 00537 typedef T value_type; 00539 typedef T& reference; 00541 typedef const T& const_reference; 00543 typedef T* pointer; 00545 typedef const T* const_pointer; 00547 typedef T* iterator; 00549 typedef const T* const_iterator; 00551 typedef std::reverse_iterator<T*> reverse_iterator; 00553 typedef std::reverse_iterator<const T*> const_reverse_iterator; 00555 00557 00558 00559 ArgArrayBase(void); 00561 explicit ArgArrayBase(int n); 00563 ArgArrayBase(const ArgArrayBase<T>& a); 00565 const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a); 00567 00569 00570 00571 int size(void) const; 00573 00575 00576 00577 T& operator [](int i); 00579 const T& operator [](int i) const; 00581 00583 00584 00585 iterator begin(void); 00587 const_iterator begin(void) const; 00589 iterator end(void); 00591 const_iterator end(void) const; 00593 reverse_iterator rbegin(void); 00595 const_reverse_iterator rbegin(void) const; 00597 reverse_iterator rend(void); 00599 const_reverse_iterator rend(void) const; 00601 00603 00604 00605 ~ArgArrayBase(void); 00607 private: 00608 static void* operator new(size_t); 00609 static void operator delete(void*,size_t); 00610 }; 00611 00612 template<class> class PrimArgArray; 00613 00617 template<class T> 00618 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00619 operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y); 00620 00624 template<class T> 00625 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00626 operator +(const PrimArgArray<T>& x, const T& y); 00627 00631 template<class T> 00632 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00633 operator +(const T& x, const PrimArgArray<T>& y); 00634 00646 template<class T> 00647 class PrimArgArray : public ArgArrayBase<T> { 00648 protected: 00649 using ArgArrayBase<T>::a; 00650 public: 00651 using ArgArrayBase<T>::size; 00653 00654 00655 PrimArgArray(void); 00657 explicit PrimArgArray(int n); 00659 PrimArgArray(int n, T e0, ...); 00661 PrimArgArray(int n, const T* e); 00663 PrimArgArray(const PrimArgArray<T>& a); 00665 00666 00667 00672 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00673 slice(int start, int inc=1, int n=-1); 00675 00676 00677 00678 typename ArrayTraits<PrimArgArray<T> >::ArgsType& 00679 operator <<(const T& x); 00681 typename ArrayTraits<PrimArgArray<T> >::ArgsType& 00682 operator <<(const PrimArgArray<T>& x); 00684 00685 friend typename ArrayTraits<PrimArgArray<T> >::ArgsType 00686 operator + <>(const PrimArgArray<T>& x, const PrimArgArray<T>& y); 00687 friend typename ArrayTraits<PrimArgArray<T> >::ArgsType 00688 operator + <>(const PrimArgArray<T>& x, const T& y); 00689 friend 00690 typename ArrayTraits<PrimArgArray<T> >::ArgsType 00691 operator + <>(const T& x, const PrimArgArray<T>& y); 00692 }; 00693 00694 template<class> class ArgArray; 00695 00699 template<class T> 00700 typename ArrayTraits<ArgArray<T> >::ArgsType 00701 operator +(const ArgArray<T>& x, const ArgArray<T>& y); 00702 00706 template<class T> 00707 typename ArrayTraits<ArgArray<T> >::ArgsType 00708 operator +(const ArgArray<T>& x, const T& y); 00709 00713 template<class T> 00714 typename ArrayTraits<ArgArray<T> >::ArgsType 00715 operator +(const T& x, const ArgArray<T>& y); 00716 00728 template<class T> 00729 class ArgArray : public ArgArrayBase<T> { 00730 protected: 00731 using ArgArrayBase<T>::a; 00732 public: 00733 using ArgArrayBase<T>::size; 00735 00736 00737 ArgArray(void); 00739 explicit ArgArray(int n); 00741 ArgArray(int n, const T* e); 00743 ArgArray(const ArgArray<T>& a); 00745 00746 00747 00748 typename ArrayTraits<ArgArray<T> >::ArgsType 00749 slice(int start, int inc=1, int n=-1); 00751 00752 00753 00754 typename ArrayTraits<ArgArray<T> >::ArgsType& 00755 operator <<(const T& x); 00757 typename ArrayTraits<ArgArray<T> >::ArgsType& 00758 operator <<(const ArgArray<T>& x); 00760 00761 friend typename ArrayTraits<ArgArray<T> >::ArgsType 00762 operator + <>(const ArgArray<T>& x, const ArgArray<T>& y); 00763 friend typename ArrayTraits<ArgArray<T> >::ArgsType 00764 operator + <>(const ArgArray<T>& x, const T& y); 00765 friend 00766 typename ArrayTraits<ArgArray<T> >::ArgsType 00767 operator + <>(const T& x, const ArgArray<T>& y); 00768 }; 00769 00770 template<class> class VarArgArray; 00771 00775 template<class Var> 00776 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00777 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y); 00778 00782 template<class Var> 00783 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00784 operator +(const VarArgArray<Var>& x, const Var& y); 00785 00789 template<class Var> 00790 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00791 operator +(const Var& x, const VarArgArray<Var>& y); 00792 00804 template<class Var> 00805 class VarArgArray : public ArgArrayBase<Var> { 00806 protected: 00807 using ArgArrayBase<Var>::a; 00808 using ArgArrayBase<Var>::n; 00810 class VarLess { 00811 public: 00812 bool operator ()(const Var&, const Var&); 00813 }; 00814 public: 00815 using ArgArrayBase<Var>::size; 00817 00818 00819 VarArgArray(void); 00821 explicit VarArgArray(int n); 00823 VarArgArray(const VarArgArray<Var>& a); 00825 VarArgArray(const VarArray<Var>& a); 00827 00828 00829 00830 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00831 slice(int start, int inc=1, int n=-1); 00833 00834 00835 00836 typename ArrayTraits<VarArgArray<Var> >::ArgsType& 00837 operator <<(const Var& x); 00839 typename ArrayTraits<VarArgArray<Var> >::ArgsType& 00840 operator <<(const VarArgArray<Var>& x); 00842 00844 bool assigned(void) const; 00845 00846 friend typename ArrayTraits<VarArgArray<Var> >::ArgsType 00847 operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y); 00848 friend typename ArrayTraits<VarArgArray<Var> >::ArgsType 00849 operator + <>(const VarArgArray<Var>& x, const Var& y); 00850 friend 00851 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00852 operator + <>(const Var& x, const VarArgArray<Var>& y); 00853 00855 00856 00861 bool same(const Space& home) const; 00867 bool same(const Space& home, const Var& y) const; 00873 bool same(const Space& home, const VarArgArray<Var>& y) const; 00875 }; 00876 00881 template<class Char, class Traits, class Var> 00882 std::basic_ostream<Char,Traits>& 00883 operator <<(std::basic_ostream<Char,Traits>& os, 00884 const VarArray<Var>& x); 00885 00890 template<class Char, class Traits, class View> 00891 std::basic_ostream<Char,Traits>& 00892 operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x); 00893 00898 template<class Char, class Traits, class T> 00899 std::basic_ostream<Char,Traits>& 00900 operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x); 00901 00902 00903 /* 00904 * Implementation 00905 * 00906 */ 00907 00908 /* 00909 * Variable arrays 00910 * 00911 * These arrays are usually allocated in the space, but if they are resized, 00912 * the new array is allocated on the heap. The size (n) and capacity show 00913 * where the array is allocated: it is in the space if and only if 00914 * n==capacity. 00915 * 00916 */ 00917 00918 template<class Var> 00919 forceinline 00920 VarArray<Var>::VarArray(void) : n(0), x(NULL) {} 00921 00922 template<class Var> 00923 forceinline 00924 VarArray<Var>::VarArray(Space& home, int n0) 00925 : n(n0) { 00926 // Allocate from space 00927 x = (n>0) ? home.alloc<Var>(n) : NULL; 00928 } 00929 00930 template<class Var> 00931 forceinline 00932 VarArray<Var>::VarArray(const VarArray<Var>& a) { 00933 n = a.n; x = a.x; 00934 } 00935 00936 template<class Var> 00937 inline const VarArray<Var>& 00938 VarArray<Var>::operator =(const VarArray<Var>& a) { 00939 n = a.n; x = a.x; 00940 return *this; 00941 } 00942 00943 template<class Var> 00944 forceinline int 00945 VarArray<Var>::size(void) const { 00946 return n; 00947 } 00948 00949 template<class Var> 00950 forceinline Var& 00951 VarArray<Var>::operator [](int i) { 00952 assert((i >= 0) && (i < size())); 00953 return x[i]; 00954 } 00955 00956 template<class Var> 00957 forceinline const Var& 00958 VarArray<Var>::operator [](int i) const { 00959 assert((i >= 0) && (i < size())); 00960 return x[i]; 00961 } 00962 00963 template<class Var> 00964 typename ArrayTraits<VarArgArray<Var> >::ArgsType 00965 VarArray<Var>::slice(int start, int inc, int maxN) { 00966 assert(start < n); 00967 if (maxN<0) 00968 maxN = n; 00969 int s; 00970 if (inc == 0) 00971 s = n-start; 00972 else if (inc > 0) 00973 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); 00974 else 00975 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); 00976 typename ArrayTraits<VarArgArray<Var> >::ArgsType r(std::min(maxN,s)); 00977 for (int i=0; i<r.size(); i++, start+=inc) 00978 r[i] = x[start]; 00979 return r; 00980 } 00981 00982 template<class Var> 00983 forceinline typename VarArray<Var>::iterator 00984 VarArray<Var>::begin(void) { 00985 return x; 00986 } 00987 00988 template<class Var> 00989 forceinline typename VarArray<Var>::const_iterator 00990 VarArray<Var>::begin(void) const { 00991 return x; 00992 } 00993 00994 template<class Var> 00995 forceinline typename VarArray<Var>::iterator 00996 VarArray<Var>::end(void) { 00997 return x+n; 00998 } 00999 01000 template<class Var> 01001 forceinline typename VarArray<Var>::const_iterator 01002 VarArray<Var>::end(void) const { 01003 return x+n; 01004 } 01005 01006 template<class Var> 01007 forceinline typename VarArray<Var>::reverse_iterator 01008 VarArray<Var>::rbegin(void) { 01009 return reverse_iterator(x+n); 01010 } 01011 01012 template<class Var> 01013 forceinline typename VarArray<Var>::const_reverse_iterator 01014 VarArray<Var>::rbegin(void) const { 01015 return const_reverse_iterator(x+n); 01016 } 01017 01018 template<class Var> 01019 forceinline typename VarArray<Var>::reverse_iterator 01020 VarArray<Var>::rend(void) { 01021 return reverse_iterator(x); 01022 } 01023 01024 template<class Var> 01025 forceinline typename VarArray<Var>::const_reverse_iterator 01026 VarArray<Var>::rend(void) const { 01027 return const_reverse_iterator(x); 01028 } 01029 01030 template<class Var> 01031 forceinline void 01032 VarArray<Var>::update(Space& home, bool share, VarArray<Var>& a) { 01033 n = a.n; 01034 if (n > 0) { 01035 x = home.alloc<Var>(n); 01036 for (int i = n; i--;) 01037 x[i].update(home, share, a.x[i]); 01038 } else { 01039 x = NULL; 01040 } 01041 } 01042 01043 template<class Var> 01044 forceinline bool 01045 VarArray<Var>::assigned(void) const { 01046 for (int i = n; i--;) 01047 if (!x[i].assigned()) 01048 return false; 01049 return true; 01050 } 01051 01052 template<class Var> 01053 void* 01054 VarArray<Var>::operator new(size_t) { 01055 return NULL; 01056 } 01057 01058 template<class Var> 01059 void 01060 VarArray<Var>::operator delete(void*,size_t) { 01061 } 01062 01063 template<class Var> 01064 typename ArrayTraits<VarArray<Var> >::ArgsType 01065 operator +(const VarArray<Var>& x, const VarArray<Var>& y) { 01066 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 01067 for (int i=x.size(); i--;) 01068 r[i] = x[i]; 01069 for (int i=y.size(); i--;) 01070 r[x.size()+i] = y[i]; 01071 return r; 01072 } 01073 01074 template<class Var> 01075 typename ArrayTraits<VarArray<Var> >::ArgsType 01076 operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) { 01077 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 01078 for (int i=x.size(); i--;) 01079 r[i] = x[i]; 01080 for (int i=y.size(); i--;) 01081 r[x.size()+i] = y[i]; 01082 return r; 01083 } 01084 01085 template<class Var> 01086 typename ArrayTraits<VarArray<Var> >::ArgsType 01087 operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) { 01088 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+y.size()); 01089 for (int i=x.size(); i--;) 01090 r[i] = x[i]; 01091 for (int i=y.size(); i--;) 01092 r[x.size()+i] = y[i]; 01093 return r; 01094 } 01095 01096 template<class Var> 01097 typename ArrayTraits<VarArray<Var> >::ArgsType 01098 operator +(const VarArray<Var>& x, const Var& y) { 01099 typename ArrayTraits<VarArray<Var> >::ArgsType r(x.size()+1); 01100 for (int i=x.size(); i--;) 01101 r[i] = x[i]; 01102 r[x.size()] = y; 01103 return r; 01104 } 01105 01106 template<class Var> 01107 typename ArrayTraits<VarArray<Var> >::ArgsType 01108 operator +(const Var& x, const VarArray<Var>& y) { 01109 typename ArrayTraits<VarArray<Var> >::ArgsType r(y.size()+1); 01110 r[0] = x; 01111 for (int i=y.size(); i--;) 01112 r[1+i] = y[i]; 01113 return r; 01114 } 01115 01116 /* 01117 * View arrays 01118 * 01119 */ 01120 01121 template<class View> 01122 forceinline 01123 ViewArray<View>::ViewArray(void) : n(0), x(NULL) {} 01124 01125 template<class View> 01126 forceinline 01127 ViewArray<View>::ViewArray(Space& home, int n0) 01128 : n(n0) { 01129 x = (n>0) ? home.alloc<View>(n) : NULL; 01130 } 01131 01132 template<class View> 01133 ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a) 01134 : n(a.size()) { 01135 if (n>0) { 01136 x = home.alloc<View>(n); 01137 for (int i = n; i--; ) 01138 x[i] = a[i]; 01139 } else { 01140 x = NULL; 01141 } 01142 } 01143 01144 template<class View> 01145 forceinline 01146 ViewArray<View>::ViewArray(const ViewArray<View>& a) 01147 : n(a.n), x(a.x) {} 01148 01149 template<class View> 01150 forceinline const ViewArray<View>& 01151 ViewArray<View>::operator =(const ViewArray<View>& a) { 01152 n = a.n; x = a.x; 01153 return *this; 01154 } 01155 01156 template<class View> 01157 forceinline int 01158 ViewArray<View>::size(void) const { 01159 return n; 01160 } 01161 01162 template<class View> 01163 forceinline void 01164 ViewArray<View>::size(int n0) { 01165 n = n0; 01166 } 01167 01168 template<class View> 01169 forceinline View& 01170 ViewArray<View>::operator [](int i) { 01171 assert((i >= 0) && (i < size())); 01172 return x[i]; 01173 } 01174 01175 template<class View> 01176 forceinline const View& 01177 ViewArray<View>::operator [](int i) const { 01178 assert((i >= 0) && (i < size())); 01179 return x[i]; 01180 } 01181 01182 template<class View> 01183 forceinline typename ViewArray<View>::iterator 01184 ViewArray<View>::begin(void) { 01185 return x; 01186 } 01187 01188 template<class View> 01189 forceinline typename ViewArray<View>::const_iterator 01190 ViewArray<View>::begin(void) const { 01191 return x; 01192 } 01193 01194 template<class View> 01195 forceinline typename ViewArray<View>::iterator 01196 ViewArray<View>::end(void) { 01197 return x+n; 01198 } 01199 01200 template<class View> 01201 forceinline typename ViewArray<View>::const_iterator 01202 ViewArray<View>::end(void) const { 01203 return x+n; 01204 } 01205 01206 template<class View> 01207 forceinline typename ViewArray<View>::reverse_iterator 01208 ViewArray<View>::rbegin(void) { 01209 return reverse_iterator(x+n); 01210 } 01211 01212 template<class View> 01213 forceinline typename ViewArray<View>::const_reverse_iterator 01214 ViewArray<View>::rbegin(void) const { 01215 return const_reverse_iterator(x+n); 01216 } 01217 01218 template<class View> 01219 forceinline typename ViewArray<View>::reverse_iterator 01220 ViewArray<View>::rend(void) { 01221 return reverse_iterator(x); 01222 } 01223 01224 template<class View> 01225 forceinline typename ViewArray<View>::const_reverse_iterator 01226 ViewArray<View>::rend(void) const { 01227 return const_reverse_iterator(x); 01228 } 01229 01230 template<class View> 01231 forceinline void 01232 ViewArray<View>::move_fst(int i) { 01233 x[i]=x[0]; x++; n--; 01234 } 01235 01236 template<class View> 01237 forceinline void 01238 ViewArray<View>::move_lst(int i) { 01239 n--; x[i]=x[n]; 01240 } 01241 01242 template<class View> 01243 forceinline void 01244 ViewArray<View>::drop_fst(int i) { 01245 assert(i>=0); 01246 x += i; n -= i; 01247 } 01248 01249 template<class View> 01250 forceinline void 01251 ViewArray<View>::drop_lst(int i) { 01252 assert(i<n); 01253 n = i+1; 01254 } 01255 01256 template<class View> 01257 forceinline void 01258 ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) { 01259 // Move x[0] to x[i] 01260 x[i].cancel(home,p,pc); 01261 x[i]=x[0]; x++; n--; 01262 } 01263 01264 template<class View> 01265 forceinline void 01266 ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) { 01267 // Move x[n-1] to x[i] 01268 x[i].cancel(home,p,pc); 01269 n--; x[i]=x[n]; 01270 } 01271 01272 template<class View> 01273 void 01274 ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) { 01275 // Drop elements from 0..i-1 01276 assert(i>=0); 01277 for (int j=i; j--; ) 01278 x[j].cancel(home,p,pc); 01279 x += i; n -= i; 01280 } 01281 01282 template<class View> 01283 void 01284 ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) { 01285 // Drop elements from i+1..n-1 01286 assert(i<n); 01287 for (int j=i+1; j<n; j++) 01288 x[j].cancel(home,p,pc); 01289 n = i+1; 01290 } 01291 01292 template<class View> 01293 forceinline void 01294 ViewArray<View>::move_fst(int i, Space& home, Advisor& a) { 01295 // Move x[0] to x[i] 01296 x[i].cancel(home,a); 01297 x[i]=x[0]; x++; n--; 01298 } 01299 01300 template<class View> 01301 forceinline void 01302 ViewArray<View>::move_lst(int i, Space& home, Advisor& a) { 01303 // Move x[n-1] to x[i] 01304 x[i].cancel(home,a); 01305 n--; x[i]=x[n]; 01306 } 01307 01308 template<class View> 01309 void 01310 ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) { 01311 // Drop elements from 0..i-1 01312 assert(i>=0); 01313 for (int j=i; j--; ) 01314 x[j].cancel(home,a); 01315 x += i; n -= i; 01316 } 01317 01318 template<class View> 01319 void 01320 ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) { 01321 // Drop elements from i+1..n-1 01322 assert(i<n); 01323 for (int j=i+1; j<n; j++) 01324 x[j].cancel(home,a); 01325 n = i+1; 01326 } 01327 01328 template<class View> 01329 void 01330 ViewArray<View>::update(Space& home, bool share, ViewArray<View>& y) { 01331 n = y.n; 01332 if (n > 0) { 01333 x = home.alloc<View>(n); 01334 for (int i = n; i--; ) 01335 x[i].update(home, share, y.x[i]); 01336 } else { 01337 x = NULL; 01338 } 01339 } 01340 01341 template<class View> 01342 void 01343 ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc, 01344 bool process) { 01345 for (int i = n; i--; ) 01346 x[i].subscribe(home,p,pc,process); 01347 } 01348 01349 template<class View> 01350 void 01351 ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) { 01352 for (int i = n; i--; ) 01353 x[i].cancel(home,p,pc); 01354 } 01355 01356 template<class View> 01357 void 01358 ViewArray<View>::subscribe(Space& home, Advisor& a) { 01359 for (int i = n; i--; ) 01360 x[i].subscribe(home,a); 01361 } 01362 01363 template<class View> 01364 void 01365 ViewArray<View>::cancel(Space& home, Advisor& a) { 01366 for (int i = n; i--; ) 01367 x[i].cancel(home,a); 01368 } 01369 01370 template<class View> 01371 forceinline bool 01372 ViewArray<View>::assigned(void) const { 01373 for (int i = n; i--;) 01374 if (!x[i].assigned()) 01375 return false; 01376 return true; 01377 } 01378 01379 template<class View> 01380 forceinline bool 01381 __before(const View& x, const View& y) { 01382 return before(x,y); 01383 } 01384 01385 template<class View> template<class X> 01386 forceinline bool 01387 ViewArray<View>::ViewLess<X>::operator ()(const X& a, const X& b) { 01388 return __before(a,b); 01389 } 01390 01391 template<class View> 01392 void 01393 ViewArray<View>::sort(View* y, int m) { 01394 ViewLess<View> vl; 01395 Support::quicksort<View,ViewLess<View> >(y,m,vl); 01396 } 01397 01398 template<class X, class Y> 01399 forceinline bool 01400 __same(const X& x, const Y& y) { 01401 return same(x,y); 01402 } 01403 template<class X, class Y> 01404 forceinline bool 01405 __shared(const X& x, const Y& y) { 01406 return shared(x,y); 01407 } 01408 01409 template<class View> 01410 bool 01411 ViewArray<View>::same(const Space& home) const { 01412 if (n < 2) 01413 return false; 01414 Region r(home); 01415 View* y = r.alloc<View>(n); 01416 for (int i = n; i--; ) 01417 y[i] = x[i]; 01418 sort(y,n); 01419 for (int i = n-1; i--; ) 01420 if (!y[i].assigned() && __same(y[i+1],y[i])) { 01421 r.free<View>(y,n); 01422 return true; 01423 } 01424 r.free<View>(y,n); 01425 return false; 01426 } 01427 01428 template<class View> 01429 bool 01430 ViewArray<View>::same(const Space&, const View& y) const { 01431 if (y.assigned()) 01432 return false; 01433 for (int i = n; i--; ) 01434 if (__same(x[i],y)) 01435 return true; 01436 return false; 01437 } 01438 01439 template<class View> 01440 void 01441 ViewArray<View>::unique(const Space&) { 01442 if (n < 2) 01443 return; 01444 sort(x,n); 01445 int j = 0; 01446 for (int i = 1; i<n; i++) 01447 if (!__same(x[j],x[i])) 01448 x[++j] = x[i]; 01449 n = j+1; 01450 } 01451 01452 template<class View> 01453 bool 01454 ViewArray<View>::shared(const Space& home) const { 01455 if (n < 2) 01456 return false; 01457 Region r(home); 01458 View* y = r.alloc<View>(n); 01459 for (int i = n; i--; ) 01460 y[i] = x[i]; 01461 sort(y,n); 01462 for (int i = n-1; i--; ) 01463 if (!y[i].assigned() && __shared(y[i+1],y[i])) { 01464 r.free<View>(y,n); 01465 return true; 01466 } 01467 r.free<View>(y,n); 01468 return false; 01469 } 01470 01471 template<class View> template<class ViewY> 01472 bool 01473 ViewArray<View>::shared(const Space&, const ViewY& y) const { 01474 if (y.assigned()) 01475 return false; 01476 for (int i = n; i--; ) 01477 if (!x[i].assigned() && __shared(x[i],y)) 01478 return true; 01479 return false; 01480 } 01481 01482 template<class View> template<class ViewY> 01483 bool 01484 ViewArray<View>::shared(const Space& home, const ViewArray<ViewY>& y) const { 01485 if ((size() < 1) || (y.size() < 1)) 01486 return false; 01487 Region r(home); 01488 View* xs = r.alloc<View>(size()); 01489 for (int i=size(); i--; ) 01490 xs[i] = x[i]; 01491 ViewLess<View> xvl; 01492 Support::quicksort<View,ViewLess<View> >(xs,size(),xvl); 01493 ViewY* ys = r.alloc<ViewY>(y.size()); 01494 for (int j=y.size(); j--; ) 01495 ys[j] = y[j]; 01496 ViewLess<ViewY> yvl; 01497 Support::quicksort<ViewY,ViewLess<ViewY> >(ys,y.size(),yvl); 01498 { 01499 int i=0, j=0; 01500 while ((i < size()) && (j < y.size())) 01501 if (!x[i].assigned() && __shared(x[i],y[j])) { 01502 r.free<View>(xs,size()); 01503 r.free<ViewY>(ys,y.size()); 01504 return true; 01505 } else if (before(x[i],y[j])) { 01506 i++; 01507 } else { 01508 j++; 01509 } 01510 } 01511 r.free<View>(xs,size()); 01512 r.free<ViewY>(ys,y.size()); 01513 return false; 01514 } 01515 01516 template<class View> 01517 void* 01518 ViewArray<View>::operator new(size_t) { 01519 return NULL; 01520 } 01521 01522 template<class View> 01523 void 01524 ViewArray<View>::operator delete(void*,size_t) { 01525 } 01526 01527 01528 /* 01529 * Argument arrays: base class 01530 * 01531 */ 01532 01533 template<class T> 01534 forceinline T* 01535 ArgArrayBase<T>::allocate(int n) { 01536 return (n > onstack_size) ? 01537 heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0]; 01538 } 01539 01540 template<class T> 01541 forceinline void 01542 ArgArrayBase<T>::resize(int i) { 01543 if (n+i >= capacity) { 01544 assert(n+i >= onstack_size); 01545 int newCapacity = (3*capacity)/2; 01546 if (newCapacity <= n+i) 01547 newCapacity = n+i; 01548 T* newA = allocate(newCapacity); 01549 heap.copy<T>(newA,a,n); 01550 if (capacity > onstack_size) 01551 heap.free(a,capacity); 01552 capacity = newCapacity; 01553 a = newA; 01554 } 01555 } 01556 01557 template<class T> 01558 forceinline 01559 ArgArrayBase<T>::ArgArrayBase(void) 01560 : n(0), capacity(onstack_size), a(allocate(0)) {} 01561 01562 template<class T> 01563 forceinline 01564 ArgArrayBase<T>::ArgArrayBase(int n0) 01565 : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {} 01566 01567 template<class T> 01568 inline 01569 ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa) 01570 : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) { 01571 heap.copy<T>(a,aa.a,n); 01572 } 01573 01574 template<class T> 01575 forceinline 01576 ArgArrayBase<T>::~ArgArrayBase(void) { 01577 if (capacity > onstack_size) 01578 heap.free(a,capacity); 01579 } 01580 01581 template<class T> 01582 forceinline const ArgArrayBase<T>& 01583 ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) { 01584 if (&aa != this) { 01585 if (capacity > onstack_size) 01586 heap.free(a,capacity); 01587 n = aa.n; 01588 capacity = (n < onstack_size ? onstack_size : n); 01589 a = allocate(aa.n); 01590 heap.copy<T>(a,aa.a,n); 01591 } 01592 return *this; 01593 } 01594 01595 template<class T> 01596 forceinline int 01597 ArgArrayBase<T>::size(void) const { 01598 return n; 01599 } 01600 01601 template<class T> 01602 forceinline T& 01603 ArgArrayBase<T>::operator [](int i) { 01604 assert((i>=0) && (i < n)); 01605 return a[i]; 01606 } 01607 01608 template<class T> 01609 forceinline const T& 01610 ArgArrayBase<T>::operator [](int i) const { 01611 assert((i>=0) && (i < n)); 01612 return a[i]; 01613 } 01614 01615 template<class T> 01616 forceinline typename ArgArrayBase<T>::iterator 01617 ArgArrayBase<T>::begin(void) { 01618 return a; 01619 } 01620 01621 template<class T> 01622 forceinline typename ArgArrayBase<T>::const_iterator 01623 ArgArrayBase<T>::begin(void) const { 01624 return a; 01625 } 01626 01627 template<class T> 01628 forceinline typename ArgArrayBase<T>::iterator 01629 ArgArrayBase<T>::end(void) { 01630 return a+n; 01631 } 01632 01633 template<class T> 01634 forceinline typename ArgArrayBase<T>::const_iterator 01635 ArgArrayBase<T>::end(void) const { 01636 return a+n; 01637 } 01638 01639 template<class T> 01640 forceinline typename ArgArrayBase<T>::reverse_iterator 01641 ArgArrayBase<T>::rbegin(void) { 01642 return reverse_iterator(a+n); 01643 } 01644 01645 template<class T> 01646 forceinline typename ArgArrayBase<T>::const_reverse_iterator 01647 ArgArrayBase<T>::rbegin(void) const { 01648 return const_reverse_iterator(a+n); 01649 } 01650 01651 template<class T> 01652 forceinline typename ArgArrayBase<T>::reverse_iterator 01653 ArgArrayBase<T>::rend(void) { 01654 return reverse_iterator(a); 01655 } 01656 01657 template<class T> 01658 forceinline typename ArgArrayBase<T>::const_reverse_iterator 01659 ArgArrayBase<T>::rend(void) const { 01660 return const_reverse_iterator(a); 01661 } 01662 01663 template<class T> template<class A> 01664 A 01665 ArgArrayBase<T>::slice(int start, int inc, int maxN) { 01666 assert(start < n); 01667 if (maxN<0) 01668 maxN = n; 01669 int s; 01670 if (inc == 0) 01671 s = n-start; 01672 else if (inc > 0) 01673 s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); 01674 else 01675 s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); 01676 A r(std::min(maxN,s)); 01677 for (int i=0; i<r.size(); i++, start+=inc) 01678 new (&r[i]) T(a[start]); 01679 return r; 01680 } 01681 01682 template<class T> template<class A> 01683 inline A& 01684 ArgArrayBase<T>::append(const T& x) { 01685 resize(1); 01686 new (&a[n++]) T(x); 01687 return static_cast<A&>(*this); 01688 } 01689 01690 template<class T> template<class A> 01691 inline A& 01692 ArgArrayBase<T>::append(const ArgArrayBase<T>& x) { 01693 resize(x.size()); 01694 for (int i=0; i<x.size(); i++) 01695 new (&a[n++]) T(x[i]); 01696 return static_cast<A&>(*this); 01697 } 01698 01699 template<class T> template<class A> 01700 inline A 01701 ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const { 01702 A r(n+x.n); 01703 for (int i=n; i--;) 01704 new (&r[i]) T(a[i]); 01705 for (int i=x.n; i--;) 01706 new (&r[n+i]) T(x.a[i]); 01707 return r; 01708 } 01709 01710 template<class T> template<class A> 01711 inline A 01712 ArgArrayBase<T>::concat(const T& x) const { 01713 A r(n+1); 01714 for (int i=n; i--;) 01715 new (&r[i]) T(a[i]); 01716 new (&r[n]) T(x); 01717 return r; 01718 } 01719 01720 /* 01721 * Argument arrays for primitive types 01722 * 01723 */ 01724 01725 template<class T> 01726 forceinline 01727 PrimArgArray<T>::PrimArgArray(void) {} 01728 01729 template<class T> 01730 forceinline 01731 PrimArgArray<T>::PrimArgArray(int n) : ArgArrayBase<T>(n) {} 01732 01733 template<class T> 01734 PrimArgArray<T>::PrimArgArray(int n, T a0, ...) 01735 : ArgArrayBase<T>(n) { 01736 va_list args; 01737 va_start(args, a0); 01738 a[0] = a0; 01739 for (int i = 1; i < n; i++) 01740 a[i] = va_arg(args,T); 01741 va_end(args); 01742 } 01743 01744 template<class T> 01745 PrimArgArray<T>::PrimArgArray(int n, const T* a0) 01746 : ArgArrayBase<T>(n) { 01747 for (int i=n; i--; ) 01748 a[i] = a0[i]; 01749 } 01750 01751 template<class T> 01752 forceinline 01753 PrimArgArray<T>::PrimArgArray(const PrimArgArray<T>& aa) 01754 : ArgArrayBase<T>(aa) {} 01755 01756 template<class T> 01757 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType 01758 PrimArgArray<T>::slice(int start, int inc, int maxN) { 01759 return ArgArrayBase<T>::template slice 01760 <typename ArrayTraits<PrimArgArray<T> >::ArgsType> 01761 (start,inc,maxN); 01762 } 01763 01764 template<class T> 01765 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType& 01766 PrimArgArray<T>::operator <<(const T& x) { 01767 return 01768 ArgArrayBase<T>::template append 01769 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x); 01770 } 01771 01772 template<class T> 01773 forceinline typename ArrayTraits<PrimArgArray<T> >::ArgsType& 01774 PrimArgArray<T>::operator <<(const PrimArgArray<T>& x) { 01775 return 01776 ArgArrayBase<T>::template append 01777 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(x); 01778 } 01779 01780 template<class T> 01781 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01782 operator +(const PrimArgArray<T>& x, const PrimArgArray<T>& y) { 01783 return x.template concat 01784 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01785 } 01786 01787 template<class T> 01788 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01789 operator +(const PrimArgArray<T>& x, const T& y) { 01790 return x.template concat 01791 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01792 } 01793 01794 template<class T> 01795 typename ArrayTraits<PrimArgArray<T> >::ArgsType 01796 operator +(const T& x, const PrimArgArray<T>& y) { 01797 return PrimArgArray<T>(1,x).template concat 01798 <typename ArrayTraits<PrimArgArray<T> >::ArgsType>(y); 01799 } 01800 01801 01802 /* 01803 * Argument arrays for non-primitive types 01804 * 01805 */ 01806 01807 template<class T> 01808 forceinline 01809 ArgArray<T>::ArgArray(void) {} 01810 01811 template<class T> 01812 forceinline 01813 ArgArray<T>::ArgArray(int n) : ArgArrayBase<T>(n) {} 01814 01815 template<class T> 01816 ArgArray<T>::ArgArray(int n, const T* a0) 01817 : ArgArrayBase<T>(n) { 01818 for (int i=n; i--; ) 01819 a[i] = a0[i]; 01820 } 01821 01822 template<class T> 01823 forceinline 01824 ArgArray<T>::ArgArray(const ArgArray<T>& aa) 01825 : ArgArrayBase<T>(aa) {} 01826 01827 template<class T> 01828 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType 01829 ArgArray<T>::slice(int start, int inc, int maxN) { 01830 return ArgArrayBase<T>::template slice 01831 <typename ArrayTraits<ArgArray<T> >::ArgsType> 01832 (start,inc,maxN); 01833 } 01834 01835 template<class T> 01836 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType& 01837 ArgArray<T>::operator <<(const T& x) { 01838 return 01839 ArgArrayBase<T>::template append 01840 <typename ArrayTraits<ArgArray<T> >::ArgsType>(x); 01841 } 01842 01843 template<class T> 01844 forceinline typename ArrayTraits<ArgArray<T> >::ArgsType& 01845 ArgArray<T>::operator <<(const ArgArray<T>& x) { 01846 return 01847 ArgArrayBase<T>::template append 01848 <typename ArrayTraits<ArgArray<T> >::ArgsType>(x); 01849 } 01850 01851 template<class T> 01852 typename ArrayTraits<ArgArray<T> >::ArgsType 01853 operator +(const ArgArray<T>& x, const ArgArray<T>& y) { 01854 return x.template concat 01855 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01856 } 01857 01858 template<class T> 01859 typename ArrayTraits<ArgArray<T> >::ArgsType 01860 operator +(const ArgArray<T>& x, const T& y) { 01861 return x.template concat 01862 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01863 } 01864 01865 template<class T> 01866 typename ArrayTraits<ArgArray<T> >::ArgsType 01867 operator +(const T& x, const ArgArray<T>& y) { 01868 ArgArray<T> xa(1); 01869 xa[0] = x; 01870 return xa.template concat 01871 <typename ArrayTraits<ArgArray<T> >::ArgsType>(y); 01872 } 01873 01874 /* 01875 * Argument arrays for variables 01876 * 01877 */ 01878 01879 template<class Var> 01880 forceinline 01881 VarArgArray<Var>::VarArgArray(void) {} 01882 01883 template<class Var> 01884 forceinline 01885 VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {} 01886 01887 template<class Var> 01888 forceinline 01889 VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa) 01890 : ArgArrayBase<Var>(aa) {} 01891 01892 template<class Var> 01893 inline 01894 VarArgArray<Var>::VarArgArray(const VarArray<Var>& x) 01895 : ArgArrayBase<Var>(x.size()) { 01896 for (int i=x.size(); i--; ) 01897 a[i]=x[i]; 01898 } 01899 01900 template<class Var> 01901 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType 01902 VarArgArray<Var>::slice(int start, int inc, int maxN) { 01903 return ArgArrayBase<Var>::template slice 01904 <typename ArrayTraits<VarArgArray<Var> >::ArgsType> 01905 (start,inc,maxN); 01906 } 01907 01908 template<class Var> 01909 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType& 01910 VarArgArray<Var>::operator <<(const Var& x) { 01911 return 01912 ArgArrayBase<Var>::template append 01913 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x); 01914 } 01915 01916 template<class Var> 01917 forceinline typename ArrayTraits<VarArgArray<Var> >::ArgsType& 01918 VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) { 01919 return 01920 ArgArrayBase<Var>::template append 01921 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(x); 01922 } 01923 01924 template<class Var> 01925 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01926 operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) { 01927 return x.template concat 01928 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01929 } 01930 01931 template<class Var> 01932 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01933 operator +(const VarArgArray<Var>& x, const Var& y) { 01934 return x.template concat 01935 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01936 } 01937 01938 template<class Var> 01939 typename ArrayTraits<VarArgArray<Var> >::ArgsType 01940 operator +(const Var& x, const VarArgArray<Var>& y) { 01941 VarArgArray<Var> xa(1); 01942 xa[0] = x; 01943 return xa.template concat 01944 <typename ArrayTraits<VarArgArray<Var> >::ArgsType>(y); 01945 } 01946 01947 template<class Var> 01948 forceinline bool 01949 VarArgArray<Var>::VarLess::operator ()(const Var& a, const Var& b) { 01950 return a.varimp() < b.varimp(); 01951 } 01952 01953 template<class Var> 01954 forceinline bool 01955 VarArgArray<Var>::assigned(void) const { 01956 for (int i = n; i--;) 01957 if (!a[i].assigned()) 01958 return false; 01959 return true; 01960 } 01961 01962 template<class Var> 01963 bool 01964 VarArgArray<Var>::same(const Space& home) const { 01965 if (n < 2) 01966 return false; 01967 Region r(home); 01968 Var* y = r.alloc<Var>(n); 01969 for (int i = n; i--; ) 01970 y[i] = a[i]; 01971 VarLess vl; 01972 Support::quicksort<Var,VarLess>(y,n,vl); 01973 for (int i = n-1; i--; ) 01974 if (!y[i].assigned() && (y[i+1].varimp() == y[i].varimp())) { 01975 r.free<Var>(y,n); 01976 return true; 01977 } 01978 r.free<Var>(y,n); 01979 return false; 01980 } 01981 01982 template<class Var> 01983 bool 01984 VarArgArray<Var>::same(const Space& home, const VarArgArray<Var>& y) const { 01985 int m = n + y.n; 01986 if (m < 2) 01987 return false; 01988 Region r(home); 01989 Var* z = r.alloc<Var>(m); 01990 for (int i = n; i--; ) 01991 z[i] = a[i]; 01992 for (int i = y.n; i--; ) 01993 z[i+n] = y.a[i]; 01994 VarLess vl; 01995 Support::quicksort<Var,VarLess>(z,m,vl); 01996 for (int i = m-1; i--; ) 01997 if (!z[i].assigned() && (z[i+1].varimp() == z[i].varimp())) { 01998 r.free<Var>(z,m); 01999 return true; 02000 } 02001 r.free<Var>(z,m); 02002 return false; 02003 } 02004 02005 template<class Var> 02006 bool 02007 VarArgArray<Var>::same(const Space&, const Var& y) const { 02008 if (y.assigned()) 02009 return false; 02010 for (int i = n; i--; ) 02011 if (a[i].varimp() == y.varimp()) 02012 return true; 02013 return false; 02014 } 02015 02016 02017 02018 02019 02020 02021 /* 02022 * Interdependent code 02023 * 02024 */ 02025 02026 template<class Var> 02027 inline 02028 VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a) 02029 : n(a.size()) { 02030 if (n>0) { 02031 x = home.alloc<Var>(n); 02032 for (int i=n; i--;) 02033 x[i] = a[i]; 02034 } else { 02035 x = NULL; 02036 } 02037 } 02038 02039 02040 /* 02041 * Printing of arrays 02042 * 02043 */ 02044 template<class Char, class Traits, class Var> 02045 std::basic_ostream<Char,Traits>& 02046 operator <<(std::basic_ostream<Char,Traits>& os, 02047 const VarArray<Var>& x) { 02048 std::basic_ostringstream<Char,Traits> s; 02049 s.copyfmt(os); s.width(0); 02050 s << '{'; 02051 if (x.size() > 0) { 02052 s << x[0]; 02053 for (int i=1; i<x.size(); i++) 02054 s << ", " << x[i]; 02055 } 02056 s << '}'; 02057 return os << s.str(); 02058 } 02059 02060 template<class Char, class Traits, class View> 02061 std::basic_ostream<Char,Traits>& 02062 operator <<(std::basic_ostream<Char,Traits>& os, 02063 const ViewArray<View>& x) { 02064 std::basic_ostringstream<Char,Traits> s; 02065 s.copyfmt(os); s.width(0); 02066 s << '{'; 02067 if (x.size() > 0) { 02068 s << x[0]; 02069 for (int i=1; i<x.size(); i++) 02070 s << ", " << x[i]; 02071 } 02072 s << '}'; 02073 return os << s.str(); 02074 } 02075 02076 template<class Char, class Traits, class T> 02077 std::basic_ostream<Char,Traits>& 02078 operator <<(std::basic_ostream<Char,Traits>& os, 02079 const ArgArrayBase<T>& x) { 02080 std::basic_ostringstream<Char,Traits> s; 02081 s.copyfmt(os); s.width(0); 02082 s << '{'; 02083 if (x.size() > 0) { 02084 s << x[0]; 02085 for (int i=1; i<x.size(); i++) 02086 s << ", " << x[i]; 02087 } 02088 s << '}'; 02089 return os << s.str(); 02090 } 02091 02092 } 02093 02094 // STATISTICS: kernel-other