From: Bob Kline <bkline@...>
Date: 2001-03-26T01:53:31+09:00
Subject: [ruby-talk:13199] Re: Reading a file backwards

On Sun, 25 Mar 2001, Daniel Berger wrote:

> Ah, crud - I forgot to mention that I *do not* want to read the
> entire file into memory, which the readlines method appears to do
> (unless I'm mistaken). I also would like to avoid tricks like
> creating temporary files.

Here's the logic (but not the ruby code - I'm not that familiar with the
language) for a two-pass approach:

   Scan the file, building an array of file positions and lengths for
      each line (an array of tuples)
   Start at the back of the array and move toward the front
   For each position in the array:
      Seek to the file position
      Read the line
      Process the line

Here's the logic for a somewhat more complicated, but possibly more
efficient one-pass approach:

   Seek to the end of the file
   Decide on a block size you can afford to keep in memory (you may
      have to keep more in memory if you run into strings longer
      than your blocksize or which straddle blocks)
   Back up the distance equal to this block size
   Read a block
   Scan backwards from the end of the block, skipping past the line-end
      character (or pair, depending on your platform) at the end of the
      block
   For each line [see note below]:
      Extract the substring for the line
      Process the line
   Save any leftover partial line at the beginning of the block
   While more data:
      Back up to the position of the prior block (or BOF if partial block)
      Read the block
      Append any leftover from earlier processing
      Scan backwards from the end of the block
      For each line in the block:
         Extract the substring for the line
         Process the line
      Save any leftover partial line at the beginning of the block
   If any leftover:
      process the leftover (which represents the first line in the file)

Recognition of a line in a block when you are using the second method
occurs when you encounter the line-termination character (or pair,
depending on your platform).  Extract the data following the
line-termination character(s) as the substring for the line.

For both algorithms, you need to open the file in binary mode, to avoid
getting bogus results when you ask for or specify file positions.
Handling all the line-end combinations can be tricky, because different
platforms use different conventions, and the real world will hand you
files that present some anomalies.  For example, Macintosh uses CR
(ASCII 13) as the line-end character.  UNIX uses LF (ASCII 10).  VAX,
CPM, DOS, and Windows all use CR followed by LF.  One too-common anomaly
is the presence of extra CR characters preceding the CR+LF pair.  Until
you see the LF you'll be tempted to think you're dealing with a Mac
file.  One way of dealing with this is to read from the beginning of the
file until you have seen at least one CR and/or LF character followed by
at least one non-CR/LF.  If only CR was seen, set an eol variable to
"\r"; if only LF was seen, set the variable to "\n"; if a CR was
followed by LF, set the variable to "\r\n"; if both were seen but the
order was LF followed by CR, you might set the variable to "\n\r"
(though this isn't a legitimate combo on any platform I know of). Then
back up and use your variable to recognize line-ends canonical to the
platform you've decided you're handling, treating the anomolous strays
as part of the line itself.  For this peek-ahead in which you attempt to
determine which platform you're dealing with, you also have to handle
the border condition of a file which consists only of CR and LF
characters.

There's a third approach which is a variation on the first, and which
avoids all the hand-wringing over end-of-line conventions by letting the
underlying I/O libraries handle the problem:

   Open the file in text mode
   Set pos variable to zero
   While more lines:
      Read and discard the line
      Append value of pos value to array
      Store the current position of the file in pos
   Process the lines using the position array as in the first option

In this case you're paying the price of a small amount of additional
overhead (making a copy of each line in the first pass) for a measurable
increase in simplicity, robustness, and portability.  And you don't need
to store line lengths in this version, either.  This third approach is
the one I recommend.

Hope this helps.

[PS: I dropped ruby-talk@netlab.co.jp from the address list; I don't
know what the conventions are for the ruby mailing list, but I didn't
want to fall into inadvertant cross-posting, which usually invites
flames.]

-- 
Bob Kline
mailto:bkline@rksystems.com
http://www.rksystems.com