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
  27 #include "incbwt/bits/deltavector.h"
  28 // Re-define word size to ulong:
  29 #undef W
  30 #if __WORDSIZE == 64
  31 #   define W 64
  32 #else
  33 #   define W 32
  34 #endif
  35
  36 #include <cassert>
  37 #include <stdexcept>
  38
  39
  40 namespace SXSI
  41 {
  42
  43 class TextStorageBuilder;
  44 class TextStoragePlainText;
  45 class TextStorageLzIndex;
  46
  47 /**
  48  * Text collection that supports fast extraction.
  49  * Defines an abstact interface class.
  50  * See subclasses TextStorageLzIndex and TextStoragePlainText
  51  * below.
  52  */
  53 class TextStorage
  54 {
  55 public:
  56     // Storage type
  57     const static char TYPE_PLAIN_TEXT = 0;
  58     const static char TYPE_LZ_INDEX = 1;
  59
  60     // Call DeleteText() for each pointer returned by GetText()
  61     // to avoid possible memory leaks.
  62     virtual uchar * GetText(TextCollection::DocId docId) const = 0;
  63     virtual uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const = 0;
  64     virtual void DeleteText(uchar *) const = 0;
  65
  66     static TextStorage * Load(FILE *file);
  67     virtual void Save(FILE *file) const = 0;
  68
  69     virtual ~TextStorage()
  70     {
  71         delete offsets_;
  72         offsets_ = 0;
  73     }
  74
  75     TextCollection::DocId DocIdAtTextPos(TextCollection::TextPosition i) const
  76     {
  77         assert(i < n_);
  78         return offsets_->rank(i)-1;
  79     }
  80
  81     TextCollection::TextPosition TextStartPos(TextCollection::DocId i) const
  82     {
  83         assert(i < (TextCollection::DocId)numberOfTexts_);
  84         return offsets_->select(i);
  85     }
  86
  87     bool IsEndmarker(TextCollection::TextPosition i) const
  88     {
  89         assert(i < n_);
  90         if (i >= n_ - 1)
  91             return true;
  92         return offsets_->isSet(i+1);
  93     }
  94
  95
  96 protected:
  97     // Define a shortcut
  98     typedef TextCollection::TextPosition TextPosition;
  99     // Block size in DeltaVector
 100     const static CSA::usint DV_BLOCK_SIZE = 32;
 101
 102     TextStorage(uchar const * text, TextPosition n)
 103         : n_(n), offsets_(0), numberOfTexts_(0)
 104     {
 105         // Delta encoded bitvector of text offsets.
 106         CSA::DeltaEncoder encoder(DV_BLOCK_SIZE);
 107         encoder.setBit(0); // Start of the first text.
 108
 109         // Read offsets by finding text end positions:
 110         for (TextPosition i = 0; i < n_ - 1; ++i)
 111             if (text[i] == '\0')
 112                 encoder.setBit(i+1);
 113
 114
 115         offsets_ = new CSA::DeltaVector(encoder, n_);
 116         numberOfTexts_ = offsets_->rank(n_ - 1);
 117     }
 118
 119     TextStorage(std::FILE *);
 120     void Save(FILE *file, char type) const;
 121
 122     TextPosition n_;
 123     CSA::DeltaVector *offsets_;
 124     TextPosition numberOfTexts_;
 125 };
 126
 127 /******************************************************************
 128  * Plain text collection.
 129  */
 130 class TextStoragePlainText : public TextStorage
 131 {
 132 public:
 133     TextStoragePlainText(uchar *text, TextPosition n)
 134         : TextStorage(text, n), text_(text)
 135     { }
 136
 137     TextStoragePlainText(FILE *file)
 138         : TextStorage(file), text_(0)
 139     {
 140         text_ = new uchar[n_];
 141         if (std::fread(this->text_, sizeof(uchar), n_, file) != n_)
 142             throw std::runtime_error("TextStorage::Load(): file read error (text_).");
 143     }
 144
 145     void Save(FILE *file) const
 146     {
 147         TextStorage::Save(file, TYPE_PLAIN_TEXT);
 148
 149         if (std::fwrite(this->text_, sizeof(uchar), n_, file) != n_)
 150             throw std::runtime_error("TextStorage::Save(): file write error (text_).");
 151     }
 152
 153     ~TextStoragePlainText()
 154     {
 155         delete [] text_;
 156         text_ = 0;
 157         n_ = 0;
 158     }
 159
 160     uchar * GetText(TextCollection::DocId docId) const
 161     {
 162         assert(docId < (TextCollection::DocId)numberOfTexts_);
 163
 164         TextPosition offset = offsets_->select(docId);
 165         return &text_[offset];
 166     }
 167
 168     uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const
 169     {
 170         assert(i < (TextCollection::DocId)numberOfTexts_);
 171         assert(j < (TextCollection::DocId)numberOfTexts_);
 172
 173         TextPosition offset = offsets_->select(i);
 174         return &text_[offset];
 175     }
 176
 177     // No operation, since text is a pointer to this->text_
 178     void DeleteText(uchar *text) const
 179     { }
 180
 181 private:
 182     uchar *text_;
 183 }; // class TextStorage
 184
 185
 186 /******************************************************************
 187  * LZ-index text collection.
 188  */
 189 struct LzTriePimpl; // Using Pimpl idiom to hide LzTrie implementation.
 190
 191 class TextStorageLzIndex : public TextStorage
 192 {
 193 public:
 194     TextStorageLzIndex(uchar *text, TextPosition n);
 195     TextStorageLzIndex(FILE *file);
 196     void Save(FILE *file) const;
 197     ~TextStorageLzIndex();
 198     uchar * GetText(TextCollection::DocId docId) const;
 199     uchar * GetText(TextCollection::DocId i, TextCollection::DocId j) const;
 200
 201     // Free the space malloc'ed in lztrie::extract()
 202     void DeleteText(uchar *text) const
 203     {
 204         free(text);
 205     }
 206
 207 private:
 208     struct LzTriePimpl * p_;
 209 }; // class TextStorageLzIndex
 210
 211
 212 /**
 213  * Builder for TextStorage class
 214  */
 215 class TextStorageBuilder
 216 {
 217 public:
 218     // Define a shortcut
 219     typedef TextCollection::TextPosition TextPosition;
 220
 221     // Build up simple uchar array
 222     explicit TextStorageBuilder(TextPosition n)
 223         : n_(n), text_(new uchar [n]), freeText(true)
 224     { }
 225
 226     ~TextStorageBuilder()
 227     {
 228         if (freeText)
 229             delete [] text_;
 230         text_ = 0;
 231         n_ = 0;
 232     }
 233
 234     // Write access to text[]
 235     uchar& operator[] (TextPosition i)
 236     {
 237         return text_[i];
 238     }
 239
 240     // Init TextStorage
 241     // Type defaults to plain text.
 242     TextStorage * InitTextStorage(char type = TextStorage::TYPE_PLAIN_TEXT)
 243     {
 244         freeText = false; // Passing text to TextStorage.
 245         switch(type)
 246         {
 247         case (TextStorage::TYPE_PLAIN_TEXT):
 248             return new TextStoragePlainText(text_, n_);
 249         case (TextStorage::TYPE_LZ_INDEX):
 250             return new TextStorageLzIndex(text_, n_);
 251         default:
 252             std::cerr << "TextStorageBuilder: Unknown type given!" << std::endl;
 253             exit(1);
 254         }
 255     }
 256
 257 private:
 258     TextPosition n_;
 259     uchar *text_;
 260     bool freeText;
 261 }; // class TextStorageBuilder
 262
 263 } // namespace SXSI
 264
 265 #endif // #ifndef _TextStorage_H_