1 //============================================================================== 2 // 3 // This file is part of GPSTk, the GPS Toolkit. 4 // 5 // The GPSTk is free software; you can redistribute it and/or modify 6 // it under the terms of the GNU Lesser General Public License as published 7 // by the Free Software Foundation; either version 3.0 of the License, or 8 // any later version. 9 // 10 // The GPSTk is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU Lesser General Public License for more details. 14 // 15 // You should have received a copy of the GNU Lesser General Public 16 // License along with GPSTk; if not, write to the Free Software Foundation, 17 // Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110, USA 18 // 19 // This software was developed by Applied Research Laboratories at the 20 // University of Texas at Austin. 21 // Copyright 2004-2020, The Board of Regents of The University of Texas System 22 // 23 //============================================================================== 24 25 //============================================================================== 26 // 27 // This software was developed by Applied Research Laboratories at the 28 // University of Texas at Austin, under contract to an agency or agencies 29 // within the U.S. Department of Defense. The U.S. Government retains all 30 // rights to use, duplicate, distribute, disclose, or release this software. 31 // 32 // Pursuant to DoD Directive 523024 33 // 34 // DISTRIBUTION STATEMENT A: This software has been approved for public 35 // release, distribution is unlimited. 36 // 37 //============================================================================== 38 39 /** 40 * @file FileFilter.hpp 41 * A framework for sorting and filtering file data. 42 */ 43 44 #ifndef GPSTK_FILEFILTER_HPP 45 #define GPSTK_FILEFILTER_HPP 46 47 #include <functional> 48 #include <algorithm> 49 #include <iterator> 50 51 #include "FFData.hpp" 52 #include "FileSpec.hpp" 53 54 namespace gpstk 55 { 56 /** @defgroup FileDirProc File and Directory Processing Utilities 57 * Tools for locating and processing files in a directory 58 * structure using TimeHandling formatting and data 59 * filtering. */ 60 61 /// @ingroup FileDirProc 62 //@{ 63 64 /** 65 * This class is a framework for sorting and filtering file data. 66 * It borrows several datatypes from FileSpec for cohesion of data 67 * types. Add the data to the filter, specify the parameters (date, 68 * exclusion filters, etc.), then process it. For the specific data 69 * type, you can specify your own operators for sorting, uniqueness, 70 * or almost anything else you want to do to the data. 71 * 72 * @warning The FFData class you're sorting MUST have a weak strict 73 * ordering as defined in the FileFilterOperator. 74 */ 75 template<class FileData> 76 class FileFilter 77 { 78 public: 79 /// Default constructor 80 FileFilter(void); 81 82 /// Destructor 83 virtual ~FileFilter(); 84 85 /// Adds the given data into the filter. 86 FileFilter& addData(const FileData& ffd); 87 88 /// Adds arbitrary data to the filter. 89 FileFilter& addData(const std::list<FileData>& datavec); 90 91 /// Sorts the data. 92 /// @warning bp MUST be a strict weak ordering! 93 template <class Compare> sort(Compare comp)94 FileFilter& sort(Compare comp) 95 { 96 // FIX: this someday... 97 // this is a total hack until Solaris gets their act together and 98 // gets list::sort() working again 99 // all the code below can be replaced (someday) by this one line: 100 // dataVec.sort(comp); 101 102 // make a vector of pointer to list iterator objects... 103 std::vector<lItrType> data(dataVec.size()); 104 lItrType itr = dataVec.begin(); 105 typename std::vector<lItrType>::size_type i = 0; 106 while (itr != dataVec.end()) 107 { 108 data[i] = itr; 109 i++; 110 itr++; 111 } 112 113 // use SortAdapter to use comp with the pointer vector 114 // then sort the vector 115 SortAdapter<Compare> sa(comp); 116 std::stable_sort(data.begin(), data.end(), sa); 117 118 // make a new list of the data in the right order, then copy that 119 // over dataVec. 120 lType fdlist; 121 for (i = 0; i < data.size(); i++) 122 { 123 fdlist.push_back(*data[i]); 124 } 125 dataVec = fdlist; 126 127 /* 128 // move the items into the correct order with splice. 129 // splice does nothing if (itr == data[i]) || (itr == ++data[i]) 130 // so the data is inserted backwards to avoid this... 131 i = data.size(); 132 while (i != 0) 133 { 134 itr = dataVec.begin(); 135 --i; 136 dataVec.splice(itr, dataVec, data[i]); 137 } 138 */ 139 140 return *this; 141 } 142 143 144 /// Combines the data from the input filter to this object. 145 FileFilter& merge(const FileFilter& right); 146 147 /// Combines the data from the input filter to this object using 148 /// the predicate to sort the data it merges. 149 /// This should use list::merge(list, bp) but since it's broken in 150 /// forte... 151 template <class Compare> merge(const FileFilter & right,Compare bp)152 FileFilter& merge(const FileFilter& right, Compare bp) 153 { merge(right); sort(bp); return *this; } 154 155 /// After sorting, use this to ensure that each data value is unique. 156 /// Filtered count is incremented for each duplicate value removed. 157 /// @param bp Test for equality 158 /// @warning The data must be sorted first 159 template <class BinaryPredicate> unique(BinaryPredicate bp)160 FileFilter& unique(BinaryPredicate bp) 161 { 162 // FIX: unique is broken or doesnt like my syntax 163 // so i wrote my own version of it. 164 // list<FileData>::iterator itr = 165 // unique(dataVec.begin(), dataVec.end(), bp); 166 filtered = 0; 167 168 typename std::list<FileData>::iterator first = dataVec.begin(); 169 typename std::list<FileData>::iterator second= dataVec.begin(); 170 171 if (second != dataVec.end() ) 172 second++; 173 else 174 return *this; // empty list 175 176 // keep only the first of many unique values 177 while (second != dataVec.end()) 178 { 179 if ( bp(*first, *second)) 180 { 181 second = dataVec.erase(second); 182 filtered++; 183 } 184 else 185 { 186 first++; 187 second++; 188 } 189 } 190 191 return *this; 192 } 193 194 /// This filters data based on a single test. All data that 195 /// passes the UnaryPredicate (i.e. it returns true) is removed 196 /// Filtered count is incremented for each value removed. 197 /// @warning Depending on the filter, your data may need to be sorted 198 template <class Predicate> filter(Predicate up)199 FileFilter& filter(Predicate up) 200 { 201 // delete all values for which up() is true 202 filtered = 0; 203 204 typename std::list<FileData>::iterator itr = dataVec.begin(); 205 206 while (itr != dataVec.end()) 207 { 208 if (up(*itr)) 209 { 210 itr = dataVec.erase(itr); 211 filtered++; 212 } 213 else 214 itr++; 215 } 216 217 return *this; 218 } 219 220 /// Applies Operation on all the data elements, counting each one that 221 /// gets modified (for which Operation returns true). The operation 222 /// is passed by reference so that it can retain state information 223 /// for use by the program calling it. 224 template <class Operation> touch(Operation & op)225 FileFilter& touch(Operation& op) 226 { 227 filtered = 0; 228 229 typename std::list<FileData>::iterator itr = dataVec.begin(); 230 231 while (itr != dataVec.end()) 232 { 233 if (op(*itr)) 234 filtered++; 235 itr++; 236 } 237 238 return *this; 239 } 240 241 /// a const operator touch for the classes that need it. 242 template <class Operation> touch(const Operation & op)243 FileFilter& touch(const Operation& op) 244 { 245 Operation o(op); 246 return touch(o); 247 } 248 249 /// Returns two lists - one of the data in *this that isn't in r and 250 /// the second of data in r that isn't in *this. Remember that /a p 251 /// has to be a strict weak ordering on the data. 252 /// @warning the input data needs to be sorted according to /a p 253 /// before running diff(). This also means that /a p is a strict 254 /// weak ordering on the data (i.e. /a p sorts the data). 255 template <class BinaryPredicate> 256 std::pair< std::list<FileData>, std::list<FileData> > diff(const FileFilter<FileData> & r,BinaryPredicate p) const257 diff(const FileFilter<FileData>& r, BinaryPredicate p) const 258 { 259 std::pair< std::list<FileData>, std::list<FileData> > toReturn; 260 261 std::set_difference(dataVec.begin(), dataVec.end(), 262 r.dataVec.begin(), r.dataVec.end(), 263 std::inserter(toReturn.first, 264 toReturn.first.begin()), 265 p); 266 267 std::set_difference(r.dataVec.begin(), r.dataVec.end(), 268 dataVec.begin(), dataVec.end(), 269 std::inserter(toReturn.second, 270 toReturn.second.begin()), 271 p); 272 273 return toReturn; 274 } 275 276 /// Returns a list of data matching the given unary predicate. 277 template <class Predicate> findAll(Predicate p) const278 std::list<FileData> findAll(Predicate p) const 279 { 280 std::list<FileData> toReturn; 281 typename std::list<FileData>::const_iterator itr = dataVec.begin(); 282 283 while (itr != dataVec.end()) 284 { 285 if (p(*itr)) 286 toReturn.push_back((*itr)); 287 itr++; 288 } 289 290 return toReturn; 291 } 292 293 /// Returns the number of items filtered from the last filter() 294 /// touch() or unique() call. getFiltered() const295 int getFiltered() const 296 { return filtered; } 297 298 /// Returns the contents of the data list. getData(void)299 std::list<FileData>& getData(void) 300 { return dataVec; } 301 302 /// Returns the contents of the data list, const. getData(void) const303 std::list<FileData> getData(void) const 304 { return dataVec; } 305 306 /// Returns the number of data items in the filter. getDataCount(void) const307 typename std::list<FileData>::size_type getDataCount(void) const 308 { return dataVec.size(); } 309 begin() const310 typename std::list<FileData>::const_iterator begin() const 311 { return dataVec.begin(); } 312 end() const313 typename std::list<FileData>::const_iterator end() const 314 { return dataVec.end(); } 315 begin()316 typename std::list<FileData>::iterator begin() 317 { return dataVec.begin(); } 318 end()319 typename std::list<FileData>::iterator end() 320 { return dataVec.end(); } 321 empty() const322 bool empty() const 323 { return dataVec.empty(); } 324 clear()325 void clear() 326 { dataVec.clear(); } 327 size()328 typename std::list<FileData>::size_type size() 329 { return dataVec.size(); } 330 front()331 FileData& front() 332 { 333 GPSTK_ASSERT(!empty()); 334 return dataVec.front(); 335 } 336 front() const337 const FileData& front() const 338 { 339 GPSTK_ASSERT(!empty()); 340 return dataVec.front(); 341 } 342 back()343 FileData& back() 344 { 345 GPSTK_ASSERT(!empty()); 346 return dataVec.back(); 347 } 348 back() const349 const FileData& back() const 350 { 351 GPSTK_ASSERT(!empty()); 352 return dataVec.back(); 353 } 354 355 protected: 356 /// List of file data to be filtered. 357 typedef std::list<FileData> lType; 358 lType dataVec; 359 typedef typename std::list<FileData>::iterator lItrType; 360 361 /// SortAdapter is an adapter class that takes any comparison 362 /// function and instead uses list iterator objects instead 363 /// of FileData. This is only used by sort() and shouldn't be 364 /// used elsewhere. 365 template<class Compare> 366 class SortAdapter : 367 public std::binary_function<lItrType, lItrType, bool> 368 { 369 public: SortAdapter(Compare & c)370 SortAdapter(Compare& c) 371 : comp(c) 372 {} 373 operator ()(const lItrType l,const lItrType r) const374 bool operator()(const lItrType l, 375 const lItrType r) const 376 { 377 return comp(*l, *r); 378 } 379 private: 380 Compare comp; 381 }; 382 383 /// A count of the last number of items filtered 384 int filtered; 385 }; 386 387 //@} 388 389 template<class FileData> FileFilter(void)390 FileFilter<FileData> :: FileFilter(void) 391 : filtered(0) 392 {} 393 394 template<class FileData> ~FileFilter()395 FileFilter<FileData> :: ~FileFilter() 396 { 397 } 398 399 template<class FileData> 400 FileFilter<FileData>& FileFilter<FileData> :: addData(const FileData & ffd)401 addData(const FileData& ffd) 402 { 403 dataVec.push_back(ffd); 404 return *this; 405 } 406 407 template <class FileData> 408 FileFilter<FileData>& FileFilter<FileData> :: addData(const std::list<FileData> & datavec)409 addData(const std::list<FileData>& datavec) 410 { 411 std::copy(datavec.begin(), datavec.end(), 412 std::inserter(dataVec, dataVec.begin())); 413 return *this; 414 } 415 416 template <class FileData> 417 FileFilter<FileData>& 418 FileFilter<FileData> :: merge(const FileFilter<FileData> & right)419 merge(const FileFilter<FileData>& right) 420 { 421 // cast out const to use the non-const version of getData() 422 FileFilter<FileData>& r = (FileFilter<FileData>&)(right); 423 424 // copy rightData into *this 425 std::list<FileData>& rightData = r.getData(); 426 std::copy(rightData.begin(), rightData.end(), 427 std::inserter(dataVec, dataVec.begin())); 428 429 return *this; 430 } 431 432 } // namespace gpstk 433 434 #endif // GPSTK_FILEFILTER_HPP 435