src/utils/bamtools_filter_engine.h

   1 // ***************************************************************************
   2 // bamtools_filter_engine.h (c) 2010 Derek Barnett, Erik Garrison
   3 // Marth Lab, Department of Biology, Boston College
   4 // All rights reserved.
   5 // ---------------------------------------------------------------------------
   6 // Last modified: 30 August 2010
   7 // ---------------------------------------------------------------------------
   8 //
   9 // ***************************************************************************
  10
  11 #ifndef BAMTOOLS_FILTER_ENGINE_H
  12 #define BAMTOOLS_FILTER_ENGINE_H
  13
  14 #include <algorithm>
  15 #include <map>
  16 #include <sstream>
  17 #include <string>
  18 #include <utility>
  19 #include <vector>
  20 #include "bamtools_utilities.h"
  21 #include "bamtools_variant.h"
  22
  23 namespace BamTools {
  24
  25 struct PropertyFilterValue {
  26
  27     // define valid ValueCompareTypes
  28     enum ValueCompareType { CONTAINS = 0
  29                           , ENDS_WITH
  30                           , EXACT
  31                           , GREATER_THAN
  32                           , GREATER_THAN_EQUAL
  33                           , LESS_THAN
  34                           , LESS_THAN_EQUAL
  35                           , NOT
  36                           , STARTS_WITH
  37                           };
  38
  39     // ctor
  40     PropertyFilterValue(const Variant& value = Variant(),
  41                         const ValueCompareType& type = PropertyFilterValue::EXACT)
  42         : Value(value)
  43         , Type(type)
  44     { }
  45
  46     // filter check methods
  47     template<typename T>
  48     bool check(const T& query) const;
  49     bool check(const std::string& query) const;
  50
  51     // data members
  52     Variant Value;
  53     ValueCompareType Type;
  54 };
  55
  56 inline
  57 const std::string toString(const PropertyFilterValue::ValueCompareType& type) {
  58
  59     switch ( type ) {
  60         case ( PropertyFilterValue::CONTAINS )           : return std::string( "CONTAINS");
  61         case ( PropertyFilterValue::ENDS_WITH )          : return std::string( "ENDS_WITH");
  62         case ( PropertyFilterValue::EXACT )              : return std::string( "EXACT");
  63         case ( PropertyFilterValue::GREATER_THAN )       : return std::string( "GREATER_THAN");
  64         case ( PropertyFilterValue::GREATER_THAN_EQUAL ) : return std::string( "GREATER_THAN_EQUAL");
  65         case ( PropertyFilterValue::LESS_THAN )          : return std::string( "LESS_THAN");
  66         case ( PropertyFilterValue::LESS_THAN_EQUAL )    : return std::string( "LESS_THAN_EQUAL");
  67         case ( PropertyFilterValue::NOT )                : return std::string( "NOT");
  68         case ( PropertyFilterValue::STARTS_WITH )        : return std::string( "STARTS_WITH");
  69         default : BAMTOOLS_ASSERT_UNREACHABLE;
  70     }
  71     return std::string();
  72 }
  73
  74 // property name => property filter value
  75 // ('name' => ('SSR', STARTS_WITH), 'mapQuality' => (50, GREATER_THAN_EQUAL), etc...)
  76 typedef std::map<std::string, PropertyFilterValue> PropertyMap;
  77
  78 struct PropertyFilter {
  79
  80     // will be used more later
  81     // if we implement a compound 'rules' system  - i.e. "(filter1 AND filter2) OR filter 3"
  82     enum FilterCompareType { AND = 0
  83                            , EXACT
  84                            , NOT
  85                            , OR
  86                            };
  87
  88     // data members
  89     PropertyMap Properties;
  90     FilterCompareType Type;
  91
  92     // ctor
  93     PropertyFilter(void) : Type( PropertyFilter::EXACT ) { }
  94
  95     // filter check methods
  96     template<typename T>
  97     bool check(const std::string& propertyName, const T& query) const;
  98 };
  99
 100 // filter name => properties
 101 // ('filter1' => properties1, 'filter2' => properties2, etc...)
 102 typedef std::map<std::string, PropertyFilter> FilterMap;
 103
 104 // used to store properties known to engine & keep track of enabled state
 105 struct Property {
 106     std::string Name;
 107     bool IsEnabled;
 108     Property(const std::string& name, bool isEnabled = false)
 109         : Name(name)
 110         , IsEnabled(isEnabled)
 111     { }
 112 };
 113
 114 inline bool operator<  (const Property& lhs, const Property& rhs) { return lhs.Name <  rhs.Name; }
 115 inline bool operator== (const Property& lhs, const Property& rhs) { return lhs.Name == rhs.Name; }
 116
 117 class FilterEngine {
 118
 119     // 'filter set' methods
 120     public:
 121         // creates a new filter set, returns true if created, false if error or already exists
 122         static bool addFilter(const std::string& filterName);
 123
 124         // return list of current filter names
 125         static const std::vector<std::string> filterNames(void);
 126
 127     // 'property' methods
 128     public:
 129
 130         // add a new known property (& type) to engine
 131         static bool addProperty(const std::string& propertyName);
 132
 133         // sets property filter (value, type) for propertyName, on a particular filter set
 134         // setProperty("filter1", "mapQuality", 50, GREATER_THAN_EQUAL)
 135         template<typename T>
 136         static bool setProperty(const std::string& filterName,
 137                                 const std::string& propertyName,
 138                                 const T& value,
 139                                 const PropertyFilterValue::ValueCompareType& type = PropertyFilterValue::EXACT);
 140
 141         // returns list of all properties known by FilterEngine  ( any created using addProperty() )
 142         static const std::vector<std::string> allPropertyNames(void);
 143
 144         // returns list of property names that are 'enabled' ( only those touched by setProperty() )
 145         static const std::vector<std::string> enabledPropertyNames(void);
 146
 147     // token parsing (for property filter generation)
 148     public:
 149         template<typename T>
 150         static bool parseToken(const std::string& token, T& value, PropertyFilterValue::ValueCompareType& type);
 151
 152     // query evaluation
 153     public:
 154         // returns true if query passes all filters on 'propertyName'
 155         template<typename T>
 156         static bool check(const std::string& propertyName, const T& query);
 157
 158     // data members
 159     private:
 160         // all 'filter sets'
 161         static FilterMap m_filters;
 162
 163         // all known properties
 164         static std::vector<Property> m_properties;
 165
 166         // token-parsing constants
 167         static const int NOT_CHAR          = (int)'!';
 168         static const int EQUAL_CHAR        = (int)'=';
 169         static const int GREATER_THAN_CHAR = (int)'>';
 170         static const int LESS_THAN_CHAR    = (int)'<';
 171         static const int WILDCARD_CHAR     = (int)'*';
 172 };
 173
 174 // -------------------------------------------------------------------
 175 // template methods
 176
 177 // checks a query against a filter (value, compare type)
 178 template<typename T>
 179 bool PropertyFilterValue::check(const T& query) const {
 180
 181     // ensure filter value & query are same type
 182     if ( !Value.is_type<T>() ) {
 183         std::cerr << "Cannot compare different types!" << std::endl;
 184         return false;
 185     }
 186
 187     // string matching
 188     if ( Value.is_type<std::string>() ) {
 189         std::cerr << "Cannot compare different types - query is a string!" << std::endl;
 190         return false;
 191     }
 192
 193     // numeric matching based on our filter type
 194     switch ( Type ) {
 195         case ( PropertyFilterValue::EXACT)              : return ( query == Value.get<T>() );
 196         case ( PropertyFilterValue::GREATER_THAN)       : return ( query >  Value.get<T>() );
 197         case ( PropertyFilterValue::GREATER_THAN_EQUAL) : return ( query >= Value.get<T>() );
 198         case ( PropertyFilterValue::LESS_THAN)          : return ( query <  Value.get<T>() );
 199         case ( PropertyFilterValue::LESS_THAN_EQUAL)    : return ( query <= Value.get<T>() );
 200         case ( PropertyFilterValue::NOT)                : return ( query != Value.get<T>() );
 201         default : BAMTOOLS_ASSERT_UNREACHABLE;
 202     }
 203     return false;
 204 }
 205
 206 template<typename T>
 207 bool PropertyFilter::check(const std::string& propertyName, const T& query) const {
 208
 209     // if propertyName found for this filter,
 210     PropertyMap::const_iterator propIter = Properties.find(propertyName);
 211     if ( propIter != Properties.end() ) {
 212       const PropertyFilterValue& filterValue = (*propIter).second;
 213
 214       // check
 215       switch ( Type ) {
 216           case ( PropertyFilter::EXACT ) : return filterValue.check(query);
 217           case ( PropertyFilter::NOT )   : return !filterValue.check(query);
 218           case ( PropertyFilter::AND )   :
 219           case ( PropertyFilter::OR )    : BAMTOOLS_ASSERT_MESSAGE(false, "Cannot use a binary compare operator on 1 value");
 220           default : BAMTOOLS_ASSERT_UNREACHABLE;
 221       }
 222       return false; // unreachable
 223     }
 224
 225     // property unknown to this filter
 226     else return true;
 227 }
 228
 229 template<typename T>
 230 bool FilterEngine::parseToken(const std::string& token, T& value, PropertyFilterValue::ValueCompareType& type) {
 231
 232     // skip if token is empty
 233     if ( token.empty() ) return false;
 234
 235     // will store token after special chars are removed
 236     std::string strippedToken;
 237
 238     // if only single character
 239     if ( token.length() == 1 ) {
 240         strippedToken = token;
 241         type = PropertyFilterValue::EXACT;
 242     }
 243
 244     // more than one character, check for special chars
 245     else {
 246         const int firstChar = (int)token.at(0);
 247
 248         switch ( (int)firstChar ) {
 249
 250             case ( (int)FilterEngine::NOT_CHAR ) :
 251
 252                 strippedToken = token.substr(1);
 253                 type = PropertyFilterValue::NOT;
 254
 255                 break;
 256
 257             case ( (int)FilterEngine::GREATER_THAN_CHAR ) :
 258
 259                 // check for '>=' case
 260                 if ( token.at(1) == FilterEngine::EQUAL_CHAR ) {
 261                     if ( token.length() == 2 ) return false;
 262                     strippedToken = token.substr(2);
 263                     type = PropertyFilterValue::GREATER_THAN_EQUAL;
 264                 }
 265
 266                 // otherwise only '>'
 267                 else {
 268                     strippedToken = token.substr(1);
 269                     type = PropertyFilterValue::GREATER_THAN;
 270                 }
 271
 272                 break;
 273
 274             case ( (int)FilterEngine::LESS_THAN_CHAR ) :
 275
 276                 // check for '<=' case
 277                 if ( token.at(1) == FilterEngine::EQUAL_CHAR ) {
 278                     if ( token.length() == 2 ) return false;
 279                     strippedToken = token.substr(2);
 280                     type = PropertyFilterValue::LESS_THAN_EQUAL;
 281                 }
 282
 283                 // otherwise only '<'
 284                 else {
 285                     strippedToken = token.substr(1);
 286                     type = PropertyFilterValue::LESS_THAN;
 287                 }
 288
 289                 break;
 290
 291             case ( (int)FilterEngine::WILDCARD_CHAR ) :
 292
 293                 // check for *str* case (CONTAINS)
 294                 if ( token.at( token.length() - 1 ) == FilterEngine::WILDCARD_CHAR ) {
 295                     if ( token.length() == 2 ) return false;
 296                     strippedToken = token.substr(1, token.length() - 2);
 297                     type = PropertyFilterValue::CONTAINS;
 298                 }
 299
 300                 // otherwise *str case (ENDS_WITH)
 301                 else {
 302                     strippedToken = token.substr(1);
 303                     type = PropertyFilterValue::ENDS_WITH;
 304                 }
 305
 306                 break;
 307
 308
 309             default :
 310
 311                 // check for str* case (STARTS_WITH)
 312                 if ( token.at( token.length() - 1 ) == FilterEngine::WILDCARD_CHAR ) {
 313                     if ( token.length() == 2 ) return false;
 314                     strippedToken = token.substr(0, token.length() - 1);
 315                     type = PropertyFilterValue::STARTS_WITH;
 316                 }
 317
 318                 // otherwise EXACT
 319                 else {
 320                     strippedToken = token;
 321                     type = PropertyFilterValue::EXACT;
 322                 }
 323
 324                 break;
 325         }
 326     }
 327
 328     // convert stripped token to value
 329     std::stringstream stream(strippedToken);
 330     if ( strippedToken == "true" || strippedToken == "false" )
 331         stream >> std::boolalpha >> value;
 332     else
 333         stream >> value;
 334
 335     // check for valid CompareType on type T
 336     Variant variantCheck = value;
 337
 338     // if T is not string AND CompareType is for string values, return false
 339     if ( !variantCheck.is_type<std::string>() ) {
 340         if ( type == PropertyFilterValue::CONTAINS ||
 341              type == PropertyFilterValue::ENDS_WITH ||
 342              type == PropertyFilterValue::STARTS_WITH )
 343
 344           return false;
 345     }
 346
 347     // return success
 348     return true;
 349 }
 350
 351 // sets property filter (value, type) for propertyName, on a particular filter set
 352 // setProperty("filter1", "mapQuality", 50, GREATER_THAN_EQUAL)
 353 template<typename T>
 354 bool FilterEngine::setProperty(const std::string& filterName,
 355                                const std::string& propertyName,
 356                                const T& value,
 357                                const PropertyFilterValue::ValueCompareType& type)
 358 {
 359     // lookup filter by name, return false if not found
 360     FilterMap::iterator filterIter = m_filters.find(filterName);
 361     if ( filterIter == m_filters.end() ) return false;
 362
 363     // lookup property for filter, add new PropertyFilterValue if not found, modify if already exists
 364     PropertyFilter& filter = (*filterIter).second;
 365     PropertyMap::iterator propertyIter = filter.Properties.find(propertyName);
 366
 367     bool success;
 368
 369     // property not found for this filter, create new entry
 370     if ( propertyIter == filter.Properties.end() )
 371         success = (filter.Properties.insert(std::make_pair(propertyName, PropertyFilterValue(value, type)))).second;
 372
 373     // property already exists, modify
 374     else {
 375         PropertyFilterValue& filterValue = (*propertyIter).second;
 376         filterValue.Value = value;
 377         filterValue.Type  = type;
 378         success = true;
 379     }
 380
 381     // if error so far, return false
 382     if ( !success ) return false;
 383
 384     // --------------------------------------------
 385     // otherwise, set Property.IsEnabled to true
 386
 387     // lookup property
 388     std::vector<Property>::iterator knownPropertyIter = std::find( m_properties.begin(), m_properties.end(), propertyName);
 389
 390     // if not found, create a new (enabled) entry (& re-sort list)
 391     if ( knownPropertyIter == m_properties.end() ) {
 392         m_properties.push_back( Property(propertyName, true) );
 393         std::sort( m_properties.begin(), m_properties.end() );
 394     }
 395
 396     // property already known, set as enabled
 397     else
 398         (*knownPropertyIter).IsEnabled = true;
 399
 400     // return success
 401     return true;
 402 }
 403
 404 // returns false if query does not pass any filters on 'propertyName'
 405 // returns true if property unknown (i.e. nothing has been set for this property... so query is considered to pass filter)
 406 template<typename T>
 407 bool FilterEngine::check(const std::string& propertyName, const T& query) {
 408
 409     // check enabled properties list
 410     // return true if no properties enabled at all OR if property is unknown to FilterEngine
 411     const std::vector<std::string> enabledProperties = enabledPropertyNames();
 412     if ( enabledProperties.empty() ) return true;
 413     const bool found = std::binary_search( enabledProperties.begin(), enabledProperties.end(), propertyName );
 414     if ( !found ) return true;
 415
 416     // iterate over all filters in FilterEngine
 417     FilterMap::const_iterator filterIter = m_filters.begin();
 418     FilterMap::const_iterator filterEnd  = m_filters.end();
 419     for ( ; filterIter != filterEnd; ++filterIter ) {
 420
 421         // check query against this filter
 422         const PropertyFilter& filter = (*filterIter).second;
 423         if ( filter.check(propertyName, query) ) return true;
 424     }
 425
 426     // query passes none of the filters with current property enabled
 427     return false;
 428 }
 429
 430 } // namespace BamTools
 431
 432 #endif // BAMTOOLS_FILTER_ENGINE_H