tools/bwt/dcs-bwt/src/inverse_bwt.h

   1 // Copyright 2007 Google Inc.
   2 //
   3 // This program is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU General Public License
   5 // as published by the Free Software Foundation; either version 2
   6 // of the License, or (at your option) any later version.
   7 //
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program; if not, write to the Free Software
  15 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16
  17 // Base class for doing the inverse Burrows-Wheeler transform.
  18 // Algorithms the inverse Burrows-Wheeler transform should
  19 // have an interface derived from the class InverseBWTransformer.
  20 //
  21 // New algorithms can be added by modifying the function
  22 // InverseBWTransformer::Options::Set in the file inverse_bwt.cc
  23
  24
  25 #ifndef DCSBWT_INVERSE_BWT_H__
  26 #define DCSBWT_INVERSE_BWT_H__
  27
  28 #include "stream.h"
  29 #include "inttypes.h"
  30
  31 #include <string>
  32
  33 namespace dcsbwt {
  34
  35 /////////////////////////////////////////////////////////////////
  36 // InverseBWTransformer
  37 /////////////////////////////////////////////////////////////////
  38 class InverseBWTransformer {
  39  protected:
  40   class AlgorithmSpecificOptions;
  41
  42  public:
  43   class Options {
  44    public:
  45     Options() : algorithm_specific_options_(NULL) { Set("f"); }
  46
  47     // Set/Get serialization mechanism is the simplest way
  48     // to implement copying.
  49     Options(const Options& other) : algorithm_specific_options_(NULL)
  50     { Set(other.Get()); }
  51     const Options& operator=(const Options& other) {
  52       Set(other.Get());
  53       return *this;
  54     }
  55     ~Options() {
  56       if (algorithm_specific_options_)
  57         delete algorithm_specific_options_;
  58     }
  59
  60     // Initialize options from a string.
  61     // Returns false in case of an invalid options_string
  62     bool Set(const std::string& options_string);
  63
  64     // Get() returns a string that as an argument to Set() sets
  65     // any options object to this object's current state.
  66     std::string Get() const {
  67       if (algorithm_specific_options_) {
  68         return algorithm_id_ + algorithm_specific_options_->Get();
  69       } else {
  70         return std::string();
  71       }
  72     }
  73
  74     // MaxBlockSize() returns the largest block size that the algorithm
  75     // specified by current options can handle within memory_budget.
  76     int64 MaxBlockSize(int64 memory_budget) const {
  77       return algorithm_specific_options_->MaxBlockSize(memory_budget);
  78     }
  79
  80    private:
  81     friend class InverseBWTransformer;
  82     InverseBWTransformer* GetAlgorithm(int64 memory_budget) {
  83       return algorithm_specific_options_->GetTransformer(memory_budget);
  84     }
  85
  86     char algorithm_id_;
  87     AlgorithmSpecificOptions* algorithm_specific_options_;
  88   };
  89
  90   InverseBWTransformer() {}
  91   virtual ~InverseBWTransformer() {}
  92
  93   static bool Transform(const char* bwt_block, size_t bwt_block_size,
  94                         size_t eob_position, OutStream* output,
  95                         Options options,
  96                         int64 memory_budget);
  97
  98  protected:
  99   // A class derived from BWTransform should
 100   // have a nested class derived from AlgorithmSpecificOptions.
 101   class AlgorithmSpecificOptions {
 102    public:
 103     AlgorithmSpecificOptions() {}
 104     virtual ~AlgorithmSpecificOptions() {}
 105
 106     // Set/Get should behave as BWTransform::Options::Set/Get
 107     // The algorithm identifying initial character is omitted from
 108     // the input to Set and should be omitted from the output of Get.
 109     virtual bool Set(const std::string& options_string) =0;
 110     virtual std::string Get() const =0;
 111     virtual int64 MaxBlockSize(int64 memory_budget) const =0;
 112
 113     // Returns a transformer object corresponding to the current options.
 114     virtual InverseBWTransformer* GetTransformer(int64 memory_budget) =0;
 115   };
 116
 117  private:
 118   virtual bool DoTransform(const char* bwt, size_t bwt_size,
 119                             size_t eob_position, OutStream* output) =0;
 120
 121   InverseBWTransformer(const InverseBWTransformer&);
 122   InverseBWTransformer& operator=(const InverseBWTransformer&);
 123 };
 124
 125 }  // namespace dcsbwt
 126
 127 #endif  // DCSBWT_INVERSE_BWT_H__