home *** CD-ROM | disk | FTP | other *** search
/ com!online 2002 May / comcd0502.iso / homepage / javaspecial / 03_01 / sitesearcher / AdvSiteSearcher / SearchSieve.java < prev   
Encoding:
Java Source  |  2000-08-18  |  6.0 KB  |  177 lines
  1. //AdvSiteSearcher c1999 The Gilbert Post by David Faden
  2. //The applet and code are distributed as linkware...
  3. //If you use this applet or a variant on its code,
  4. //include a link to The Gilbert Post, 
  5. //http://www.geocities.com/Athens/Parthenon/1911
  6. //The Gilbert Post and David Faden take no responsibility
  7. //for anything bad that happens as a result of using this applet
  8. //or a derivative based on its code. USE AT YOUR OWN RISK. (big letters)
  9. //Please send reports of problems to gilbertnews@hotmail.com, anyway, though.
  10.  
  11. //begin SearchSieve.java
  12. //The SearchSieve class is probably the most useful of any of the classes of AdvSiteSearcher...
  13. //It is designed with the idea of char stream in mind...there is a more efficient search method
  14. //which I'm thinking about
  15. public class SearchSieve {
  16.   private int num_matches;//how many matches have been found?
  17.   private int kposition;//current position in key
  18.   private char[] key;//search word/phrase
  19.   private boolean exact;//must the word be an exact match or
  20.   //can it be part of a larger word
  21.   private char prevc;//the previous char examined,
  22.   //if it's a word separator char, then the SearchSieve is passed -1
  23.   private int ambiguity_mark;//position of an ambiguous char in the buf
  24.   //amibiguous means the same as the first char of the key
  25.   private char[] buffer;//store chars as one sequence is examined in case
  26.   //the key starts at another spot within the chain
  27.   private int bufferlength;
  28.   private boolean buffering;
  29.   private char[] temp;
  30.   
  31.   //spaces needed if exact match option being used; need to know if there are 
  32.   //"spaces" around the "word"
  33.   //renamed defaultspaces to dspaces
  34.   private static final char[] dspaces={' ',
  35. '\n','\r', ',', '.','!','(',')','?','\t','\'','\"','=','+',':',';','{',
  36.   '}','[',']','\\','|', '<', '>', '/'};
  37.   /*private char[] spaces;
  38.   private int spaceslength;*/
  39.   
  40.   //This will not handle zero length arrays very gracefully
  41.   public SearchSieve(char[] c, boolean bexact) {
  42.     setKey(c,bexact);
  43.   }
  44.   
  45.   public void setKey(char[] c,boolean bexact) {
  46.     exact=bexact;
  47.     //reset();
  48.     key=new char[c.length];
  49.     System.arraycopy(c,0,key,0,c.length);
  50.     buffer=new char[key.length];
  51.     temp=new char[buffer.length];//temp is created here to 
  52.     //avoid the overhead of recreating it each time it is needed
  53.     bufferlength=0;
  54.     buffering=false;
  55.   }
  56.     
  57.   //This method needs more thought
  58.   public void reset() {
  59.     kposition=0;
  60.     num_matches=0;
  61.     prevc=(char)-1;//I think this may be equal to (char)0
  62.     //because -1 is all zeros in the lowest two bytes
  63.     bufferlength=0;//clear the buffer
  64.     buffering=false;
  65.   }
  66.   
  67.   public boolean addChar(char c) {
  68.     //if there's a match, return true
  69.     boolean matchfound=false;//left unchanged if nothing found
  70.     boolean eatthebuffer=false;
  71.     if(exact) {
  72.       if(kposition==key.length) {
  73.         //found a match
  74.         if(isSpace(c)) {
  75.           num_matches++;
  76.           matchfound=true;
  77.         }
  78.         kposition=0;
  79.         eatthebuffer=true;
  80.       }
  81.       else if(kposition==0) {
  82.         if(c==key[0] && isSpace(prevc)) kposition++;
  83.       }
  84.       else if(c==key[kposition]) kposition++;
  85.       else {
  86.         //found no match
  87.         kposition=0;
  88.         eatthebuffer=true;
  89.       }
  90.     }
  91.     //Inexact match check
  92.     else {
  93.       if(kposition==0) { if(c==key[0]) kposition++;}
  94.       else if(c==key[kposition]) kposition++;
  95.       else {
  96.         //no match found
  97.         kposition=0;
  98.         eatthebuffer=true;
  99.       }
  100.       if(kposition==key.length) {
  101.         num_matches++;
  102.         kposition=0;
  103.         eatthebuffer=true;
  104.         matchfound=true;
  105.       }
  106.     }
  107.     //a kposition of 1 indicates that one char match has been found
  108.     if(kposition>1 && !buffering && c==key[0]) {
  109.       if(!exact) {
  110.         bufferlength=0;
  111.         buffering=true;
  112.       }//if exact, matches have to be surrounded by spaces
  113.       else if(isSpace(prevc)) {
  114.         bufferlength=0;
  115.         buffering=true;
  116.       }
  117.     }
  118.     if(buffering) {
  119.       if(c==key[bufferlength]){
  120.         buffer[bufferlength]=c;
  121.         bufferlength++;
  122.       }
  123.       else {
  124.         bufferlength=0;
  125.         buffering=false;
  126.       }
  127.     }
  128.     if(eatthebuffer && bufferlength>0) eatTheBuffer();//feed the buffer back into the
  129.     //search system on failures and finds
  130.     prevc=c;
  131.     return matchfound;
  132.   }
  133.   
  134.   //Feed the buffer through addChar(char) as if it were being externally entered.
  135.   //No match can ever be found in the buffer alone, so there is
  136.   //no need to check the return of addChar(char).
  137.   //Huge problem with this method which will cause fatal error...
  138.   //Buffer itself may contain a second ambiguous char...
  139.   //However, if the buffer doesn't match up, it is overwritten
  140.   //When the next call to eatTheBuffer is made
  141.   //Idea, what if temp is made internal to eatTheBuffer?
  142.   //This could lead to a major memory leak, though...
  143.   //Fixed...breath easy now!
  144.   private void eatTheBuffer() {
  145.     //reset search
  146.     kposition=0;
  147.     /*char[] temp=new char[bufferlength];*/
  148.     System.arraycopy(buffer,0,temp,0,bufferlength);
  149.     int templength=bufferlength;//save the value of bufferlength
  150.     bufferlength=0;//reset the buffer
  151.     buffering=false;
  152.     //don't bother checking addChar(char) return value--can never be true
  153.     //in this case
  154.     for(int i=0;i<templength;i++) addChar(temp[i]);
  155.   }
  156.   
  157.   public int numOfMatches() {
  158.     return num_matches;
  159.   }
  160.   
  161.   //I'm not sure how much overhead this will add;
  162.   //changed so as to only be used with default dspaces
  163.   //It might actually pay to use a hash...
  164.   //we can avoid the synchronized methods of Hashtable
  165.   //since everything that we consider to be a space is with the ASCII range...
  166.   //so we can just store the info in an array with entries for every ASCII char...
  167.   //Something to put on the "to-do" list.
  168.   private boolean isSpace(char c) {
  169.     if(c==(char)-1) return true;
  170.     for(int i=0;i<dspaces.length;i++) {
  171.        if(c==dspaces[i]) return true;
  172.     }
  173.     return false;
  174.   }
  175.   
  176. }//end SearchSieve.java
  177.