src/com/stevesoft/pat/FastMulti.java

   1 /*******************************************************************************
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $(date) The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  *******************************************************************************/
  21 //
  22 // This software is now distributed according to
  23 // the Lesser Gnu Public License.  Please see
  24 // http://www.gnu.org/copyleft/lesser.txt for
  25 // the details.
  26 //    -- Happy Computing!
  27 //
  28 package com.stevesoft.pat;
  29
  30 import java.util.Hashtable;
  31
  32 /**
  33  * A special case of Multi, implemented when minChars().equals(maxChars()), and
  34  * some other conditions spelled out in RegOpt.safe4fm "Safe for FastMulti." It
  35  * avoids stack growth problems as well as being slightly faster.
  36  */
  37 class FastMulti extends PatternSub
  38 {
  39   patInt fewestMatches, mostMatches;
  40
  41   public patInt minChars()
  42   {
  43     return sub.countMinChars().mul(fewestMatches);
  44   }
  45
  46   public patInt maxChars()
  47   {
  48     return sub.countMaxChars().mul(mostMatches);
  49   }
  50
  51   public boolean matchFewest = false;
  52
  53   FastMulti(patInt a, patInt b, Pattern p) throws RegSyntax
  54   {
  55     if (p == null)
  56     {
  57       RegSyntaxError.endItAll("Null length pattern "
  58               + "followed by *, +, or other Multi.");
  59     }
  60     fewestMatches = a;
  61     mostMatches = b;
  62     sub = p;
  63     step = p.countMinChars().intValue();
  64     sub.setParent(null);
  65   }
  66
  67   public String toString()
  68   {
  69     return sub.toString() + "{" + fewestMatches + "," + mostMatches + "}"
  70             + (matchFewest ? "?" : "") + "(?# <= fast multi)"
  71             + nextString();
  72   }
  73
  74   int step = -1;
  75
  76   public int matchInternal(int pos, Pthings pt)
  77   {
  78     int m = -1;
  79     int i = pos;
  80     int endstr = pt.src.length() - step;
  81     patInt matches = new patInt(0);
  82     if (matchFewest)
  83     {
  84       if (fewestMatches.lessEq(matches))
  85       {
  86         int ii = nextMatch(i, pt);
  87         if (ii >= 0)
  88         {
  89           return ii;
  90         }
  91       }
  92       while (i >= 0 && i <= endstr)
  93       {
  94         i = sub.matchInternal(i, pt);
  95         if (i >= 0)
  96         {
  97           matches.inc();
  98           if (fewestMatches.lessEq(matches))
  99           {
 100             int ii = nextMatch(i, pt);
 101             if (ii >= 0)
 102             {
 103               return ii;
 104             }
 105           }
 106           if (matches.equals(mostMatches))
 107           {
 108             return -1;
 109           }
 110         }
 111       }
 112       return -1;
 113     }
 114     int nMatches = 0;
 115     while (fewestMatches.intValue() > nMatches)
 116     {
 117       i = sub.matchInternal(i, pt);
 118       if (i >= 0)
 119       {
 120         nMatches++;
 121       }
 122       else
 123       {
 124         return -1;
 125       }
 126     }
 127     m = i;
 128     if (mostMatches.finite())
 129     {
 130       while (nMatches < mostMatches.intValue())
 131       {
 132         i = sub.matchInternal(i, pt);
 133         if (i >= 0)
 134         {
 135           m = i;
 136           nMatches++;
 137         }
 138         else
 139         {
 140           break;
 141         }
 142       }
 143     }
 144     else
 145     {
 146       while (true)
 147       {
 148         i = sub.matchInternal(i, pt);
 149         if (i >= 0)
 150         {
 151           m = i;
 152           nMatches++;
 153         }
 154         else
 155         {
 156           break;
 157         }
 158       }
 159     }
 160     while (m >= pos)
 161     {
 162       int r = nextMatch(m, pt);
 163       if (r >= 0)
 164       {
 165         return r;
 166       }
 167       m -= step;
 168       nMatches--;
 169       if (nMatches < fewestMatches.intValue())
 170       {
 171         return -1;
 172       }
 173     }
 174     return -1;
 175   }
 176
 177   public Pattern clone1(Hashtable h)
 178   {
 179     try
 180     {
 181       FastMulti fm = new FastMulti(fewestMatches, mostMatches, sub.clone(h));
 182       fm.matchFewest = matchFewest;
 183       return fm;
 184     } catch (RegSyntax rs)
 185     {
 186       return null;
 187     }
 188   }
 189 }