merge with upstream

1 files changed, 0 insertions, 140 deletions

diff --git a/utils/agenda.h b/utils/agenda.h
deleted file mode 100755
index d4f13696..00000000
--- a/utils/agenda.h
+++ /dev/null
@@ -1,140 +0,0 @@
-#ifndef AGENDA_H
-#define AGENDA_H
-
-#define DBG_AGENDA(x) x
-/*
-  a priority queue where you expect to queue the same item at different
-  priorities several times before finally popping it.  higher priority = better.
-  so in best first you'd be using negative cost or e^-cost (probabilities, in
-  other words).
-
-  this means you have a way to look up a key and see its location in the queue,
-  so its priority can be adjusted (or, simpler implementation: so when you pop,
-  you see if you've already popped before at a lower cost, and skip the
-  subsequent pops).
-
-  it's assumed that you'll never queue an item @ a better priority after it has
-  already been popped.  that is, the agenda will track already completed items.
-  maybe in the future i will let you recompute a cheaper way to reach things
-  after first-pop also, it's assumed that we're always improving prios of
-  existing items, never making them worse (even though technically this is
-  possible and sensible if it hasn't been popped yet).
-
-  simple binary max heap for now.  there are better practical options w/
-  superior cache locaility.  movements in the heap need to update a record for
-  that key of where the key went.  i do this by creating canonical key pointers
-  out of boost object pools (if the key were lightweight e.g. an int, then it
-  would make sense to use the hash lookup too
-
-  since i'm doing key hashing to start with, i also allow you to attach some
-  arbitrary data (value) payload beyond key+priority.
-
-  hash map from key to done (has been popped) -> set where doneness is marked in key item?
-
-  a slightly different way to make an adjustable heap would be to use
-  tree-structured parent/children links intrusively (or mapped by key) in the
-  key, rather than indices in a compact binary-tree heap
-
- */
-
-#include "best.h"
-#include "intern_pool.h"
-#include "d_ary_heap.h"
-#include "lvalue_pmap.h"
-#include <vector>
-#include <functional>
-
-/*
-template <class P>
-struct priority_traits {
-  typedef typename P::priority_type priority_type;
-};
-*/
-
-typedef best_t agenda_best_t;
-typedef unsigned agenda_location_t;
-
-PMAP_MEMBER_INDIRECT(LocationMap,agenda_location_t,location)
-PMAP_MEMBER_INDIRECT(PriorityMap,agenda_best_t,priority)
-
-struct Less {
-  typedef bool result_type;
-  template <class A,class B>
-  bool operator()(A const& a,B const& b) const { return a<b; }
-};
-
-// LocMap and PrioMap are boost property maps put(locmap,key,size_t), Better(get(priomap,k1),get(priomap,k2)) means k1 should be above k2 (be popped first).  Locmap and PrioMap may have state; the rest are assumed stateless functors
-// make sure the (default) location is not -1 for anything you add, or else an assertion may trigger
-template <class Item,class Better=Less, /* intern_pool args */ class KeyF=get_key<Item>,class HashKey=boost::hash<typename KeyF::result_type>,class EqKey=std::equal_to<typename KeyF::result_type>, class Pool=boost::object_pool<Item> >
-struct Agenda : intern_pool<Item,KeyF,HashKey,EqKey,Pool> {
-  typedef intern_pool<Item,KeyF,HashKey,EqKey,Pool> Intern; // inherited because I want to use construct()
-  /* this is less generic than it could be, because I want to use a single hash mapping to intern to canonical mutable object pointers, where the property maps are just lvalue accessors */
-  typedef typename KeyF::result_type Key;
-  typedef Item * Handle;
-  typedef LocationMap<Handle> LocMap;
-  typedef PriorityMap<Handle> PrioMap;
-  LocMap locmap;
-  PrioMap priomap; // note: priomap[item] is set by caller before giving us the item; then tracks best (for canonicalized item) thereafter
-
-  Better better;
-  //NOT NEEDED: initialize function object state (there is none)
-
-  typedef Item *ItemC; //canonicalized pointer
-  typedef Item *ItemP;
-  static const std::size_t heap_arity=4; // might be fastest possible (depends on key size probably - cache locality is bad w/ arity=2)
-  typedef std::vector<ItemC> HeapStorage;
-  typedef d_ary_heap_indirect<Handle,heap_arity,LocMap,PrioMap,Better,HeapStorage,agenda_location_t> Heap;
-  Heap q;
-
-  // please don't call q.push etc. directly.
-  void add(ItemP i) {
-    bool fresh=interneq(i);
-    DBG_AGENDA(assert(fresh && !q.contains(i)));
-    q.push(i);
-  }
-  bool improve(ItemP i) {
-    ItemP c=i;
-    bool fresh=interneq(c);
-    if (fresh) {
-      add(c);
-      return true;
-    }
-    DBG_AGENDA(assert(q.contains(c)));
-    return q.maybe_improve(priomap[i]);
-  }
-  inline bool empty() {
-    return q.empty();
-  }
-  // no need to destroy the canon. item because we want to remember the best cost and reject more expensive ways of using it).
-  ItemC pop() {
-    ItemC r=q.top();
-    q.pop();
-    return r;
-  }
-  void pop_discard() {
-    q.pop();
-  }
-
-  ItemC top() {
-    DBG_AGENDA(assert(!empty()));
-    return q.top();
-  }
-
-  agenda_best_t best() const {
-    return q.best(); //TODO: cache/track the global best?
-  }
-
-  agenda_best_t second_best() const {
-    return q.second_best();
-  }
-
-  // add only if worse than queue current best, otherwise evaluate immediately (e.g. for early stopping w/ expensive to compute additional cost).  return true if postponed (added)
-  bool postpone(ItemP i) {
-    if (better(priomap[i],best())) return false;
-    return improve(i);
-  }
-
-  Agenda(unsigned reserve=1000000,LocMap const& lm=LocMap(),PrioMap const& pm=PrioMap(),EqKey const& eq=EqKey(),Better const& better=Better()) : locmap(lm), priomap(pm), better(better), q(priomap,locmap,better,reserve) {  }
-};
-
-#endif