/*M///////////////////////////////////////////////////////////////////////////////////////
//
//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
//
//  By downloading, copying, installing or using the software you agree to this license.
//  If you do not agree to this license, do not download, install,
//  copy or use the software.
//
//
//                        Intel License Agreement
//                For Open Source Computer Vision Library
//
// Copyright (C) 2000, Intel Corporation, all rights reserved.
// Third party copyrights are property of their respective owners.
//
// Redistribution and use in source and binary forms, with or without modification,
// are permitted provided that the following conditions are met:
//
//   * Redistribution's of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//
//   * Redistribution's in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//
//   * The name of Intel Corporation may not be used to endorse or promote products
//     derived from this software without specific prior written permission.
//
// This software is provided by the copyright holders and contributors "as is" and
// any express or implied warranties, including, but not limited to, the implied
// warranties of merchantability and fitness for a particular purpose are disclaimed.
// In no event shall the Intel Corporation or contributors be liable for any direct,
// indirect, incidental, special, exemplary, or consequential damages
// (including, but not limited to, procurement of substitute goods or services;
// loss of use, data, or profits; or business interruption) however caused
// and on any theory of liability, whether in contract, strict liability,
// or tort (including negligence or otherwise) arising in any way out of
// the use of this software, even if advised of the possibility of such damage.
//
//M*/
#include "_cvaux.h"
#include "_cvvm.h"
#include <stdlib.h>
#include <assert.h>


/*======================================================================================*/

CvStatus
icvDynamicCorrespond( int *first,       /* first sequence of runs */
                      /* s0|w0|s1|w1|...|s(n-1)|w(n-1)|sn */
                      int first_runs,   /* number of runs */
                      int *second,      /* second sequence of runs */
                      int second_runs, int *first_corr, /* s0'|e0'|s1'|e1'|... */
                      int *second_corr )
{

    float Pd, Fi, S;
    float Occlusion;
    float *costTable;
    uchar *matchEdges;
    int prev;
    int curr;
    int baseIndex;
    int i, j;
    int i_1, j_1;
    int n;
    int l_beg, r_beg, l_end, r_end, l_len, r_len;
    int first_curr;
    int second_curr;
    int l_color, r_color;
    int len_color;
    float cost, cost1;
    float min1, min2, min3;
    float cmin;
    uchar cpath;
    int row_size;

    /* Test arguments for errors */

    if( (first == 0) ||
        (first_runs < 1) ||
        (second == 0) || (second_runs < 1) || (first_corr == 0) || (second_corr == 0) )

        return CV_BADFACTOR_ERR;


    Pd = 0.95f;
    Fi = (float) CV_PI;
    S = 1;

    Occlusion = (float) log( Pd * Fi / ((1 - Pd) * sqrt( fabs( (CV_PI * 2) * (1. / S) ))));

    costTable = (float *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( float ));

    if( costTable == 0 )
        return CV_OUTOFMEM_ERR;

    matchEdges = (uchar *)cvAlloc( (first_runs + 1) * (second_runs + 1) * sizeof( uchar ));

    if( matchEdges == 0 )
    {
        cvFree( &costTable );
        return CV_OUTOFMEM_ERR;
    }

    row_size = first_runs + 1;

    /* ============= Fill costTable ============= */

    costTable[0] = 0.0f;

    /* Fill upper line in the cost Table */

    prev = first[0];
    curr = 2;

    for( n = 0; n < first_runs; n++ )
    {

        l_end = first[curr];
        curr += 2;
        costTable[n + 1] = costTable[n] + Occlusion * (l_end - prev);
        prev = l_end;

    }                           /* for */

    /* Fill lefter line in the cost Table */

    prev = second[0];
    curr = 2;
    baseIndex = 0;

    for( n = 0; n < second_runs; n++ )
    {

        l_end = second[curr];
        curr += 2;
        costTable[baseIndex + row_size] = costTable[baseIndex] + Occlusion * (l_end - prev);
        baseIndex += row_size;
        prev = l_end;

    }                           /* for */

    /* Count costs in the all rest cells */

    first_curr = 0;
    second_curr = 0;

    for( i = 1; i <= first_runs; i++ )
    {
        for( j = 1; j <= second_runs; j++ )
        {

            first_curr = (i - 1) * 2;
            second_curr = (j - 1) * 2;

            l_beg = first[first_curr];
            first_curr++;
            l_color = first[first_curr];
            first_curr++;
            l_end = first[first_curr];
            l_len = l_end - l_beg + 1;

            r_beg = second[second_curr];
            second_curr++;
            r_color = second[second_curr];
            second_curr++;
            r_end = second[second_curr];
            r_len = r_end - r_beg + 1;

            i_1 = i - 1;
            j_1 = j - 1;

            if( r_len == l_len )
            {
                cost = 0;
            }
            else
            {

                if( r_len > l_len )
                {
                    cost = (float) (r_len * r_len - l_len * l_len) * (1 / (r_len * l_len));
                }
                else
                {
                    cost = (float) (l_len * l_len - r_len * r_len) * (1 / (r_len * l_len));
                }
            }                   /* if */

            len_color = r_color - l_color;

            cost1 = (float) ((len_color * len_color) >> 2);

            min2 = costTable[i_1 + j * row_size] + Occlusion * l_len;

            min3 = costTable[i + j_1 * row_size] + Occlusion * r_len;

            min1 = costTable[i_1 + j_1 * row_size] + cost + (float) cost1;

            if( min1 < min2 )
            {

                if( min1 < min3 )
                {
                    cmin = min1;
                    cpath = 1;
                }
                else
                {
                    cmin = min3;
                    cpath = 3;
                }               /* if */

            }
            else
            {

                if( min2 < min3 )
                {
                    cmin = min2;
                    cpath = 2;
                }
                else
                {
                    cmin = min3;
                    cpath = 3;
                }               /* if */

            }                   /* if */

            costTable[i + j * row_size] = cmin;
            matchEdges[i + j * row_size] = cpath;
        }                       /* for */
    }                           /* for */

    /* =========== Reconstruct the Path =========== */

    i = first_runs;
    j = second_runs;

    first_curr = i * 2 - 2;
    second_curr = j * 2 - 2;


    while( i > 0 && j > 0 )
    {

        /* Connect begins */
        switch (matchEdges[i + j * row_size])
        {

        case 1:                /* to diagonal */

            first_corr[first_curr] = second[second_curr];
            first_corr[first_curr + 1] = second[second_curr + 2];
            second_corr[second_curr] = first[first_curr];
            second_corr[second_curr + 1] = first[first_curr + 2];

            first_curr -= 2;
            second_curr -= 2;
            i--;
            j--;

            break;

        case 2:                /* to left */

            first_corr[first_curr] = second[second_curr + 2];
            first_corr[first_curr + 1] = second[second_curr + 2];

            first_curr -= 2;
            i--;

            break;

        case 3:                /* to up */

            second_corr[second_curr] = first[first_curr + 2];
            second_corr[second_curr + 1] = first[first_curr + 2];

            second_curr -= 2;
            j--;

            break;
        }                       /* switch */
    }                           /* while */

    /* construct rest of horisontal path if its need */
    while( i > 0 )
    {

        first_corr[first_curr] = second[second_curr + 2];       /* connect to begin */
        first_corr[first_curr + 1] = second[second_curr + 2];   /* connect to begin */

        first_curr -= 2;
        i--;

    }                           /* while */

    /* construct rest of vertical path if its need */
    while( j > 0 )
    {

        second_corr[second_curr] = first[first_curr + 2];
        second_corr[second_curr + 1] = first[first_curr + 2];

        second_curr -= 2;
        j--;

    }                           /* while */

    cvFree( &costTable );
    cvFree( &matchEdges );

    return CV_NO_ERR;
}                               /* icvDynamicCorrespond */


