//*******************************************************************
//*                                                                 *
//*  File Name:       homophonic.cpp                                *
//*  Project:         Cryptology Programming Project #3             *
//*  Author:          Richard Kernan                                *
//*  Date:            01/21/01                                      *
//*                                                                 *
//*******************************************************************
//*                                                                 *
//*  File Description:                                              *
//*  This file contains the method definitions for the homophonic   *
//*  class.  This class allows for the computation, access, and     *
//*  manipulation of data retrieved from a homophonic ciphertext    *
//*  file.                                                          *
//*                                                                 *
//*  There are 3 files needed to build this project:                *
//*     1)  h_substitution.cpp  (this has "main")                   *
//*     2)  homophonic.cpp      (this file)                         *
//*     3)  homophonic.H                                            *
//*                                                                 *
//*  To compile this project with a specific executable file name,  *
//*     type the following (replace <exec_name> with the name that  *
//*     you want for you executable file).                          *
//*                                                                 *
//*  CC -o <exec_name> h_sustitution.cpp homophonic.cpp             *
//*                                                                 *
//*  Note "CC" is in capital letters.  This invokes the C++         *
//*  compiler.  "cc" (lower-case) WILL NOT WORK.  This is a plain   *
//*  C compiler.                                                    *
//*                                                                 *
//*  I suggest that you DO NOT try to compile this project using    *
//*  the GNU compiler "gcc".  This project uses the C++ Standard    *
//*  Template Library, and gcc has a very strange way of dealing    *
//*  with templates.                                                *
//*                                                                 *
//*******************************************************************


#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include "homophonic.H"


using namespace std;



//*******************************************************************
//*                                                                 *
//*  METHOD:     homophonic constructor                             *
//*                                                                 *
//*******************************************************************
homophonic::homophonic()
{
    _size = 0;
    _char_count = 0;
    _num_char_count = 0;
    _lowest_changed = -1;
    _ciphertext = NULL;
    _plaintext  = NULL;
    _undo.reserve( 10 );
}



//*******************************************************************
//*                                                                 *
//*  METHOD:     homophonic copy constructor                        *
//*                                                                 *
//*******************************************************************
homophonic::homophonic( const homophonic &rhs )
{
    *this = rhs;
}



//*******************************************************************
//*                                                                 *
//*  METHOD:     homophonic destructor                              *
//*                                                                 *
//*******************************************************************
homophonic::~homophonic()
{
    for( int i = 0; i < _undo.size(); i++ )
    {
        if( _undo[i] != NULL )
            delete _undo[i];
    }

    if( _plaintext != NULL )
        delete [] _plaintext;

    if( _ciphertext != NULL )
        delete [] _ciphertext;
}



