RLCSAWrapper.h

   1 /******************************************************************************
   2  *   Copyright (C) 2010 by Niko Välimäki                                      *
   3  *                                                                            *
   4  *   RLCSA implementation for the TextCollection interface                  *
   5  *                                                                            *
   6  *   This program is free software; you can redistribute it and/or modify     *
   7  *   it under the terms of the GNU Lesser General Public License as published *
   8  *   by the Free Software Foundation; either version 2 of the License, or     *
   9  *   (at your option) any later version.                                      *
  10  *                                                                            *
  11  *   This program is distributed in the hope that it will be useful,          *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  14  *   GNU Lesser General Public License for more details.                      *
  15  *                                                                            *
  16  *   You should have received a copy of the GNU Lesser General Public License *
  17  *   along with this program; if not, write to the                            *
  18  *   Free Software Foundation, Inc.,                                          *
  19  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  20  *****************************************************************************/
  21
  22 #ifndef _RLCSAWrapper_H_
  23 #define _RLCSAWrapper_H_
  24
  25 #include "TextCollection.h"
  26
  27 #include "incbwt/rlcsa.h"
  28
  29 // Re-define word size to ulong:
  30 #undef W
  31 #if __WORDSIZE == 64
  32 #   define W 64
  33 #else
  34 #   define W 32
  35 #endif
  36
  37 #include <set>
  38 #include <string>
  39
  40 namespace SXSI
  41 {
  42
  43 /**
  44  * Partial implementation of the TextCollection interface
  45  *
  46  * Supports index construction, save, load and simple search.
  47  * Use FMIndex implementation for full support.
  48  */
  49 class RLCSAWrapper : public SXSI::TextCollection
  50 {
  51 public:
  52     RLCSAWrapper(const CSA::RLCSA* index)
  53         : rlcsa(index)
  54     { /* NOP */ }
  55
  56     ~RLCSAWrapper()
  57     {
  58         delete rlcsa; rlcsa = 0;
  59     }
  60
  61     bool EmptyText(DocId k) const
  62     {
  63         return false; // Empty texts are not indexed
  64     }
  65
  66     /**
  67      * Extracting one text.
  68      *
  69      * Call DeleteText() for each pointer returned by GetText()
  70      * to avoid possible memory leaks.
  71      */
  72     uchar * GetText(DocId i) const
  73     {
  74         return rlcsa->display(i);
  75     }
  76     void DeleteText(uchar *text) const
  77     {
  78         delete [] text;
  79     }
  80
  81     /**
  82      * Returns a pointer to the beginning of texts i, i+1, ..., j.
  83      * Texts are separated by a '\0' byte.
  84      *
  85      * Call DeleteText() for each pointer returned by GetText()
  86      * to avoid possible memory leaks.
  87      */
  88     uchar * GetText(DocId i, DocId j) const
  89     {
  90         std::cerr << "RLCSAWrapper::GetText(i,j): unsupported method!" << std::endl
  91                   << "Use the default (FMIndex) text collection instead!" << std::endl;
  92         std::exit(1);
  93     }
  94
  95     bool IsPrefix(uchar const *) const { unsupported(); return false; };
  96     bool IsSuffix(uchar const *) const { unsupported(); return false; };
  97     bool IsEqual(uchar const *) const { unsupported(); return false; };
  98     bool IsContains(uchar const *) const { unsupported(); return false; };
  99     bool IsLessThan(uchar const *) const { unsupported(); return false; };
 100
 101     bool IsPrefix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 102     bool IsSuffix(uchar const *, DocId, DocId) const { unsupported(); return false; };
 103     bool IsEqual(uchar const *, DocId, DocId) const { unsupported(); return false; };
 104     bool IsContains(uchar const *, DocId, DocId) const { unsupported(); return false; };
 105     bool IsLessThan(uchar const *, DocId, DocId) const { unsupported(); return false; };
 106
 107     ulong Count(uchar const *pattern) const
 108     {
 109 //        std::pair<TextPosition, TextPosition> p = backwards(pattern);
 110         CSA::pair_type p = rlcsa->count(std::string((char const *)pattern));
 111
 112         if (p.first <= p.second)
 113             return p.second - p.first + 1;
 114         else
 115             return 0;
 116     }
 117
 118     unsigned CountPrefix(uchar const *) const { unsupported(); return 0; };
 119     unsigned CountSuffix(uchar const *) const { unsupported(); return 0; };
 120     unsigned CountEqual(uchar const *) const { unsupported(); return 0; };
 121     unsigned CountContains(uchar const *) const { unsupported(); return 0; };
 122     unsigned CountLessThan(const unsigned char*) const { unsupported(); return 0; };
 123
 124     unsigned CountPrefix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 125     unsigned CountSuffix(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 126     unsigned CountEqual(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 127     unsigned CountContains(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 128     unsigned CountLessThan(uchar const *, DocId, DocId) const { unsupported(); return 0; };
 129
 130     // Definition of document_result is inherited from SXSI::TextCollection.
 131     document_result Prefix(uchar const *) const { unsupported(); return document_result(); };
 132     document_result Suffix(uchar const *) const { unsupported(); return document_result(); };
 133     document_result Equal(uchar const *) const { unsupported(); return document_result(); };
 134     document_result Contains(uchar const *pattern) const
 135     {
 136         //std::pair<TextPosition,TextPosition> p = backwards(pattern);
 137         CSA::pair_type p = rlcsa->count(std::string((char const *)pattern));
 138         if (p.first > p.second)
 139             return document_result();
 140
 141         document_result dr;
 142         dr.reserve(p.second - p.first + 2);
 143         for (ulong i = p.first; i <= p.second; ++i)
 144             dr.push_back(rlcsa->getSequenceForPosition(rlcsa->locate(i)));
 145         return dr;
 146     }
 147     document_result LessThan(uchar const *) const { unsupported(); return document_result(); };
 148     document_result KMismaches(uchar const *, unsigned) const { unsupported(); return document_result(); };
 149     document_result KErrors(uchar const *, unsigned) const { unsupported(); return document_result(); };
 150
 151     document_result Prefix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 152     document_result Suffix(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 153     document_result Equal(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 154     document_result Contains(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 155     document_result LessThan(uchar const *, DocId, DocId) const { unsupported(); return document_result(); };
 156
 157     // Definition of full_result is inherited from SXSI::TextCollection.
 158     full_result FullContains(uchar const *) const { unsupported(); return full_result(); };
 159     full_result FullContains(uchar const *, DocId, DocId) const { unsupported(); return full_result(); };
 160     full_result FullKMismatches(uchar const *, unsigned) const { unsupported(); return full_result(); };
 161     full_result FullKErrors(uchar const *, unsigned) const { unsupported(); return full_result(); };
 162
 163     // Index from/to disk
 164     RLCSAWrapper(FILE *file, char const *filename)
 165         : rlcsa(new CSA::RLCSA(std::string(filename)))
 166     { /* NOP */ }
 167
 168     void Save(FILE *file, char const *filename) const
 169     {
 170         const char type = 'R';
 171         // Saving type info:
 172         if (std::fwrite(&type, 1, 1, file) != 1)
 173             throw std::runtime_error("RLCSAWrapper::Save(): file write error (type flag).");
 174
 175         this->rlcsa->writeTo(std::string(filename));
 176     }
 177
 178 private:
 179     const CSA::RLCSA* rlcsa;
 180
 181 /*    std::pair<TextPosition, TextPosition> backwards(uchar const *pattern) const
 182     {
 183         TextPosition i = std::strlen((char const *)pattern) - 1;
 184         int c = (int)pattern[i];
 185
 186         std::cerr << "\nFirst symb = " << (char)c << std::endl;
 187
 188         TextPosition sp = rlcsa->C(c);
 189         TextPosition ep = rlcsa->C(c+1)-1;
 190         printf("i = %lu, c = %c, sp = %lu, ep = %lu\n", i, pattern[i], sp, ep);
 191         while (sp<=ep && i>=1)
 192         {
 193             c = (int)pattern[--i];
 194             sp = LF(c, sp);
 195             ep = LF(c, ep+1)-1;
 196             printf("new: c = %c, sp = %lu, ep = %lu\n", pattern[i], sp, ep);
 197         }
 198
 199         uchar* found = rlcsa->display(sp, std::strlen((char const *)pattern), 5, i);
 200         std::cerr << "found: " << found << " (" << i << std::endl;
 201
 202         return std::make_pair(sp, ep);
 203         }*/
 204
 205     inline TextCollection::TextPosition
 206         LF(uchar c, TextPosition i) const
 207     {
 208         if(i == (TextPosition)-1 || i < this->rlcsa->getNumberOfSequences())
 209         { return this->rlcsa->C(c); }
 210         return this->rlcsa->LF(i - this->rlcsa->getNumberOfSequences(), c);
 211     }
 212
 213
 214     void unsupported() const
 215     {
 216         std::cerr << std::endl << "-------------------------------------------------------------\n"
 217             << "RLCSAWrapper: unsupported method!\nSee RLCSAWrapper.h for more details.\n"
 218             << "The default index (FMIndex) implements this method!" << std::endl;
 219         std::exit(5);
 220     }
 221 }; // class RLCSAWrapper
 222
 223 } // namespace SXSI
 224
 225 #endif