#ifndef JszL9wNT11XcdnV6wZR3NcSJB0 #define JszL9wNT11XcdnV6wZR3NcSJB0 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include "heap.hpp" #include "priority_queue.hpp" #include "quant_types.hpp" #include "template_helpers.hpp" #include "type_set.hpp" namespace MultiQueueImpl { using namespace boost; using namespace boost::mpl; using boost::mpl::empty; using boost::mpl::size; const unsigned char numRID = 1 + RuntimeID::type>::value; template struct DefaultContainer { typedef Heap> type; }; // the actual class (the only one lifted) template class Payload, // values belongig to above keys typename Members, // list of all data sources template class Container = DefaultContainer> // queue impl struct MultiQueue { // type constructions typedef typename size::type numMembers; typedef typename transform> >::type MemberList; // typedef typename CalcSetType::type MemberList; typedef typename UnpackTypeList::type set_t; // get time and type of min element Val min() { return minVal[1]; } uint8_t minType() { return minRID[1]; } // insert event template inline void insert(Val ct, Val val, Payload payload) { assert(ct() <= val()); BOOST_STATIC_ASSERT(( numRID > RuntimeID::value )); get()(ct).insert(val, payload); uint pos = RIDpos[RuntimeID::value]; minVal[pos] = get()(ct).minVal(); // correct order; val can only decrease -> bubble down for (uint i=pos-1; maybeSwap(i); i--); } // remove min event; ugly part: caller has to supply correct quant // and position template inline void removeMin(Val ct, uint pos=1) { assert(RuntimeID::value == minRID[pos]); get()(ct).removeMin(); minVal[pos] = get()(ct).isEmpty() ? Val::never() : get()(ct).minVal(); // correct order; val can only increase -> bubble up for (int i=pos; maybeSwap(i); i++); } // like removeMin, but the quant does not need to be the current // global min and no position has to be specified template inline void removeLocalMin(Val ct) { removeMin(ct, RIDpos[RuntimeID::value]); } // constructor template MultiQueue(Arg... arg) : typeSet(std::move(arg)...) { init(); } MultiQueue() : typeSet() { init(); } void init() { // set fake entries (to avoid boundary condition during sorting) minVal[0] = Val::beforeAll(); minRID[0] = -1; // (and prefill minVal/minRID in case of missing values in loadInitial()) for (int i=1; i<=numMembers::value + 1; i++) { minVal[i] = Val::never(); minRID[i] = i - 1; } // init queue head caches loadInitial(); // blind in-place bubble sort for (int i=0; i void loadInitial(uint pos=1) { typedef typename front::type head_t; typedef empty::type> isLast_t; typedef typename if_::type >::type tail_t; // read current time from heaps Val ct = get().currentTime; // init queue head caches minRID[pos] = RuntimeID::value; if (get()(ct).isEmpty()) { minVal[pos] = Val::never(); }else{ minVal[pos] = get()(ct).minVal(); } RIDpos[RuntimeID::value] = pos; // template recursion if (!is_same::value) loadInitial(pos+1); } // access underlying queues directly template inline typename Container>::type & get() { return typeSet.get>::type>(); } // swap if i and i+1 are in wrong order; return if swapped inline bool maybeSwap(uint i) { // check if order is violated if (minVal[i] < minVal[i+1]) return false; if ((minVal[i] == minVal[i+1]) && (minRID[i] <= minRID[i+1])) return false; // sort by RID if val is equal // swap std::swap(minVal[i], minVal[i+1]); std::swap(minRID[i], minRID[i+1]); RIDpos[minRID[i]] = i; RIDpos[minRID[i + 1]] = i + 1; return true; } // data set_t typeSet; Val minVal[numMembers::value + 2]; uint minRID[numMembers::value + 2]; uint RIDpos[numRID]; }; } using MultiQueueImpl::MultiQueue; #endif // JszL9wNT11XcdnV6wZR3NcSJB0