sort/MergeSortFile.java

Go to the documentation of this file.

package sort;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;

public class MergeSortFile<T extends Comparable<T> & Serializable> {
    private static String TEMP_ROOT_NAME = "tempFile";
    private final int mNumObjects;
    private MergeSort<T> mSort = new MergeSort<T>();
    private int mFileCnt = 0;

    protected class FileObjContainer {
        FileInputStream inStr = null;
        BufferedInputStream bufStr = null;
        ObjectInputStream objStr = null;
        boolean EOF = false;

        public FileObjContainer(File inFile) throws IOException {
            inStr = new FileInputStream(inFile);
            bufStr = new BufferedInputStream(inStr);
            objStr = new ObjectInputStream(bufStr);
        }

        public T readObj() throws IOException, ClassNotFoundException {
            T newObj = null;
            if ((!EOF) && bufStr.available() > 0) {
                newObj = (T) objStr.readObject();
            } else {
                EOF = true;
            }
            return newObj;
        }

        public void close() throws Throwable {
            super.finalize();
            try {
                if (inStr != null) {
                    inStr.close();
                }
                if (bufStr != null) {
                    bufStr.close();
                }
                if (objStr != null) {
                    bufStr.close();
                }
            } catch (IOException e) {
            }
        } // finalize
    } // ================< class FileObjContainer >======================

    protected class ReadFileValues {
        private ArrayList<FileObjContainer> mObjFiles;
        private ArrayList<T> mValues;

        public ReadFileValues(ArrayList<FileObjContainer> objFiles) throws ClassNotFoundException, IOException {
            this.mObjFiles = objFiles;
            mValues = new ArrayList<T>();
            // initialize the mValues ArrayList with the first value from each
            // file
            for (FileObjContainer objFile : objFiles) {
                T obj = objFile.readObj();
                mValues.add(obj);
            }
        }

        protected int minIx(ArrayList<T> values) {
            int ix = -1;
            T minVal = null;
            for (int i = 0; i < values.size(); i++) {
                T tstVal = values.get(i);
                if (tstVal != null) {
                    if (minVal == null) {
                        minVal = tstVal;
                        ix = i;
                    } else if (minVal.compareTo((T) tstVal) > 0) {
                        minVal = tstVal;
                        ix = i;
                    }
                }
            }
            return ix;
        } // minIx

        public T getLeastVal() throws ClassNotFoundException, IOException {
            T leastVal = null;
            int ix = minIx(mValues);
            if (ix >= 0) {
                leastVal = mValues.get(ix);
                // read a new value to replace the one that will be returned
                T newValue = mObjFiles.get(ix).readObj();
                mValues.set(ix, newValue);
            }
            return leastVal;
        }
    } // ================< class ReadFileValues >==========================

    public MergeSortFile(int numObjs) {
        this.mNumObjects = numObjs;
    }

    protected String nextTempFileName() {
        mFileCnt++;
        String tempFileName = String.format("%s%02d", TEMP_ROOT_NAME, mFileCnt);
        return tempFileName;
    }

    protected File writeSortedBlock(ArrayList<T> objList, File parentDir) throws IOException {
        String tempFileName = nextTempFileName();
        // create a temporary file in the parent directory
        File tempFile = new File(parentDir, tempFileName);
        FileOutputStream fileStr = null;
        BufferedOutputStream bufStr = null;
        ObjectOutputStream objOutStr = null;
        try {
            fileStr = new FileOutputStream(tempFile);
            bufStr = new BufferedOutputStream(fileStr);
            objOutStr = new ObjectOutputStream(bufStr);
            for (T obj : objList) {
                objOutStr.writeObject(obj);
            }
            objOutStr.flush();
        } finally {
            try {
                if (fileStr != null) {
                    fileStr.close();
                }
                if (bufStr != null) {
                    bufStr.close();
                }
                if (objOutStr != null) {
                    objOutStr.close();
                }
            } catch (IOException e) {
            }
        }
        return tempFile;
    } // writeSortedBlock

    protected File readAndSortBlock(BufferedInputStream bufStr, ObjectInputStream objStr, File parentDir) 
            throws IOException, ClassNotFoundException {
        File tempFile = null;
        ArrayList<T> objList = new ArrayList<T>();
        int objCnt = 0;
        while (objCnt < mNumObjects && (bufStr.available() > 0)) {
            T obj = (T) objStr.readObject();
            objList.add(obj);
            objCnt++;
        }

        if (objList.size() > 0) {
            mSort.mergeSort(objList);
            tempFile = writeSortedBlock(objList, parentDir);
        }
        return tempFile;
    } // readAndSortBlock

    protected void mergeFiles(ArrayList<File> fileList, File outFile) throws IOException, ClassNotFoundException {
        if (fileList.size() > 0) {
            if (fileList.size() == 1) {
                File tempFile = fileList.get(0);
                tempFile.renameTo(outFile);
            } else {
                ArrayList<FileObjContainer> fileObjs = new ArrayList<FileObjContainer>();
                for (int i = 0; i < fileList.size(); i++) {
                    File file = fileList.get(i);
                    fileObjs.add(new FileObjContainer(file));
                } // for
                ReadFileValues fileReader = new ReadFileValues(fileObjs);
                FileOutputStream fileStr = null;
                BufferedOutputStream bufStr = null;
                ObjectOutputStream objOutStr = null;
                try {
                    fileStr = new FileOutputStream(outFile);
                    bufStr = new BufferedOutputStream(fileStr);
                    objOutStr = new ObjectOutputStream(bufStr);
                    T obj = null;
                    while ((obj = fileReader.getLeastVal()) != null) {
                        objOutStr.writeObject(obj);
                    }
                    objOutStr.flush();
                } finally {
                    try {
                        for (FileObjContainer fileObj : fileObjs) {
                            fileObj.close();
                        }
                    } catch (Throwable t) {
                    }
                    try {
                        if (fileStr != null) {
                            fileStr.close();
                        }
                        if (bufStr != null) {
                            bufStr.close();
                        }
                        if (objOutStr != null) {
                            objOutStr.close();
                        }
                    } catch (IOException e) {
                    }
                } // finally
            } // else
        } // if
    } // mergeFiles

    protected ArrayList<File> buildSortedFileList(File inFile) throws IOException, ClassNotFoundException {
        ArrayList<File> fileList = new ArrayList<File>();
        FileInputStream fileStr = null;
        BufferedInputStream bufStr = null;
        ObjectInputStream objStr = null;
        try {
            fileStr = new FileInputStream(inFile);
            File parentDir = inFile.getParentFile();
            bufStr = new BufferedInputStream(fileStr);
            objStr = new ObjectInputStream(bufStr);
            File tempFile = null;
            while ((tempFile = readAndSortBlock(bufStr, objStr, parentDir)) != null) {
                fileList.add(tempFile);
            }
        } finally {
            try {
                if (fileStr != null) {
                    fileStr.close();
                }
                if (bufStr != null) {
                    bufStr.close();
                }
                if (objStr != null) {
                    objStr.close();
                }
            } catch (IOException e) {
            }
        }
        return fileList;
    } // buildSortedFileList

    public void sortFile(File inFile, File outFile) throws ClassNotFoundException, IOException {
        ArrayList<File> fileList = buildSortedFileList(inFile);
        mergeFiles(fileList, outFile);
        for (File file : fileList) {
            file.delete(); // delete the temporary files
        }
    }

}