MacHack 1998/MacHack 1998.toast/Programming Contest/~Solutions Submitted/Problem 01 - McMullen/Solution.cp

Text File | 1998-06-19 | 4.1 KB | 191 lines | [TEXT/CWIE]

/*
Problem 01 - Mode Sort

This problem is to sort an input string of N characters, N<1000000, based on
the number of times a character occurs in the input.  The most frequently
occurring character should be sorted to the front of the string, followed by
the next most frequently occurring character, etc.  For characters occurring
the same number of times, the character that occurs first in the input should
be sorted to the front.

Header specification

pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile );

Input specification

The infile input file contains the characters.  Input characters other than
those printable low ascii characters c, 0x20<c<0x7f, must be ignored.

Output specification

The outfile must be created and then filled with the sorted characters.  It's
final length should be exactly the same as the count of characters in the
allowed range (0x20<c<0x7f) (which may be shorter than the infile file length).

Sample input

abcdefghabbcccdddeee
or
012345678911234567892123456789312345678941234567895123456789612345678971234567891

Sample output

ccccddddeeeebbbaafgh
or
111111111122222222233333333344444444455555555566666666677777777788888888999999990
*/


#include <stdlib.h>
#include <string.h>

#include "myqsort.h"
#include "Solution.h"


// Fill in your solution and then submit this folder

// Team Name: No. 5

#define kFreqArrayLength        (0x7F - 0x20)
#define kCharStart                0x21

typedef struct
{
    long            freq;
    unsigned char    order;
    char            theChar;
} TCharFreq;


static OSErr SortFreqs(void *a, void *b, short *result)
{
    TCharFreq        *first = (TCharFreq *)a;
    TCharFreq        *second = (TCharFreq *)b;

    if (second->freq == first->freq)
        *result = (first->order - second->order);
    else
        *result = (second->freq - first->freq);
    return noErr;
}

pascal OSErr ModeSort( const FSSpec* infile, const FSSpec* outfile )
{
    short        fileRef = 0;
    short        outFileRef = 0;
    long        fileLength, outDataLength;
    long        i;
    TCharFreq    charFreqs[kFreqArrayLength];
    long        numValidChars = 0;
    Handle        dataHand = nil;
    Handle        outData = nil;
    OSErr        err;

    err = FSpOpenDF(infile, fsRdPerm, &fileRef);
    if (err != noErr) return err;

    // Get the length of the input file
    err = GetEOF(fileRef, &fileLength);
    if (err != noErr) return err;

    // Make a temp handle to hold the data
    dataHand = TempNewHandle(fileLength, &err);
    if (dataHand == nil) return memFullErr;

    HLock(dataHand);

    err = FSRead(fileRef, &fileLength, *dataHand);
    if (err != noErr) goto exit;
    HUnlock(dataHand);

    // zero the freq array
    for (i = 0; i < kFreqArrayLength; i ++)
    {
        charFreqs[i].theChar = kCharStart + i;
        charFreqs[i].order = 0;
        charFreqs[i].freq = 0;
    }

    // copy valid chars into the output handle
    {
        char            *src = *dataHand;
        char            *dst = *outData;
        unsigned char    ordinal = 0;

        for (i = 0; i < fileLength; i ++)
        {
            if (*src > 0x20 && *src < 0x7F)
            {
                short    index = *src - kCharStart;

                // is this a new one?
                if (charFreqs[index].freq == 0)
                {
                    charFreqs[index].order = ordinal;
                    ordinal ++;
                }

                charFreqs[index].freq ++;

                numValidChars ++;
            }

            *src ++;
        }

        outDataLength = dst - *outData;
    }


    outDataLength = numValidChars;
    outData = TempNewHandle(outDataLength, &err);
    if (outData == nil) return memFullErr;

    err = FastQSort(charFreqs, kFreqArrayLength, sizeof(TCharFreq), SortFreqs);
    if (err != noErr) return err;

    // dump the freqs into the output handle
    i = 0;
    HLock(outData);

    {
        char    *dst = *outData;
        long    j;

        do
        {
            for (j = 0; j < charFreqs[i].freq; j ++)
            {
                *dst ++ = charFreqs[i].theChar;
            }

            i ++;

        } while (charFreqs[i].freq > 0);

    }

    // delete the output file
    (void)FSpDelete(outfile);

    // create the output file
    err = FSpCreate(outfile, 'CWIE', 'TEXT', smSystemScript);
    if (err != noErr) return err;

    err = FSpOpenDF(outfile, fsRdWrPerm, &outFileRef);
    if (err != noErr) return err;

    err = FSWrite(outFileRef, &outDataLength, *outData);
    if (err != noErr) return err;
    DisposeHandle(outData);

    err = FSClose(outFileRef);

exit:
    if (dataHand != nil)
        DisposeHandle(dataHand);
    return err;
}