string_generator.cc revision 5821806d5e7f356e8fa4b058a389a808ea183019
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
14namespace re2 {
15
16StringGenerator::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
29StringGenerator::~StringGenerator() {
30  delete acm_;
31}
32
33// Resets the string generator state to the beginning.
34void 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.
44bool 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.
63bool 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.
79const 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.
96void 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
107void StringGenerator::GenerateNULL() {
108  generate_null_ = true;
109  hasnext_ = true;
110}
111
112}  // namespace re2
113
114