Added approximate pattern matching with Suffix Filters

[SXSI/TextCollection.git] / Query.h

diff --git a/Query.h b/Query.h
new file mode 100644 (file)
index 0000000..bf77802
--- /dev/null
+++ b/Query.h
@@ -0,0 +1,86 @@
+/**
+ * Interface for alignment queries
+ */
+
+#ifndef _Query_H_
+#define _Query_H_
+
+#include "TextCollection.h"
+
+#include <stack>
+#include <vector>
+#include <set>
+
+namespace SXSI
+{
+
+/**
+ * Base class for queries
+ */
+class Query
+{
+public:
+    TextCollection::document_result align(uchar const *p, unsigned k);
+
+    void setDebug(bool b)
+    { this->debug = b; }
+
+    virtual ~Query() 
+    {  }
+
+protected:
+    virtual void firstStep() = 0;
+
+    inline bool pushChar(char c) {
+        ulong nmin = tc->LF(c, smin.top()-1);
+        ulong nmax = tc->LF(c, smax.top())-1;
+        if (nmin > nmax) return false;
+        smin.push(nmin);
+        smax.push(nmax);
+        match.push_back(c);
+        return true;
+    }
+
+    inline void popChar() {
+        smin.pop();
+        smax.pop();
+        match.pop_back();
+    }
+
+    inline int min(int a, int b) {
+        if (a < b) return a; else return b;
+    }
+
+    inline int min(int a, int b, int c) {
+        if (a < b) if (a < c) return a; else return c;
+        else if (b < c) return b; else return c;
+    }
+
+    Query(TextCollection const *tc_);
+
+    uchar const *pat;
+    unsigned patlen;
+    TextCollection const *tc;
+    bool debug;
+    unsigned klimit;
+    ulong textlen;
+    
+    const char *ALPHABET;
+    static const unsigned ALPHABET_SIZE = 5;
+    static const char ALPHABET_DNA[];
+
+    std::stack<ulong> smin;
+    std::stack<ulong> smax;
+    std::vector<uchar> match;
+    std::set<TextCollection::DocId> result;
+ 
+private:
+    Query();
+    // No copy constructor or assignment
+    Query(Query const&);
+    Query& operator = (Query const&);
+};
+
+} // Namespace
+
+#endif // _Query_H_