How can we revere order of lines in a file not the lines themselves. File can get huge.
No assumption should be made about the length of a line.
Input:
this is line1
this is line2
this is line3
Example Output:
this is line3
this is line2
this is line1
I though of making use of another file as buffer, like a stack data structures, but could not really go anywhere with it.
Any thoughts on this ?
Read in large blocks of the file starting at both ends. Inside those blocks, swap the first line for the last line and then move both pointers to keep track of where you are. Write out each block as you fill it. When the two pointers meet in the middle, you are done.
Don't try to modify the blocks in place, that will make things more complicated. Use four blocks, the first read block, the first write block, the last read block, and the last write block. As each write block is complete, write it out. As each read block is exhausted, read in another one. Be careful not to overwrite anything you've not yet read!
It should be fairly straightforward, just tedious. If you don't need it to be optimal, you can just read blocks backwards and write out a new file and then move it on top of the existing file.
If the file won't fit in memory, then it's a two-pass process. The first pass, you read chunks of the file (as many lines as will fit into memory), and then write them to a temporary file in reverse order. So you have:
while not end of input
read chunk of file into array of lines
write lines from array to temporary file, in reverse order
end while
When you're done with the first pass, you'll have a bunch of temporary files: temp1.txt, temp2.txt, temp3.txt ... tempN.txt.
Now open the last file (tempN.txt) for append, and start appending the files in reverse order. So you have:
open fileN for append
fileno = N-1
while fileno > 0
append file_fileno to fileN
fileno--
end while
Then rename tempN.txt and delete the other temporary files.
By the way, you can use the operating system supplied concatenation utility for step 2. On Windows, for example, you could replace step 2 with:
copy /A file4.txt+file3.txt+file2.txt+file1.txt mynewfile.txt
There are similiar utilities on other platforms.
You might run into command line length limitations, though.
it can be done in 2 simple steps:
step 1: reverse all the file
step 2: reverse each line
step:0 1 2
---------------------
abc zyx xyz
1234 => 4321 => 1234
xyz cba abc
EDIT: here is a complete solution:
#include <iostream>
#include <fstream>
#include <algorithm>
#define BUFFSIZE 4098 /*make sure this is larger then the longest line...*/
using namespace std;
bool reverse_file(const char* input, const char* output)
{
streamsize count=0;
streamoff size=0,pos;
char buff[BUFFSIZE];
ifstream fin(input);
ofstream fout(output);
if(fin.fail() || fout.fail()){
return false;
}
fin.seekg(0, ios::end);
size = fin.tellg();
fin.seekg(0);
while(!fin.eof()){
fin.read(buff, BUFFSIZE);
count = fin.gcount();
reverse(buff,buff+count);
pos = fin.tellg();
if(pos<0) {
pos = size;
}
fout.seekp(size - pos);
fout.write(buff,count);
}
return true;
}
bool reverse_file_lines(const char* input, const char* output)
{
streamsize count=0;
char buff[BUFFSIZE];
ifstream fin(input);
ofstream fout(output);
if(fin.fail() || fout.fail()){
return false;
}
while(!fin.eof()){
fin.getline(buff, BUFFSIZE);
/*if BUFFSIZE is smallest then line size gcount will return 0,
but I didn't handle it...*/
count = fin.gcount();
if(buff[count-1]==0)count--;
reverse(buff,buff+count);
fout.write(buff,count);
if(!fin.eof()){
fout<<endl;
}
}
return true;
}
int main()
{
reverse_file("test.in", "test.tmp");
reverse_file_lines("test.tmp","test.out");
return 0;
}
