// Decompiled by Jad v1.5.7f. Copyright 2000 Pavel Kouznetsov.
// Jad home page: http://www.geocities.com/SiliconValley/Bridge/8617/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Burst.java

package edu.drexel.cis.citespace.burst;

import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Burst
{
    class cell_type
    {

        double cost[];
        double total[];
        int prev[];
        int path;
        int min_rate_class;
        int candidate[];
        int end_candidate[];
        int mark[];
        int breakpt[];
        int subordinate[];
        double power[];
        double total_power[];

        public cell_type()
        {
            cost = new double[20];
            total = new double[20];
            prev = new int[20];
            candidate = new int[20];
            end_candidate = new int[20];
            mark = new int[20];
            breakpt = new int[20];
            subordinate = new int[20];
            power = new double[20];
            total_power = new double[20];
        }
    }

    class ep_type
    {

        int word_index;
        int start;
        int end;
        int length;
        int pre_delta;
        int max_gap;
        double pre_gap;
        double rate;
        double power;
        double total_power;
        double weight;
        double rate_value;
        double min_rate_value;
        int rate_class;
        int min_rate_class;
        int index_appearances;
        int instig;
        int subordinate;

        ep_type()
        {
        }
    }

    class wd_type
    {

        String value;
        int start;
        int end;
        double total_power;
        int bin[];

        public wd_type()
        {
            value = "";
            bin = new int[1000];
        }
    }

    class blk_type
    {

        String name;
        int denom;

        public blk_type()
        {
            name = "";
        }
    }


    double log_choose(int n, int k)
    {
        double val = 0.0D;
        for(int i = n; i > n - k; i--)
            val += Math.log(i);

        for(int i = 1; i <= k; i++)
            val -= Math.log(i);

        return val;
    }

    double binom_w(double prob, int k, int n)
    {
        if(prob >= 1.0D)
        {
            return 1000000D;
        } else
        {
            double x = log_choose(n, k) + (double)k * Math.log(prob) + (double)(n - k) * Math.log(1.0D - prob);
            x = -1D * x;
            return x;
        }
    }

    double fluid(double x, double y)
    {
        return x / y + Math.log(y);
    }

    double w(double x, double y)
    {
        return fluid(x, y);
    }

    void compute_states(int n)
    {
        char in_line[] = new char[300];
        char s[] = new char[300];
        int q = 0;
        cell_type tmp[] = new cell_type[n];
        for(int k = 0; k < n; k++)
            tmp[k] = new cell_type();

        cell = tmp;
        tmp = null;
        if(BINS != 1)
        {
            expected = (double)time_span / (double)(n + 1);
        } else
        {
            int bin_k = 0;
            int bin_n = 0;
            for(int i = 0; i < n; i++)
            {
                bin_k += entry[i];
                bin_n += bin_base[i];
            }

            if(bin_n == 0 || bin_k == 0)
                return;
            expected = (double)bin_n / (double)bin_k;
        }
        trans_cost = TRANS * Math.log(n + 1) - Math.log(DTRANS);
        if(trans_cost < 0.0D)
            trans_cost = 0.0D;
        if(BINS != 1 && expected < FAST)
        {
            f_levels = 0;
            return;
        }
        if(REL_OPT == 0)
        {
            f_levels = REL_LEVELS + 1;
            f_rate[f_levels - 1] = expected;
            f_rate[f_levels - 2] = expected / REL_BASE;
            for(int j = f_levels - 3; j >= 0; j--)
                f_rate[j] = f_rate[j + 1] / REL_INC;

        } else
        {
            f_rate[0] = FAST;
            f_levels = FAST_LEVELS;
            for(int j = 1; j < FAST_LEVELS; j++)
            {
                f_rate[j] = f_rate[j - 1] * FAST_INC;
                if(f_rate[j] < expected)
                    continue;
                f_levels = j;
                break;
            }

            f_rate[f_levels] = expected;
            f_levels++;
        }
        for(int k = 0; k < f_levels; k++)
            if(BINS == 1)
                o_rate[k] = f_rate[k];
            else
                o_rate[k] = f_rate[k] / 60D;

        for(int j = 0; j < n; j++)
        {
            cell[j] = new cell_type();
            cell[j].path = 0;
            for(int k = 0; k < f_levels; k++)
            {
                cell[j].candidate[k] = 0;
                cell[j].subordinate[k] = 0;
                cell[j].end_candidate[k] = 0;
                cell[j].mark[k] = 0;
                cell[j].breakpt[k] = 0;
                cell[j].power[k] = 0.0D;
                cell[j].total_power[k] = 0.0D;
                cell[j].cost[k] = 0.0D;
                cell[j].total[k] = 0.0D;
                cell[j].prev[k] = 0;
            }

        }

        for(int j = 0; j < n; j++)
            if(BINS != 1)
            {
                if(j == n - 1)
                    delta = last_time - entry[j];
                else
                    delta = entry[j + 1] - entry[j];
                if(delta < MIN_GAP)
                    delta = MIN_GAP;
                for(int k = 0; k < f_levels; k++)
                    cell[j].cost[k] = w(delta, f_rate[k]);

            } else
            {
                for(int k = 0; k < f_levels; k++)
                    cell[j].cost[k] = binom_w(1.0D / f_rate[k], entry[j], bin_base[j]);

            }

        for(int k = 0; k < f_levels; k++)
            cell[0].total[k] = cell[0].cost[k] + (double)(f_levels - 1 - k) * trans_cost;

        for(int j = 1; j < n; j++)
        {
            for(int k = 0; k < f_levels; k++)
            {
                double d = cell[j].cost[k] + cell[j - 1].total[0];
                q = 0;
                for(int m = 1; m < f_levels; m++)
                {
                    if(m > k && cell[j].cost[k] + cell[j - 1].total[m] + (double)(m - k) * trans_cost < d)
                    {
                        d = cell[j].cost[k] + cell[j - 1].total[m] + (double)(m - k) * trans_cost;
                        q = m;
                    }
                    if(m <= k && cell[j].cost[k] + cell[j - 1].total[m] < d)
                    {
                        d = cell[j].cost[k] + cell[j - 1].total[m];
                        q = m;
                    }
                }

                cell[j].total[k] = d;
                cell[j].prev[k] = q;
            }

        }

        for(int k = 0; k < f_levels; k++)
        {
            double d = cell[n - 1].total[0];
            q = 0;
            for(int m = 1; m < f_levels; m++)
                if(cell[n - 1].total[m] < d)
                {
                    d = cell[n - 1].total[m];
                    q = m;
                }

        }

        cell[n - 1].path = q;
        for(int j = n - 2; j >= 0; j--)
        {
            int x = cell[j + 1].prev[cell[j + 1].path];
            cell[j].path = x;
        }

        for(int k = cell[0].path; k < f_levels - 1; k++)
            cell[0].mark[k] = 1;

        for(int j = 1; j < n; j++)
        {
            for(int k = cell[j].path; k < cell[j - 1].path; k++)
                cell[j].mark[k] = 1;

        }

        for(int k = 0; k < f_levels - 1; k++)
            left_barrier[k] = -1;

        for(int j = 0; j < n; j++)
        {
            for(int k = 0; k < f_levels - 1; k++)
                if(cell[j].mark[k] == 1)
                    left_barrier[k] = j;

            for(int k = 0; k < cell[j].path; k++)
                if(left_barrier[k] >= 0)
                {
                    cell[left_barrier[k]].breakpt[k] = j;
                    cell[left_barrier[k]].candidate[k] = 1;
                    cell[j].end_candidate[k] = 1;
                    left_barrier[k] = -1;
                }

            for(int k = cell[j].path; k < f_levels - 1; k++)
                if(left_barrier[k] >= 0)
                {
                    cell[left_barrier[k]].power[k] += cell[j].cost[k + 1] - cell[j].cost[k];
                    cell[left_barrier[k]].total_power[k] += cell[j].cost[f_levels - 1] - cell[j].cost[k];
                }

        }

        for(int k = 0; k < f_levels - 1; k++)
            if(left_barrier[k] >= 0)
            {
                cell[left_barrier[k]].breakpt[k] = n - 1;
                cell[left_barrier[k]].candidate[k] = 1;
                cell[n - 1].end_candidate[k] = 1;
                left_barrier[k] = -1;
            }

        for(int j = 0; j < n - 1; j++)
        {
            int p = -1;
            q = -1;
            for(int k = 0; k < f_levels - 1; k++)
                if(cell[j].candidate[k] == 1)
                {
                    p = k;
                    if(q < 0)
                        q = k;
                }

            if(p >= 0)
            {
                cell[j].min_rate_class = q;
                for(int k = 0; k < p; k++)
                    if(cell[j].candidate[k] == 1)
                    {
                        cell[j].total_power[p] += cell[j].power[k];
                        cell[j].subordinate[k] = 1;