//*******************************************************************
//*                                                                 *
//*  METHOD:     operator=( const homophonic & )                    *
//*  PURPOSE:    To make the lhs homophonic object the same as the  *
//*              rhs homophonic object.                             *
//*  ARGUMENTS:  This function takes a constant reference to a      *
//*              homophonic object.                                 *
//*  RETURNS:    A constant reference to a homophonic object.       *
//*  NOTES:      None.                                              *
//*                                                                 *
//*******************************************************************
const homophonic & homophonic::operator=( const homophonic &rhs )
{
    if( this != &rhs )
    {
        // Free the old memory
        for( int i = 0; i < _undo.size(); i++ )
        {
            if( _undo[i] != NULL )
                delete _undo[i];
        }
        _undo.clear();
        
        delete [] _plaintext;
        delete [] _ciphertext;
        
        _size = rhs._size;
        _char_count = rhs._char_count;
        _num_char_count = rhs._num_char_count;
        _lowest_changed = rhs._lowest_changed;
        
        number *n = NULL;
        _undo.reserve( rhs._undo.capacity() );
        
        // Copy the "undo" vector
        for( i = 0; i < rhs._undo.size(); i++ )
        {
            n = new number;
            if( n == NULL )
            {
                fprintf( stderr, "Memory Allocation Failure in homophonic::operator=\n" );
                fprintf( stderr, "Program terminated!\n\n" );
                exit( 1 );
            }
            
            n->num_char = rhs._undo[i]->num_char;
            n->changed  = rhs._undo[i]->changed;
            n->start_newline = rhs._undo[i]->start_newline;
            
            _undo.push_back( n );
        }
        
        // Allocate memory for the text
        _ciphertext = new char[_size];
        _plaintext  = new number[_num_char_count];
        
        if( _ciphertext == NULL || _plaintext == NULL )
        {
            fprintf( stderr, "Memory Allocation Failure in homophonic::operator=\n" );
            fprintf( stderr, "Program terminated!\n\n" );
            exit( 1 );
        }
        
        // Copy the ciphertext and plaintext
        for( i = 0; i < _size; i++ )
            _ciphertext[i] = rhs._ciphertext[i];
        
        for( i = 0; i < _num_char_count; i++ )
        {
            _plaintext[i].num_char = rhs._plaintext[i].num_char;
            _plaintext[i].changed  = rhs._plaintext[i].changed;
        }
    }
    
    return *this;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     num_freq( std::string ) const                      *
//*  PURPOSE:    To report the number of times that a number (or a  *
//*              character) appears in the text.                    *
//*  ARGUMENTS:  A std::string that is the number or character      *
//*              whose frequency is to be determined.               *
//*  RETURNS:    An integer which is the frequency of the number    *
//*              (or character).                                    *
//*  NOTES:      A group of numeric digits (perhaps starting with   *
//*              a negative sign) in the file that are not          *
//*              separated by whitespace will be taken as a single  *
//*              number.                                            *
//*                                                                 *
//*******************************************************************
int homophonic::num_freq( std::string n ) const
{
    if( _plaintext == NULL || _num_char_count < 1 )
            return 0;
    
    int count = 0;
    
    // For each character in the plaintext...
    for( int i = 0; i < _num_char_count; i++ )
    {
        // See if the character in the string
        // matches the given character.
        if( _plaintext[i].num_char == n )
            count++;
    }
    
    return count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     num_percent( std::string ) const                   *
//*  PURPOSE:    To report the percentage of occurrences of a given *
//*              number (or character).                             *
//*  ARGUMENTS:  A std::string that is the number (or character)    *
//*              whose percentage of occurrences is to be           *
//*              determined.                                        *
//*  RETURNS:    A floating point number 0.0 <= n <= 1.0 that       *
//*              represents the percentage.                         *
//*  NOTES:      If you already know the character's frequency, it  *
//*              is faster to calculate the percent by dividing     *
//*              that number by the value returned by "get_size"    *
//*              than to call this method.                          *
//*                                                                 *
//*******************************************************************
float homophonic::num_percent( std::string n ) const
{
    if( _plaintext == NULL || _num_char_count < 1 )
        return 0.0;
    
    // Divide the frequency by the 
    // number of characters in the text
    int freq = num_freq( n );
    return ((float)freq / _num_char_count) * 100;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     neighbor( number, std::string, int ) const         *
//*  PURPOSE:    To report the number of times the plaintext        *
//*              "number" n1 is a neighbor of n2.                   *
//*  ARGUMENTS:  A "number" which is from the plaintext and a       *
//*              std::string that may or may not be in the          *
//*              plaintext.  The third argument determines          *
//*              whether c2 must appear before or after c1 (or both)*
//*              Valid arguments are H_BEFORE, H_AFTER, H_BOTH.     *
//*  RETURNS:    The number of times n1 is next to n2 in the        *
//*              plaintext.                                         *
//*  NOTES:      An example of the meaning of "neighbor" is on      *
//*              page 22 of the book "The Code Book" by Simon Singh *
//*                                                                 *
//*              Since the numbers are stored as strings, non-      *
//*              numeric strings can also be tested with this       *
//*              method.                                            *
//*                                                                 *
//*******************************************************************
int homophonic::neighbor( number n1, std::string n2, int side ) const
{
    if( _plaintext == NULL || _num_char_count < 2 )
        return 0;

    int count = 0;

    for( int i = 0; i < _num_char_count; i++ )
    {
        // For each occurrence of c1 in the plaintext
        // Check if it is next to c2
        if( _plaintext[i].num_char == n1.num_char )
        {
            if( i > 0 && (side == H_BOTH || side == H_BEFORE) )
            {
                // If c2 is before c1...
                if( _plaintext[i - 1].num_char == n2 )
                    count++;
            }
            if( i < (_num_char_count - 1) && (side == H_BOTH || side == H_AFTER) )
            {
                // If c2 is after c1...
                if( _plaintext[i + 1].num_char == n2 )
                    count++;
            }
        }
    }

    return count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     neighbor( std::string, std::string, int ) const    *
//*  PURPOSE:    To report the number of times the plaintext        *
//*              string n1 is a neighbor of n2.                     *
//*  ARGUMENTS:  A std::string which is from the plaintext and a    *
//*              std::string that may or may not be in the          *
//*              plaintext.  The third argument determines          *
//*              whether c2 must appear before or after c1 (or both)*
//*              Valid arguments are H_BEFORE, H_AFTER, H_BOTH.     *
//*  RETURNS:    The number of times n1 is next to n2 in the        *
//*              plaintext.                                         *
//*  NOTES:      An example of the meaning of "neighbor" is on      *
//*              page 22 of the book "The Code Book" by Simon Singh *
//*                                                                 *
//*              Since the numbers are stored as strings, non-      *
//*              numeric strings can also be tested with this       *
//*              method.                                            *
//*                                                                 *
//*******************************************************************
int homophonic::neighbor( std::string n1, std::string n2,
                          int side ) const
{
    if( _plaintext == NULL || _num_char_count < 2 )
        return 0;

    int count = 0;

    for( int i = 0; i < _num_char_count; i++ )
    {
        // For each occurrence of c1 in the plaintext
        // Check if it is next to c2
        if( _plaintext[i].num_char == n1 )
        {
            if( i > 0 && (side == H_BOTH || side == H_BEFORE) )
            {
                // If c2 is before c1...
                if( _plaintext[i - 1].num_char == n2 )
                    count++;
            }
            if( i < (_num_char_count - 1) && (side == H_BOTH || side == H_AFTER) )
            {
                // If c2 is after c1...
                if( _plaintext[i + 1].num_char == n2 )
                    count++;
            }
        }
    }

    return count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     get_size() const                                   *
//*  PURPOSE:    To report the number of numbers or characters in   *
//*              the text.                                          *
//*  ARGUMENTS:  None.                                              *
//*  RETURNS:    The number of numbers or characters in the text.   *
//*  NOTES:      If you already know a number's frequency, it is    *
//*              faster to calculate the percentage by dividing     *
//*              that number by the number returned by this method  *
//*              than to call "num_percent".  b                     *
//*                                                                 *
//*******************************************************************
int homophonic::get_size() const
{
    return _size;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     get_non_white_size() const                         *
//*  PURPOSE:    To report the number of individual characters in   *
//*              the text.                                          *
//*  ARGUMENTS:  None.                                              *
//*  RETURNS:    The number of non-whitespace numbers or characters *
//*              in the text.                                       *
//*  NOTES:      If you already know a number's frequency, it is    *
//*              faster to calculate the percentage by dividing     *
//*              that number by the number returned by this method  *
//*              than to call "num_percent".                        *
//*                                                                 *
//*******************************************************************
int homophonic::get_non_white_size() const
{
    return _char_count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     get_num_char_size() const                          *
//*  PURPOSE:    To report the number of numbers or characters in   *
//*              the text.                                          *
//*  ARGUMENTS:  None.                                              *
//*  RETURNS:    The number of non-whitespace numbers or characters *
//*              in the text.                                       *
//*  NOTES:      If you already know a number's frequency, it is    *
//*              faster to calculate the percentage by dividing     *
//*              that number by the number returned by this method  *
//*              than to call "num_percent".                        *
//*                                                                 *
//*******************************************************************
int homophonic::get_num_char_size() const
{
    return _num_char_count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     print_soc_idx_table( int ) const                   *
//*  PURPOSE:    To print a table that shows the social index of    *
//*              one or more numbers or characters.                 *
//*  ARGUMENTS:  An integer, n, which indicates that the "n" most   *
//*              frequent numbers should be printed in the table.   *
//*  RETURNS:    Nothing.                                           *
//*  NOTES:      The social index for this method is number of      *
//*              times in the ciphertext that a character is the    *
//*              neighbor of each other character.                  *
//*              An example of this table is on page 22 of the      *
//*              book "The Code Book" by Simon Singh.               *
//*                                                                 *
//*******************************************************************
void homophonic::print_soc_idx_table( int n_most_freq ) const
{
    if( _plaintext == NULL || _num_char_count < 1 || n_most_freq < 1 )
        return;

    // Create a vector of all numbers in the 
    // plaintext.
    vector<frequency*> nums;
    nums.reserve( 100 );
    bool skip = false;
    int i = 0;
    
    // Get a list of one of each number or
    // character in the text.
    for( i = 0; i < _num_char_count; i++ )
    {
        skip = false;
        if( nums.capacity() == nums.size() )
            nums.reserve( nums.capacity() + 20 );
        
        for( int j = 0; j < nums.size(); j++ )
        {
            if( _plaintext[i].num_char == nums[j]->num.num_char )
            {
                skip = true;
                break;
            }
        }
        
        if( ! skip )
        {
            // create a "frequency" and insert it
            // into the vector in the correct order.
            frequency* fptr = new frequency;
            if( fptr == NULL )
            {
                fprintf( stderr, "\nMemory allocation failure in homophonic::print_soc_idx_table" );
                fprintf( stderr, "\nUnable to print table.\n\n" );
                return;
            }
            
            fptr->num.num_char = _plaintext[i].num_char;
            fptr->num.changed  = _plaintext[i].changed;
            fptr->freq = num_freq( _plaintext[i].num_char );
            
            if( nums.size() == nums.capacity() )
                nums.reserve( nums.capacity() + 20 );
            
            vector<frequency*>::iterator pos;
            
            for( int j = 0; j < nums.size(); j++ )
            {
                // Ordered from largest to smallest frequency
                if( nums[j]->freq <= fptr->freq )
                    break;
            }
            
            // Insert the the new frequency
            pos = find( nums.begin(), nums.end(), nums[j] );
            nums.insert( pos, fptr );
        }

    }  //  close  =>  for(i=0; i<_num_char_count; i++)
    
    int width = 80;
    int stop_point = 0;
    if( nums.size() < n_most_freq )
        stop_point = nums.size();
    else
        stop_point = n_most_freq;
    
    // Print the Header
    for( i = 0; i < width; i++ )
        fprintf( stdout, "=" );
    fprintf( stdout, "\n\n" );
    
    for( i = 0; i < ((width - 26) / 2); i++ )
        fprintf( stdout, " " );
    
    fprintf( stdout, "General Social Index Table\n\n" );
    
    int k = 0;
    int j = 0;
    while( k < nums.size() )
    {
        for( i = 0; i < width; i++ )
            fprintf( stdout, "=" );
        
        // Print the number headers
        fprintf( stdout, "\n         |" );
        
        j = k;
        
        int space_before = 0;
        int space_after = 0;

        for( i = 11; i < width; i = i + 10 )
        {
            space_before = ( 9 - nums[j]->num.num_char.size() ) / 2;
            space_after = 9 - space_before - nums[j]->num.num_char.size();

            for( int m = 0; m < space_before; m++ )
                fprintf( stdout, " " );

            fprintf( stdout, "%s", nums[j]->num.num_char.c_str() );

            for( m = 0; m < space_after; m++ )
                fprintf( stdout, " " );

            fprintf( stdout, "|" );

            j++;
            
            if( j >= nums.size() )
                break;
        }
        
        fprintf( stdout, "\n" );
        for( i = 0; i < width; i++ )
            fprintf( stdout, "=" );
        fprintf( stdout, "\n" );
        

        // Print the Body
        // For each character in "chars",
        // print the social index
        for( i = 0; i < stop_point; i++ )
        {
            // Print the number whose social index
            // will be calculated.
            // Print it in the center of its cell.
            space_before = ( 9 - nums[i]->num.num_char.size() ) / 2;
            space_after = 9 - space_before - nums[i]->num.num_char.size();

            j = k;

            for( int m = 0; m < space_before; m++ )
                fprintf( stdout, " " );

            fprintf( stdout, "%s", nums[i]->num.num_char.c_str() );

            for( m = 0; m < space_after; m++ )
                fprintf( stdout, " " );

            fprintf( stdout, "|" );

            // Print each of the social indices in
            // the center of their respective cells.
            for( m = 11; m < width; m = m + 10 )
            {
                int neighbor_val = neighbor( nums[i]->num, nums[j]->num.num_char );
                string neig_str = intToString( neighbor_val );

                space_before = ( 9 - neig_str.size() ) / 2;
                space_after = 9 - space_before - neig_str.size();

                for( int l = 0; l < space_before; l++ )
                    fprintf( stdout, " " );

                fprintf( stdout, "%d", neighbor_val );

                for( l = 0; l < space_after; l++ )
                    fprintf( stdout, " " );

                fprintf( stdout, "|" );

                j++;
                
                if( j >= nums.size() )
                    break;
            }
            
            fprintf( stdout, "\n" );
            for( m = 0; m < width; m++ )
                fprintf( stdout, "-" );
            fprintf( stdout, "\n" );
        }

        fprintf( stdout, "\n\n" );

        k = j;

    }  //  close  =>  while(k<nums.size())
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     print_freq_table() const                           *
//*  PURPOSE:    To print a table that details the frequency of     *
//*              each number or character in the ciphertext.        *
//*  ARGUMENTS:  None.                                              *
//*  RETURNS:    Nothing.                                           *
//*  NOTES:      The frequency table will show, for each number or  *
//*              character in the ciphertext, the number of         *
//*              occurences and the percentage frequency.           *
//*              An example of this table is on page 21 of the      *
//*              book "The Code Book" by Simon Singh.               *
//*                                                                 *
//*******************************************************************
void homophonic::print_freq_table() const
{
    // Create a vector of all numbers in the 
    // plaintext.
    vector<frequency*> nums;
    nums.reserve( 100 );
    bool skip = false;
    int i = 0;
    
    // Get a list of one of each number or
    // character in the text.
    for( i = 0; i < _num_char_count; i++ )
    {
        skip = false;
        if( nums.capacity() == nums.size() )
            nums.reserve( nums.capacity() + 20 );
        
        for( int j = 0; j < nums.size(); j++ )
        {
            if( _plaintext[i].num_char == nums[j]->num.num_char )
            {
                skip = true;
                break;
            }
        }
        
        if( ! skip )
        {
            // create a "frequency" and insert it
            // into the vector in the correct order.
            frequency* fptr = new frequency;
            if( fptr == NULL )
            {
                fprintf( stderr, "\nMemory allocation failure in homophonic::print_freq_table" );
                fprintf( stderr, "\nUnable to print table.\n\n" );
                return;
            }
            
            fptr->num.num_char = _plaintext[i].num_char;
            fptr->num.changed  = _plaintext[i].changed;
            fptr->freq = num_freq( _plaintext[i].num_char );
            
            if( nums.size() == nums.capacity() )
                nums.reserve( nums.capacity() + 20 );
            
            vector<frequency*>::iterator pos;
            
            for( int j = 0; j < nums.size(); j++ )
            {
                // Ordered from largest to smallest frequency
                if( nums[j]->freq <= fptr->freq )
                    break;
            }
            
            // Insert the the new frequency
            pos = find( nums.begin(), nums.end(), nums[j] );
            nums.insert( pos, fptr );
        }

    }  //  close  =>  for(i=0; i<_num_char_count; i++)
    
    int width = 32;
    int num_chars = nums.size();
    int row1 = 0;
    int row2 = 0;
    int line_count = 0;
    if( num_chars % 2 == 0 )
        row2 = num_chars / 2;
    else
        row2 = num_chars / 2 + 1;
    line_count = row2;
    
    
    // Print the Header
    fprintf( stdout, "\n" );
    for( i = 0; i < width; i++ )
        fprintf( stdout, "=" );
    fprintf( stdout, "     " );
    for( i = 0; i < width; i++ )
        fprintf( stdout, "=" );
    
    fprintf( stdout, "\nNumber" );
    fprintf( stdout, "%19s", "Frequency" );
    fprintf( stdout, "%18s", "Number" );
    fprintf( stdout, "%21s", "Frequency\n" );
    fprintf( stdout, "        " );
    for( i = 0; i < 24; i++ )
        fprintf( stdout, "-" );
    fprintf( stdout, "             " );
    for( i = 0; i < 24; i++ )
        fprintf( stdout, "-" );
    fprintf( stdout, "\n" );
    fprintf( stdout, "%19s", "Occurrences" );
    fprintf( stdout, "%13s", "Percentage" );
    fprintf( stdout, "%24s", "Occurrences" );
    fprintf( stdout, "%13s", "Percentage" );
    fprintf( stdout, "\n" );
    
    for( i = 0; i < width; i++ )
        fprintf( stdout, "-" );
    fprintf( stdout, "     " );
    for( i = 0; i < width; i++ )
        fprintf( stdout, "-" );
    fprintf( stdout, "\n" );
    
    for( i = 0; i < line_count; i++ )
    {
        fprintf( stdout, "%-10s%5d%14.2f", nums[row1]->num.num_char.c_str(),
            nums[row1]->freq, num_percent( nums[row1]->num.num_char ) );
        fprintf( stdout, "        " );
        
        if( row2 < num_chars )
            fprintf( stdout, "%-11s%5d%14.2f", nums[row2]->num.num_char.c_str(),
            nums[row2]->freq, num_percent( nums[row2]->num.num_char ) );
        fprintf( stdout, "\n" );
        row1++;
        row2++;
    }
    
    for( i = 0; i < width; i++ )
        fprintf( stdout, "=" );
    fprintf( stdout, "     " );
    for( i = 0; i < width; i++ )
        fprintf( stdout, "=" );
    fprintf( stdout, "\n\n" );
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     print_ngram_table( int )                           *
//*  PURPOSE:    To print a table that shows the number of          *
//*              occurrences of each "n-gram" in the ciphertext.    *
//*  ARGUMENTS:  An integer which is the number of numbers or       *
//*              characters in the "n-gram".                        *
//*              The value for "n" must be >= 2.                    *
//*  RETURNS:    Nothing.                                           *
//*  NOTES:      An "n-gram" is a set of "n" numbers or characters  *
//*              that occurs together in a given order.             *
//*              Example:  a "digram" would be a 2-gram, such as:   *
//*                 "th", "sh", "101 43", etc.                      *
//*              A trigram would be a 3-gram, such as:              *
//*                 "the", "and", "2753 12 781", etc.               *
//*                                                                 *
//*              This method finds all "n-grams" that appear at     *
//*              least twice in the ciphertext and prints a table   *
//*              to show the frequency of each such "n-gram".       *
//*                                                                 *
//*******************************************************************
void homophonic::print_ngram_table( int n ) const
{
    if( n >= _num_char_count || n < 2 )
    {
        fprintf( stdout, "%d-grams are not valid with the current file.\n", n );
        fprintf( stdout, "\"n\" must be >= 2 AND < %d\n", _num_char_count );
        return;
    }

    int count = 0;
    vector<ngram_index*> valid_ngrams;
    ngram_index *save_ngram = NULL;

    // Go through the text and check the frequency of each n-gram.
    for( int i = 0, j = n - 1; j < _num_char_count; i++, j++ )
    {
        // Count the number of occurrences
        // of each n-gram.
        count = get_ngram_count( i, j );

        // Save the indices and frequencies of the
        // n-grams that appear at least twice.
        if( count >= 2 )
        {
            bool already_saved = false;

            // Check if the n-gram has already been saved.
            // For each saved n-gram...
            for( int k = 0; k < valid_ngrams.size(); k++ )
            {
                already_saved = true;

                // For each "number" in the n-gram...
                // If they all match, then the n-gram is already saved.
                for( int m = i, n = valid_ngrams[k]->beginning; m <= j; m++, n++ )
                {
                    if( _plaintext[m].num_char == _plaintext[n].num_char )
                        continue;
                    else
                    {
                        already_saved = false;
                        break;
                    }
                }

                if( already_saved )
                    break;
            }

            // If the n-gram is not already saved,
            // then save it.
            if( ! already_saved )
            {
                save_ngram = new ngram_index;
                
                // Validate the memory allocation
                if( save_ngram == NULL )
                {
                    fprintf( stderr, "Memory allocation failure in homophonic::print_ngram_table\n" );
                    fprintf( stderr, "Unable to print %d-gram table\n", n );
                    
                    // Free any allocated memory
                    for( k = 0; k < valid_ngrams.size(); k++ )
                    {
                        if( valid_ngrams[k] != NULL )
                        {
                            delete valid_ngrams[k];
                            valid_ngrams[k] = NULL;
                        }
                    }
                    valid_ngrams.clear();
                    return;
                }
                
                save_ngram->beginning = i;
                save_ngram->end = j;
                save_ngram->count = count;

                if( valid_ngrams.size() == valid_ngrams.capacity() )
                    valid_ngrams.reserve( valid_ngrams.capacity() + 20 );

                vector<ngram_index*>::iterator pos;

                for( k = 0; k < valid_ngrams.size(); k++ )
                {
                    // Ordered from largest to smallest frequency
                    if( valid_ngrams[k]->count <= save_ngram->count )
                        break;
                }

                // Insert the ngram to be saved
                pos = find( valid_ngrams.begin(), valid_ngrams.end(),
				            valid_ngrams[k] );
                valid_ngrams.insert( pos, save_ngram );

            }  //  close  =>  if(!already_saved)

        }  //  close  =>  if(count>1)

    }  //  close  =>  for(int i=0, j=n-1; j<_num_char_count; i++, j++)
    

    // At this point we have a saved list of all n-grams
    // that appear in the text at least twice.


    // If there are n-grams to print,
    // then print them.
    if( ! valid_ngrams.empty() )
    {
        int width = 51;
        
        // Print the Header
        fprintf( stdout, "\n" );
        for( i = 0; i < width; i++ )
            fprintf( stdout, "=" );
        fprintf( stdout, "\n" );
        fprintf( stdout, "\n**********   " );
        if( n == 2 )
            fprintf( stdout, "\"DIGRAM\" FREQUENCY TABLE" );
        else if( n == 3 )
            fprintf( stdout, "\"TRIGRAM\" FREQUENCY TABLE" );
        else
            fprintf( stdout, "\"%d-GRAM\" FREQUENCY TABLE", n );
        
        fprintf( stdout, "   **********\n\n" );
        for( i = 0; i < width; i++ )
            fprintf( stdout, "-" );
        
        int prev_freq = -1;
        int curr_freq = 0;
        
        // For each saved n-gram...
        // print out the n-gram and its frequency.
        for( i = 0; i < valid_ngrams.size(); i++ )
        {
            // Print the header for each
            // frequency level.
            curr_freq = valid_ngrams[i]->count;
            if( valid_ngrams[i]->count != prev_freq )
            {
                fprintf( stdout, "\n" );
                for( int k = 0; k < width; k++ )
                    fprintf( stdout, "-" );
                if( n == 2 )
                    fprintf( stdout, "\n\tDIGRAMS WITH FREQUENCY: %d\n", curr_freq );
                else if( n == 3 )
                    fprintf( stdout, "\n\tTRIGRAMS WITH FREQUENCY: %d\n", curr_freq );
                else
                    fprintf( stdout, "\n\t%d-GRAMS WITH FREQUENCY: %d\n", n, curr_freq );
            }
            
            if( n == 2 )
                fprintf( stdout, "\n  DIGRAM = \"" );
            else if( n == 3 )
                fprintf( stdout, "\n  TRIGRAM = \"" );
            else
                fprintf( stdout, "\n  %d-GRAM = \"", n );
            
            // Print each element of the n-gram (separated by a space)
            for( int j = valid_ngrams[i]->beginning; j <= valid_ngrams[i]->end; j++ )
            {
                fprintf( stdout, "%s", _plaintext[j].num_char.c_str() );
                if( j < valid_ngrams[i]->end )
                    fprintf( stdout, " " );
            }
            fprintf( stdout, "\"" );
            prev_freq = curr_freq;
        }
        
        fprintf( stdout, "\n" );
        for( i = 0; i < width; i++ )
            fprintf( stdout, "=" );
        fprintf( stdout, "\n\n" );
        
    }  //  close  =>  if(!valid_ngrams.empty())
    
    else if( n > 3 )
        fprintf( stdout, "No %d-grams found with a frequency of at least 2\n", n );
    else if( n == 3 )
        fprintf( stdout, "No trigrams found with a frequency of at least 2\n" );
    else
        fprintf( stdout, "No digrams found with a frequency of at least 2\n" );
    
    // Free allocated memory
    for( i = 0; i < valid_ngrams.size(); i++ )
    {
        if( valid_ngrams[i] != NULL )
        {
            delete valid_ngrams[i];
            valid_ngrams[i] = NULL;
        }
    }
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     get_ngram_count( int, int )                        *
//*  PURPOSE:    To determine the number of occurrences of an       *
//*              ngram in the plaintext.                            *
//*  ARGUMENTS:  An integer which is the starting index of the      *
//*              ngram (from the plaintext) and an integer which is *
//*              the ending index of the ngram.                     *
//*  RETURNS:    An integer which is the number of occurrences of   *
//*              the n-gram, or -1 if either argument is invalid.   *
//*  NOTES:      An "n-gram" is a set of "n" numbers or characters  *
//*              that occurs together in a given order.             *
//*              Example:  a "digram" would be a 2-gram, such as:   *
//*                 "th", "sh", "101 43", etc.                      *
//*              A trigram would be a 3-gram, such as:              *
//*                 "the", "and", "2753 12 781", etc.               *
//*                                                                 *
//*              Valid arguments:                                   *
//*              start must be >= 0 and < (_num_char_count - 1)     *
//*              end must be >= 1 and > start and < _num_char_count *
//*                                                                 *
//*              This method is private.                            *
//*                                                                 *
//*******************************************************************
int homophonic::get_ngram_count( int start, int end ) const
{
    // Validate the input
    if( start < 0 || start >= _num_char_count - 1 ||
        end   < 1 ||   end >= _num_char_count     ||
        end   <= start )
        return -1;

    int count = 0;
    int idx_diff = end - start;
    bool found = false;

    // For each possible ngram in the text...
    for( int i = 0; i < (_num_char_count - idx_diff); i++ )
    {
        found = true;

        // For each "number" in the ngram...
        for( int j = i, s = start; j <= (i + idx_diff); j++, s++ )
        {
            if( _plaintext[j].num_char == _plaintext[s].num_char )
                continue;
            else
            {
                found = false;
                break;
            }
        }

        if( found )
            count++;
    }

    return count;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     print_txt() const                                  *
//*  PURPOSE:    To print the ciphertext or plaintext.              *
//*  ARGUMENTS:  H_CIPHERTEXT to print the ciphertext, or           *
//*              H_PLAINTEXT to print the plaintext.                *
//*  RETURNS:    Nothing.                                           *
//*  NOTES:      H_PLAINTEXT is the default value.                  *
//*                                                                 *
//*******************************************************************
void homophonic::print_txt( bool which ) const
{
    fprintf( stdout, "\n" );
    if( which == H_PLAINTEXT )
    {
        if( _plaintext == NULL )
            return;
        
        // For each number or character in the text...
        for( int i = 0; i < _num_char_count; i++ )
        {
            if( _plaintext[i].start_newline )
                fprintf( stdout, "\n" );
            fprintf( stdout,"%s ", _plaintext[i].num_char.c_str() );
        }
    }
    
    else  // which == H_CIPHERTEXT
    {
        if( _ciphertext == NULL )
            return;
        
        // For each character in the text...
        for( int i = 0; i < _size; i++ )
            fprintf( stdout, "%c", _ciphertext[i] );
    }
    fprintf( stdout, "\n" );
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     save() const                                       *
//*  PURPOSE:    To save the plaintext to a file.                   *
//*  ARGUMENTS:  A std::string which is the name of the file, and   *
//*              a boolean value which determines if the            *
//*  RETURNS:    true if successful, false otherwise.               *
//*  NOTES:      The default value for "write_ciphertext" is true.  *
//*                                                                 *
//*******************************************************************
bool homophonic::save( string filename, bool write_ciphertext ) const
{
    if( _plaintext == NULL || _num_char_count < 1 || filename.size() < 1 )
        return false;
    
    FILE *outfile = fopen( filename.c_str(), "w" );
    if( outfile == NULL )
        return false;
    
    
    if( write_ciphertext && _ciphertext != NULL )
    {
        fprintf( outfile, "\nCIPHERTEXT...\n\n" );
        // For each character in the text...
        for( int i = 0; i < _size; i++ )
            fprintf( outfile, "%c", _ciphertext[i] );
        
        fprintf( outfile, "\n\n\nPLAINTEXT...\n\n" );
    }
    
    // For each number or character in the text...
    for( int i = 0; i < _num_char_count; i++ )
    {
        if( _plaintext[i].start_newline )
            fprintf( outfile, "\n" );
        fprintf( outfile,"%s ", _plaintext[i].num_char.c_str() );
    }
    
    fclose( outfile );
    
    return true;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     load_file( const std::string filename )            *
//*  PURPOSE:    To load the ciphertext document from a file.       *
//*  ARGUMENTS:  A std::string that is the name of the file.        *
//*  RETURNS:    true on success, false otherwise.                  *
//*  NOTES:      It is the resposibility of the user to ensure that *
//*              the pointer is valid.  The only check that is      *
//*              done is for a NULL pointer.                        *
//*                                                                 *
//*******************************************************************
bool homophonic::load_file( const string filename )
{
    if( filename.size() < 1 )
        return false;
    
    FILE *infile = fopen( filename.c_str(), "r" );
    if( infile == NULL )
        return false;
    
    int c;
    int prev_c = ' ';
    _size = 0;
    _char_count = 0;
    
    // Count the number of characters in the file
    while( (c = fgetc( infile )) != EOF )
    {
        _size++;
        
        if( ! isspace( c ) )
            _char_count++;

        if( isdigit( c ) && ! isdigit( prev_c ) )
            _num_char_count++;

        else if( ! isspace( c ) && ! isdigit( c ) &&
                 isgraph( c ) && c != '-' )
            _num_char_count++;

        else if( prev_c == '-' && ! isdigit( c ) )
            _num_char_count++;

        prev_c = c;
    }
    
    if( _char_count < 1 )
    {
        fclose( infile );
        return false;
    }

    // Allocate the memory for the text
    _ciphertext = new char[_size];
    _plaintext = new number[_num_char_count];
    
    if( _plaintext == NULL || _ciphertext == NULL )
    {
        if( _ciphertext != NULL )
            free( _ciphertext );
        if( _plaintext != NULL )
            free( _plaintext );
        fclose( infile );
        return false;
    }
    
    int i = 0;
    int j = -1;
    char char_str[3];
    bool newline = false;
    rewind( infile );
    prev_c = ' ';
    
    // Read each line of the file into the arrays
    // and keep track of the number of characters
    while( (c = fgetc( infile )) != EOF )
    {
        // Dash by itself
        // Load as its own "number".
        if( prev_c == '-' && ! isdigit( c ) )
        {
            j++;
            char_str[0] = prev_c;
            char_str[1] = '\0';
            _plaintext[j].num_char += char_str;
            _plaintext[j].changed = -1;

            if( newline )
            {
                _plaintext[j].start_newline = true;
                newline = false;
            }
            else
                _plaintext[j].start_newline = false;
        }

        // New number
        // Load as a new "number"
        if( isdigit( c ) && ! isdigit( prev_c ) )
        {
            j++;
            int k = 0;

            if( prev_c == '-' )
            {
                char_str[k] = prev_c;
                k++;
            }

            char_str[k] = c;
            k++;
            char_str[k] = '\0';
            _plaintext[j].num_char += char_str;
            _plaintext[j].changed = -1;

            if( newline )
            {
                _plaintext[j].start_newline = true;
                newline = false;
            }
            else
                _plaintext[j].start_newline = false;
        }

        // Part of current number
        // Add to the current "number".
        else if( isdigit( c ) && isdigit( prev_c ) )
        {
            char_str[0] = c;
            char_str[1] = '\0';
            _plaintext[j].num_char += char_str;
        }

        // Single character
        // Load as its own "number".
        else if( ! isspace( c ) && ! isdigit( c ) &&
                 isgraph( c ) && c != '-' )
        {
            j++;
            char_str[0] = c;
            char_str[1] = '\0';
            _plaintext[j].num_char += char_str;
            _plaintext[j].changed = -1;

            if( newline )
            {
                _plaintext[j].start_newline = true;
                newline = false;
            }
            else
                _plaintext[j].start_newline = false;
        }

        // Save newline positions before dashes
        if( c == '\n' )
            newline = true;

        prev_c = c;
        _ciphertext[i] = c;
        
        i++;
    }
    
    fclose( infile );
    
    return true;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     substitute( std::string, std::string )             *
//*  PURPOSE:    To substitute a new character for an existing      *
//*              number or character in the ciphertext.             *
//*  ARGUMENTS:  Two std::string objects that represent the new     *
//*              character and the old character or number.         *
//*  RETURNS:    true on success, false otherwise.                  *
//*  NOTES:      Only the matching numbers or characters that have  *
//*              not been changed for the longest amount of time    *
//*              are changed.                                       *
//*              If the "old_num" does not exist in the ciphertext  *
//*              then this method returns false.                    *
//*                                                                 *
//*******************************************************************
bool homophonic::substitute( std::string new_char, std::string old_num )
{

    if( _plaintext == NULL || _num_char_count < 1 )
        return false;
    
    // If the characters are the same
    // (based on the case sensitivity of this object)
    // then do nothing.
    if( new_char == old_num )
        return true;
    
    number *undo = new number;
    if( undo == NULL )
        return false;
    
    int lowest = get_lowest_changed_value( old_num );
    
    bool found = false;
    
    // For each number in the text...
    for( int i = 0; i < _num_char_count; i++ )
    {
        // If the "old_num" is found, change
        // the number or character in the plaintext.
        // NOTE: if there are two numbers or characters
        // in the plaintext that match, only those
        // that have not been changed for the longest
        // time will be changed.
        if( ( _plaintext[i].num_char == old_num ) &&
            _plaintext[i].changed == lowest )
        {
            undo->num_char = _plaintext[i].num_char;
            undo->changed  = _plaintext[i].changed;
            undo->start_newline = _plaintext[i].start_newline;
            
            _plaintext[i].num_char = new_char;
            _plaintext[i].changed  = _lowest_changed + 1;
            
            found = true;
        }
    }
    
    if( ! found )
        return false;
    
    // If there are two numbers or characters
    // in the plaintext that match, decide
    // which ones have not been changed for
    // the longest time.
    // This is set for the "undo" method.
    _lowest_changed++;
    
    // Make sure there is enough space in the undo vector
    if( _undo.capacity() == _undo.size() )
        _undo.reserve( _undo.capacity() + 10 );
    
    // Save the character substitution
    _undo.push_back( undo );

    return true;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     undo_sub();                                        *
//*  PURPOSE:    To undo a character substitution.                  *
//*  ARGUMENTS:  None.                                              *
//*  RETURNS:    true on success, false otherwise.                  *
//*  NOTES:      This method will undo the previous character       *
//*              substitution.  This can be continued until all     *
//*              substitutions made have been "undone."  If this    *
//*              method is called after that point, it returns      *
//*              false.                                             *
//*                                                                 *
//*******************************************************************
bool homophonic::undo_sub()
{
    if( _plaintext == NULL || _num_char_count < 1 )
        return false;
    
    int sz = _undo.size() - 1;
    
    if( sz < 0 )
        return false;
    
    number *sub = _undo.back();
    if( sub == NULL )
        return false;
    
    // For each number or character in the text...
    for( int i = 0; i < _num_char_count; i++ )
    {
        // If the changed value of the character
        // matches the index of the last change
        // made, change it back.
        if( _plaintext[i].changed == _lowest_changed )
        {
            _plaintext[i].num_char = sub->num_char;
            _plaintext[i].changed  = sub->changed;
        }
    }
    
    // Delete the corresponding characters
    // from the vector
    delete sub;
    _undo[sz] = NULL;
    
    vector<number*>::iterator pos = _undo.end();
    --pos;
    _undo.erase( pos );
    _lowest_changed--;

    return true;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     get_lowest_changed_value( std::string )            *
//*  PURPOSE:    To determine the lowest changed value for the      *
//*              simple character c.                                *
//*  ARGUMENTS:  A simple character whose changed value is checked. *
//*  RETURNS:    An integer which is the lowest changed value for   *
//*              the simple character c.                            *
//*  NOTES:      This method is case sensitive only if the charsub  *
//*              object has been created to be case sensitive.      *
//*                                                                 *
//*              Return value is -2 if there is no text, or the     *
//*              character is not in the text.  Otherwise it is     *
//*              n - 1 (where n = the number of changes to the      *
//*              character).                                        *
//*                                                                 *
//*******************************************************************
int homophonic::get_lowest_changed_value( std::string num ) const
{
    if( _plaintext == NULL || _num_char_count < 1 )
        return -2;

    int low = -2;

    bool first = true;

    for( int i = 0; i < _num_char_count; i++ )
    {
        if( first )  // First character match found
        {
            // Set the changed value of the first match
            if( _plaintext[i].num_char == num )
            {
                low = _plaintext[i].changed;
                first = false;
            }
        }
        else  // Not the first match found
        {
            // If a subsequent match has a lower changed
            // value, set that value to the _lowest_change.
            if( ( _plaintext[i].num_char == num ) &&
                ( _plaintext[i].changed < low ) )
                low = _plaintext[i].changed;
        }
    }

    return low;
}




//*******************************************************************
//*                                                                 *
//*  METHOD:     intToString( long )                                *
//*  PURPOSE:    To change an integer value into a  string.         *
//*  ARGUMENTS:  An integer that will be returned as a string.      *
//*  RETURNS:    A string which represents the integer value passed *
//*              into the function.                                 *
//*  NOTES:      This function can handle integers up to 64 bits.   *
//*                                                                 *
//*              This method is private.                            *
//*                                                                 *
//*******************************************************************
string homophonic::intToString( long number ) const
{
   char str_reverse[22] = {'0'};
   string n_string;

   long temp_num = number;
   int char_num = 0;
   int i = 0;
   int j = 0;

   /*  Make temp_num positive  */
   if( number < 0 )
      temp_num *= -1;

   while( temp_num > 0 && i < 21 )
   {
      /*  Get each digit, starting with
      the least significant one and work
      backwards.  Add 48 to get the ASCII
      value of the digit.  */
      char_num = 48 + ( temp_num % 10 );
      temp_num /= 10;

      /*  Assign the characters into the
      array in reverse order.  */
      str_reverse[i] = (char) char_num;

      i++;
   }

   /*  If number is negative,
   add a negative sign.  */
   if( number < 0 )
   {
      str_reverse[i] = '-';
      i++;
   }

   if( number == 0 )
      i++;

   n_string.reserve( ( i + 1 ) * sizeof( char ) );

   i--;
   /*  i = the index of the last digit,
   or the negative sign  */

   for( j = 0; j <= i; j++ )
   {
      /*  Assign the characters into the
      permanent array in correct order.  */
      n_string.insert( (string::size_type)j, 1, str_reverse[i - j] );
   }

   return n_string;
}