15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2008 The RE2 Authors.  All Rights Reserved.
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file.
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// String generator: generates all possible strings of up to
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// maxlen letters using the set of letters in alpha.
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Fetch strings using a Java-like Next()/HasNext() interface.
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string>
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector>
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/test.h"
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/testing/string_generator.h"
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 {
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)StringGenerator::StringGenerator(int maxlen, const vector<string>& alphabet)
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    : maxlen_(maxlen), alphabet_(alphabet),
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      generate_null_(false),
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      random_(false), nrandom_(0), acm_(NULL) {
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Degenerate case: no letters, no non-empty strings.
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (alphabet_.size() == 0)
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    maxlen_ = 0;
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Next() will return empty string (digits_ is empty).
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hasnext_ = true;
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)StringGenerator::~StringGenerator() {
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete acm_;
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Resets the string generator state to the beginning.
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void StringGenerator::Reset() {
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  digits_.clear();
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hasnext_ = true;
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  random_ = false;
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  nrandom_ = 0;
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  generate_null_ = false;
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Increments the big number in digits_, returning true if successful.
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns false if all the numbers have been used.
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool StringGenerator::IncrementDigits() {
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // First try to increment the current number.
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = digits_.size() - 1; i >= 0; i--) {
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (++digits_[i] < alphabet_.size())
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      return true;
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    digits_[i] = 0;
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // If that failed, make a longer number.
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (digits_.size() < maxlen_) {
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    digits_.push_back(0);
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return true;
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return false;
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Generates random digits_, return true if successful.
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns false if the random sequence is over.
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool StringGenerator::RandomDigits() {
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (--nrandom_ <= 0)
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return false;
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Pick length.
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int len = acm_->Uniform(maxlen_+1);
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  digits_.resize(len);
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < len; i++)
715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    digits_[i] = acm_->Uniform(alphabet_.size());
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return true;
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the next string in the iteration, which is the one
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// currently described by digits_.  Calls IncrementDigits
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// after computing the string, so that it knows the answer
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for subsequent HasNext() calls.
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const StringPiece& StringGenerator::Next() {
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(hasnext_);
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (generate_null_) {
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    generate_null_ = false;
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    sp_ = NULL;
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return sp_;
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s_.clear();
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < digits_.size(); i++) {
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    s_ += alphabet_[digits_[i]];
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hasnext_ = random_ ? RandomDigits() : IncrementDigits();
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  sp_ = s_;
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return sp_;
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sets generator up to return n random strings.
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void StringGenerator::Random(int32 seed, int n) {
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (acm_ == NULL)
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    acm_ = new ACMRandom(seed);
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  else
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    acm_->Reset(seed);
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  random_ = true;
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  nrandom_ = n;
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hasnext_ = nrandom_ > 0;
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void StringGenerator::GenerateNULL() {
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  generate_null_ = true;
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  hasnext_ = true;
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace re2
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
114