From ca9c1f40cad1f99f00beb2871dc50bf7222d44d4 Mon Sep 17 00:00:00 2001 From: graehl Date: Sat, 21 Aug 2010 03:07:42 +0000 Subject: agenda for fsa git-svn-id: https://ws10smt.googlecode.com/svn/trunk@612 ec762483-ff6d-05da-a07a-a48fb63a330f --- utils/agenda.h | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++ utils/best.h | 13 ++++++++ utils/hash.h | 6 ++++ utils/lvalue_pmap.h | 25 ++++++++++++++ utils/null_traits.h | 26 +++++++++++++++ utils/value_array.h | 30 +++++++++++++++-- 6 files changed, 193 insertions(+), 2 deletions(-) create mode 100755 utils/agenda.h create mode 100755 utils/best.h create mode 100755 utils/lvalue_pmap.h create mode 100755 utils/null_traits.h (limited to 'utils') diff --git a/utils/agenda.h b/utils/agenda.h new file mode 100755 index 00000000..8198f077 --- /dev/null +++ b/utils/agenda.h @@ -0,0 +1,95 @@ +#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 "hash.h" +#include "d_ary_heap.h" +#include "lvalue_pmap.h" +#include +#include + +/* +template +struct priority_traits { + typedef typename P::priority_type priority_type; +}; + +// P p has priority_traits

::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 +struct AdjustablePriority { + typedef AdjustablePriority

Self; + typedef typename priority_traits

::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 Equal=std::equal_to,class Better=std::less > +struct Agenda { + /* 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 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 HeapStorage; + typedef boost::detail::d_ary_heap_indirect Heap; + HASH_SET queued; + typedef LocationMap + LocMap locmap; + PrioMap priomap; + Agenda(LocMap const& lm=LocMap(),PrioMap const& pm=PrioMap()) : locmap(lm), priomap(pm) { } +*/ +}; + +#endif diff --git a/utils/best.h b/utils/best.h new file mode 100755 index 00000000..8ff896bb --- /dev/null +++ b/utils/best.h @@ -0,0 +1,13 @@ +#ifndef UTILS__BEST_H +#define UTILS__BEST_H + +#include "max_plus.h" + +typedef MaxPlus best_t; + +inline bool operator <(best_t const& a,best_t const& b) { + return a.v_>b.v_; // intentionally reversed, so default min-heap, sort, etc. put best first. +} + + +#endif diff --git a/utils/hash.h b/utils/hash.h index 7e38bb2c..e9584dd5 100755 --- a/utils/hash.h +++ b/utils/hash.h @@ -9,17 +9,23 @@ #ifdef HAVE_SPARSEHASH # include # define HASH_MAP google::dense_hash_map +# define HASH_SET google::dense_hash_set # define HASH_MAP_RESERVED(h,empty,deleted) do { h.set_empty_key(empty); h.set_deleted_key(deleted); } while(0) # define HASH_MAP_EMPTY(h,empty) do { h.set_empty_key(empty); } while(0) #else # include # define HASH_MAP std::tr1::unordered_map +# define HASH_SET std::tr1::unordered_set # define HASH_MAP_RESERVED(h,empty,deleted) # define HASH_MAP_EMPTY(h,empty) #endif #define BOOST_HASHED_MAP(k,v) HASH_MAP > +namespace { +const unsigned GOLDEN_MEAN_FRACTION=2654435769U; +} + // assumes C is POD template struct murmur_hash diff --git a/utils/lvalue_pmap.h b/utils/lvalue_pmap.h new file mode 100755 index 00000000..03ddf5e7 --- /dev/null +++ b/utils/lvalue_pmap.h @@ -0,0 +1,25 @@ +#ifndef LVALUE_PMAP_H +#define LVALUE_PMAP_H + +#include + +// i checked: boost provides get and put given [] + +// lvalue property map pmapname

that is: P p; valtype &v=p->name; +#define PMAP_MEMBER_INDIRECT(pmapname,valtype,name) template struct pmapname { \ + typedef P key_type; \ + typedef valtype value_type; \ + typedef value_type & reference; \ + typedef boost::lvalue_property_map_tag category; \ + reference operator[](key_type p) const { return p->name; } \ +}; + +#define PMAP_MEMBER_INDIRECT_2(pmapname,name) template struct pmapname { \ + typedef P key_type; \ + typedef R value_type; \ + typedef value_type & reference; \ + typedef boost::lvalue_property_map_tag category; \ + reference operator[](key_type p) const { return p->name; } \ +}; + +#endif diff --git a/utils/null_traits.h b/utils/null_traits.h new file mode 100755 index 00000000..fac857d9 --- /dev/null +++ b/utils/null_traits.h @@ -0,0 +1,26 @@ +#ifndef NULL_TRAITS_H +#define NULL_TRAITS_H + +template +struct null_traits { + static V null; //TODO: maybe take out default null and make ppl explicitly define? they may be surprised that they need to when they include a header lib that uses null_traits +}; +// global bool is_null(V const& v) + +// definitely override this, and possibly set_null and is_null. that's the point. +template +V null_traits::null; +//TODO: are we getting single init of the static null object? + +template +void set_null(V &v) { + v=null_traits::null; +} + +template +void is_null(V const& v) { + return v==null_traits::null; +} + + +#endif diff --git a/utils/value_array.h b/utils/value_array.h index 82e66e8d..a10f754f 100755 --- a/utils/value_array.h +++ b/utils/value_array.h @@ -103,6 +103,12 @@ protected: } } + template + inline void init_map(C const& c,F const& f) { + alloc(c.size()); + copy_construct_map(c.begin(),c.end(),array,f); + } + // warning: std::distance is likely slow on maps (anything other than random access containers. so container version using size will be better template inline void init_range_map(I itr, I end,F const& f) { alloc(std::distance(itr,end)); @@ -123,11 +129,25 @@ public: { init(s,t); } - void resize(size_type s, const_reference t = T()) { + void reinit(size_type s, const_reference t = T()) { clear(); init(s,t); } + //copy any existing data like std::vector. not A::construct exception safe. try blah blah? + void resize(size_type s, const_reference t = T()) { + pointer na=A::allocate(s); + size_type nc=s void reinit(I itr, I end) { clear(); @@ -135,10 +155,16 @@ public: } template - void reinit_map(I itr, I end,F const& map) { + void reinit_map(I itr,I end,F const& map) { clear(); init_range_map(itr,end,map); } + // warning: std::distance is likely slow on maps,lists (anything other than random access containers. so container version below using size() will be better + template + void reinit_map(C const& c,F const& map) { + clear(); + init_map(c,map); + } template ValueArray(I itr, I end) -- cgit v1.2.3