/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package reedSolomon;

import java.io.Closeable;
import java.io.FileNotFoundException;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Implements ReedSolomon code. Basic idea of class is to compute checksums to
 * already existing fragments. These checksums can be later used to restore
 * original files. All files must be of same size.
 *
 * This is fan in implementation of Reed-Solomon algorithm. All checksums are
 * calculated centraly and can be distributed to hosts later.
 *
 * @author Marcel Duris
 */
public class ReedSolomonLocal {

    /**
     * This method reads input streams from passed iterator to get bytes of data
     * which are in turn used to calculate checksum files written into output
     * streams from outputstream iterator. Default size of finite field of 2^16
     * is used.
     *
     * @param ins Iterable over inputstreams
     * @param outs Iterable over outputstreams
     * @param m number of checksums to calculate
     */
    public static void calculateChecksums(Iterable<InputStream> ins, Iterable<OutputStream> outs, int m) {
        calculateChecksums(ins, outs, m, 16);
    }

    /**
     * This method reads input streams from passed iterator to get bytes of data
     * which are in turn used to calculate checksum files written into output
     * streams from outputstream iterator. Size of finite field of 2^w is used,
     * where w is argument passed to function.
     *
     * @param ins Iterable over inputstreams
     * @param outs Iterable over outputstreams
     * @param m number of checksums to calculate
     * @param w used to set size of finite field
     */
    public static void calculateChecksums(Iterable<InputStream> ins, Iterable<OutputStream> outs, int m, int w) {

        iField f = new GaloisField(w);
        VandermondeMatrix vm = new VandermondeMatrix(w);
        Iterator<OutputStream> oit = outs.iterator();
        for (int i = 0; i < m; i++) {
            ArrayList<InputStream> lin = new ArrayList<InputStream>();
            for (InputStream in : ins) {
                lin.add(in);
            }
            OutputStream out = oit.next();
            calculateChecksumFile(lin, out, vm.getNextRow(), f);
            try {
                out.flush();
                out.close();
            } catch (IOException ex) {
                Logger.getLogger(ReedSolomonLocal.class.getName()).log(Level.SEVERE, null, ex);
            }
        }

    }

    /**
     * Calculates single checksum file. Every original file fragment is read and
     * and multiplied by one row of Vandermonde matrix in similar fassion like
     * multiplication of matrices is performed.
     *
     * @param size how long input files are
     * @param in array of input streams from which bytes of original files are read
     * @param out output stream into resulting checksum is written
     * @param VandermondeRow nth row of usual vandermonde matrix
     */
    private static void calculateChecksumFile(ArrayList<InputStream> in, OutputStream out, int[] VandermondeRow, iField f) {
        //System.out.println("Calculating fragment");
        try {
            while (true) {
                int sum = 0;
                for (int i = 0; i < in.size(); i++) {
                    int r = read(in.get(i));
                    if (r == -1) {
                        return;
                    }
                    sum = f.add(sum, f.multiply(VandermondeRow[i], r));
                }
                write(out, sum);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * This method reads input streams and if any of first n streams is missing,
     * it is calculated and written into corresponding outputstream.
     * 
     * @param ins
     * @param outs
     * @param n
     * @param m
     * @throws IOException
     */
    public static void recover(Iterable<InputStream> ins, Iterable<OutputStream> outs, int n, int m) throws Exception {
        recover(ins, outs, n, m, 16);
    }

    /**
     * This function takes up to n original file pieces and 
     * file checksums. If any of n original file pieces is missing, it is
     * restored. The function uses inverse matrix to compute missing files.
     *
     * @throws FileNotFoundException
     * @throws IOException
     */
    private static void recover(Iterable<InputStream> ins, Iterable<OutputStream> outs, int n, int m, int w) throws Exception {

        ArrayList<InputStream> available = new ArrayList<InputStream>();
        ArrayList<OutputStream> missing = new ArrayList<OutputStream>();
        int[][] A = new int[n][n];
        Iterator<InputStream> inIter = ins.iterator();
        Iterator<OutputStream> outIter = outs.iterator();
        VandermondeMatrix vm = new VandermondeMatrix(w);
        Matrix matrix = new Matrix(new GaloisField(w));

        //Get fragments of data available, build first rows of matrix from
        //identity matrix.
        for (int i = 0; i < n; i++) {
            InputStream in = inIter.next();
            OutputStream out = outIter.next();

            if (in != null) {
                available.add(in);
                A[available.size() - 1][i] = 1;
                missing.add(null);
            } else {
                missing.add(out);
            }
        }

        //Get as many checksums as necessary
        for (int i = 0; (i < m) && (available.size() < n); i++) {
            int[] vrow = vm.getNextRow();
            InputStream in = inIter.next();
            if (in != null) {
                available.add(in);
                System.arraycopy(vrow, 0, A[available.size() - 1], 0, n);
            }
        }

        if (available.size() < n) {
            throw new Exception("Not enough data to recover.");
        }

        // Get inverse matrix
        int[][] inv = matrix.eliminate(A);
        int[] E = new int[n];

        // Now we can recover bytes from every missing fragment.
        // At first we recover first byte of every fragment, then second...
        while (true) {

            for (int i = 0; i < n; i++) {
                E[i] = read(available.get(i));
            }

            if (E[0] == -1) {
                break; //Every file is of same size, if one is at the end, so are others.
            }

            int[] D = matrix.multiplyByVector(inv, E);

            for (int i = 0; i < n; i++) {
                if (missing.get(i) != null) {
                    write(missing.get(i), D[i]);
                }
            }
        }
        
        flushStreams(outs);
        closeStreams(outs);
        closeStreams(ins);
        
    }

    private static void closeStreams(Iterable<? extends Closeable> streams) {
        for (Closeable stream : streams) {
            if (stream != null) {
                try {
                    stream.close();
                } catch (IOException ex) {
                }
            }
        }
    }

    private static void flushStreams(Iterable<? extends Flushable> streams) {
        for (Flushable stream : streams) {
            if (stream != null) {
                try {
                    stream.flush();
                } catch (IOException ex) {
                }
            }
        }
    }

    /**
     * This method reads two bytes from input stream to get one 16 bit long
     * number. If end of stream is reached either one or zero bytes are read.
     * 
     * @param in input stream
     * @return one two bytes long number.
     * @throws IOException if problem while reading.
     */
    private static int read(InputStream in) throws IOException {
        int b0 = in.read();
        if (b0 == -1) {
            return -1;
        }
        int b1 = in.read();
        b1 = Math.max(0, b1);
        int bb = (b0 << 8) ^ b1;
        return bb;
    }

    /**
     * This method write 16 bites long number as two 8 bites long numbers into
     * output stream.
     *
     * @param out output stream
     * @param bb 16 bit number
     * @throws IOException if problem during writing is encountered
     */
    private static void write(OutputStream out, int bb) throws IOException {

        int b0 = bb >> 8;
        int b1 = b0 << 8 ^ bb;
        out.write(b0);
        out.write(b1);
    }
}
