Initial commitHEADmaster

1 files changed, 187 insertions, 0 deletions

diff --git a/core/multi_queue.hpp b/core/multi_queue.hpp
new file mode 100644
index 0000000..b77785b
--- /dev/null
+++ b/core/multi_queue.hpp
@@ -0,0 +1,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