Thursday, February 19, 2015

Read N Characters Given Read4 I & II

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note: (for II)
The read function may be called multiple times.



Update: 2015 - 03 - 30
I realized that I understood the question wrong. The char* buf is the output array. The explanation below is correct, here is the updated code.


public int read4(char[] buff){
  return 4;
 }
 public int readN(char[] buff, int N){
  char[] tmp = new char[4];
  int index = 0, next = 0;
  while(index < N  && (next = read4(tmp)) != 0)
   for(int i = 0; i < next && index < N; buff[index++] = tmp[i++]);
  return index;
 }
 int curr = 0;
 public int readN2(char[] buff, int N){
  char[] tmp = new char[4];
  int next = 0;
  int length = 0;
  while(length < N && (next = read4(tmp)) != 0){
   for(int i = 0; i < next && length++ < N; buff[curr++] = tmp[i++]);
  }
  return length;
 }


It took me a while to understand how the read() method works. I implemented the read4() method, which makes the whole class easier to test.

Basically, if n >= length of the buf, we read the whole array and return its length. Otherwise, we track the position of the next character (nextChar) we will read next time we call readN() method, so we simply start from nextChar every time we call readN(). Since we initialize the out array (the one we stored the characters) with size n, each time we call readN(), we need to increment the length of the out array if the length of  buf is larger than n. I wrote another method read() to handle cases such as length of buff is smaller than n or the remaining unread length of array is smaller than n, reset index and nextChar to zero since we have reached the end of the array.

It is much easier to understand if you happen to know how Java implements read().


public class ReadN {
 static char[] out = new char[4];
 static int index = 0;
 static int nextChar = 0;
 
 private static int read4(char[] buf, int start, int length) {
  int len = length - start;
  if (len < 4) {
   int i = len;
   while (i > 0) {
    out[index++] = buf[start++];
    i--;
   } 
   return len;
  }
  for (int i = 0; i < 4; i++) {
   out[index++] = buf[start++];
  }
  return 4;
 }
 private static int read(char[] buf) {
  int total = 0;
  int length = buf.length;
  int start = nextChar;
  while (start < length) {
   total += read4(buf, start, length);
   start += 4;
  }
  index = 0;
  nextChar = 0;
  return total;
 }
 /**
  * I
  * @param buf
  * @param n
  * @return
  */
 public static int readN(char[] buf, int n) {
  if (buf == null)
   throw new NullPointerException("Null array!");
  int length = buf.length;
  out = new char[n];
  if (length <= n) {
   return read(buf);
  }
  int start = 0;
  int total = 0;
  while (start < n) {
   total += read4(buf, start, n);
   start += 4;
  }
  return total;
 }
 /**
  * II
  * call multiple times
  * @param buf
  * @param n
  * @return
  */
 public static int readNII(char[] buf, int n) {
  if (buf == null)
   throw new NullPointerException("Null array!");
  int length = buf.length;
  if (index == 0)
   out = new char[n];
  else {
   int incrementLen = length - nextChar >= n ? n : length - nextChar;
   char[] copy = new char[out.length + incrementLen];
   System.arraycopy(out, 0, copy, 0, out.length);
   out = copy;
   if (incrementLen < n)
    length = incrementLen;
  }
  if (length <= n) {
   return read(buf);
  }
  int start = nextChar;
  int total = 0;
  while (start < n) {
   total += read4(buf, start, n);
   if (start + 4 > n) {
    start = n;
    break;
   }
   start += 4;
  }
  nextChar = start;
  return total;
 }
 public static void main(String[] args) {
  //char[] input = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
  //char[] input = {};
  //char[] input = {'a', 'b', 'c'};
  char[] input = {'a', 'b', 'c', 'd'};
  int total = 0;
  while (total < input.length) {
   total += readNII(input, 6);
  }
  System.out.println(total);

 }
}

No comments:

Post a Comment