/** shuffle.cpp --- Shuffle lines in a file
 *
 * Copyright (C) 2007  Aaron S. Hawley <aaronh@localhost>
 *
 * Author: Aaron S. Hawley
 * Keywords: random, games
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * $Id: shuffle.cpp,v 1.5 2007/09/24 13:01:23 aaronh Exp $
 *
 * Commentary:
 *
 * Shuffle the lines on standard input and print them on standard
 * output.  See: David R. Musser, "Test-line Random Shuffling
 * Program", 25 April 2005.
 *
 * Examples:
 *
 * $ seq 1 7 | ./shuffle
 * 4
 * 1
 * 6
 * 2
 * 5
 * 3
 * 7
 *
 * $ ./shuffle < INFILE > OUTFILE
 *
 * Code:
 */

#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;

  
template <typename Container> 
class RandomGenerator
{
  typedef typename Container::difference_type fun_argument;
  typedef typename Container::difference_type fun_result;
public:
  RandomGenerator() {
    // Seed random number generator with current time.
    srand48(time(NULL));
  }

  fun_result operator() (fun_argument n) {
    return lrand48() % n;
  }
};


main ()
{
  vector<string> lines;
  string line;
  RandomGenerator< vector<string> > randline;
  ostream_iterator<string> output(cout, "\n"); // FIXME: use std::endl

  // Read lines into a vector.
  while (getline(cin, line))
    {
      lines.push_back(line);
    }

  random_shuffle(lines.begin(), lines.end(), randline);
  copy(lines.begin(), lines.end(), output);
}