/* FREQ.C - PROCEDURES FOR MAINTAINING FREQUENCIES. */

#include <stdio.h>

#include "code.h"
#include "freq.h"


/* INITIALIZE FREQUENCIES.  Sets all the counts to one. */

void initialize_frequencies
(   frequencies *f		/* Structure holding frequencies            */
)
{   
    int i;

    for (i = 0; i<No_of_symbols; i++) {		/* Set up tables that       */
        f->symbol_to_index[i] = i+1;		/* translate between symbol */
        f->index_to_symbol[i+1] = i;		/* indexes and symbols.     */
    }

    f->cum_freq[No_of_symbols] = 0;
    for (i = No_of_symbols; i>0; i--) {		/* Set initial frequencies  */
        f->freq[i] = 1;				/* to all be one.           */
        f->cum_freq[i-1] = f->cum_freq[i] + f->freq[i];	
    }

    f->freq[0] = 0;				/* Freq[0] must not be the  */
						/* same as freq[1].         */
}


/* UPDATE THE FREQUENCIES TO COUNT ANOTHER SYMBOL.  Increments the frequency
   of the symbol (given by its index), swaps symbols as necessary to keep 
   them sorted by decreasing frequency, and scales down frequencies if they 
   are too big. */

void update_frequencies
(   frequencies *f,		/* Structure holding frequencies            */
    int index			/* Index of new symbol                      */
)
{   
    int sym_i, sym_index;	/* Temporaries for exchanging symbols       */
    int i;

    for (i = index; f->freq[i]==f->freq[i-1]; i--) ;   /* Find new index.   */

    if (i<index) {
        sym_i = f->index_to_symbol[i];		/* Update the translation   */
        sym_index = f->index_to_symbol[index];	/* tables if the symbol has */
        f->index_to_symbol[i] = sym_index;	/* moved.                   */
        f->index_to_symbol[index] = sym_i;
        f->symbol_to_index[sym_i] = index;
        f->symbol_to_index[sym_index] = i;
    }

    f->freq[i] += 1;				/* Increment the frequency  */
    while (i>0) {				/* count for the symbol and */
        i -= 1;					/* update the cumulative    */
        f->cum_freq[i] += 1;			/* frequencies.             */
    }

    if (f->cum_freq[0]>Freq_full) {		/* See if frequency counts  */
        f->cum_freq[No_of_symbols] = 0;		/* are past their maximum.  */
        for (i = No_of_symbols; i>0; i--) {	/* If so, halve all counts  */
            f->freq[i] = (f->freq[i]+1) >> 1;	/* (keeping them non-zero). */
            f->cum_freq[i-1] = f->cum_freq[i] + f->freq[i]; 
        }
    }
}