src/third_party/re2/re2/testing/string_generator.cc

   1 // Copyright 2008 The RE2 Authors.  All Rights Reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // String generator: generates all possible strings of up to
   6 // maxlen letters using the set of letters in alpha.
   7 // Fetch strings using a Java-like Next()/HasNext() interface.
   8
   9 #include <string>
  10 #include <vector>
  11 #include "util/test.h"
  12 #include "re2/testing/string_generator.h"
  13
  14 namespace re2 {
  15
  16 StringGenerator::StringGenerator(int maxlen, const vector<string>& alphabet)
  17     : maxlen_(maxlen), alphabet_(alphabet),
  18       generate_null_(false),
  19       random_(false), nrandom_(0), acm_(NULL) {
  20
  21   // Degenerate case: no letters, no non-empty strings.
  22   if (alphabet_.size() == 0)
  23     maxlen_ = 0;
  24
  25   // Next() will return empty string (digits_ is empty).
  26   hasnext_ = true;
  27 }
  28
  29 StringGenerator::~StringGenerator() {
  30   delete acm_;
  31 }
  32
  33 // Resets the string generator state to the beginning.
  34 void StringGenerator::Reset() {
  35   digits_.clear();
  36   hasnext_ = true;
  37   random_ = false;
  38   nrandom_ = 0;
  39   generate_null_ = false;
  40 }
  41
  42 // Increments the big number in digits_, returning true if successful.
  43 // Returns false if all the numbers have been used.
  44 bool StringGenerator::IncrementDigits() {
  45   // First try to increment the current number.
  46   for (int i = digits_.size() - 1; i >= 0; i--) {
  47     if (++digits_[i] < alphabet_.size())
  48       return true;
  49     digits_[i] = 0;
  50   }
  51
  52   // If that failed, make a longer number.
  53   if (digits_.size() < maxlen_) {
  54     digits_.push_back(0);
  55     return true;
  56   }
  57
  58   return false;
  59 }
  60
  61 // Generates random digits_, return true if successful.
  62 // Returns false if the random sequence is over.
  63 bool StringGenerator::RandomDigits() {
  64   if (--nrandom_ <= 0)
  65     return false;
  66
  67   // Pick length.
  68   int len = acm_->Uniform(maxlen_+1);
  69   digits_.resize(len);
  70   for (int i = 0; i < len; i++)
  71     digits_[i] = acm_->Uniform(alphabet_.size());
  72   return true;
  73 }
  74
  75 // Returns the next string in the iteration, which is the one
  76 // currently described by digits_.  Calls IncrementDigits
  77 // after computing the string, so that it knows the answer
  78 // for subsequent HasNext() calls.
  79 const StringPiece& StringGenerator::Next() {
  80   CHECK(hasnext_);
  81   if (generate_null_) {
  82     generate_null_ = false;
  83     sp_ = NULL;
  84     return sp_;
  85   }
  86   s_.clear();
  87   for (int i = 0; i < digits_.size(); i++) {
  88     s_ += alphabet_[digits_[i]];
  89   }
  90   hasnext_ = random_ ? RandomDigits() : IncrementDigits();
  91   sp_ = s_;
  92   return sp_;
  93 }
  94
  95 // Sets generator up to return n random strings.
  96 void StringGenerator::Random(int32 seed, int n) {
  97   if (acm_ == NULL)
  98     acm_ = new ACMRandom(seed);
  99   else
 100     acm_->Reset(seed);
 101
 102   random_ = true;
 103   nrandom_ = n;
 104   hasnext_ = nrandom_ > 0;
 105 }
 106
 107 void StringGenerator::GenerateNULL() {
 108   generate_null_ = true;
 109   hasnext_ = true;
 110 }
 111
 112 }  // namespace re2
 113