← Back to branch summary

~ubuntu-branches/ubuntu/feisty/ncbi-tools6/feisty

« back to all changes in this revision

Viewing changes to api/sqnutil2.c

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese
  • Date: 2006-12-07 15:02:17 UTC
  • mfrom: (1.1.6 upstream) (2.1.2 etch)
  • Revision ID: james.westby@ubuntu.com-20061207150217-dhkefi84mxhwof0l
Tags: 6.1.20061015-1ubuntu1
* Re-sync with Debian
* Re-add .desktop files from Phil Bull (Closes Malone: #36384)

Show diffs side-by-side

added added

removed removed

Lines of Context:
api/sqnutil2.c
29
29
*
30
30
* Version Creation Date:   9/2/97
31
31
*
32
 
* $Revision: 6.251 $
 
32
* $Revision: 6.264 $
33
33
*
34
34
* File Description: 
35
35
*
251
251
  return protRef;
252
252
}
253
253
 
254
 
NLM_EXTERN CdRegionPtr CreateNewCdRgn (Int2 frame, Boolean orf, Int2 genCode)
 
254
NLM_EXTERN CdRegionPtr CreateNewCdRgn (Uint1 frame, Boolean orf, Int2 genCode)
255
255
 
256
256
{
257
257
  CdRegionPtr  cdRgn;
763
763
  Boolean         partial5;
764
764
  Boolean         partial3;
765
765
  SeqLocPtr       slp;
766
 
  Int2            strand;
 
766
  Uint1           strand;
767
767
 
768
768
  if (target == NULL) return NULL;
769
769
  if (to == NULL && from == NULL) return NULL;
1843
1843
 
1844
1844
static CharPtr molinfo_biomol_list [] = {
1845
1845
  "?", "genomic", "precursor RNA", "mRNA", "rRNA", "tRNA", "snRNA",
1846
 
  "scRNA", "peptide", "other-genetic", "genomic-mRNA", "cRNA", "snoRNA", NULL
 
1846
  "scRNA", "peptide", "other-genetic", "genomic-mRNA", "cRNA", "snoRNA",
 
1847
  "transcribed RNA", NULL
1847
1848
};
1848
1849
 
1849
1850
static CharPtr molinfo_tech_list [] = {
2453
2454
  CharPtr  tmp;
2454
2455
 
2455
2456
  if (uop == NULL) {
2456
 
    uop = CreateStructuredCommentUserObject ();
 
2457
    uop = CreateStructuredCommentUserObject (prefix, suffix);
2457
2458
    if (uop == NULL) return uop;
2458
2459
  }
2459
2460
  if (str == NULL) return uop;
2928
2929
  Char        ch;
2929
2930
  Int2        i, j, k;
2930
2931
  CharPtr     str;
2931
 
  Char        tmp [1024];
 
2932
  Char        tmp [2048];
2932
2933
  ValNodePtr  vnp;
2933
2934
 
2934
2935
  vnp = NULL;
3638
3639
  return isProt;
3639
3640
}
3640
3641
 
 
3642
static Int4 CountBadChars (Int4Ptr bad_chars, Boolean include_warn)
 
3643
{
 
3644
  Int4 num_bad_chars = 0, i;
 
3645
  
 
3646
  for (i = 0; i < 255; i++)
 
3647
  {  
 
3648
        if (bad_chars [i] > 0)
 
3649
        {
 
3650
          if (include_warn || (i != '-' && i != '?' && i != ':' && !isdigit(i)))
 
3651
          {
 
3652
            num_bad_chars ++;
 
3653
          }
 
3654
        }
 
3655
  }
 
3656
  return num_bad_chars;
 
3657
}
 
3658
 
3641
3659
static Int4 ReportFlatFileDNABadChars (Int4Ptr bad_chars, CharPtr origline, CharPtr id_str)
3642
3660
{
3643
3661
  Int4    num_bad_chars = 0;
3647
3665
  CharPtr msg_format_single = "One illegal character (%c) was found %d times.";
3648
3666
  CharPtr msg_format_one = "'%c' (%d),";
3649
3667
  CharPtr msg_ptr;
 
3668
  Boolean   indexerVersion;
3650
3669
  
3651
 
  for (i = 0; i < 255; i++)
 
3670
  /* don't warn indexers about numbers */
 
3671
  indexerVersion = (Boolean) (GetAppProperty ("InternalNcbiSequin") != NULL);
 
3672
  if (indexerVersion)
3652
3673
  {
3653
 
    if (isdigit (i))
 
3674
    for (i = 0; i < 255; i++)
3654
3675
    {
3655
 
      /* don't report numbers as bad characters */
3656
 
      bad_chars [i] = 0;
 
3676
      if (isdigit (i))
 
3677
      {
 
3678
        /* don't report numbers as bad characters */
 
3679
        bad_chars [i] = 0;
 
3680
      }
3657
3681
    }
3658
 
  
3659
 
        if (bad_chars [i] > 0)
3660
 
        {
3661
 
          num_bad_chars ++;
3662
 
        }
3663
3682
  }
3664
3683
  
 
3684
  num_bad_chars = CountBadChars(bad_chars, TRUE);
 
3685
  
3665
3686
  if (num_bad_chars == 0) return 0;
3666
3687
  
3667
3688
  if (num_bad_chars == 1)
3698
3719
          *msg_ptr = 0;
3699
3720
        }
3700
3721
  }
