#pragma ident "$Id: FileFilter.hpp 70 2006-08-01 18:36:21Z ehagen $"



/**
 * @file FileFilter.hpp
 * A framework for sorting and filtering file data.
 */

#ifndef GPSTK_FILEFILTER_HPP
#define GPSTK_FILEFILTER_HPP

//============================================================================
//
//  This file is part of GPSTk, the GPS Toolkit.
//
//  The GPSTk is free software; you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published
//  by the Free Software Foundation; either version 2.1 of the License, or
//  any later version.
//
//  The GPSTk 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 Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with GPSTk; if not, write to the Free Software Foundation,
//  Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//  
//  Copyright 2004, The University of Texas at Austin
//
//============================================================================

//============================================================================
//
//This software developed by Applied Research Laboratories at the University of
//Texas at Austin, under contract to an agency or agencies within the U.S. 
//Department of Defense. The U.S. Government retains all rights to use,
//duplicate, distribute, disclose, or release this software. 
//
//Pursuant to DoD Directive 523024 
//
// DISTRIBUTION STATEMENT A: This software has been approved for public 
//                           release, distribution is unlimited.
//
//=============================================================================






#include <functional>
#include <algorithm>

#include "FFData.hpp"
#include "FileSpec.hpp"

namespace gpstk
{
   /** @defgroup filedirgroup File and Directory Processing Utilities */
   //@{

      /**
       * This class is a framework for sorting and filtering file data.
       * It borrows several datatypes from FileSpec for cohesion of data
       * types.  Add the data to the filter, specify the parameters (date,
       * exclusion filters, etc.), then process it.  For the specific data
       * type, you can specify your own operators for sorting, uniqueness,
       * or almost anything else you want to do to the data.
       *
       * @warning The FFData class you're sorting MUST have a weak strict
       * ordering as defined in the FileFilterOperator.
       */

   template<class FileData>
   class FileFilter
   {
   public:
         /// Default constructor
      FileFilter(void);

         /// Destructor
      virtual ~FileFilter();

         /// Adds the given data into the filter.
      FileFilter& addData(const FileData& ffd);

         /// Adds arbitrary data to the filter.
      FileFilter& addData(const std::list<FileData>& datavec);

         /// Sorts the data.
         /// @warning bp MUST be a strict weak ordering!
      template <class Compare>
      FileFilter& sort(Compare comp)
     {
         // FIX: this someday...
         // this is a total hack until Solaris gets their act together and
         // gets list::sort() working again
         // all the code below can be replaced (someday) by this one line:
         //      dataVec.sort(comp);

         // make a vector of pointer to list iterator objects...
      std::vector<lItrType> data(dataVec.size());
      lItrType itr = dataVec.begin();
      typename std::vector<lItrType>::size_type i = 0;
      while (itr != dataVec.end())
      {
         data[i] = itr;
         i++;
         itr++;
      }
      
         // use SortAdapter to use comp with the pointer vector
         // then sort the vector
      SortAdapter<Compare> sa(comp);
      std::stable_sort(data.begin(), data.end(), sa);
      
         // make a new list of the data in the right order, then copy that
         // over dataVec.
      lType fdlist;
      for (i = 0; i < data.size(); i++)
      {
         fdlist.push_back(*data[i]);
      }
      dataVec = fdlist;
      
/*
         // move the items into the correct order with splice.
         // splice does nothing if (itr == data[i]) || (itr == ++data[i])
         // so the data is inserted backwards to avoid this...
      i = data.size();
      while (i != 0)
      {
         itr = dataVec.begin();
         --i;
         dataVec.splice(itr, dataVec, data[i]);
      }
*/            
      return *this;
   }


         /// Combines the data from the input filter to this object.
      FileFilter& merge(const FileFilter& right);

         /// Combines the data from the input filter to this object using
         /// the predicate to sort the data it merges.
         /// This should use list::merge(list, bp) but since it's broken in
         /// forte...
      template <class Compare>
      FileFilter& merge(const FileFilter& right, Compare bp)
         { merge(right); sort(bp); return *this; }

         /// After sorting, use this to filter the data.
         /// @warning The data must be sorted first
      template <class BinaryPredicate>
      FileFilter& unique(BinaryPredicate bp)
   {
         //  FIX: unique is broken or doesnt like my syntax
         //  so i wrote my own version of it
//      list<FileData>::iterator itr = 
//         unique(dataVec.begin(), dataVec.end(), bp);
      filtered = 0;
      
      typename std::list<FileData>::iterator first = dataVec.begin();
      typename std::list<FileData>::iterator second= dataVec.begin();
      second++;
      
         // keep only the first of many unique values
      while (second != dataVec.end())
      {
         if ( bp(*first, *second))
         {
            second = dataVec.erase(second);
            filtered++;
         }
         else
         {
            first++;
            second++;
         }
      }
      
      return *this;
   }

         /// This filters data based on a single test.  All data that
         /// passes the UnaryPredicate (i.e. it returns true) is removed
         /// @warning Depending on the filter, your data may need to be sorted
      template <class Predicate>
      FileFilter& filter(Predicate up)
   {
         // delete all values for which up() is true
      filtered = 0;
      
      typename std::list<FileData>::iterator itr = dataVec.begin();
      
      while (itr != dataVec.end())
      {
         if (up(*itr))
         {
            itr = dataVec.erase(itr);
            filtered++;
         }
         else
            itr++;
      }
      
      return *this;
   }

