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
|
#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
|
