Accelerated C++ Chapter05 Exercise 5-1編

ドウモデス。

Exercise 5-1を綺麗にしようと試行錯誤していて，簡潔になる方法を思いついたので，
実装していたら，途中で，うまくいかないことに気づいてしばし心折れました。
結局，最初に解いた汚い解答を載せる次第となったこと，ここに深く詫びるでござる。
というか，1問1問の答えがでかくなってきたので，分割しつついきます。
なので，ここでは，Exercise 5-1だけ。

Exercise 5-1

ex5-1.hh

#ifndef GUARD_EX5_1_H
#define GUARD_EX5_1_H

#include <string>
#include <vector>
#include <list>
#include <algorithm>

struct Line {
  std::string line;
  std::string rotated_line;
  std::string index;
};

// clean up needed. I hate all these `::'s
std::list<std::string> rotate(const std::list<std::string>& l);
std::string rotate(const std::string& s);
std::vector<std::string> split_into_vec(const std::string&);
std::vector<std::string> get_all_rotations(const std::string& s);
bool cmp(const Line&, const Line&);
void sort_rotations(std::vector<Line> &vec);
void print_permuted_line(const std::vector<std::string>&, const std::string&, std::string::size_type);
void print_permuted_lines(const std::vector<std::string>& original_lines);
std::string str_from_list(const std::list<std::string>& l);
std::string::size_type get_maxlen(const std::vector<std::string>&);

#endif  // GUARD_EX5_1_H

ex5-1.cc

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <cctype>

#include "ex5-1.hh"

using namespace std;

string::size_type get_maxlen(const vector<string>& lines)
{
  string::size_type ret = 0;

  for (vector<string>::const_iterator it = lines.begin(); it != lines.end(); ++it) {
    string::size_type len = it->length();
    if (len > ret) {
      ret = len;
    }
  }

  return ret;
}

list<string> rotate(const list<string>& l)
{
  list<string> ret;
  list<string>::const_iterator it = l.begin();
  list<string>::const_iterator beg = l.begin();
  ++it;
  for (; it != l.end(); ++it) {
    ret.push_back(*it);
  }
  ret.push_back(*beg);

  return ret;
}

string rotate(const string& s)
{
  string ret;
  vector<string> v = split_into_vec(s);
  list<string> l(v.begin(), v.end());
  l = rotate(l);

  return str_from_list(l);
}

string str_from_list(const list<string>& l)
{
  string ret;

  for (list<string>::const_iterator it = l.begin(); it != l.end(); ++it) {
    ret += *it;
    if (it != --l.end()) {
      ret += " ";
    }
  }
  return ret;
}

vector<string> split_into_vec(const string& s)
{
  vector<string> ret;
  string::const_iterator it = s.begin();
  while (it != s.end()) {
    while (it != s.end() && isspace(*it)) {
      ++it;
    }
    string::const_iterator beg = it;
    while (it != s.end() && !isspace(*it)) {
      ++it;
    }
    if (beg != it) {
      ret.push_back(string(beg, it));
    }
  }

  return ret;
}

vector<string> get_all_rotations(const string& s)
{
  vector<string> ret;
  vector<string> splited = split_into_vec(s);
  // Of course, we need the original line
  ret.push_back(s);
  string rotated = s;
  // Get each rotated string and store it into vector
  for (int i = 0, j = splited.size() - 1; i < j; ++i) {
    rotated = rotate(rotated);
    ret.push_back(rotated);
  }

  return ret;
}

bool cmp(const Line& l1, const Line& l2)
{
  string key1 = l1.rotated_line;
  transform(key1.begin(), key1.end(), key1.begin(), (int (*)(int))toupper);
  string key2 = l2.rotated_line;
  transform(key2.begin(), key2.end(), key2.begin(), (int (*)(int))toupper);

  return key1.compare(key2) < 0;
}

void sort_rotations(vector<Line> &vec)
{
  sort(vec.begin(), vec.end(), cmp);
}

// @lines lines[0] => "The quick brown fox",
//        lines[1] => "jumped over the fence", etc...
void print_permuted_lines(const vector<string>& lines)
{
  vector<Line> sorted_lines;
  for (vector<string>::const_iterator it = lines.begin(); it != lines.end(); ++it) {
    // Get all rotations of this line
    vector<string> v = get_all_rotations(*it);
    // For each rotation, store the index and its line into vector.
    for (vector<string>::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
      string index = split_into_vec(*iter).front();
      Line line;
      line.line = *it;
      line.index = index;
      line.rotated_line = *iter;
      sorted_lines.push_back(line);
    }
  }
  sort_rotations(sorted_lines);
  string::size_type maxlen = get_maxlen(lines);
  for (vector<Line>::const_iterator it = sorted_lines.begin(); it != sorted_lines.end(); ++it) {
    vector<string> splited = split_into_vec(it->line);
    print_permuted_line(splited, it->index, maxlen);
  }
}

void print_permuted_line(const vector<string>& line, const string& index, string::size_type maxlen)
{
  string former, latter;
  const string separator = " | ";
  vector<string>::const_iterator it = line.begin();

  for (; it != line.end() && it->compare(index) != 0; ++it) {
    former += *it;
    if (it != line.end() - 1 && it[1] != index) {
      former += " ";
    }
  }
  // this is index
  latter += *it;
  // and the rest
  for (++it; it != line.end(); ++it) {
    latter += " " + *it;
  }
  cout << string(maxlen - former.size(), ' ') << former;
  cout << separator;
  cout << latter;
  cout << endl;
}

デモ用メイン ex5-1_main.cc マインちゃん。えっ。

#include <iostream>
#include <string>
#include <vector>
#include <list>

#include "ex5-1.hh"

using namespace std;

int main()
{
  string s;
  vector<string> vec;
  while (getline(cin, s)) {
    vec.push_back(s);
  }

  print_permuted_lines(vec);

  return 0;
}

実行結果

% echo "The quick brown fox\njumped over the fence" | ./ex5-1_demo
            The quick | brown fox
      jumped over the | fence
      The quick brown | fox
                      | jumped over the fence
               jumped | over the fence
                  The | quick brown fox
          jumped over | the fence
                      | The quick brown fox

おまけ

すごくメモリを贅沢に使っていることはわかっちゃーいるんですが，
いいデータ構造を思いつかないし，知らない。いや，凡夫だから，
知らないから思いつかないのか。

オリジナルの行とインデックスの対応を持っておかないと，
出力するときに困るから，オリジナルの行は必要だし，
すべて読み込んだ後にソートするから，ローテーションも全部必要だし・・・。
うーん，わからん。