Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
57 kB · 2047 lines
C++
at develop
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * Guido Tack <tack@gecode.org> * * Contributing authors: * Gregory Crosswhite <gcross@phys.washington.edu> * * Copyright: * Gregory Crosswhite, 2011 * Christian Schulte, 2003 * Guido Tack, 2004 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <iostream>#include <iterator>#include <vector>#include <sstream>#include <initializer_list>
namespace Gecode { namespace Kernel {
/// Occurence information for a view template<class View> class ViewOcc { public: /// The view View x; /// The original index in the array int i; /// Sorting order bool operator <(const ViewOcc& y) const; };
template<class View> forceinline bool ViewOcc<View>::operator <(const ViewOcc& y) const { return x < y.x; }
/// Check whether \a p has duplicates among its \a n elements (changes \a p) GECODE_KERNEL_EXPORT bool duplicates(void** p, int n);
/// Check whether \a p has common elements with \a q GECODE_KERNEL_EXPORT bool duplicates(void** p, int n, void** q, int m);
}}
namespace Gecode {
template<class Var> class VarArray; template<class Var> class VarArgArray;
/** \brief Traits of arrays in %Gecode * * This class collects the traits of an array in Gecode. * The traits used are the following. * - <code>typedef Type StorageType</code> where \c Type is the type * of an appropriate storage type for this array. * - <code>typedef Type ValueType</code> where \c Type is the type * of the elements of this array. * - <code>typedef Type ArgsType</code> where \c Type is the type * of the appropriate Args-array type (e.g., \c BoolVarArgs if \c A is * \c BoolVarArray). */ template<class A> class ArrayTraits {};
/** * \brief %Variable arrays * * %Variable arrays store variables. They are typically used * for storing the variables being part of a solution. * * Never use them for temporary purposes, use argument arrays * instead. * * %Variable arrays can be enlarged dynamically. For memory efficiency, the * initial array is allocated in the space. When adding variables, it is * automatically resized and allocated on the heap. * * \ingroup TaskVar */ template<class Var> class VarArray { protected: /// Number of variables (size) int n; /// Array of variables Var* x; public: /// \name Associated types //@{ /// Type of the variable stored in this array typedef Var value_type; /// Type of a reference to the value type typedef Var& reference; /// Type of a constant reference to the value type typedef const Var& const_reference; /// Type of a pointer to the value type typedef Var* pointer; /// Type of a read-only pointer to the value type typedef const Var* const_pointer; /// Type of the iterator used to iterate through this array's elements typedef Var* iterator; /// Type of the iterator used to iterate read-only through this array's elements typedef const Var* const_iterator; /// Type of the iterator used to iterate backwards through this array's elements typedef std::reverse_iterator<Var*> reverse_iterator; /// Type of the iterator used to iterate backwards and read-only through this array's elements typedef std::reverse_iterator<const Var*> const_reverse_iterator; //@}
//@{ /// \name Constructors and initialization //@{ /// Default constructor (array of size 0) VarArray(void); /// Allocate array with \a m variables VarArray(Space& home, int m); /// Initialize from variable argument array \a a (copy elements) VarArray(Space& home, const VarArgArray<Var>&); /// Initialize from variable array \a a (share elements) VarArray(const VarArray<Var>& a); /// Initialize from variable array \a a (share elements) const VarArray<Var>& operator =(const VarArray<Var>& a); //@}
/// \name Array size //@{ /// Return size of array (number of elements) int size(void) const; //@}
/// \name Array elements //@{ /// Return variable at position \a i Var& operator [](int i); /// Return variable at position \a i const Var& operator [](int i) const; /** Return slice \f$y\f$ of length at most \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$ * * If \a n is -1, then all possible elements starting from \a start * with increment \a inc are returned. */ typename ArrayTraits<VarArgArray<Var>>::ArgsType slice(int start, int inc=1, int n=-1); //@}
/// \name Array iteration //@{ /// Return an iterator at the beginning of the array iterator begin(void); /// Return a read-only iterator at the beginning of the array const_iterator begin(void) const; /// Return an iterator past the end of the array iterator end(void); /// Return a read-only iterator past the end of the array const_iterator end(void) const; /// Return a reverse iterator at the end of the array reverse_iterator rbegin(void); /// Return a reverse and read-only iterator at the end of the array const_reverse_iterator rbegin(void) const; /// Return a reverse iterator past the beginning of the array reverse_iterator rend(void); /// Return a reverse and read-only iterator past the beginning of the array const_reverse_iterator rend(void) const; //@}
/// Test if all variables are assigned bool assigned(void) const;
/// \name Cloning //@{ /// Update array to be a clone of array \a a void update(Space& home, VarArray<Var>& a); //@}
/// Allocate memory from heap (disabled) static void* operator new(size_t s) = delete; /// Free memory allocated from heap (disabled) static void operator delete(void* p) = delete; };
/** Concatenate \a x and \a y and return result * \relates VarArray */ template<class T> typename ArrayTraits<VarArray<T>>::ArgsType operator +(const VarArray<T>& x, const VarArgArray<T>& y);
/** Concatenate \a x and \a y and return result * \relates VarArray */ template<class T> typename ArrayTraits<VarArray<T>>::ArgsType operator +(const VarArray<T>& x, const VarArray<T>& y);
/** Concatenate \a x and \a y and return result * \relates VarArray */ template<class T> typename ArrayTraits<VarArray<T>>::ArgsType operator +(const VarArgArray<T>& x, const VarArray<T>& y);
/** Concatenate \a x and \a y and return result * \relates VarArray */ template<class T> typename ArrayTraits<VarArray<T>>::ArgsType operator +(const VarArray<T>& x, const T& y);
/** Concatenate \a x and \a y and return result * \relates VarArray */ template<class T> typename ArrayTraits<VarArray<T>>::ArgsType operator +(const T& x, const VarArray<T>& y);
/** * \brief View arrays * * View arrays store views. They are typically used for storing the * views with which propagators and branchers compute. * \ingroup TaskActor */ template<class View> class ViewArray { private: /// Number of views (size) int n; /// Views View* x; public: /// \name Associated types //@{ /// Type of the view stored in this array typedef View value_type; /// Type of a reference to the value type typedef View& reference; /// Type of a constant reference to the value type typedef const View& const_reference; /// Type of a pointer to the value type typedef View* pointer; /// Type of a read-only pointer to the value type typedef const View* const_pointer; /// Type of the iterator used to iterate through this array's elements typedef View* iterator; /// Type of the iterator used to iterate read-only through this array's elements typedef const View* const_iterator; /// Type of the iterator used to iterate backwards through this array's elements typedef std::reverse_iterator<View*> reverse_iterator; /// Type of the iterator used to iterate backwards and read-only through this array's elements typedef std::reverse_iterator<const View*> const_reverse_iterator; //@}
/// \name Constructors and initialization //@{ /// Default constructor (array of size 0) ViewArray(void); /// Allocate array with \a m views ViewArray(Space& home, int m); /// Allocate array with \a m views ViewArray(Region& r, int m); /// Initialize from view array \a a (share elements) ViewArray(const ViewArray<View>& a); /// Initialize from view array \a a (copy elements) ViewArray(Space& home, const ViewArray<View>& a); /// Initialize from view array \a a (copy elements) ViewArray(Region& r, const ViewArray<View>& a); /// Initialize from view array \a a (share elements) const ViewArray<View>& operator =(const ViewArray<View>& a); /** * \brief Initialize from variable argument array \a a (copy elements) * * Note that the view type \a View must provide a constructor * for the associated \a Var type. */ template<class Var> ViewArray(Space& home, const VarArgArray<Var>& a) : n(a.size()) { // This may not be in the hpp file (to satisfy the MS compiler) if (n>0) { x = home.alloc<View>(n); for (int i=0; i<n; i++) x[i]=a[i]; } else { x = nullptr; } } /** * \brief Initialize from variable argument array \a a (copy elements) * * Note that the view type \a View must provide a constructor * for the associated \a Var type. */ template<class Var> ViewArray(Region& r, const VarArgArray<Var>& a) : n(a.size()) { // This may not be in the hpp file (to satisfy the MS compiler) if (n>0) { x = r.alloc<View>(n); for (int i=0; i<n; i++) x[i]=a[i]; } else { x = nullptr; } } //@}
/// \name Array size //@{ /// Return size of array (number of elements) int size(void) const; /// Decrease size of array (number of elements) void size(int n); //@}
/// \name Array elements //@{ /// Return view at position \a i View& operator [](int i); /// Return view at position \a i const View& operator [](int i) const; //@}
/// \name Array iteration //@{ /// Return an iterator at the beginning of the array iterator begin(void); /// Return a read-only iterator at the beginning of the array const_iterator begin(void) const; /// Return an iterator past the end of the array iterator end(void); /// Return a read-only iterator past the end of the array const_iterator end(void) const; /// Return a reverse iterator at the end of the array reverse_iterator rbegin(void); /// Return a reverse and read-only iterator at the end of the array const_reverse_iterator rbegin(void) const; /// Return a reverse iterator past the beginning of the array reverse_iterator rend(void); /// Return a reverse and read-only iterator past the beginning of the array const_reverse_iterator rend(void) const; //@}
/// \name Dependencies //@{ /** * \brief Subscribe propagator \a p with propagation condition \a pc to variable * * In case \a process is false, the propagator is just subscribed but * not scheduled for execution (this must be used when creating * subscriptions during propagation). */ void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); /// Cancel subscription of propagator \a p with propagation condition \a pc to all views void cancel(Space& home, Propagator& p, PropCond pc); /// Subscribe advisor \a a to variable void subscribe(Space& home, Advisor& a); /// Cancel subscription of advisor \a a void cancel(Space& home, Advisor& a); /// Re-schedule propagator \a p with propagation condition \a pc void reschedule(Space& home, Propagator& p, PropCond pc); //@}
/// \name Cloning //@{ /// Update array to be a clone of array \a a void update(Space& home, ViewArray<View>& a); //@}
/// \name Moving elements //@{ /// Move view from position 0 to position \a i (shift elements to the left) void move_fst(int i); /// Move view from position \c size()-1 to position \a i (truncate array by one) void move_lst(int i); /** \brief Move view from position 0 to position \a i (shift elements to the left) * * Before moving, cancel subscription of propagator \a p with * propagation condition \a pc to view at position \a i. */ void move_fst(int i, Space& home, Propagator& p, PropCond pc); /** \brief Move view from position \c size()-1 to position \a i (truncate array by one) * * Before moving, cancel subscription of propagator \a p with * propagation condition \a pc to view at position \a i. */ void move_lst(int i, Space& home, Propagator& p, PropCond pc); /** \brief Move view from position 0 to position \a i (shift elements to the left) * * Before moving, cancel subscription of advisor \a a * to view at position \a i. */ void move_fst(int i, Space& home, Advisor& a); /** \brief Move view from position \c size()-1 to position \a i (truncate array by one) * * Before moving, cancel subscription of advisor \a a to view * at position \a i. */ void move_lst(int i, Space& home, Advisor& a); //@}
/// \name Dropping elements //@{ /// Drop views from positions 0 to \a i-1 from array void drop_fst(int i); /// Drop views from positions \a i+1 to \c size()-1 from array void drop_lst(int i); /** \brief Drop views from positions 0 to \a i-1 from array * * Before moving, cancel subscription of propagator \a p with * propagation condition \a pc to views at positions 0 to \a i-1. */ void drop_fst(int i, Space& home, Propagator& p, PropCond pc); /** \brief Drop assigned views from positions \a i+1 to \c size()-1 from array * * Before moving, cancel subscription of propagator \a p with * propagation condition \a pc to views at positions \a i+1 to * \c size()-1. */ void drop_lst(int i, Space& home, Propagator& p, PropCond pc); /** \brief Drop views from positions 0 to \a i-1 from array * * Before moving, cancel subscription of advisor \a a to views at * positions 0 to \a i-1. */ void drop_fst(int i, Space& home, Advisor& a); /** \brief Drop assigned views from positions \a i+1 to \c size()-1 from array * * Before moving, cancel subscription of advisor \a a to views at * positions \a i+1 to \c size()-1. */ void drop_lst(int i, Space& home, Advisor& a); //@}
/// Test if all variables are assigned bool assigned(void) const;
/// \name View equality //@{ /** * \brief Test whether array has multiple occurence of the same view * * Note that assigned views are ignored. */ bool same(void) const; /** * \brief Test whether array contains a view being the same as \a y * * Note that assigned views are ignored. */ bool same(const View& y) const; /// Remove all duplicate views from array (changes element order) void unique(void); //@}
/// Allocate memory from heap (disabled) static void* operator new(size_t s) = delete; /// Free memory allocated from heap (disabled) static void operator delete(void* p) = delete; };
/** * \brief Test whether array \a x together with array \a y contains shared views * * Note that assigned views are ignored. * \relates ViewArray */ template<class ViewX, class ViewY> bool shared(ViewArray<ViewX> x, ViewArray<ViewY> y); /** * \brief Test whether array \a x contains a view shared with \a y * * Note that assigned views are ignored. * \relates ViewArray */ template<class ViewX, class ViewY> bool shared(ViewArray<ViewX> x, ViewY y); /** * \brief Test whether array \a y contains a view shared with \a x * * Note that assigned views are ignored. * \relates ViewArray */ template<class ViewX, class ViewY> bool shared(ViewX x, ViewArray<ViewY> y); /** * \brief Test whether array \a x contains shared views * * Note that assigned views are ignored. * \relates ViewArray */ template<class View> bool shared(ViewArray<View> x);
/** * \brief Base-class for argument arrays * * Argument arrays are used as convenient mechanism of passing arguments * when calling functions as they combine both the size and the elements * of an array. For a small number of elements, memory is allocated by * creating an argument array object. Otherwise the memory is allocated * from the heap. * * \ingroup TaskVar */ template<class T> class ArgArrayBase { protected: /// Number of elements int n; /// Allocated size of the array int capacity; /// Element array T* a; /// How many elements are possible inside array static const int onstack_size = 16; /// In-array storage for elements T onstack[onstack_size]; /// Allocate memory for \a n elements T* allocate(int n); /// Resize to hold at least \a i additional elements void resize(int i); /// Return this array concatenated with \a x template<class A> A concat(const ArgArrayBase<T>& x) const; /// Return this array concatenated with \a x template<class A> A concat(const T& x) const; /// Insert a new element \a x at the end of the array (increase size by 1) template<class A> A& append(const T& x); /// Append \a x to the end of the array template<class A> A& append(const ArgArrayBase<T>& x); /** Return slice \f$y\f$ of length at most \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$ * * If \a n is -1, then all possible elements starting from \a start * with increment \a inc are returned. */ template<class A> A slice(int start, int inc=1, int n=-1); public: /// \name Associated types //@{ /// Type of the view stored in this array typedef T value_type; /// Type of a reference to the value type typedef T& reference; /// Type of a constant reference to the value type typedef const T& const_reference; /// Type of a pointer to the value type typedef T* pointer; /// Type of a read-only pointer to the value type typedef const T* const_pointer; /// Type of the iterator used to iterate through this array's elements typedef T* iterator; /// Type of the iterator used to iterate read-only through this array's elements typedef const T* const_iterator; /// Type of the iterator used to iterate backwards through this array's elements typedef std::reverse_iterator<T*> reverse_iterator; /// Type of the iterator used to iterate backwards and read-only through this array's elements typedef std::reverse_iterator<const T*> const_reverse_iterator; //@}
/// \name Constructors and initialization //@{ /// Allocate empty array ArgArrayBase(void); /// Allocate array with \a n elements explicit ArgArrayBase(int n); /// Initialize from argument array \a a (copy elements) ArgArrayBase(const ArgArrayBase<T>& a); /// Initialize from view array \a a (copy elements) const ArgArrayBase<T>& operator =(const ArgArrayBase<T>& a); /// Initialize from vector \a a ArgArrayBase(const std::vector<T>& a); /// Initialize from initializer list \a a ArgArrayBase(std::initializer_list<T> a); /// Initialize from InputIterator \a begin and \a end template<class InputIterator> ArgArrayBase(InputIterator first, InputIterator last); //@}
/// \name Array size //@{ /// Return size of array (number of elements) int size(void) const; //@}
/// \name Array elements //@{ /// Return element at position \a i T& operator [](int i); /// Return element at position \a i const T& operator [](int i) const; //@}
/// \name Array iteration //@{ /// Return an iterator at the beginning of the array iterator begin(void); /// Return a read-only iterator at the beginning of the array const_iterator begin(void) const; /// Return an iterator past the end of the array iterator end(void); /// Return a read-only iterator past the end of the array const_iterator end(void) const; /// Return a reverse iterator at the end of the array reverse_iterator rbegin(void); /// Return a reverse and read-only iterator at the end of the array const_reverse_iterator rbegin(void) const; /// Return a reverse iterator past the beginning of the array reverse_iterator rend(void); /// Return a reverse and read-only iterator past the beginning of the array const_reverse_iterator rend(void) const; //@}
/// \name Destructor //@{ /// Destructor ~ArgArrayBase(void); //@} };
template<class> class ArgArray;
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const ArgArray<T>& x, const ArgArray<T>& y);
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const ArgArray<T>& x, const T& y);
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const T& x, const ArgArray<T>& y);
/** * \brief Argument array for non-primitive types * * Argument arrays are used as convenient mechanism of passing arguments * when calling functions as they combine both the size and the elements * of an array. For a small number of elements, memory is allocated by * creating an argument array object. Otherwise the memory is allocated * from the heap. * * \ingroup TaskVar */ template<class T> class ArgArray : public ArgArrayBase<T> { protected: using ArgArrayBase<T>::a; public: using ArgArrayBase<T>::size; /// \name Constructors and initialization //@{ /// Allocate empty array ArgArray(void); /// Allocate array with \a n elements explicit ArgArray(int n); /// Allocate array with \a n elements and initialize with elements from array \a e ArgArray(int n, const T* e); /// Initialize from argument array \a a (copy elements) ArgArray(const ArgArray<T>& a); /// Initialize from vector \a a ArgArray(const std::vector<T>& a); /// Initialize from initializer list \a a ArgArray(std::initializer_list<T> a); /// Initialize from InputIterator \a first and \a last template<class InputIterator> ArgArray(InputIterator first, InputIterator last); //@} /// \name Array elements //@{ /// Return slice \f$y\f$ of length \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$ typename ArrayTraits<ArgArray<T>>::ArgsType slice(int start, int inc=1, int n=-1); //@} /// \name Appending elements //@{ /// Insert a new element \a x at the end of the array (increase size by 1) typename ArrayTraits<ArgArray<T>>::ArgsType& operator <<(const T& x); /// Append \a x to the end of the array typename ArrayTraits<ArgArray<T>>::ArgsType& operator <<(const ArgArray<T>& x); //@}
friend typename ArrayTraits<ArgArray<T>>::ArgsType operator + <>(const ArgArray<T>& x, const ArgArray<T>& y); friend typename ArrayTraits<ArgArray<T>>::ArgsType operator + <>(const ArgArray<T>& x, const T& y); friend typename ArrayTraits<ArgArray<T>>::ArgsType operator + <>(const T& x, const ArgArray<T>& y); };
template<class> class VarArgArray;
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y);
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const VarArgArray<Var>& x, const Var& y);
/** Concatenate \a x and \a y and return result * \relates ArgArray */ template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const Var& x, const VarArgArray<Var>& y);
/** * \brief Argument array for variables * * Argument arrays are used as convenient mechanism of passing arguments * when calling functions as they combine both the size and the elements * of an array. For a small number of elements, memory is allocated by * creating an argument array object. Otherwise the memory is allocated * from the heap. * * \ingroup TaskVar */ template<class Var> class VarArgArray : public ArgArrayBase<Var> { protected: using ArgArrayBase<Var>::a; using ArgArrayBase<Var>::n; public: using ArgArrayBase<Var>::size; /// \name Constructors and initialization //@{ /// Allocate empty array VarArgArray(void); /// Allocate array with \a n elements explicit VarArgArray(int n); /// Initialize from variable argument array \a a (copy elements) VarArgArray(const VarArgArray<Var>& a); /// Initialize from variable array \a a (copy elements) VarArgArray(const VarArray<Var>& a); /// Initialize from vector \a a VarArgArray(const std::vector<Var>& a); /// Initialize from initializer list \a a VarArgArray(std::initializer_list<Var> a); /// Initialize from InputIterator \a first and \a last template<class InputIterator> VarArgArray(InputIterator first, InputIterator last); //@} /// \name Array elements //@{ /// Return slice \f$y\f$ of length \a n such that forall \f$0\leq i<n\f$, \f$y_i=x_{\text{start}+i\cdot\text{inc}}\f$ typename ArrayTraits<VarArgArray<Var>>::ArgsType slice(int start, int inc=1, int n=-1); //@} /// \name Appending elements //@{ /// Insert a new element \a x at the end of the array (increase size by 1) typename ArrayTraits<VarArgArray<Var>>::ArgsType& operator <<(const Var& x); /// Append \a x to the end of the array typename ArrayTraits<VarArgArray<Var>>::ArgsType& operator <<(const VarArgArray<Var>& x); //@}
/// Test if all variables are assigned bool assigned(void) const;
friend typename ArrayTraits<VarArgArray<Var>>::ArgsType operator + <>(const VarArgArray<Var>& x, const VarArgArray<Var>& y); friend typename ArrayTraits<VarArgArray<Var>>::ArgsType operator + <>(const VarArgArray<Var>& x, const Var& y); friend typename ArrayTraits<VarArgArray<Var>>::ArgsType operator + <>(const Var& x, const VarArgArray<Var>& y); };
/** * \brief Test whether array \a x together with array \a y contains at least one variable being the same * * Note that assigned variables are ignored. * \relates VarArgArray */ template<class Var> bool same(VarArgArray<Var> x, VarArgArray<Var> y); /** * \brief Test whether array \a x contains variable \a y * * Note that assigned variables are ignored. * \relates VarArgArray */ template<class Var> bool same(VarArgArray<Var> x, Var y); /** * \brief Test whether array \a y contains variable \a x * * Note that assigned variables are ignored. * \relates VarArgArray */ template<class Var> bool same(Var x, VarArgArray<Var> y); /** * \brief Test whether array \a x contains a variable multiply * * Note that assigned variables are ignored. * \relates VarArgArray */ template<class Var> bool same(VarArgArray<Var> x);
/** * \brief Print array elements enclosed in curly brackets * \relates VarArray */ template<class Char, class Traits, class Var> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const VarArray<Var>& x);
/** * \brief Print array elements enclosed in curly brackets * \relates ViewArray */ template<class Char, class Traits, class View> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x);
/** * \brief Print array elements enclosed in curly brackets * \relates ArgArrayBase */ template<class Char, class Traits, class T> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x);
/* * Implementation * */
/* * Variable arrays * * These arrays are allocated in the space. * */
template<class Var> forceinline VarArray<Var>::VarArray(void) : n(0), x(nullptr) {}
template<class Var> forceinline VarArray<Var>::VarArray(Space& home, int n0) : n(n0) { // Allocate from space x = (n>0) ? home.alloc<Var>(n) : nullptr; }
template<class Var> forceinline VarArray<Var>::VarArray(const VarArray<Var>& a) { n = a.n; x = a.x; }
template<class Var> inline const VarArray<Var>& VarArray<Var>::operator =(const VarArray<Var>& a) { n = a.n; x = a.x; return *this; }
template<class Var> forceinline int VarArray<Var>::size(void) const { return n; }
template<class Var> forceinline Var& VarArray<Var>::operator [](int i) { assert((i >= 0) && (i < size())); return x[i]; }
template<class Var> forceinline const Var& VarArray<Var>::operator [](int i) const { assert((i >= 0) && (i < size())); return x[i]; }
template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType VarArray<Var>::slice(int start, int inc, int maxN) { assert(n==0 || start < n); if (n==0 || maxN<0) maxN = n; int s; if (inc == 0) s = n-start; else if (inc > 0) s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); else s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); typename ArrayTraits<VarArgArray<Var>>::ArgsType r(std::min(maxN,s)); for (int i=0; i<r.size(); i++, start+=inc) r[i] = x[start]; return r; }
template<class Var> forceinline typename VarArray<Var>::iterator VarArray<Var>::begin(void) { return x; }
template<class Var> forceinline typename VarArray<Var>::const_iterator VarArray<Var>::begin(void) const { return x; }
template<class Var> forceinline typename VarArray<Var>::iterator VarArray<Var>::end(void) { return x+n; }
template<class Var> forceinline typename VarArray<Var>::const_iterator VarArray<Var>::end(void) const { return x+n; }
template<class Var> forceinline typename VarArray<Var>::reverse_iterator VarArray<Var>::rbegin(void) { return reverse_iterator(x+n); }
template<class Var> forceinline typename VarArray<Var>::const_reverse_iterator VarArray<Var>::rbegin(void) const { return const_reverse_iterator(x+n); }
template<class Var> forceinline typename VarArray<Var>::reverse_iterator VarArray<Var>::rend(void) { return reverse_iterator(x); }
template<class Var> forceinline typename VarArray<Var>::const_reverse_iterator VarArray<Var>::rend(void) const { return const_reverse_iterator(x); }
template<class Var> forceinline void VarArray<Var>::update(Space& home, VarArray<Var>& a) { n = a.n; if (n > 0) { x = home.alloc<Var>(n); for (int i=0; i<n; i++) x[i].update(home, a.x[i]); } else { x = nullptr; } }
template<class Var> forceinline bool VarArray<Var>::assigned(void) const { for (int i=0; i<n; i++) if (!x[i].assigned()) return false; return true; }
template<class Var> typename ArrayTraits<VarArray<Var>>::ArgsType operator +(const VarArray<Var>& x, const VarArray<Var>& y) { typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size()); for (int i=0; i<x.size(); i++) r[i] = x[i]; for (int i=0; i<y.size(); i++) r[x.size()+i] = y[i]; return r; }
template<class Var> typename ArrayTraits<VarArray<Var>>::ArgsType operator +(const VarArray<Var>& x, const VarArgArray<Var>& y) { typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size()); for (int i=0; i<x.size(); i++) r[i] = x[i]; for (int i=0; i<y.size(); i++) r[x.size()+i] = y[i]; return r; }
template<class Var> typename ArrayTraits<VarArray<Var>>::ArgsType operator +(const VarArgArray<Var>& x, const VarArray<Var>& y) { typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+y.size()); for (int i=0; i<x.size(); i++) r[i] = x[i]; for (int i=0; i<y.size(); i++) r[x.size()+i] = y[i]; return r; }
template<class Var> typename ArrayTraits<VarArray<Var>>::ArgsType operator +(const VarArray<Var>& x, const Var& y) { typename ArrayTraits<VarArray<Var>>::ArgsType r(x.size()+1); for (int i=0; i<x.size(); i++) r[i] = x[i]; r[x.size()] = y; return r; }
template<class Var> typename ArrayTraits<VarArray<Var>>::ArgsType operator +(const Var& x, const VarArray<Var>& y) { typename ArrayTraits<VarArray<Var>>::ArgsType r(y.size()+1); r[0] = x; for (int i=0; i<y.size(); i++) r[1+i] = y[i]; return r; }
/* * View arrays * */
template<class View> forceinline ViewArray<View>::ViewArray(void) : n(0), x(nullptr) {}
template<class View> forceinline ViewArray<View>::ViewArray(Space& home, int n0) : n(n0) { x = (n>0) ? home.alloc<View>(n) : nullptr; } template<class View> forceinline ViewArray<View>::ViewArray(Region& r, int n0) : n(n0) { x = (n>0) ? r.alloc<View>(n) : nullptr; }
template<class View> ViewArray<View>::ViewArray(Space& home, const ViewArray<View>& a) : n(a.size()) { if (n>0) { x = home.alloc<View>(n); for (int i=0; i<n; i++) x[i] = a[i]; } else { x = nullptr; } } template<class View> ViewArray<View>::ViewArray(Region& r, const ViewArray<View>& a) : n(a.size()) { if (n>0) { x = r.alloc<View>(n); for (int i=0; i<n; i++) x[i] = a[i]; } else { x = nullptr; } }
template<class View> forceinline ViewArray<View>::ViewArray(const ViewArray<View>& a) : n(a.n), x(a.x) {}
template<class View> forceinline const ViewArray<View>& ViewArray<View>::operator =(const ViewArray<View>& a) { n = a.n; x = a.x; return *this; }
template<class View> forceinline int ViewArray<View>::size(void) const { return n; }
template<class View> forceinline void ViewArray<View>::size(int n0) { n = n0; }
template<class View> forceinline View& ViewArray<View>::operator [](int i) { assert((i >= 0) && (i < size())); return x[i]; }
template<class View> forceinline const View& ViewArray<View>::operator [](int i) const { assert((i >= 0) && (i < size())); return x[i]; }
template<class View> forceinline typename ViewArray<View>::iterator ViewArray<View>::begin(void) { return x; }
template<class View> forceinline typename ViewArray<View>::const_iterator ViewArray<View>::begin(void) const { return x; }
template<class View> forceinline typename ViewArray<View>::iterator ViewArray<View>::end(void) { return x+n; }
template<class View> forceinline typename ViewArray<View>::const_iterator ViewArray<View>::end(void) const { return x+n; }
template<class View> forceinline typename ViewArray<View>::reverse_iterator ViewArray<View>::rbegin(void) { return reverse_iterator(x+n); }
template<class View> forceinline typename ViewArray<View>::const_reverse_iterator ViewArray<View>::rbegin(void) const { return const_reverse_iterator(x+n); }
template<class View> forceinline typename ViewArray<View>::reverse_iterator ViewArray<View>::rend(void) { return reverse_iterator(x); }
template<class View> forceinline typename ViewArray<View>::const_reverse_iterator ViewArray<View>::rend(void) const { return const_reverse_iterator(x); }
template<class View> forceinline void ViewArray<View>::move_fst(int i) { x[i]=x[0]; x++; n--; }
template<class View> forceinline void ViewArray<View>::move_lst(int i) { n--; x[i]=x[n]; }
template<class View> forceinline void ViewArray<View>::drop_fst(int i) { assert(i>=0); x += i; n -= i; }
template<class View> forceinline void ViewArray<View>::drop_lst(int i) { assert(i<n); n = i+1; }
template<class View> forceinline void ViewArray<View>::move_fst(int i, Space& home, Propagator& p, PropCond pc) { // Move x[0] to x[i] x[i].cancel(home,p,pc); x[i]=x[0]; x++; n--; }
template<class View> forceinline void ViewArray<View>::move_lst(int i, Space& home, Propagator& p, PropCond pc) { // Move x[n-1] to x[i] x[i].cancel(home,p,pc); n--; x[i]=x[n]; }
template<class View> void ViewArray<View>::drop_fst(int i, Space& home, Propagator& p, PropCond pc) { // Drop elements from 0..i-1 assert(i>=0); for (int j=0; j<i; j++) x[j].cancel(home,p,pc); x += i; n -= i; }
template<class View> void ViewArray<View>::drop_lst(int i, Space& home, Propagator& p, PropCond pc) { // Drop elements from i+1..n-1 assert(i<n); for (int j=i+1; j<n; j++) x[j].cancel(home,p,pc); n = i+1; }
template<class View> forceinline void ViewArray<View>::move_fst(int i, Space& home, Advisor& a) { // Move x[0] to x[i] x[i].cancel(home,a); x[i]=x[0]; x++; n--; }
template<class View> forceinline void ViewArray<View>::move_lst(int i, Space& home, Advisor& a) { // Move x[n-1] to x[i] x[i].cancel(home,a); n--; x[i]=x[n]; }
template<class View> void ViewArray<View>::drop_fst(int i, Space& home, Advisor& a) { // Drop elements from 0..i-1 assert(i>=0); for (int j=0; j<i; j++) x[j].cancel(home,a); x += i; n -= i; }
template<class View> void ViewArray<View>::drop_lst(int i, Space& home, Advisor& a) { // Drop elements from i+1..n-1 assert(i<n); for (int j=i+1; j<n; j++) x[j].cancel(home,a); n = i+1; }
template<class View> void ViewArray<View>::update(Space& home, ViewArray<View>& y) { n = y.n; if (n > 0) { x = home.alloc<View>(n); for (int i=0; i<n; i++) x[i].update(home, y.x[i]); } else { x = nullptr; } }
template<class View> void ViewArray<View>::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) { for (int i=0; i<n; i++) x[i].subscribe(home,p,pc,schedule); }
template<class View> void ViewArray<View>::cancel(Space& home, Propagator& p, PropCond pc) { for (int i=0; i<n; i++) x[i].cancel(home,p,pc); }
template<class View> void ViewArray<View>::subscribe(Space& home, Advisor& a) { for (int i=0; i<n; i++) x[i].subscribe(home,a); }
template<class View> void ViewArray<View>::cancel(Space& home, Advisor& a) { for (int i=0; i<n; i++) x[i].cancel(home,a); }
template<class View> void ViewArray<View>::reschedule(Space& home, Propagator& p, PropCond pc) { for (int i=0; i<n; i++) x[i].reschedule(home,p,pc); }
template<class View> forceinline bool ViewArray<View>::assigned(void) const { for (int i=0; i<n; i++) if (!x[i].assigned()) return false; return true; }
template<class View> bool ViewArray<View>::same(void) const { if (n < 2) return false; Region r; View* y = r.alloc<View>(n); int j=0; for (int i=0; i<n; i++) if (!x[i].assigned()) y[j++] = x[i]; if (j < 2) return false; Support::quicksort<View>(y,j); for (int i=1; i<j; i++) if (y[i-1] == y[i]) return true; return false; }
template<class View> bool ViewArray<View>::same(const View& y) const { if (y.assigned()) return false; for (int i=0; i<n; i++) if (x[i] == y) return true; return false; }
template<class View> void ViewArray<View>::unique(void) { if (n < 2) return; Region r; Kernel::ViewOcc<View>* o = r.alloc<Kernel::ViewOcc<View>>(n); for (int i=0; i<n; i++) { o[i].x = x[i]; o[i].i = i; } Support::quicksort<Kernel::ViewOcc<View>>(o,n); // Assign bucket numbers int* bkt = r.alloc<int>(n); int b = 0; bkt[o[0].i] = b; for (int i=1; i<n; i++) { if (o[i-1].x != o[i].x) b++; bkt[o[i].i] = b; } // Eliminate duplicate elements Support::BitSet<Region> seen(r,static_cast<unsigned int>(b+1)); int j=0; for (int i=0; i<n; i++) if (!seen.get(static_cast<unsigned int>(bkt[i]))) { x[j++]=x[i]; seen.set(static_cast<unsigned int>(bkt[i])); } else { x[j]=x[i]; } assert(j == b+1); n = j; }
/* * Sharing for view arrays * */ template<class ViewX, class ViewY> bool shared(ViewArray<ViewX> x, ViewArray<ViewY> y) { if ((x.size() == 0) || (y.size() == 0)) return false; Region r; void** px = r.alloc<void*>(x.size()); int j=0; for (int i=0; i<x.size(); i++) if (!x[i].assigned() && x[i].varimp()) px[j++] = x[i].varimp(); if (j == 0) return false; void** py = r.alloc<void*>(y.size()); int k=0; for (int i=0; i<y.size(); i++) if (!y[i].assigned() && y[i].varimp()) py[k++] = y[i].varimp(); if (k == 0) return false; return Kernel::duplicates(px,j,py,k); }
template<class ViewX, class ViewY> bool shared(ViewArray<ViewX> x, ViewY y) { if (y.assigned() || !y.varimp()) return false; for (int i=0; i<x.size(); i++) if (!x[i].assigned() && x[i].varimp() && (x[i].varimp() == y.varimp())) return true; return false; }
template<class ViewX, class ViewY> forceinline bool shared(ViewX x, ViewArray<ViewY> y) { return shared(y,x); }
template<class View> bool shared(ViewArray<View> x) { if (x.size() < 2) return false; Region r; void** px = r.alloc<void*>(x.size()); int j=0; for (int i=0; i<x.size(); i++) if (!x[i].assigned() && x[i].varimp()) px[j++] = x[i].varimp(); return (j > 2) && Kernel::duplicates(px,j); }
/* * Argument arrays: base class * */
template<class T> forceinline T* ArgArrayBase<T>::allocate(int n) { return (n > onstack_size) ? heap.alloc<T>(static_cast<unsigned int>(n)) : &onstack[0]; }
template<class T> forceinline void ArgArrayBase<T>::resize(int i) { if (n+i >= capacity) { assert(n+i >= onstack_size); int newCapacity = (3*capacity)/2; if (newCapacity <= n+i) newCapacity = n+i; T* newA = allocate(newCapacity); heap.copy<T>(newA,a,n); if (capacity > onstack_size) heap.free(a,capacity); capacity = newCapacity; a = newA; } }
template<class T> forceinline ArgArrayBase<T>::ArgArrayBase(void) : n(0), capacity(onstack_size), a(allocate(0)) {}
template<class T> forceinline ArgArrayBase<T>::ArgArrayBase(int n0) : n(n0), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) {}
template<class T> inline ArgArrayBase<T>::ArgArrayBase(const ArgArrayBase<T>& aa) : n(aa.n), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) { heap.copy<T>(a,aa.a,n); }
template<class T> inline ArgArrayBase<T>::ArgArrayBase(const std::vector<T>& aa) : n(static_cast<int>(aa.size())), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) { heap.copy<T>(a,&aa[0],n); }
template<class T> inline ArgArrayBase<T>::ArgArrayBase(std::initializer_list<T> aa) : n(static_cast<int>(aa.size())), capacity(n < onstack_size ? onstack_size : n), a(allocate(n)) { int i=0; for (const T& x : aa) a[i++]=x; }
template<class T> forceinline ArgArrayBase<T>::~ArgArrayBase(void) { if (capacity > onstack_size) heap.free(a,capacity); }
template<class T> forceinline const ArgArrayBase<T>& ArgArrayBase<T>::operator =(const ArgArrayBase<T>& aa) { if (&aa != this) { if (capacity > onstack_size) heap.free(a,capacity); n = aa.n; capacity = (n < onstack_size ? onstack_size : n); a = allocate(aa.n); heap.copy<T>(a,aa.a,n); } return *this; }
template<class T> forceinline int ArgArrayBase<T>::size(void) const { return n; }
template<class T> forceinline T& ArgArrayBase<T>::operator [](int i) { assert((i>=0) && (i < n)); return a[i]; }
template<class T> forceinline const T& ArgArrayBase<T>::operator [](int i) const { assert((i>=0) && (i < n)); return a[i]; }
template<class T> forceinline typename ArgArrayBase<T>::iterator ArgArrayBase<T>::begin(void) { return a; }
template<class T> forceinline typename ArgArrayBase<T>::const_iterator ArgArrayBase<T>::begin(void) const { return a; }
template<class T> forceinline typename ArgArrayBase<T>::iterator ArgArrayBase<T>::end(void) { return a+n; }
template<class T> forceinline typename ArgArrayBase<T>::const_iterator ArgArrayBase<T>::end(void) const { return a+n; }
template<class T> forceinline typename ArgArrayBase<T>::reverse_iterator ArgArrayBase<T>::rbegin(void) { return reverse_iterator(a+n); }
template<class T> forceinline typename ArgArrayBase<T>::const_reverse_iterator ArgArrayBase<T>::rbegin(void) const { return const_reverse_iterator(a+n); }
template<class T> forceinline typename ArgArrayBase<T>::reverse_iterator ArgArrayBase<T>::rend(void) { return reverse_iterator(a); }
template<class T> forceinline typename ArgArrayBase<T>::const_reverse_iterator ArgArrayBase<T>::rend(void) const { return const_reverse_iterator(a); }
template<class T> template<class A> A ArgArrayBase<T>::slice(int start, int inc, int maxN) { assert(n==0 || start < n); if (n==0 || maxN<0) maxN = n; int s; if (inc == 0) s = n-start; else if (inc > 0) s = (n-start)/inc + ((n-start) % inc == 0 ? 0 : 1); else s = (start+1)/-inc + ((start+1) % -inc == 0 ? 0 : 1); A r(std::min(maxN,s)); for (int i=0; i<r.size(); i++, start+=inc) new (&r[i]) T(a[start]); return r; }
template<class T> template<class A> inline A& ArgArrayBase<T>::append(const T& x) { resize(1); new (&a[n++]) T(x); return static_cast<A&>(*this); }
template<class T> template<class InputIterator> inline ArgArrayBase<T>::ArgArrayBase(InputIterator first, InputIterator last) : n(0), capacity(onstack_size), a(allocate(0)) { while (first != last) { (void) append<ArgArrayBase<T>>(*first); ++first; } }
template<class T> template<class A> inline A& ArgArrayBase<T>::append(const ArgArrayBase<T>& x) { resize(x.size()); for (int i=0; i<x.size(); i++) new (&a[n++]) T(x[i]); return static_cast<A&>(*this); }
template<class T> template<class A> inline A ArgArrayBase<T>::concat(const ArgArrayBase<T>& x) const { A r(n+x.n); for (int i=0; i<n; i++) new (&r[i]) T(a[i]); for (int i=0; i<x.n; i++) new (&r[n+i]) T(x.a[i]); return r; }
template<class T> template<class A> inline A ArgArrayBase<T>::concat(const T& x) const { A r(n+1); for (int i=0; i<n; i++) new (&r[i]) T(a[i]); new (&r[n]) T(x); return r; }
/* * Argument arrays * */
template<class T> forceinline ArgArray<T>::ArgArray(void) {}
template<class T> forceinline ArgArray<T>::ArgArray(int n) : ArgArrayBase<T>(n) {}
template<class T> ArgArray<T>::ArgArray(int n, const T* a0) : ArgArrayBase<T>(n) { for (int i=0; i<n; i++) a[i] = a0[i]; }
template<class T> forceinline ArgArray<T>::ArgArray(const ArgArray<T>& aa) : ArgArrayBase<T>(aa) {}
template<class T> forceinline ArgArray<T>::ArgArray(const std::vector<T>& aa) : ArgArrayBase<T>(aa) {}
template<class T> forceinline ArgArray<T>::ArgArray(std::initializer_list<T> aa) : ArgArrayBase<T>(aa) {}
template<class T> template<class InputIterator> forceinline ArgArray<T>::ArgArray(InputIterator first, InputIterator last) : ArgArrayBase<T>(first,last) {}
template<class T> forceinline typename ArrayTraits<ArgArray<T>>::ArgsType ArgArray<T>::slice(int start, int inc, int maxN) { return ArgArrayBase<T>::template slice <typename ArrayTraits<ArgArray<T>>::ArgsType> (start,inc,maxN); }
template<class T> forceinline typename ArrayTraits<ArgArray<T>>::ArgsType& ArgArray<T>::operator <<(const T& x) { return ArgArrayBase<T>::template append <typename ArrayTraits<ArgArray<T>>::ArgsType>(x); }
template<class T> forceinline typename ArrayTraits<ArgArray<T>>::ArgsType& ArgArray<T>::operator <<(const ArgArray<T>& x) { return ArgArrayBase<T>::template append <typename ArrayTraits<ArgArray<T>>::ArgsType>(x); }
template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const ArgArray<T>& x, const ArgArray<T>& y) { return x.template concat <typename ArrayTraits<ArgArray<T>>::ArgsType>(y); }
template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const ArgArray<T>& x, const T& y) { return x.template concat <typename ArrayTraits<ArgArray<T>>::ArgsType>(y); }
template<class T> typename ArrayTraits<ArgArray<T>>::ArgsType operator +(const T& x, const ArgArray<T>& y) { ArgArray<T> xa(1); xa[0] = x; return xa.template concat <typename ArrayTraits<ArgArray<T>>::ArgsType>(y); }
/* * Argument arrays for variables * */
template<class Var> forceinline VarArgArray<Var>::VarArgArray(void) {}
template<class Var> forceinline VarArgArray<Var>::VarArgArray(int n) : ArgArrayBase<Var>(n) {}
template<class Var> forceinline VarArgArray<Var>::VarArgArray(const VarArgArray<Var>& aa) : ArgArrayBase<Var>(aa) {}
template<class Var> forceinline VarArgArray<Var>::VarArgArray(const std::vector<Var>& aa) : ArgArrayBase<Var>(aa) {}
template<class Var> forceinline VarArgArray<Var>::VarArgArray(std::initializer_list<Var> aa) : ArgArrayBase<Var>(aa) {}
template<class Var> template<class InputIterator> forceinline VarArgArray<Var>::VarArgArray(InputIterator first, InputIterator last) : ArgArrayBase<Var>(first,last) {}
template<class Var> inline VarArgArray<Var>::VarArgArray(const VarArray<Var>& x) : ArgArrayBase<Var>(x.size()) { for (int i=0; i<x.size(); i++) a[i]=x[i]; }
template<class Var> forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType VarArgArray<Var>::slice(int start, int inc, int maxN) { return ArgArrayBase<Var>::template slice <typename ArrayTraits<VarArgArray<Var>>::ArgsType> (start,inc,maxN); }
template<class Var> forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType& VarArgArray<Var>::operator <<(const Var& x) { return ArgArrayBase<Var>::template append <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x); }
template<class Var> forceinline typename ArrayTraits<VarArgArray<Var>>::ArgsType& VarArgArray<Var>::operator <<(const VarArgArray<Var>& x) { return ArgArrayBase<Var>::template append <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(x); }
template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const VarArgArray<Var>& x, const VarArgArray<Var>& y) { return x.template concat <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y); }
template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const VarArgArray<Var>& x, const Var& y) { return x.template concat <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y); }
template<class Var> typename ArrayTraits<VarArgArray<Var>>::ArgsType operator +(const Var& x, const VarArgArray<Var>& y) { VarArgArray<Var> xa(1); xa[0] = x; return xa.template concat <typename ArrayTraits<VarArgArray<Var>>::ArgsType>(y); }
template<class Var> forceinline bool VarArgArray<Var>::assigned(void) const { for (int i=0; i<n; i++) if (!a[i].assigned()) return false; return true; }
/* * Checking for multiple occurences of the same variable * */ template<class Var> bool same(VarArgArray<Var> x, VarArgArray<Var> y) { if ((x.size() == 0) || (y.size() == 0)) return false; Region r; void** px = r.alloc<void*>(x.size()); int j=0; for (int i=0; i<x.size(); i++) if (!x[i].assigned()) px[j++] = x[i].varimp(); if (j == 0) return false; void** py = r.alloc<void*>(y.size()); int k=0; for (int i=0; i<y.size(); i++) if (!y[i].assigned()) py[k++] = y[i].varimp(); if (k == 0) return false; return Kernel::duplicates(px,j,py,k); }
template<class Var> bool same(VarArgArray<Var> x, Var y) { if (y.assigned()) return false; for (int i=0; i<x.size(); i++) if (x[i].varimp() == y.varimp()) return true; return false; }
template<class Var> forceinline bool same(Var x, VarArgArray<Var> y) { return same(y,x); }
template<class Var> bool same(VarArgArray<Var> x) { if (x.size() < 2) return false; Region r; void** px = r.alloc<void*>(x.size()); int j=0; for (int i=0; i<x.size(); i++) if (!x[i].assigned()) px[j++] = x[i].varimp(); return (j > 1) && Kernel::duplicates(px,j); }
/* * Interdependent code * */
template<class Var> inline VarArray<Var>::VarArray(Space& home, const VarArgArray<Var>& a) : n(a.size()) { if (n>0) { x = home.alloc<Var>(n); for (int i=0; i<n; i++) x[i] = a[i]; } else { x = nullptr; } }
/* * Printing of arrays * */ template<class Char, class Traits, class Var> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const VarArray<Var>& x) { std::basic_ostringstream<Char,Traits> s; s.copyfmt(os); s.width(0); s << '{'; if (x.size() > 0) { s << x[0]; for (int i=1; i<x.size(); i++) s << ", " << x[i]; } s << '}'; return os << s.str(); }
template<class Char, class Traits, class View> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ViewArray<View>& x) { std::basic_ostringstream<Char,Traits> s; s.copyfmt(os); s.width(0); s << '{'; if (x.size() > 0) { s << x[0]; for (int i=1; i<x.size(); i++) s << ", " << x[i]; } s << '}'; return os << s.str(); }
template<class Char, class Traits, class T> std::basic_ostream<Char,Traits>& operator <<(std::basic_ostream<Char,Traits>& os, const ArgArrayBase<T>& x) { std::basic_ostringstream<Char,Traits> s; s.copyfmt(os); s.width(0); s << '{'; if (x.size() > 0) { s << x[0]; for (int i=1; i<x.size(); i++) s << ", " << x[i]; } s << '}'; return os << s.str(); }
}
// STATISTICS: kernel-other