3701
 
  Message (MSG_POSTERR, "%s", msg);
3702
 
 
3703
3722
  StringCpy (origline + 60, "...");
3704
3723
  origline [63] = '\0';
3705
 
  Message (MSG_POSTERR, "Offending line started at: %s", origline);
3706
 
  if (!StringHasNoText (id_str))
3707
 
  {
3708
 
    Message (MSG_POSTERR, "Sequence %s:", id_str);
 
3724
  if (indexerVersion) {
 
3725
    Message (MSG_POSTERR, "%s", msg);
 
3726
    Message (MSG_POSTERR, "Offending line started at: %s", origline);
 
3727
    if (!StringHasNoText (id_str))
 
3728
    {
 
3729
      Message (MSG_POSTERR, "Sequence %s:", id_str);
 
3730
    }
 
3731
  } else {
 
3732
    Message (MSG_ERROR, "Sequence %s: %s. Offending line started at: %s.",
 
3733
                        StringHasNoText (id_str) ? "no id provided" : id_str,
 
3734
                        msg,
 
3735
                        origline);
3709
3736
  }
 
3737
 
 
3738
  
 
3739
  num_bad_chars = CountBadChars (bad_chars, FALSE);
 
3740
  
3710
3741
  return num_bad_chars;  
3711
3742
}
3712
3743
 
4194
4225
      }
4195
4226
    }
4196
4227
  }
4197
 
  return res;
 
4228
  return (Char) res;
4198
4229
}
4199
4230
 
4200
4231
 
4311
4342
 
4312
4343
{
4313
4344
  Char    ch;
4314
 
  Int2    i;
 
4345
  Uint2    i;
4315
4346
  size_t  len;
4316
4347
 
4317
4348
  if (StringHasNoText (str)) return FALSE;
5064
5095
 
5065
5096
{
5066
5097
  Uint1           aa;
 
5098
  AffilPtr        affil;
 
5099
  AuthListPtr     alp;
5067
5100
  Boolean         bail;
5068
5101
  Uint1           codon [6];
5069
5102
  CdRegionPtr     crp;
 
5103
  CitSubPtr       csp;
5070
5104
  DbtagPtr        db;
5071
5105
  GBQualPtr       gbq;
5072
5106
  GeneRefPtr      grp;
5074
5108
  Boolean         isGeneDesc = FALSE;
5075
5109
  Boolean         isGeneSyn = FALSE;
5076
5110
  Boolean         isLocusTag = FALSE;
 
5111
  Boolean         isAuthor = FALSE;
 
5112
  Boolean         isAffil = FALSE;
 
5113
  Boolean         isMuid = FALSE;
 
5114
  Boolean         isPmid = FALSE;
5077
5115
  Int2            j;
5078
5116
  Boolean         justTrnaText;
5079
5117
  GBQualPtr       last;
5108
5146
    } else if (StringNCmp (qual, "locus_tag", 9) == 0) {
5109
5147
      qnum = GBQUAL_gene;
5110
5148
      isLocusTag = TRUE;
 
5149
    } else if (sfp->data.choice == SEQFEAT_PUB) {
 
5150
      if (StringICmp (qual, "pmid") == 0 || StringICmp (qual, "PubMed") == 0) {
 
5151
        isPmid = TRUE;
 
5152
      } else if (StringICmp (qual, "muid") == 0 || StringICmp (qual, "MEDLINE") == 0) {
 
5153
        isMuid = TRUE;
 
5154
      } else if (StringICmp (qual, "Author") == 0) {
 
5155
        isAuthor = TRUE;
 
5156
      } else if (StringICmp (qual, "Affil") == 0 || StringICmp (qual, "Affiliation") == 0) {
 
5157
        isAffil = TRUE;
 
5158
      }
5111
5159
    }
5112
5160
  }
5113
5161
  if (qnum == GBQUAL_evidence) {
5137
5185
          sfp->data.value.intvalue = j;
5138
5186
        }
