// Decompiled by DJ v3.5.5.77 Copyright 2003 Atanas Neshkov  Date: 2003-6-23 11:13:43
// Home Page : http://members.fortunecity.com/neshkov/dj.html  - Check often for new version!
// Decompiler options: packimports(3) 
// Source File Name:   Diff.java

package com.struts2.framework.util;

import java.util.Hashtable;

public class Diff
{
    public static class change
    {

        public change link;
        public final int inserted;
        public final int deleted;
        public final int line0;
        public final int line1;

        change(int line0, int line1, int deleted, int inserted, change old)
        {
            this.line0 = line0;
            this.line1 = line1;
            this.inserted = inserted;
            this.deleted = deleted;
            link = old;
        }
    }

    class file_data
    {

        void clear()
        {
            changed_flag = new boolean[buffered_lines + 2];
        }

        int[] equivCount()
        {
            int equiv_count[] = new int[equiv_max];
            for(int i = 0; i < buffered_lines; i++)
                equiv_count[equivs[i]]++;

            return equiv_count;
        }

        void discard_confusing_lines(file_data f)
        {
            clear();
            byte discarded[] = discardable(f.equivCount());
            filterDiscards(discarded);
            discard(discarded);
        }

        private byte[] discardable(int counts[])
        {
            int end = buffered_lines;
            byte discards[] = new byte[end];
            int equivs[] = this.equivs;
            int many = 5;
            for(int tem = end / 64; (tem >>= 2) > 0;)
                many *= 2;

            for(int i = 0; i < end; i++)
                if(equivs[i] != 0)
                {
                    int nmatch = counts[equivs[i]];
                    if(nmatch == 0)
                        discards[i] = 1;
                    else
                    if(nmatch > many)
                        discards[i] = 2;
                }

            return discards;
        }

        private void filterDiscards(byte discards[])
        {
            int end = buffered_lines;
            for(int i = 0; i < end; i++)
                if(discards[i] == 2)
                    discards[i] = 0;
                else
                if(discards[i] != 0)
                {
                    int provisional = 0;
                    int j;
                    for(j = i; j < end; j++)
                    {
                        if(discards[j] == 0)
                            break;
                        if(discards[j] == 2)
                            provisional++;
                    }

                    while(j > i && discards[j - 1] == 2) 
                    {
                        discards[--j] = 0;
                        provisional--;
                    }
                    int length = j - i;
                    if(provisional * 4 > length)
                    {
                        while(j > i) 
                            if(discards[--j] == 2)
                                discards[j] = 0;
                    } else
                    {
                        int minimum = 1;
                        for(int tem = length / 4; (tem >>= 2) > 0;)
                            minimum *= 2;

                        minimum++;
                        j = 0;
                        int consec = 0;
                        for(; j < length; j++)
                            if(discards[i + j] != 2)
                                consec = 0;
                            else
                            if(minimum == ++consec)
                                j -= consec;
                            else
                            if(minimum < consec)
                                discards[i + j] = 0;

                        j = 0;
                        consec = 0;
                        for(; j < length; j++)
                        {
                            if(j >= 8 && discards[i + j] == 1)
                                break;
                            if(discards[i + j] == 2)
                            {
                                consec = 0;
                                discards[i + j] = 0;
                            } else
                            if(discards[i + j] == 0)
                                consec = 0;
                            else
                                consec++;
                            if(consec == 3)
                                break;
                        }

                        i += length - 1;
                        j = 0;
                        consec = 0;
                        for(; j < length; j++)
                        {
                            if(j >= 8 && discards[i - j] == 1)
                                break;
                            if(discards[i - j] == 2)
                            {
                                consec = 0;
                                discards[i - j] = 0;
                            } else
                            if(discards[i - j] == 0)
                                consec = 0;
                            else
                                consec++;
                            if(consec == 3)
                                break;
                        }

                    }
                }

        }

        private void discard(byte discards[])
        {
            int end = buffered_lines;
            int j = 0;
            for(int i = 0; i < end; i++)
                if(no_discards || discards[i] == 0)
                {
                    undiscarded[j] = equivs[i];
                    realindexes[j++] = i;
                } else
                {
                    changed_flag[1 + i] = true;
                }

            nondiscarded_lines = j;
        }

        void shift_boundaries(file_data f)
        {
            boolean changed[] = changed_flag;
            boolean other_changed[] = f.changed_flag;
            int i = 0;
            int j = 0;
            int i_end = buffered_lines;
            int preceding = -1;
            int other_preceding = -1;
            do
            {
                while(i < i_end && !changed[1 + i]) 
                {
                    while(other_changed[1 + j++]) 
                        other_preceding = j;
                    i++;
                }
                if(i != i_end)
                {
                    int start = i;
                    int other_start = j;
                    do
                    {
                        while(i < i_end && changed[1 + i]) 
                            i++;
                        int end = i;
                        if(end == i_end || equivs[start] != equivs[end] || other_changed[1 + j] || end == i_end || preceding >= 0 && start == preceding || other_preceding >= 0 && other_start == other_preceding)
                            break;
                        changed[1 + end++] = true;
                        changed[1 + start++] = false;
                        i++;
                        j++;
                    } while(true);
                    preceding = i;
                    other_preceding = j;
                } else
                {
                    return;
                }
            } while(true);
        }

        final int buffered_lines;
        private final int equivs[];
        final int undiscarded[];
        final int realindexes[];
        int nondiscarded_lines;
        boolean changed_flag[];

        file_data(Object data[], Hashtable h)
        {
            buffered_lines = data.length;
            equivs = new int[buffered_lines];
            undiscarded = new int[buffered_lines];
            realindexes = new int[buffered_lines];
            for(int i = 0; i < data.length; i++)
            {
                Integer ir = (Integer)h.get(data[i]);
                if(ir == null)
                    h.put(data[i], new Integer(equivs[i] = equiv_max++));
                else
                    equivs[i] = ir.intValue();
            }

        }
    }


    private int diag(int xoff, int xlim, int yoff, int ylim)
    {
        int fd[] = fdiag;
        int bd[] = bdiag;
        int xv[] = xvec;
        int yv[] = yvec;
        int dmin = xoff - ylim;
        int dmax = xlim - yoff;
        int fmid = xoff - yoff;
        int bmid = xlim - ylim;
        int fmin = fmid;
        int fmax = fmid;
        int bmin = bmid;
        int bmax = bmid;