include/wipal/filter/fast_intersector.hxx

/*
 * WiPal - A library and a set of tools to manipulate wireless traces.
 * Copyright (C) 2007, 2008, 2009  Universite Pierre et Marie Curie - Paris 6
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA  02110-1301  USA
 *
 * Author: Thomas Claveirole <thomas.claveirole@lip6.fr>
 */
#ifndef FILTER_FAST_INTERSECTOR_HXX_
# define FILTER_FAST_INTERSECTOR_HXX_

# include <iostream>
# include <sstream>
# include <boost/foreach.hpp>

# include "fast_intersector.hh"

namespace wpl
{

  namespace filter
  {

    namespace internals
    {

      template <class I1, class I2, class B1, class B2>
      fast_intersector_iterator<I1, I2, B1, B2>::
      fast_intersector_iterator(const iterable_type& i, bool end):
        super_type (),
        iterable_ (&i),
        next_ (end ? i.last_ : i.first_)
# ifdef WP_ENABLE_INFO
        , rhs_total_ (0),
        ref_total_ (0)
# endif // WP_ENABLE_INFO
      {
        if (not end)
          increment();
      }

      template <class I1, class I2, class B1, class B2>
      bool
      fast_intersector_iterator<I1, I2, B1, B2>::
      equal(const fast_intersector_iterator& rhs) const
      {
        if (not rhs.value())
          return not this->value();
        return next_ == rhs.next_;
      }

      template <class I1, class I2, class B1, class B2>
      void
      fast_intersector_iterator<I1, I2, B1, B2>::increment()
      {
        const I2&               last = this->iterable_->last_;
        bool                    found (false);

        while (next_ != last and not found)
          {
            found = check();
            ++next_;
# ifdef WP_ENABLE_INFO
            ++rhs_total_;
# endif // WP_ENABLE_INFO
          }

        if (not found)
          {
            this->value() = lookahead_;
            lookahead_ = boost::none_t ();
          }

# ifdef WP_ENABLE_INFO
        if (not found and not this->value())
          {
            const unsigned      lhs_total = this->iterable_->arrivals_.size();

            std::cerr << "INFO: Trace 2 has " << rhs_total_
                      << " unique frames.\n"
                      << "INFO: " << ref_total_ << " reference frames.\n"
                      << "INFO: " << (ref_total_ * 100.f / lhs_total)
                      << "% of trace 1's unique frames.\n"
                      << "INFO: " << (ref_total_ * 100.f / rhs_total_)
                      << "% of trace 2's unique frames." << std::endl;
          }
        else
          ++ref_total_;
# endif // WP_ENABLE_INFO
      }

      template <class I1, class I2, class B1, class B2>
      bool
      fast_intersector_iterator<I1, I2, B1, B2>::check()
      {
        const arrivals_iterator  i = iterable_->arrivals_.find(*next_);

        if (i == iterable_->arrivals_.end())
          return false;

        if (not lookahead_)
          {
            // First reference we encounter.  Delay it so we can
            // filter it out in case it is dubious.

            lookahead_ = value_type (*i, *next_);
            return false;
          }

        value_type&                     lookahead = lookahead_.get();
        const tool::microseconds        dt1 (i->microseconds() -
                                             lookahead.first.microseconds());
        const tool::microseconds        dt2 (next_->microseconds() -
                                             lookahead.second.microseconds());

        if (not check_drift(dt1, dt2, *i, *next_))
          return false;
        check_consistency(dt1, dt2, *i, *next_);

        this->value() = lookahead;
        lookahead = value_type (*i, *next_);
        return true;
      }

      template <class I1, class I2, class B1, class B2>
      bool
      fast_intersector_iterator<I1, I2, B1, B2>::
      check_drift(const tool::microseconds&             dt1,
                  const tool::microseconds&             dt2,
                  const typename I1::value_type&        f1,
                  const typename I2::value_type&        f2)
      {
        assert(lookahead_);

        value_type&                     lookahead = lookahead_.get();
        const tool::microseconds        drift (dt1 - dt2);

        if (drift < -drift_warn_threshold or drift_warn_threshold < drift)
          {
            std::cerr << f1 << '-' << f2 << ": Dubious drift: "
                      << (drift / 1000.f) << "ms";
            if (this->value())
              {
                // General case.  The dubious frame is the current one.

                std::cerr << " (ignoring reference)." << std::endl;

                ignore(f1, f2);
                return false;
              }
            else
              {
                // We are on the second frame.  Consider the first frame
                // as dubious, and delay this one.

                std::cerr << ".\n"
                          << lookahead.first << '-' << lookahead.second
                          << ": Previous reference (ignoring, "
                          << "potentially invalid)." << std::endl;

                ignore(lookahead.first, lookahead.second);
                lookahead = value_type (f1, f2);
                return false;
              }
          }
        dont_ignore(f1, f2);
        return true;
      }