5139
5187
      }
5140
 
    } else if (sfp->data.choice == SEQFEAT_PUB && (StringICmp (qual, "pmid") == 0 || StringICmp (qual, "PubMed") == 0)) {
5141
 
      if (sscanf (val, "%ld", &uid) == 1) {
 
5188
    } else if (sfp->data.choice == SEQFEAT_PUB) {
 
5189
      if (isPmid) {
 
5190
        if (sscanf (val, "%ld", &uid) == 1) {
 
5191
          pdp = (PubdescPtr) sfp->data.value.ptrvalue;
 
5192
          if (pdp != NULL) {
 
5193
            ValNodeAddInt (&(pdp->pub), PUB_PMid, (Int4) uid);
 
5194
          }
 
5195
        }
 
5196
      } else if (isMuid) {
 
5197
        if (sscanf (val, "%ld", &uid) == 1) {
 
5198
          pdp = (PubdescPtr) sfp->data.value.ptrvalue;
 
5199
          if (pdp != NULL) {
 
5200
            ValNodeAddInt (&(pdp->pub), PUB_Muid, (Int4) uid);
 
5201
          }
 
5202
        }
 
5203
      } else if (isAuthor || isAffil) {
5142
5204
        pdp = (PubdescPtr) sfp->data.value.ptrvalue;
 
5205
        csp = NULL;
5143
5206
        if (pdp != NULL) {
5144
 
          ValNodeAddInt (&(pdp->pub), PUB_PMid, (Int4) uid);
 
5207
          for (vnp = pdp->pub; vnp != NULL; vnp = vnp->next) {
 
5208
            if (vnp->choice == PUB_Sub) {
 
5209
              csp = (CitSubPtr) vnp->data.ptrvalue;
 
5210
              break;
 
5211
            }
 
5212
          }
 
5213
          if (csp == NULL) {
 
5214
            csp = CitSubNew ();
 
5215
            if (csp != NULL) {
 
5216
              csp->date = DateCurr ();
 
5217
              ValNodeAddPointer (&(pdp->pub), PUB_Sub, (Pointer) csp);
 
5218
            }
 
5219
          }
 
5220
          if (csp != NULL) {
 
5221
            alp = csp->authors;
 
5222
            if (alp == NULL) {
 
5223
              alp = AuthListNew ();
 
5224
              if (alp != NULL) {
 
5225
                alp->choice = 3;
 
5226
                csp->authors = alp;
 
5227
              }
 
5228
            }
 
5229
            if (alp != NULL) {
 
5230
              if (isAuthor) {
 
5231
                ValNodeCopyStr (&(alp->names), 3, val);
 
5232
              } else if (isAffil) {
 
5233
                affil = alp->affil;
 
5234
                if (affil == NULL) {
 
5235
                  affil = AffilNew ();
 
5236
                  alp->affil = affil;
 
5237
                }
 
5238
                if (affil != NULL) {
 
5239
                  affil->choice = 1;
 
5240
                  affil->affil = StringSave (val);
 
5241
                }
 
5242
              }
 
5243
            }
 
5244
          }
5145
5245
        }
5146
5246
      }
5147
5247
    } else if (sfp->data.choice == SEQFEAT_PUB && (StringICmp (qual, "muid") == 0 || StringICmp (qual, "MEDLINE") == 0)) {
5148
 
      if (sscanf (val, "%ld", &uid) == 1) {
5149
 
        pdp = (PubdescPtr) sfp->data.value.ptrvalue;
5150
 
        if (pdp != NULL) {
5151
 
          ValNodeAddInt (&(pdp->pub), PUB_Muid, (Int4) uid);
5152
 
        }
5153
 
      }
5154
5248
    } else if (sfp->data.choice == SEQFEAT_BIOSRC && ParseQualIntoBioSource (sfp, qual, val)) {
5155
5249
    } else if (sfp->data.choice == SEQFEAT_CDREGION && StringCmp (qual, "prot_desc") == 0) {
5156
5250
      xref = sfp->xref;
5534
5628
  SeqLocPtr   rsult = NULL;
5535
5629
  SeqIntPtr   sintp;
5536
5630
  SeqLocPtr   slp;
5537
 
  Int2        strand;
 
5631
  Uint1        strand;
5538
5632
  SeqLocPtr   tmp;
5539
5633
 
5540
5634
  if (sip == NULL) return NULL;
5723
5817
  Char           buf [128];
5724
5818
  CdRegionPtr    crp;
5725
5819
  AnnotDescrPtr  desc;
 
5820
  Boolean        endsinspace;
5726
5821
  CharPtr        feat;
5727
5822
  IntFuzzPtr     fuzz;
5728
5823
  GeneRefPtr     grp;
5729
5824
  Int2           idx;
5730
5825
  ImpFeatPtr     ifp;
5731
5826
  Boolean        isminus;
 
5827
  Boolean        isnote;
5732
5828
  Boolean        ispoint;
5733
5829
  Int2           j;
5734
5830
  CharPtr        label;
 
5831
  size_t         len;
5735
5832
  Char           line [2047];
5736
5833
  CharPtr        loc;
5737
5834
  Boolean        nonewline;
5767
5864
  str = FileCacheReadLine (fcp, line, sizeof (line), &nonewline);
5768
5865
  while (str != NULL) {
5769
5866
 
 
5867
    isnote = FALSE;
 
5868
    endsinspace = FALSE;
 
5869
    len = StringLen (str);
 
5870
    if (len > 2 && str [len - 1] == ' ') {
 
5871
      endsinspace = TRUE;
 
5872
    }
 
5873
 
5770
5874
    if (! HasNoText (line)) {
5771
5875
 
5772
5876
      if (StringNCmp (line, ">", 1) == 0 ||
5927
6031
              sfp->data.choice = SEQFEAT_SITE;
5928
6032
              sfp->data.value.intvalue = 255;
5929
6033
 
5930
 
            } else if (StringICmp (feat, "REFERENCE") == 0) {
 
6034
            } else if (StringICmp (feat, "REFERENCE") == 0 || StringICmp (feat, "CITSUB") == 0) {
5931
6035
 
5932
6036
              sfp->data.choice = SEQFEAT_PUB;
5933
6037
              pdp = PubdescNew ();
6007
6111
                    StringCmp (qual, "exception") == 0 ||
6008
6112
                    StringCmp (qual, "mitochondrion") == 0)) {
6009
6113
 
 
6114
          if (StringICmp (qual, "note") == 0) {
 
6115
            isnote = TRUE;
 
6116
          }
6010
6117
          AddQualifierToFeatureEx (sfp, qual, val, offset);
6011
6118
 
6012
6119
        } else if (sfp != NULL && qual != NULL && val == NULL) {
6036
6143
 
6037
6144
    }
6038
6145
 
6039
 
    /* if humongously long line (e.g., /note), truncate by ignoring */
 
6146
    /* if humongously long line /note, now extends by concatenation */
6040
6147
 
6041
6148
    while (nonewline && str != NULL) {
6042
6149
      str = FileCacheReadLine (fcp, line, sizeof (line), &nonewline);
 
6150
      if (isnote && sfp != NULL && StringDoesHaveText (str)) {
 
6151
        if (sfp->comment == NULL) {
 
6152
          sfp->comment = StringSave (val);
 
6153
        } else {
 
6154
          len = StringLen (sfp->comment) + StringLen (str) + 5;
 
6155
          tmp = MemNew (sizeof (Char) * len);
 
6156
          StringCpy (tmp, sfp->comment);
 
6157
          if (endsinspace) {
 
6158
            StringCat (tmp, " ");
 
6159
            endsinspace = FALSE;
 
6160
          }
 
6161
          StringCat (tmp, str);
 
6162
          sfp->comment = MemFree (sfp->comment);
 
6163
          sfp->comment = tmp;
 
6164
        }
 
6165
      }
6043
6166
    }
6044
6167
 
6045
6168
    pos = FileCacheTell (fcp);
6534
6657
reading the sequence (or object) and restoring the file pointer to the beginning of the
6535
6658
next record. */
6536
6659
 
6537
 
NLM_EXTERN Pointer ReadAsnFastaOrFlatFileEx (FILE *fp, Uint2Ptr datatypeptr, Uint2Ptr entityIDptr,
6538
 
                                           Boolean forceNuc, Boolean forceProt,
6539
 
                                           Boolean parseFastaSeqId, Boolean fastaAsSimpleSeq,
6540
 
                                           BoolPtr chars_stripped)
 
6660
NLM_EXTERN Pointer ReadAsnFastaOrFlatFileEx (
 
6661
  FILE *fp,
 
6662
  Uint2Ptr datatypeptr,
 
6663
  Uint2Ptr entityIDptr,
 
6664
  Boolean forceNuc,
 
6665
  Boolean forceProt,
 
6666
  Boolean parseFastaSeqId,
 
6667
  Boolean fastaAsSimpleSeq,
 
6668
  BoolPtr chars_stripped
 
6669
)
6541
6670
 
6542
6671
{
6543
6672
  AsnIoPtr       aip;
6651
6780
          fseek (fp, pos, SEEK_SET);
6652
6781
          aip = AsnIoNew (ASNIO_TEXT_IN, fp, NULL, NULL, NULL);
6653
6782
          aip->scan_for_start = TRUE;
 
6783
          SeqMgrHoldIndexing (TRUE);
6654
6784
          ptr = (*(omtp->asnread)) (aip, NULL);
 
6785
          SeqMgrHoldIndexing (FALSE);
6655
6786
          pos = AsnIoTell (aip);
6656
6787
          AsnIoFree (aip, FALSE);
6657
6788
          FileCacheSetup (&fc, fp);
7647
7778
        return head;
7648
7779
      }
7649
7780
 
 
7781
      if (line [0] == ']') {
 
7782
        ErrPostEx (SEV_ERROR, 0, 0, "Unbalanced square bracket in ReadDeltaLits");
 
7783
      
 
7784
        if (bs != NULL) {
 
7785
          ValNodeAddPointer (&head, 1, (Pointer) bs);
 
7786
        }
 
7787
 
 
7788
        return head;
 
7789
      }
 
7790
 
7650
7791
      if (line [0] == '>' && line [1] == '?') {
7651
7792
        if (bs != NULL) {
7652
7793
          ValNodeAddPointer (&head, 1, (Pointer) bs);
7884
8025
              SeqDescrAddPointer (&(bsp->descr), Seq_descr_title, (Pointer) title);
7885
8026
            }
7886
8027
 
7887
 
            bsp->id = MakeSeqID (seqid);
 
8028
            if (StringNICmp (seqid, "lcl|", 4) == 0 
 
8029
                ||StringNICmp (seqid, "gnl|", 4) == 0) {
 
8030
                bsp->id = SeqIdParse (seqid);
 
8031
            }
 
8032
            if (bsp->id == NULL) {
 
8033
              bsp->id = MakeSeqID (seqid);
 
8034
            }
7888
8035
            SeqMgrAddToBioseqIndex (bsp);
7889
8036
 
7890
8037
            if (entityIDptr != NULL) {
7989
8136
  return NULL;
7990
8137
}
7991
8138
 
 
8139
/* general purpose text finite state machine */
 
8140
/* based on Practical Algorithms for Programmers by Binstock and Rex */
 
8141
 
 
8142
typedef struct fsagoto {
 
8143
  Char             ch;
 
8144
  Int2             newstate;
 
8145
  struct fsagoto * next;
 
8146
} GotoItem, PNTR GotoPtr;
 
8147
 
 
8148
typedef struct fsastate {
 
8149
  GotoPtr       transition;
 
8150
  ValNodePtr    matchfound;
 
8151
  Int2          onfailure;
 
8152
} StateItem, PNTR StatePtr;
 
8153
 
 
8154
#define FAIL_STATE -1
 
8155
 
 
8156
static StatePtr GetState (
 
8157
  StatePtr PNTR stateTable,
 
8158
  Int2 state
 
8159
)
 
8160
 
 
8161
{
 
8162
  StatePtr  sp;
 
8163
 
 
8164
  sp = stateTable [state];
 
8165
  if (sp == NULL) {
 
8166
    sp = (StatePtr) MemNew (sizeof (StateItem));
 
8167
    stateTable [state] = sp;
 
8168
  }
 
8169
 
 
8170
  return sp;
 
8171
}
 
8172
 
 
8173
static Int2 GotoState (StatePtr PNTR stateTable, Int2 state,
 
8174
                       Char ch, Boolean zeroFailureReturnsZero)
 
8175
 
 
8176
{
 
8177
  GotoPtr   gp;
 
8178
  StatePtr  sp;
 
8179
 
 
8180
  sp = GetState (stateTable, state);
 
8181
  if (sp == NULL) return 0;
 
8182
 
 
8183
  for (gp = sp->transition; gp != NULL; gp = gp->next) {
 
8184
    if (gp->ch == ch) return gp->newstate;
 
8185
  }
 
8186
 
 
8187
  if (state == 0 && zeroFailureReturnsZero) return 0;
 
8188
 
 
8189
  return FAIL_STATE;
 
8190
}
 
8191
 
 
8192
/*
 
8193
#define FailState(stateTable,state) stateTable [state].onfailure
 
8194
*/
 
8195
 
 
8196
static Int2 FailState (
 
8197
  StatePtr PNTR stateTable,
 
8198
  Int2 state
 
8199
)
 
8200
 
 
8201
{
 
8202
  StatePtr  sp;
 
8203
 
 
8204
  sp = GetState (stateTable, state);
 
8205
  if (sp == NULL) return 0;
 
8206
 
 
8207
  return sp->onfailure;
 
8208
}
 
8209
 
 
8210
static void AddTransition (StatePtr PNTR stateTable, Int2 oldState,
 
8211
                           Char ch, Int2 newState)
 
8212
 
 
8213
{
 
8214
  GotoPtr   gp;
 
8215
  GotoPtr   prev;
 
8216
  StatePtr  sp;
 
8217
 
 
8218
  gp = (GotoPtr) MemNew (sizeof (GotoItem));
 
8219
  if (gp == NULL) return;
 
8220
 
 
8221
  gp->ch = ch;
 
8222
  gp->newstate = newState;
 
8223
 
 
8224
  sp = GetState (stateTable, oldState);
 
8225
  if (sp == NULL) return;
 
8226
 
 
8227
  prev = sp->transition;
 
8228
  if (prev == NULL) {
 
8229
    sp->transition = gp;
 
8230
  } else {
 
8231
    while (prev->next != NULL) {
 
8232
      prev = prev->next;
 
8233
    }
 
8234
    prev->next = gp;
 
8235
  }
 
8236
}
 
8237
 
 
8238
static void AddOutput (StatePtr PNTR stateTable, Int2 state, CharPtr word)
 
8239
 
 
8240
{
 
8241
  StatePtr    sp;
 
8242
  ValNodePtr  vnp;
 
8243
 
 
8244
  sp = GetState (stateTable, state);
 
8245
  if (sp == NULL) return;
 
8246
 
 
8247
  for (vnp = sp->matchfound; vnp != NULL; vnp = vnp->next) {
 
8248
    if (StringCmp (word, (CharPtr) vnp->data.ptrvalue) == 0) return;
 
8249
  }
 
8250
 
 
8251
  ValNodeCopyStr (&(sp->matchfound), 0, word);
 
8252
}
 
8253
 
 
8254
static Int2 EnterWord (StatePtr PNTR stateTable, CharPtr word,
 
8255
                       Int2 highState, Int2 maxState)
 
8256
 
 
8257
{
 
8258
  Char     ch;
 
8259
  Int2     next;
 
8260
  CharPtr  ptr;
 
8261
  Int2     state;
 
8262
 
 
8263
  state = 0;
 
8264
  next = 0;
 
8265
 
 
8266
  /* try to overlay beginning of word onto existing table */
 
8267
 
 
8268
  for (ptr = word, ch = *ptr; ch != '\0'; ptr++, ch = *ptr) {
 
8269
    next = GotoState (stateTable, state, ch, FALSE);
 
8270
    if (next == FAIL_STATE) break;
 
8271
    state = next;
 
8272
  }
 
8273
 
 
8274
  /* now create new states for remaining characters in word */
 
8275
 
 
8276
  for ( ; ch != '\0'; ptr++, ch = *ptr) {
 
8277
    highState++;
 
8278
    if (highState >= maxState) return highState;
 
8279
 
 
8280
    AddTransition (stateTable, state, ch, highState);
 
8281
    state = highState;
 
8282
  }
 
8283
 
 
8284
  /* at end of word record match information */
 
8285
 
 
8286
  AddOutput (stateTable, state, word);
 
8287
 
 
8288
  return highState;
 
8289
}
 
8290
 
 
8291
static void QueueAdd (Int2Ptr queue, Int2 qbeg, Int2 val)
 
8292
 
 
8293
{
 
8294
  Int2  q;
 
8295
 
 
8296
  q = queue [qbeg];
 
8297
  if (q == 0) {
 
8298
    queue [qbeg] = val;
 
8299
  } else {
 
8300
    for ( ; queue [q] != 0; q = queue [q]) continue;
 
8301
    queue [q] = val;
 
8302
  }
 
8303
  queue [val] = 0;
 
8304
}
 
8305
 
 
8306
static void FindFail (StatePtr PNTR stateTable, Int2 state,
 
8307
                      Int2 newState, Char ch)
 
8308
 
 
8309
{
 
8310
  Int2        next;
 
8311
  StatePtr    sp;
 
8312
  ValNodePtr  vnp;
 
8313
 
 
8314
  /* traverse existing failure path */
 
8315
 
 
8316
  next = GotoState (stateTable, state, ch, TRUE);
 
8317
 
 
8318
  while ((next = GotoState (stateTable, state, ch, TRUE)) == FAIL_STATE) {
 
8319
    state = FailState (stateTable, state);
 
8320
  }
 
8321
 
 
8322
  /* add new failure state */
 
8323
 
 
8324
  sp = GetState (stateTable, newState);
 
8325
  if (sp == NULL) return;
 
8326
 
 
8327
  sp->onfailure = next;
 
8328
 
 
8329
  /* add matches of substring at new state */
 
8330
 
 
8331
  sp = GetState (stateTable, next);
 
8332
  if (sp == NULL) return;
 
8333
 
 
8334
  for (vnp = sp->matchfound; vnp != NULL; vnp = vnp->next) {
 
8335
    AddOutput (stateTable, newState, (CharPtr) vnp->data.ptrvalue);
 
8336
  }
 
8337
}
 
8338
 
 
8339
static void ComputeFail (StatePtr PNTR stateTable, Int2Ptr queue, Int2 highState)
 
8340
 
 
8341
{
 
8342
  GotoPtr   gp;
 
8343
  Int2      qbeg, r, s, state;
 
8344
  StatePtr  sp;
 
8345
 
 
8346
  qbeg = 0;
 
8347
  queue [0] = 0;
 
8348
 
 
8349
  /* queue up states reached directly from state 0 (depth 1) */
 
8350
 
 
8351
  sp = GetState (stateTable, 0);
 
8352
  if (sp == NULL) return;
 
8353
 
 
8354
  for (gp = sp->transition; gp != NULL; gp = gp->next) {
 
8355
    s = gp->newstate;
 
8356
 
 
8357
    sp = GetState (stateTable, s);
 
8358
    if (sp == NULL) return;
 
8359
 
 
8360
    sp->onfailure = 0;
 
8361
    QueueAdd (queue, qbeg, s);
 
8362
  }
 
8363
 
 
8364
  while (queue [qbeg] != 0) {
 
8365
    r = queue [qbeg];
 
8366
    qbeg = r;
 
8367
 
 
8368
    /* depth 1 states beget depth 2 states, etc. */
 
8369
 
 
8370
    sp = GetState (stateTable, r);
 
8371
    if (sp == NULL) return;
 
8372
 
 
8373
    for (gp = sp->transition; gp != NULL; gp = gp->next) {
 
8374
      s = gp->newstate;
 
8375
      QueueAdd (queue, qbeg, s);
 
8376
 
 
8377
      /*
 
8378
         State   Substring   Transitions   Failure
 
8379
           2       st          a ->   3       6
 
8380
           3       sta         l ->   4
 
8381
           6       t           a ->   7       0
 
8382
           7       ta          p ->   8
 
8383
 
 
8384
         For example, r = 2 (st), if 'a' would go to s = 3 (sta).
 
8385
         From previous computation, 2 (st) fails to 6 (t).
 
8386
         Thus, check state 6 (t) for any transitions using 'a'.
 
8387
         Since 6 (t) 'a' -> 7 (ta), therefore set fail [3] -> 7.
 
8388
      */
 
8389
 
 
8390
      state = FailState (stateTable, r);
 
8391
      FindFail (stateTable, state, s, gp->ch);
 
8392
    }
 
8393
  }
 
8394
}
 
8395
 
 
8396
typedef struct TextFsa {
 
8397
  StatePtr PNTR  stateTable;
 
8398
  ValNodePtr     siteList;
 
8399
  Int2           highState;
 
8400
  Boolean        primed;
 
8401
} TextFsaData;
 
8402
 
 
8403
static void PrimeStateTable (TextFsaPtr tbl)
 
8404
 
 
8405
{
 
8406
  Int2           highState;
 
8407
  Int4           maxState;
 
8408
  Int2Ptr        queue;
 
8409
  StatePtr PNTR  stateTable;
 
8410
  ValNodePtr     vnp;
 
8411
  CharPtr        word;
 
8412
 
 
8413
  if (tbl == NULL || tbl->siteList == NULL || tbl->primed) return;
 
8414
 
 
8415
  for (maxState = 1, vnp = tbl->siteList; vnp != NULL; vnp = vnp->next) {
 
8416
    word = (CharPtr) vnp->data.ptrvalue;
 
8417
    maxState += StringLen (word);
 
8418
  }
 
8419
 
 
8420
  maxState++;
 
8421
  if (maxState > 32000) {
 
8422
    maxState = 32000;
 
8423
  }
 
8424
 
 
8425
  stateTable = (StatePtr PNTR) MemNew (sizeof (StatePtr) * (size_t) maxState);
 
8426
  queue = (Int2Ptr) MemNew (sizeof (Int2) * maxState);
 
8427
 
 
8428
  if (stateTable == NULL || queue == NULL) {
 
8429
    MemFree (stateTable);
 
8430
    MemFree (queue);
 
8431
    Message (MSG_POST, "FiniteStateSearch unable to allocate buffers");
 
8432
    return;
 
8433
  }
 
8434
 
 
8435
  for (highState = 0, vnp = tbl->siteList; vnp != NULL; vnp = vnp->next) {
 
8436
    word = (CharPtr) vnp->data.ptrvalue;
 
8437
    highState = EnterWord (stateTable, word, highState, maxState);
 
8438
  }
 
8439
 
 
8440
  if (highState >= maxState) {
 
8441
    ErrPostEx (SEV_ERROR, 0, 0, "FiniteStateSearch cannot handle more than %d states", (int) highState);
 
8442
  }
 
8443
 
 
8444
  ComputeFail (stateTable, queue, highState);
 
8445
 
 
8446
  MemFree (queue);
 
8447
 
 
8448
  tbl->stateTable = stateTable;
 
8449
  tbl->highState = highState;
 
8450
  tbl->primed = TRUE;
 
8451
}
 
8452
 
 
8453
NLM_EXTERN TextFsaPtr TextFsaNew (void)
 
8454
 
 
8455
{
 
8456
  TextFsaPtr  tbl;
 
8457
 
 
8458
  tbl = (TextFsaPtr) MemNew (sizeof (TextFsaData));
 
8459
  if (tbl == NULL) return NULL;
 
8460
  tbl->stateTable = NULL;
 
8461
  tbl->siteList = NULL;
 
8462
  tbl->primed = FALSE;
 
8463
  return tbl;
 
8464
}
 
8465
 
 
8466
NLM_EXTERN void TextFsaAdd (TextFsaPtr tbl, CharPtr word)
 
8467
 
 
8468
{
 
8469
  if (tbl == NULL) return;
 
8470
  ValNodeCopyStr (&(tbl->siteList), 0, word);
 
8471
}
 
8472
 
 
8473
NLM_EXTERN Int2 TextFsaNext (TextFsaPtr tbl, Int2 currState,
 
8474
                             Char ch, ValNodePtr PNTR matches)
 
8475
 
 
8476
{
 
8477
  Int2           next;
 
8478
  StatePtr       sp;
 
8479
  StatePtr PNTR  stateTable;
 
8480
 
 
8481
  if (matches != NULL) {
 
8482
    *matches = NULL;
 
8483
  }
 
8484
  if (tbl == NULL) return 0;
 
8485
  if (! tbl->primed) {
 
8486
    PrimeStateTable (tbl);
 
8487
  }
 
8488
  stateTable = tbl->stateTable;
 
8489
  if (stateTable == NULL) return 0;
 
8490
 
 
8491
  while ((next = GotoState (stateTable, currState, ch, TRUE)) == FAIL_STATE) {
 
8492
    currState = FailState (stateTable, currState);
 
8493
  }
 
8494
 
 
8495
  if (matches != NULL) {
 
8496
 
 
8497
    sp = GetState (stateTable, next);
 
8498
    if (sp == NULL) return next;
 
8499
 
 
8500
    *matches = sp->matchfound;
 
8501
  }
 
8502
 
 
8503
  return next;
 
8504
}
 
8505
 
 
8506
NLM_EXTERN TextFsaPtr TextFsaFree (TextFsaPtr tbl)
 
8507
 
 
8508
{
 
8509
  GotoPtr        gp;
 
8510
  Int2           highState;
 
8511
  GotoPtr        nxtgp;
 
8512
  StatePtr       sp;
 
8513
  Int2           state;
 
8514
  StatePtr PNTR  stateTable;
 
8515
 
 
8516
  if (tbl == NULL) return NULL;
 
8517
 
 
8518
  stateTable = tbl->stateTable;
 
8519
  if (stateTable != NULL) {
 
8520
    highState = tbl->highState;
 
8521
 
 
8522
    for (state = 0; state < highState; state++) {
 
8523
      sp = stateTable [state];
 
8524
      if (sp == NULL) continue;
 
8525
 
 
8526
      gp = sp->transition;
 
8527
      while (gp != NULL) {
 
8528
        nxtgp = gp->next;
 
8529
        MemFree (gp);
 
8530
        gp = nxtgp;
 
8531
      }
 
8532
 
 
8533
      ValNodeFreeData (sp->matchfound);
 
8534
      MemFree (sp);
 
8535
    }
 
8536
 
 
8537
    MemFree (stateTable);
 
8538
  }
 
8539
 
 
8540
  ValNodeFreeData (tbl->siteList);
 
8541
 
 
8542
  return MemFree (tbl);
 
8543
}
 
8544
 
 
8545
#if 0 /* original text fsa */
7992
8546
 
7993
8547
/* general purpose text finite state machine */
7994
8548
/* based on Practical Algorithms for Programmers by Binstock and Rex */
8314
8868
  return MemFree (tbl);
8315
8869
}
8316
8870
 
 
8871
#endif /* original text fsa */
 
8872
 
8317
8873
/* sequence quality exchange */
8318
8874
 
8319
8875
typedef struct gphgetdata {