include/wipal/filter/windowed_merge.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_WINDOWED_MERGE_HXX_
# define FILTER_WINDOWED_MERGE_HXX_

# include <iostream>

# include "windowed_merge.hh"

# include <wipal/filter/merge.hh>

namespace wpl
{

  namespace filter
  {

    namespace internals
    {

# ifdef WP_ENABLE_INFO
#  define WP_increment(X)       ++(X)
#  define WP_increase(X, Y...)  ((X) += (Y))
# else // ! WP_ENABLE_INFO
#  define WP_increment(X)       (void) 0
#  define WP_increase(X, Y...)  (void) (Y)
# endif // WP_ENABLE_INFO

      template <class HT, class I1, class I2, class B1, class B2>
      windowed_merge_iterator<HT, I1, I2, B1, B2>::
      windowed_merge_iterator(const iterable_type& i, bool end):
        iterable_ (&i),
        next1_ (end ? i.last1_ : i.first1_),
        next2_ (end ? i.last2_ : i.first2_),
        current_ (-1)
# ifdef WP_ENABLE_INFO
        , lhs_total_ (0),
        rhs_total_ (0),
        shared_ (0),
        total_ (0),
        sync_error_ (0)
# endif // WP_ENABLE_INFO
      {
        if (not end)
          {
            WP_increase(lhs_total_, fill(win1_, next1_, iterable_->last1_,
                                         window_size));
            WP_increase(rhs_total_, fill(win2_, next2_, iterable_->last2_,
                                         window_size));
            update_current();
          }
      }

      template <class HT, class I1, class I2, class B1, class B2>
      bool
      windowed_merge_iterator<HT, I1, I2, B1, B2>::
      equal(const windowed_merge_iterator& rhs) const
      {
        return (next1_ == rhs.next1_ and win1_.size() == rhs.win1_.size() and
                next2_ == rhs.next2_ and win2_.size() == rhs.win2_.size());
      }

#define WP_advance(Counter, N)                                          \
      do                                                                \
        {                                                               \
          WP_increase(Counter, fill(win ## N ## _, next ## N ## _,      \
                                    iterable_->last ## N ## _, 1));     \
          win ## N ## _.pop_front();                                    \
        }                                                               \
      while (0)

      template <class HT, class I1, class I2, class B1, class B2>
      void
      windowed_merge_iterator<HT, I1, I2, B1, B2>::increment()
      {
        assert(current_ == 0 or current_ == 1);

        if (win1_.empty())
          WP_advance(rhs_total_, 2);
        else if (win2_.empty())
          WP_advance(lhs_total_, 1);
        else if (const optional_match r = match())
          {
# ifdef WP_ENABLE_INFO
            {
              const tool::microseconds& t1 = r->first->microseconds();
              const tool::microseconds& t2 = r->second->microseconds();

              if (t1 > t2)
                sync_error_ += tool::microseconds (t1 - t2).get_ui();
              else
                sync_error_ += tool::microseconds (t2 - t1).get_ui();
            }
            ++shared_;
# endif // WP_ENABLE_INFO
            win1_.erase(r->first);
            win2_.erase(r->second);
            WP_increase(lhs_total_,
                        fill(win1_, next1_, iterable_->last1_, 1));
            WP_increase(rhs_total_,
                        fill(win2_, next2_, iterable_->last2_, 1));
          }
        else
          {
            if (current_)
              WP_advance(rhs_total_, 2);
            else
              WP_advance(lhs_total_, 1);
          }
        WP_increment(total_);

        update_current();

# ifdef WP_ENABLE_INFO
        if (current_ == -1)
          std::cerr << "INFO: " << shared_ << " frames shared by"
            " both traces.\n"
                    << "INFO: Trace 1 has " << lhs_total_ << " frames ("
                    << (shared_ * 100.f / lhs_total_) << "% shared).\n"
                    << "INFO: Trace 2 has " << rhs_total_ << " frames ("
                    << (shared_ * 100.f / rhs_total_) << "% shared).\n"
                    << "INFO: Output has " << total_ << " frames ("
                    << (shared_ * 100.f / total_) << "% shared).\n"
                    << "INFO: Mean sync. error is "
                    << (sync_error_ / shared_) << " microseconds."
                    << std::endl;
# endif // WP_ENABLE_INFO
      }

# undef WP_advance
# undef WP_increment
# undef WP_increase

      template <class HT, class I1, class I2, class B1, class B2>
      int
      windowed_merge_iterator<HT, I1, I2, B1, B2>::first_packet() const
      {
        const bool first_at_end = win1_.empty();
        const bool second_at_end        = win2_.empty();

        if (first_at_end)
          return second_at_end ? -1 : 1;
        if (second_at_end)
          return 0;

        return win1_.front().microseconds() < win2_.front().microseconds() ?
          0 : 1;
      }

      template <class HT, class I1, class I2, class B1, class B2>
      void
      windowed_merge_iterator<HT, I1, I2, B1, B2>::update_current()
      {
        switch (current_ = first_packet())
          {
          case -1:
            this->value() = boost::none_t ();
            break;

          case 0:
            this->value() = win1_.front();
            break;

          case 1:
            this->value() = win2_.front();
            break;

          default:
            throw std::logic_error ("Internal error, this code should not "
                                    "be reachable.  Please fill a bug "
                                    "report.");
          }
      }

      template <class HT, class I1, class I2, class B1, class B2>
      template <class WindowType, class I>
      unsigned
      windowed_merge_iterator<HT, I1, I2, B1, B2>::
      fill(WindowType&  w,
           I&                   i,
           const I&             last,
           size_t               n)
      {
        unsigned r;

        for (r = 0; r < n and i != last; ++r)
          w.push_back(*i++);
        return r;
      }

      template <class HT, class I1, class I2, class B1, class B2>
      typename windowed_merge_iterator<HT, I1, I2, B1, B2>::optional_match
      windowed_merge_iterator<HT, I1, I2, B1, B2>::match()
      {
        using internals::make_equal;

        if (current_)
          {
            const win1_iterator f = win1_.begin();
            const win1_iterator l = win1_.end();
            const win1_iterator r =
              std::find(f, l,
                        make_equal<HT>(win2_.front(),
                                       iterable_->precision_,
                                       iterable_->phy_end_,
                                       iterable_->pcap_tstamps_));

            if (r == l)
              return boost::none_t ();

            return match_type (r, win2_.begin());
          }
        else
          {
            const win2_iterator f = win2_.begin();
            const win2_iterator l = win2_.end();
            const win2_iterator r =
              std::find(f, l,
                        make_equal<HT>(win1_.front(),
                                       iterable_->precision_,
                                       iterable_->phy_end_,
                                       iterable_->pcap_tstamps_));

            if (r == l)
              return boost::none_t ();

            return match_type (win1_.begin(), r);
          }
      }

    } // End of namespace internals.

    template <class HeaderType,
              class InputIterator1,
              class InputIterator2,
              class Bottom>
    windowed_merge<HeaderType, InputIterator1, InputIterator2, Bottom>::
    windowed_merge(const InputIterator1& first1, const InputIterator1& last1,
                   const InputIterator2& first2, const InputIterator2& last2,
                   const unsigned               precision,
                   const tool::end::endianness  phy_end,
                   const bool                   pcap_tstamps):
      precision_ (precision),
      phy_end_ (phy_end),
      pcap_tstamps_ (pcap_tstamps),
      first1_ (first1),
      last1_ (last1),
      first2_ (first2),
      last2_ (last2)
    {
    }

  } // End of namespace wpl::filter.

} // End of namespace wpl.

#endif // ! FILTER_WINDOWED_MERGE_HXX_

---