/** 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.3 2007/09/17 17:41:30 aaronh Exp $
 *
 * Commentary:
 *
 * This C++ program will shuffle the lines in a file randomly.
 *
 * Based on shuffle.awk by the same author.
 *
 * Examples:
 *
 * $ seq 1 7 | ./shuffle
 * 4
 * 1
 * 6
 * 2
 * 5
 * 3
 * 7
 *
 * $ ./shuffle < INFILE > OUTFILE
 *
 * Code:
 */

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

using namespace std;

main ()
{
  vector<string> lines;
  string line;

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

  // Seed random number generator with current time.
  srand48(time(NULL));

  // for i from 1 .. n
  for (vector<string>::iterator i = lines.begin(); i < lines.end(); i++)
    {
      // Generate random number between [1, n - i]
      long int random_n = floor(drand48() * (lines.end() - i));

      // Pick random line between [i, n]
      vector<string>::iterator random_line = i + random_n;

      // Print random line.
      cout << *random_line << endl;

      // Delete randomly picked line by overwriting it with line i.
      *random_line = *i; // line[random] = line[i]
    }
}