TextStorage.h

   1 /******************************************************************************
   2  *   Copyright (C) 2009 Niko Välimäki                                         *
   3  *                                                                            *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            *
  19  *****************************************************************************/
  20
  21 #ifndef _TextStorage_H_
  22 #define _TextStorage_H_
  23
  24 #include "TextCollection.h"
  25 #include "Tools.h"
  26 #include "incbwt/bits/deltavector.h"
  27 #include <cassert>
  28 #include <stdexcept>
  29
  30
  31 namespace SXSI
  32 {
  33
  34 class TextStorageBuilder;
  35 class TextStoragePlainText;
  36 class TextStorageLzIndex;
  37
  38 /**
  39  * Text collection that supports fast extraction.
  40  * Defines an abstact interface class.
  41  * See subclasses TextStorageLzIndex and TextStoragePlainText
  42  * below.
  43  */
  44 class TextStorage
  45 {
  46 public:
  47     // Storage type
  48     const static char TYPE_PLAIN_TEXT = 0;
  49     const static char TYPE_LZ_INDEX = 1;
  50
  51     // Call DeleteText() for each pointer returned by GetText()
  52     // to avoid possible memory leaks.
  53     virtual uchar * GetText(TextCollection::DocId docId) const = 0;
  54     virtual uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const = 0;
  55     virtual void DeleteText(uchar *) const = 0;
  56
  57     static TextStorage * Load(FILE *file);
  58     virtual void Save(FILE *file) const = 0;
  59
  60     virtual ~TextStorage()
  61     {
  62         delete offsets_;
  63         offsets_ = 0;
  64     }
  65
  66     TextCollection::DocId DocIdAtTextPos(TextCollection::TextPosition i) const
  67     {
  68         assert(i < n_);
  69         return offsets_->rank(i)-1;
  70     }
  71
  72     TextCollection::TextPosition TextStartPos(TextCollection::DocId i) const
  73     {
  74         assert(i < (TextCollection::DocId)numberOfTexts_);
  75         return offsets_->select(i);
  76     }
  77
  78     bool IsEndmarker(TextCollection::TextPosition i) const
  79     {
  80         assert(i < n_);
  81         if (i >= n_ - 1)
  82             return true;
  83         return offsets_->isSet(i+1);
  84     }
  85
  86
  87 protected:
  88     // Define a shortcut
  89     typedef TextCollection::TextPosition TextPosition;
  90     // Block size in DeltaVector
  91     const static CSA::usint DV_BLOCK_SIZE = 32;
  92
  93     TextStorage(uchar const * text, TextPosition n)
  94         : n_(n), offsets_(0), numberOfTexts_(0)
  95     {
  96         // Delta encoded bitvector of text offsets.
  97         CSA::DeltaEncoder encoder(DV_BLOCK_SIZE);
  98         encoder.setBit(0); // Start of the first text.
  99
 100         // Read offsets by finding text end positions:
 101         for (TextPosition i = 0; i < n_ - 1; ++i)
 102             if (text[i] == '\0')
 103                 encoder.setBit(i+1);
 104
 105
 106         offsets_ = new CSA::DeltaVector(encoder, n_);
 107
 108 /*        for (ulong i = 0; i < n_-1; ++i)
 109             if ((text[i] == '\0') != IsEndmarker(i))
 110                 std::cout << "misplaced endmarker at i = " << i << std::endl;
 111 */
 112         numberOfTexts_ = offsets_->rank(n_ - 1);
 113     }
 114
 115     TextStorage(std::FILE *);
 116     void Save(FILE *file, char type) const;
 117
 118     TextPosition n_;
 119     CSA::DeltaVector *offsets_;
 120     TextPosition numberOfTexts_;
 121 };
 122
 123 /******************************************************************
 124  * Plain text collection.
 125  */
 126 class TextStoragePlainText : public TextStorage
 127 {
 128 public:
 129     TextStoragePlainText(uchar *text, TextPosition n)
 130         : TextStorage(text, n), text_(text)
 131     { }
 132
 133     TextStoragePlainText(FILE *file)
 134         : TextStorage(file), text_(0)
 135     {
 136         text_ = new uchar[n_];
 137         if (std::fread(this->text_, sizeof(uchar), n_, file) != n_)
 138             throw std::runtime_error("TextStorage::Load(): file read error (text_).");
 139     }
 140
 141     void Save(FILE *file) const
 142     {
 143         TextStorage::Save(file, TYPE_PLAIN_TEXT);
 144
 145         if (std::fwrite(this->text_, sizeof(uchar), n_, file) != n_)
 146             throw std::runtime_error("TextStorage::Save(): file write error (text_).");
 147     }
 148
 149     ~TextStoragePlainText()
 150     {
 151         delete [] text_;
 152         text_ = 0;
 153         n_ = 0;
 154     }
 155
 156     uchar * GetText(TextCollection::DocId docId) const
 157     {
 158         assert(docId < (TextCollection::DocId)numberOfTexts_);
 159
 160         TextPosition offset = offsets_->select(docId);
 161         return &text_[offset];
 162     }
 163
 164     uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const
 165     {
 166         assert(i < (TextCollection::DocId)numberOfTexts_);
 167         assert(j < (TextCollection::DocId)numberOfTexts_);
 168
 169         TextPosition offset = offsets_->select(i);
 170         return &text_[offset];
 171     }
 172
 173     // No operation, since text is a pointer to this->text_
 174     void DeleteText(uchar *text) const
 175     { }
 176
 177 private:
 178     uchar *text_;
 179 }; // class TextStorage
 180
 181
 182 /******************************************************************
 183  * LZ-index text collection.
 184  */
 185 struct LzTriePimpl; // Pimpl, declared in .cpp
 186
 187 class TextStorageLzIndex : public TextStorage
 188 {
 189 public:
 190     TextStorageLzIndex(uchar *text, TextPosition n);
 191     TextStorageLzIndex(FILE *file);
 192     void Save(FILE *file) const;
 193     ~TextStorageLzIndex();
 194     uchar * GetText(TextCollection::DocId docId) const;
 195     uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const;
 196
 197     // Free the space malloc'ed in lztrie::extract()
 198     void DeleteText(uchar *text) const
 199     {
 200         free(text);
 201     }
 202
 203 private:
 204     struct LzTriePimpl * p_;
 205 }; // class TextStorageLzIndex
 206
 207
 208 /**
 209  * Builder for TextStorage class
 210  */
 211 class TextStorageBuilder
 212 {
 213 public:
 214     // Define a shortcut
 215     typedef TextCollection::TextPosition TextPosition;
 216
 217     // Build up simple uchar array
 218     explicit TextStorageBuilder(TextPosition n)
 219         : n_(n), text_(new uchar [n]), freeText(true)
 220     { }
 221
 222     ~TextStorageBuilder()
 223     {
 224         if (freeText)
 225             delete [] text_;
 226         text_ = 0;
 227         n_ = 0;
 228     }
 229
 230     // Write access to text[]
 231     uchar& operator[] (TextPosition i)
 232     {
 233         return text_[i];
 234     }
 235
 236     // Init TextStorage
 237     // Type defaults to plain text.
 238     TextStorage * InitTextStorage(char type = TextStorage::TYPE_PLAIN_TEXT)
 239     {
 240         freeText = false; // Passing text to TextStorage.
 241         switch(type)
 242         {
 243         case (TextStorage::TYPE_PLAIN_TEXT):
 244             return new TextStoragePlainText(text_, n_);
 245         case (TextStorage::TYPE_LZ_INDEX):
 246             return new TextStorageLzIndex(text_, n_);
 247         default:
 248             std::cerr << "TextStorageBuilder: Unknown type given!" << std::endl;
 249             exit(1);
 250         }
 251     }
 252
 253 private:
 254     TextPosition n_;
 255     uchar *text_; // FIXME Replace with a succinct representation.
 256     bool freeText;
 257 }; // class TextStorageBuilder
 258
 259 } // namespace SXSI
 260
 261 #endif // #ifndef _TextStorage_H_