teaching machines

CS 330 Lecture 26 – C++’s standard template library

April 6, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• map
• vector
• using STL to write a probababble engine
• http://www.gutenberg.org/

Code

bsearch.cpp

#include <iostream>

template<typename T>
int binarysearch(T *haystack,
                 T needle,
                 int first,
                 int last) {
  if (first > last) return -1;

  int mid = (first + last) / 2;
  if (needle < haystack[mid]) {
    return binarysearch<T>(haystack, needle, first, mid - 1);
  } else if (needle > haystack[mid]) {
    return binarysearch<T>(haystack, needle, mid + 1, last);
  } else {
    return mid;
  }
}

int main() {
  int numbers[] = {1, 3, 8, 100, 1003, 12000};
  std::cout << binarysearch<int>(numbers, 12000, 0, 5) << std::endl;

  std::string names[] = {"Ashlyn", "Becky", "Kevin"};
  std::cout << binarysearch<std::string>(names, "Chris", 0, 2) << std::endl;
}

probababble.cpp

#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

typedef std::map<std::string, std::vector<std::string> > strvec_map_t;

void fill_map(strvec_map_t& two_words_to_chasers) {
  string aquel;
  string ese;
  string este;

  cin >> aquel >> ese;

  while (cin >> este) {
    string key = aquel + " " + ese;
    /* cout << "key: " << key << std::endl; */
    /* cout << "este: " << este << std::endl; */
    /* cout << "" << std::endl; */

    // append este to key list
    strvec_map_t::iterator match = two_words_to_chasers.find(key); 

    // Did I not find the key?
    if (match == two_words_to_chasers.end()) {
      vector<string> chasers;
      chasers.push_back(este);

      pair<string, vector<string> > record;
      record.first = key;
      record.second = chasers;

      two_words_to_chasers.insert(record);
    }

    // Otherwise, I found the key. Append.
    else {
      match->second.push_back(este);
    }

    aquel = ese;
    ese = este;
  }

  /* for (strvec_map_t::iterator key = two_words_to_chasers.begin(); */
       /* key != two_words_to_chasers.end(); */
       /* ++key) { */
    /* std::cout << "key: " << key->first << std::endl; */
  /* } */
}

void generate(const strvec_map_t& two_words_to_chasers,
              const string& first,
              const string& second,
              int nwords) {
  bool hit_dead_end = false;
  string aquel = first;
  string ese = second;

  string key = aquel + " " + ese;
  nwords -= 2;
  std::cout << key;

  while (nwords > 0 && !hit_dead_end) {
    // generate a random chaser
    strvec_map_t::const_iterator match = two_words_to_chasers.find(key);

    hit_dead_end = match == two_words_to_chasers.end();

    if (!hit_dead_end) {
      vector<string> chasers = match->second;
      int random_index = (int) ((rand() / (float) RAND_MAX) * (chasers.size() - 1));
      std::string este = chasers[random_index];
      std::cout << " " << este;

      --nwords;
      aquel = ese;
      ese = este;
      key = aquel + " " + ese;
    }
  }
}

int main(int argc, char **argv) {
  strvec_map_t two_words_to_chasers;

  fill_map(two_words_to_chasers);
  generate(two_words_to_chasers, argv[1], argv[2], atoi(argv[3]));
  return 0;
}

Haiku