include/wipal/wifi/traces/extended_merge.hxx

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

# include "extended_merge.hxx"

# include <set>
# include <map>
# include <utility>
# include <iostream>

# include <boost/lexical_cast.hpp>
# include <boost/tuple/tuple.hpp>
# include <boost/tuple/tuple_comparison.hpp>

# include <wipal/pcap/stream.hh>
# include <wipal/wifi/traces/merge.hh>
# include <wipal/wifi/traces/similarity.hh>

namespace wpl
{

  namespace wifi
  {

    namespace merge_helpers
    {

      template <class Iterator>
      struct extended_merge_state
      {
        typedef std::map<Iterator, std::string>         parent_map;

        extended_merge_state(opt::list& options): options_ (options),
                                                  merge_count_ (0)
        {
          typedef std::set< std::pair<unsigned, unsigned> >     blist_type;

          if (not options_.count("ref_blacklist"))
            options_.add("ref_blacklist", blist_type ());
        }

        parent_map&
        pmap()
        {
          return pmap_;
        }

        const parent_map&
        pmap() const
        {
          return pmap_;
        }

        std::string
        output() const
        {
          return "merge-" + boost::lexical_cast<std::string>(merge_count_);
        }

        void
        update_parent(const std::string& parent_name)
        {
          const std::string& o = output();

          BOOST_FOREACH(typename parent_map::value_type& p, pmap_)
            if (p.second == parent_name)
              p.second = o;
        }

        template <class U, class P,
                  template <class, class, class> class I,
                  template <class, class, class, class> class M,
                  class T1, class T2>
        void
        merge(T1& lhs, T2& rhs)
        {
          ++merge_count_;

          const std::string     out_name = output();

# ifdef WP_ENABLE_INFO
          std::cerr << "INFO: Begining a new merge operation.\n"
                    << "INFO: Trace 1 is " << lhs << ".\n"
                    << "INFO: Trace 2 is " << rhs << ".\n"
                    << "INFO: Output is " << out_name << "." << std::endl;
# endif // WP_ENABLE_INFO

          // Always use the smallest trace as left hand side, because
          // the intersection process loads all its unique frames into
          // memory.
          wifi::merge<U, P, I, M>(lhs, rhs, out_name, options_);
        }

      private:
        opt::list       options_;
        unsigned        merge_count_;
        parent_map      pmap_;
      };

    } // End of namespace merge_helpers.

    template <class U, class P,
              template <class, class, class> class I,
              template <class, class, class, class> class M,
              class C>
    std::string
    merge(C& traces, opt::list& options)
    {
      typedef typename C::iterator                              iterator;
      typedef merge_helpers::extended_merge_state<iterator>     state;
      typedef typename state::parent_map                        parent_map;
      typedef boost::tuple<unsigned, iterator, iterator>        score;
      typedef std::set<score>                                   score_set;

      state             st (options);
      parent_map&       pm = st.pmap();
      score_set         ss = similarity<U, P, I>(traces, options);

      for (typename score_set::reverse_iterator i = ss.rbegin();
           i != ss.rend();
           ++i)
        {
          iterator                      t1 = boost::get<1>(*i);
          iterator                      t2 = boost::get<2>(*i);

          typename parent_map::iterator t1_parent = pm.find(t1);
          typename parent_map::iterator t2_parent = pm.find(t2);

          if (t1_parent != pm.end())
            {
              if (t2_parent != pm.end())
                {
                  const std::string     t1_trace_name = t1_parent->second;
                  const std::string     t2_trace_name = t2_parent->second;

                  if (t1_trace_name == t2_trace_name)
                    continue;

                  pcap::file<>          t1_trace (t1_trace_name);
                  pcap::file<>          t2_trace (t2_trace_name);

                  if (t1_trace.filesize() < t2_trace.filesize())
                    st.merge<U, P, I, M>(t1_trace, t2_trace);
                  else
                    st.merge<U, P, I, M>(t2_trace, t1_trace);
                  st.update_parent(t1_trace_name);
                  st.update_parent(t2_trace_name);
                }
              else
                {
                  const std::string     t1_trace_name = t1_parent->second;
                  pcap::file<>          t1_trace (t1_trace_name);

                  st.merge<U, P, I, M>(*t2, t1_trace);
                  st.update_parent(t1_trace_name);
                  pm[t2] = st.output();
                }
            }
          else
            {
              if (t2_parent != pm.end())
                {
                  const std::string     t2_trace_name = t2_parent->second;
                  pcap::file<>          t2_trace (t2_trace_name);

                  st.merge<U, P, I, M>(*t1, t2_trace);
                  pm[t1] = st.output();
                  st.update_parent(t2_trace_name);
                }
              else
                {
                  st.merge<U, P, I, M>(*t1, *t2);
                  pm[t1] = st.output();
                  pm[t2] = st.output();
                }
            }
        }

      return st.output();
    }

  } // End of namespace wpl::wifi.

} // End of namespace wpl.

#endif // ! WIFI_TRACES_EXTENDED_MERGE_HXX_

---