tools/bwt/dcs-bwt/src/bw_transform.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 Burrows-Wheeler transform.
  18 // Algorithms the Burrows-Wheeler transform should
  19 // have an interface derived from the class BWTransformer.
  20 //
  21 // New algorithms can be added by modifying the function
  22 // BWTransformer::Options::Set in the file bw_transform.cc
  23
  24 #ifndef DCSBWT_BW_TRANSFORM_H__
  25 #define DCSBWT_BW_TRANSFORM_H__
  26
  27 #include "stream.h"
  28 #include "inttypes.h"
  29
  30 #include <string>
  31 #include <cstddef>  // for size_t
  32
  33 namespace dcsbwt {
  34
  35 class BWTransformer {
  36  protected:
  37   class AlgorithmSpecificOptions;
  38
  39  public:
  40   // A class representing options affecting the BW transform
  41   class Options {
  42    public:
  43     Options() : algorithm_specific_options_(NULL) { Set("p"); }
  44
  45     // Set/Get serialization mechanism is the simplest way
  46     // to implement copying.
  47     Options(const Options& other) : algorithm_specific_options_(NULL)
  48     { Set(other.Get()); }
  49     const Options& operator=(const Options& other) {
  50       Set(other.Get());
  51       return *this;
  52     }
  53     ~Options() {
  54       if (algorithm_specific_options_)
  55         delete algorithm_specific_options_;
  56     }
  57
  58     // Initialize options from a string.
  59     // Returns false in case of an invalid options_string
  60     bool Set(const std::string& options_string);
  61
  62     // Get() returns a string that as an argument to Set() sets
  63     // any options object to this object's current state.
  64     std::string Get() const {
  65       if (algorithm_specific_options_) {
  66         return algorithm_id_ + algorithm_specific_options_->Get();
  67       } else {
  68         return std::string();
  69       }
  70     }
  71
  72     // MaxSizeInBytes() returns the peak memory consumption
  73     // during the BW transform of a block of size block_size
  74     // under the current options when the memory budget is
  75     // unlimited or large enough.
  76     // The size includes the input block but not the output.
  77     int64 MaxSizeInBytes(int64 block_size) const {
  78       return algorithm_specific_options_->MaxSizeInBytes(block_size);
  79     }
  80
  81     // MaxBlockSize() returns the largest block size that the algorithm
  82     // specified by current options can handle within memory_budget.
  83     int64 MaxBlockSize(int64 memory_budget) const {
  84       return algorithm_specific_options_->MaxBlockSize(memory_budget);
  85     }
  86
  87     // SuggestedBlockSize() returns the "optimal" block size
  88     // for the given memory_budget under the current options.
  89     // It may be possible to use a larger block size but at
  90     // a (significantly) reduced speed, and the algorithm might
  91     // run (slightly) faster using a smaller block size.
  92     int64 SuggestedBlockSize(int64 memory_budget) const {
  93       return algorithm_specific_options_->SuggestedBlockSize(memory_budget);
  94     }
  95
  96    private:
  97     friend class BWTransformer;
  98     BWTransformer* GetAlgorithm(int64 memory_budget) {
  99       return algorithm_specific_options_->GetTransformer(memory_budget);
 100     }
 101
 102     char algorithm_id_;
 103     AlgorithmSpecificOptions* algorithm_specific_options_;
 104   };
 105
 106   static int64 Transform(char* block, size_t block_size,
 107                          OutStream* output,
 108                          Options options,
 109                          int64 memory_budget);
 110
 111   BWTransformer() {}
 112   virtual ~BWTransformer() {}
 113
 114  protected:
 115   // A class derived from BWTransform should
 116   // have a nested class derived from AlgorithmSpecificOptions.
 117   class AlgorithmSpecificOptions {
 118    public:
 119     AlgorithmSpecificOptions() {}
 120     virtual ~AlgorithmSpecificOptions() {}
 121
 122     // Set/Get should behave as BWTransform::Options::Set/Get
 123     // The algorithm identifying initial character is omitted from
 124     // the input to Set and should be omitted from the output of Get.
 125     virtual bool Set(const std::string& options_string) =0;
 126     virtual std::string Get() const =0;
 127     virtual int64 MaxSizeInBytes(int64 block_size) const =0;
 128     virtual int64 MaxBlockSize(int64 memory_budget) const =0;
 129     virtual int64 SuggestedBlockSize(int64 memory_budget) const =0;
 130
 131     // Returns a transformer object corresponding to the current options.
 132     virtual BWTransformer* GetTransformer(int64 memory_budget) =0;
 133   };
 134
 135  private:
 136   virtual int64 DoTransform(char* block, size_t block_size,
 137                             OutStream* output) =0;
 138
 139   BWTransformer(const BWTransformer&);
 140   BWTransformer& operator=(const BWTransformer&);
 141 };
 142
 143 }  // namespace dcsbwt
 144
 145 #endif  // DCSBWT_BW_TRANSFORM_H__