/*======================================================================================*/

static CvStatus
icvDynamicCorrespondMulti( int lines,   /* number of scanlines */
                           int *first,  /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
                           int *first_runs,     /* numbers of runs */
                           int *second, int *second_runs, int *first_corr,      /* s0'|e0'|s1'|e1'|... */
                           int *second_corr )
{
    CvStatus error;

    int currFirst;
    int currSecond;
    int currFirstCorr;
    int currSecondCorr;
    int n;

    /* Test errors */

    if( (lines < 1) ||
        (first == 0) ||
        (first_runs == 0) ||
        (second == 0) || (second_runs == 0) || (first_corr == 0) || (second_corr == 0) )
        return CV_BADFACTOR_ERR;

    currFirst = 0;
    currSecond = 0;
    currFirstCorr = 0;
    currSecondCorr = 0;

    for( n = 0; n < lines; n++ )
    {

        error = icvDynamicCorrespond( &(first[currFirst]),
                                      first_runs[n],
                                      &(second[currSecond]),
                                      second_runs[n],
                                      &(first_corr[currFirstCorr]),
                                      &(second_corr[currSecondCorr]) );

        if( error != CV_NO_ERR )
            return error;

        currFirst += first_runs[n] * 2 + 1;
        currSecond += second_runs[n] * 2 + 1;
        currFirstCorr += first_runs[n] * 2;
        currSecondCorr += second_runs[n] * 2;

    }

    return CV_NO_ERR;

}                               /* icvDynamicCorrespondMulti */


/*======================================================================================*/

/*F///////////////////////////////////////////////////////////////////////////////////////
//    Name: cvDynamicCorrespondMulti
//    Purpose: The functions 
//    Context:
//    Parameters:  
//
//    Notes:  
//F*/
CV_IMPL void
cvDynamicCorrespondMulti( int lines,    /* number of scanlines */
                          int *first,   /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
                          int *first_runs,      /* numbers of runs */
                          int *second, int *second_runs, int *first_corr,       /* s0'|e0'|s1'|e1'|... */
                          int *second_corr )
{
    CV_FUNCNAME( "cvDynamicCorrespondMulti" );
    __BEGIN__;

    IPPI_CALL( icvDynamicCorrespondMulti( lines,        /* number of scanlines */
                                          first,        /* s0|w0|s1|w1|...s(n-1)|w(n-1)|sn */
                                          first_runs,   /* numbers of runs */
                                          second, second_runs, first_corr,      /* s0'|e0'|s1'|e1'|... */
                                          second_corr ));
    __CLEANUP__;
    __END__;
}