Algorithm Alley
by Mark R. Nelson

Listing One
string get_token( ifstream &file )
{
    string token;
    while ( file )
    {
        char c;
        file >> c;
        if ( isalpha( c ) || c == '\'' )
            token += c;
        else if ( token.size() )
            return token;
    }
    return token;
}

Listing Two
string token = get_token( infile );
if ( token.size() == 0 )
  break;
map< string, int >::const_iterator ii = frequency.find( token );
if ( ii == frequency.end() )
  frequency[ token ] = 1;
else
  frequency[ token ]++;

Listing Three
multimap<int, string> counts;
for ( map<string, int>::iterator ii = frequency.begin() ; 
      ii != frequency.end();
      ii++ )
  counts.insert( pair<int,string>( (*ii).second, (*ii).first ) )

Listing Four
set<string> used_codes;
for ( multimap<int, string>::reverse_iterator jj = counts.rbegin() ; 
      jj != counts.rend() ; 
      jj++ )
{
  string code = create_star_code( (*jj).second, used_codes );
  used_codes.insert( code );
  codes[ (*jj).second ] = code;
  cout << (*jj).second << " " << code << " " << (*jj).first << endl;
}

Listing Five
for ( int star_count = token.size() ; star_count > 0 ; star_count-- )
{
  vector<char> pattern( token.size(), '*' );
  for ( int i = star_count ; i < token.size() ; i++ )
    pattern[ i ] = '-';
  do 
  {
    string test( token );
    for ( int j = 0 ; j < token.size() ; j++ )
      if ( pattern[ j ] == '*' )
        test[ j ] = '*';
    set<string>::const_iterator kk = used_codes.find( test );
    if ( kk == used_codes.end() )
      return test;
  } while ( next_permutation( pattern.begin(), pattern.end() ) );
}
return token;

Listing Six
int star_code = 0;
for ( multimap< int, string >::reverse_iterator jj = counts.rbegin() ; 
      jj != counts.rend() ; 
      jj++ )
{
  string token = (*jj).second;
  if ( token.size() > 1 )
  {
    cout << token 
         << " " 
         << '*' 
         << star_code++ 
         << " " 
         << (*jj).first 
         << endl;
  }
}







2


