simgear/misc/ListDiff.hxx

   1 ///@file
   2 /// Compare lists and get differences
   3 ///
   4 // Copyright (C) 2013  Thomas Geymayer <tomgey@gmail.com>
   5 //
   6 // This library is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU Library General Public
   8 // License as published by the Free Software Foundation; either
   9 // version 2 of the License, or (at your option) any later version.
  10 //
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // Library General Public License for more details.
  15 //
  16 // You should have received a copy of the GNU Library General Public
  17 // License along with this library; if not, write to the Free Software
  18 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  19
  20 #ifndef SG_LISTDIFF_HXX_
  21 #define SG_LISTDIFF_HXX_
  22
  23 #include <vector>
  24 #include <boost/function.hpp>
  25
  26 namespace simgear
  27 {
  28
  29   template<class T>
  30   struct ListDiff
  31   {
  32     typedef std::vector<T> List;
  33     typedef boost::function<void (T)> Callback;
  34
  35     /**
  36      * Perform list diff in-place (modifies both lists) and call cb_add for
  37      * every element in new_list not in old_list and cb_remove for every element
  38      * in old_list not in new_list.
  39      */
  40     static void inplace( List& old_list,
  41                          List& new_list,
  42                          Callback cb_add,
  43                          Callback cb_remove )
  44     {
  45       // Check which elements have been removed. (Removing first and adding
  46       // second should keep the memory usage lower - not for this function, but
  47       // probably for users of this function which use the callbacks to delete
  48       // and create objects)
  49       while( !old_list.empty() )
  50       {
  51         T& old_el = old_list.front();
  52         typename List::iterator new_el =
  53           std::find(new_list.begin(), new_list.end(), old_el);
  54
  55         if( new_el == new_list.end() )
  56         {
  57           if( cb_remove )
  58             cb_remove(old_el);
  59         }
  60         else
  61         {
  62           // Element is in both lists -> just ignore
  63           *new_el = new_list.back();
  64           new_list.pop_back();
  65         }
  66
  67         old_list.front() = old_list.back();
  68         old_list.pop_back();
  69       }
  70
  71       // All remaing elements in new_list have not been in old_list, so call
  72       // the add callback for every element if required.
  73       if( cb_add )
  74       {
  75         for( typename List::iterator it = new_list.begin();
  76                                      it != new_list.end();
  77                                    ++it )
  78           cb_add(*it);
  79       }
  80     }
  81   };
  82
  83 } // namespace simgear
  84
  85 #endif /* SG_LISTDIFF_HXX_ */