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
|
#ifndef AGENDA_H
#define AGENDA_H
/*
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;
};
// P p has priority_traits<P>::type &p->agenda_priority() and unsigned &p->agenda_location(), and bool & p->agenda_done()
// this is really 4 functors in 1 (or lvalue property maps); you can supply your own as the Prio type in Agenda<...> below ; state is allowed.
template <class P>
struct AdjustablePriority {
typedef AdjustablePriority<P> Self;
typedef typename priority_traits<P>::priority_type Priority;
Priority & priority(P const &x) {
return x->agenda_priority();
}
unsigned & location(P const &x) { // this gets updated by push, pop, and adjust
return x->agenda_location();
}
void is_done(P const& x) const {
return x->agenda_done();
}
void set_done(P const& x) const {
x->agenda_done()=true;
}
};
*/
typedef best_t agenda_best_t;
PMAP_MEMBER_INDIRECT(LocationMap,unsigned,location)
PMAP_MEMBER_INDIRECT(PriorityMap,best_t,priority)
// 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
template <class Item,class Better=std::less<Item>, /* intern_pool args */ class KeyF=get_key<Item>,class HashKey=boost::hash<typename KeyF::return_type>,class EqKey=std::equal_to<typename KeyF::return_type>, class Pool=boost::object_pool<Item> >
struct Agenda : intern_pool<Item,KeyF,EqKey,Pool> {
/* 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 intern_pool<Item,KeyF,EqKey,Pool> Intern; // inherited because I want to use construct()
typedef Item * Handle;
typedef LocationMap<Handle> LocMap;
typedef PriorityMap<Handle> PrioMap;
LocMap locmap;
PrioMap priomap;
//NOT NEEDED: initialize function object state (there is none)
/*
typedef Item *CanonItem;
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<CanonItem> HeapStorage;
typedef boost::detail::d_ary_heap_indirect<Key,heap_arity,LocMap,PrioMap,Better,HeapStorage> Heap;
HASH_SET<Key,Hash,Equal> queued;
Agenda(LocMap const& lm=LocMap(),PrioMap const& pm=PrioMap()) : locmap(lm), priomap(pm) { }
*/
};
#endif
|
