00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WIFI_FRAME_FILTER_FAST_INTERSECTOR_HXX_
00023 # define WIFI_FRAME_FILTER_FAST_INTERSECTOR_HXX_
00024
00025 # include <iostream>
00026 # include <sstream>
00027 # include <boost/foreach.hpp>
00028
00029 # include "fast_intersector.hh"
00030
00031 # include <wipal/wifi/frame/filter/non_noisy_prism.hh>
00032 # include <wipal/wifi/frame/filter/uniquely_identifiable.hh>
00033
00034 namespace wifi
00035 {
00036 namespace frame
00037 {
00038 namespace filter
00039 {
00040
00041 namespace internals
00042 {
00043
00044 template <class I1, class I2, class B1, class B2>
00045 fast_intersector_iterator<I1, I2, B1, B2>::
00046 fast_intersector_iterator(const iterable_type& i, bool end):
00047 super_type (),
00048 iterable_ (&i),
00049 next_ (end ? i.last_ : i.first_)
00050 # ifdef WP_ENABLE_INFO
00051 , rhs_total_ (0),
00052 ref_total_ (0)
00053 # endif
00054 {
00055 if (not end)
00056 increment();
00057 }
00058
00059 template <class I1, class I2, class B1, class B2>
00060 bool
00061 fast_intersector_iterator<I1, I2, B1, B2>::
00062 equal(const fast_intersector_iterator& rhs) const
00063 {
00064 if (not rhs.value())
00065 return not this->value();
00066 return next_ == rhs.next_;
00067 }
00068
00069 template <class I1, class I2, class B1, class B2>
00070 void
00071 fast_intersector_iterator<I1, I2, B1, B2>::increment()
00072 {
00073 const I2& last = this->iterable_->last_;
00074 bool found (false);
00075
00076 while (next_ != last and not found)
00077 {
00078 found = check();
00079 ++next_;
00080 # ifdef WP_ENABLE_INFO
00081 ++rhs_total_;
00082 # endif // WP_ENABLE_INFO
00083 }
00084
00085 if (not found)
00086 {
00087 this->value() = lookahead_;
00088 lookahead_ = boost::none_t ();
00089 }
00090
00091 # ifdef WP_ENABLE_INFO
00092 if (not found and not this->value())
00093 {
00094 const unsigned lhs_total = this->iterable_->arrivals_.size();
00095
00096 std::cerr << "INFO: Trace 2 has " << rhs_total_
00097 << " unique frames.\n"
00098 << "INFO: " << ref_total_ << " reference frames.\n"
00099 << "INFO: " << (ref_total_ * 100.f / lhs_total)
00100 << "% of trace 1's unique frames.\n"
00101 << "INFO: " << (ref_total_ * 100.f / rhs_total_)
00102 << "% of trace 2's unique frames." << std::endl;
00103 }
00104 else
00105 ++ref_total_;
00106 # endif // WP_ENABLE_INFO
00107 }
00108
00109 template <class I1, class I2, class B1, class B2>
00110 bool
00111 fast_intersector_iterator<I1, I2, B1, B2>::check()
00112 {
00113 const arrivals_iterator i = iterable_->arrivals_.find(*next_);
00114
00115 if (i == iterable_->arrivals_.end())
00116 return false;
00117
00118 if (not lookahead_)
00119 {
00120
00121
00122
00123 lookahead_ = value_type (*i, *next_);
00124 return false;
00125 }
00126
00127 value_type& lookahead = lookahead_.get();
00128 const tool::microseconds dt1 (i->microseconds() -
00129 lookahead.first.microseconds());
00130 const tool::microseconds dt2 (next_->microseconds() -
00131 lookahead.second.microseconds());
00132
00133 if (not check_drift(dt1, dt2, *i, *next_))
00134 return false;
00135 check_consistency(dt1, dt2, *i, *next_);
00136
00137 this->value() = lookahead;
00138 lookahead = value_type (*i, *next_);
00139 return true;
00140 }
00141
00142 template <class I1, class I2, class B1, class B2>
00143 bool
00144 fast_intersector_iterator<I1, I2, B1, B2>::
00145 check_drift(const tool::microseconds& dt1,
00146 const tool::microseconds& dt2,
00147 const typename I1::value_type& f1,
00148 const typename I2::value_type& f2)
00149 {
00150 assert(lookahead_);
00151
00152 value_type& lookahead = lookahead_.get();
00153 const tool::microseconds drift (dt1 - dt2);
00154
00155 if (drift < -drift_warn_threshold or drift_warn_threshold < drift)
00156 {
00157 std::cerr << f1 << '-' << f2 << ": Dubious drift: "
00158 << (drift / 1000.f) << "ms";
00159 if (this->value())
00160 {
00161
00162
00163 std::cerr << " (ignoring reference)." << std::endl;
00164
00165 ignore(f1, f2);
00166 return false;
00167 }
00168 else
00169 {
00170
00171
00172
00173 std::cerr << ".\n"
00174 << lookahead.first << '-' << lookahead.second
00175 << ": Previous reference (ignoring, "
00176 << "potentially invalid)." << std::endl;
00177
00178 ignore(lookahead.first, lookahead.second);
00179 lookahead = value_type (f1, f2);
00180 return false;
00181 }
00182 }
00183 dont_ignore(f1, f2);
00184 return true;
00185 }
00186
00187 template <class I1, class I2, class B1, class B2>
00188 void
00189 fast_intersector_iterator<I1, I2, B1, B2>::
00190 check_consistency(const tool::microseconds& dt1,
00191 const tool::microseconds& dt2,
00192 const typename I1::value_type& f1,
00193 const typename I2::value_type& f2) const
00194 {
00195 assert(lookahead_);
00196
00197 const value_type& lookahead = lookahead_.get();
00198
00199 const tool::microseconds& f1_us = f1.microseconds();
00200 const tool::microseconds& f2_us = f2.microseconds();
00201 const tool::microseconds& la1_us = lookahead.first.microseconds();
00202 const tool::microseconds& la2_us = lookahead.second.microseconds();
00203
00204 if (f1_us - la1_us < -unordered_warn_threshold or
00205 f2_us - la2_us < -unordered_warn_threshold)
00206 std::cerr << f1 << '-' << f2 << ": Reference anterior to "
00207 << lookahead.first << '-' << lookahead.second << '.'
00208 << std::endl;
00209 else if (dt1 > dt_warn_threshold or dt2 > dt_warn_threshold)
00210 std::cerr << f1 << '-' << f2 << ": "
00211 << (dt1 / 1000.f) << "ms and "
00212 << (dt2 / 1000.f) << "ms since "
00213 << lookahead.first << '-' << lookahead.second << '.'
00214 << std::endl;
00215 }
00216
00217 template <class I1, class I2, class B1, class B2>
00218 void
00219 fast_intersector_iterator<I1, I2, B1, B2>::
00220 ignore(const typename I1::value_type& f1,
00221 const typename I2::value_type& f2)
00222 {
00223
00224
00225
00226
00227
00228
00229 if (not ign_)
00230 ign_ = ignore_info (f1.microseconds(), f2.microseconds(),
00231 f1.frame_id(), f2.frame_id());
00232 }
00233
00234 template <class I1, class I2, class B1, class B2>
00235 void
00236 fast_intersector_iterator<I1, I2, B1, B2>::
00237 dont_ignore(const typename I1::value_type& f1,
00238 const typename I2::value_type& f2)
00239 {
00240
00241
00242 if (ign_)
00243 {
00244 std::ostringstream os;
00245
00246 os << f1 << '-' << f2 << ": ";
00247
00248 const std::string head = os.str();
00249
00250 std::cerr
00251 << head << "Frames since first ignored reference:\n"
00252 << head << "* T1: " << (f1.frame_id() - ign_->total1_)
00253 << " (" << (f1.microseconds() - ign_->stamp1_) << "us)\n"
00254 << head << "* T2: " << (f2.frame_id() - ign_->total2_)
00255 << " (" << (f2.microseconds() - ign_->stamp2_) << "us)\n"
00256 << std::flush;
00257
00258 ign_ = boost::none_t ();
00259 }
00260 }
00261
00262 template <class I1, class I2, class B1, class B2>
00263 unsigned
00264 fast_intersector_iterator<I1, I2, B1, B2>::rhs_frame_count() const
00265 {
00266 return next_.frame_count();
00267 }
00268
00269 template <class I1, class I2, class B1, class B2>
00270 unsigned
00271 fast_intersector_iterator<I1, I2, B1, B2>::rhs_uframe_count() const
00272 {
00273 return next_.unique_frame_count();
00274 }
00275
00276 template <class I1, class I2, class B1, class B2>
00277 fast_intersector_iterator<I1, I2, B1, B2>::
00278 ignore_info::ignore_info(const tool::microseconds& stamp_rhs,
00279 const tool::microseconds& stamp_lhs,
00280 const unsigned total_rhs,
00281 const unsigned total_lhs):
00282 stamp1_ (stamp_rhs),
00283 stamp2_ (stamp_lhs),
00284 total1_ (total_rhs),
00285 total2_ (total_lhs)
00286 {
00287 }
00288
00289 }
00290
00291
00292 template <class I1, class I2, class B>
00293 fast_intersector<I1, I2, B>::
00294 fast_intersector(const I1& first1, const I1& last1,
00295 const I2& first2, const I2& last2):
00296 first_ (first2),
00297 last_ (last2)
00298 # ifndef WP_DONT_USE_HASH
00299 , arrivals_ (hash_bucket_count)
00300 # endif
00301 {
00302 reset_lhs(first1, last1);
00303 }
00304
00305 template <class I1, class I2, class B>
00306 void
00307 fast_intersector<I1, I2, B>::reset_lhs(const I1& first1, const I1& last1)
00308 {
00309 arrivals_type collisions;
00310
00311 arrivals_.clear();
00312 for (I1 i = first1; i != last1; ++i)
00313 {
00314 typedef typename arrivals_type::iterator iterator;
00315
00316 std::pair<iterator, bool> r = arrivals_.insert(*i);
00317
00318 if (not r.second)
00319 {
00320 collisions.insert(*i);
00321
00322 std::cerr << *i << ": Unique frame actually a duplicate of "
00323 << *r.first << " (ignoring both)." << std::endl;
00324 }
00325 }
00326
00327 BOOST_FOREACH(const typename I1::value_type& v, collisions)
00328 arrivals_.erase(v);
00329
00330 # ifdef WP_ENABLE_INFO
00331 std::cerr << "INFO: Trace 1's unique frames successfuly loaded.\n"
00332 << "INFO: Trace 1 has " << arrivals_.size()
00333 << " unique frames." << std::endl;
00334 # endif // WP_ENABLE_INFO
00335 }
00336
00337 template <class I1, class I2, class B>
00338 void
00339 fast_intersector<I1, I2, B>::reset_rhs(const I2& first2, const I2& last2)
00340 {
00341 first_ = first2;
00342 last_ = last2;
00343 }
00344
00345 }
00346
00347 }
00348
00349 }
00350
00351 #endif // ! WIFI_FRAME_FILTER_FAST_INTERSECTOR_HXX_