Back to index

scribus-ng  1.3.4.dfsg+svn20071115
Classes | Defines | Typedefs | Functions
hyphen.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  _HyphenDict
struct  _HyphenState
struct  _HyphenTrans

Defines

#define MAX_CHARS   256
#define MAX_NAME   20

Typedefs

typedef struct _HyphenDict
typedef struct _HyphenState
typedef struct _HyphenTrans

Functions

HyphenDict * hnj_hyphen_load (const char *fn)
void hnj_hyphen_free (HyphenDict *dict)
int hnj_hyphen_hyphenate (HyphenDict *dict, const char *word, int word_size, char *hyphens)

Class Documentation

struct _HyphenDict

Definition at line 55 of file hyphen.h.

Class Members
char cset
int num_states
HyphenState * states
struct _HyphenState

Definition at line 61 of file hyphen.h.

Class Members
int fallback_state
char * match
int num_trans
HyphenTrans * trans
struct _HyphenTrans

Definition at line 68 of file hyphen.h.

Class Members
char ch
int new_state

Define Documentation

#define MAX_CHARS   256

Definition at line 52 of file hyphen.h.

#define MAX_NAME   20

Definition at line 53 of file hyphen.h.


Typedef Documentation

typedef struct _HyphenDict

Definition at line 49 of file hyphen.h.

typedef struct _HyphenState

Definition at line 50 of file hyphen.h.

typedef struct _HyphenTrans

Definition at line 51 of file hyphen.h.


Function Documentation

void hnj_hyphen_free ( HyphenDict *  dict)

Definition at line 360 of file hyphen.c.

{
  int state_num;
  HyphenState *hstate;

  for (state_num = 0; state_num < dict->num_states; state_num++)
    {
      hstate = &dict->states[state_num];
      if (hstate->match)
       hnj_free (hstate->match);
      if (hstate->trans)
       hnj_free (hstate->trans);
    }

  hnj_free (dict->states);

  hnj_free (dict);
}

Here is the call graph for this function:

int hnj_hyphen_hyphenate ( HyphenDict *  dict,
const char *  word,
int  word_size,
char *  hyphens 
)

Definition at line 381 of file hyphen.c.

{
  char prep_word_buf[MAX_WORD];
  char *prep_word;
  int i, j, k;
  int state;
  char ch;
  HyphenState *hstate;
  char *match;
  int offset;

  if (word_size + 3 < MAX_WORD)
    prep_word = prep_word_buf;
  else
    prep_word = hnj_malloc (word_size + 3);

  j = 0;
  prep_word[j++] = '.';
  
  for (i = 0; i < word_size; i++)
      prep_word[j++] = word[i];
      
  for (i = 0; i < j; i++)                                                       
    hyphens[i] = '0';    
  
  prep_word[j++] = '.';

  prep_word[j] = '\0';
#ifdef VERBOSE
  printf ("prep_word = %s\n", prep_word);
#endif

  /* now, run the finite state machine */
  state = 0;
  for (i = 0; i < j; i++)
    {
      ch = prep_word[i];
      for (;;)
       {

         if (state == -1) {
            /* return 1;
            KBH: FIXME shouldn't this be as follows? */
            state = 0;
            goto try_next_letter;
          }          

#ifdef VERBOSE
         char *state_str;
         state_str = get_state_str (state);

         for (k = 0; k < i - strlen (state_str); k++)
           putchar (' ');
         printf ("%s", state_str);
#endif

         hstate = &dict->states[state];
         for (k = 0; k < hstate->num_trans; k++)
           if (hstate->trans[k].ch == ch)
             {
              state = hstate->trans[k].new_state;
              goto found_state;
             }
         state = hstate->fallback_state;
#ifdef VERBOSE
         printf (" falling back, fallback_state %d\n", state);
#endif
       }
    found_state:
#ifdef VERBOSE
      printf ("found state %d\n",state);
#endif
      /* Additional optimization is possible here - especially,
        elimination of trailing zeroes from the match. Leading zeroes
        have already been optimized. */
      match = dict->states[state].match;
      if (match)
       {
         offset = i + 1 - strlen (match);
#ifdef VERBOSE
         for (k = 0; k < offset; k++)
           putchar (' ');
         printf ("%s\n", match);
#endif
         /* This is a linear search because I tried a binary search and
            found it to be just a teeny bit slower. */
         for (k = 0; match[k]; k++)
           if (hyphens[offset + k] < match[k])
             hyphens[offset + k] = match[k];
       }

      /* KBH: we need this to make sure we keep looking in a word
       for patterns even if the current character is not known in state 0
       since patterns for hyphenation may occur anywhere in the word */
      try_next_letter: ;

    }
#ifdef VERBOSE
  for (i = 0; i < j; i++)
    putchar (hyphens[i]);
  putchar ('\n');
#endif

  for (i = 0; i < j - 4; i++)
#if 0
    if (hyphens[i + 1] & 1)
      hyphens[i] = '-';
#else
    hyphens[i] = hyphens[i + 1];
#endif
  hyphens[0] = '0';
  for (; i < word_size; i++)
    hyphens[i] = '0';
  hyphens[word_size] = '\0';

  if (prep_word != prep_word_buf)
    hnj_free (prep_word);
  return 0;    
}