         /// Applies Operation on all the data elements, counting each one that
         /// gets modified (for which Operation returns true). The operation
         /// is passed by reference so that it can retain state information
         /// for use by the program calling it.
      template <class Operation>
      FileFilter& touch(Operation& op)
   {
      filtered = 0;
      
      typename std::list<FileData>::iterator itr = dataVec.begin();
      
      while (itr != dataVec.end())
      {
         if (op(*itr))
            filtered++;
         itr++;
      }
      
      return *this;
   }

         /// a const operator touch for the classes that need it.
      template <class Operation>
      FileFilter& touch(const Operation& op)
         { Operation o(op); return touch(o); }

         /// Returns two lists - one of the data in *this that isn't in r and
         /// the second of data in r that isn't in *this.  Remember that /a p
         /// has to be a strict weak ordering on the data.  
         /// @warning the input data needs to be sorted according to /a p 
         /// before running diff().  This also means that /a p is a strict
         /// weak ordering on the data (i.e. /a p sorts the data).
      template <class BinaryPredicate>
      std::pair< std::list<FileData>, std::list<FileData> > 
      diff(const FileFilter<FileData>& r, BinaryPredicate p) const
   {
      std::pair< std::list<FileData>, std::list<FileData> > toReturn;
      
      std::set_difference(dataVec.begin(), dataVec.end(),
                          r.dataVec.begin(), r.dataVec.end(),
                          std::inserter(toReturn.first, 
                                        toReturn.first.begin()),
                          p);
      
      std::set_difference(r.dataVec.begin(), r.dataVec.end(),
                          dataVec.begin(), dataVec.end(),
                          std::inserter(toReturn.second, 
                                        toReturn.second.begin()),
                          p);
      
      return toReturn;
   }

         /// Returns a list of data matching the given unary predicate.
      template <class Predicate>
      std::list<FileData> findAll(Predicate p) const
   {
      std::list<FileData> toReturn;
      typename std::list<FileData>::const_iterator itr = dataVec.begin();
      
      while (itr != dataVec.end())
      {
         if (p(*itr))
            toReturn.push_back((*itr));
         itr++;
      }
      
      return toReturn;
      
   }

         /// Returns the number of items filtered from the last filter()
         /// touch() or unique() call.
      int getFiltered() const {return filtered;}

         /// Returns the contents of the data list.
      std::list<FileData>& getData(void) {return dataVec;}

         /// Returns the contents of the data list, const.
      std::list<FileData> getData(void) const {return dataVec;}

         /// Returns the number of data items in the filter.
      typename std::list<FileData>::size_type getDataCount(void) const 
         { return dataVec.size(); }

      typename std::list<FileData>::const_iterator begin() const
         { return dataVec.begin(); }

      typename std::list<FileData>::const_iterator end() const
         { return dataVec.end(); }

      typename std::list<FileData>::iterator begin() 
         { return dataVec.begin(); }

      typename std::list<FileData>::iterator end() 
         { return dataVec.end(); }

      bool empty() const
         { return dataVec.empty(); }

      void clear()
         { dataVec.clear(); }

      typename std::list<FileData>::size_type size()
         { return dataVec.size(); }

      FileData& front()
         { return dataVec.front(); }

      const FileData& front() const
         { return dataVec.front(); }

      FileData& back()
         { return dataVec.back(); }

      const FileData& back() const
         { return dataVec.back(); }

   protected:
         /// List of file data to be filtered.
      typedef std::list<FileData> lType;
      lType dataVec;
      typedef typename std::list<FileData>::iterator lItrType;

         /// SortAdapter is an adapter class that takes any comparison
         /// function and instead uses list iterator objects instead
         /// of FileData.  This is only used by sort() and shouldn't be 
         /// used elsewhere.
      template<class Compare>
      class SortAdapter  : 
         public std::binary_function<lItrType, lItrType, bool>
      {
      public:
         SortAdapter(Compare& c)
               : comp(c)
            {}

         bool operator()(const lItrType l,
                         const lItrType r) const
            {
               return comp(*l, *r);
            }
      private:
         Compare comp;
      };

         /// A count of the last number of items filtered
      int filtered;
   };

   //@}

      template<class FileData>
   FileFilter<FileData> :: FileFilter(void)
         : filtered(0)
   {}

   template<class FileData>
   FileFilter<FileData> :: ~FileFilter()
   {
   }

   template<class FileData>
   FileFilter<FileData>& FileFilter<FileData> :: 
   addData(const FileData& ffd)
   {
      dataVec.push_back(ffd);
      return *this;
   }

   template <class FileData>
   FileFilter<FileData>& FileFilter<FileData> :: 
   addData(const std::list<FileData>& datavec)
   {
      std::copy(datavec.begin(), datavec.end(),
                std::inserter(dataVec, dataVec.begin()));
      return *this;
   }
   
   template <class FileData>
   FileFilter<FileData>&
   FileFilter<FileData> ::
   merge(const FileFilter<FileData>& right)
   {
         // cast out const to use the non-const version of getData()
      FileFilter<FileData>& r = (FileFilter<FileData>&)(right);
      
         // copy rightData into *this
      std::list<FileData>& rightData = r.getData();
      std::copy(rightData.begin(), rightData.end(),
                std::inserter(dataVec, dataVec.begin()));
      
      return *this;
   }

} // namespace gpstk

#endif // GPSTK_FILEFILTER_HPP