      template <class I1, class I2, class B1, class B2>
      void
      fast_intersector_iterator<I1, I2, B1, B2>::
      check_consistency(const tool::microseconds&               dt1,
                        const tool::microseconds&               dt2,
                        const typename I1::value_type&  f1,
                        const typename I2::value_type&  f2) const
      {
        assert(lookahead_);

        const value_type&          lookahead = lookahead_.get();

        const tool::microseconds&  f1_us = f1.microseconds();
        const tool::microseconds&  f2_us = f2.microseconds();
        const tool::microseconds&  la1_us = lookahead.first.microseconds();
        const tool::microseconds&  la2_us = lookahead.second.microseconds();

        const tool::microseconds   precision = iterable_->precision_;

        /*
         * Check that references are correctly ordered, but ignore
         * anomalies when the interval between frames is less than
         * the expected merge precision.
         */
        if (f1_us - la1_us < -precision or f2_us - la2_us < -precision)
          std::cerr << f1 << '-' << f2 << ": Reference anterior to "
                    << lookahead.first << '-' << lookahead.second << '.'
                    << std::endl;

        else if (dt1 > dt_warn_threshold or dt2 > dt_warn_threshold)
          std::cerr << f1 << '-' << f2 << ": "
                    << (dt1 / 1000.f) << "ms and "
                    << (dt2 / 1000.f) << "ms since "
                    << lookahead.first << '-' << lookahead.second << '.'
                    << std::endl;
      }

      template <class I1, class I2, class B1, class B2>
      void
      fast_intersector_iterator<I1, I2, B1, B2>::
      ignore(const typename I1::value_type& f1,
             const typename I2::value_type& f2)
      {
        // FIXME: This is an error to use frame_id() here.  That
        // FIXME: produces invalid output in case of ignored frames
        // FIXME: spreading on two consecutive trace files.
        // FIXME: Unfortunately, there is no statisfying solution
        // FIXME: for the moment.

        if (not ign_)
          ign_ = ignore_info (f1.microseconds(), f2.microseconds(),
                              f1.frame_id(), f2.frame_id());
      }

      template <class I1, class I2, class B1, class B2>
      void
      fast_intersector_iterator<I1, I2, B1, B2>::
      dont_ignore(const typename I1::value_type& f1,
                  const typename I2::value_type& f2)
      {
        // FIXME: See previous FIXME in ignore().

        if (ign_)
          {
            std::ostringstream  os;

            os << f1 << '-' << f2 << ": ";

            const std::string           head = os.str();

            std::cerr
              << head << "Frames since first ignored reference:\n"
              << head << "* T1: " << (f1.frame_id() - ign_->total1_)
              <<       " (" << (f1.microseconds() - ign_->stamp1_) << "us)\n"
              << head << "* T2: " << (f2.frame_id() - ign_->total2_)
              <<       " (" << (f2.microseconds() - ign_->stamp2_) << "us)\n"
              << std::flush;

            ign_ = boost::none_t ();
          }
      }

      template <class I1, class I2, class B1, class B2>
      unsigned
      fast_intersector_iterator<I1, I2, B1, B2>::rhs_frame_count() const
      {
        return next_.frame_count();
      }

      template <class I1, class I2, class B1, class B2>
      unsigned
      fast_intersector_iterator<I1, I2, B1, B2>::rhs_uframe_count() const
      {
        return next_.unique_frame_count();
      }

      template <class I1, class I2, class B1, class B2>
      fast_intersector_iterator<I1, I2, B1, B2>::
      ignore_info::ignore_info(const tool::microseconds&        stamp_rhs,
                               const tool::microseconds&        stamp_lhs,
                               const unsigned                   total_rhs,
                               const unsigned                   total_lhs):
        stamp1_ (stamp_rhs),
        stamp2_ (stamp_lhs),
        total1_ (total_rhs),
        total2_ (total_lhs)
      {
      }

    } // End of namespace internals.


    template <class I1, class I2, class B>
    fast_intersector<I1, I2, B>::
    fast_intersector(const I1& first1, const I1& last1,
                     const I2& first2, const I2& last2,
                     const unsigned precision):
      first_ (first2),
      last_ (last2),
# ifndef WP_DONT_USE_HASH
      arrivals_ (hash_bucket_count),
# endif
      precision_ (precision)
    {
      reset_lhs(first1, last1);
    }

    template <class I1, class I2, class B>
    void
    fast_intersector<I1, I2, B>::reset_lhs(const I1& first1, const I1& last1)
    {
      arrivals_type     collisions;

      arrivals_.clear();
      for (I1 i = first1; i != last1; ++i)
        {
          typedef typename arrivals_type::iterator      iterator;

          std::pair<iterator, bool> r = arrivals_.insert(*i);

          if (not r.second)
            {
              collisions.insert(*i);

              std::cerr << *i << ": Unique frame actually a duplicate of "
                        << *r.first << " (ignoring both)." << std::endl;
            }
        }

      BOOST_FOREACH(const typename I1::value_type& v, collisions)
        arrivals_.erase(v);

# ifdef WP_ENABLE_INFO
      std::cerr << "INFO: Trace 1's unique frames successfuly loaded.\n"
                << "INFO: Trace 1 has " << arrivals_.size()
                << " unique frames." << std::endl;
# endif // WP_ENABLE_INFO
    }

    template <class I1, class I2, class B>
    void
    fast_intersector<I1, I2, B>::reset_rhs(const I2& first2, const I2& last2)
    {
      first_ = first2;
      last_ = last2;
    }

  } // End of namespace wpl::filter.

} // End of namespace wpl.

#endif // ! FILTER_FAST_INTERSECTOR_HXX_

---