Here is the call graph for this function:

HyphenDict* hnj_hyphen_load ( const char *  fn)

Definition at line 226 of file hyphen.c.

{
  HyphenDict *dict;
  HashTab *hashtab;
  FILE *f;
  char buf[80];
  char word[80];
  char pattern[80];
  int state_num, last_state;
  int i, j;
  char ch;
  int found;
  HashEntry *e;

  f = fopen (fn, "r");
  if (f == NULL)
    return NULL;

  hashtab = hnj_hash_new ();
#ifdef VERBOSE
  global = hashtab;
#endif
  hnj_hash_insert (hashtab, "", 0);

  dict = hnj_malloc (sizeof(HyphenDict));
  dict->num_states = 1;
  dict->states = hnj_malloc (sizeof(HyphenState));
  dict->states[0].match = NULL;
  dict->states[0].fallback_state = -1;
  dict->states[0].num_trans = 0;
  dict->states[0].trans = NULL;

  /* read in character set info */
  for (i=0;i<MAX_NAME;i++) dict->cset[i]= 0;
  fgets(dict->cset,  sizeof(dict->cset),f);
  for (i=0;i<MAX_NAME;i++)
    if ((dict->cset[i] == '\r') || (dict->cset[i] == '\n'))
        dict->cset[i] = 0;

  while (fgets (buf, sizeof(buf), f) != NULL)
    {
      if (buf[0] != '%')
       {
         j = 0;
         pattern[j] = '0';
         for (i = 0; ((buf[i] > ' ') || (buf[i] < 0)); i++)
           {
             if (buf[i] >= '0' && buf[i] <= '9')
              pattern[j] = buf[i];
             else
              {
                word[j] = buf[i];
                pattern[++j] = '0';
              }
           }
         word[j] = '\0';
         pattern[j + 1] = '\0';

         /* Optimize away leading zeroes */
         for (i = 0; pattern[i] == '0'; i++);

#ifdef VERBOSE
         printf ("word %s pattern %s, j = %d\n", word, pattern + i, j);
#endif
         found = hnj_hash_lookup (hashtab, word);

         state_num = hnj_get_state (dict, hashtab, word);
         dict->states[state_num].match = hnj_strdup (pattern + i);

         /* now, put in the prefix transitions */
         for (; found < 0 ;j--)
           {
             last_state = state_num;
             ch = word[j - 1];
             word[j - 1] = '\0';
             found = hnj_hash_lookup (hashtab, word);
             state_num = hnj_get_state (dict, hashtab, word);
             hnj_add_trans (dict, state_num, last_state, ch);
           }
       }
    }

  /* Could do unioning of matches here (instead of the preprocessor script).
     If we did, the pseudocode would look something like this:

     foreach state in the hash table
        foreach i = [1..length(state) - 1]
           state to check is substr (state, i)
           look it up
           if found, and if there is a match, union the match in.

     It's also possible to avoid the quadratic blowup by doing the
     search in order of increasing state string sizes - then you
     can break the loop after finding the first match.

     This step should be optional in any case - if there is a
     preprocessed rule table, it's always faster to use that.

*/

  /* put in the fallback states */
  for (i = 0; i < HASH_SIZE; i++)
    for (e = hashtab->entries[i]; e; e = e->next)
      {
/*     for (j = 1; 1; j++) */
       for (j = 1; *(e->key); j++)
         {
           state_num = hnj_hash_lookup (hashtab, e->key + j);
           if (state_num >= 0)
             break;
         }
        /* KBH: FIXME state 0 fallback_state should always be -1? */
       if (e->val) 
         dict->states[e->val].fallback_state = state_num;
      }
#ifdef VERBOSE
  for (i = 0; i < HASH_SIZE; i++)
    for (e = hashtab->entries[i]; e; e = e->next)
      {
       printf ("%d string %s state %d, fallback=%d\n", i, e->key, e->val,
              dict->states[e->val].fallback_state);
       for (j = 0; j < dict->states[e->val].num_trans; j++)
         printf (" %c->%d\n", dict->states[e->val].trans[j].ch,
                dict->states[e->val].trans[j].new_state);
      }
#endif

#ifndef VERBOSE
  hnj_hash_free (hashtab);
#endif
  fclose(f);
  return dict;
}

Here is the call graph for this function: