Alexander Gutkin | 0d4c523 | 2013-02-28 13:47:27 +0000 | [diff] [blame] | 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 | |