Tynt programming assignment (Part 4)

Finally, here is where I have to implement the sorting algorithm and collection. I created a List collection I called IntegerList:

package com.tynt.app.util;

public class IntegerList {
 public static final int BUFFER_SIZE = 100;
 private Integer[] internalArray;
 private int size;
 
 public IntegerList() {
  internalArray = new Integer[BUFFER_SIZE];
  size = 0;
 }
 
 public IntegerList(int size) {
  if (size < 0) {
   throw new RuntimeException("Cannot create IntegerList with negative size");
  }
  internalArray = new Integer[size];
  size = 0;
 }
 
 public int size() {
  return size;
 }
 
 public void put(int index, Integer value) {
  if (index > -1 && index < size) {
   internalArray[index] = value;
  } else {
   throw new RuntimeException("Cannot put value "+value+" at index "+index+" IntegerList has size "+size);
  }
 }
 
 public void concatenate(Integer value) {
  if (value == null) {
   throw new RuntimeException("Cannot concatenate null values");
  }
  if (size + 1 == internalArray.length) {
   Integer[] temp = new Integer[internalArray.length + BUFFER_SIZE];
   System.arraycopy(internalArray, 0, temp, 0,
     internalArray.length);
   internalArray = temp;
  }
  internalArray[size++] = value;
 }
 
 public void concatenate(IntegerList values) {
  for (int i = 0 ; i < values.size(); i++) {
   concatenate(values.get(i));
  }
 }
 
 public Integer get(int index) {
  if (index > -1 && index < size) {
   return internalArray[index];
  } else {
   throw new RuntimeException("Cannot access value at "+index+" in IntegerList size "+size);
  }
 }
 
 public Integer remove(int index) {
  if (index > -1 && index < size) {
   Integer result = get(index);
   IntegerList integerList = new IntegerList();
   for(int i = 0; i < size; i++) {
    if (i != index) {
     integerList.concatenate(get(i));
    }
   }
   internalArray = integerList.internalArray;
   size = size - 1;
   return result;
  } else {
   throw new RuntimeException("Cannot access value at "+index+" in IntegerList size "+size);
  }
 }
 
 public static IntegerList quicksort(IntegerList unsorted) {
      IntegerList less = new IntegerList();
      IntegerList greater = new IntegerList();
      if (unsorted.size() <= 1) {
          return unsorted;
      }
      Integer pivot = selectPivot(unsorted);
      for(int i = 0; i < unsorted.size(); i++) {
       Integer value = unsorted.get(i);
       if (value <= pivot) {
        less.concatenate(value);
       } else {
        greater.concatenate(value);
       }
      }
      return concatenate(quicksort(less), pivot, quicksort(greater));
 }
 
 public static Integer selectPivot(IntegerList unsorted) {
  if (unsorted == null || unsorted.size() < 2) {
   throw new RuntimeException("Cannot select pivot on empty or single element list");
  }
  int pivotIndex = unsorted.size() / 2;
  return unsorted.remove(pivotIndex);
 }
 
 public static IntegerList concatenate(IntegerList less, Integer pivot, IntegerList greater) {
  if (less == null | pivot == null || greater == null) {
   throw new RuntimeException("Cannot concatenate null values");
  }
  IntegerList finalList = new IntegerList(less.size()+1+greater.size());
  finalList.concatenate(less);
  finalList.concatenate(pivot);
  finalList.concatenate(greater);
  return finalList;
 }
}

IntegerList implements a quicksort method which returns the IntegerList as a sorted IntegerList. My implementation of quicksort has several drawbacks:

• I create additional collections (less,greater,etc...) for each invocation of quicksort and concatenate, so lots of memory could be used up with a long list to sort. It would be less memory to sort the list in-place without recursion/extra collections.
  
• Speaking of recursion, too much recursion could cause a stack overflow as well.

With IntegerList implemented, I can use it to implement Assignment4:

package com.tynt.app;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

import com.tynt.app.util.*;

public class Assignment4 implements InputReader {

  public String readFile(InputStream is) {
      BufferedReader d = new BufferedReader(new InputStreamReader(is));
      String line;
      IntegerList unsortedList = new IntegerList();
      try {
          line = d.readLine();
          while (line != null) {
              Integer value = null;
              try {
                  value = new Integer(Integer.parseInt(line));
              } catch (NumberFormatException e) {
                  throw new RuntimeException(e);
              }
              unsortedList.concatenate(value);
              line = d.readLine();
          }
      } catch (IOException e) {
          throw new RuntimeException(e);
      }
      StringBuilder sb = new StringBuilder();
      IntegerList sortedList = IntegerList.quicksort(unsortedList);
      if (sortedList == null) {
          sortedList = new IntegerList();
      }
      for (int i=0;i < sortedList.size();i++) {
          sb.append(sortedList.get(i));
          sb.append(NEW_LINE);
      }
      return sb.toString();
  }

}

Still need to implement the Hash collection and driver.