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 // ---------------------------------------------------------------------------
   5 // Last modified: 10 October 2011
   6 // ---------------------------------------------------------------------------
   7 // Provides a generic filter engine based on filter-sets of properties,
   8 // with possible "rules" (compound logical expressions) to create more complex
   9 // queries on a data set.
  10 //
  11 // FilterEngine consists, most importantly, of :
  12 //
  13 //     a list of possible properties (each tagged whether it has been 'enabled' as a filter)
  14 //     a map of filterName => propertySet
  15 //     queue for compound rule expression (i.e. "(filter1 AND filter2) OR !filter3" )
  16 //
  17 // Each propertySet is a list of properties enabled for this particular filter object
  18 //
  19 //     Implemented as a map of propertyNames to propertyFilterValue
  20 //     ( "property1" => pfv1
  21 //       "property2" => pfv2
  22 //       "property4" => pfv4
  23 //       etc. )
  24 //
  25 //     Any properties that are 'possible', via FilterEngine::addProperty(), but not enabled
  26 //     via FilterEngine::setProperty() (in our example, say "property3"), evaluate to true
  27 //     for any query.  Meaning that if a property is not set on this filter, we don't care
  28 //     about it here, so it passes though OK.
  29 //
  30 // A propertyFilterValue contains a value and comparison type
  31 //
  32 //    ( pfv1: Value = 50,    Type = GREATER_THAN_EQUAL
  33 //      pfv2: Value = "foo", Type = STARTS_WITH
  34 //      pfv4: Value = "bar", Type = CONTAINS
  35 //      etc. )
  36 //
  37 //    This allows for more complex queries (than simple isEqual?) against a variety of data types.
  38 //
  39 // ***************************************************************************
  40
  41 #ifndef BAMTOOLS_FILTER_ENGINE_H
  42 #define BAMTOOLS_FILTER_ENGINE_H
  43
  44 #include "utils/utils_global.h"
  45 #include "utils/bamtools_filter_properties.h"
  46 #include "utils/bamtools_filter_ruleparser.h"
  47 #include "utils/bamtools_utilities.h"
  48
  49 #include <algorithm>
  50 #include <iostream>
  51 #include <map>
  52 #include <queue>
  53 #include <sstream>
  54 #include <stack>
  55 #include <string>
  56 #include <utility>
  57 #include <vector>
  58
  59 namespace BamTools {
  60
  61 struct UTILS_EXPORT FilterCompareType {
  62     enum Type { AND = 0
  63               , NOT
  64               , OR
  65     };
  66 };
  67
  68 // -----------------------------------------------------------
  69 // FilterEngine
  70
  71 template <typename FilterChecker>
  72 class UTILS_EXPORT FilterEngine {
  73
  74     // ctor & dtor
  75     public:
  76         FilterEngine(void)
  77             : m_ruleString("")
  78             , m_isRuleQueueGenerated(false)
  79             , m_defaultCompareType(FilterCompareType::OR)
  80             , AND_OPERATOR("&")
  81             , OR_OPERATOR("|")
  82             , NOT_OPERATOR("!")
  83         { }
  84
  85         ~FilterEngine(void) { }
  86
  87     // 'filter set' methods
  88     public:
  89         // creates a new filter set, returns true if created, false if error or already exists
  90         bool addFilter(const std::string& filterName);
  91
  92         // return list of current filter names
  93         const std::vector<std::string> filterNames(void);
  94
  95     // 'property' methods
  96     public:
  97
  98         // add a new known property (& type) to engine
  99         bool addProperty(const std::string& propertyName);
 100
 101         // sets property filter (value, type) for propertyName, on a particular filter set
 102         // setProperty("filter1", "mapQuality", 50, GREATER_THAN_EQUAL)
 103         template<typename T>
 104         bool setProperty(const std::string& filterName,
 105                          const std::string& propertyName,
 106                          const T& value,
 107                          const PropertyFilterValue::ValueCompareType& type = PropertyFilterValue::EXACT);
 108
 109         // returns list of all properties known by FilterEngine  ( any created using addProperty() )
 110         const std::vector<std::string> allPropertyNames(void);
 111
 112         // returns list of property names that are 'enabled' ( only those touched by setProperty() )
 113         const std::vector<std::string> enabledPropertyNames(void);
 114
 115      // 'rule' methods
 116     public:
 117
 118         // sets comparison operator between filters if no rule string given
 119         // default is to do an OR on each filter
 120         void setDefaultCompareType(const FilterCompareType::Type& type = FilterCompareType::OR);
 121
 122         // sets rule string for building expression queue
 123         // if empty, creates
 124         void setRule(const std::string& ruleString = "");
 125
 126     // token parsing (for property filter generation)
 127     public:
 128         template<typename T>
 129         static bool parseToken(const std::string& token, T& value, PropertyFilterValue::ValueCompareType& type);
 130
 131     // query evaluation
 132     public:
 133         // returns true if query passes all filters in FilterEngine
 134         template<typename T>
 135         bool check(const T& query);
 136
 137     // internal rule-handling methods
 138     private:
 139         void buildDefaultRuleString(void);
 140         void buildRuleQueue(void);
 141         template<typename T>
 142         bool evaluateFilterRules(const T& query);
 143
 144     // data members
 145     private:
 146         // all 'filter sets'
 147         FilterMap m_filters;
 148
 149         // all known properties
 150         std::vector<Property> m_properties;
 151
 152         // infix expression of filter-set comparison rules
 153         std::string m_ruleString;
 154
 155         // postfix expression of tokens (filterNames) and operators (as strings)
 156         // if this is empty, uses m_compareType to build default expression queue
 157         std::queue<std::string> m_ruleQueue;
 158
 159         // flag to test if the rule expression queue has been generated
 160         bool m_isRuleQueueGenerated;
 161
 162         // 'default' comparison operator between filters if no rule string given
 163         // if this is changed, m_ruleString is used to build new m_ruleQueue
 164         FilterCompareType::Type m_defaultCompareType;
 165
 166         // client-specified checking type ( provides method: bool check(PropertyFilter, T object) )
 167         FilterChecker m_checker;
 168
 169         // token-parsing constants
 170         static const int NOT_CHAR          = (int)'!';
 171         static const int EQUAL_CHAR        = (int)'=';
 172         static const int GREATER_THAN_CHAR = (int)'>';
 173         static const int LESS_THAN_CHAR    = (int)'<';
 174         static const int WILDCARD_CHAR     = (int)'*';
 175
 176         // filter evaluation constants
 177         const std::string AND_OPERATOR;
 178         const std::string OR_OPERATOR;
 179         const std::string NOT_OPERATOR;
 180 };
 181
 182 // creates a new filter set, returns true if created, false if error or already exists
 183 template<typename FilterChecker>
 184 inline bool FilterEngine<FilterChecker>::addFilter(const std::string& filterName) {
 185     return (m_filters.insert(std::make_pair(filterName, PropertyFilter()))).second;
 186 }
 187
 188 // add a new known property & type to engine
 189 template<typename FilterChecker>
 190 inline bool FilterEngine<FilterChecker>::addProperty(const std::string& propertyName) {
 191     const std::vector<std::string> propertyNames = allPropertyNames();
 192     bool found = std::binary_search( propertyNames.begin(), propertyNames.end(), propertyName );
 193     if ( found ) return false;
 194     m_properties.push_back( Property(propertyName) );
 195     std::sort( m_properties.begin(), m_properties.end() );
 196     return true;
 197 }
 198
 199 // returns list of all properties known by FilterEngine
 200 // ( any that were created using addProperty() )
 201 template<typename FilterChecker>
 202 inline const std::vector<std::string> FilterEngine<FilterChecker>::allPropertyNames(void) {
 203     // set up stringlist
 204     std::vector<std::string> names;
 205     names.reserve(m_properties.size());
 206     // iterate through all properties, appending to stringlist
 207     std::vector<Property>::const_iterator propIter = m_properties.begin();
 208     std::vector<Property>::const_iterator propEnd  = m_properties.end();
 209     for ( ; propIter != propEnd; ++propIter )
 210         names.push_back( (*propIter).Name );
 211     // return stringlist
 212     return names;
 213 }
 214
 215 // builds a default rule string based on m_defaultCompareType
 216 // used if user supplied an explicit rule string
 217 template<typename FilterChecker>
 218 inline void FilterEngine<FilterChecker>::buildDefaultRuleString(void) {
 219
 220     // set up temp string stream
 221     std::stringstream ruleStream("");
 222
 223     // get first filterName
 224     FilterMap::const_iterator mapIter = m_filters.begin();
 225     ruleStream << (*mapIter).first;
 226
 227     // if there are more filters present
 228     // iterate over remaining filters, appending compare operator and filter name
 229     if ( m_filters.size() > 1 ) {
 230         for ( ++mapIter ; mapIter != m_filters.end(); ++mapIter )
 231             ruleStream << ( (m_defaultCompareType == FilterCompareType::AND) ? " & " : " | " )
 232                        << (*mapIter).first;
 233     }
 234
 235     // set m_ruleString from temp stream
 236     m_ruleString = ruleStream.str();
 237 }
 238
 239 // build expression queue based on ruleString
 240 template<typename FilterChecker>
 241 inline void FilterEngine<FilterChecker>::buildRuleQueue(void) {
 242
 243     // skip if no filters present
 244     if ( m_filters.empty() ) return;
 245
 246     // clear out any prior expression queue data
 247     while ( !m_ruleQueue.empty() )
 248         m_ruleQueue.pop();
 249
 250     // create a rule string, if not provided
 251     if ( m_ruleString.empty() )
 252         buildDefaultRuleString();
 253
 254     // initialize RuleParser, run, and retrieve results
 255     RuleParser ruleParser(m_ruleString);
 256     ruleParser.parse();
 257     m_ruleQueue = ruleParser.results();
 258
 259     // set flag if rule queue contains any values
 260     m_isRuleQueueGenerated = (!m_ruleQueue.empty());
 261 }
 262
 263 // returns whether query value passes filter engine rules
 264 template<class FilterChecker> template<typename T>
 265 bool FilterEngine<FilterChecker>::check(const T& query) {
 266
 267     // return result of querying against filter rules
 268     return evaluateFilterRules(query);
 269 }
 270
 271 // returns list of property names that are 'enabled' ( only those touched by setProperty() )
 272 template<typename FilterChecker>
 273 inline const std::vector<std::string> FilterEngine<FilterChecker>::enabledPropertyNames(void) {
 274     // initialize stringlist
 275     std::vector<std::string> names;
 276     names.reserve(m_properties.size());
 277     // iterate over all properties, appending if enabled
 278     std::vector<Property>::const_iterator propIter = m_properties.begin();
 279     std::vector<Property>::const_iterator propEnd  = m_properties.end();
 280     for ( ; propIter != propEnd; ++propIter )
 281         if ( (*propIter).IsEnabled )
 282             names.push_back( (*propIter).Name );
 283     // return stringlist
 284     return names;
 285 }
 286
 287 // evaluates postfix rule queue - with each filter as an operand, AND|OR|NOT as operators
 288 template<class FilterChecker> template<typename T>
 289 bool FilterEngine<FilterChecker>::evaluateFilterRules(const T& query) {
 290
 291     // build ruleQueue if not done before
 292     if ( !m_isRuleQueueGenerated )
 293         buildRuleQueue();
 294
 295     std::stack<bool> resultStack;
 296     FilterMap::const_iterator filterIter;
 297     FilterMap::const_iterator filterEnd  = m_filters.end();
 298     std::queue<std::string> ruleQueueCopy = m_ruleQueue;
 299     while ( !ruleQueueCopy.empty() ) {
 300         const std::string& token = ruleQueueCopy.front();
 301
 302         // token is NOT_OPERATOR
 303         if ( token == FilterEngine<FilterChecker>::NOT_OPERATOR ) {
 304             BAMTOOLS_ASSERT_MESSAGE( !resultStack.empty(), "Empty result stack - cannot apply operator: !" );
 305             resultStack.top() = !resultStack.top();
 306         }
 307
 308         // token is AND_OPERATOR
 309         else if ( token == FilterEngine<FilterChecker>::AND_OPERATOR ) {
 310             BAMTOOLS_ASSERT_MESSAGE( resultStack.size() >= 2 , "Not enough operands - cannot apply operator: &" );
 311             bool topResult = resultStack.top();
 312             resultStack.pop();
 313             resultStack.top() &= topResult;
 314         }
 315
 316         // token is OR_OPERATOR
 317         else if ( token == FilterEngine<FilterChecker>::OR_OPERATOR ) {
 318             BAMTOOLS_ASSERT_MESSAGE( resultStack.size() >= 2 , "Not enough operands - cannot apply operator: |" );
 319             bool topResult = resultStack.top();
 320             resultStack.pop();
 321             resultStack.top() |= topResult;
 322         }
 323
 324         // token is an operand
 325         else {
 326             // look up PropertyFilter that matches this token
 327             filterIter = m_filters.find(token);
 328             BAMTOOLS_ASSERT_MESSAGE( (filterIter != filterEnd), "Filter mentioned in rule, not found in FilterEngine" );
 329             const PropertyFilter& filter = (*filterIter).second;
 330             bool result = m_checker.check(filter, query);
 331             resultStack.push( result );
 332         }
 333
 334         // pop token from ruleQueue
 335         ruleQueueCopy.pop();
 336     }
 337
 338     // return last result
 339     BAMTOOLS_ASSERT_MESSAGE( resultStack.size() == 1, "Result stack should only have one value remaining - cannot return result" );
 340     return resultStack.top();
 341 }
 342
 343 // return list of current filter names
 344 template<typename FilterChecker>
 345 inline const std::vector<std::string> FilterEngine<FilterChecker>::filterNames(void) {
 346     // initialize stringlist
 347     std::vector<std::string> names;
 348     names.reserve(m_filters.size());
 349     // iterate over all filters, appending filter name
 350     FilterMap::const_iterator mapIter = m_filters.begin();
 351     FilterMap::const_iterator mapEnd  = m_filters.end();
 352     for ( ; mapIter != mapEnd; ++mapIter )
 353         names.push_back( (*mapIter).first );
 354     // return stringlist
 355     return names;
 356 }
 357
 358 // parse a filterValue token string that may contain comparison qualifiers (">50", "*SRR", etc.)
 359 template<class FilterChecker> template<typename T>
 360 bool FilterEngine<FilterChecker>::parseToken(const std::string& token, T& value, PropertyFilterValue::ValueCompareType& type) {
 361
 362     // skip if token is empty
 363     if ( token.empty() ) return false;
 364
 365     // will store token after special chars are removed
 366     std::string strippedToken;
 367
 368     // if only single character
 369     if ( token.length() == 1 ) {
 370         strippedToken = token;
 371         type = PropertyFilterValue::EXACT;
 372     }
 373
 374     // more than one character, check for special chars
 375     else {
 376         const int firstChar = (int)token.at(0);
 377         switch ( firstChar ) {
 378
 379             case ( FilterEngine<FilterChecker>::NOT_CHAR ) :
 380                 strippedToken = token.substr(1);
 381                 type = PropertyFilterValue::NOT;
 382                 break;
 383
 384             case ( FilterEngine<FilterChecker>::GREATER_THAN_CHAR ) :
 385
 386                 // check for '>=' case
 387                 if ( token.at(1) == FilterEngine<FilterChecker>::EQUAL_CHAR ) {
 388                     if ( token.length() == 2 ) return false;
 389                     strippedToken = token.substr(2);
 390                     type = PropertyFilterValue::GREATER_THAN_EQUAL;
 391                 }
 392
 393                 // otherwise only '>'
 394                 else {
 395                     strippedToken = token.substr(1);
 396                     type = PropertyFilterValue::GREATER_THAN;
 397                 }
 398
 399                 break;
 400
 401             case ( FilterEngine<FilterChecker>::LESS_THAN_CHAR ) :
 402
 403                 // check for '<=' case
 404                 if ( token.at(1) == FilterEngine<FilterChecker>::EQUAL_CHAR ) {
 405                     if ( token.length() == 2 ) return false;
 406                     strippedToken = token.substr(2);
 407                     type = PropertyFilterValue::LESS_THAN_EQUAL;
 408                 }
 409
 410                 // otherwise only '<'
 411                 else {
 412                     strippedToken = token.substr(1);
 413                     type = PropertyFilterValue::LESS_THAN;
 414                 }
 415
 416                 break;
 417
 418             case ( FilterEngine<FilterChecker>::WILDCARD_CHAR ) :
 419
 420                 // check for *str* case (CONTAINS)
 421                 if ( token.at( token.length() - 1 ) == FilterEngine<FilterChecker>::WILDCARD_CHAR ) {
 422                     if ( token.length() == 2 ) return false;
 423                     strippedToken = token.substr(1, token.length() - 2);
 424                     type = PropertyFilterValue::CONTAINS;
 425                 }
 426
 427                 // otherwise *str case (ENDS_WITH)
 428                 else {
 429                     strippedToken = token.substr(1);
 430                     type = PropertyFilterValue::ENDS_WITH;
 431                 }
 432
 433                 break;
 434
 435             default :
 436                 // check for str* case (STARTS_WITH)
 437                 if ( token.at( token.length() - 1 ) == FilterEngine<FilterChecker>::WILDCARD_CHAR ) {
 438                     if ( token.length() == 2 ) return false;
 439                     strippedToken = token.substr(0, token.length() - 1);
 440                     type = PropertyFilterValue::STARTS_WITH;
 441                 }
 442
 443                 // otherwise EXACT
 444                 else {
 445                     strippedToken = token;
 446                     type = PropertyFilterValue::EXACT;
 447                 }
 448
 449                 break;
 450         }
 451     }
 452
 453     // convert stripped token to value
 454     std::stringstream stream(strippedToken);
 455     if ( strippedToken == "true" || strippedToken == "false" )
 456         stream >> std::boolalpha >> value;
 457     else
 458         stream >> value;
 459
 460     // check for valid CompareType on type T
 461     Variant variantCheck = value;
 462
 463     // if T is not string AND CompareType is for string values, return false
 464     if ( !variantCheck.is_type<std::string>() ) {
 465         if ( type == PropertyFilterValue::CONTAINS ||
 466              type == PropertyFilterValue::ENDS_WITH ||
 467              type == PropertyFilterValue::STARTS_WITH )
 468
 469           return false;
 470     }
 471
 472     // return success
 473     return true;
 474 }
 475
 476 // sets comparison operator between filters if no rule string given
 477 // default is to do an OR on each filter
 478 template<typename FilterChecker>
 479 inline void FilterEngine<FilterChecker>::setDefaultCompareType(const FilterCompareType::Type& type) {
 480     // check for supported compare type
 481     if ( type == FilterCompareType::AND || type == FilterCompareType::OR ) {
 482         // if not the current compare type
 483         if ( m_defaultCompareType != type ) {
 484             m_defaultCompareType = type;
 485             buildRuleQueue();
 486         }
 487     }
 488 }
 489
 490 // sets property filter (value, type) for propertyName, on a particular filter set
 491 // setProperty("filter1", "mapQuality", 50, GREATER_THAN_EQUAL)
 492 template<class FilterChecker> template<typename T>
 493 bool FilterEngine<FilterChecker>::setProperty(const std::string& filterName,
 494                                               const std::string& propertyName,
 495                                               const T& value,
 496                                               const PropertyFilterValue::ValueCompareType& type)
 497 {
 498     // lookup filter by name, return false if not found
 499     FilterMap::iterator filterIter = m_filters.find(filterName);
 500     if ( filterIter == m_filters.end() ) return false;
 501
 502     // lookup property for filter, add new PropertyFilterValue if not found, modify if already exists
 503     PropertyFilter& filter = (*filterIter).second;
 504     PropertyMap::iterator propertyIter = filter.Properties.find(propertyName);
 505
 506     bool success;
 507
 508     // property not found for this filter, create new entry
 509     if ( propertyIter == filter.Properties.end() )
 510         success = (filter.Properties.insert(std::make_pair(propertyName, PropertyFilterValue(value, type)))).second;
 511
 512     // property already exists, modify
 513     else {
 514         PropertyFilterValue& filterValue = (*propertyIter).second;
 515         filterValue.Value = value;
 516         filterValue.Type  = type;
 517         success = true;
 518     }
 519
 520     // if error so far, return false
 521     if ( !success ) return false;
 522
 523     // --------------------------------------------
 524     // otherwise, set Property.IsEnabled to true
 525
 526     // lookup property
 527     std::vector<Property>::iterator knownPropertyIter = std::find( m_properties.begin(), m_properties.end(), propertyName);
 528
 529     // if not found, create a new (enabled) entry (& re-sort list)
 530     if ( knownPropertyIter == m_properties.end() ) {
 531         m_properties.push_back( Property(propertyName, true) );
 532         std::sort( m_properties.begin(), m_properties.end() );
 533     }
 534
 535     // property already known, set as enabled
 536     else (*knownPropertyIter).IsEnabled = true;
 537
 538     // return success
 539     return true;
 540 }
 541
 542 // sets user-specified rule string & signals update of rule-expression queue
 543 template<typename FilterChecker>
 544 inline void FilterEngine<FilterChecker>::setRule(const std::string& ruleString) {
 545     if ( m_ruleString != ruleString) {
 546         m_ruleString = ruleString;
 547         buildRuleQueue();
 548     }
 549 }
 550
 551 } // namespace BamTools
 552
 553 #endif // BAMTOOLS_FILTER_ENGINE_H