_Algorithm Alley_
by Carlo Pescio

Listing One

void WordSet :: Reorder()
  {
  // reorder items in the set, so that if an item first and last letter
  // occurred before, the item is moved upward in the list. This heuristic
  // maximizes the likelihood that collisions are found early in the
  // assignment of values.

  const unsigned NO_OCCURRENCE = MAXINT ;
  for( unsigned i = 1; i < card; i++ )
    {
    const Word& w = *(set[ i ]) ;
    char first = w.First() ;
    char last = w.Last() ;
    unsigned firstOccurredIndex = NO_OCCURRENCE ;
    unsigned lastOccurredIndex = NO_OCCURRENCE ;
    for( unsigned j = 0; j < i; j++ )
      {
      const Word& prev = *(set[ j ]) ;
      if( lastOccurredIndex == NO_OCCURRENCE &&
          ( prev.Last() == last || prev.First() == last ) )
        lastOccurredIndex = j ;
      if( firstOccurredIndex == NO_OCCURRENCE &&
          ( prev.First() == first || prev.Last() == first ) )
        firstOccurredIndex = j ;
      if( firstOccurredIndex != NO_OCCURRENCE &&
          lastOccurredIndex != NO_OCCURRENCE )
        {
        // both letters occurred before: move the item upward, by pushing down
        // the ones between the maximum occurence index and the item index
        // itself. This preserve the original ordering as much as possible
        unsigned firstToMoveDown =
           max( firstOccurredIndex, lastOccurredIndex ) + 1 ;
        unsigned lastToMoveDown = i - 1 ;
        Word* itemToMoveUp = set[ i ] ;
        for( unsigned k = lastToMoveDown; k >= firstToMoveDown; k-- )
          set[ k + 1 ] = set[ k ] ;
        set[ firstToMoveDown ] = itemToMoveUp ;
        break ; // item 'i' handled
        }
      }
    }
  }


Listing Two

bool HashFinder :: Search( unsigned index )
  {
  const Word& w = words[ index ] ;
  if( value[ w.First() ] != NO_VALUE && value[ w.Last() ] != NO_VALUE )
    {
    // try to insert into the table     int h = Hash( w ) ;
    if( h < 0 || h >= maxTableSize || ! buckets.IsFree( h ) )
      return( FALSE ) ;
    else
      {
      buckets.MarkUsed( h ) ;
      index++ ;
      int card = words.Card() ;
      if( index == card )
        {
        cout << "------------\n" ;
        cout << "perfect hashing found\n" ;
        for( int i = 0; i < CHAR_MAX; i++ )
          if( value[ i ] != NO_VALUE )
            cout << (char)i << " = " << value[ i ] << "  " ;
        cout << endl ;
        for( i = 0; i < card; i++ )
          cout << words[ i ] << " = " << Hash( words[ i ] ) << endl ;
        // calculate and print loading factor
        int used = 0 ;
        for( i = 0; i < maxTableSize; i++ )
          if( ! buckets.IsFree( i ) )
            used++ ;
        cout << "loading factor: " << (float)used/maxTableSize << endl;

        // decide if it is time to stop now
        stopNow = stopFirst || ( used == maxTableSize && stopMinimal );

        buckets.MarkFree( h ) ; // restore for backtracking
        return( TRUE ) ;
        }
      else
        {
        bool res = Search( index ) ;
        buckets.MarkFree( h ) ; // restore for backtracking
        return( res ) ;
        }
      }
    }
  else if( value[ w.First() ] == NO_VALUE &&
           value[ w.Last() ] == NO_VALUE )
    {
    // must find values for both first and last;

    int firstValToAssign = w.First() ;
    int lastValToAssign = w.Last() ;
    bool found = FALSE ;
    for( int i = minVal; i < maxVal && ! stopNow; i++ )
      {
      value[ firstValToAssign ] = i ;
     // here we can change the heuristics: we already assigned one of
     // the values, so we have modified the boundaries.
     // Now we must have FirstFree <= to-assign + 'i' + len <= LastFree
      int minVal2 = buckets.FirstFree() - i - w.Len() ;
      int maxVal2 = buckets.LastFree() - i - w.Len() + 1 ;       for( int j = minVal2; j < maxVal2 && ! stopNow; j++ )
        {
        value[ lastValToAssign ] = j ;
        bool res = Search( index ) ;
        found = found ||  res ;
        }
      }
    value[ firstValToAssign ] = NO_VALUE ; // restore for backtracking
    value[ lastValToAssign ] = NO_VALUE ;
    return( found ) ;
    }
  else
    {
    // must find valid values for the one without values
    int valToAssign ;
    int valAssigned ;
    if( value[ w.First() ] == NO_VALUE )
      {
      valToAssign = w.First() ;
      valAssigned = w.Last() ;
      }
    else
      {
      valToAssign = w.Last() ;
      valAssigned = w.First() ;
      }

    // see above for heuristics used here
    int minVal2 = buckets.FirstFree() - value[ valAssigned ] - w.Len();
    int maxVal2 = buckets.LastFree() -value[valAssigned] - w.Len() + 1;

    assert( value[ valToAssign ] == NO_VALUE ) ;
    bool found = FALSE ;
    for( int i = minVal2; i < maxVal2 && ! stopNow; i++ )
      {
      value[ valToAssign ] = i ;
      bool res = Search( index ) ;  // will take first branch this time
      found = found ||  res ;
      }
    value[ valToAssign ] = NO_VALUE ; // restore for backtracking
    return( found ) ;
    }
  }