include/wipal/filter/deprecated/old_intersector.hxx

/*
 * WiPal - A library and a set of tools to manipulate wireless traces.
 * Copyright (C) 2007, 2008  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 WIFI_FRAME_FILTER_OLD_INTERSECTOR_HXX_
# define WIFI_FRAME_FILTER_OLD_INTERSECTOR_HXX_

# include <iostream>

# include "old_intersector.hh"

namespace wifi
{
  namespace frame
  {
    namespace filter
    {

      namespace internals
      {

        template <class I1, class I2, class B1, class B2>
        old_intersector_iterator<I1, I2, B1, B2>::
	old_intersector_iterator(const iterable_type& i, bool end):
          super_type (),
          iterable_ (&i),
          next1_ (end ? i.last1_ : i.first1_),
          next2_ (end ? i.last2_ : i.first2_)
# ifndef WP_DONT_USE_HASH
          ,
          arrivals1_ (hash_bucket_count),
          arrivals2_ (hash_bucket_count)
# endif
        {
          if (not end)
            increment();
        }

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

        template <class I1, class I2, class B1, class B2>
        void
        old_intersector_iterator<I1, I2, B1, B2>::increment()
        {
          const I1&             last1 = this->iterable_->last1_;
          const I2&             last2 = this->iterable_->last2_;

          while (next1_ != last1 or next2_ != last2)
            if ((next1_ != last1 and check<false>(next1_, arrivals1_,
                                                  arrivals2_))
                or
                (next2_ != last2 and check<true>(next2_, arrivals2_,
                                                 arrivals1_)))
              return;
          arrivals1_.clear();
          arrivals2_.clear();
          this->value() = boost::none_t ();
        }

        template <class I1, class I2, class B1, class B2>
        template <bool SwapResult, class ArrType, class RHSArrType>
        bool
        old_intersector_iterator<I1, I2, B1, B2>::
        check(I1&               frm,
              ArrType&          frm_arrivals,
              RHSArrType&       rhs_arrivals)
        {
          typename RHSArrType::iterator i = rhs_arrivals.find(*frm);

          if (i == rhs_arrivals.end())
            {
              frm_arrivals.insert(*frm);
              ++frm;
              return false;
            }

          // Basic consistency check.  Needed due to the following
          // optimization (and the fact that theoretically unique
          // frames are not always that unique...)
          {
            const tool::microseconds&   t = i->microseconds();
            const size_t                lhs = SwapResult;
            const size_t                rhs = not SwapResult;

            if (t < last_arrival_[rhs])
              {
                std::cerr << "WARNING: Unique frame " << i->frame_id()
                          << " (" << t << " us) anterior to previous unique "
                             "frame (" << last_arrival_[rhs] << " us), "
                             "ignoring.\n"
                             "WARNING: Probably this frame is not really "
                             "unique inside its trace." << std::endl;
                rhs_arrivals.erase(i);
                frm_arrivals.insert(*frm);
                ++frm;
                return false;
              }
            last_arrival_[lhs] = frm->microseconds();
            last_arrival_[rhs] = t;
          }

          this->value() =
            SwapResult ? value_type (*i, *frm) : value_type (*frm, *i);

          // Cleanup the set of arrivals (i.e. remove frames previous
          // to this one).  We should do it systematically, but that
          // operation takes time.  So we ignore it by default.  We
          // only do it if the set of arrivals is too big (i.e. there
          // is a risk of saturating memory, or the search time may
          // become non-negligible).
          if (rhs_arrivals.size() > arrivals_max_size)
            cleanup_arrivals(i, rhs_arrivals);

          frm_arrivals.clear();
          rhs_arrivals.erase(i);
          ++frm;
          return true;
        }

        template <class I1, class I2, class B1, class B2>
        template <class ArrType>
        void
        old_intersector_iterator<I1, I2, B1, B2>::
        cleanup_arrivals(const typename ArrType::iterator&      frame,
                         ArrType&                               arrivals)
        {
          typedef typename ArrType::iterator    iterator;

          const tool::microseconds      m = frame->microseconds();
          iterator                      i = arrivals.begin();
          const iterator                e = arrivals.end();

          while (i != e)
            {
              if (i->microseconds() < m)
                arrivals.erase(i++);
              else
                ++i;
            }
        }

      } // End of namespace internals.


      template <class I1, class I2, class B>
      old_intersector<I1, I2, B>::old_intersector(const I1& first1,
                                                  const I1& last1,
                                                  const I2& first2,
                                                  const I2& last2):
        first1_ (first1),
        last1_ (last1),
        first2_ (first2),
        last2_ (last2)
      {
      }

    } // End of namespace wifi::frame::filter.

  } // End of namespace wifi::frame.

} // End of namespace wifi.

#endif // ! WIFI_FRAME_FILTER_OLD_INTERSECTOR_HXX_

---