1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#ifndef JszL9wNT11XcdnV6wZR3NcSJB0
#define JszL9wNT11XcdnV6wZR3NcSJB0
#include <assert.h>
#include <boost/mpl/list.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/back.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/tuple/tuple.hpp>
#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<back<DiscreteQuantorList>::type>::value;
template<typename Val, typename Payload>
struct DefaultContainer {
typedef Heap<PriorityQueue<Val, Payload>> type;
};
// the actual class (the only one lifted)
template <typename Val, // keys to be sorted
template<typename X> class Payload, // values belongig to above keys
typename Members, // list of all data sources
template<typename _Val, typename _Payload> class Container
= DefaultContainer> // queue impl
struct MultiQueue {
// type constructions
typedef typename size<Members>::type numMembers;
typedef typename transform<Members,
Container<Val, Payload<_>>
>::type MemberList;
// typedef typename CalcSetType<Val, Container, Payload, Members>::type MemberList;
typedef typename UnpackTypeList<TypeSet, MemberList>::type set_t;
// get time and type of min element
Val min() {
return minVal[1];
}
uint8_t minType() {
return minRID[1];
}
// insert event
template<typename Quant>
inline void insert(Val ct, Val val, Payload<Quant> payload) {
assert(ct() <= val());
BOOST_STATIC_ASSERT(( numRID > RuntimeID<Quant>::value ));
get<Quant>()(ct).insert(val, payload);
uint pos = RIDpos[RuntimeID<Quant>::value];
minVal[pos] = get<Quant>()(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<typename Quant>
inline void removeMin(Val ct, uint pos=1) {
assert(RuntimeID<Quant>::value == minRID[pos]);
get<Quant>()(ct).removeMin();
minVal[pos] = get<Quant>()(ct).isEmpty()
? Val::never()
: get<Quant>()(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<typename Quant>
inline void removeLocalMin(Val ct) {
removeMin<Quant>(ct, RIDpos[RuntimeID<Quant>::value]);
}
// constructor
template<typename... Arg>
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<Members>();
// blind in-place bubble sort
for (int i=0; i<numMembers::value; i++)
for (int j=1; j<numMembers::value; j++)
maybeSwap(j);
}
template<typename RemMembers>
void loadInitial(uint pos=1) {
typedef typename front<RemMembers>::type head_t;
typedef empty<typename pop_front<RemMembers>::type> isLast_t;
typedef typename if_<isLast_t,
RemMembers,
typename pop_front<RemMembers>::type
>::type tail_t;
// read current time from heaps
Val ct = get<head_t>().currentTime;
// init queue head caches
minRID[pos] = RuntimeID<head_t>::value;
if (get<head_t>()(ct).isEmpty()) {
minVal[pos] = Val::never();
}else{
minVal[pos] = get<head_t>()(ct).minVal();
}
RIDpos[RuntimeID<head_t>::value] = pos;
// template recursion
if (!is_same<RemMembers, tail_t>::value)
loadInitial<tail_t>(pos+1);
}
// access underlying queues directly
template <typename Quant>
inline typename Container<Val, Payload<Quant>>::type & get() {
return typeSet.get<typename Container<Val, Payload<Quant>>::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
|
