Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

I wanted to compare two binary files using Longest Common Subsequence, but Java heap space error made me comparing the file every 2048 bytes. The problem occured when i wanted to return the value of bytes to my main program, i wanted to return over and over again without erasing the previous return. How to do recursive return?

My source code: public static byte[] Compare(byte[] x, byte[] y) {

    StringBuffer sb = new StringBuffer();
    int i, j;
    final int x_length = x.length;
    final int y_length = y.length;
    int n = 2048;
    int m = 2048;


    // D[i][j] = direction, L[i][j] = Length of LCS 
    int[][] D = new int[n + 1][m + 1];
    byte[][] L = new byte[n + 1][m + 1]; // { 1, 2, 3 }

    // D[i][0] = 0 for 0<=i<=n 
    // D[0][j] = 0 for  0<=j<=m 
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (x[i - 1] == y[j - 1]) {
                D[i][j] = D[i - 1][j - 1] + 1;
                L[i][j] = 1;
            } else if (D[i - 1][j] >= D[i][j - 1]) {
                D[i][j] = D[i - 1][j];
                L[i][j] = 2;
            } else {
                D[i][j] = D[i][j - 1];
                L[i][j] = 3;
            }
        }
    }

    // Backtrack 
    ByteArrayOutputStream lcs = new ByteArrayOutputStream();
    i = n;  
    j = m;
    while (i != 0 && j != 0) {
        switch (L[i][j]) {
            case 1:   // diagonal 
                lcs.write(x[i - 1]); // Unreversed LCS
                --i;
                --j;
                break;
            case 2:  // up 
                --i;
                break;
            case 3:  // backward 
                --j;
                break;
        }
    }
    byte[] result = lcs.toByteArray();

    // Reverse:
    for (i = 0, j = result.length - 1; i < j; ++i, --j) {
        byte b = result[i];
        result[i] = result[j];
        result[j] = b;
    }
    //return result; << I want to return the initial result

    //While not end of file
    while(n < x_length && m < y_length){
        if(n+2048 < x.length){
            n = n+2048;
        } else {
            n = x.length;
        }

        if(m+2048 < y.length){
            m = m+2048;
        } else {
            m = y.length;
        }

    // D[i][j] = direction, L[i][j] = Length of LCS 
    int[][] D_new = new int[n + 1][m + 1];
    byte[][] L_new = new byte[n + 1][m + 1]; // { 1, 2, 3 }

    // D[i][0] = 0 for 0<=i<=n 
    // D[0][j] = 0 for  0<=j<=m 
    for (i = i+2048; i <= n; i++) {
        for (j = j+2048; j <= m; j++) {
            if (x[i - 1] == y[j - 1]) {
                D_new[i][j] = D_new[i - 1][j - 1] + 1;
                L_new[i][j] = 1;
            } else if (D_new[i - 1][j] >= D_new[i][j - 1]) {
                D_new[i][j] = D_new[i - 1][j];
                L_new[i][j] = 2;
            } else {
                D_new[i][j] = D_new[i][j - 1];
                L_new[i][j] = 3;
            }
        }
    }

    // Backtrack 
    ByteArrayOutputStream lcs_next = new ByteArrayOutputStream();
    i = n;  
    j = m;
    while (i != 0 && j != 0) {
        switch (L[i][j]) {
            case 1:   // diagonal 
                lcs_next.write(x[i - 1]); // Unreversed LCS
                --i;
                --j;
                break;
            case 2:  // up 
                --i;
                break;
            case 3:  // backward 
                --j;
                break;
        }
    }
    byte[] result_new = lcs_next.toByteArray();

    // Reverse:
    for (i = 0, j = result_new.length - 1; i < j; ++i, --j) {
        byte b = result_new[i];
        result_new[i] = result_new[j];
        result_new[j] = b;
    }

    lcs_next.reset();
    //return result_new; << appending the result

}
}
share|improve this question
    
You don't need a return. You need a callback for notifying the caller of results found. –  Fildor yesterday
    
Where's the recursion; am I missing it? –  Chief Two Pencils yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.