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