From ca9c1f40cad1f99f00beb2871dc50bf7222d44d4 Mon Sep 17 00:00:00 2001
From: graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>
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 <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 Hash=boost::hash<Item>,class Equal=std::equal_to<Item>,class Better=std::less<Item> >
+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<CanonItem> HeapStorage;
+ typedef boost::detail::d_ary_heap_indirect<Key,heap_arity,LocMap,PrioMap,Better,HeapStorage> Heap;
+ HASH_SET<Key,Hash,Equal> queued;
+ typedef LocationMap<ItemP>
+ 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<double> 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 <google/dense_hash_map>
# 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 <tr1/unordered_map>
# 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<k,v,boost::hash<k> >
+namespace {
+const unsigned GOLDEN_MEAN_FRACTION=2654435769U;
+}
+
// assumes C is POD
template <class C>
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 <boost/property_map/property_map.hpp>
+
+// i checked: boost provides get and put given []
+
+// lvalue property map pmapname<P> that is: P p; valtype &v=p->name;
+#define PMAP_MEMBER_INDIRECT(pmapname,valtype,name) template <class P> 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 <class P,class R> 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 <class V>
+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 <class V>
+V null_traits<V>::null;
+//TODO: are we getting single init of the static null object?
+
+template <class V>
+void set_null(V &v) {
+ v=null_traits<V>::null;
+}
+
+template <class V>
+void is_null(V const& v) {
+ return v==null_traits<V>::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 <class C,class F>
+ 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 <class I,class F>
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<sz ? s : sz;
+ size_type i=0;
+ for (;i<nc;++i)
+ A::construct(na+i,array[i]);
+ for (;i<s;++i)
+ A::construct(na+i,t);
+ clear();
+ array=na;
+ sz=s;
+ }
+
template <class I>
void reinit(I itr, I end) {
clear();
@@ -135,10 +155,16 @@ public:
}
template <class I,class F>
- 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 <class C,class F>
+ void reinit_map(C const& c,F const& map) {
+ clear();
+ init_map(c,map);
+ }
template <class I>
ValueArray(I itr, I end)
--
cgit v1.2.3