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: 21 September 2010
   7 // ---------------------------------------------------------------------------
   8 // Provides a generic filter engine based on filter-sets of properties,
   9 // with possible "rules" (compound logical expressions) to create more complex
  10 // queries on a data set.
  11 //
  12 // FilterEngine consists, most importantly, of :
  13 //
  14 //     a list of possible properties (each tagged whether it has been 'enabled' as a filter)
  15 //     a map of filterName => propertySet
  16 //     queue for compound rule expression (i.e. "(filter1 AND filter2) OR !filter3" )
  17 //
  18 // Each propertySet is a list of properties enabled for this particular filter object
  19 //
  20 //     Implemented as a map of propertyNames to propertyFilterValue
  21 //     ( "property1" => pfv1
  22 //       "property2" => pfv2
  23 //       "property4" => pfv4
  24 //       etc. )
  25 //
  26 //     Any properties that are 'possible', via FilterEngine::addProperty(), but not enabled
  27 //     via FilterEngine::setProperty() (in our example, say "property3"), evaluate to true
  28 //     for any query.  Meaning that if a property is not set on this filter, we don't care
  29 //     about it here, so it passes though OK.
  30 //
  31 // A propertyFilterValue contains a value and comparison type
  32 //
  33 //    ( pfv1: Value = 50,    Type = GREATER_THAN_EQUAL
  34 //      pfv2: Value = "foo", Type = STARTS_WITH
  35 //      pfv4: Value = "bar", Type = CONTAINS
  36 //      etc. )
  37 //
  38 //    This allows for more complex queries (than simple isEqual?) against a variety of data types.
  39 //
  40 // ***************************************************************************
  41
  42 #ifndef BAMTOOLS_FILTER_ENGINE_H
  43 #define BAMTOOLS_FILTER_ENGINE_H
  44
  45 #include <algorithm>
  46 #include <iostream>
  47 #include <map>
  48 #include <queue>
  49 #include <sstream>
  50 #include <stack>
  51 #include <sstream>
  52 #include <string>
  53 #include <utility>
  54 #include <vector>
  55 #include "bamtools_filter_properties.h"
  56 #include "bamtools_filter_ruleparser.h"
  57 #include "bamtools_utilities.h"
  58
  59 namespace BamTools {
  60
  61 struct FilterCompareType {
  62     enum Type { AND = 0
  63               , NOT
  64               , OR
  65     };
  66 };
  67
  68 // -----------------------------------------------------------
  69 // FilterEngine
  70
  71 template <typename FilterChecker>
  72 class 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         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
 381                 strippedToken = token.substr(1);
 382                 type = PropertyFilterValue::NOT;
 383
 384                 break;
 385
 386             case ( FilterEngine<FilterChecker>::GREATER_THAN_CHAR ) :
 387
 388                 // check for '>=' case
 389                 if ( token.at(1) == FilterEngine<FilterChecker>::EQUAL_CHAR ) {
 390                     if ( token.length() == 2 ) return false;
 391                     strippedToken = token.substr(2);
 392                     type = PropertyFilterValue::GREATER_THAN_EQUAL;
 393                 }
 394
 395                 // otherwise only '>'
 396                 else {
 397                     strippedToken = token.substr(1);
 398                     type = PropertyFilterValue::GREATER_THAN;
 399                 }
 400
 401                 break;
 402
 403             case ( FilterEngine<FilterChecker>::LESS_THAN_CHAR ) :
 404
 405                 // check for '<=' case
 406                 if ( token.at(1) == FilterEngine<FilterChecker>::EQUAL_CHAR ) {
 407                     if ( token.length() == 2 ) return false;
 408                     strippedToken = token.substr(2);
 409                     type = PropertyFilterValue::LESS_THAN_EQUAL;
 410                 }
 411
 412                 // otherwise only '<'
 413                 else {
 414                     strippedToken = token.substr(1);
 415                     type = PropertyFilterValue::LESS_THAN;
 416                 }
 417
 418                 break;
 419
 420             case ( FilterEngine<FilterChecker>::WILDCARD_CHAR ) :
 421
 422                 // check for *str* case (CONTAINS)
 423                 if ( token.at( token.length() - 1 ) == FilterEngine<FilterChecker>::WILDCARD_CHAR ) {
 424                     if ( token.length() == 2 ) return false;
 425                     strippedToken = token.substr(1, token.length() - 2);
 426                     type = PropertyFilterValue::CONTAINS;
 427                 }
 428
 429                 // otherwise *str case (ENDS_WITH)
 430                 else {
 431                     strippedToken = token.substr(1);
 432                     type = PropertyFilterValue::ENDS_WITH;
 433                 }
 434
 435                 break;
 436
 437             default :
 438
 439                 // check for str* case (STARTS_WITH)
 440                 if ( token.at( token.length() - 1 ) == FilterEngine<FilterChecker>::WILDCARD_CHAR ) {
 441                     if ( token.length() == 2 ) return false;
 442                     strippedToken = token.substr(0, token.length() - 1);
 443                     type = PropertyFilterValue::STARTS_WITH;
 444                 }
 445
 446                 // otherwise EXACT
 447                 else {
 448                     strippedToken = token;
 449                     type = PropertyFilterValue::EXACT;
 450                 }
 451
 452                 break;
 453         }
 454     }
 455
 456     // convert stripped token to value
 457     std::stringstream stream(strippedToken);
 458     if ( strippedToken == "true" || strippedToken == "false" )
 459         stream >> std::boolalpha >> value;
 460     else
 461         stream >> value;
 462
 463     // check for valid CompareType on type T
 464     Variant variantCheck = value;
 465
 466     // if T is not string AND CompareType is for string values, return false
 467     if ( !variantCheck.is_type<std::string>() ) {
 468         if ( type == PropertyFilterValue::CONTAINS ||
 469              type == PropertyFilterValue::ENDS_WITH ||
 470              type == PropertyFilterValue::STARTS_WITH )
 471
 472           return false;
 473     }
 474
 475     // return success
 476     return true;
 477 }
 478
 479 // sets comparison operator between filters if no rule string given
 480 // default is to do an OR on each filter
 481 template<typename FilterChecker>
 482 inline void FilterEngine<FilterChecker>::setDefaultCompareType(const FilterCompareType::Type& type) {
 483     // check for supported compare type
 484     if ( type == FilterCompareType::AND || type == FilterCompareType::OR ) {
 485         // if not the current compare type
 486         if ( m_defaultCompareType != type ) {
 487             m_defaultCompareType = type;
 488             buildRuleQueue();
 489         }
 490     }
 491 }
 492
 493 // sets property filter (value, type) for propertyName, on a particular filter set
 494 // setProperty("filter1", "mapQuality", 50, GREATER_THAN_EQUAL)
 495 template<class FilterChecker> template<typename T>
 496 bool FilterEngine<FilterChecker>::setProperty(const std::string& filterName,
 497                                               const std::string& propertyName,
 498                                               const T& value,
 499                                               const PropertyFilterValue::ValueCompareType& type)
 500 {
 501     // lookup filter by name, return false if not found
 502     FilterMap::iterator filterIter = m_filters.find(filterName);
 503     if ( filterIter == m_filters.end() ) return false;
 504
 505     // lookup property for filter, add new PropertyFilterValue if not found, modify if already exists
 506     PropertyFilter& filter = (*filterIter).second;
 507     PropertyMap::iterator propertyIter = filter.Properties.find(propertyName);
 508
 509     bool success;
 510
 511     // property not found for this filter, create new entry
 512     if ( propertyIter == filter.Properties.end() )
 513         success = (filter.Properties.insert(std::make_pair(propertyName, PropertyFilterValue(value, type)))).second;
 514
 515     // property already exists, modify
 516     else {
 517         PropertyFilterValue& filterValue = (*propertyIter).second;
 518         filterValue.Value = value;
 519         filterValue.Type  = type;
 520         success = true;
 521     }
 522
 523     // if error so far, return false
 524     if ( !success ) return false;
 525
 526     // --------------------------------------------
 527     // otherwise, set Property.IsEnabled to true
 528
 529     // lookup property
 530     std::vector<Property>::iterator knownPropertyIter = std::find( m_properties.begin(), m_properties.end(), propertyName);
 531
 532     // if not found, create a new (enabled) entry (& re-sort list)
 533     if ( knownPropertyIter == m_properties.end() ) {
 534         m_properties.push_back( Property(propertyName, true) );
 535         std::sort( m_properties.begin(), m_properties.end() );
 536     }
 537
 538     // property already known, set as enabled
 539     else (*knownPropertyIter).IsEnabled = true;
 540
 541     // return success
 542     return true;
 543 }
 544
 545 // sets user-specified rule string & signals update of rule-expression queue
 546 template<typename FilterChecker>
 547 inline void FilterEngine<FilterChecker>::setRule(const std::string& ruleString) {
 548     if ( m_ruleString != ruleString) {
 549         m_ruleString = ruleString;
 550         buildRuleQueue();
 551     }
 552 }
 553
 554 } // namespace BamTools
 555
 556 #endif // BAMTOOLS_FILTER_ENGINE_H