diff options
author | Patrick Simianer <p@simianer.de> | 2011-10-19 14:02:34 +0200 |
---|---|---|
committer | Patrick Simianer <p@simianer.de> | 2011-10-19 14:02:34 +0200 |
commit | 9beaeb42b71fa504bfa41a402cb17eb6ac4001af (patch) | |
tree | 0add4afabc526391753e4e6b9443a7bf21e3e2c3 /gi/pf/reachability.h | |
parent | ce3b4db94d40c111ede321ac6de2bb061a81c4af (diff) | |
parent | 09297047e446f49804d3f48bf320cdbd38d6396a (diff) |
merge upstream/master
Diffstat (limited to 'gi/pf/reachability.h')
-rw-r--r-- | gi/pf/reachability.h | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/gi/pf/reachability.h b/gi/pf/reachability.h new file mode 100644 index 00000000..98450ec1 --- /dev/null +++ b/gi/pf/reachability.h @@ -0,0 +1,28 @@ +#ifndef _REACHABILITY_H_ +#define _REACHABILITY_H_ + +#include "boost/multi_array.hpp" + +// determines minimum and maximum lengths of outgoing edges from all +// coverage positions such that the alignment path respects src and +// trg maximum phrase sizes +// +// runs in O(n^2 * src_max * trg_max) time but should be relatively fast +// +// currently forbids 0 -> n and n -> 0 alignments + +struct Reachability { + boost::multi_array<bool, 4> edges; // edges[src_covered][trg_covered][x][trg_delta] is this edge worth exploring? + boost::multi_array<short, 2> max_src_delta; // msd[src_covered][trg_covered] -- the largest src delta that's valid + + Reachability(int srclen, int trglen, int src_max_phrase_len, int trg_max_phrase_len) : + edges(boost::extents[srclen][trglen][src_max_phrase_len+1][trg_max_phrase_len+1]), + max_src_delta(boost::extents[srclen][trglen]) { + ComputeReachability(srclen, trglen, src_max_phrase_len, trg_max_phrase_len); + } + + private: + void ComputeReachability(int srclen, int trglen, int src_max_phrase_len, int trg_max_phrase_len); +}; + +#endif |